RATE MATCHING IN POLAR CODES

Abstract

A communication apparatus includes: an encoder that encodes an input vector to output a codeword of polar code; a memory that stores a reliability-ordered sequence of indices of the input vector and a set of indices for rate-matching; a controller that is configured to: select a frozen set of indices based on at least one of a universal rate-matching scheme and the reliability-ordered sequence stored in the memory such that the reliability-ordered sequence is generated without considering the rate-matching scheme; construct the input vector by setting the frozen set to a frozen bit and a non-frozen set to information bits; and skip codebits of the codeword outputted by the encoder from transmission, the codebits corresponding respectively to the set of indices for rate-matching.

Claims

1. A communication apparatus comprising: an encoder that encodes an input vector to output a codeword of polar code; a memory that stores a reliability-ordered sequence of indices of the input vector and a set of indices for rate-matching; a controller that is configured to: select a frozen set of indices based on at least one of a universal rate-matching scheme and the reliability-ordered sequence stored in the memory such that the reliability-ordered sequence is generated without considering the rate-matching scheme; construct the input vector by setting the frozen set to a frozen bit and a non-frozen set to information bits; and skip the transmission of those codebits of the codeword outputted by the encoder that correspond respectively to the set of indices for rate-matching.

2. The communication apparatus according to claim 1, wherein the memory previously stores a reference sequence which is a reliability-ordered sequence of a length greater or small or same as that of the reliability-ordered sequence, wherein the reliability-ordered sequence is derived from the reference sequence when their lengths are not same.

3. The communication apparatus according to claim 1, wherein the universal rate-matching scheme is a rate-matching scheme and pattern which satisfies at least one of the following: It does not change a content of the non-frozen set significantly with and without rate-matching consideration; and the error correcting performance produced by a rate-matched polar codes encoded using a sequence generated for non-rate-matched polar codes is very similar to that generated using a sequence optimized for the rate-matching scheme.

4. The communication apparatus according to claim 1, wherein a specific rate-matching scheme is one of universal rate-matching schemes on condition that first error correcting performance of a polar code obtained according to reliability values optimized to the specific rate-matching scheme is substantially same as second error correcting performance of a polar code obtained according to reliability values which are generated without considering the specific rate-matching scheme.

5. The communication apparatus according to claim 1, wherein the universal rate-matching scheme is a bit-reversal shortening scheme.

6. The communication apparatus according to claim 5, wherein the bit-reversal shortening scheme is at least one of the following: the last N-M bits of the codeword are not transmitted and the indices of the input vector to the encoder obtained by bit reversal permutation of the last N-M indices are set to a known value, when the encoder is of the form
c=uBG.sub.2.sup..Math.n (Math. 1) and the indices of the codeword obtained by bit reversal permutation of the last N-M indices are not transmitted and the indices of the input vector to the encoder obtained by bit reversal permutation of the last N-M indices are set to a known value, when the encoder is of the form
c=uG.sub.2.sup..Math.n. (Math. 2)

7. The communication apparatus according to claim 1, wherein the controller is configured to select the frozen set by: selecting at least N-M indices of the input vector of length N corresponding to N-M codebits that are not transmitted in the rate-matching scheme, ; and storing the selected N-M indices into the frozen set, wherein N is a length of the polar code before rate-matching and M is a length of the polar code after rate-matching.

8. The communication apparatus according to claim 1, wherein the controller is configured to select the frozen set by: selecting indices from the input vector which are bit-reversal permutation of the last N-M indices and including them in the frozen set; and in response to determining that number of indices of the frozen set is smaller than N-K, selecting shortfall indices from the reliability-ordered sequence stored in the memory that have lower reliability than the remaining indices in the memory, where K is number of information bits.

9. The communication apparatus according to claim 7, wherein the controller is configured to: in response to determining that number of indices of the frozen set is smaller than N-K, select shortfall indices from the reliability-ordered sequence stored in the memory that have lower reliability than the remaining indices in the memory, where K is number of information bits.

