Patent Description:
Channel codes are essential in all digital communications systems. A system for forward error correction (FEC) coding, also called generally 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 can obtain the transmitted data free of errors despite a noisy communication channel between encoder and decoder.

In particular, polar codes are linear block codes that rely on the polarization effect (see, e.g., <NPL>), which allows to sort bit positions of so-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.

The reliability of the channels can be determined according to the Bhattacharyya parameter: <MAT> where W is a binary memoryless symmetric channel, and W(y|<NUM>), W(y|<NUM>) are transition probabilities, Y is the output alphabet and Z is the Bhattacharyya parameter. The lower the Bhattacharyya parameter, the more reliable the channel. Other methods may be used to estimate bit-channel reliabilities. For example, a density evolution method (DE) may be used, and for additive white Gaussian noise (AWGN) the channels reliabilities may be determined according to a Gaussian approximation (GA). Other categories of noisy channels may be modelled such as a binary symmetric channel (BSC) or a binary erasure channel (BEC), for example, using Monte-Carlo statistical methods.

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 into two groups: the most reliable bit-channels that will carry the information bits and are indexed by the information set, and the less reliable bit-channels that are fixed to a predefined value (usually <NUM>) and are indexed by the frozen set. In case of finite code lengths, the bit-channels with the highest reliability are selected to form the information set, while the remaining bit-channels are frozen.

Polar codes are based on the kernel matrix <MAT>.

Encoding of such a polar code of length N = <NUM>n and information length K is explained in the following. The frozen set F of size N-K is chosen, as described above. The bits ui of the input vector u are set to <NUM> for i ∈ F and to the information bits otherwise. The codeword x is computed as x = uT with the transformation matrix <MAT>, ⊗n denoting the n-fold Kronecker product.

