DECODERS AND METHODS FOR DECODING POLAR CODES AND PRODUCT CODES

TECHNICAL FIELD

Generally, the present invention relates to the fields of channel coding. More specifically, the present invention relates to decoders and corresponding methods for decoding a polar code codeword as well as a product code codeword.

BACKGROUND

Channel codes are essential in all digital communications systems. A system for forward error correction (FEC) coding, also called a coding scheme, consists of an encoder at the transmitter side and a decoder at the receiver side. The encoder adds redundancy to the data to be transmitted, i.e. additional redundant data, and the decoder exploits this redundancy to correct transmission errors, such that the receiver obtains the transmitted data free of errors despite the noisy communication channel. Figure 1 shows such a communication system 100, wherein the data u to be transmitted, termed information word, is given to an encoder 101 , which produces the codeword x containing redundancy. This is then transmitted over a noisy communication channel 103 which typically introduces errors. The output vector y is provided to a decoder 105, which produces estimates of the transmitted codeword and the transmitted data. The set C of possible codewords is called the code, or channel code, and the following is particularly concerned with such a code.

Polar codes are linear block codes that rely on the polarization effect, which allows to sort the bit positions of u, called bit-channels, in order of reliability. As the code length goes toward infinity, the polarization phenomenon influences the reliability of bit-channels, which are either completely noisy or completely noiseless. Furthermore, the fraction of noiseless bit-channels equals the channel capacity. More details about polar codes can be found in E. Arikan,“Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels,” IEEE Transactions on

Information Theory, vol. 55, no. 7, pp. 3051 , July 2009. For finite practical code lengths, the polarization of bit-channels is incomplete; therefore, there are bit-channels that are partially noisy. The polar encoding process consists in the classification of the bit-channels in u into two groups: the K good bit-channels that will carry the information bits and are indexed by the information set /, and the N— K bad bit- channels that are fixed to a predefined value (usually 0) and are indexed by the frozen set F. In case of finite code lengths, the K best bit-channels, i.e. the ones with the highest reliability, are selected to form the information set, while the remaining bit-channels are frozen. The frozen set F is available to both the encoder and decoder (see figure 1 ).

Arikan polar codes are based on the kernel matrix T ₂ = Encoding of such a polar

code of length N = 2 ⁿ and information length K is as follows. The frozen set F of size N K is chosen, as described above. The bits u* of the input vector u are set to 0 for i e F and to the information bits otherwise. The codeword x is computed as x = uT with the transformation matrix T = T® ⁿ , denoting the n-fold Kronecker product. As a

generalization, different kernels may be used and frozen sets may be defined in alternative ways.

Most polar code decoding algorithms are based on the Successive Cancellation (SC) decoding algorithm, which is inherently sequential. It can be viewed as a binary tree search, where bits are estimated at leaf nodes, and the tree is traversed depth-first, with priority given to the left branch. In SC decoding, the decoder starts with a decision for bit u _x and feeds this decision back into the decoding process; then it makes a decision of bit u ₂ and feeds this decision back into the decoding process; it proceeds in this fashion until it obtains the design for the last bit u _N . Besides plain SC decoding, also SC list decoding, SC stack decoding, or similar decoding algorithms may be applied.

Product codes are a class of error-correction codes constructed by encoding a matrix of information symbols row-wise with a row component code, and subsequently column-wise using a column component code, as depicted in figure 2. The twofold encoding acts as a concatenation of the row and column component codes. In a generalized product code, different component codes may be used for the rows, and different component codes may be used for the columns. Polar product codes have been proposed in T. Koike-Akino et. al.,“Irregular polar turbo product coding for high-throughput optical interface,” in Optical Fiber Communication Conference and Exhibition, 2018, wherein systematic polar codes are used as component codes.