10. A rate matching method for a communication apparatus which comprises: an encoder that encodes an input vector to output a codeword of polar code; and a memory that stores a reliability-ordered sequence of indices of the input vector and a set of indices for rate-matching, the method comprising: selecting a frozen set of indices based on at least one of a universal rate-matching scheme and the reliability-ordered sequence stored in the memory such that the reliability-ordered sequence is generated without considering the rate-matching scheme; constructing the input vector by setting the frozen set to a frozen bit and a non-frozen set to information bits; and skipping codebits of the codeword outputted by the encoder from transmission, the codebits corresponding respectively to the set of indices for rate-matching.

11. The rate matching method according to claim 10, wherein the memory previously stores a reference sequence which is a reliability-ordered sequence of a length greater or small or same as that of the reliability-ordered sequence, wherein the reliability-ordered sequence is derived from the reference sequence when their lengths are not same.

12. The rate matching method according to claim 10, wherein the universal rate-matching scheme is a rate-matching scheme and pattern which satisfies at least one of the following: it does not change a content of the non-frozen set significantly between with and without rate-matching consideration; and the error correcting performance produced by a rate-matched polar codes encoded using a sequence generated for non-rate-matched polar codes is very similar to that generated using a sequence optimized for the rate-matching scheme.

13. The rate matching method according to claim 10, wherein a specific rate-matching scheme is one of universal rate-matching schemes on condition that first error correcting performance of a polar code obtained according to reliability values optimized to the specific rate-matching scheme is substantially same as second error correcting performance of a polar code obtained according to reliability values which are generated without considering the specific rate-matching scheme.

14. The rate matching method according to claim 10, wherein the universal rate-matching scheme is a bit-reversal shortening scheme.

15. The rate matching method according to claim 14, wherein the bit-reversal shortening scheme is at least one of the following: the last N-M bits of the codeword are not transmitted and the indices of the input vector to the encoder obtained by bit reversal permutation of the last N-M indices are set to a known value, when the encoder is of the form
c=uBG.sub.2.sup..Math.n (Math. 3) and the indices of the codeword obtained by bit reversal permutation of the last N-M indices are not transmitted and the indices of the input vector to the encoder obtained by bit reversal permutation of the last N-M indices are set to a known value, when the encoder is of the form
c=uG.sub.2.sup..Math.n. (Math. 4)

16. The rate matching method according to claim 10, wherein the frozen set is selected by: selecting at least N-M indices of the input vector of length N corresponding to N-M codebits that are not transmitted in the rate-matching scheme; and storing the selected N-M indices into the frozen set, wherein N is a length of the polar code before rate-matching and M is a length of the polar code after rate-matching.

17. The rate matching method according to claim 10, wherein the frozen set is selected by: selecting indices from the input vector which are bit-reversal permutation of the last N-M indices and including them in the frozen set; and in response to determining that number of indices of the frozen set is smaller than N-K, selecting shortfall indices from the reliability-ordered sequence stored in the memory that have lower reliability than the remaining indices in the memory, where K is number of information bits.

18. The rate matching method according to claim 16, wherein the frozen set is selected by: in response to determining that number of indices of the frozen set is smaller than N-K, selecting shortfall indices from the reliability-ordered sequence stored in the memory that have lower reliability than the remaining indices in the memory, where K is number of information bits.

19. A non-transitory recording medium that stores a program for controlling a communication apparatus which comprises: an encoder that encodes an input vector to output a codeword of polar code; and a memory that stores a reliability-ordered sequence of indices of the input vector and a set of indices for rate-matching, the program comprising a set of instructions to: select a frozen set of indices based on at least one of a universal rate-matching scheme and the reliability-ordered sequence stored in the memory such that the reliability-ordered sequence is generated without considering the rate-matching scheme; construct the input vector by setting the frozen set to a frozen bit and a non-frozen set to information bits; and skip codebits of the codeword outputted by the encoder from transmission, the codebits corresponding respectively to the set of indices for rate-matching.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0020] FIG. 1 is a schematic diagram illustrating an encoding operation in polar codes according to an exemplary embodiment of the present invention.

[0021] FIG. 2 is a flowchart illustrating an operation of reliability-ordered sequence design without considering rate-matching scheme and pattern at the sender device.

