PERFORMANCE ENHANCEMENT OF POLAR CODES FOR SHORT FRAME LENGTHS CONSIDERING ERROR PROPAGATION EFFECTS

Abstract

A method for performance enhancement of polar codes for short frame lengths considering error propagation effects is provided. The method inspects effects of the error propagation on a performance of the polar codes and proposes methods to alleviate degrading effects of the error propagation on a code performance for the short frame lengths.

Claims

1. A method for a performance enhancement of polar codes for short frame lengths considering error propagation effects, comprising the steps of: extracting statistical information for most probable error locations, transmitting a number of frames and recording an index of a first erroneous bit when a Successive Cancellation (SC) algorithm is employed, and repeating the steps of extracting, transmitting and recording for a transmission of a number of random data frames, wherein the number of random data frames are 50 or 100 frames or more, from the index of first erroneous bit, choosing even indices, employing a cyclic code with a rate for chosen data bits at the even indices, concatenating parity bits to an end of a polar codeword to obtain cyclic parity bits, at a receiver side, running the SC algorithm and decoding the chosen data bits at the even indices when a turn of the even indices comes, at the receiver side, when the decoding of the chosen data bits at the even indices are complete, performing a check for the cyclic parity bits, when any error in the chosen data bits are detected, performing a syndrome decoding for the chosen data bits.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0009] The figures used to better explain performance enhancement of polar codes for short frame lengths considering error propagation effects developed with this invention and their descriptions are as follows:

[0010] FIG. 1: Polar Encoder and Decoder Units.

[0011] In FIG. 1 a, b are data bits, c, d are code bits, e, d are estimated code bits and a, b are estimated data bits.

[0012] FIG. 2: Polar Encoder for N=4.

[0013] In FIG. 2 u.sub.1, u.sub.2, u.sub.3, u.sub.4 are data bits, x.sub.1, x.sub.2, x.sub.3, x.sub.4 are code bits, W represents a channel, and y.sub.1, y.sub.2, y.sub.3, y.sub.4 are channel outputs.

[0014] FIG. 3: Tree representation of polar decoders for N=2.

[0015] In FIG. 3 â, {circumflex over (b)} and ĉ are bits.

[0016] In FIG. 3 u.sub.1, u.sub.2, u.sub.3, u.sub.4 are data bits estimated, x.sub.1, x.sub.2, x.sub.3, x.sub.4 are estimated code bits, W represents a channel, and y.sub.1, y.sub.2, y.sub.3, y.sub.4 are channel outputs.

[0017] FIG. 4: Polar decoding path of u.sub.3 and its tree representation for N=4.

[0018] In FIG. 4 u.sub.1, u.sub.2, u.sub.3 are data bits estimated, x.sub.1, x.sub.2, x.sub.3, x.sub.4 are estimated code bits, g.sub.1, g.sub.2 are bits

[0019] FIG. 5: Polar decoding path of u.sub.8 and its tree representation for N=8.

[0020] In FIG. 5, u.sub.1, . . . , u.sub.8 are estimated data bits, x.sub.1, . . . , x.sub.8 are estimated code bits, g.sub.1, . . . g.sub.4 and h.sub.1, h.sub.2 are bits

[0021] FIG. 6: Error propagation vs error location, Rate=0.5, N=1024, α=0.5

[0022] FIG. 7: Frequency graph for the index of first erroneous bit, N=32, BEC with α=0.5 and Rate=0.5 is used.

[0023] FIG. 8: Frequency graph for the index of first erroneous bit, N=64, BEC with α=0.5 and Rate=0.5 is used.

[0024] FIG. 9: Communication system with CRC.

[0025] CRC means cyclic redundancy check.

[0026] FIG. 10: BER performance comparison in BEC where α=0.5, N=32.

[0027] BEC means binary erasure channel.

[0028] FIG. 11: BER performance comparison in BEC where α=0.5, N=64.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0029] To better explain a performance enhancement of polar codes for short frame lengths considering error propagation effects developed with this invention, the details are as presented below.

[0030] Polar codes are decoded in a sequential manner using successive cancelation algorithm introduced in Arikan's original work [1]. The sequential nature of the decoding process suffers from error propagation. In this paper, we inspect the effects of error propagation on the performance of polar codes and propose some methods to alleviate the degrading effects of error propagation on the code performance for short frame lengths.

