Coding and decoding of polar codes extended to lengths which are not powers of two

Abstract

An encoding apparatus includes a processor a non-transitory computer-readable storage medium storing a program for encoding data into a codeword. The program includes instructions to encode the data x using a code that is a product of a matrix generated using the Kronecker product of the Q with itself and factors generated according to frozen bit indices of the code and a constraint matrix generated according to a precoding matrix.

Claims

1. An encoding apparatus, comprising: a processor; and a non-transitory computer-readable storage medium storing a program for encoding data x of dimension k into a codeword c of length n, the program to be executed by the processor, the program including instructions to: encode the data x using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2.sup.m.sup.1+ . . . +2.sup.m.sup.s, wherein m.sub.h, h=1, . . . , s, is an integer number, on the basis of the equation:
c=uA, wherein u.sub.i=x.sub.j.sub.i, 0j.sub.i<k1, if i.Math.F, wherein F is a set of nk frozen bit indices of the code C(n, k, d), and u.sub.i=.sub.s=0.sup.i1u.sub.s, if iF, wherein is a constraint matrix given by a solution of the equation:
=0, wherein .sub.i is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as: $A=\left(\begin{array}{cccc}{A}_{m_1}& 0& \mathrm{.Math.}& 0\\ 0& A_{m_2}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& A_{m_s}\end{array}\right),$ and wherein $A_{m_h}={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_h},$ and wherein Q.sup..Math.m denotes the m-times Kronecker product of a matrix Q with itself; and send, after the codeword c is encoded, encoded codeword c over a transmission channel to a decoding apparatus for recovery of correct symbols of codeword c.

2. The encoding apparatus of claim 1, wherein the program further includes instructions to: construct the code C(n, k, d) according to a plurality of nested linear block codes C.sub.ij(2.sup.m.sup.i,K.sub.i,j,d.sub.ij), K.sub.i,j+1>K.sub.i,j, 0j<.sub.i, wherein .sub.i is a positive integer, wherein a generator matrix of C.sub.ij(2.sup.m.sup.i,K.sub.i,j,d.sub.ij) is given by the equation: ${\tilde{G}}^{\left(i,j\right)}=\left(\begin{array}{c}{G}^{\left(i,0\right)}\\ G^{\left(i,1\right)}\\ \mathrm{.Math.}\\ G^{\left(i,j\right)}\end{array}\right),$ wherein G.sup.(i,j) is a k.sub.i,j2.sup.m.sup.i matrix, K.sub.i,j=s=0.sup.jk.sub.i,s, wherein a precoding matrix of G.sup.(i,j) is defined by $W^{\left(i,j\right)}={G^{\left(i,j\right)}\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.i},$ wherein a precoding matrix of {tilde over (G)}.sup.(i,j) is defined by {tilde over (W)}.sup.(i,j)= ${\tilde{W}}^{\left(i,j\right)}={{\tilde{G}}^{\left(i,j\right)}\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.i},$ and wherein an index l.sub.iip of a column, where a p-th row of the matrix {tilde over (W)}.sup.(i,.sup.i.sup.1) starts, is defined by the equation $l_{i,p}=\min \underset{{\tilde{W}}_{p,t}^{\left(i,{}_i-1\right)}=1}{0t<2^i}t,$ and construct the precoding matrix as a block matrix, wherein the blocks of the precoding matrix consist of selected rows of the matrices {tilde over (W)}.sup.(i,j).

3. The encoding apparatus of claim 2, wherein the plurality of nested linear block codes C.sub.ij(2.sup.m.sup.i,K.sub.i,j, d.sub.ij) are extended Bose-Chaudhuri-Hocquenghem (e-BCH) codes.

4. The encoding apparatus of claim 2, wherein the program further includes instructions to construct a precoding matrix of the code C(n, k, d) according to: $\widetilde{\mathrm{��}}=\left(\begin{array}{ccccc}{\tilde{W}}^{\left(1,r_1\right)}& 0& 0& \mathrm{.Math.}& 0\\ 0& {\tilde{W}}^{\left(2,r_2\right)}& 0& \mathrm{.Math.}& 0\\ 0& 0& {\tilde{W}}^{\left(3,r_3\right)}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& 0& \mathrm{.Math.}& {\tilde{W}}^{\left(s,r_s\right)}\\ W^{\left(1,r_1+1\right)}& {\hat{W}}^{\left(2,1\right)}& {\hat{W}}^{\left(3,1\right)}& \mathrm{.Math.}& {\hat{W}}^{\left(s,1\right)}\\ 0& W^{\left(2,r_2+1\right)}& {\hat{W}}^{\left(3,2\right)}& \mathrm{.Math.}& {\hat{W}}^{\left(s,2\right)}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\end{array}\right),$ wherein r.sub.i=max.sub.j:d.sub.ij.sub.d j is an index of a largest e-BCH code of length 2.sup.m.sup.i having a minimum distance of at least d, and wherein .sup.(i,j) is a matrix defined on the basis of the matrix {tilde over (W)}.