[0022] FIG. 3 is a flowchart illustrating an operation of reliability-ordered sequence design optimized based on puncturing scheme and pattern at the sender device.

[0023] FIG. 4 is a flowchart illustrating an operation of reliability-ordered sequence design optimized based on bit-reversal shortening scheme and pattern at the sender device.

[0024] FIG. 5 illustrates BLER-SNR graphs showing universality property of bit-reversal shortening and non-universality of block puncturing.

[0025] FIG. 6 is a schematic diagram illustrating a functional configuration of a sender device according to an exemplary embodiment of the present invention.

[0026] FIG. 7A is a flowchart illustrating an operation of constructing (M, K) rate-matched polar code at the sender device according to the exemplary embodiment of the present invention.

[0027] FIG. 7B is a flowchart illustrating an operation of frozen set selection according to the exemplary embodiment of the present invention.

[0028] FIG. 8 is a schematic diagram illustrating a functional configuration of a receiver device according to the exemplary embodiment.

[0029] FIG. 9 is a diagram illustrating another architecture of a communication device according to the exemplary embodiment of the present invention.

DETAILED DESCRIPTION

[0030] Hereinafter, the word exemplary is used herein to mean serving as an example, instance, or illustration. Any embodiment described herein as exemplary is not necessarily to be construed as preferred or advantageous over other embodiments.

1. Outline of Exemplary Embodiments

[0031] The above-discussed technical problems can be solved by one or more variants of the exemplary embodiments of the present invention. In this present disclosure, design of a rate-matched polar code system will be explained. It is assumed that the terms scheme, pattern and parameters used in the present disclosure imply the followings: [0032] Scheme: puncturing, shortening, repetition etc.; [0033] Pattern: natural order, bit-reversal, pseudorandom etc.; and [0034] Parameter: M, K, K/M, wherein M is the number of transmitted codebits (M is not a power of two), and K is the number of information bits.

[0035] Bit-reversal order permutation may be understood as the following: If (b.sub.db.sub.d1. . . b.sub.0) be the binary representation of a decimal number x, then the decimal number represented by (b.sub.0. . . b.sub.d1b.sub.d) may be regarded as the bit-reversal of x.

1.1) Universal Rate-Matching Scheme

[0036] A basic procedure for (N, K) polar code encoding is as follows: [0037] Store reliability-based ordering of all N (=2.sup.n) indices; [0038] Divide N indices of input vector U into a frozen set and a non-frozen set based on reliabilities of indices, [0039] Put information bits at the K high reliable indices and frozen bit (e.g. 0) at the N-K low reliable indices to construct an input vector; and [0040] Encode by multiplying the input vector U with a bit-reversal permutation matrix B and the generator matrix

G.sub.2.sup..Math.n (Math. 2)

which may be n-times Kronecker product of the polarizing kernel G.sub.2. Thus the encoding operation may be written as

c=uBG.sub.2.sup..Math.n (Math. 3)

where c is generated codeword, u is input to the encoder.

[0041] When constructing (M, K) rate-matched polar code, however, the reliability ordering of N indices cannot be used normally because the reliability-based ordering may change when puncturing or shortening is considered. As described before, a conventional solution to this problem is to regenerate the sequence based on rate-matching scheme and code parameters.

[0042] In contrast, according to a novel solution to the problem, a puncturing or shortening scheme which does not change the reliability ordering of indices significantly is used to construct a rate-matched polar code with at least a single pre-computed sequence. Such a scheme may have a special feature that causes no significant change in sequence design with and without rate-matching consideration. Hereinafter, the scheme having such a special feature is referred to as a universal rate-matching scheme or a universally exploitable rate-matching scheme.

[0043] A universal rate-matching scheme can be found by comparing error correcting performance of rate-matched polar code with and without sequence redesign (i.e., using sequence designed for non-rate-matched polar code and using another sequence that is designed based on the used rate-matching scheme) after applying a puncturing or shortening scheme. If the error correcting performance of the rate-matched polar code with and without sequence redesign is very similar to each other or substantially overlaps, the applied scheme can be used as a universal rate-matching scheme. In other words, the universal rate-matching scheme may allow the reliability-based ordering of indices without considering rate-matching to be very similar to that optimized to rate-matching. Accordingly, the same sequence design can be used for non-rate-matched polar codes and can be used even for rate-matched polar codes, resulting in no need of sequence redesign. More details will be described later.