In a product code, information bits are arranged in a K _c x K _r array, then code C _r is used to encode the K _c rows independently. Afterwards, the N _r columns obtained in the previous step are encoded using code C _c . The result is an N _r x N _c array, where rows are codewords of code C _r and columns are codewords of code C _c . Product codes can be decoded by sequentially decoding rows and column component codes. A product code decoder typically decodes first all the row codewords, which can be done in parallel. Using the results of the row-decoding, the decoder next decodes all the column codewords, which can be done in parallel. The decoder proceeds in this fashion for a certain number of iterations and produces the estimates of the transmitted bits. Soft-input/soft-output decoders are normally used to improve the decoding performance by iterating the decoding of rows and columns and exchanging soft information between the two decoders.

Product codes can be decoded with a high degree of parallelism, but good error correction performance comes at the cost of complex soft-in-soft-out decoding. Polar code decoding, on the other hand, suffers from long decoding latency, due to the sequential nature of SC- based decoding.

Using polar codes as constituent codes raises the problem of combining efficiently product decoding and component code decoding. For powerful product decoding, the information output from the component code decoding needs to be soft. However, the most effective decoders for polar codes, based on SC decoding, return hard information. Soft-output decoding of polar codes is inherently suboptimal, since polar codes achieve capacity under SC decoding, and are constructed targeting SC-based decoding algorithms.

In light of the above, there is still a need for improved decoders and corresponding methods allowing, in particular, for a more efficient decoding of a polar code codeword as well as a product code codeword. SUMMARY

It is an object of the invention to provide improved decoders and corresponding methods allowing, in particular, for a more efficient decoding of a polar code codeword as well as a product code codeword.

The foregoing and other objects are achieved by the subject matter of the independent claims. Further implementation forms are apparent from the dependent claims, the description and the figures.

Polar codes can be decoded with Successive Cancellation (SC)-based algorithms with good error-correction performance and limited complexity; however, SC-based decoding cannot be well parallelized. On the other hand, product decoding is easily parallelizable, but soft-in-soft-out decoding algorithms are necessary in order to improve error-correction performance of product decoding, which are computationally complex and suboptimal for polar codes. No trade-off between these two approaches is currently available in the state of the art.

Embodiments of the invention address the problem of how to decode polar codes with low latency, and how to decode product polar codes with enhanced error-correction performance, which is achieved through an observation of polar code properties and the interpretation of product polar codes as polar codes, and vice versa. Embodiments of the invention allow to parallelize the decoding of polar codes, and to exploit the interpretation of polar codes as product codes to use polar decoding as a powerful post-processing step. This allows to combine the speed of product decoding to the efficiency of decoding algorithms that are optimal for polar codes, such as Successive Cancellation (SC) decoding algorithm.

More specifically, according to a first aspect the invention relates to a decoder for decoding a polar code codeword, wherein the polar code codeword results from encoding information data using a polar code encoding scheme and the polar code codeword comprises a plurality of code values. The decoder comprises a processor being configured to: select first successive code values to obtain a first sub-codeword; select second successive code values to obtain a second sub-codeword, the second successive code values following the first successive code values; arrange the first sub-codeword and the second sub-codeword to form a product code matrix comprising a first matrix row with the first successive code values and a second matrix row with the second successive code values, a first matrix column comprising code values of the first sub-codeword and the second sub-codeword, and a second matrix column comprising code values of the first sub-codeword and the second sub-codeword; and decode the product code matrix using a product code decoding scheme to retrieve the information data from the polar codeword.

Thus, an improved decoder is provided allowing, in particular, for a more efficient decoding of a polar code codeword.

In a further possible implementation form of the first aspect, the processor is configured to determine a decoding measure indicating decoding quality when decoding the product code matrix, and to decode the polar codeword using a polar code decoding scheme if the decoding measure exceeds or equals to a predetermined threshold.

In a further possible implementation form of the first aspect, the decoding measure is an error measure indicating decoding errors when decoding the product code matrix.

In a further possible implementation form of the first aspect, the processor is configured to decode the product code matrix by individually decoding rows and/or columns of the product code matrix.

In a further possible implementation form of the first aspect, the processor is configured to decode at least two rows of the product code matrix in parallel, and/or to decode at least two columns of the product code matrix in parallel.