As a generalization, different kernels of different sizes can be introduced in the code design, obtaining a multi-kernel polar code (see, e.g., <NPL>. As a result, the transformation matrix takes the form T = Ta ⊗ Tb ⊗. ⊗ Tg, and the frozen set has to be calculated accordingly.

Polar code decoding can be based on a Successive Cancellation (SC) decoding algorithm (see, e.g., the aforementioned work of 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 fashion until it obtains the design for the last bit uN.

SC list decoding (SCL) is an enhanced version of SC, wherein the decision is postponed to the end of the decoding process, and is usually performed with the help of a cyclic redundancy check (CRC) (see, e.g., <NPL>).

When too many information bits need to be transmitted, they are usually divided into blocks and transmitted separately on an independent codeword of length M. However, independent transmissions increase the block error rate of the system, since information is correctly recovered, only if all the S codewords are decoded correctly. Even a single error in one of the transmission results in an overall decoding failure.

Moreover, many polar-code-based encoding and decoding devices and methods are too complex. Thus, there is generally a need for improved devices for coding data using polar codes.

<NPL>) discloses a folding technique using a two stage concatenated interpretation of the standard polar encoder, including a pre-processing stage referred to as interleaved polar encoding (IPE) stage followed by a block-wise polar encoding (BPE) stage. Each stage includes independent polar-like codes, which are encoded/decoded in parallel. The BPE stage is SCL decoded and the IPE stage is maximumlikelihood decoded (MLD). The BPE stage encoding may constitute an element-wise XOR on bit components.

<NPL>, discloses subcode-wise polar encoding and decoding for reducing memory complexity, where SCL decoding is applied subcode-wise while simple SC decoding is used across subcodes to exploit the polarization gain. Then, hard decision is amde after each subcode decoding, confining the SCL decoder complexity to the subcode size. The overall decoder complexity is reduced from whole-codeblock SCL to one subcode SCL decoding plus one whole-codeblock decoding.

In view of the above-mentioned disadvantages, the present disclosure aims to improve devices and methods for encoding and decoding based on polar code. An object is, in particular, to provide a polar-code based encoding device and method, and to provide a polar-code based decoding device and method, which devices and methods can operate with reduced complexity.

The object is achieved by the embodiments provided in the appended claims.

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 data communication system <NUM> comprising a device <NUM> ("encoder") according to an embodiment of the invention. The device <NUM> is configured to encode an input sequence u, which comprises the bits of a message m, into a codeword x using a polar code.

The device <NUM> is generally configured to obtain the input sequence u to be transmitted (the "input sequence" may also be termed "information word" or "input vector"), and to produce the codeword x, which may contain redundancy. This codeword x may, then, be transmitted over a noisy communication channel <NUM> to a device <NUM> ("decoder") for decoding, e.g., according to another embodiment of the invention. This transmission typically introduces errors. The noisy signal may be received by the decoder <NUM> as a sequence of bits y (the "sequence of bits" may also termed "output vector"). The decoder <NUM> may then use the received bit values to calculate estimates of the transmitted codeword x and the transmitted message m. The set of possible codewords is called the code, or the channel code. In this embodiment, a polar code is used at the encoder <NUM> to encode the input sequence u. Both the encoder <NUM> and decoder <NUM> may know the polar code and, thus, may be aware of positions of the frozen bits F or information set I, respectively. The information set I (sometimes also called "reliability sequence") may be used by the decoder <NUM> in both determining the input sequence u (e.g. during successive decoding) and in extracting the message bits m from the input sequence u.

In particular, the encoder <NUM>, according to the embodiment of the invention, is configured to sequentially encode each of a plurality of blocks ui of the input sequence u based on an XOR operation to obtain a codeword block x'i of the codeword x'. Further, the encoder <NUM> is configured to sequentially output each obtained codeword block x'i of the codeword x'.

Moreover, the decoder <NUM> is configured to decode the sequence of bits y into an output sequence u using the polar code. The sequence of bits y represents the codeword x after transmission over the (noisy) communication channel <NUM>. The decoder <NUM>, according to an embodiment of the invention, is configured to sequentially decode each of a plurality of blocks of the sequence of bits y by applying a sliding window, in order to obtain an auxiliary sequence u'. Further, the decoder <NUM> is configured to process the auxiliary sequence u' to obtain the output sequence u, wherein each block of the output sequence u is processed based on an XOR operation of a block of the auxiliary sequence ui' and a previous block of the auxiliary sequence ui-<NUM>'. Furthermore, the device <NUM> can be configured to obtain message bits m from the output sequence u.

For the sake of the completeness, in the following, a summary of the theory behind the sliding window polar coding, as applied in embodiments of the invention, is given.

A sliding window polar code of length N and dimension K according to the invention, which it is decodable through a sliding window of size M, is designed as follows. Given S = N/M, its transformation matrix can be defined as T = W<NUM>S ⊗ TM/<NUM>, where <MAT>, with m = log<NUM>(M/<NUM>), is the transformation matrix of a classical polar code of length M/<NUM>, while W<NUM>S is a full binary lower triangular matrix of size <NUM>S. This matrix is given by a square matrix of size <NUM>S × <NUM>S having ones on and below the diagonal, and zeros above the diagonal. The resulting transformation matrix T can be described as a multi-kernel polar code (see the aforementioned work of Bioglio et al. This also permits to calculate the frozen set F accordingly.

In the following, as also exemplarily illustrated in <FIG>, an example of the proposed framework for a sliding window polar code of length N = <NUM> and dimension K=<NUM> with window size M = <NUM> is given. <FIG> is not according to the claimed invention but represents an example useful to understand the invention It is assumed that a message m = <NUM> is to be encoded. This message m can be encoded by means of the matrix T= W<NUM> ⊗ T<NUM>, wherein numerical representation of the matrices W<NUM>, T<NUM>, and T are shown as example in <FIG>. In order to perform the encoding of the message m, the information set I or, equivalently, the frozen set of bits F is needed. For the generation matrix T, the information set I is shown in <FIG> and may be given by I = {<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>}. Moreover, as illustrated in <FIG>, from the information set I, sub-information sets I<NUM> ={<NUM>}, I<NUM>={<NUM>}, I<NUM>={<NUM>,<NUM>}, I<NUM> = {<NUM>,<NUM>,<NUM>,<NUM>} may be obtained as well as the four corresponding sub-input vectors u<NUM> to u<NUM> populated accordingly (see <FIG>).

Depending on the sub-information set I<NUM>,. I<NUM>, the bits of the message m may be divided in four blocks m<NUM> = <NUM>, m<NUM> = <NUM>, m<NUM> = <NUM> and m<NUM> = <NUM> (see <FIG>). The input vector blocks ui are, then, given by u<NUM> = <NUM>, u<NUM> = <NUM>, u<NUM> = <NUM> and u<NUM> = <NUM> (see <FIG>). The encoder <NUM> may first calculate x'<NUM> = u<NUM> · T<NUM> = <NUM> and transmits it, then other codeword block may be calculated sequentially obtaining x'<NUM> = (u<NUM> ⊕ u<NUM>) · T<NUM> = <NUM>, x'<NUM> = (u<NUM> ⊕ u<NUM>) · T<NUM> = <NUM> and x'<NUM> = (u<NUM> ⊕ u<NUM>) · T<NUM> = <NUM> (see <FIG>).

At the decoder side, received blocks may be processed in couples to recover the auxiliary input vector u'. The first input vector is retrieved as u<NUM> = u'<NUM> = <NUM>. After the second auxiliary input vector u'<NUM> = <NUM> has been decoded, the second input vector block can be calculated as u<NUM> = u'<NUM> ⊕ u'<NUM> = <NUM> and the message block m<NUM> = <NUM> can be extracted. The other message blocks may be calculated accordingly with the subsequent auxiliary input vectors. In <FIG>, the exemplary input vector u, its shifted vector u, the vector u' obtained on the basis of u, and the corresponding codeword x' are shown. The transmitted codeword x' is received after transmission of the communication channel as vector y, as shown in <FIG>.

The proposed polar code design and decoding procedure improves BLER performance in the Device-to-Device (D2D) scenario (see <FIG>) without increasing the decoding computational complexity, and in some cases permitting to reach the performance of the full length polar code.

In the following, some methods for determining the information set I are described.

Under AWGN channel, the DE/GA method (see, e.g., <NPL>) can be used to evaluate bit-channels polarization of kernel W<NUM>S tracking the LLR mean as: <MAT> where µ is the imput LLR mean and function ϕ can be calculated as described in <NPL>. Using the above metrics, the reliability of each bit of the input vector u can be calculated. The K bits having the highest reliability may form the information set I, while the indices of the remaining N - K bit-channels may form the frozen set F of the code. The K message bits may then be inserted in the input vector u according to the information I set previously calculated, namely storing their values in the indices listed in I, while the remaining bits of u are set to zero. Codeword x' is then calculated as x' = u · T and transmitted through the channel <NUM> (see <FIG>).

The N channel LLRs may be stored in the vector y (see <FIG>). The decoder <NUM> may perform <NUM>S polar decoding of (M/<NUM>, Kt) polar codes. Upper LLRs L<NUM> may be initialized to zero (see <FIG>). At step t, a sub-information set It may be calculated from the information set I as the set of entries of I comprised between <MAT> and t · M/<NUM> reduced by (t - <NUM>) ·M/<NUM>. This sub-information set may be used as the information set of a polar code having transformation matrix TM/<NUM>. The M/<NUM> LLRs for this decoder <NUM> may be calculated as follows on the basis of y: the vector <MAT> is extracted from y, while a second vector L<NUM> of length M/<NUM> is calculated as: <MAT>.

The LLRs to be given to the current decoder are calculated on the basis of these two vectors as = (L<NUM> + L<NUM>) <IMG> L<NUM> , where
<MAT>.

Next, the (M/<NUM>, Kt) polar code defined by It may be decoded via SC using L as channel LLRs. Decoding can be performed with any other polar decoder (device <NUM>), e.g. SCL. The resulting input vector ut can then used to calculate the partial sums used in the SC decoding as xt = ut · TM/<NUM>; these partial sums are then used to update the upper LLRs L<NUM> as L<NUM> = (L<NUM> + L<NUM>) · (<NUM> - <NUM>xt). When t = <NUM>S, decoding is concluded, and input vector u is calculated appending all the sub input vectors as u = [u<NUM> u<NUM>.

As first, the device <NUM> may be configured to encode portions of the input vector u independently using a classical polar code. Moreover, the sliding window encoder mechanism may be implemented by the device <NUM> to perform on-the-fly encoding of incoming bits of message m.

The device <NUM> may divide the input vector u into <NUM> blocks of length M/<NUM> as u = [u<NUM> u<NUM>. u<NUM>S] and polar encode each block independently, i.e. by matrix multiplication with channel transformation matrix of size M/<NUM> as ci = ui · TM/<NUM>. According to an example which is not covered by the claims, these intermediary polar codewords ci can be used to create a sliding window polar codeword x', having a peculiar input vector u', by transmitting first the last one and performing a XOR operation with all the subsequent polar codewords before transmission. As a consequence, the final transmitted codeword x' is obtained as x' = [c<NUM>S|c<NUM> ⊕ c<NUM>S|c<NUM> ⊕ c<NUM>S|. |c<NUM>S-<NUM> ⊕ c<NUM>S].

The rationale to obtain the described framework can be found in the structure of the channel transformation matrix of a sliding window polar code. The codeword may be created on-the-fly without waiting to collect all the bits of the message m. In and embodiment which is not covered by the claims, starting from the original input vector u = [u<NUM> u<NUM>. u<NUM>S], this result can be obtained creating the auxiliary input vector u' = [u'<NUM> u'<NUM>. u'<NUM>S] imposing u'i = ui-<NUM> ⊕ ui with u<NUM> = <NUM>. This auxiliary input vector u' may then have the structure u' = [u<NUM>|u<NUM> ⊕ u<NUM>|u<NUM> ⊕ u<NUM>|. |u<NUM>S-<NUM> ⊕ u<NUM>S]. Given the nested property of frozen sets, it is known that Ii-<NUM> ⊇ Ii, where Ii is the information set of input vector block ui, so that u and u' share the same frozen set and u' is then well defined. This intermediary vector is in fact the input vector of codeword x' calculated with the proposed framework, x' = u' · T, since u' · T = [u<NUM>S · TM/<NUM>|(u<NUM> ⊕ u<NUM>S) · TM/<NUM>|(u<NUM> ⊕ u<NUM>S) · TM/<NUM>|. |(u<NUM>S-<NUM> ⊕ u<NUM>S) · TM/<NUM>]. As a consequence, the result of sliding window decoding of transmitted codeword x' will be the intermediary input vector u'. However, input vector u is needed to extract message bits, hence a further post processing step is needed at the receiver to retrieve message bits.

At the side of the decoder <NUM>, channel outcomes y corresponding to codeword x' can be decoded by applying the sliding window. As discussed previously, the result of the decoding process is the auxiliary input vector u'. This vector has to be post-processed to retrieve the original input vector u. This process consists of performing a XOR operation of each input vector block with the previously decoded one such that ui = u'i-<NUM> ⊕ u'i with u'<NUM> = <NUM>. As a consequence, original input vector can be calculated as u = [u'<NUM>|u'<NUM> ⊕ u'<NUM>|u'<NUM> ⊕ u'<NUM>|. |u'<NUM>S-<NUM> ⊕ u'<NUM>S].

Therefore, the proposed framework permits to create codes based on polarization that have on-the-fly encoding and decoding. The last input vector block u<NUM>S may be moved to the beginning of the message m. It can be supposed that the K bits of message m are going to be transmitted through a sliding window polar code of length N and dimension K with window size M and information set I. For each block ui forming the input vector u it is in this case possible to extract a sub-information set Ii of size Ki. The K message bits stored in vector m are then divided into <NUM>S blocks as m = [m<NUM> m<NUM> m<NUM>. m<NUM>S-<NUM>] of size K<NUM>, K<NUM>, K<NUM>,. , K<NUM>S-<NUM> respectively, where |m<NUM>| = K<NUM>S and I<NUM> = I<NUM>S. In and embodiment which is not covered by the claims, each block x'i of encoded vector x' is then calculated as x'i = (ui-<NUM> ⊕ u<NUM>) · TM/<NUM> for i = <NUM>,. ,<NUM>S, with the exception of first block that is calculated as x'<NUM> = u<NUM> · TM/<NUM>. Each block of codeword x' is then calculated using only two sub-input vectors, namely the very first and the current one.

At the decoder <NUM> side, the sliding window decoding may output blocks of auxiliary input vector u' sequentially. On-the fly decoding may calculate original input vector blocks as ui = u'i-<NUM> ⊕ u'i and extract message bits mi. Last input vector block u<NUM>S is used to calculate first message block m<NUM>.

<FIG> shows a communication system <NUM> comprising the device <NUM> for encoding the input sequence u according to an embodiment.

In particular, <FIG> shows the wireless communication system <NUM> including a base station <NUM> and user equipment (UE) <NUM> where the UE <NUM> may be a portable device such as a smart phone or tablet. The base station <NUM> includes a transmitter and the UE <NUM> a receiver, whereby the base station <NUM> is able to transmit data to the UE <NUM>, for example, in a downlink or uplink connection <NUM> made according to a telecommunications protocol. Embodiments of the invention may be applied in various communications systems. For example, it could be applied to any of a Global System for Mobile Communications (GSM), code division multiple access (CDMA), wideband code division multiple access (WCDMA), general packet radio service (GPRS), long term evolution (LTE), LTE frequency division duplex (FDD), LTE Time Division Duplex (TDD), a universal mobile telecommunications system (UMTS), enhanced mobile broadband (eMBB), ultra-reliable low-latency communications (URLLC) and massive machine-type communications (mMTC), or any 5th generation (<NUM>) wireless communication system.

<FIG> shows a method <NUM> for encoding an input sequence comprising message bits into a codeword using a polar code according to an embodiment.

<FIG> shows a method <NUM> for decoding a sequence of bits into an output sequence using a polar code, wherein the sequence of bits represents a codeword after a transmission over a communication channel <NUM> according to an embodiment.

The method <NUM> comprises: sequentially.

Claim 1:
A device (<NUM>) for encoding an input sequence comprising message bits into a codeword of a sliding window polar code of length N and dimension K which is decodable through a sliding window of size M, where a transformation matrix of the sliding window polar code is defined as T = W<NUM>S ⊗ TM/<NUM>, where S = N/M and m = log<NUM>(M/<NUM>), and where TM/<NUM> is a transformation matrix of a classical polar code based on a kernel matrix <MAT>, defined as <MAT>, and where W<NUM>S is a full binary lower triangular matrix of size <NUM>Sx2S, wherein the device is configured to:
- sequentially encode each of a plurality of blocks of the input sequence by applying the transformation matrix, TM/<NUM> to an auxiliary sequence to sequentially obtain each block of the codeword, wherein the auxiliary sequence is obtained by performing an XOR operation to the block and a previous block of the input sequence, or in case of the first block of the input sequence, the XOR operation is not performed; and
- sequentially output each obtained codeword block of the codeword.