1.2) Construction of (M, K) Rate-Matched Polar Code

[0044] As illustrated in FIG. 1, an encoding procedure in polar codes according to the present invention has the feature that the sequence design can be performed without considering rate-matching, resulting in no need to design a sequence for every change in rate-matching parameter.

[0045] More specifically, the encoding procedure for (M, K) rate-matched polar code is as follows: [0046] S101: Estimate reliabilities of N.sub.ref indices without considering any rate-matching scheme and sort the indices according to reliability for each index, wherein N.sub.ref is 2.sup.n, n is a positive integer and Store this reliability based ordering of N.sub.ref indices in memory. [0047] S102: Obtain the reliability-based ordering of N indices of an input vector assuming no rate-matching scheme from the reference sequence N.sub.ref, where N can be longer, shorter or of same length as N.sub.ref. [0048] S103: Use the universal rate-matching pattern and the reliability-based ordering of N indices obtained in S102 to select a frozen set and a non-frozen set. [0049] S104: Construct the input vector to the encoder of polar code based on the frozen set and the non-frozen set. [0050] S105: Encode by multiplying the input vector with the generator matrix to output a rate-matched codeword. A bit-reversal permutation matrix B may also be multiplied.

1.3) Advantages

[0051] As described above, by using the universal rate-matching scheme, it is possible to continue using the pre-stored reliability-ordered sequence of indices (that has been generated without considering rate-matching) for selecting the frozen and non-frozen sets of indices. This solves the problem of designing optimized reliability-ordered sequence of indices corresponding to each rate-matching pattern and scheme. Thus the implementation of a rate-matched polar code system becomes significantly simpler.

2. Universality Property

2.1) Reliability-Ordered Sequence Design

[0052] The reliabilities of indices can be calculated by Density Evolution (DE) based on Gaussian Approximation (GA) as explained in NPL 3 but other methods are not precluded. Hereinafter, how the estimation of reliability of each index in the input vector of length N is made (assuming the case that N is same as N.sub.ref as an example for ease of understanding) will be described in the following cases: without rate-matching consideration; and with rate-matching consideration (block puncturing, bit-reversal shortening, etc).

<Sequence Design with No Rate-Matching Consideration>

[0053] As illustrated in FIG. 2, the reliability values of the bit indices in input vector are estimated without taking into account any rate-matching scheme or pattern. The initial channel output likelihood values corresponding to each codebit index may be set to the same value using the noise variance of the underlying channel (Operation S201), for instance, an Additive White Gaussian Noise (AWGN) channel. The reliabilities of the indices in the input vector can then be estimated using the DE based on GA (Operation S202). The indices are then sorted based on their reliability values to obtain a reliability-based sequence SEQO (Operation S203).

<Sequence Design for Block Puncturing>

[0054] As illustrated in FIG. 3, the reliability values of the bit indices are estimated with block puncturing. First, the codebit indices that would not be transmitted in a chosen puncturing scheme are selected (Operation S301). For instance, a block puncturing scheme may select the codebits with indices which are bit-reversal of the first N-M indices and skip the transmission of these codebits when the encoder is of the form

BG.sub.2.sup..Math.n. (Math. 4)

The LLR values at the codebit indices selected in S301 are set to very small value (e.g. 0) and the values at the remaining indices are kept the same value as in S201 (Operation S302). The reliabilities of the indices in the input vector can then be estimated using the DE based on GA (Operation S403). The indices of input vector are then sorted based on their reliability values to obtain a reliability-based sequence SEQ1 (Operation S304). When estimating the reliabilities with block puncturing, the resultant reliability-based sequence SEQ1 may be changed from the reliability-based sequence SEQ0 obtained in the case of no rate-matching consideration. Accordingly, block puncturing shows degraded block error rate (BLER) performance if new reliability ordering is not done.
<Sequence Design with Bit-Reversal Shortening>