In a further possible implementation form of the first aspect, the polar codeword is based on a frozen bit set comprising positions of frozen bits, the frozen bits not carrying information, wherein each row or column of the product code matrix is based on a frozen bit sub-set, wherein the processor is configured to determine frozen bits in each frozen bit sub-set by replicating a bit vector comprising a logical 1 at a position at which a frozen bit shall be detected and logical zero elsewhere to obtain a replicated bit vector, and to compare the replicated bit vector with a frozen bit sub-set. According to a second aspect the invention relates to a decoder for decoding a product code codeword, wherein the product code codeword results from encoding information data using a product code encoding scheme providing a product code matrix comprising matrix rows and matrix columns being formed by values of the product code codeword, each matrix row and matrix column comprising a component codeword. The decoder comprises a processor which is configured to concatenate component codewords to obtain a concatenated codeword with serially arranged code values, and to decode the concatenated codeword using polar code decoding scheme.

Thus, an improved decoder is provided allowing, in particular, for a more efficient decoding of a product code codeword.

In a further possible implementation form of the second aspect, the processor is configured to concatenate component codewords arranged in subsequent matrix rows or in subsequent matrix columns to obtain the concatenated codeword.

In a further possible implementation form of the second aspect, each component code codeword is based on a frozen bit sub-set with frozen bits, and wherein the processor is configured to replicate frozen bit sub-sets arranged in rows and columns and to compare the replicated frozen bit sub-sets to obtain a frozen bit set of a polar code codeword.

In a further possible implementation form of the second aspect, the processor is configured to select a bit value for the frozen bit set if corresponding bit values of different frozen bit sub-sets are equal. In particular logical 1.

According to a third aspect the invention relates to a decoding method for decoding a polar code codeword, wherein the polar code codeword results from encoding information data using a polar code encoding scheme and the polar code codeword comprises a plurality of code values. The decoding method comprises the following steps: selecting first successive code values to obtain a first sub-codeword; selecting second successive code values to obtain a second sub-codeword, the second successive code values following the first successive code values; arranging the first sub-codeword and the second sub-codeword to form a product code matrix comprising a first matrix row with the first successive code values and a second matrix row with the second successive code values, a first matrix column comprising code values of the first sub-codeword and the second sub-codeword, and a second matrix column comprising code values of the first sub-codeword and the second sub-codeword; and decoding the product code matrix using a product code decoding scheme to retrieve the information data from the polar codeword.

Thus, an improved decoding method is provided allowing, in particular, for a more efficient decoding of a polar code codeword.

In a further possible implementation form of the third aspect, the decoding method further comprises a step of determining a decoding measure indicating decoding quality when decoding the product code matrix, and to decode the polar codeword using a polar code decoding scheme if the decoding measure exceeds or equals to a predetermined threshold.

According to a fourth aspect the invention relates to a decoding method for decoding a product code codeword, wherein the product code codeword results from encoding information data using a product code encoding scheme providing a product code matrix comprising matrix rows and matrix columns being formed by values of the product code codeword, each matrix row and matrix column comprising a component codeword. The decoding method comprises a step of concatenating component codewords to obtain a concatenated codeword with serially arranged code values, and decoding the

concatenated codeword using a polar code decoding scheme.

Thus, an improved decoding method is provided allowing, in particular, for a more efficient decoding of a product code codeword.

According to a fifth aspect the invention relates to a computer program comprising program code for performing the method according to the second aspect or the method according to fourth aspect when executed on a computer.

The invention can be implemented in hardware and/or software.

BRIEF DESCRIPTION OF THE DRAWINGS

Further embodiments of the invention will be described with respect to the following figures, wherein: Fig. 1 shows a schematic diagram illustrating a communication system comprising an encoder, a communication channel and a decoder;

Fig. 2 shows a schematic diagram illustrating an encoding scheme of a product code;

