Patent Description:
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.

The data u to be transmitted, named information word, is given as input to the encoder, which produces the codeword x which contains redundancy. This is then transmitted over the noisy communication channel which typically introduces errors. The output vector y is provided to the decoder, 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.

Therefore, reliable transmission of data over noisy communication channels requires some kind of error correction coding to be used. Polar codes were shown to achieve the Shannon capacity of many channels (see, <NPL>).

In their original or classical construction as specified in the above mentioned work by Arikan, polar codes are based on the polarization effect generated by the Kronecker products of the following kernel: <MAT>.

In general, a classical polar code of length N and dimension K is defined by a generator matrix <MAT>, N = <NUM>", and a set of frozen bit indices F ⊂ [N], [N] = {<NUM>,<NUM>,. ,N - <NUM>}, wherein the size of the set of frozen bit indices F is given by |F| = N - K. A set of K information bit indices I is defined as the complementary set of the set of frozen bit indices, namely I = [N]/F, and therefore |I| = K.

In order to encode the K information bits into a polar code or codeword cN of length N, the elements ui of a binary input vector uN of length N are set equal to zero for i ∈ F and equal to the K information bits for i ∈ I. Then, the encoded polar code cN can be obtained as: <MAT>.

According to the classical construction of polar codes, the effective generator matrix GN is a sub-matrix of <MAT> formed by rows of <MAT>, denoting the n-fold Kronecker product. As a consequence, only polar codes having a length of powers of <NUM>, namely N = <NUM>n, can be generated. Therefore, given a code dimension (i.e. number of information bits) K, classical polar codes admit only a polar code rate R = K/N, under the condition that N is a power of <NUM>. A simple implementation of the encoder requires n stages of XOR gates.

Therefore, 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; even more, the fraction of noiseless bit-channels equals the channel capacity.

For finite practical code lengths, the polarization of bit-channels is incomplete, therefore, there are bit-channels that are partially noisy.

Polar code decoding can be based on successive cancellation (SC) decoding algorithm (see the work by Arikan), 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<NUM> and feeds this decision back into the decoding process. Then, it makes a decision of bit u<NUM> and feeds this decision back into the decoding process.