[0031] Successive Cancelation Decoding of Polar Codes with Tree Structure:

[0032] Polar encoder and decoder structures are as presented below, then provide information about tree representation of polar decoder structure.

[0033] Kernel Polar Encoder Structures and Basic Formulas:

[0034] The kernel polar encoder and decoder structures are depicted in FIG. 1. From the decoder unit in FIG. 1, we can

[0035] write

â=ĉ⊕{circumflex over (d)} {circumflex over (b)}={circumflex over (d)}  (1)

[0036] from which, it can be shown that we can calculate

[00001]$\begin{array}{cc}\mathrm{LR}\left(\hat{a}\right)=\frac{p\left(\hat{a}=0\right)}{p\left(\hat{a}=1\right)}\mathrm{as}& \left(2\right)\\ \mathrm{LR}\left(\hat{a}\right)=\frac{1+LR\left(\hat{c}\right)LR\left(\hat{d}\right)}{LR\left(\hat{c}\right)+LR\left(\hat{d}\right)}.& \left(3\right)\end{array}$

[0037] The value of â can be decided using (3). After deciding the value of â, we can start to decoding of b and the likelihood ratio for {circumflex over (b)} can be found as

[00002]$\begin{array}{cc}LR\left(\hat{b}\right)=\frac{p\left(\hat{b}=0\right)}{p\left(\hat{b}=1\right)}.fwdarw.LR\left(\hat{b}\right)=L{R\left(\hat{c}\right)}^{1-2\hat{a}}LR\left(\hat{d}\right).& \left(4\right)\end{array}$

[0038] The formulas in (3) and (4) are expressed in a recursive manner in [1] as

[00003]$\begin{array}{cc}{L}_N^{\left(2i-1\right)}\left(y_1^N,{\hat{u}}_1^{2i-2}\right)=\frac{L_{N/2}^{\left(i\right)}\left(y_1^{N/2},{\stackrel{\sim }{u}}_{1,o}^{2i-2}\oplus {\stackrel{\sim }{u}}_{1,e}^{2i-2}\right)L_{N/2}^{\left(i\right)}\left(y_{N/2+1}^N,{\stackrel{\sim }{u}}_{1,e}^{2i-2}\right)+1}{L_{N/2}^{\left(i\right)}\left(y_1^{N/2},{\tilde{u}}_{1,o}^{2i-2}\oplus {\tilde{u}}_{1,e}^{2i-2}\right)+L_{N/2}^{\left(i\right)}\left(y_{N/2+1}^N,{\tilde{u}}_{1,e}^{2i-2}\right)}\mathrm{and}& \left(5\right)\\ L_N^{\left(2i\right)}\left(y_1^N,{\hat{u}}_1^{2i-1}\right)={\left[L_{N/2}^{\left(i\right)}\left(y_1^{N/2},{\stackrel{\sim }{u}}_{1,o}^{2i-2}\oplus {\stackrel{\sim }{u}}_{1,e}^{2i-2}\right)\right]}^{1-2{\stackrel{\sim }{u}}_{2i-1}}{L}_{N/2}^{\left(i\right)}\left(y_{N/2+1}^N,{\stackrel{\sim }{u}}_{1,e}^{2i-2}\right)& \left(6\right)\end{array}$

[0039] The polar encoders are constructed assembling the kernel units depicted in FIG. 1 in a Butterfly structure. The polar encoder with discrete memoryless channels for N=4 is shown in FIG. 2.

[0040] Tree Structure for Polar Decoder:

[0041] The decoding operation for N=2 can be illustrated using simple trees as in FIG. 3 where the left tree corresponds to the decoding of a, i.e., the first bit, and the right tree correspond to the decoding of b, i.e., the second bit. And as can be seen from the decoding tree of b, the decision result of the first bit is used as a node-bit. Now assume that N=4, and third-bit is to be decoded. The decoding path of the third-bit for N=4 and its tree representation is shown in FIG. 4. It is clear from the tree graphs depicted in FIG. 4 that the nodes in the decoder tree may have some bits assigned to them depending on the index of the current-bit to be decoded. The tree consists of levels each of which has an index. The top-most level has the index value 0, and the bottom-most level has an index value n=log.sub.2 N. The topmost level has 2.sup.0=1 node, and the bottom most level has N=2.sup.n nodes. In fact, the level with index m, where m ∈ [0 . . . n], has 2.sup.m nodes.