Fig. 3 shows a schematic diagram illustrating a decoder for decoding a polar code codeword according to an embodiment and a decoder for decoding a product code codeword according to an embodiment;

Fig. 4 shows a schematic diagram illustrating conversion of polar code to product code performed by a decoder according to an embodiment;

Fig. 5 shows a schematic diagram illustrating a communication system comprising an encoder, a communication channel, a product code decoder according to an embodiment and a polar code decoder according to an embodiment;

Fig. 6 shows a schematic diagram illustrating a method of decoding a polar code codeword according to an embodiment; and

Fig. 7 shows a schematic diagram illustrating a method of decoding a product code codeword according to an embodiment.

In the various figures, identical reference signs will be used for identical or at least functionally equivalent features.

DETAILED DESCRIPTION OF EMBODIMENTS

In the following description, reference is made to the accompanying drawings, which form part of the disclosure, and in which are shown, by way of illustration, specific aspects in which the present invention may be placed. It is understood that other aspects may be utilized and structural or logical changes may be made without departing from the scope of the present invention. The following detailed description, therefore, is not to be taken in a limiting sense, as the scope of the present invention is defined be the appended claims. For instance, it is understood that a disclosure in connection with a described method may also hold true for a corresponding device or system configured to perform the method and vice versa. For example, if a specific method step is described, a corresponding device may include a unit to perform the described method step, even if such unit is not explicitly described or illustrated in the figures. Further, it is understood that the features of the various exemplary aspects described herein may be combined with each other, unless specifically noted otherwise.

As will be described in more detail in the following, embodiments of the invention offer in particular the advantages of decoding polar codes with low latency and decoding product polar codes with enhanced error-correction performance, which is achieved through an observation of polar code properties and the interpretation of product polar codes as polar codes, and vice versa.

Figure 3 shows a schematic diagram illustrating a decoder 301 for decoding a polar code codeword according to an embodiment and a decoder 31 1 for decoding a product code codeword according to an embodiment.

Assuming a polar code codeword x with a length N obtained through encoding of a length N information and frozen bit vector u, x can be divided in N _c segments of N _r consecutive bits each, starting from the first bit of x, and can be arranged in a N _c x N _r matrix X, so that the first column is constituted of the first bit of the N _c segments, the second column of the second bit, etc. Furthermore, the first row corresponds to the first JV _r -bit segment, the second row to the second segment, etc.

Given the recursive nature of polar codes, the rows and the columns of X are codewords of N _r - bit and N _c - bit long polar codes respectively and are called component codes. This matrix-like structure is a characteristic of product codes and allows for decoding the row (column) component codes concurrently. Product decoding can thus be applied to polar codes.

More specifically, the decoder 301 as shown in figure 3 can decode a polar code codeword resulting from encoding information data using a polar code encoding scheme and comprises a processor 303 configured to: select first successive code values to obtain a first sub-codeword; select second successive code values to obtain a second sub-codeword, the second successive code values following the first successive code values; arrange the first sub-codeword and the second sub-codeword to form a product code matrix comprising a first matrix row with the first successive code values and a second matrix row with the second successive code values, a first matrix column comprising code values of the first sub-codeword and the second sub-codeword, and a second matrix column comprising code values of the first sub-codeword and the second sub-codeword; and decode the product code matrix using a product code decoding scheme to retrieve the information data from the polar codeword.

In an embodiment, the processor 303 is configured to determine a decoding measure indicating decoding quality when decoding the product code matrix, and to decode the polar codeword using a polar code decoding scheme if the decoding measure exceeds or equals to a predetermined threshold. The decoding measure is an error measure indicating decoding errors when decoding the product code matrix.

In an embodiment, the processor 303 is configured to decode the product code matrix by individually decoding rows and/or columns of the product code matrix and to decode at least two rows of the product code matrix in parallel, and/or to decode at least two columns of the product code matrix in parallel.