[0055] As illustrated in FIG. 4, the reliability values of the bit indices are estimated with bit-reversal shortening. First, the codebit indices that would not be transmitted in a chosen shortening scheme are selected (Operation S401). The channel output likelihood values at the codebit indices selected in S401 are set to very large value (e.g. infinity) and the values at the remaining indices are kept the same value as in S201 (Operation S402). The reliabilities of the indices in the input vector can then be estimated using the DE based on GA (Operation S403). The indices are then sorted based on their reliability values to obtain a reliability-based sequence SEQ2 (Operation S404). When estimating the reliabilities with bit-reversal shortening, the resultant reliability-based sequence SEQ2 may be approximately similar to the reliability-based sequence SEQ0 obtained in the case of no rate-matching consideration. Accordingly, the bit-reversal shortening can be used as a universal rate-matching scheme.

2.2) Example of Universal Rate-Matching Scheme

[0056] As described above, the bit-reversal shortening may be an example of the universal rate-matching scheme because it has the universality property such that the reliability-based sequence is not changed by much and therefore new reliability ordering of indices optimized for a specific rate-matching scheme may not be required.

[0057] In the case of the bit-reversal shortening, as compared to the block puncturing, the BLER performance is almost the same with redesign as without redesign as illustrated in FIG. 5.

[0058] In the case where a bit-reversal shortening pattern is used, a set of N-M indices of a codeword can be skipped from transmission so as to transmit a relatively short-length rate-matched polar code. For one example of the bit-reversal shortening pattern, the last N-M indices (i.e., {N-M+1, . . . , N1}) of a codeword may be skipped from transmission, where the set of all indices in the codeword is denoted as {0, 1, . . . , N1}. If a polar encoder of the form

c=uG.sub.2.sup..Math.n (Math. 5)

is used, then the bit-reversal permutation of the last N-M indices may be skipped from transmission. Other examples of a bit-reversal shortening pattern are also not precluded.

[0059] Next, taking the bit-reversal shortening pattern as an example of the universal rate-matching scheme, an exemplary embodiment of the present invention will be described in detail.

3. Exemplary Embodiment

[0060] Hereinafter, an exemplary embodiment of the present invention will be discussed in its complete details with accompanying figures. The embodiment described herein is only illustrative of some specific representations of the invention acknowledging the fact that the inventive concepts can be embodied in a wide variety of contexts. Thus the exemplary embodiment does not limit the scope of the present invention.

3.1) Sender Device

[0061] As illustrated in FIG. 6, a sender device 601 is provided with data sending functions including a message source 602, a Forward Error Correction (FEC) encoder 603 of encoding scheme for Polar Codes, a first memory 604 that stores at least one reliability-ordered sequence of indices, a second memory 605 that stores a bit-reversal shortening pattern as a universal rate-matching scheme, and a controller 606 that selects the frozen set 607 and non-frozen set 608 and constructs the input vector for encoding at the FEC encoder 603. The controller 606 or a separate controller may control which bits are skipped from the encoder output by referring to the bit-reversal shortening pattern stored in the second memory 605. In the present exemplary embodiment, the second memory 605 stores a bit-reversal shortening pattern as an example of the universal rate-matching scheme.

[0062] The controller 606 uses a frozen set memory 607 and a non-frozen set memory 608 to select or store a frozen set and a non-frozen set of indices using the at least one sequence stored in the first memory 604 and the bit-reversal shortening pattern store in the second memory 605. A modulator 609 modulates the rate-matched polar code and then sends it to a radio-frequency (RF) unit for transmission (not shown). The functions of the sender device 601, including functions of generating the reliability-ordered sequence and the bit-reversal shortening pattern and of the polar code encoding, may be implemented on a processor running respective programs stored in a memory device (not shown).

[0063] The message source 602 generates some information bits that need to be encoded and then transmitted. The FEC encoder 603 may encode an input vector u using the following equation:

c=uBG.sub.2.sup..Math.n (Math. 6)

where c is a codeword of polar codes, u is input vector to the encoder, B is a NN bit-reversal permutation matrix, and

G.sub.2.sup..Math.n (Math. 7)

