High-speed decoder for polar codes

Abstract

A high speed decoding algorithm that can decode all the information bits simultaneously at the same time, i.e., in parallel. The method of high speed decoding of polar codes includes the steps of transmitting data bits through a second part of communication channels, wherein a receiver is provided to set frozen bits as 0, apply Sc algorithm, and decode remaining bits in parallel.

Claims

1. A method of high speed decoding of polar codes comprising the steps of; transmitting data bits through a second part of communication channels, wherein a receiver is provided to; set frozen bits as 0 (first 512 bits); input N frame length and received bits, determine active frozen level, and let $l=\frac{N}{2},$ applying Sc algorithm for following 256 bits, decoding remaining bits in parallel; finding an active region comprising; determining active levels for l, using g-nodes for active levels, and using f-nodes for inactive levels, calculating likelihood ratios for each stage comprising; calculating LR from a bottom of a tree to a top thereof, and determining a bit u.sub.l+1, increment l, i.e., l=l+1, and determining active levels for l, when l=N stop.

2. The method of high speed decoding of polar codes according to claim 1; wherein all information bits are simultaneously decoded.

3. The method of high speed decoding of polar codes according to claim 1; wherein at the top node of the tree, a decision is made using: $u_i=\{\begin{array}{cc}0,& \mathrm{if}{\mathrm{LR}}_{u_i}\ge 1\\ 1,& \mathrm{otherwise}\end{array}.$

4. The method of high speed decoding of polar codes according to claim 1; wherein the method comprises bitwise parallel decoding.

5. The method of high speed decoding of polar codes according to claim 1; wherein the method reduces latency and increases speed of decoding.

6. The method of high speed decoding of polar codes according to claim 1; wherein the method includes use of a second group containing remaining N/2 channels for data bits.

7. The method of high speed decoding of polar codes according to claim 1; wherein data bits are decoded in parallel without needing previously decoded bits.

8. The method of high speed decoding of polar codes according to claim 1; wherein the method includes F-type nodes characterized by not having bit-labels.

9. The method of high speed decoding of polar codes according to claim 1; wherein the method includes g-type nodes characterized by having bit-labels.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The figures used to better explain developed with this invention and their descriptions are as follows:

(2) FIG. 1 (a) The idea of bit distribution stage for SC decoder (b) A numerical example of bits distribution for SC decoder at block-length 8.

(3) FIG. 2 A numerical example of bits distribution for presented high-speed decoder at block-length 8.

(4) FIG. 3 Improved high-speed decoding approach

(5) FIG. 4 W.sub.4, W.sub.2 and W channels

(6) FIG. 5 (a) Right to left decoding procedure with N=4. (b) Basic decoding computation unit.

(7) FIG. 6 (a) The calculation of the node likelihoods for the decoding of u.sub.1 (b) The tree structure.

(8) FIG. 7 Performance of comparison of SC decoding and improved high speed decoding technique at block-length 2.sup.10 on a BEC with α=0.5.

(9) FIG. 8 Performance of comparison of SC decoding and improved high speed decoding technique at block-length 2.sup.10 on a BEC with α=0.5.

(10) FIG. 9 Flow diagram of the presented method for N=2.sup.10.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(11) Polar codes are a recently discovered family of capacity-achieving codes that are seen as a major breakthrough in coding theory. Polar codes are the first mathematically proven capacity achieving codes. The proposed high-speed decoding algorithm can decode all the information bits simultaneously at the same time, i.e., in parallel. Next, improved version of the proposed high speed decoding algorithm is introduced. The proposed high speed decoding approach and its improved version are simulated on computer environment and their BER performances are compared to that of the classical successive cancellation method.

(12) The present invention has been described in detail in the following.

(13) In this section, a novel high speed decoding technique for successive cancellation polar decoding is going to be demonstrated. A proposed High-speed decoder is based on original SC decoder which is limited by the bit by bit decoding strategy [1], [6]. Since the original SC decoder requires (2N−2) cycles to output a codeword, the latency with large N is not suitable for real-time high-speed applications [6]. Therefore, the design of low-latency and high-speed polar decoders is a requirement for the employment of polar decoders in practical applications. Our proposed algorithm can decode N successive bits at the same time. Therefore, the latency can be reduced and speed can be increased.

(14) The presented N-bit-decoding algorithm, able to decode N bits at the same time (in parallel), i.e., it can decode n.sup.th bit without a need to (n−1) previously decoded bits. The estimated code word is denoted by û.sub.1.sup.N=(û.sub.1, . . . û.sub.N). If u.sub.i is a frozen bit, then it's simply assigned û.sub.i=0. Otherwise, the code bit can be determined by (2). In the next section, the proposed algorithm is explained in detail.

(15) 4. High-Speed Decoding Algorithm

(16) Using the proposed code tree in FIG. 6b the decoding operation can be divided into two parts, distribution of the previously decided bits to the nodes, and calculation of node LRs for the decoding of current bit. In the bit distribution stage, the code tree is divided into log.sub.2 N levels, where N is frame length a power of 2. When the previously decoded information bits are distributed to the nodes, it's seen that nodes at certain levels receive the distributed bits, i.e., g-nodes appears at certain levels. Let us call the levels where g-nodes appear as active levels. In fact, for the distribution of l previously decoded bits, the active levels can be determined using

(17) $\begin{array}{cc}l=\underset{i}{.Math.}{2}^i& \left(1\right)\end{array}$
where i denotes the active level index. The g-nodes in active levels have labels 1 or 0. The distribution of the previously decoded bits to the nodes is illustrated in FIG. 1a where it is clear that the decoded bit frame is divided into its even and odd elements and divided parts are added for the left node and even part is used for the right part, and this procedure is continued until a single bit is available for each node. For the better understanding of bits distribution stage, in FIG. 1b numerical example of decoding of 6th bit with frame length N=8 is illustrated. In FIG. 1b, it is assumed that the previously decoded 5 bits are “1 0 0 1 1”. To start the decoding of 6th bit, the previously decoded 5 bits are distributed into the nodes. The number of previously decoded bits is 5, and 5 can be written as

(18) $5=\underset{i}{.Math.}{2}^i.fwdarw.5=2^0+2^2$
where powers of 2 indicates the locations of g-type nodes. i.e., they indicate the active levels. From FIG. 1b, it is clear that levels 0 and 2 are active levels, and the nodes in these levels are all g-type nodes, i.e., nodes have bit-labels; the bit-labels either include zero or one. This idea can be generalized as in FIG. 2. The nodes in active levels node-bits, and the node-bits can be either ‘0’ or ‘1’.

(19) After the first stage of the decoding operation, i.e., distribution of previously decoded bits to the nodes, the second stage of the decoding operation starts. In the second stage of the decoding operation LRs of the nodes in each level starting from bottom level to top level are calculated. In addition, during the LRs calculations (10) is used for f-type nodes and (11) is used for g-type nodes. F-type nodes do not have bit-labels; on the other hand g-type nodes have bit-labels. After calculating the likelihood of the top-node, the decision for the decoding of current bit is made according to

(20) $\begin{array}{cc}{\hat{u}}_i\stackrel{\Delta }{=}\{\begin{array}{cc}0,& \mathrm{if}\mathrm{LR}\ge 1\\ 1,& \mathrm{otherwise}\end{array}.& \left(2\right)\end{array}$

(21) Since frozen bits are chosen as ‘0’, likelihood calculation is not needed for frozen bits and they are automatically resolved as ‘0’ and used for the decoding of next bit in decoding sequence.

(22) 5. High-Speed Decoding

(23) For an N-bit information sequence, after channel splitting operation there are N new channels. For these N channels it is seen that most of the low capacity channels occurs in the first half, i.e., low capacity channels have indices 1, . . . , N/2. And most of the frozen bits are assigned to these low capacity channels. This is the main motivation of our study. Although some of the channels in the second half have low capacities, their number is few considering the total number of channels. For this reason, the first group containing N/2 channels dedicated to the frozen bits, and use the second group containing the rest of the N/2 channels for the data bits. This means that the decoding operation starts for the data bits transmitted through the second part of the communication channels.

(24) When N/2 frozen bits are distributed on the tree, it is seen that N/2 nodes get ‘0’ as node-bit. Besides, these N/2 nodes exist on the same level which is called as frozen level. When the bit distribution is performed for the decoding of consecutive data bits, it is seen that these N/2 nodes always contain ‘0’s as node-bits, i.e., frozen level stay the same. And some levels depending on the order of the data bit to be decoded become active levels, and the nodes in these active levels either contain ‘0’ or ‘1’, and these nodes are nothing but g-type nodes. The likelihood ratio at these nodes can be calculated separately for node-bit ‘0’ and node-bit ‘1’ and the larger can be selected to be used for the nodes at upper levels. And this logic can be carried till the top level. In this way, there is no need to know the previously decoded bits, but just need to know the active and frozen levels.

(25) The advantage of the mentioned method is that the active levels can be determined for the decoding of data bits and data bits can be decoded in a parallel manner without needing the previously decoded bits. Hence, if sufficient place can be found in an electronic device like FPGA it is possible to decode all the data bits in a concurrent manner. The algorithm explained can be outlined as in the chart Algorithm-1.

(26) TABLE-US-00001 ALGORITHM1: HIGH-SPEED DECODING  1: INPUT N FRAME LENGTH AND RECEIVED BITS.  2: DETERMINE ACTIVE FROZEN LEVEL.  3: $\mathrm{LET}l=\frac{N}{2}.$  4: DETERMINE ACTIVE LEVELS FOR l.  5: USE G-NODES FOR ACTIVE LEVELS.  6: USE F-NODES FOR INACTIVE LEVELS.  7: CALCULATE LR FROM THE BOTTOM OF THE TREE TO THE TOP.  8: DETERMINE THE BIT u.sub.l+1.  9: INCREMENT l, I.E., l = l + 1. 10: GO TO STEP 4. 11: WHEN l = N STOP.
6. Improved High-Speed Decoding

(27) In order to improve performance of proposed high-speed decoder, a new decoding scheme called improved high-speed decoding technique is introduced. In this new approach some percent of the information bits are decoded using the classical successive cancellation method and the rest is of the bits are decoded at the same time using the proposed parallel decoding approach. With this approach aim is to increase the BER performance of the communication system. An example of the new approach is depicted in FIG. 3 where the first N/2 bits are frozen which corresponding to low capacity channels, and successive cancellation decoding approach is employed to decode the 50% of the rest of the information bits, finally, the remaining information bits are decoded in parallel at the same time using the proposed approach. With this new proposed method, the latency of the previously proposed parallel decoding technique is increased, however, better performance is obtained considering all parallel decoding approach. In addition, the total latency is still much less than the latency of successive cancellation method. When FIG. 3 is inspected in details, it is seen that since the low capacity channels occurs in the first half of the data frame, by freezing the first half of the transmission frame the error propagation is prevented which affects the decoding of the second half, and by successively decoding some of the bits in the second half, more robust bit decisions are provided which will be used for the decoding of the rest of the bits, and for this reason better results are obtained.

(28) Computer simulation is performed using the improved high decoding method employing the frame structure in FIG. 3. And performance results are depicted in FIG. 8. It is seen from FIG. 8 that at block-length 1024 bits, the improved high-speed decoding method gives better performance with reduced latency.

(29) In FIG. 7 the performance of polar codes are compared under proposed high-speed decoding approach and SC decoding at block length 2.sup.10 in terms of bit error rate BER when the communication takes place over the binary erasure channel BEC with erasure probabilities 0.1, 0.2, 0.3, 0.4 and 0.5. From simulation result, proposed high-speed decoding algorithm gives good performance at low rates, especially for the rates between 0.35 and 0.5. Computer simulation is performed using the improved high decoding method employing the frame structure in FIG. 3. And performance results are depicted in FIG. 8. It is seen from FIG. 8 that at block-length 1024 bits, the improved high-speed decoding method gives better performance with reduced latency over the binary erasure channel BEC with erasure probability 0.5.

(30) A high speed low latency decoding algorithm for polar codes, such that, using the proposed algorithm it is possible to decode all the information bits simultaneously in parallel, is shown. BER performance of polar codes under proposed high-speed decoding method over binary-erasure channels is obtained via computer simulations. From simulation results, it's obvious that proposed high-speed decoding algorithm shows good performance at high code rates, especially for the rates between 0.35 and 0.5. The proposed high-speed decoding algorithm gives a great improvement in polar codes decoding speed. For frame length N=1024 and rate=0.5, while original SC decoder can decode only one bit for a decoding stage, the proposed high-speed decoder can decode 512 bits all together at the same decoding stage and since in the proposed high-speed decoding algorithm there is no need to know the previously decoded bits. Next, it's suggested that an improved version of the proposed high speed decoding technique. The proposed improved high speed decoding method shows better performance than that of the classical successive cancellation decoding method at high rates with much lower decoding latency. In fact, originally for N=1024, at least 1024 clock cycles to decode whole sequence. However, only 257 (256 for SC decoding, 1 for proposed method) clock cycles are sufficient.

(31) From the above detailed description, the method of high speed decoding of polar codes comprising the steps of; the data bits transmitted through the second part of the communication channels, In receiver part; For setting frozen bits as 0(first 512 bits); Input N frame length and received bits, Determine active frozen level, Let

(32) $l=\frac{N}{2},$ Apply Sc algorithm for the following 256 bits, For decoding rest of bits in parallel; For finding active region; Determine active levels for l, Use g-nodes for active levels, Use f-nodes for inactive levels For calculating likelihood ratios for each stage; Calculate LR from the bottom of the tree to the top Determine the bit u.sub.l+1, Increment l, i.e., l=l+1, Go to determine active levels for l, When l=N stop.