In a further embodiment, the polar codeword is based on a frozen bit set comprising positions of frozen bits, the frozen bits not carrying information, wherein each row or column of the product code matrix is based on a frozen bit sub-set. The processor 303 is configured to determine frozen bits in each frozen bit sub-set by replicating a bit vector comprising a logical 1 at a position at which a frozen bit shall be detected and logical zero elsewhere to obtain a replicated bit vector, and to compare the replicated bit vector with a frozen bit sub-set.

An exemplary conversion 400 of polar code to product code performed by the decoder 301 is shown in figure 4. Given a polar code of length N, a codeword x can be split in V/V sections of length V/v each and the sections can be rearranged one below the other. The resulting V/V x V/V matrix is a non-systematic product code matrix where each row and each column is a valid polar codeword of length V/V. Figure 4 illustrates an example 400 of a polar code codeword for N = 16. This applies even with sections of length different from V/V; the resulting matrix N _r x N _c is rectangular, but still this property applies. On the other hand, the encoding process of product codes can be expressed as T* u - T _r , where 7^ is the transpose of the transformation matrix for the column component codes and T _r is the transformation matrix for the row component codes respectively. They encode the information matrix U into a product codeword X. By considering T _c and T _r to be the transformation matrices for two polar codes of length N _c and N _r respectively, the resulting product code is a product polar code.

The N _c rows of X can be chained as the segments of an N _c x N _r vector x, so that the first row constitutes the first segment, the second row the second segment, etc. Given the construction of polar codes as product of smaller codes, vector x is the codeword of a polar code of length N _c x N _r . Polar decoding can thus be applied to a product code with polar component codes.

More specifically, the decoder 31 1 as shown in figure 3 can decode a product code codeword, wherein the product code codeword results from encoding information data using a product code encoding scheme providing a product code matrix comprising matrix rows and matrix columns being formed by values of the product code codeword, each matrix row and matrix column comprising a component codeword.

Furthermore, the decoder 31 1 comprises a processor 313 configured to concatenate component codewords to obtain a concatenated codeword with serially arranged code values, and to decode the concatenated codeword using a polar code decoding scheme.

In an embodiment, the processor 313 is configured to concatenate component codewords arranged in subsequent matrix rows or in subsequent matrix columns to obtain the concatenated codeword.

In a further embodiment, each component code codeword is based on a frozen bit sub-set with frozen bits, and the processor 313 is configured to replicate frozen bit sub-sets arranged in rows and columns and to compare the replicated frozen bit sub-sets to obtain a frozen bit set of a polar code codeword. Furthermore, the processor 313 is configured to select a bit value for the frozen bit set if corresponding bit values of different frozen bit sub-sets are equal, in particular logical 1 .

Given the aforementioned equivalences, the proposed decoding approach foresees the decoding of the rows and column component polar codes as a first step, with information exchanged between the row and column decoding phases in a product-like manner. Product decoding can be parallelized easily, as all rows can be processed in parallel and all columns can be processed in parallel, which substantially reduces the decoding latency for a length-A/ polar code.

As a second step, in the case errors that are left after the first decoding step, the overall length- A/ code is decoded with a polar decoding algorithm. To limit complexity and maximize hardware reuse, the same decoding algorithm can be used for the component codes in the first step and for the overall code in the second step. Any decoding algorithm can be used in any of the two phases, for example both hard-output algorithms such as SC-based decoding algorithms and soft-output decoding algorithms such as belief propagation or soft cancellation (SCAN) algorithms.

The speed and implementation complexity of the proposed decoding process are dependent on the number of parallel component code decoders instantiated, the number of product-like iterations, and the percentage of times that the second decoding step is activated.

Figure 5 shows a schematic diagram illustrating a communication system 500 comprising an encoder 501 , a communication channel 503, a product code decoder 31 1 according to an embodiment and a polar code decoder 301 according to an embodiment. The modified transmission system 500 in figure 5 shows the new decoding architecture as already discussed above.

Embodiments of the invention provide three novel decoding approaches. They are based on the above observation that a polar code codeword can be split into rows of a product code with row and column polar component codes, and vice versa.

