TECHNICAL FIELD

Polar codes, Cyclic Redundancy Check (CRC), error detection

BACKGROUND

Polar codes, proposed by Arikan [1], are the first class of constructive coding schemes that are provable to achieve the symmetric capacity of the binary-input discrete memoryless channels under a low-complexity Successive Cancellation (SC) decoder. However, the finite-length performance of polar codes under SC is not competitive compared to other modern channel coding schemes such as Low-Density Parity-Check (LDPC) codes and Turbo codes. Later, a SC List (SCL) decoder is proposed in [2], which can approach the performance of an optimal Maximum-Likelihood (ML) decoder. By concatenating a simple Cyclic Redundancy Check (CRC) coding, it was shown that the performance of concatenated polar code is competitive with that of well-optimized LDPC and Turbo codes. As a result, polar codes are being considered as a candidate for future Fifth Generation (5G) wireless communication systems.

The main idea of polar coding is to transform a pair of identical binary-input channels into two distinct channels of different qualities, one better and one worse than the original binary-input channel. By repeating such a pair-wise polarizing operation on a set of 2Mindependent uses of a binary-input channel, a set of 2M“bit-channels” of varying qualities can be obtained. Some of these bit channels are nearly perfect (i.e., error free) while the rest of them are nearly useless (i.e., totally noisy). The point is to use the nearly perfect channel to transmit data to the receiver while setting the input to the useless channels to have fixed or frozen values (e.g., 0) known to the receiver. For this reason, those input bits to the nearly useless and the nearly perfect channel are commonly referred to as frozen bits and non-frozen (or information) bits, respectively. Only the non-frozen bits are used to carry data in a polar code. An illustration of the structure of a length 8 polar code is illustrated inFIG. 1.

FIG. 2illustrates the labeling of the intermediate information bits sl,i, where l∈{0, 1, . . . , n} and i∈{0, 1, . . . , N−1} during polar encoding with N=8. The intermediate information bits are related by the following equation:

sl+1,i=sl,i⊕sl,i+2l,if⁢⁢mod⁡(⌊i2l⌋,2)=0,⁢sl+1,i=sl,i,if⁢⁢mod⁡(⌊i2l⌋,2)=1
for i∈{0, 1, . . . , N−1} and l∈{0, 1, . . . , n−1}, with s0,i≡uibeing the information bits, and sn,i≡xibeing the code bits, for i∈{0, 1, . . . , N−1}.

In this discussion, we assume a butterfly based decoder as illustrated inFIG. 3for the case of N=8. Messages passed in the decoder are Log-Likelihood Ratio (LLR) values denoted as LI,i, where I and i correspond to the graph stage index and row index, respectively. In addition, Ln,iis the LLR directly calculated from the channel output yi. The basic components of the decoder are two functions given by:

Ll-1,i=f⁡(Ll,i,Ll,i+2l)⁢=△⁢Δ2tanh-1⁡(tanh⁡(Ll,i⁢/⁢2)⁢tanh⁢(Ll,i+2l⁢/⁢2))if⁢⁢B⁡(l,i)=0Ll-1,i=g⁡(s^l,i-2l,Ll,i,Ll,i-2l)⁢=△⁢(-1)s^l,i-2l⁢Ll,i-2l+Ll,i⁢if⁢⁢B⁡(l,i)=1
for l∈{0, 1, . . . , n−1} and i∈{0, 1, . . . , N−1}, where B(l, i) denotes the lth significant bit in the binary representation of i, and where ŝl,idenotes an estimate of the intermediate information bit sl,i.

SUMMARY

Systems and methods for performing polar decoding using a transformation of the coded bits prior to polar decoding and an inverse transformation of the resulting data bits after polar decoding are disclosed. In some embodiments, a method of operation of a receiving node to perform polar decoding comprises transforming a received code bit vector yNin accordance with a transformation TNto thereby provide a transformed code bit vector yN′=yNTN, performing polar decoding of the transformed code bit vector yN′ to thereby provide a transformed data bit vector vN′, and inversely transforming the transformed data bit vector vN′ in accordance with an inverse transformation TN−1to thereby provide an estimated data bit vector vN=vN′TN−1. In some embodiments, the transformation TNre-orders coded bits in the coded bit vector yNsuch that some future frozen bit(s) are swapped in front of some information bit(s) prior to performing polar decoding. As a result, conventional successive decoding based on a natural ordering can be used while taking into account those future frozen bit(s) that would otherwise be ignored by conventional Successive Cancellation (SC) or SC List (SCL) polar decoders. By doing do, decoding performance can be enhanced without the need of increasing decoding complexity, e.g., through an increased list size of a SCL decoder.

In some embodiments, the transformation TNsatisfies:
GN=TNGNTN−1
where GNis a polar generating matrix of length N. Further, in some embodiments, the transformation TNis a bit-reversal matrix RNthat performs permutation in such a way that eiRN=er(i), for all i∈{0, 1, 2, . . . , N−1}, where eidenotes a vector with all zeros except at the ith position where the element is one, and where r(i)∈{0, 1, 2, . . . , N−1} denotes a number whose binary representation is in a reversed bit order as the binary representation of the number i. In some embodiments, the transformation TNis a bit-reversal matrix RNthat performs permutation in such a way that an order of the bits in a binary representation of indices that address elements in the received code bit vector yNis reversed to provide the transformed code bit vector yN′. In some embodiments, the transformation TNis a last-to-first permutation matrix FNof the following form:

FN=[IN/2⊗⁢[10]|IN/2⊗[01]]
where IN/2is the (N/2)×(N/2) identity matrix. In some embodiments, the transformation TNis a last-to-first permutation matrix FNthat performs permutation in such a way that a last bit in a binary representation of indices that address elements of the received code bit vector yNbecomes a first bit in a binary representation of indices that address elements of the transformed code bit vector yN′. In some embodiments, the transformation TNis an any-bit-to-any-bit permutation matrix AM,Nof the following form:

AM,N=FM⊗INM
for any M that is a power of 2 and is no larger than N. In some embodiments, the transformation TNis an any-bit-to-any-bit permutation matrix AM,Nthat performs permutation in such a way that a bit at a first bit location in a binary representation of indices that address elements of the received code bit vector yNbecomes a bit at a second bit location in a binary representation of indices that address elements of the transformed code bit vector yN′, wherein the first bit location is different than the second bit location. In some embodiments, the transformation TNis an arbitrary bit permutation matrix Sμ,Nof the following form:

Sμ,N⁢=△⁢AM1,N⁢AM1,N⁢AM2,N⁢⁢…⁢⁢AMlog2⁢N,N⁢⁢where⁢⁢{Mi,N}i=1log2⁢N
can be chosen one-by-one such that the μ(i)-th bit is in the i-th position in the final permuted binary representation. In some embodiments, the transformation TNis an arbitrary bit permutation matrix Sμ,Nthat performs multiple any-bit-to-most-significant bit permutations on bits in a binary representation of indices that address elements of the received code bit vector yNto provide the transformed code bit vector yN′.

In some embodiments, performing polar decoding of the transformed code bit vector yN′ comprises performing SC decoding of the transformed code bit vector yN′ to thereby provide the transformed data bit vector vN′.

In some embodiments, performing polar decoding of the transformed code bit vector yNcomprises performing SCL decoding of the transformed code bit vector yNto thereby provide the transformed data bit vector vN′.

In some embodiments, the received code bit vector yNis a vector of Log-Likelihood Ratios (LLRs). In some embodiments, transforming the received code bit vector yNin accordance with the transformation TNcomprises transforming the vector of LLRs in accordance with the transformation TNto thereby provide the transformed data bit vector vN′, and performing polar decoding of the transformed code bit vector yN′ comprises performing SC or SCL decoding of the transformed code bit vector yN′ based on a natural ordering of bit indices for the transformed code bit vector yN′ to thereby provide the transformed data bit vector vN′. In some embodiments, the method further comprises extracting an output information bit vector from the transformed data bit vector vN′ according to an original information set for the received code bit vector yN, wherein the original information set for the received code bit vector yNdefines which bits of the received code bit vector yNare information bits and which bits of the received code bit vector yNare frozen bits.

In some embodiments, the method further comprises extracting information bits, as opposed to frozen bits, from the estimated data bit vector VN.

In some embodiments, the method further comprises performing the steps of transforming, decoding, and inversely transforming for each of a plurality of independent component polar codes having respective lengths that are less than N according to a prefix-free code C={b1, b2, . . . , BQ} of which each codeword bihas a maximum length of N bits, where Q is an integer no larger than (log2N)−2, and wherein a prefix-free code is a code where no codeword is a prefix of another codeword. In some embodiments, the transformation TNis not the same for all of the plurality of independent component polar codes.

In some embodiments, the method further comprises performing the steps of transforming, decoding, and inversely transforming for each of a plurality of different transformations TNto thereby provide a plurality of estimated data bit vectors. In some embodiments, the method further comprises selecting a best estimated data bit vector from among the plurality of estimated data bit vectors output based on the plurality of different transformations TNas a final estimated data bit vector. In some embodiments, selecting the best estimated data bit vector comprises selecting the best estimated data bit vector from among the plurality of estimated data bit vectors output based on the plurality of different transformations TNbased on one or more criteria comprising at least one of a path metric magnitude, a Cyclic Redundancy Check (CRC) checksum, and a parity-checksum.

In some embodiments, the method further comprises performing the steps of transforming, decoding, and inversely transforming for each of a plurality of independent component polar codes having respective lengths that are less than N according to a code C={b1, b2, . . . , bQ} of which each codeword bihas a maximum length of N bits, where Q is an integer no larger than (log2N)−2. In some embodiments, the transformation TNis not the same for all of the plurality of independent component polar codes.

Embodiments of a receiving node are also disclosed. In some embodiments, a receiving node operable to perform polar decoding is adapted to transform a received code bit vector yNin accordance with a transformation TNto thereby provide a transformed code bit vector yN′=yNTN, perform polar decoding of the transformed code bit vector yN′ to thereby provide a transformed data bit vector vN′, and inversely transform the transformed data bit vector vN′ in accordance with an inverse transformation TN−1to thereby provide an estimated data bit vector vN=vN′TN−1.

In some embodiments, a receiving node operable to perform polar decoding comprises at least one receiver and processing circuitry adapted to transform a received code bit vector yNin accordance with a transformation TNto thereby provide a transformed code bit vector yN′=yNTN, perform polar decoding of the transformed code bit vector yN′ to thereby provide a transformed data bit vector vN′, and inversely transform the transformed data bit vector vN′in accordance with an inverse transformation TN−1to thereby provide an estimated data bit vector vN=vN′TN−1.

In some embodiments, a receiving node operable to perform polar decoding comprises a plurality of modules comprising a transforming module operable to transform a received code bit vector yNin accordance with a transformation TNto thereby provide a transformed code bit vector yN′=yNTN, a performing module operable to perform polar decoding of the transformed code bit vector yN′ to thereby provide a transformed data bit vector vN′, and an inverse transforming module operable to inversely transform the transformed data bit vector vN′ in accordance with an inverse transformation TN−1to thereby provide an estimated data bit vector vN=vN′TN−1.