5. The encoding apparatus of claim 2, wherein the program further includes instructions to construct the matrix .sup.(i,j) using rows of the matrix {tilde over (W)}.sup.(i,.sup.j.sup.) having the smallest value of P.sub.m.sub.i.sub.,l.sub.i,p, wherein P.sub.m,i is an error probability in a bit subchannel W.sub.m.sup.(i)(y.sub.0.sup.2.sup.m.sup.1,u.sub.0.sup.i1|u.sub.i), and wherein y.sub.0.sup.2.sup.m.sup.1=y.sub.0 . . . y.sub.2.sub.m.sub.1 denotes 2.sup.m1 noisy symbols of the codeword c after a transmission over a communication channel.

6. The encoding apparatus of claim 2, wherein the program further includes instructions to arrange the rows of the matrix W.sup.(i,r.sup.i.sup.+1) or .sup.(j,i) in an ascending order of the values l.sub.i,p and l.sub.j,p, respectively.

7. The encoding apparatus of claim 2, wherein the program further includes instructions to construct the matrix based on k rows of the matrix with the smallest values of l.sub.i,p.

8. The encoding apparatus of claim 1, wherein the program further includes instructions to: construct a first plurality of t rows of the matrix such that the last non-zero elements in the first plurality of t rows are located in distinct positions j, jj.sub.0 for some integer j.sub.0; construct elements of the first plurality of t rows located in columns having an index z<j using a pseudorandom number generator; and construct a second plurality of nkt rows of matrix V as distinct weight-one rows.

9. The encoding apparatus of claim 8, wherein the pseudorandom number generator is a linear feedback shift register.

10. A method, comprising: encoding data x of dimension k into a codeword c of length n using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2.sup.m.sup.1+ . . . +2.sup.m.sup.s, wherein m.sub.h, h=1, . . . , s, is an integer number, on the basis of the equation:
c=uA, wherein u.sub.i=x.sub.j.sub.i, 0j.sub.i<k1, if i.Math.F, wherein F is a set of nk frozen bit indices of the code C(n, k, d), and u.sub.i=.sub.s=0.sup.i1.sub..sub.i.sub.,su.sub.s, if iF wherein is a constraint matrix given by a solution of the equation:
.sup.T=0, wherein .sub.i is an index of a row of the matrix V, which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as: $A=\left(\begin{array}{cccc}{A}_{m_1}& 0& \mathrm{.Math.}& 0\\ 0& A_{m_2}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& A_{m_s}\end{array}\right),$ and wherein $A_{m_h}={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_h},$ and wherein Q.sup..Math.m denotes the m-times Kronecker product of a matrix Q with itself; and sending, after the codeword c is encoded, encoded codeword c over a transmission channel to a decoding apparatus for recovery of correct symbols of codeword c.

11. The method of claim 10, further comprising: constructing the code C(n, k, d) on the basis of a plurality of nested linear block codes C.sub.ij(2.sup.m.sup.i,K.sub.i,j,d.sub.ij),K.sub.i,j+1>K.sub.i,j, 0j<.sub.i, wherein .sub.i is a positive integer, wherein a generator matrix of C.sub.ij (2.sup.m.sup.i,K.sub.i,j,d.sub.ij) is given by the equation: ${\tilde{G}}^{\left(i,j\right)}=\left(\begin{array}{c}{G}^{\left(i,0\right)}\\ G^{\left(i,1\right)}\\ \mathrm{.Math.}\\ G^{\left(i,j\right)}\end{array}\right),$ wherein G.sup.(i,j) is a k.sub.i,j2.sup.m.sup.i matrix, K.sub.i,j=.sub.s=0.sup.jk.sub.i,s, wherein a precoding matrix of G.sup.(i,j) is defined by ${\tilde{W}}^{\left(i,j\right)}={{\tilde{G}}^{\left(i,j\right)}\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.i},$ wherein a precoding matrix of {tilde over (G)}.sup.(i,j) is defined by $W^{\left(i,j\right)}={G^{\left(i,j\right)}\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.i},$ wherein an index l.sub.i,p of a column, where a p-th row of the matrix {tilde over (W)}.sup.(i,.sup.i.sup.1) starts, is defined by the equation $l_{i,p}=\min \underset{{\tilde{W}}_{p,t}^{\left(i,{}_i-1\right)}=1}{0t<2^i}t,0p<2^{m_i};$ and construct the precoding matrix as a block matrix, wherein the blocks of the precoding matrix consist of selected rows of the matrices {tilde over (W)}.sup.(i,j).