[0042] Determination of Node-Bits: In this subsection, we propose a short method to determine the values of node-bits in the decoder tree used for the decoding of bit u.sub.k+1 where k ∈ [0 . . . N−1]. For this purpose, we first determine the nodebits, then calculate the likelihoods of the nodes starting from the bottom ones till the top-most node. For the determination of the node bits, we first write the integer k as sum of powers of 2, i.e.,

[00004]$\begin{array}{cc}k=\underset{i}{.Math.}{2}^i& \left(7\right)\end{array}$

[0043] where i refers to the levels whose nodes have assigned bits. Once we determine the level indices i, we partition the previously decoded bit stream starting from the last bit into consecutive sub-streams ū.sub.i containing 2.sup.i bits, and the node bits are determined using

n.sub.i=ū.sub.i×G.sub.i   (8)

[0044] where G.sub.i is the sub-generator matrix of size 2.sup.i×2.sup.i.

[0045] Example: Assume that N=16 and we want to decode u.sub.13 and the previous 12 decoded bits are b=[100101110011]. We can write 12 as 12=2.sup.3+2.sup.2 and obtain the sub-streams as b.sub.2=[0011] and b.sub.3=[10010111]. Then the node bits are calculated as

n.sub.2=ū.sub.2×G.sub.2.fwdarw.n.sub.2=[0011]×G.sub.2

n.sub.3=ū.sub.3×G.sub.3.fwdarw.n.sub.3=[10010111]×G.sub.3

[0046] Sequential Decoding and Error Propagation:

[0047] In successive cancelation decoding of polar codes, for the decoding of (k+1).sup.th-bit we benefit from two kinds of information sources. One is the soft information obtained from the received (k+1).sup.th-signal, i.e., soft information obtained from the output of the (k+1).sup.th-channel. The other is the k decision results obtained from the decoding of the previous k bits. This means that the wrong decisions made for the decoding of previous bits affect the decoding of current bit, i.e., bit error propagate throughout the decoding operation.

[0048] Bit Errors in Even and Odd Locations:

[0049] Decoding tree can help us to visualize the distribution of the previously decoded bits to the nodes. For instance, for the decoding of u.sub.8, the distribution of 7 decoded bits u.sub.1, u.sub.2, . . . , u.sub.7 can be achieved using the sub-generator matrices G.sub.1, G.sub.2, G.sub.4, and we get the decoding tree as in FIG. 5. When FIG. 5 is inspected in details, we see that even indexed bits appears at every node-bit combinations, on the other hand, odd indexed bits appear only in some of the node-bit combinations. In addition, the bit u.sub.4 appears in every node bit combinations at level-2. It is obvious that a wrong decision on the value of bit u.sub.4 affects the probability calculation of the all the nodes of level-2, and nodes at upper levels receive wrong probability values. To test the effects of even and odd indexed bit errors, we introduced single bit errors without BEC, and obtained BER graphs via computer simulations. The obtained graph is depicted in FIG. 6. It is clear from FIG. 6 that the even indexed bit errors have more degrading effects on code performance.

[0050] Alleviation of Error Propagation Via Training Based Approach:

[0051] In this sub-section, we introduce a training based approach for the alleviation of error propagation problem. In our proposed approach, we first extract some statistical information for the most probable error locations. For this purpose, we transmit 50 frames and record the index of first erroneous bit. The statistical data for N=32, N=64 and rate R=0.5 are plotted as histogram as in FIGS. 7 and 8 from which we see that the first erroneous bits usually appear at the small capacity channels, and they correspond, in general, to the first half of the data block. For different rates the statistical information is extracted via training approach. Since erroneous bits occurring at even indexes have more degrading effects than the erroneous bits at odd indexes, for N=32 for the first 4 data bits, and for N=64 for the first 6 data bits, which are most probably to the errors, we employ cyclic codes with generator polynomials g.sub.1(x)=x.sub.6+1, g.sub.2(x)=x.sub.4+1. The rate of the cyclic codes are R=0.5. The parity bits obtained from the cyclic codes are concatenated to the end of the polar codes as side information.