is an n-Kronecker product of a polarizing kernel G.sub.2.

[0064] The first memory 604 stores at least one reliability-ordered sequence of indices that is generated without taking into consideration the change in reliability values of indices resulting from rate-matching. Such a reliability-ordered sequence of indices may be generated by estimating the reliability values of the indices (see S701 of FIG. 7A) using a method like DE based on GA. The indices may then be sorted according to their reliability values (see S702 of FIG. 7A) and stored in the first memory 604.

[0065] The second memory 605 stores the bit-reversal shortening pattern as a universal rate-matching pattern that can be used to construct a short length polar codes without significantly changing reliability ordering of indices. The bit-reversal shortening pattern may be a set of N-M indices that can be skipped from transmission so as to transmit a relatively short-length rate-matched polar code. For one example of the bit-reversal shortening pattern, the last N-M indices (i.e., {N-M+1, . . . , N1}) of a codeword may be employed, where the codeword may be denoted as {0, 1, . . . , N1}.

[0066] For bit-reversal shortening, the bit-reversal permuted values of the set of {N-M+1, . . . , N1} are included in the frozen set 607. The remaining indices of the frozen set 607 may be chosen from the at least one reliability-ordered sequence stored in the first memory 604.

[0067] Once the frozen set 607 is completely selected by the controller 606, it can select the non-frozen set 608 as the set difference of {0, 1, . . . , N1} and the frozen set. The controller 606 can then set information bits (received from message source 602) at the indices contained in the non-frozen set 608 and frozen bits (for e.g., 0) at the indices contained in the frozen set 607 to construct the input vector. The input vector thus designed is fed as input to the FEC encoder 603, which encodes the input vector into a polar codeword. The controller 606 refers to the bit-reversal shortening pattern stored in the second memory 605 for skipping the last N-M indices of the generated codeword from transmission to output a rate-matched polar codeword to the modulator 609. An outline of constructing a rate-matched polar codeword employing a universal rate-matching scheme will be described with reference to FIG. 7.

3.2) Construction of Rate-Matched Polar Codes

[0068] As illustrated in FIGS. 7A and 7B, an (M, K) rate-matched polar codeword is constructed using a bit-reversal shortening pattern. The reliability value of each index in input vector is estimated using DE based on GA (Operation S701). For instance, the initial LLR values corresponding to the channel outputs which are fed as input to the Density Evolution block may be all set to the same value based on the noise variance, thereby it is possible to estimate a reliability value of each index position in input vector U. Preferably, reliability values of N.sub.max indices are estimated, where N.sub.max is a power of 2. N.sub.max can be greater than, less than or equal to N (a power of 2.sup.n, where n is a ceiling function of log.sub.2 M).

[0069] When the reliability value of each index position in the input vector U has been estimated, the N indices of the input vector U are sorted in ascending/descending order of reliability and the resulting reliability-ordered sequence of length N is stored in the first memory 604 (Operation S702). Preferably, a reliability-ordered sequence of length N.sub.max is pre-stored as a reference sequence. A reliability-ordered sequence of any length N can be obtained as an ordered subset from the reference sequence of length N.sub.max.

[0070] Subsequently, the controller 606 selects the frozen set 607 from the reliability-ordered sequence stored in the first memory 604 and the bit-reversal shortening (Operation S703). A bit-reversal shortening pattern may be a set of last N-M indices of a codeword, which can be skipped from transmission so as to transmit a relatively short-length rate-matched polar code. For bit-reversal shortening, the bit-reversal permuted values of the set of {N-M+1, . . . , N1} are included in the frozen set 607. The remaining indices of the frozen set 607 may be chosen from the at least one reliability-ordered sequence stored in the first memory 604. More specifically, such frozen set selection is performed as illustrated in FIG. 7B.

[0071] In FIG. 7B, the controller 606 selects indices in the input vector corresponding to the non-transmitted codebits and includes them in the frozen set 607 (Operation S703-1). For example, if bit-reversal shortening scheme is used with an encoder of the form

c=uBG.sub.2.sup..Math.n, (Math. 8)