12. The method of claim 11, wherein the plurality of nested linear block codes C.sub.ij(2.sup.m.sup.i,K.sub.i,j,d.sub.ij) are extended Bose-Chaudhuri-Hocquenghem (e-BCH) codes.

13. The method of claim 11, further comprising: constructing a precoding matrix of the code C(n, k, d) according to: $\widetilde{\mathrm{��}}=\left(\begin{array}{ccccc}{\tilde{W}}^{\left(1,r_1\right)}& 0& 0& \mathrm{.Math.}& 0\\ 0& {\tilde{W}}^{\left(2,r_2\right)}& 0& \mathrm{.Math.}& 0\\ 0& 0& {\tilde{W}}^{\left(3,r_3\right)}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& 0& \mathrm{.Math.}& {\tilde{W}}^{\left(s,r_s\right)}\\ W^{\left(1,r_1+1\right)}& {\hat{W}}^{\left(2,1\right)}& {\hat{W}}^{\left(3,1\right)}& \mathrm{.Math.}& {\hat{W}}^{\left(s,1\right)}\\ 0& W^{\left(2,r_2+1\right)}& {\hat{W}}^{\left(3,2\right)}& \mathrm{.Math.}& {\hat{W}}^{\left(s,2\right)}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\end{array}\right),$ wherein r.sub.i=max.sub.j:d.sub.ij.sub.d j is an index of a largest e-BCH code of length 2.sup.m.sup.i having a minimum distance of at least d, and wherein .sup.(i,j) is a matrix defined on the basis of the matrix {tilde over (W)}.

14. The method of claim 11, further comprising: constructing the matrix .sup.(i,j) using rows of the matrix {tilde over (W)}.sup.(i,.sup.j.sup.) having the smallest value of P.sub.m.sub.i.sub.,l.sub.i,p, wherein P an error probability in a bit subchannel W.sub.m.sup.(i)(y.sub.0.sup.2.sup.m.sup.1,u.sub.0.sup.i1|u.sub.i), and wherein y.sub.0.sup.2.sup.m.sup.1=y.sub.0 . . . y.sub.2.sub.m.sub.1 denotes 2.sup.m1 noisy symbols of the codeword c after a transmission over a communication channel.

15. The method of claim 10, further comprising: constructing a first plurality of t rows of the matrix such that the last non-zero elements in the first plurality of t rows are located in distinct positions j, jj.sub.0 for some integer j.sup.0; constructing elements of the first plurality oft rows located in columns having an index z<j using a pseudorandom number generator; and constructing a second plurality of nkt rows of matrix V as distinct weight-one rows.

16. A decoding apparatus a processor; and a non-transitory computer-readable storage medium storing a program for decoding a codeword c of length n, the program to be executed by the processor, the program including instructions to: receive, from an encoding apparatus, a signal that is transmitted over a transmission channel and that has the codeword c in an encoded form; and decode the codeword c using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2.sup.m.sup.1+ . . . +2.sup.m.sup.s, wherein m.sub.h, h=1, . . . s, is an integer number, wherein:
c=uA, wherein u.sub.i=x.sub.j.sub.i, 0j.sub.i<1, wherein x is data of dimension k, if i.Math.F, wherein F is a set of nk frozen bit indices of the code C(n, k, d) and u.sub.i=.sub.s=0.sup.i1.sub..sub.i.sub.,su.sub.s, if F, wherein is a constraint matrix given by a solution of the equation:
.sup.T=0, wherein .sub.i is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as: $A=\left(\begin{array}{cccc}{A}_{m_1}& 0& \mathrm{.Math.}& 0\\ 0& A_{m_2}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& A_{m_s}\end{array}\right),$ wherein $A_{m_h}={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_h},$ and wherein Q.sup..Math.m denotes the m-times Kronecker product of a matrix Q with itself.

17. The decoding apparatus of claim 16, wherein the instructions to decode the codeword include instructions to decode the codeword c by generalization of a successive cancellation algorithm.

