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.

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.

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 an input vector u into two groups: the K good bit-channels that will carry the information bits and are indexed by the information set I, and the N - K bad bit-channels that are fixed to a predefined value (usually <NUM>) 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.

Polar codes are based on the fundamental kernel matrix <MAT>. Encoding of such a polar code of length N = <NUM>n and information length K is as follows. The frozen 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>, denoting the n-fold Kronecker product.

The reliability of the channels can be determined according to the Bhattacharyya parameter <MAT>.

Where W is a binary memory less 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 Gaussion noise (AWGN) channels reliabilities may be determined according to Gaussian approximation (GA). Other categories of noisy channels may be modelled such as a binary summetric channel (BSC) or a binary erasure channel (BEC), for example, using monte-carlo statistical methods.

Generally, different kernels of different sizes can be introduced in the code design, obtaining a multi-kernel polar code. When different kernels are used, the transformation matrix takes the form T = Ta ⊗ Tb ⊗. ⊗ Tg, where the suffixes a-g denote different kernel matrices, and the frozen set F has to be calculated accordingly.

Polar code decoding is based on Successive Cancellation (SC) decoding algorithm, which is inherently sequential. In SC decoding, the decoding is performed bit by bit. 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 hard decision for a first bit u<NUM> of the input vector u and feeds this decision back into the decoding process. Then a hard decision is made for second bit u<NUM> and the decision made for bit u<NUM> is fed back into the decoding process. Decoding proceeds in this fashion until a decision is obtained for the last bit uN such that an estimation is made of all of the bits of the input vector u.

SC list decoding (SCL) is an enhanced version of SC where multiple paths are followed during the decoding, and where the decision on the value of bits of the input vector are postponed to the end of the decoding process. Further error correction performance can be added with the help of a CRC applied as an outer code concatenated with the polar code.

<NPL>; <NPL>; and <NPL> disclose relevant background art.

The application provides a method of decoding according to claim <NUM>, methods of encoding according to claims <NUM> and <NUM>, an apparatus for decoding according to claim <NUM>, an encoding apparatus according to claim <NUM>, and a computer program according to claim <NUM>. Further aspects of the invention are defined in the dependent claims.

Example embodiments are described below in sufficient detail to enable those of ordinary skill in the art to embody and implement the systems and processes herein described.

Accordingly, while embodiments can be modified in various ways and take on various alternative forms, specific embodiments thereof are shown in the drawings and described in detail below as examples. There is no intent to limit to the particular forms disclosed. Elements of the example embodiments are consistently denoted by the same reference numerals throughout the drawings and detailed description where appropriate.

<FIG> shows a data communication system <NUM>. The data u to be transmitted, termed the information word or input vector, is given to the encoder <NUM>, which produces a codeword x which contains redundancy. This is transmitted over a noisy communication channel <NUM> which typically introduces errors. The noisy signal is then received by a receiver as an output vector y. The output vector y is provided to the decoder <NUM> at the receiver side, which uses the received values to calculate estimates of the transmitted codeword x and the transmitted data u. The set C of possible codewords is called the code, or channel code. In this embodiment, a polar code is used at the encoder to encode the input vector u. Both the encoder and decoder know the polar code and thus the positions of the frozen bits or information set are provided at each end. The information set (sometimes called a reliability sequence) is used by the decoder in both determining the decoded the input vector (e.g. during successive decoding) and in extracting the message bits from the input vector.

<FIG> shows a wireless communication system <NUM> including a base station <NUM> and user equipment (UE) <NUM> where the UE may be a portable device such as a smart phone or tablet. The base station <NUM> includes a transmitter and the UE a receiver, whereby the base station 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 <NUM>th generation (<NUM>) wireless communication system. For example, information or data in any of these systems encoded using a traditional error correcting code such as a Turbo code or an LDPC code on the base station <NUM> or UE <NUM> may be encoded instead using a code generated according to the following embodiments.

We consider communication between a transmitter and a receiver having different computational capabilities, namely when the receiver is less powerful than the transmitter, e.g. the downlink in the wireless communication system <NUM>. In the following embodiments, the transmitter is able to encode message data to create polar codewords of length N, while the receiver can process and decode only polar codewords of length M < N.