It proceeds in this manner until it obtains the design for the last bit uN. SC list decoding (SCL) (<NPL>. ) is an enhanced version of SC where multiple are followed during the decoding, while the decision is postponed to the end of the decoding process and is usually performed with the help of a CRC (<NPL>.

Staircase codes were introduced in <NPL>, targeting <NUM> Gb/s optical transport networks. Inspiration is taken from both product codes and convolutional codes, in that they combine the use of a block code as component code, and entangle part of it with past and future codewords, alternating row and column encoding/decoding.

<FIG> depicts a straightforward example of staircase code. Encoding and transmission proceeds from the top left towards the bottom right. Bits belonging to multiple component codes are transmitted only once. When interpreted through this graphical representation, staircase codes natively make use of systematic component codes.

Decoding of staircase codes starts from the newest received blocks (bottom right in <FIG>) propagating information towards the older blocks (top left). A decoding window of W blocks is selected for practical reasons, identifying the number of blocks through which the decoding information is propagated. Every time a new block is received, the oldest block in the window is output.

Staircase code decoding is possible both as hard-decoding and soft decoding. Hard decoding requires the decoding of component codes to return hard decisions, and the information propagated is the value of the bit itself. Soft decoding requires component code decoders to return soft values, which are scaled and propagated through the window. Hard decisions are taken only at output time. Soft decoding can achieve substantially better error-correction performance than hard decoding, at the cost of increased decoding complexity.

Preliminary results with staircase codes using polar codes have been presented in <NPL> and <NPL>, where systematic polar codes are considered. Systematic polar codes are straightforward, but come with the disadvantage of increased encoding and decoding latency, that can be critical in optical communications.

Document "<NPL>et al. discloses staircase codes which are a class of braided block codes, which have been demonstrated to have good performance for high speed optical communication. In particular, it discloses a soft-decision decoding and a Chase-Pyndiah algorithm based sliding-window decoding for staircase codes over a AWGN channel.

Thus, there is a need for an improved apparatus and method for encoding and decoding data using polar codes.

In view of the above-mentioned problems and disadvantages, embodiments of the present invention aim to improve the conventional polar codes and their construction methods. An objective is thereby to provide an improved apparatus for encoding data using polar codes.

The objective is achieved by the embodiments provided in the enclosed independent claims. Advantageous implementations of the embodiments are further defined in the dependent claims.

According to a first aspect, the invention relates to an apparatus for encoding a sequence including information bits into a sequence of matrices, wherein the apparatus is configured to generate a MxN matrix UNh, wherein M=N/<NUM>, wherein in each row <NUM>≤i<M of UNh each bit position <NUM>≤j<M contains an information bit of the input sequence or a frozen bit depending on a set of frozen bit indices F of a polar code of length N associated with that row, wherein the bits xij, for <NUM>≤i<M and <NUM>≤j<N-M form a matrix Uh+<NUM>, while the bits xij for <NUM>≤i<M and M≤j<N form a matrix Xh', encode each row of UNh on the basis of the polar code of length N associated with that row, in order to obtain an encoded matrix XNh, wherein the bits xij of XNh for <NUM>≤i<M and <NUM>≤j<N-M form a matrix Xh+<NUM>' while the bits xij for <NUM>≤i<M and M≤j<N form a matrix Xh, and transmit the matrix Xh.

Further, the apparatus is configured to generate a NxM matrix UNh+<NUM>, wherein in each column <NUM>≤j<M of UNh+<NUM> each bit position <NUM>≤i<N contains an information bit of the input sequence or a frozen bit depending on a set of frozen bit indices F of the polar code of length N associated with that column, wherein the bits xij, for <NUM>≤i<M and <NUM>≤i<N-M form a matrix Uh+<NUM>, while the bits xij for <NUM>≤j<M and N-M≤i<N form the matrix Xh+<NUM>', encode each column of UNh+<NUM> on the basis of the polar code of length N associated with that column, in order to obtain an encoded matrix XNh+<NUM>, wherein the bits xij of XNh+<NUM> for <NUM>≤j<M and <NUM>≤i<N-M form a matrix Xh+<NUM>' while the bits xij for <NUM>≤j<M and N-M≤j<N form a matrix Xh+<NUM>, transmit the matrix Xh+<NUM>. The polar encoding is based on a non-systematic polar encoding.

This provides the advantage that the polarization effects of polar codes can be used while encoding the sequence.

This provides the advantage that the polarization effects of polar codes can be used while encoding the sequence. Moreover the encoding is simple and fast.

Further, this provides the advantage that the staircase construction with non-systematic polar code design has the same error-correction performance of an equivalent construction with systematic polar codes, with simpler and faster component encoding.

In an implementation form of the apparatus according to the first aspect, the apparatus is further configured to generate a MxN matrix UNh+<NUM>, wherein in each row <NUM>≤i<M of UNh+<NUM> each bit position <NUM>≤j<N-M contains an information bit of the input sequence or a frozen bit depending on the set of frozen bit indices F of the polar code of length N associated with that row, wherein the bits xij, for <NUM>≤i<M and <NUM>≤j<N-M form a matrix Uh+<NUM>, while the bits xij for <NUM>≤i<M and N-M≤j<N form the matrix Xh+<NUM>', encode each row of UNh+<NUM> on the basis of the polar code of length N associated with that row, in order to obtain an encoded matrix XNh+<NUM>, wherein the bits xij of XNh+<NUM> for <NUM>≤i<M and <NUM>≤j<N-M form a matrix Xh+<NUM>' while the bits xij for <NUM>≤i<M and N-M≤j<N form a matrix Xh+<NUM>, transmit the matrix Xh+<NUM>.

In an implementation form of the apparatus according to the first aspect, the apparatus is further configured to set to <NUM> all bits xij for j≥N-M forming the matrix X<NUM>'.

This provides the advantage that the matrix X<NUM>' can be initialized in a simple way.

In an implementation form of the apparatus according to the first aspect, for the polar code of length N, the apparatus is configured to choose K most reliable positions i, with i<N-M, as positions of information bits, freeze the remaining N-M-K positions with i<N-M, and put information bits in any position i≥N-M.

In an implementation form of the apparatus according to the first aspect, for the polar code of length N and N-M being a power of <NUM>, with N=<NUM>, the apparatus is configured to select the K most reliable positions i as non-frozen positions from the frozen set of polar code of length N-M, wherein non-frozen positions correspond to positions of information bits, freeze the remaining N-M-K positions, and put information bits in any position i≥N-M.

According to a second aspect, the invention relates to a method encoding an input sequence including information bits, wherein the method comprises the steps of generating a MxN matrix UNh, wherein M=N/<NUM>, wherein in each row <NUM>≤i<M of UNh each bit position <NUM>≤j<M contains an information bit of the input sequence or a frozen bit depending on a set of frozen bit indices F of a polar code of length N associated with that row, wherein the bits xij, for <NUM>≤i<M and <NUM>≤j<M form a matrix Uh+<NUM>, while the bits xij for <NUM>≤i<M and M≤j<N form a matrix Xh', encoding each row of UNh on the basis of the polar code of length N associated with that row, in order to obtain an encoded matrix XNh, wherein the bits xij of XNh for <NUM>≤i<M and <NUM>≤j<M form a matrix Xh+<NUM>' while the bits xij for <NUM>≤i<M and M≤j<N form a matrix Xh, and transmitting the matrix Xh.

The method further comprises generating a MxN matrix UNh+<NUM>, wherein in each row <NUM>≤i<M of UNh+<NUM> each bit position <NUM>≤j<N-M contains an information bit of the input sequence or a frozen bit depending on the set of frozen bit indices F of the polar code of length N associated with that row, wherein the bits xij, for <NUM>≤i<M and <NUM>≤j<N-M form a matrix Uh+<NUM>, while the bits xij for <NUM>≤i<M and N-M≤j<N form the matrix Xh+<NUM>', encoding each row of UNh+<NUM> on the basis of the polar code of length N associated with that row, in order to obtain an encoded matrix XNh+<NUM>, wherein the bits xij of XNh+<NUM> for <NUM>≤i<M and <NUM>≤j<N-M form a matrix Xh+<NUM>' while the bits xij for <NUM>≤i<M and N-M≤j<N form a matrix Xh+<NUM> and transmitting the matrix Xh+<NUM>. The polar encoding is based on a non-systematic polar encoding.

In an implementation form of the second aspect, the method further comprises generating a NxM matrix UNh+<NUM>, wherein in each column <NUM>≤i<M of UNh+<NUM> each bit position <NUM>≤i<N contains an information bit of the input sequence or a frozen bit depending on a set of frozen bit indices F of the polar code of length N associated with that column, wherein the bits xij, for <NUM>≤j<M and <NUM>≤i<N-M form a matrix Uh+<NUM>, while the bits xij for <NUM>≤j<M and N-M≤i<N form the matrix Xh+<NUM>', encoding each column of UNh+<NUM> on the basis of the polar code of length N associated with that column, in order to obtain an encoded matrix XNh+<NUM>, wherein the bits xij of XNh+<NUM> for <NUM>≤j<M and <NUM>≤i<N-M form a matrix Xh+<NUM>' while the bits xij for <NUM>≤j<M and N-M≤j<N form a matrix Xh+<NUM> and transmitting the matrix Xh+<NUM>.

The method of the second aspect and its respective implementation forms provide the same advantages and effects as described above for the respective apparatus of the first aspect and its respective implementation forms.

The above described aspects and implementation forms of the present invention will be explained in the following description of specific embodiments in relation to the enclosed drawings, in which:.

<FIG> shows a schematic representation of a communication system <NUM> comprising an apparatus <NUM> according to an embodiment.

The apparatus <NUM> is configured to encode a sequence including information bits into a sequence of matrices. The apparatus is further configured to:.

In <FIG>, the vector u comprises information bits and frozen bits and is encoded into a codeword x. After propagation over the communication channel <NUM>, the codeword x is changed into the codeword y due to the noise of the communication channel <NUM>.

The apparatus or decoder <NUM> is configured to decode the codeword y in order to recover the originally sent sequence or vector u.

The apparatus or decoder <NUM> is configured to decode a sequence of bits from a sequence of matrices Λk, k=<NUM>,. ,W received over the communication channel <NUM> and resulting from a transmission of the sequence of bits encoded in a sequence of matrices Xh, h=<NUM>,. , W over the communication channel <NUM>.

In an embodiment, optical transport network are considered whose error-correction performance requirements demand that a soft-decoding approach is taken at the receiver.

According to the invention, a staircase code is designed using non-systematic polar codes. Given the nature of polar codes, the direction of encoding and decoding in the staircase can be inverted.

There is no constraint on the number of component codes M that each block of the staircase contains, except that M=N/<NUM>.

The codeword length N is imposed by the component code. Polar codes have code lengths equal to powers of <NUM>, but shortening and puncturing techniques, and multi-kernel designs, can be used in order to obtain different lengths of polar codes.

Moreover, the frozen set F of the polar code can be selected in two ways:.

In order to better understand the different steps of the encoding, different steps of the encoding process are portrayed in <FIG> for an example where M=N/<NUM>, N=<NUM>, M=<NUM>.

In this embodiment, the N-bit input vector u to the polar encoder is composed of a first part unew of N-M bits, where information bits are placed, and a second part x' that is composed of previously encoded bits.

All frozen bits are placed in unew: consequently, F has frozen bits in the N-M-K least reliable positions among the leftmost N-M bit positions.

M input vectors u compose an input matrix U. Let us build an input matrix UN<NUM>, where in every row <NUM>≤i<M each bit position <NUM>≤j<N-M is an information or a frozen bit according to F, while all bit positions j>N-M are set to <NUM>.

The leftmost part of UN<NUM> is called U<NUM>, while the rightmost part is X<NUM>' (see <FIG>).

The apparatus <NUM> can be configured to set to <NUM> all bits xij for j≥N-M forming the matrix X<NUM>'.

The apparatus <NUM> can be configured to encode each row of U and obtain the encoded matrix XN<NUM>: the rightmost MxM matrix is called X<NUM>, and the leftmost part is called X<NUM>' (see <FIG>).

Afterwards, the apparatus <NUM> is configured to transmit the matrix X<NUM>.

Furthermore, the apparatus <NUM> con be configured to generate LN<NUM> through a set of column input vectors U<NUM> and the columns of X<NUM>'. After encoding, XN<NUM> can be obtained, with X<NUM> on the right side and X<NUM>' on the left side (see <FIG>). Then, X<NUM> can be transmitted.

Furthermore, the apparatus <NUM> can be configured to perform the following steps:.

The process is repeated alternating row and column encoding (see further <FIG>). Each component encoding is a standard non-systematic polar code encoder, which has half the systematic encoder latency.

<FIG> shows a schematic representation of a decoding scheme for decoding a staircase code encoded according to the invention.

On the receiver side, the decoder or apparatus <NUM> receives a set of logarithmic likelihood ratios (LLRs) A for each transmitted matrix X.

Then, the apparatus <NUM> can be configured to store matrices Λk, <NUM>≤k≤W representing a decoding window of W+<NUM> frames. While it is implemented as a circular buffer, the received frame can be stored in ΛW and the oldest frame can be stored in Λ<NUM>. Λ<NUM> is the one output from the decoder <NUM>, but to decode it, the information stored in frame Λ<NUM> can be used.

The LLRs of ΛW are relative to the encoded matrix Xw ,which can be assumed as being last encoded by rows. ΛW-<NUM> is relative instead to XW-<NUM>, encoded by columns.

In order to decode ΛW-<NUM> by columns, the LLRs in ΛW should be changed from representing XW to representing XW ', which was last encoded by columns. This can be done by the propagate LLRs function, concatenated with an interleaver Π. The interleaver rotates the LLR matrix of <NUM> degrees clockwise or anti-clockwise, depending if we are converting a row-encoded matrix for column decoding or vice versa.

Thus, after obtaining ΛW ', relative to XW ', the apparatus <NUM> can be configured to prepend it to ΛW-<NUM>, and decode each column.

The component decoding takes each column separately: any polar code decoding algorithm can be used, as long as soft values can be inferred from it. Component decoding of non-systematic polar codes is inherently faster than the systematic case.

The component decoding process returns a matrix of extrinsic values Γ. The updated ΛW-<NUM> is computed as ΛW-<NUM> = Γ + YW-<NUM> where YW-<NUM> stores the LLRs originally received from the communication channel <NUM> after the transmission of XW-<NUM>.

ΛW is not updated, as back-propagating information is damaging, an effect exacerbated by the propagate LLRs function.

In the next decoding step, ΛW-<NUM> and ΛW-<NUM> should be considered, with the LLRs in ΛW-<NUM> being propagated to identify XW-<NUM>', and thus enable row decoding of ΛW-<NUM>' and ΛW-<NUM>. The process is repeated alternating row and column decoding, until Λ<NUM> is decoded with Λ<NUM>: the output of the decoding iteration is then the estimated Û<NUM>.

The LLRs are propagated by applying soft encoding process to a vector of LLRs, where the box-plus operation substitutes the XOR.

The box-plus operation between a and b is defined as:
min(|a|,|b|) x sign(a) x sign(b).

<FIG> shows a schematic representation of a method <NUM> for encoding an input sequence including information bits according to an embodiment.

<FIG> shows a schematic representation of a method <NUM> for decoding an input sequence including information bits from a sequence of matrices Λk which has been encoded according to the invention.

The sequence of matrices Λk, k=<NUM>,. ,W is received over a communication channel <NUM> and results from a transmission of the sequence of bits encoded in a sequence of matrices Xh, h=<NUM>,. , W over the communication channel <NUM>.

The apparatuses described above may comprise hardware and software which are configured to carry out the above described operations. The hardware may comprise digital circuitry. Digital circuitry may comprise components such as application-specific integrated circuits (ASICs), field-programmable arrays (FPGAs), digital signal processors (DSPs), or general-purpose processors. In one embodiment, the processing circuitry comprises one or more processors and a non-transitory memory connected to the one or more processors. The non-transitory memory may carry executable program code which, when executed by the one or more processors, causes the apparatus to perform the operations or methods described herein.

Claim 1:
An apparatus (<NUM>) for encoding a sequence including information bits into a sequence of matrices, wherein the apparatus (<NUM>) is configured to:
- generate a MxN matrix UNh, wherein M=N/<NUM>, wherein in each row <NUM>≤i<M of UNh each bit position <NUM>≤j<M contains an information bit of the input sequence or a frozen bit depending on a set of frozen bit indices F of a polar code of length N associated with that row, wherein the bits xij, for <NUM>≤i<M and <NUM>≤j<N-M form a matrix Uh+<NUM>, while the bits xij for <NUM>≤i<M and M≤j<N form a matrix Xh';
- encode each row of UNh on the basis of the polar code of length N associated with that row, in order to obtain an encoded matrix XNh, wherein the bits xij of XNh for <NUM>≤i<M and <NUM>≤j<N-M form a matrix Xh+<NUM>' while the bits xij for <NUM>≤i<M and M≤j<N form a matrix Xh;
- transmit the matrix Xh;
- generate a NxM matrix UNh+<NUM>, wherein in each column <NUM>≤j<M of UNh+<NUM> each bit position <NUM>≤i<N contains an information bit of the input sequence or a frozen bit depending on a set of frozen bit indices F of the polar code of length N associated with that column, wherein the bits xij, for <NUM>≤j<M and <NUM>≤i<N-M form a matrix Uh+<NUM>, while the bits xij for <NUM>≤j<M and N-M≤i<N form the matrix Xh+<NUM>';
- encode each column of UNh+<NUM> on the basis of the polar code of length N associated with that column, in order to obtain an encoded matrix XNh+<NUM>, wherein the bits xij of XNh+<NUM> for <NUM>≤j<M and <NUM>≤i<N-M form a matrix Xh+<NUM>' while the bits xij for <NUM>≤j<M and N-M≤j<N form a matrix Xh+<NUM>;
- transmit the matrix Xh+<NUM>; and
- wherein the polar encoding is based on a non-systematic polar encoding.