18. The decoding apparatus of claim 17, wherein the program further includes instructions to compute u according to:
.sub.i=.sub.s=0.sup.i1.sub..sub.i.sub.,s.sub.s, if iF
and
.sub.i=arg max.sub.u.sub.iW.sub..sub.i.sup.(i mod 2.sup..sup.i)(y.sub.t.sub.i.sup.2.sup..sup.i+t.sup.i.sup.1,.sub.t.sub.i.sup.i1|u.sub.i), if i.Math.F wherein .sub.i is an index of a row of the matrix , which has a last non-zero element in column i, wherein y.sub.0.sup.n1=y.sub.0 . . . y.sub.n1 denotes n noisy symbols of the codeword c after a transmission over a communication channel to the decoding apparatus, .sub.i=log.sub.2(2.sup.log .sup.2.sup.ni), and t.sub.i=2.sup.log .sup.2.sup.n2.sup..sup.i.sup.+1.

19. The decoding apparatus of claim 18, wherein the program further includes instructions to compute .sub.i.sub.1 before .sub.i.sub.2, if .sub.i.sub.1=.sub.i.sub.2 and i.sub.1<i.sub.2, and to compute .sub.s: .sub..sub.i.sub.,s0, s<i, before .sub.i, if iF.

20. A method, comprising: receiving, from an encoding apparatus, a signal that is transmitted over a transmission channel and that has the codeword c of length n in encoded form; and decoding the codeword c using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2.sup.m.sup.1+ . . . +2.sup.m.sup.s, wherein m.sub.h, h=1, . . . ,s, is an integer number, wherein:
c=uA, wherein u.sub.i=x.sub.j.sub.i, 0j.sub.i<k1, wherein x is data of dimension k, if i.Math.F, wherein F is a set of nk frozen bit indices of the code C(n, k, d), and u.sub.i=.sub.s=0.sup.i1.sub..sub.i.sub.,su.sub.s, if iF, wherein is a constraint matrix given by a solution of the equation:
.sup.T=0, wherein .sub.i is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as follows: $A=\left(\begin{array}{cccc}{A}_{m_1}& 0& \mathrm{.Math.}& 0\\ 0& A_{m_2}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& A_{m_s}\end{array}\right),$ wherein $A_{m_h}={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_h},$ and wherein Q.sup..Math.m denotes the m-times Kronecker product of a matrix Q with itself.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Further embodiments of the application will be described with respect to the following figures, wherein:

(2) FIG. 1 shows a schematic diagram illustrating a communication system comprising an encoding apparatus according to an embodiment and a decoding apparatus according to an embodiment;

(3) FIG. 1a shows four exemplary generator matrices of extended BHC codes used to construct a code according to an embodiment;

(4) FIG. 1b shows three exemplary generator matrices of extended BHC codes used to construct a code according to an embodiment;

(5) FIG. 1c shows four exemplary precoding matrices of generator matrices of extended BHC codes used to construct a code according to an embodiment;

(6) FIG. 1d shows three exemplary precoding matrices of generator matrices of extended BHC codes used to construct a code according to an embodiment;

(7) FIG. 1e shows an exemplary precoding matrix of a parent code according to an embodiment;

(8) FIG. 1f shows an exemplary precoding matrix of a code according to an embodiment;

(9) FIG. 1g shows an exemplary constraint matrix of a code according to an embodiment;

(10) FIG. 2 shows a schematic diagram of a structure of an encoding apparatus for a code based on chained polar subcode according to an embodiment;

(11) FIG. 3 shows frame error rates (FER) of different codes as a function of a signal-to-noise ratio (E.sub.b/N.sub.0) in dB according to an embodiment;

(12) FIG. 4 shows frame error rates (FER) of different codes as a function of a signal-to-noise ratio (E.sub.b/N.sub.0) in dB according to an embodiment;

(13) FIG. 5 shows a schematic diagram of a method for encoding data x of dimension k into a codeword c of length n according to an embodiment; and

(14) FIG. 6 shows a schematic diagram of a method for decoding a codeword c of length n according to an embodiment.

(15) In the figures, identical reference signs will be used for identical or functionally equivalent features.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

(16) In the following description, reference is made to the accompanying drawings, which form part of the disclosure, and in which are shown, by way of illustration, specific aspects in which the present application may be placed. It will be appreciated that the application may be placed in other aspects and that structural or logical changes may be made without departing from the scope of the application. The following detailed description, therefore, is not to be taken in a limiting sense, as the scope of the application is defined by the appended claims.