First, a polar product code can be decoded with polar code decoding algorithms.

Secondly, a polar code can be decoded with product code decoding algorithms. Thirdly, a hybrid decoding approach can be performed by the following steps: a first step of considering the code as a product code and applying product-code decoding, i.e. iterative decoding of the row and column polar component codes and exchanging of information between the two phases; a second step of considering the code as a single polar code of length N and applying polar decoding in case errors are left after the first step. The first decoding step as mentioned above allows the parallelization of polar code decoding process, reducing latency. Implementation complexity can be tuned depending on the number of parallel component code decoders instantiated. The second decoding step improves the error-correction performance by strengthening the decoding process with the decoding of a longer code. It is activated with a probability g. As channel conditions improve, g tends to be 0, thus having negligible impact on the average decoding latency. To limit the implementation complexity of the second step, the same decoding algorithm can be used for the second step and also for the component codes at the first step, thus maximizing resource sharing.

Figure 6 shows a schematic diagram illustrating a method 600 of decoding a polar code codeword, wherein the polar code codeword results from encoding information data using a polar code encoding scheme and the polar code codeword comprises a plurality of code values.

The decoding method 600 comprises the following steps: a first step 601 of selecting first successive code values to obtain a first sub-codeword; a second step 603 of selecting second successive code values to obtain a second sub-codeword, the second successive code values following the first successive code values; a third step 605 of arranging the first sub-codeword and the second sub-codeword to form a product code matrix comprising a first matrix row with the first successive code values and a second matrix row with the second successive code values, a first matrix column comprising code values of the first sub-codeword and the second sub-codeword, and a second matrix column comprising code values of the first sub-codeword and the second sub-codeword; and a fourth step 607 of decoding the product code matrix using a product code decoding scheme to retrieve the information data from the polar codeword.

Figure 7 shows a schematic diagram illustrating a method 700 of decoding a product code codeword, wherein the product code codeword results from encoding information data using a product code encoding scheme providing a product code matrix comprising matrix rows and matrix columns being formed by values of the product code codeword, each matrix row and matrix column comprising a component codeword. The decoding method 700 comprises a step 701 of concatenating component codewords to obtain a concatenated codeword with serially arranged code values, and a step 703 of decoding the concatenated codeword using a polar code decoding scheme.

While a particular feature or aspect of the disclosure may have been disclosed with respect to only one of several implementations or embodiments, such feature or aspect may be combined with one or more other features or aspects of the other implementations or embodiments as may be desired and advantageous for any given or particular application. Furthermore, to the extent that the terms "include", "have", "with", or other variants thereof are used in either the detailed description or the claims, such terms are intended to be inclusive in a manner similar to the term "comprise". Also, the terms "exemplary", "for example" and "e.g." are merely meant as an example, rather than the best or optimal. The terms "coupled" and "connected", along with derivatives may have been used. It should be understood that these terms may have been used to indicate that two elements cooperate or interact with each other regardless whether they are in direct physical or electrical contact, or they are not in direct contact with each other.

Although specific aspects have been illustrated and described herein, it will be

appreciated by those of ordinary skill in the art that a variety of alternate and/or equivalent implementations may be substituted for the specific aspects shown and described without departing from the scope of the present disclosure. This application is intended to cover any adaptations or variations of the specific aspects discussed herein.

Although the elements in the following claims are recited in a particular sequence with corresponding labeling, unless the claim recitations otherwise imply a particular sequence for implementing some or all of those elements, those elements are not necessarily intended to be limited to being implemented in that particular sequence.

Many alternatives, modifications, and variations will be apparent to those skilled in the art in light of the above teachings. Of course, those skilled in the art readily recognize that there are numerous applications of the invention beyond those described herein. While the present invention has been described with reference to one or more particular embodiments, those skilled in the art recognize that many changes may be made thereto without departing from the scope of the present invention. It is therefore to be understood that within the scope of the appended claims and their equivalents, the invention may be practiced otherwise than as specifically described herein.