then the last N-M indices of the codeword are not transmitted and the indices obtained by applying bit-reversal permutation on the last N-M indices are set to a known value (e.g., frozen bit) and may be included in frozen set. If the number of indices selected in the S703-1 is less than N-K (Operation S703-2; YES), the controller 606 selects the remaining indices of the frozen set 607 from the indices sorted in the first memory 604 that have relatively low reliability than the remaining indices (Operation S703-3). For instance, the controller 606 includes the bit-reversed permutations of the last N-M indices in the frozen set 607. The remaining of the indices in the frozen set 607 are selected from the reliability-ordered sequence stored in the first memory 604, i.e., indices with least reliability in the reliability-ordered sequence stored in the first memory 604 are included in the frozen set 607 to fill the shortfall indices in frozen set 607.

[0072] Referring to FIG. 6 and FIG. 7A, the controller 606 puts information bits generated by the message source 602 in the non-frozen set 608 and the indices in the frozen set 607 are filled with frozen bit (for instance, 0) to construct the input vector U (Operation S704).

[0073] The controller 606 provides the resulting input vector U to the FEC encoder 603, which encodes the input vector U to output a codeword. At the output of the encoder, the resulting codeword is controlled so as to skip the codebits corresponding to the indices in the universal rate-matching pattern from transmission (Operation S705).

[0074] Further specific details of the many variants discussed above will be explained using the following embodiments supplemented by figures.

3.3) Example

[0075] An example of how to design a (11, 8) rate-matched polar code using the bit-reversal shortening is as follows:

Step 1: <Reliability Ordering>

[0076] Sort the indices 0, 1, . . . , 2.sup.n1 (n=a ceiling function of log.sub.211) in ascending order of reliability-, for example: {0,1,2,4,8,3,5,6,9,10,12,7,11,13,14,15}.

Step 2: <Select Frozen Set>

[0077] Step 2.1: Include the bit-reversal permutation of the last N-M indices {11, 12, 13, 14, 15} in the frozen set, i.e., {13, 3, 11, 7, 15}.

[0078] Step 2.2: Since size of frozen set is N-K=168=8, hence 85=3 more indices have to be selected. These 3 indices can be selected according to the sequence generated in Step1 which are {0, 1, 2}. Thus total frozen set is {0, 1, 2, 3, 7, 11, 13, 15}. These indices are set to frozen bit (e.g., 0). Information bits are put in the remaining indices.

Step 3: <Encoding>

[0079] Multiply with

BG.sub.2.Math.n. (Math. 9)

[0080] As described above, using the universal rate-matching scheme and pattern causes the reliability-ordering of indices without considering rate-matching to be very similar to the reliability-ordering of indices optimized according to the rate-matching. Accordingly, the same sequence can be used both with and without rate-matching. Also, the same sequence can be used to design any length of rate-matched code.

3.4) Receiver Device

[0081] As illustrated in FIG. 8, a receiver device 801 is provided with data receiving functions including a demodulator 802, a FEC decoder 803 and a decoded message processor 804, which may be implemented on a processor running respective programs stored in a memory device (not shown). An LLR vector of length M is constructed from the received vector (i.e., channel output) of length M. Then an LLR vector of length N may be constructed from the LLR vector of length M by filling the indices corresponding to non-transmitted bits by very high value (in case of shortening) or very low value (in case of puncturing). For instance, in case of bit-reversal shortening, the LLR values for the last N-M bits may be set to very high value, assuming that an encoder of the form

BG.sub.2.sup..Math.n (Math. 10)

is used. This LLR vector of length N may be fed as input to the decoding algorithm in the FEC decoder 803. The FEC decoder 803 runs a decoding algorithm on the LLR vector to produce a decoded message, which is output to the decoded message processor 804.

3.5) Other Applications

[0082] A communication device according to the exemplary embodiment of the present invention will be described as a sender device or a receiver device. The sender device and the receiver device may be integrated into a single communication device.

[0083] As illustrated in FIG. 9, a communication device 900 may be provided with at least the sender device 601 as shown in FIG. 6. The communication device 900 may contain a memory 901 to store at least one sequence of indices sorted in reliability-ordered sequence 905 and at least one rate-matching pattern 906, a processor 902 consisting of at least one controller which can select frozen and non-frozen sets and do encoding so as to construct a polar codeword as described before. The communication device 900 includes a program memory 903, a communication interface 904, and other units necessary for communication.