(17) For instance, it will be appreciated that a disclosure in connection with a described method will generally also hold true for a corresponding device or system configured to perform the method and vice versa. For example, if a specific method step is described, a corresponding device may include a unit to perform the described method step, even if such unit is not explicitly described or illustrated in the figures.

(18) Moreover, in the following detailed description as well as in the claims, embodiments with functional blocks or processing units are described, which are connected with each other or exchange signals. It will be appreciated that the application also covers embodiments which include additional functional blocks or processing units that are arranged between the functional blocks or processing units of the embodiments described below.

(19) Finally, it is understood that the features of the various exemplary aspects described herein may be combined with each other, unless specifically noted otherwise.

(20) FIG. 1 shows a schematic diagram illustrating a communication system 100 comprising an encoding apparatus 102 and a decoding apparatus 104, which can communicate via a communication channel 110.

(21) The encoding apparatus 102 comprises a processor iota and is configured to encode data. Likewise, the decoding apparatus 104 comprises a processor 104a and is configured to decode data, in particular data encoded by the encoding apparatus 102. The encoding apparatus 102 and/or the decoding apparatus 104 can be implemented as part of a communication device, such as a mobile phone or a base station of a cellular communication network.

(22) In an embodiment, the processor iota is configured to encode data x of dimension k into a codeword c of length n using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2.sup.m.sup.1+ . . . +2.sup.m.sup.s, wherein m.sub.h>m.sub.h+1, h=1, . . . , s, is an integer number, on the basis of the equation:
c=uA,

(23) wherein u.sub.i=x.sub.j.sub.i, 0j.sub.i<k1, if i.Math.F, wherein F is a set of nk frozen bit indices of the code C(n, k, d), and u.sub.i=.sub.s=0.sup.i1.sub..sub.i.sub.,su.sub.s, if iF, wherein V is a constraint matrix. The constraint matrix V is given by a solution of the equation:
.sup.T=0,

(24) wherein .sub.i is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as follows:

(25) 0$A=\left(\begin{array}{cccc}{A}_{m_1}& 0& \mathrm{.Math.}& 0\\ 0& A_{m_2}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& A_{m_s}\end{array}\right),$

(26) wherein

(27) $A_{m_h}={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_h},$
and wherein Q.sup..Math.m denotes the m-times Kronecker product of a matrix Q with itself.

(28) In an embodiment, similarly to the processor iota, the processor 104a of the decoding apparatus 104 is configured to decode the codeword c using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2.sup.m.sup.1+ . . . +2.sup.m.sup.s, wherein m.sub.h>m.sub.h+1 h=1, . . . , s, is an integer number, wherein:
c=uA,

(29) wherein u.sub.i=x.sub.j, 0j<k1, wherein x is data of dimension k, if i.Math.F, wherein F is a set of nk frozen bit indices of the code C(n, k, d) and u.sub.i=.sub.s=0.sup.i1.sub..sub.i.sub.,su.sub.s, if iF, wherein is a constraint matrix given by a solution of the equation:
.sup.T=0,

(30) wherein .sub.i is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as follows:

(31) $A=\left(\begin{array}{cccc}{A}_{m_1}& 0& \mathrm{.Math.}& 0\\ 0& A_{m_2}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& A_{m_s}\end{array}\right),$

(32) wherein

(33) $A_{m_h}={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_h},$
and wherein Q.sup..Math.m denotes the m-times Kronecker product of a matrix Q with itself.

(34) The communication channel 110 can be a wired or a wireless communication channel.

(35) In an embodiment, the processor iota can be configured to generate the constraint matrix on the basis of the following steps.

(36) 1.sup.st step: construct generator matrices

(37) ${\tilde{G}}^{\left(i,j\right)}=\left(\begin{array}{c}{G}^{\left(i,0\right)}\\ G^{\left(i,1\right)}\\ \mathrm{.Math.}\\ G^{\left(i,j\right)}\end{array}\right)$
of nested extended primitive narrow-sense BCH codes C.sub.ij(2.sup.m.sup.i, K.sub.i,j, d.sub.ij), 0j<.sub.i, wherein G.sup.(i,j) is a k.sub.i,j2.sup.m.sup.i matrix, K.sub.i,j=.sub.s=0.sup.jk.sub.i,s, and define the corresponding precoding matrices of G.sup.(i,j) as:

(38) ${\tilde{W}}^{\left(i,j\right)}={{\tilde{G}}^{\left(i,j\right)}\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_i}\mathrm{and}{W}^{\left(i,j\right)}={G^{\left(i,j\right)}\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.i},$

(39) wherein an index of a column where the p.sup.th row of the matrix {tilde over (W)}.sup.(i,.sup.i.sup.1) starts is defined by:

(40) $l_{i,p}=\min \underset{{\tilde{W}}_{p,t}^{\left(i,{}_i-1\right)}=1}{0t<2^i}t,0p<2^{m_i}.$

(41) In an embodiment, it can be assumed that for any i all l.sub.i,p are distinct and, in general, the integer number .sub.i is equal to the number of irreducible polynomials of degree M, wherein M represents the number of divisors of m.sub.i.

(42) 2.sup.nd step: apply elementary row operations to {tilde over (W)}.sup.(i,j) in order to ensure that all rows start in distinct columns, while preserving the nested structure of the matrices {tilde over (W)}.sup.(i,j).

(43) 3.sup.rd step: select rows of matrices {tilde over (W)}.sup.(i,j):d.sub.i,jd, and put them into the i-th column of a precoding matrix , wherein the precoding matrix is a block matrix.

(44) 4.sup.th step: select rows of matrices {tilde over (W)}.sup.(i,j):d>d.sub.i,jd for some >0, put them into the i-th column of the precoding matrix . For every such a row, select a row of a matrix {tilde over (W)}.sup.(i,j),i>i,d.sub.i,j, which has not been selected in the previous step, and put it into the same row of matrix in column i. Summarizing, the constructed precoding matrix is given by:

(45) $\widetilde{\mathrm{��}}=\left(\begin{array}{ccccc}{\tilde{W}}^{\left(1,r_1\right)}& 0& 0& \mathrm{.Math.}& 0\\ 0& {\tilde{W}}^{\left(2,r_2\right)}& 0& \mathrm{.Math.}& 0\\ 0& 0& {\tilde{W}}^{\left(3,r_3\right)}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& 0& \mathrm{.Math.}& {\tilde{W}}^{\left(s,r_s\right)}\\ W^{\left(1,r_1+1\right)}& {\hat{W}}^{\left(2,1\right)}& {\hat{W}}^{\left(3,1\right)}& \mathrm{.Math.}& {\hat{W}}^{\left(s,1\right)}\\ 0& W^{\left(2,r_2+1\right)}& {\hat{W}}^{\left(3,2\right)}& \mathrm{.Math.}& {\hat{W}}^{\left(s,2\right)}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\end{array}\right),$

(46) wherein r.sub.i=max.sub.j:d.sub.ij.sub.dj is an index of a largest e-BCH code of length 2.sup.m.sup.i with minimum distance d and .sub.i=dd.sub.i,r.sub.i.sub.+1 is the minimum distance difference of the next largest e-BCH code. The matrices .sup.(i,j) consist of some rows of matrix {tilde over (W)}.sup.(i,.sup.j.sup.) and zero rows, wherein .sub.j=max.sub.s:d.sub.i,s.sub..sub.j s, so that for any s there is at most one block i with non-zero row .sub.s,_.sup.(i,j).

(47) 5.sup.th step: keep k rows of matrix which start in column l.sub.i,p of block i with the smallest where P.sub.m.sub.i.sub.,l.sub.i,p, is the error probability in a bit subchannel W.sub.m.sup.(i)(y.sub.0.sup.2.sup.m.sup.1,u.sub.0.sup.i1|u.sub.i), wherein y.sub.0.sup.2.sup.m.sup.1=y.sub.0 . . . y.sub.2.sub.m.sub.1 denotes 2.sup.m1 noisy symbols of the codeword c after a transmission over the communication channel 110. Let be the obtained matrix.

(48) 6.sup.th step: obtain :.sup.T=0, use Gaussian elimination to ensure that rows of end in distinct columns j.sub.i, 0i<nk and define the set of (dynamic) frozen bit indices as F={j.sub.i, 0i<nk}.

(49) In order to illustrate the above described steps to generate the constraint matrix V, the construction of an exemplary (24,11,6) code on the basis of chained polar subcodes is considered. In this case, the code has dimension n=24, which can also be written as 24=2.sup.4+2.sup.3, so that m.sub.0=4, m.sub.1=3. In FIGS. 1a and 1b, the nested generator matrices G.sup.(i,j), i=0, 1 and j=1, 2, 3, of the corresponding extended BCH codes C.sub.ij are shown, wherein d.sub.0,0=16, d.sub.0,1=8, d.sub.0,2=6, d.sub.0,3=4, d.sub.1,0=8, d.sub.1,1=4, d.sub.1,2=2. By multiplying the matrices G.sup.(i,j) shown in FIGS. 1a and 1b by the matrices

