CROSS REFERENCE TO THE RELATED APPLICATIONS

This application is the national stage entry of International Application No. PCT/TR2018/050718, filed on Nov. 23, 2018, the entire contents of which are incorporated herein by reference.

TECHNICAL FIELD

The present invention relates to the field of communication and particularly to architectures of decoders for polar codes.

BACKGROUND

Polar coding is a linear block coding method that is proved to achieve Shannon's channel capacity for any symmetric binary-input discrete memoryless channel (B-DMC) by Erdal Arikan.

Block length of a polar code is represented by N=2n, where n is a positive integer. An uncoded bit vector of length-N consists of information bits and frozen bits. The number of information bits is represented by K. The number of frozen bits is given by N-K. The code rate is represented by R=K/N.

For generic N, the encoding operation of polar codes can be written in vector-matrix multiplication form as:
x=uGN

The generator matrix, GN, is defined as GN=BNF⊗m, where

F=[1011]

and F⊗mis m-th Kronecker power of the kernel matrix F. The matrix BN is the bit-reversal matrix for a vector of length-N. If the binary representation of an integer k∈{0, . . . , N−1} is denoted by (i0, . . . , in-1), the elements of vectors a and b of length-N have the relation a(i0, . . . , in-1)=b(in-1, . . . , i0)if a=bBN. Polar codes can be defined with or without the bit-reversal operation.

For polar code construction, the reliabilities of bit channels are determined. The most reliable K channels are reserved for K information bits. Known bit values are assigned to remaining N-K frozen bit channels. Information bit locations in the uncoded bit vector are the elements of the set A. Frozen bit locations in the uncoded bit vector are the elements of the set Ac.

Several decoding methods can be employed to decode polar codes. Example decoding methods are Successive Cancellation (SC) and Successive Cancellation List (SCL) decoding.

SC is a low-complexity algorithm in which bits are decoded sequentially and one at a time. SC decoder takes the channel observations and the frozen bit locations as inputs and calculates the bit estimates. Channel observations may be taken in hard decisions (bits) or soft decisions. In an exemplary embodiment, soft decision form is log-likelihood ratio (LLR), which is defined as:

λ=P⁡(y❘x=0)P⁡(y❘x=1)

In SC decoding, bit decisions are made according to the following pseudocode:

for i=0 to N-1 doif i ∈ ACthenûi← uielseif⁢⁢ln⁢⁢(WN(i)(y,u0i-1⁢ui=0WN(i)(y,u0i-1⁢ui=1)≥0⁢⁢thenûi← 0elseûi← 1endend

Herein, uidenotes the the i-th uncoded bit, ûidenotes the bit estimation for uiat the decoder output, WN(i)(y,u0i-1|ui=u) is the conditional channel transition probability of polarized i-th bit channel. The likelihood functions

ln⁡(wN(i)⁡(y,u0i-1❘ui=0)wN(i)⁡(y,u0i-1❘ui=1))
are calculated sequentially in SC decoding.
An SC decoder has a complexity order O(Nlog2N). A full parallel implementation of SC decoder has 2N−2 latency.

SCL decoding algorithm is based on SC decoding algorithm. SCL decoders achieve better error performance than SC decoders, while having higher complexity than SC decoders.

Storage elements in SCL decoder implementations may be used to store intermediate LLR values, decoded bits and partial-sums of for each of L paths. Storage elements may be register or RAM blocks depending on the hardware architecture. For example, intermediate LLR values are conventionally stored in RANI blocks due to large amounts of bits to be stored. Decoded bits and partial-sum bits may be stored in registers or RAM blocks depending on the architecture, as they do not require as many bits as intermediate LLR values.

Implementations of SCL decoders require copying of contents of storage elements of each path after path pruning stages. L-to-1 multiplexers are used for each of L paths. Input widths of multiplexers are equal to the widths of storage elements. For example, in a hardware design where decoded bits are stored in N-bit registers, L-to-1 multiplexers with input widths of N bits are used to copy registers of each of L paths. For the case in which RANI blocks are used for storage, a method to keep pointer registers may be employed in order to access the contents of correct RANI blocks during decoding. In that case, L-to-1 multiplexers with input widths equal to the width of pointer registers are required for each of L paths.

An important portion of hardware complexity in SCL decoder implementations emerges from multiplexer blocks. Decreasing the complexity of the explained multiplexing operation is expected to reduce the complexity of overall SCL decoder architecture.

In prior art, patent document numbered KR101600759B1 discloses a method and an apparatus to simplify merged processing element for SCL polar decoders. The said apparatus includes a first merged processing calculation part (SM-PE1) which searches for the selection signal of a multiplexer by using an XOR calculation, and a second merged processing calculation part (SM-PE2) which performs a calculation by using a sign bit only in a final step of performing decoding. In this document, hardware complexity resulted from multiplexers is not disclosed.

Patent application document numbered US2016056843A1 discloses a method and a system reducing hardware complexity of polar code decoders. This document addresses to architectures and decoding processes to reduce polar code decoder complexity both in terms of the number of processing elements required, but also the number of memory elements and the number of steps required to decode a codeword. However, similar to the document above, this document does not disclose hardware complexity reduction technique regarding multiplexers either.

Patent application document numbered US2017366204A1 discloses a design for multiple-symbol combination based decoding comprising list decoding.

The paper A. Balatsoukas-Stimming, M. B. Parizi and A. Burg, “LLR-Based Successive Cancellation List Decoding of Polar Codes,” in IEEE Transactions on Signal Processing, vol. 63, no. 19, pp. 5165-5179, Oct. 1, 2015 discloses a formulation for successive cancellation list decoding using log-likelihood ratios.

The paper A. Balatsoukas-Stimming, M. Bastani Parizi and A. Burg, “On metric sorting for successive cancellation list decoding of polar codes,” 2015 IEEE International Symposium on Circuits and Systems (ISCAS), Lisbon, Portugal, 2015, pp. 1993-1996. discloses an exploitation of the structure of the path metrics in a log-likelihood ratio based formulation of successive cancellation list decoding.

The paper K. Chen, K. Niu and J. Lin, “A Reduced-Complexity Successive Cancellation List Decoding of Polar Codes,” 2013 IEEE 77th Vehicular Technology Conference (VTC Spring), Dresden, Germany, 2013, pp. 1-5 discloses a version of successive cancellation list decoding algorithm based on a tree-pruning technique.

The paper J. Chen et al., “Low-Complexity List Successive-Cancellation Decoding of Polar Codes Using List Pruning,” 2016 IEEE Global Communications Conference (GLOBECOM), Washington, D.C., USA, 2016, pp. 1-6 discloses a design for successive cancellation list decoding based on a list pruning method.

However, similar to the documents above, this document does not disclose hardware complexity reduction techniques regarding multiplexers either.

SUMMARY

Present invention proposes a hardware complexity reduction method for SCL decoders. This method suggests reducing the input numbers of L multiplexers used in copying operations. In path pruning stages of SCL decoding, L paths with smallest path metrics out of 2L candidate paths are chosen as surviving candidate paths. Moreover, the path indexes of L surviving candidate paths are provided in a sorted manner according to the indexes at the output of a sorter module. After path pruning, instead of L-to-1 multiplexers used in conventional SCL decoders, (L/2+1)-to-1 multiplexers are required to perform copying operations of any required elements stored in registers of continuing and/or duplicated paths.