[0052] We did our simulations for BEC with erasure probability α=0.5. The even indices for the data bits for rate R=0.5 and N=32 are chosen as [12, 14, 20, 22], and they are chosen for rates 0.43, 0.37, 0.32 as [14, 16, 20, 22], [16, 22, 26, 28], [16, 24, 26, 28] respectively. In a similar manner using a training based approach, the even indices for rate R=0.5 and N=64 are chosen as [16, 24, 28, 40, 50, 58], and they are chosen for rates 0.4, 0.37, 0.32 as [24, 28, 30, 40, 50, 52], [28, 30, 40, 46, 50, 52], [30, 40, 44, 46, 50, 52] respectively. For the chosen data bits at the even indices, we employed cyclic code with rate R=0.5, and the parity bits are concatenated to the end of the polar codeword. At the received side, SC(successive cancelation) algorithm is run, and when the decoding of the chosen data bits at even indices are complete, a check is performed for the cyclic parity bits. If any error in the chosen bits are detected, syndrome decoding is performed for the chosen data bits and decoding operation is continued for the rest of the bits. The proposed system is depicted in FIG. 9.

[0053] The simulation results for binary erasure channel are depicted in FIGS. 10 and 11 where it is seen that the proposed approach shows better performance than that of the classical successive cancelation algorithm proposed in [1]. This is the expected result, since employing cyclic codes for the most probable even error locations, we alleviate the degrading effect of error propagation, and even for very short frame lengths we obtain significant performance improvement for short sizes.

[0054] The method of an a performance enhancement of polar codes for short frame lengths considering error propagation effects comprising the steps of; [0055] Employing of cyclic code with rate for the chosen data bits at the even indices, concatenating of the parity bits to the end of the polar codeword, [0056] At the receiver side, running of SC algorithm decoding of the chosen data bits at even indices, [0057] At the receiver side, when the decoding of the chosen data bits at even indices are complete, performing of the check for the cyclic parity bits, [0058] If any error in the chosen bits are detected, syndrome decoding is performed for the chosen data bits and, [0059] Decoding operation continues for the rest of the bits.

REFERENCES:

[0060] [1] E. Arikan, “Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels,” IEEE Trans. on Inf. Theory, vol. 55, no. 7, pp. 30513073, July 2009.

[0061] [2] U. U. Fayyaz and J. R. Barry, “Low-complexity soft-output decoding of polar codes,” in IEEE Journal on Selected Areas in Comm., vol. 32, no. 5, May 2014.

[0062] [3] I. Tal and A. Vardy, “List decoding of polar codes,” in Proc. of IEEE Int. Symp. on Inf. Theory, 2011, pp. 15.

[0063] [4] K. Niu and K. Chen, “Stack decoding of polar codes,” Electronics Letters, vol. 48, no. 12, pp. 695697, June 2012.

[0064] [5] K. Chen, K. Niu, and J. Lin, “Improved successive cancellation decoding of polar codes,” IEEE Trans. on Communications, vol. 61, no. 8, pp. 31003107, August 2013.

[0065] [6] Univ Shenzhen, “LSC-CRC Decoding-Based Segmented Polar Code Encoding And Decoding Method And System”, WO2018133215 (A1), Jul. 26, 2018.

[0066] [7] Qualcomm Inc, “Enhanced Polar Code Constructions By Strategic Placement Of CRC Bits”, US2018205498 (A1), Jul. 19, 2018.

[0067] [8] Qualcomm Inc, “CRC Bits For Joint Decoding And Verification Of Control Information Using Polar Codes”, WO2018107680 (A1), Jun. 21, 2018.

[0068] [9] Huawei Technologies, “Decoding Method And Decoding Apparatus For Polar Code Concatenated With Cyclic Redundancy Check”, EP2802080, May 25, 2012.

[0069] [10] Sungkyunkwan University Research & Business Foundation, “Encoding Method And Apparatus Using CRC Code And Polar Code”, US2014/0173376 (A1), Jun. 19, 2014.