(50) $A_{m_i}={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_i},$
and by applying elementary row operations, the corresponding precoding matrices W.sup.(i,j) can be obtained, as shown in FIGS. 1c and 1d. Combining the precoding matrices W.sup.(i,j) with =2, the precoding matrix of the parent code can be obtained as shown in FIG. 1e. In the case of a binary erasure channel having erasure probability 0.5, the error probabilities in bit subchannels are for instance: 0.499, 0.496, 0.492, 0.386, 0.48, 0.32, 0.26, 0.5e1, 0.44, 0.23, 0.17, 0.18e1, 0.11, 0.38e2, 0.76e5; 0.498, 0.44, 0.40, 0.15, 0.34, 0.09, 0.06, 0.0019.

(51) Since the 6.sup.th row of the matrix starts in column 3, which corresponds to a subchannel with the highest error probability 0.386, it can be eliminated. Therefore, a precoding matrix for the (24,11,6) code based on chained polar subcodes can be obtained as shown in figure if. Finally, the corresponding constraint matrix can be obtained as shown in FIG. 1g.

(52) In another embodiment the processor 102a can be configured to construct the (nk)n matrix , according to the following steps:

(53) 1.sup.st step: set the rows of V to distinct vectors of weight 1, containing 1 in columns l.sub.i,p of block i with the highest P.sub.m.sub.i.sub.,l.sub.i,p; and

(54) 2.sup.nd step: put arbitrary binary values into columns j<l.sub.i,p of at most two blocks i, for each of the last rows of .

(55) In an embodiment, the binary values can be obtained by a pseudo-random number generator (PRNG), such as a linear feedback shift register. This has the advantage that the code can be specified in a compact way by providing just the parameters and seed value of the PRNG. Furthermore, the matrix constructed according to the above mentioned steps has the advantage of providing chained polar subcodes which have a high performance.

(56) Once the matrices and are available, in another embodiment, the processor 102a can further be configured to encode the data x of dimension k into the codeword c according to the following equation:

(57) $c=\mathrm{x��A},A=\left(\begin{array}{cccc}{A}_{m_1}& 0& \mathrm{.Math.}& 0\\ 0& A_{m_2}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& A_{m_s}\end{array}\right).$

(58) Furthermore, once the codeword c is encoded, it can be sent to the decoding apparatus 104 via the communication channel 110. However, after the transmission over the communication channel 110, the n symbols of the codeword c are affected by noise and they result in noisy symbols y.sub.0.sup.n1=y.sub.0 . . . y.sub.n1, therefore a method is needed in order to recover the correct symbols of the codeword c.

(59) In an embodiment, the processor 104a of the decoding apparatus 104 can be configured to recover the codeword c using a generalized successive cancellation algorithm and its list or sequential extensions on the basis of the following equations:
.sub.i=.sub.s=0.sup.i1.sub..sub.i.sub.,s.sub.s,iF and .sub.i=arg max.sub.u.sub.iW.sub..sub.i.sup.(i mod 2.sup..sup.i)(y.sub.t.sub.i.sup.2.sup..sup.i+t.sup.i.sup.1,.sub.t.sub.i.sup.i1|u.sub.i),i.Math.F

(60) wherein .sub.i=log.sub.2(2.sup..sup.2.sup.ni) and t.sub.i=2.sup.log.sup.2.sup.n2.sup..sup.i.sup.+1.

(61) This decoding method can also be extended to obtain list and sequential successive cancellation methods similar to the ones presented in the aforementioned works by Tal and Vardy and Miloslayskaya and Trifonov.

(62) In an embodiment the order to obtain the symbol 11, can be rearranged on the basis of the following rules: a. If .sub.i.sub.1=.sub.i.sub.2 and i.sub.1<i.sub.2, then .sub.i.sub.1 is calculated before .sub.i.sub.2; and b. If iF, then .sub.s:.sub..sub.i.sub.,s0, s<i, is calculated before .sub.i.

(63) Rearranging the detection order of symbols .sub.i has the advantage that it can lead to an improved performance of list and sequential successive cancellation algorithms.