According to an embodiment, we describe how to design a polar code of length N and dimension K such that it is decodable through a sliding window of size M. To design a polar code means to provide a transformation matrix T and a frozen set F (or conversely the information set K.

The process of generating a polar code will be described with reference to the flow chart of <FIG>.

The transformation matrix T may be designed as follows. In a first step <NUM>, we obtain a first kernel matrix TM/<NUM>. Given S = N/M, where N is the length of the polar codeword to be generated at the encoder and M is the length of codeword that can be processed at a target decoder, <MAT> with m = log<NUM> (M/<NUM>) and the fundamental T<NUM> polar code matrix is given by <MAT>. Thus, TM/<NUM> is the transformation matrix of a classical polar code of length M/<NUM>.

The next stage <NUM> is to obtain a second kernel matrix W<NUM>S. In an embodiment, the kernel W<NUM>S is a kernel defined by a full binary lower triangular matrix of size <NUM>Sx2S. The value of S being as given before, S=N/M. The W<NUM>S kernel matrix is illustrated for an arbitrary value of <NUM> in <FIG>. The matrix can be redrawn as a factor graph comprising <NUM> input bit channels <NUM> and <NUM> output bit channels <NUM>. The rows in the graph are interconnected by a series of summation nodes which perform an XOR operation on bitwise inputs. The output of each summation node is fed into the input of the summation node in the row above. In this way the input values are iteratively reverse summed starting from the last bit value in the input bit channels <NUM>.

The transformation matrix is then determined according to the definition T = W<NUM>S ⊗ TM/<NUM>. In other words, the transfer matrix is defined as the Kronecker (tensor) product of the W<NUM>S kernel obtained in <NUM> with the classic transformation matrix of a polar code of length M/<NUM> This matrix his given by a square matrix of size <NUM>S × <NUM>S having ones on and below the diagonal, and zeros above the diagonal as depicted in <FIG>. Moreover, its factor graph representation is depicted in <FIG>. The Tanner graph of the resulting transformation matrix T can be described as a multi-kernel polar code and is depicted in <FIG> for the general case of an input vector u of size N. The number of connections shown in <FIG> illustrative and the actual number will depend on the kernel sizes for W<NUM>S and TM/<NUM>.

The Tanner graph <NUM> comprises a series of input channels or rows over which the values of an input vector <NUM> are received. In a first stage of the graph there are a series of TM/<NUM> encoding units <NUM>-<NUM> to <NUM>-<NUM> to which the input rows receiving the values of an input vector u are sequentially connected. The input vector can be considered as a series of sub-input vectors u<NUM> to u<NUM> each received at the inputs of a corresponding TM/<NUM> encoding unit which is encodes the M/<NUM> inputs according to a classical polar code kernel i.e. for a sub-input vector un the encoded bits are equal to un. These output bits are then spread evenly across the W<NUM>S coding units <NUM>-<NUM> to <NUM>-<NUM>, according to permutation network <NUM> such that each output is received at a corresponding one of the inputs of respective W<NUM>S coding units <NUM>-<NUM> to <NUM>-<NUM> in a second coding stage. Accordingly, the outputs of the first TM/<NUM> encoding unit are received by the first inputs of each W<NUM>S coding unit respectively, the outputs of the second TM/<NUM> unit are received at the second inputs of each W<NUM>S coding unit respectively, and so on. The outputs of the W<NUM>S coding units are then reordered according to the permutation connections (reordering network) <NUM> to output an encoded codeword x. The permutations (reordering) being such that a partial vector consisting of the first M/<NUM> values of the codeword x correspond to the first outputs from the four W<NUM>S coding units <NUM>-<NUM> to <NUM>-<NUM> respectively, a second partial vector consisting of the next M/<NUM> values of x correspond to the second outputs from the four W<NUM>S coding units <NUM>-<NUM> to <NUM>-<NUM>, and so on.

In the above embodiment, the selection of the second kernel matrix is a full binary lower triangular matrix of size 2Sx2S. However, other choices are possible for the second kernel matrix. In particular, the key property that enables the received codeword x to be sequentially decoded in portions with the decoding result of each portion being fed back into the decoding of the next portion, (i.e. by applying a sliding window) is that the inverse W-<NUM> of the second kernel matrix W consists of a lower triangular band matrix. As will be illustrated by way of a later embodiment, it is this property that allows each set of M values received to be iteratively decoded in t-uples of vectors of M/<NUM> values according to existing successive decoding update rules. The absence of '<NUM>'s in each column of W-<NUM> below a certain point ensures that only a subset of the N received LLRs need to be used for the decoding of a particular input bit ui.

A frozen set can be designed according to multi-kernel polar code mechanism. Reliabilities are determined for each output of the kernel matrix W<NUM>S and then propagated from right-to-left along the Tanner graph to the TM/<NUM> kernel matrices and determine the reliability at each input bit channel. The most reliable channels are determined from the resulting values and the frozen channel positions determined as the remaining unreliable channels.

Accordingly, we need to determine the polarization equations of the kernels W<NUM>S and TM/<NUM>. Under BEC, bit error probability can be calculated, while under AWGN channel, DE/GA method can be used [<NUM>]. This algorithm estimates the log-likelihood ratios (LLRs) distribution of the polarized channels by tracking their mean at each stage of the SC decoding tree. Given the block decoder representation of kernel W<NUM>S depicted in <FIG>, the bit error probability of bit ui of the kernel can be calculated as <MAT> where δ is the error probability of the input channels, while the LLR mean µi for a bit channel ui can be calculated as <MAT> where µ is the input LLR mean and function ϕ can be defined as <MAT> and can be approximated through curve-fitting. The curve fitting may be performed using methods known to those in the art, for example. as described in <NPL>.

Using the above metrics, the reliability of each bit of the input vector can be calculated; the K best bits will form the information set I, while the indices of the remaining N - K bit-channels form the frozen set F of the code.

The bit error probabilities log-likelihood ratio means of the classical polar code kernel can be determined in an existing manner that would be known to those skilled in the art.

With equations for both the TM/<NUM> and W<NUM>S matrices, given a known error probability or LLR mean at the output we can work back to determine a value that is a measure of the reliability of each bit channel in the transformation matrix.

The K message bits are 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, where T is the transformation matrix of the code calculated as previously described. Codeword x is then transmitted through the channel as shown in <FIG>.

Alternatively, codeword x can be calculated only on the basis of the transformation matrix TM/<NUM> of a polar code, e.g. without the need of implementing matrix W<NUM>S. In fact, given the sub-information set It for t = <NUM>,. ,<NUM>S, 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>, input vectors u<NUM>,. , u<NUM>S are created accordingly on the basis of the message bits. Each partial input vector is encoded independently through matrix multiplication by TM/<NUM>, obtaining partial codewords x<NUM>,. Finally, codeword x is obtained by backward accumulating the partial codewords starting from the last one, i.e. x = [x<NUM> ⊕. ⊕x<NUM>S,x<NUM>⊕. ,x<NUM>S-<NUM>⊕x<NUM>S,x<NUM>S]. where ⊕ applies a bitwise XOR operation when applied to binary partial codewords.

As an example, we will now describe the generation of a polar code when the N=<NUM>, M=<NUM> and, thus, S=N/M=<NUM>.

Given M/<NUM>=<NUM>, then the first kernel matrix <NUM> is selected as classical polar transformation matrix of dimension M/<NUM>, i.e. T<NUM> as shown in <FIG>. The second kernel matrix <NUM> is of dimensions 2Sx2S=4x4 and the 4x4 full binary lower triangular matrix W<NUM> is used. The transform matrix T of the generated polar code is then given by the Kronecker product of W<NUM> with T<NUM>, giving transformation matrix <NUM>, as shown.

The Tanner graph of the matrix <NUM> may be constructed using the coding blocks for T4
and W<NUM> shown in <FIG> respectively. The full Tanner graph is then as shown in <FIG>, consisting of four T<NUM> units <NUM>-<NUM> to <NUM>-<NUM> and four W<NUM> units <NUM>-<NUM> to <NUM>-<NUM> connected by reordering (permutation) network (connections) <NUM> and having outputs reordered according to reordering (permutation) network (connections) <NUM>. The input vector may be considered as a sequence of sub-input (partial) vectors u<NUM> to u<NUM> each having M/<NUM>=<NUM> bits and the output vector x is provided after the reordering network <NUM>. The encoded bits of the output vector x would then be propagated through a communications channel and received at a received as a vector y or received values (e.g. LLRs).

In this embodiment, LLR mean values are calculated as the basis for determining the reliability of each bit channel to which the bits of the input vector are applied. Thus, for the W<NUM> block equation (<NUM>) may be applied giving the expressions for µ<NUM>, µ<NUM>, µ<NUM>, µ<NUM> as shown in <FIG>. The corresponding expressions for the T<NUM> block are also shown and these are determined according to existing techniques known to those skilled in the art.

If we start at the right hand side of the Tanner graph and take the input mean LLR value to be µ = <NUM> then the resulting output mean LLRs for each bit channel i=<NUM>. <NUM> are given as µi = {<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>}. Low values correspond to unreliable channels and the order of the bit channels in terms of reliability is shown as the column <NUM> in <FIG>. Taking K=<NUM> information channels from the N bit channels upon which message bits can be transmitted, the information set is I = {<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>}. Conversely, the frozen set contains N-K channels and comprises F = {<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>}. Each of the bit channels in the frozen set is set to zero in the input vector and the message bits are placed in the positions indicated by the information set. Either the frozen set F or the information set I may be provided as a component of the polar code together with the transformation matrix as one is the converse of the other.

This can be illustrated by the following encoding example which uses the polar code of <FIG> already described above. Consider a message m = [<NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM>] that we wish to encode and transmit. If we use the frozen set F={<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>} then the resulting input vector u = [<NUM> <NUM> <NUM> <NUM> <NUM> <NUM> <NUM> <NUM> <NUM> <NUM> <NUM><NUM><NUM><NUM><NUM><NUM>], where the values shown in underline are the frozen bits set to <NUM> and the message bits m are inserted across the remaining positions. The encoded message x can then be calculated according to the transformation matrix T of <FIG> as: <MAT>.

Alternatively, the alternate encoding method already described above can be used that doesn't explicitly require generating the transformation matrix T. According to this process the input vector u= [<NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM>]. The input vector may be divided into sub-input vectors u<NUM> to u4 of length M/<NUM>=<NUM> such that, u<NUM>=[<NUM><NUM><NUM><NUM>], u<NUM>=[<NUM><NUM><NUM><NUM>], u<NUM>=[<NUM><NUM><NUM><NUM>], u<NUM>=[<NUM><NUM><NUM><NUM>]. Equivalently, a sub-information set I1 to I4 may be obtained from the information set I for the full polar code such that I<NUM> ={<NUM>}, I<NUM>={<NUM>}, I<NUM>={<NUM>,<NUM>}, I<NUM> = {<NUM>,<NUM>,<NUM>,<NUM>} and the four sub-input vectors u<NUM> to u<NUM> populated accordingly. Each of the sub-input vectors u<NUM> to u<NUM> may then be encoded using the T<NUM> classical polar transformation matrix. The resulting encoded vectors are x<NUM>=[<NUM><NUM><NUM><NUM>], x<NUM>=[<NUM><NUM><NUM><NUM>], x<NUM>=[<NUM><NUM><NUM><NUM>], x<NUM>=[<NUM><NUM><NUM><NUM>]. In order to generate the slidably decodable codeword, the following operation is performed: <MAT> where ⊕ denotes a bitwise XOR operation applied to binary partial codewords x<NUM> to x<NUM>.

This is further illustrated in <FIG>, and can intuitively be seen to be replicating the process denoted by the units <NUM>, <NUM>-<NUM> to <NUM>-<NUM>, and <NUM> of the Tanner graph of <FIG> but without explicit reference to the W4 transformation matrix. In particular, the reverse summation can be seen to correspond to the XOR operations carried out in the W<NUM> blocks <NUM>-<NUM> to <NUM>-<NUM> on the output values provided by the T<NUM> blocks <NUM>-<NUM> to <NUM>-<NUM>. As will become clear from the subsequent decoding embodiment, it is this iterative summation process which is inversed by application of a sliding window to received signal values of a codeword x encoded according to the above described embodiments.

Sliding window decoding of a polar codeword generated using a polar code designed according to the above example is performed such that <NUM>S polar decoding steps are used, each one using M channel signals (e.g. received signal values upon which LLRs are based). Each step outputs M/<NUM> bits of the input vector, using the M/<NUM> input bits decoded at the previous step to steer half of the LLRs used in the decoding. We consider can consider the W2S block, as shown in <FIG> as a decoding box having u<NUM>. <NUM> input channels and x<NUM>. <NUM> decoded output values.

In general, the decoding proceeds as shown in <FIG> and according to the flow chart of <FIG>. In a first step <NUM>, a window <NUM> is applied to a received sequence of signal values corresponding to likelihoods of the coded bits x received at decoder. In the example shown in <FIG>, the received signal has N=<NUM> values and the window size M=<NUM>.

Then at a second step <NUM> a sub-input vector is calculated from the windowed values. Where the sub-input vector ut , where t is the number of the decoding step, is comprised of M/<NUM> bits and is calculated from M/<NUM> likelihood values (LLRs) which are derived from the windowed values. As will be seen these are derived by combining the values according to the Tanner graph representation of the Polar code as previously shown in <FIG> and <FIG>, for example. Once the sub-input vector u<NUM> is calculated at the first window position, at <NUM> the window is shifted to a further (e.g. second position) <NUM>. In particular, the window is shifted to the right from an initial position by M/<NUM> values. Further likelihood values are determined at <NUM> corresponding to the second position in a similar manner as the first but also taking into account the LLR values now having been discarded in moving the window position. A further sub-input vector u<NUM> is then decoded based on the derived likelihoods (Step <NUM>).

At <NUM>, a determination is made as whether all the received signal values have been decoded. In other words, have all the sub-input vectors that make up the input vector been decoded from the received signal values. If the answer is 'No' then the process returns to step <NUM> and the window is shifted by M/<NUM> values to a further position <NUM> and the decoding process continues. At <NUM>, in obtaining the further likelihood values not only are the likelihoods discarded from the immediately preceding window taken into account but also all preceding but now discarded values. This may be achieved by maintaining a buffer that is updated at the end of each decoding stage by performing a process using the values that are to imminently be discarded. A specific embodiment describing this process will be described subsequently.

If the answer is "yes" at step <NUM> then the process moves to step <NUM> in which message/information bits are determined from the sub-input vectors which when concatenated together comprise the full input vector into which the information bits to be decoded have been inserted. The information bits can be extracted using the information set (i.e. reliability sequence) which specifies the bit positions containing information (good channels) and those containing frozen bit values (noisy/bad channels). The information set is the full-length information set corresponding to the polar code generated above having the length N.

A decoding example is depicted in <FIG> whereby the window position is changed at each stage t of a decoding process. A received signal y comprises multiple LLR values. The LLR values are based on signals received when the codeword correspond to the previous encoding example where N=<NUM> and M=<NUM> traverses a communications channel. In this example, two LLR values <NUM>, <NUM> have a sign error. A first window position <NUM> is denoted by t=<NUM> and a shifted window position <NUM> by t=<NUM>, for example. The window is shifted again to a further position <NUM> at t=<NUM> but remains at the same position for t=<NUM>. The window is shifted at each stage by M/<NUM>=<NUM> values in this example. The resulting sub-input vector ut decoded at each stage t is fed forward to the next decoding stage and used together with the LLR values from y at the shifted position to decode the next sub-input vector. The frozen bits indicated by underline, are set according to respective a sub-information set It determined from the information set I of the full length polar code. As only the last M/<NUM> values are used in the final decoding step, the window at t=<NUM> can be considered the same as at t=<NUM>. Another way to view this, would be that the window is shifted at t=<NUM> but the window extends beyond the codeword and those values are not used and are set to infinity. The output sub-input vectors u<NUM>, u<NUM>, u<NUM>, u<NUM> are concatenated to determine the full input vector u.

In embodiments, the received signal values y are log likelihood ratios (LLRs) and the decoding process based on a successive cancellation (SC) decoding scheme. However, it is noted that other existing polar decoding schemes (e.g. successive cancellation list (SCL) decoding) may alternatively be used to iteratively determine the values of the input vector by evaluating and updating received values as they propagate through the Tanner graph, making hard decisions on the input bits based on the propagated received values and knowledge of the positions of the frozen bits according to the polar code. Further, although log-likelihood ratio (LLR) values are used here, another measure of likelihoods based on received signal values (e.g. from a demodulated signal) may be used. LLR values are convenient computationally because they avoid computational under-flow occurring when the algorithm is implemented by a processor.

In general, the log-likelihood ratios (LLRs) are propagated along the Tanner graph from right-to-left and hard decisions on the decoded bits of the input vector u are passed from left-to-right and used to update the LLR values in subsequent branches for consistency with the decoded bits. Initially, the LLRs of the coded bits x based on the received vector y are calculated at the receiver. The received signal is decoded bit-by-bit using LLR propagation through the graph to retrieve the transmitted input vector u (i.e. the transmitted message). For every bit ui, the position i is checked against the information set which indicates the bit positions of the input vector that contain frozen bits and those that contain information bits. If the position i of the bit ui corresponds to a frozen bit then its value is decoded as the predetermined value ui=<NUM>, and the decoder moves on to evaluating the next bit. If the information set indicates that ui is an information bit, then a corresponding LLR is recursively calculated for that bit position. A decision is then taken based on the calculate LLR as to the value of the bit ui at that position. This is typically done according to a threshold, where negative LLR values are indicative of '<NUM>' and positive values indicative of a '<NUM>'. The determination of the LLR for the bit ui generally involves receiving LLR values from a preceding stage in the multi-kernel tanner graph and updating the values according to the update rules for that kernel block. Each kernel block consists of recursively connected iterations of the fundamental T<NUM> polar code block and uses existing decoding rules for the existing polar codes kernel. Such that where (u<NUM>u<NUM>). T<NUM> = (x<NUM>x<NUM>), with <MAT>, and where λi and li denote LLRs at the input vector side and output side (i.e. received LLR values) respectively, and ui and xi denote the hard decision on the bit values being decoded. The hard decision update rules dictate that <MAT> <MAT>.

Further, the inverse update rules (i.e. going from right-to-left in the Tanner graph) are u<NUM> = x<NUM> + x<NUM> and u<NUM> = x<NUM> = u<NUM> + x<NUM> which corresponding to the message update equations:
<MAT>
<MAT> and
<MAT>.

A further embodiment of the decoding process is provided in <FIG>. Let us suppose that the N channel LLRs are stored in the vector y consisting of received values of codeword transmitted over a noisy channel. The decoder performs t=<NUM>. <NUM> polar decoding steps of (M/<NUM>, Kt) polar codes, where Kt is the number of information bits in a sub-information set It for the classical polar code with transformation matrix TM/<NUM>. The value t indicates a decoding window position for M signal values which are derived as set out below.

In an initialization step <NUM>, upper LLRs L<NUM> (LLR buffer) are initialized to zero. We call these upper LLRs because they relate to the LLRs that propagates downwards from an upper branch in the Tanner graph derived in a previous decoding window t. The input vector y is initialized with LLR values corresponding to values of a signal received at the decoder. An information set I is initialized with the reliability sequence of the full multi-kernel polar code by which the received signal was encoded. The step counter t is initialized to t=<NUM>.

At step <NUM>, sub-information set It is calculated from the information set I as the set of entries of I comprised for the values in the current decoding window defined by t. The values of It are the values of I between <MAT> and t · M/<NUM> reduced by (t - <NUM>) · M/<NUM>; obviously, Kt = |It|. This sub-information set will be used as the information set of a polar code having a classical polar code transformation matrix TM/<NUM>.

The next step is to extract sub-channel LLRs L<NUM> and L<NUM> from the received signal values y. The M/<NUM> LLRs for this decoder are 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 first and second sub-channel LLRs L<NUM> and L<NUM> are then used in step <NUM> to derive the channel LLRs L. The channel LLRs L to be used for the current decoding step are calculated on the basis of these two vectors as
<MAT>
where
<MAT>.

This is derivable from the update rules for existing successive cancellation decoding according to equation (<NUM>) set out above when applied to the branches of the Tanner graph of the decoding box W<NUM>.

Next, at steps <NUM> and <NUM> the (M/<NUM>, Kt) polar code defined by It is decoded via SC decoding using L as channel LLRs and based on the Tanner graph for the classical polar code TM/<NUM> block. Successive cancellation decoding results in a sub-input vector ut (step <NUM>). In SC decoding, the hard decisions made on the bits of the sub-input vector ut are further used to calculate the partial sums xt used in the SC decoding such that xt = ut · TM/<NUM>. Accordingly, the SC decoding provides both ut and xt as outputs.

In step <NUM>, the partial sums xt are then used to update the upper LLRs L<NUM> as <MAT>.

Again, this is based on the classical successive decoding update rules when applied to the nodes of the Tanner graph of the W<NUM>S block, specifically update equation <NUM> mentioned above.

Further, at step <NUM> it is determined if t = <NUM>S. If t = <NUM>S, decoding is concluded, and input vector u is calculated at step <NUM> by appending all the decoded sub input vectors to form u = [u<NUM> u<NUM>.

If at step <NUM> it is determined that t is not equal to <NUM> then the process returns to step <NUM> t is incremented by <NUM> at step <NUM> and another decoding step is performed. The increment of the value of t by <NUM> having the effect of shifting a decoding window by M/<NUM> values to the right other than for the last position where the L<NUM> values are the last M/<NUM> values of the received signal and the L<NUM> values are taking as infinity. Accordingly, as will be appreciated, standard a successive cancellation decoder may be used to decode received signal values of a codeword encoded according the earlier described embodiments of a multi-kernel polar code.

An example of a decoding process using successive decoding will now be described when applied to a polar code where N=<NUM> as per the example code generation and encoding example shown in <FIG> and already described above. Assume that the following polar encoded binary sequence from the encoding example above, has been generated and is transmitted over a channel: <MAT> <MAT>.

In the initialization step the following are received as the channel LLRs, <MAT> and the following as the information set, <MAT> further the M/<NUM>=<NUM> LLR buffer values (upper LLR values) are set to zero such that <MAT>.

The channel LLR values shown in underline have a sign error due to the noise in the channel. As will be demonstrated the error correcting properties of the polar code will allow the correct input vector u and encoded bit values x to be decoded from the channel LLRs.

<FIG> show an example embodiment in which a Tanner graph becomes populated with determined values at each of four decoding stages t=<NUM>. Considering first of all t=<NUM> and <FIG>, from the received values y, L<NUM> = {<NUM>, -<NUM>, <NUM>, <NUM>} and L<NUM>={-<NUM>, <NUM>, -<NUM>, <NUM>}. The L<NUM> and L<NUM> values are propagated across the permutation network <NUM> such that they are provided to the first and second rows of the W4 decoding blocks <NUM>-<NUM>. <NUM>-<NUM> respectively. Because there is no upper LLRs for the first iteration the buffer L<NUM> is zero and L<NUM>+ L<NUM>=L<NUM>, and thus the channel LLRs are L = L<NUM> <IMG> L<NUM> = {-<NUM>, -<NUM>, -<NUM>, <NUM>}. The channel LLRs L are propagated across the permutation network <NUM> such that are provided at the outputs of the first T<NUM> polar coding block <NUM>-<NUM>. Thus, these values can be successively decoded across the polar coding block using the sub information set I<NUM> = {<NUM>}. The resulting decoded sub-input vector u<NUM>= [<NUM><NUM><NUM><NUM>] and the partial sum values x<NUM> = [ <NUM><NUM><NUM><NUM>]. The partial sum values propagate from left-to-right and are used to update the upper LLR buffer according to L<NUM> = (L<NUM> + L<NUM>) · (<NUM> - <NUM>x<NUM>) = L<NUM> · (<NUM> - <NUM>x<NUM>)= {-<NUM>, <NUM>, -<NUM>, - <NUM>}.

At the next stage t=<NUM> shown in <FIG>. The decoding window is shifted by <NUM> values and the sub-channel LLRs become L<NUM> = {-<NUM>, <NUM>, -<NUM>, <NUM>} and L<NUM> = {<NUM>, <NUM>, <NUM>, -<NUM>}. The L<NUM> and L<NUM> values are propagated across the permutation network <NUM> such that they are provided to the second and third rows of the W4 decoding blocks <NUM>-<NUM>. <NUM>-<NUM> respectively. The buffer L<NUM> updated at the end of the first stage is equal to {-<NUM>, <NUM>, -<NUM>, -<NUM>} and, thus L<NUM> + L<NUM> = {-<NUM>, <NUM>, -<NUM>, <NUM>}.

Thus, the channel LLRs are L = (L<NUM> + L<NUM>) <IMG> L<NUM> = {-<NUM>, -<NUM>, -<NUM>, <NUM>}. The channel LLRs L are propagated across the permutation network <NUM> such that are provided at the outputs of the second T<NUM> polar coding block <NUM>-<NUM>. Again, these values are successively decoded across the polar coding block using the sub information set I<NUM> = {<NUM>} derived from the information set I values that correspond to the bit positions of the second sub-input vector. The resulting decoded sub-input vector is u<NUM>= [<NUM><NUM><NUM><NUM>] and the partial sum values x<NUM> = [ <NUM><NUM><NUM><NUM>]. The update of the upper LLR buffer proceeds according to L<NUM> = (L<NUM> + L<NUM>) · (<NUM> - <NUM>x<NUM>) = {-<NUM>, <NUM>, -<NUM>, -<NUM>}.

The third stage t=<NUM> is shown in <FIG>. The decoding window is shifted by <NUM> values and the sub-channel LLRs become L<NUM> = {<NUM>, <NUM>, <NUM>, -<NUM>} and L<NUM>= {-<NUM>, -<NUM>, -<NUM>, -<NUM>}. The L<NUM> and L<NUM> values are propagated across the permutation network <NUM> such that they are provided to the third and fourth rows of the W4 decoding blocks <NUM>-<NUM>. <NUM>-<NUM> respectively. The buffer L<NUM> is {-<NUM>, <NUM>, -<NUM>, -<NUM>} from the previous update and, thus, L<NUM>+ L<NUM>= {<NUM>, - <NUM>, <NUM>, -<NUM>}.

Thus, the channel LLRs are derived as L = (L<NUM> + L<NUM>) <IMG> L<NUM> = {-<NUM>, <NUM>, -<NUM>, <NUM>}. The channel LLRs L are propagated across the permutation network <NUM> such that are provided at the outputs of the third T<NUM> polar coding block <NUM>-<NUM>. Again, these LLR values are used to perform successive decoding across the polar coding block using the sub information set I<NUM> = {<NUM>, <NUM>} derived from the information set I values that correspond to the bit positions of the second sub-input vector. The resulting decoded sub-input vector is u<NUM>= [<NUM><NUM><NUM><NUM>] and the partial sum values x<NUM> = [ <NUM><NUM><NUM><NUM>]. The update of the upper LLR buffer proceeds according to L<NUM> = (L<NUM> + L<NUM>) · (<NUM> - <NUM>x<NUM>) = {-<NUM>, -<NUM>, -<NUM>, -<NUM>}. Decoding then proceeds to the final stage t=<NUM>, effectively the window is shifted so that only the last four values are within the decoding window. This means that the sub-channel LLRs become L<NUM> = {-<NUM>, -<NUM>, -<NUM>, -<NUM>} and L<NUM>= {∞, ∞, ∞, ∞}. The L<NUM> values are propagated across the permutation network <NUM> such that they are provided to fourth rows of the W4 decoding blocks <NUM>-<NUM>. <NUM>-<NUM> respectively. The buffer L<NUM> is {-<NUM>, -<NUM>, -<NUM>, -<NUM>} and, thus, L<NUM>+ L<NUM>= {-<NUM>, -<NUM>, -<NUM>, -<NUM>}.

Thus, the channel LLRs are derived as L = (L<NUM> + L<NUM>) <IMG> L<NUM> = {-<NUM>, -<NUM>, -<NUM>, -<NUM>}. The channel LLRs L are propagated across the permutation network <NUM> such that are provided at the outputs of the third T<NUM> polar coding block <NUM>-<NUM>. Again, these LLR values are used to perform successive decoding across the polar coding block using the sub information set I<NUM> = {<NUM>,<NUM>,<NUM>,<NUM>} derived from the information set I values that correspond to the bit positions of the second sub-input vector. The resulting decoded sub-input vector is u<NUM>= [<NUM><NUM><NUM><NUM>]. As this is the final decoding step, the steps of determining the partial sum values x<NUM> and updating the buffer L<NUM> are redundant and may be omitted.

The derived sub-input vectors u<NUM>= [<NUM><NUM><NUM><NUM>] , u<NUM>= [<NUM><NUM><NUM><NUM>] , u<NUM>= [<NUM><NUM><NUM><NUM>] , u<NUM>= [<NUM><NUM><NUM><NUM>] may be concatenated and the decoded input vector u is <MAT>.

From the information set I, the decoded message is thus, <MAT> and matches the message as originally encoded using the generated multi-kernel polar code according to this embodiment.

<FIG> is a block diagram of an apparatus for generating a Polar code.

An apparatus <NUM> shown in <FIG> includes an a first obtaining unit <NUM>, a second obtaining unit <NUM>, a generating unit <NUM> and an information set unit <NUM>.

The first obtaining unit <NUM> obtains a first matrix as an m-fold Kronecker product of a 2x2 binary lower triangular matrix where m= log2(M/<NUM>), M<N, and N is the length of a polar code to be generated.

The second obtaining unit <NUM> obtains a second matrix of dimension 2Sx2S, where S=N/M and the inverse of the second matrix is a lower triangular band matrix.

The generating unit <NUM> generates a transformation matrix for the polar code by calculating a Kronecker product of the second matrix with the first matrix.

The information set unit <NUM> determines an information set I identifying reliable bit channels for the polar code. The selection by the first and second selecting units is such that a polar codeword of length N may be obtained using the polar code that is decodable by iteratively applying a sliding decoding window of length M to the polar codeword, where M<N.

Additionally, an encoder <NUM> may be provided that receives the polar code from the apparatus <NUM> and uses it to encode a message to be transmitted on a communications channel. Further, a transmitter <NUM> may be provided (that may include an antenna) that is capable of transmitted the encoded message data across a channel e.g. by modulating a signal and transmitting it via an antenna.

The apparatus <NUM>, <NUM> and <NUM> shown in <FIG> can implement each step of the method shown in <FIG>. To avoid repetition, detailed description is not repeated. The encoder <NUM> and the transmitter <NUM> may be embodied on a base station element of a communications network or user equipment such as a smart phone or tablet.

<FIG> is a block diagram of an apparatus for decoding a received signal according to an embodiment of the present invention. The apparatus <NUM> shown in <FIG> includes a window unit <NUM>, a first decoding unit <NUM>, a shifting unit <NUM>, a likelihood obtaining unit <NUM> and a second decoding unit <NUM>.

The window unit <NUM> applies at a first position, a window of length M to a received signal containing N signal values, where M<N.

The first decoding unit <NUM> decodes a first sub-input vector using a polar code and first channel likelihoods L based on signal values obtained from the window at the first position.

The shifting unit <NUM> shifts the window position to second position.

The channel likelihood obtaining unit <NUM> obtains second channel likelihoods L based on the signal values from the window at the second position and the decoded first sub-input vector.

The second decoding unit <NUM> decodes a second-sub-input vector using a polar code and the second channel likelihoods.

A receiver <NUM> may be provided that receives a signal to be decoded e.g. via a communications network and provides it to the apparatus <NUM>. A demodulator <NUM> may be provided that demodulates the signal received at the receiver <NUM> before providing it to the apparatus <NUM> for decoding.

The apparatus <NUM>, <NUM> and <NUM> shown in <FIG> can implement each step of the method shown in <FIG> and <FIG>. To avoid repetition, detailed description is not repeated. The apparatus <NUM>, <NUM>, and <NUM> may be located in any network element, for example, may be located in a user equipment or a base station.

<FIG> is a schematic block diagram of an apparatus according to another embodiment of the present invention. An apparatus <NUM> shown in <FIG> may be configured to implement each step and method in the foregoing method embodiments. The apparatus <NUM> may be applied to a base station or a terminal in various communications systems. In an embodiment shown in <FIG>, the apparatus <NUM> includes a processing unit (including one or more processors) <NUM>, a memory <NUM>, a transmitter/receiver circuit <NUM>, and an antenna <NUM>. The processing unit <NUM> controls an operation of the apparatus <NUM>, and may also be called a CPU (Central Processing Unit, central processing unit). The memory <NUM> may include a read-only memory and a random-access memory (RAM), and provides an instruction and data for the processing unit <NUM>. A part of the memory <NUM> may further include a nonvolatile random-access memory (NVRAM). In an actual application, the apparatus <NUM> may be embedded into or may be a wireless communications device such as a mobile phone or other portable communications device such as a smart phone or tablet. The transmitter/receiver circuit <NUM> may be coupled to the antenna <NUM>. Components of the apparatus <NUM> are coupled together through a bus system <NUM>, where the bus system <NUM> may further include a power bus, a control bus, and a status signal bus, in addition to a data bus. However, for clear description, all buses are marked as the bus system <NUM> in <FIG>.

The method disclosed in the embodiments of the present invention may be applied in processing unit <NUM>. In a process of implementation, each step of the method may be completed by using an integrated logic circuit of hardware in the processing unit <NUM> or instructions in a software form. These instructions may be implemented and controlled by using the processing unit <NUM>. Configured to execute the method disclosed in the embodiments of the present invention, the foregoing processing unit may include a general-purpose processor, a digital signal processor (DSP), an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or another programmable logic device, a discrete gate or transistor logic device, or a discrete hardware component; and can implement or execute each disclosed method, step, and logic block diagram in the embodiments of the present invention. The general-purpose processor may be a microprocessor or the processor may be any common processor or decoder, and so on. The step with reference to the method disclosed in the embodiments of the present invention may be directly executed and completed by a hardware decoding processor or executed and completed by a combination of hardware and a software module in a decoding processor. The software module may be located in a mature storage medium in the art, such as a random-access memory, a flash memory, a read-only memory, a programmable read-only memory, an electronically erasable programmable memory, or a register. The storage medium is located in the memory <NUM>, and the processing unit <NUM> reads information in the memory <NUM>, and completes the steps of the method with reference to the hardware. For example, the memory <NUM> may store information about an obtained Polar code or frozen or information set for the processing unit <NUM> to use during encoding or decoding.

A communications system or a communications apparatus according to an embodiment of the present invention may include the apparatus <NUM> the apparatus <NUM> or the apparatus <NUM>.

The block error rate (BLER) performance of the sliding window design and decoding of polar codes in embodiments of the disclosure may be compared with independent block transmission and optimal full polar code transmission. Specifically, we consider the scenario where the transmitter has to send K bits to the receiver at a rate R = K/N, i.e. it should transmit N bits, however the receiver can handle only M < N bit per reception due to limited decoding capabilities.

In the following, we show a performance result under SC (SCL-<NUM> in the figures) and SCL decoding. <FIG> studies the case where N = <NUM>, K = <NUM> and M = <NUM>, i.e. having a rate R = <NUM>/<NUM>, while <FIG> studies a similar scenario where K = <NUM> and the rate is R = <NUM>/<NUM>. <FIG> shows that proposed solution slightly outperforms IND under SC decoding, but is far away from full polar code; this gap is annulled under SCL, while IND is not able to improve its performance. <FIG> shows that proposed solution permits up to 1dB gain over state-of-the-art, even if results are still far from optimality. Finally, <FIG> studies the case where N = <NUM>, K = <NUM> and M = <NUM>, i.e. having a rate R = <NUM>/<NUM>. In this case, gain is still around 1dB over IND. In general, the simulations show that embodiments of the invention always provide a better block error rate than existing solutions, and in some cases may even reach optimal BLER performance.

A person of ordinary skill in the art may be aware that, in combination with the examples described in the embodiments disclosed in this specification, units and algorithm steps may be implemented by electronic hardware, or a combination of computer software and electronic hardware. A person skilled in the art may use different methods to implement the described functions for each particular application, but it should not be considered that such implementation goes beyond the scope of the present invention.

It may be clearly understood by a person skilled in the art that, for the purpose of convenient and brief description, for a detailed working process of the foregoing system, apparatus, and unit, reference may be made to the corresponding process in the foregoing method embodiments, and details are not described herein again.

In the embodiments provided in the present application, it should be understood that the disclosed system, apparatus, and method may be implemented in other manners. For example, the described apparatus embodiment is merely exemplary. In addition, the displayed or discussed mutual couplings or direct couplings or communications connections may be implemented through some interfaces. The indirect couplings or communications connections between the apparatuses or units may be implemented in electronic, mechanical, or other forms.

A part or all of the units may be selected according to actual needs to achieve the objectives of the solutions of the embodiments.

When the functions are implemented in the form of a software functional unit and sold or used as an independent product, the functions may be stored in a computer-readable storage medium. Based on such an understanding, the technical solutions of the present invention essentially, or the part contributing to the prior art, or a part of the technical solutions may be implemented in the form of a software product. The computer software product is stored in a storage medium, and includes several instructions for instructing a computer device (which may be a personal computer, a server, or a network device) to perform all or a part of the steps of the methods described in the embodiments of the present invention. The foregoing storage medium includes: any medium that can store program codes, such as a USB flash drive, a removable hard disk, a read-only memory (ROM, Read-Only Memory), a random access memory (RAM, Random Access Memory), a magnetic disk, or an optical disc.

Claim 1:
A method of decoding a received signal representing a multi-kernel polar code of length N, the method comprising:
applying (<NUM>), at a first position, a window of length M to a received signal containing N signal values, where M<N;
decoding (<NUM>) a first sub-input vector using a multi-kernel polar code and first channel likelihoods L based on signal values obtained from the window at the first position;
shifting (<NUM>)the window position to a second position;
obtaining (<NUM>) second channel likelihoods L based on the signal values from the window at the second position and the decoded first sub-input vector; and
decoding a (<NUM>) second sub-input vector using the multi-kernel polar code and the second channel likelihoods;
the polar code being obtained as a Tanner graph of a transformation matrix T, the transformation matrix T being obtained as the Kronecker product of a first kernel matrix and a second kernel matrix, the first kernel matrix being of size M/<NUM> x M/<NUM> and being obtained as m-fold Kronecker product of the 2x2 full binary lower triangular matrix, where m=log2(M/<NUM>) and the second kernel matrix being of size <NUM> x <NUM>
wherein S=N/M, such that the transformation matrix T is of size N;
wherein the inverse of the second kernel matrix is a lower triangular band matrix.