[0084] The program memory 903 stores computer-readable programs for implementing at least the selection of frozen set 607 and non-frozen set 608, design of input vector to the FEC encoder 603 as shown in FIG. 6. According to the programs stored in the program memory 903, the processor 902 uses the reliability-ordered sequence 905 and the universal rate-matching pattern 906 in the memory 901 to select frozen and non-frozen sets, construct input vector to the polar encoder and output a rate-matched polar codeword to the communication interface 904 as described above.

[0085] Where applicable, various embodiments provided by the present disclosure may be implemented using hardware, software, or combinations of hardware and software. Also where applicable, the various hardware components and/or software components set forth herein may be combined into composite components comprising software, hardware, and/or both without departing from the spirit of the present disclosure. Where applicable, the various hardware components and/or software components set forth herein may be separated into sub-components comprising software, hardware, or both without departing from the spirit of the present invention. In addition, where applicable, it is contemplated that software components may be implemented as hardware components, and vice-versa.

[0086] Although embodiments of the present disclosure have been described, these embodiments illustrate but do not limit the disclosure. For example, the frozen set may have any constant bit pattern (not restricting to the all-zero pattern) that is known to the decoder in advance. The generator matrix used in polar code encoding can be even of a form other than the n-time Kronecker product of

[00002]$\begin{array}{cc}{G}_2=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right).& \left(\mathrm{Math}..Math.11\right)\end{array}$

A different matrix may also be used as polarizing kernel. For example, the following matrix can be used as a different polarizing kernel:

[00003]$\begin{array}{cc}{G}_2=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 1& 0& 1\end{array}\right).& \left(\mathrm{Math}..Math.12\right)\end{array}$

[0087] Shortening may also include setting some input bits to a known value (not limited to zero) such that codebits corresponding to those known input bits can be skipped during transmission. The decoder can set the initial LLR value corresponding to the non-transmitted codebits to very high value.

[0088] Encoder of the form

c=uG.sub.2.sup..Math.n (Math. 13)

is also not precluded. If a universal shortening scheme is used with such an encoder, then the indices of the non-transmitted codebits in the codeword are selected and set to a known value (e.g., frozen bit) in the input to the encoder. For instance, if a bit-reversal shortening scheme is used with such an encoder, then the bit-reversal permutations of the last N-M indices in the codeword are not transmitted and the same indices are set to a known value (e.g., frozen bit).

[0089] In other embodiments, it is possible that only one of a frozen set and non-frozen set is stored in memory, not both. For instance, if the frozen set is stored in memory, then the non-frozen set is automatically known to be the remaining indices other than frozen set in the input vector of length N to the encoder.

[0090] Application software in accordance with the present disclosure, such as computer programs executed by the device and may be stored on one or more computer readable mediums. It is also contemplated that the steps identified herein may be implemented using one or more general purpose or specific purpose computers and/or computer systems, networked and/or otherwise. Where applicable, the ordering of various steps described herein may be changed, combined into composite steps, and/or separated into sub-steps to provide features described herein.

[0091] It should also be understood that embodiments of the present disclosure should not be limited to these embodiments but that numerous modifications and variations may be made by one of ordinary skill in the art in accordance with the principles of the present disclosure and be included within the spirit and scope of the present disclosure as hereinafter claimed.

[0092] The above exemplary embodiments can be applied to communication systems employing polar encoding and decoding.

REFERENCE SIGNS LIST

[0093] 601 Sender device [0094] 602 Message source [0095] 603 FEC Encoder [0096] 604 first memory (reliability-ordered sequence memory) [0097] 605 second memory (bit-reversal shortening pattern memory) [0098] 606 Controller [0099] 607 Frozen set memory [0100] 608 Non-frozen set memory [0101] 609 Modulator [0102] 901 Receiver device [0103] 902 Demodulator [0104] 903 Decoder controller [0105] 903 FEC Decoder [0106] 904 Decoded message processor