(64) FIG. 2 shows a schematic diagram of a structure of an encoding apparatus 102 for a code based on chained polar subcode according to an embodiment. In this embodiment, the code has a length n=12=2.sup.3+2.sup.2 and it includes two polarizing transformations: A.sub.m.sub.1, m.sub.1=3, (polarizing transformation 1) of size 8 and A.sub.m.sub.2, m.sub.2=2, (polarizing transformation 2) of size 4. The data x of dimension 4 to be encoded is represented by the four symbols x.sub.0, x.sub.1, x.sub.2, x.sub.3, which are mapped onto symbols u.sub.3, u.sub.5, u.sub.7, u.sub.9. The set of frozen bit symbols is represented by u.sub.0, u.sub.1, u.sub.2, u.sub.4, u.sub.6, u.sub.8, u.sub.10, u.sub.11. In an embodiment, the processor iota of the encoding apparatus 102 can be configured to calculate symbols u.sub.6 and u.sub.10 as a function of some linear combinations of other input symbols of the corresponding polarizing transformations as shown in FIG. 2. Furthermore, the processor iota can be configured to calculate the input symbol u.sub.11 of the polarizing transformation 2 as a function of an input symbol of the polarizing transformation 1. Moreover, the structure of the freezing and cross-coding constraints can be realized in such a way that the obtained code has sufficiently high minimum distance and it can be decoded in an efficient way by a possible generalization or modification of the successive cancellation algorithm.

(65) FIG. 3 shows a frame error rate (FER) of different codes as a function of a signal-to-noise ratio (E.sub.b/N.sub.0) in dB according to an embodiment. As it is shown in FIG. 3, the performance of codes based on chained polar subcodes under a sequential decoding algorithm can significantly be improved compared to the performance of shortened polar subcodes, turbo codes and convolutional LTE tailbiting codes. In particular, codes based on chained polar subcodes can provide up to 0.3-0.7 dB power gain compared to shortened polar subcodes.

(66) FIG. 4 shows a frame error rate (FER) of different codes as a function of a signal-to-noise ratio (E.sub.b/N.sub.0) in dB according to an embodiment. Analogously to FIG. 3, in this case as well, the performance of codes based on chained polar subcodes is significantly improved compared to the performance of shortened polar subcodes and turbo codes.

(67) FIG. 5 shows a schematic diagram of a method 500 for encoding data x of dimension k into a codeword c of length n according to an embodiment. The method 500 comprises the step of encoding 502 the data x using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2.sup.m.sup.1+ . . . +2.sup.m.sup.s, wherein m.sub.h, h=1, . . . ,s, is an integer number, on the basis of the equation:
c=uA,

(68) wherein u.sub.i=x.sub.j.sub.i, 0j.sub.i<k1, if i.Math.F, wherein F is a set of nk frozen bit indices of the code C(n, k, d), and u.sub.i=.sub.s=0.sup.i1.sub..sub.i.sub.,su.sub.s, if iF, wherein V is a constraint matrix given by a solution of the equation:
.sup.T=0,

(69) wherein .sub.i is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as follows:

(70) 0$A=\left(\begin{array}{cccc}{A}_{m_1}& 0& \mathrm{.Math.}& 0\\ 0& A_{m_2}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& A_{m_s}\end{array}\right),$

(71) wherein

(72) $A_{m_h}={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_h},$
and wherein Q.sup..Math.m denotes the m-times Kronecker product of a matrix Q with itself.

(73) FIG. 6 shows a schematic diagram of a method 600 for decoding a codeword c of length n according to an embodiment. The method 600 comprises the step of decoding 602 the codeword c using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2.sup.m.sup.1+ . . . +2.sup.m.sup.s, wherein m.sub.h, h=1, . . . , s, is an integer number, wherein:
c=uA,

(74) wherein u.sub.i=x.sub.j.sub.i, 0j.sub.i<k1, wherein x is data of dimension k, if i.Math.F, wherein F is a set of n k frozen bit indices of the code C(n, k, d) and u.sub.i=.sub.s=0.sup.i1.sub..sub.i.sub.,su.sub.s, if iF, wherein is a constraint matrix given by a solution of the equation:
.sup.T=0,

(75) wherein .sub.i is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as follows:

(76) $A=\left(\begin{array}{cccc}{A}_{m_1}& 0& \mathrm{.Math.}& 0\\ 0& A_{m_2}& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& A_{m_s}\end{array}\right),$

(77) wherein

(78) $A_{m_h}={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m_h},$
and wherein Q.sup..Math.m denotes the m-times Kronecker product of a matrix Q with itself.

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

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

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

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