Apparatus and method for generating polar codes

Abstract

A method for generating a polar code c.sub.N of length N and dimension K, on the basis of a generator matrix G.sub.N of size NN, is provided. The method includes generating a distance spectrum vector d.sub.T.sub.p=(d.sub.T.sub.p(1), . . . , d.sub.T.sub.p(p)) of size p of the kernel T.sub.p, wherein d.sub.T.sub.p(h), h=1, . . . , p, corresponds to a maximum value among all possible minimum distances of all possible polar codes of size p and dimension h generated on the basis of the kernel T.sub.p. The method also includes generating a distance spectrum vector d.sub.G.sub.N of size N of the generator matrix G.sub.N on the basis of the distance spectrum vector d.sub.T.sub.p, determining the set of K information bit indices I on the basis of the distance spectrum vector d.sub.G.sub.N, and generating the polar code c.sub.N on the basis of the set of K information bit indices I.

Claims

1. An apparatus, comprising: a processor; and a computer-readable storage medium storing a program to be executed by the processor, the program including instructions for: generating a distance spectrum vector d.sub.T.sub.p=(d.sub.T.sub.p(1), . . . ,d.sub.T.sub.p(p)) of size p of a kernel T.sub.p, wherein the kernel T.sub.p has a size pp, with p<N, and wherein d.sub.T.sub.p(h), for each h of h=1, . . . , p, and corresponds to a maximum value among all possible minimum distances of all possible polar codes of size p and dimension h generated by selecting h rows of the kernel T.sub.p; generating a distance spectrum vector d.sub.G.sub.N of size N of a generator matrix G.sub.N on the basis of the distance spectrum vector d.sub.T.sub.p, wherein the generator matrix G.sub.N has a size NN, the generator matrix G.sub.N is based on the kernel T.sub.p; determining a set of K information bit indices I on the basis of the distance spectrum vector d.sub.G.sub.N; recording a polar code c.sub.N on the basis of the set of K information bit indices I, wherein the polar code c.sub.N has a length N and a dimension K, wherein the polar code c.sub.N is given by c.sub.N=u.sub.N.Math.G.sub.N, wherein u.sub.N=(u.sub.0, . . . , u.sub.N-1) is a vector of size N,u.sub.i, i=0, . . . N1, corresponding to an information bit if iI, I being the set of K information bit indices, and u.sub.i=0, if iF, F being a set of NK frozen bit indices; encoding first data using the recorded polar code c.sub.N; and transmitting the encoded first data to a second apparatus.

2. The apparatus of claim 1, wherein p=3, and the kernel T.sub.3 is given by: $T_{3} = (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}) .$

3. The apparatus of claim 2, wherein the generator matrix G.sub.N is given by:
G.sub.N=G.sub.n.Math.T.sub.3; and wherein G.sub.n represents a first additional generator matrix and .Math. represents the Kronecker product operator.

4. The apparatus of claim 3, wherein the program further includes instructions for: generating the distance spectrum vector d.sub.G.sub.N of the generator matrix G.sub.N on the basis of the following:
d.sub.G.sub.N=d.sub.G.sub.n.Math.d.sub.T.sub.3, wherein d.sub.G.sub.n is the distance spectrum vector of the first additional generator matrix G.sub.n and d.sub.T.sub.3=(3,2,1) is the distance spectrum vector of the kernel T.sub.3.

5. The apparatus of claim 1, wherein p=5 and the kernel T.sub.5 is given by: $T_{5} = (\begin{matrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{matrix}) .$

6. The apparatus of claim 5, wherein the generator matrix G.sub.N is given by:
G.sub.N=G.sub.m.Math.T.sub.5; and wherein G.sub.m represents a second additional generator matrix and .Math. represents the Kronecker product operator.

7. The apparatus of claim 6, wherein the program further includes instructions for: generating the distance spectrum vector d.sub.G.sub.N of the generator matrix G.sub.N on the basis of the following:
d.sub.G.sub.N=d.sub.G.sub.m.Math.d.sub.T.sub.5; and wherein d.sub.G.sub.m is the distance spectrum vector of the second additional generator matrix G.sub.m and d.sub.T.sub.5=(5,3,2,1,1) is the distance spectrum vector of the kernel T.sub.5.

8. The apparatus of claim 1, wherein the first row of the kernel T.sub.p has a maximum Hamming weight among all rows of the kernel T.sub.p.

9. The apparatus of claim 8, wherein the generator matrix G.sub.N is:
G.sub.N=G.sub.q.Math.G.sub.p, wherein G.sub.q is a third generator matrix of a code of size q and G.sub.p is a fourth generator matrix of a code of size p, and wherein the program further includes instructions for: generating a vector r.sub.G.sub.p=(d.sub.G.sub.p(1),d.sub.G.sub.p(p1),d.sub.G.sub.p(p2) . . . , d.sub.G.sub.p(2),d.sub.G.sub.p(2)) of size p; generating an auxiliary vector:
rG.sub.p=(d.sub.G.sub.p(p),d.sub.G.sub.p(p1),d.sub.G.sub.p(p2) . . . ,d.sub.G.sub.p(2),d.sub.G.sub.p(2)) of size p; generating a vector r.sub.G.sub.N=d.sub.G.sub.q.sup.rev.Math.r.sub.G.sub.p of size q.Math.p, wherein the vector d.sub.G.sub.q.sup.rev is the reverse of a distance spectrum vector d.sub.G.sub.q, d.sub.G.sub.q being the distance spectrum vector of the third generator matrix G.sub.q; generating a vector r.sub.G.sub.N=d.sub.G.sub.q.sup.rev.Math.r.sub.G.sub.p; determining, for i=1, . . . , K, a position l of the last largest entry of the vector r.sub.G.sub.N; adding l to the set of K information bit indices I; setting r.sub.G.sub.N(l) equal to zero; removing, when l=0 mod p, from the set of frozen bit indices F, an index t equal to lp+1; substituting the index t by l1; setting r.sub.G.sub.p(l1)=0; and setting r.sub.G.sub.p(lp+1)=r.sub.G.sub.p(lp+1).

10. A method, comprising: generating, by a device, a distance spectrum vector d.sub.T.sub.p=(d.sub.T.sub.p(1), . . . ,d.sub.T.sub.p(p)) of size p of a kernel T.sub.p, wherein the kernel T.sub.p has a size pp, with p<N, and wherein d.sub.T.sub.p(h), for each h of h=1, . . . ,p, and corresponds to a maximum value among all possible minimum distances of all possible codes of size p and dimension h generated by selecting h rows of the kernel T.sub.p; generating, by the device, a distance spectrum vector d.sub.G.sub.N of size N of a generator matrix G.sub.N on the basis of the distance spectrum vector d.sub.T.sub.p, wherein the generator matrix G.sub.N has a size NN, the generator matrix G.sub.N is based on the kernel T.sub.p; determining, by the device, a set of K information bit indices I on the basis of the distance spectrum vector d.sub.G.sub.N; recording, by the device, a polar code c.sub.N on the basis of the set of K information bit indices I, wherein to polar code c.sub.N has a length N and a dimension K, wherein the polar code c.sub.N is given by c.sub.N=u.sub.N.Math.G.sub.N, wherein u.sub.N=(u.sub.0, . . . , u.sub.N-1) is a vector of size N, u.sub.i, i=0, . . . N1, corresponding to an information bit if iI, I being the set of K information bit indices, and u.sub.i=0, if iF, F being a set of NK frozen bit indices; encoding, by the device, first data using the recorded polar code c.sub.N; and transmitting, by the device, the encoded first data to a second apparatus.

11. The method of claim 10, wherein p=3, and the kernel T.sub.3 is given by: $T_{3} = (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}) .$

12. The method of claim 11, wherein the generator matrix G.sub.N is given by:
G.sub.N=G.sub.n.Math.T.sub.3; and wherein G.sub.n represents a first additional generator matrix and .Math. represents the Kronecker product operator.

13. The method of claim 12, further comprising: generating the distance spectrum vector d.sub.G.sub.N of the generator matrix G.sub.N on the basis of the following:
d.sub.G.sub.N=d.sub.G.sub.n.Math.d.sub.T.sub.3, wherein d.sub.G.sub.n is the distance spectrum vector of the first additional generator matrix G.sub.n and d.sub.T.sub.3=(3,2,1) is the distance spectrum vector of the kernel T.sub.3.

14. The method of claim 10, wherein p=5 and the kernel T.sub.5 is given by: $T_{5} = (\begin{matrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{matrix}) .$

15. The method of claim 14, wherein the generator matrix G.sub.N is given by:
G.sub.N=G.sub.m.Math.T.sub.5; and wherein G.sub.m represents a second additional generator matrix and .Math. represents the Kronecker product operator.

16. The method of claim 15, further comprising: generating the distance spectrum vector d.sub.G.sub.N of the generator matrix G.sub.N on the basis of the following:
d.sub.G.sub.N=d.sub.G.sub.m.Math.d.sub.T.sub.5; and wherein d.sub.G.sub.m is the distance spectrum vector of the second additional generator matrix G.sub.m and d.sub.T.sub.5=(5,3,2,1,1) is the distance spectrum vector of the kernel T.sub.5.

17. The method of claim 10, wherein the first row of the kernel T.sub.p has a maximum Hamming weight among all rows of the kernel T.sub.p.

18. The method of claim 17, wherein the generator matrix G.sub.N is:
G.sub.N=G.sub.q.Math.G.sub.p, wherein G.sub.q is a third generator matrix of a code of size q and G.sub.p is a fourth generator matrix of a code of size p, and wherein the method comprises: generating a vector r.sub.G.sub.p=(d.sub.G.sub.p(1), d.sub.G.sub.p(p1),d.sub.G.sub.p(p2) . . . , d.sub.G.sub.p(2),d.sub.G.sub.p(2)) of size p; generating an auxiliary vector: r.sub.G.sub.p=(d.sub.G.sub.p(p),d.sub.G.sub.p(p1),d.sub.G.sub.p(p2) . . . , d.sub.G.sub.p(2),d.sub.G.sub.p(2)) of size p; generating a vector r.sub.G.sub.N=.sub.G.sub.q.sup.rev.Math.r.sub.G.sub.p of size q.Math.p, wherein the vector d.sub.G.sub.q.sup.rev is the reverse of a distance spectrum vector d.sub.G.sub.q, d.sub.G.sub.q being the distance spectrum vector of the third generator matrix G.sub.q; generating a vector rG.sub.N=d.sub.G.sub.q.sup.rev.Math.r.sub.G.sub.p; determining, for i=1, . . . , K, a position l of the last largest entry of the vector r.sub.G.sub.N; adding l to the set of K information bit indices l; setting r.sub.G.sub.N(l) equal to zero; removing, when l=0 mod p, from the set of frozen bit indices F, an index t equal to lp+1; substituting the index t by l1; setting r.sub.G.sub.p(l1)=0; and setting r.sub.G.sub.p(lp+1)=r.sub.G.sub.p(lp+1).

19. A method, comprising: generating, by a device, a distance spectrum vector d.sub.T.sub.p=(d.sub.T.sub.p(1), . . . ,d.sub.T.sub.p(p)) of size p of a kernel T.sub.p, wherein the kernel T.sub.p has a size pp, with p<N, and wherein d.sub.T.sub.p(h), for each h of h=1, . . . ,p, and corresponds to a maximum value among all possible minimum distances of all possible codes of size p and dimension h generated spanned by h rows of the kernel T.sub.p; generating, by the device, a distance spectrum vector d.sub.G.sub.N of size N of a generator matrix G.sub.N on the basis of the distance spectrum vector d.sub.T.sub.p, wherein the generator matrix G.sub.N has a size NN, the generator matrix G.sub.N is based on the kernel T.sub.p; determining, by the device, a set of K information bit indices I on the basis of the distance spectrum vector d.sub.G.sub.N; recording, by the device, a polar code c.sub.N on the basis of the set of K information bit indices I, wherein to polar code c.sub.N has a length N and a dimension K, wherein the polar code c.sub.N is given by c.sub.N=u.sub.N.Math.G.sub.N, wherein u.sub.N=(u.sub.0, . . . ,u.sub.N-1) is a vector of size N, u.sub.i, i=0, . . . N1, corresponding to an information bit if iI, I being the set of K information bit indices, and u.sub.i=0, if iF, F being a set of NK frozen bit indices; encoding, by the device, first data using the recorded polar code c.sub.N; and transmitting, by the device, the encoded first data to a second apparatus.

20. The method of claim 19, wherein p=3, and the kernel T.sub.3 is given by: $T_{3} = (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}) .$

Description

BRIEF DESCRIPTION OF THE DRAWINGS

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

(2) FIG. 1 shows a schematic diagram illustrating a conventional polar code of length 8;

(3) FIG. 2 shows a schematic diagram of a communication system comprising a channel encoder comprising an apparatus for generating a polar code according to an embodiment and a channel decoder encoder comprising an apparatus for generating a polar code according to an embodiment;

(4) FIG. 3 shows a schematic diagram illustrating a polar code of length 6 according to an embodiment;

(5) FIG. 4 shows a graph illustrating the performance of a polar code according to an embodiment;

(6) FIG. 5 shows a graph illustrating the performance of a polar code according to an embodiment;

(7) FIG. 6 shows a graph illustrating the performance of a polar code according to an embodiment; and

(8) FIG. 7 shows a schematic diagram of a method for generating a polar code according to an embodiment.

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

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

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

(11) For instance, it is understood that a disclosure in connection with a described method may also hold true for a corresponding device or system configured to perform the method and vice versa. For example, if a specific method step is described, a corresponding device may include a unit to perform the described method step, even if such unit is not explicitly described or illustrated in the figures. Further, it is understood that the features of the various exemplary aspects described herein may be combined with each other, unless specifically noted otherwise.

(12) FIG. 2 shows a schematic diagram of a communication system 100 comprising a channel encoder 110 comprising an apparatus 110a for generating a polar code according to an embodiment. In this embodiment, the channel encoder 110 is in communication with a channel decoder 130 via a communication channel 120. The channel encoder 110 can be configured to send an encoded polar code or codeword c.sub.N to the channel decoder 130. Moreover, the channel decoder 130 can comprise an apparatus 130a for decoding the polar code c.sub.N by means of a processor 130a-1. In an embodiment, the apparatus 130a of the channel decoder 130 can be identical to the apparatus 110a of the channel encoder 110.

(13) The apparatus 110a can generate the polar code c.sub.N of length N and dimension K, on the basis of a generator matrix G.sub.N of size NN, wherein the generator matrix G.sub.N is based on a kernel T.sub.p of size pp, with pN, wherein the polar code c.sub.N is given by c.sub.N=u.sub.N.Math.G.sub.N, wherein u.sub.N=(u.sub.0, . . . , u.sub.N-1) is a vector of size N, u.sub.i, i=0, . . . N1, corresponding to an information bit if iI, I being a set of K information bit indices, and u.sub.i=0, if iF, F being a set of NK frozen bit indices. The apparatus 110a comprises a processor 110a-1, wherein the processor 110a-1 is configured to perform the following steps: (i) generate a distance spectrum vector d.sub.T.sub.p=(d.sub.T.sub.p(1), . . . , d.sub.T.sub.p(p)) of size p of the kernel T.sub.p, wherein d.sub.T.sub.p(h), h=1, . . . , p, corresponds to a maximum value among all possible minimum distances of all possible polar codes of size p and dimension h generated on the basis of the kernel T.sub.p, (ii) generate a distance spectrum vector d.sub.G.sub.N of size N of the generator matrix G.sub.N on the basis of the distance spectrum vector d.sub.T.sub.p, (iii) determine the set of K information bit indices I on the basis of the distance spectrum vector d.sub.G.sub.N, and (iv) generate the polar code c.sub.N on the basis of the set of K information bit indices I.

(14) Thus, as will be appreciate, in an embodiment of the invention, the generation of the polar code c.sub.N can be divided into two main steps: firstly, the generator matrix G.sub.N having good distance properties is constructed, and then the set of K information bit indices of the polar code or of the multi-kernel polar code is generated on the basis of the distance properties of the generator matrix G.sub.N, as will be described in more detail in the following.

(15) In embodiment of the invention, for codes having short lengths, the kernel T.sub.p can be constructed in such a way that the code distance is taken into account. For a given kernel T.sub.p, the minimum distance of a code based on T.sub.p is closely related to the minimum Hamming weight of vectors in the space spanned by the rows selected to generate the set of K information bit indices I. In multi-kernel polar codes, the number of rows of G.sub.N to be selected depends on the number of information bits, namely on K. Traditionally (see e.g., the aforementioned work by Arikan), the rows of G.sub.N are selected according to a transmission reliability order, namely the K information bits are put in the K most reliable positions of the input vector u.sub.N, while the unreliable positions (frozen bits) are fixed to the bit value o. As a result, codes of same length but different dimension are nested, i.e., the set of information bit indices of the code of a smaller rate is a subset of the set of information bit indices of the code of a larger rate, differently from embodiments of the present invention, where different subsets of rows for different information set sizes are selected. In this way, the information sets of codes of different dimension may not be nested.

(16) In embodiments of the invention, for p=3, the kernel T.sub.3 of size 33 is given by:

(17) $T_{3} = (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}) .$

(18) This kernel shows polarization effects similar to the one shown by the conventional kernel T.sub.2, and shows optimal properties in terms of the distance profile.

(19) In embodiments of the invention, p=5 and the kernel T.sub.5 is given by following equation:

(20) $T_{5} = (\begin{matrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{matrix}) .$

(21) In order to better elucidate some advantages of the generation of polar codes according to embodiments of the present invention compared to prior art solutions, the distance spectrum vector d.sub.T.sub.3 of the kernel T.sub.3 according to embodiments of the invention is calculated in the following.

(22) Since the kernel T.sub.3 has a size of 33, only codes of size 3 having a dimension K=1, 2 or 3 can be generated: c.sub.3=u.sub.3.Math.T.sub.3.

(23) If K=1, one row i of the kernel T.sub.3 can be selected, or equivalently the information bit can be put in the i-th component of the input vector u.sub.3. In particular, in order to maximize the minimum distance of the polar code c.sub.3, the first row (1 1 1) is selected, giving a minimum distance 3. Any other row selection would result in a smaller minimum distance, namely 2. In fact, the only possible non-zero input sequences for u.sub.3 are {1 0 0}, {0 1 0}, and {0 0 1}, for the first, second and third bits being chosen as information bits, respectively. This results in the codes or codewords c.sub.3: {111}, {101}, {011}, which have minimum distances 3, 2, and 2, respectively. Therefore, by choosing the first row, the codeword having maximum value, i.e. 3, among all possible values of the minimum distances is obtained. In particular, in case K=1, the obtained set of codewords corresponds to the rows of the generator matrix, which in this case is T.sub.3.

(24) If K=2, the possible input vectors are given by: u(2,3)={001,010,011}, if the two information bits are put into the last two rows of the kernel T.sub.3 (or equivalently correspond to the second and third elements of the input vector u.sub.3); u(1,3)={101,001,100}, if the two information bits are put into the first and third row of T.sub.3, respectively, and, analogously, u(1,2)={100,010,110}. The corresponding polar codes or codewords are given by: c(2,3)={011,101,110} (having minimum distance 2), c(1,3)={100,011,111} (having minimum distance 1), and c(1,2)={111,101,010} (having minimum distance 1), respectively. Therefore, in order to maximize the minimum distance among all possible minimum distances among all possible codewords, the last two rows

(25) $(\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix})$
of T.sub.3 can be selected to place the two information bits, generating a code of minimum distance equal to 2.

(26) If K=3, then all the rows of T.sub.3 have to be selected to put the 3 information bits. Namely, all non-zero input vectors are given by: u.sub.3={001,010,100,011,101,110,111} which results in a minimum distance 1 (since e.g. c(110)=010 has weight 1). Therefore, the distance spectrum vector d.sub.3 in this embodiment in given by: d.sub.3=(3,2,1).

(27) The classical construction of the distance spectrum vector on the basis of the reliability of the transmission selects the last row for dimension 1, the last two rows for dimension 2, and all rows for dimension 3. This results in the classical distance spectrum vector d.sub.3=(2,2,1).

(28) By comparing the distance spectrum vector used in embodiments of the invention and the classical distance spectrum vector, it can be seen that the construction of the polar code according to embodiments of the invention achieves a larger distance for dimension 1 (K=1) than the conventional construction based on reliabilities of the transmission.

(29) In embodiments of the invention, the generator matrix G.sub.N is given by the Kronecker product of various kernels, e.g. T.sub.2 and T.sub.3. In this case, the generated code c.sub.N is a multi-kernel polar code and shows polarization properties. It can be proved that the distance spectrum vector of the Kronecker product of two or more kernels is given by the Kronecker product of the distance spectrum vectors of the kernels, sorted in descending order. This property can be used to easily calculate the distance spectrum vector of a multi-kernel code designed according to embodiments of the invention.

(30) In order to better elucidate the construction of multi-kernel polar codes and of their distance spectrum vectors, in FIG. 3 a schematic construction of a Tanner graph of a multi-kernel polar code of length 6 according to embodiments of the invention is shown, wherein P denotes an edge permutation and P.sup.1 its inverse, and wherein the generator matrix G.sub.6 is given by:

(31) $G_{6} = T_{2} .Math. T_{3} = (\begin{matrix} T_{3} & 0 \\ T_{3} & T_{3} \end{matrix}) = (\begin{matrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \end{matrix}) .$
In this embodiment, a code c.sub.6 of length 6 is obtained as c.sub.6=u.sub.6.Math.G.sub.6, wherein u.sub.6 is an input vector of length 6 comprising K information bits and NK frozen bits.

(32) As mentioned above, in order to calculate the distance spectrum vector of G.sub.6, the Kronecker product of the distance spectrum vectors of T.sub.2 and T.sub.3 can be calculated according to the following formula:
d.sub.6=d.sub.2.Math.d.sub.3=(2,1).Math.(3,2,1)=(6,4,2,3,2,1),
wherein d.sub.2=(2,1) is the distance spectrum of the kernel T.sub.2. Sorting the result in descending order, the distance spectrum vector of G.sub.6 can be obtained for the minimum distance construction, namely: (6,4,3,2,2,1). This means that sets of information bit indices can be selected in order to obtain a code of dimension K=1 with minimum distance 6, of dimension K=2 with minimum distance 4, etc. On the other hand, the distance spectrum vector according to of the classical reliability construction is given by: (4,4,2,2,2,1). In this case as well, the construction of the polar code according to embodiments of the invention shows better distance properties compared to prior art constructions.

(33) In embodiments of the invention, the distance spectrum vector d.sub.G.sub.N of the generator matrix G.sub.N determines which minimum distance is achievable for a given dimension K. Once the distance spectrum vector d.sub.G.sub.N is generated, the remaining task to generate the polar code c.sub.N is to determine the set of K information bit indices I in order to achieve this minimum distance. In embodiments of the invention, the following algorithm (herein also referred to as row selection algorithm) can be used to determine the set of K information bit indices I, such that the polar code has the minimum distance as defined in the distance spectrum vector.

(34) In embodiments of the invention, the kernel T.sub.p with distance spectrum d.sub.T.sub.p=(d.sub.T.sub.p(1), . . . , d.sub.T.sub.p(p)), wherein d.sub.T.sub.p(i) represents the minimum distance of the polar code of dimension i, has the following structure: the first row is the row with the maximum Hamming weight, while the other rows, when selected starting from the last row to the second row, provide the desired distance. For small kernel sizes, this is not a strong limitation, since kernels with good spectra can be designed respecting this property. As an example, the T.sub.3 kernel presented previously has this property. In an embodiment, the following algorithm is used to generate the set of K information bit indices I.

(35) As first, the distance spectrum of the kernel is used to create a vector r.sub.T.sub.p, defined as r.sub.T.sub.p=(d.sub.T.sub.p(1), d.sub.T.sub.p(p1), d.sub.T.sub.p(p2) . . . , d.sub.T.sub.p(2), d.sub.T.sub.p(2)), along with an auxiliary vector r.sub.T.sub.p, defined as r.sub.T.sub.p=(d.sub.T.sub.p(p), d.sub.T.sub.p(p1), d.sub.T.sub.p(p2) . . . , d.sub.T.sub.p(2), d.sub.T.sub.p(2)). The difference between r.sub.T.sub.p and its auxiliary vector r.sub.T.sub.p is given by the first element. If the generator matrix G.sub.N can be written as G.sub.N=G.sub.q.Math.G.sub.p, i.e., with G.sub.p at the rightmost position of the Kronecker product, then the algorithm comprises the steps explained in the following.

(36) First, the vector r.sub.G.sub.N=d.sub.G.sub.q.sup.rev.Math.r.sub.G.sub.p and the vector r.sub.G.sub.N=d.sub.G.sub.q.sup.rev.Math.r.sub.G.sub.p are calculated, wherein d.sub.G.sub.q.sup.rev is the reverse of d.sub.G.sub.q. Due to the fact that for a code of dimension K, K row indices are required for the information set, the algorithm adds sequentially one row index per step to the information set. At each step, the position l of the last largest entry in r.sub.G.sub.N is found, and l is added to the set of information bit indices, while r.sub.G.sub.N(l) is set to zero. However, if l=0 mod p, then by construction r.sub.G.sub.N(lp+1) is in the set of frozen bit indices, since in r.sub.G.sub.p(1) is larger than the other elements of r.sub.G.sub.p, while r.sub.G.sub.N(l1) is not in the set of K information bit indices I, since r.sub.G.sub.p(p)=r.sub.G.sub.p(p1). Otherwise, lp+1 is removed by the set of frozen bit indices and substituted by l1, while the algorithm sets r.sub.G.sub.p (l1)=0 and r.sub.G.sub.p(lp+1)=r.sub.G.sub.p(lp+1). The algorithm stops when the set of information bit indices I includes K elements. Afterwards, the remaining NK elements are stored in the set of frozen bit indices F.

(37) This algorithm finds an optimal solution if only one kernel of size larger than 2 is used in the multi-kernel construction. It may also be applied in the case of multiple kernels of size larger than 2, leading to good results, as demonstrated by simulations illustrated in FIGS. 4, 5, and 6. Generalizations of the proposed algorithm are also possible.

(38) In order to better elucidate the steps of the row selection algorithm according to embodiments of the invention, the set of information bit indices I obtained for the exemplary generator matrix G.sub.6 described above is shown in table 1, wherein

(39) $G_{6} = (\begin{matrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \end{matrix}), r_{6} = (\begin{matrix} 3 \\ 2 \\ 2 \\ 6 \\ 4 \\ 4 \end{matrix}) and r_{6}^{} = (\begin{matrix} 1 \\ 2 \\ 2 \\ 2 \\ 4 \\ 4 \end{matrix}),$

(40) and wherein the differences between the vector r.sub.6 and the vector r.sub.6 are indicated in boldface. In particular, in table 1, the set of information bit indices I calculated by means of the row selection algorithm following the distance criterion according to embodiments of the invention and the set of information bit indices obtained by using the conventional criterion based on transmission reliability are shown for different dimensions K. In table 1, the differences between the two sets of information bit indices are indicated in boldface.

(41) TABLE-US-00001 TABLE 1 Distance properties of multi-kernel polar codes according to embodiments of the invention. Dimension K 1 2 3 design by Information Set [u.sub.5] [u.sub.4, u.sub.5] [u.sub.2, u.sub.4, u.sub.5] reliability Minimum distance 4 4 2 design by Information Set [u.sub.3] [u.sub.4, u.sub.5] [u.sub.0, u.sub.4, u.sub.5] distance Minimum distance 6 4 3

(42) The bit positions or indices of u.sub.6 ordered according a decreasing reliability are [5,4,2,3,1,0]. For example, if the coding rate is fixed to R=, which means that there are K=3 information bits (R=K/N), then the 3 information bits are put in the 3 most reliable bit positions, corresponding to the bits [u.sub.5, u.sub.4, u.sub.2], while the 3 less reliable bits are fixed to o, i.e., they are frozen bits. Therefore, according to the classical construction of polar codes, the set of indices {5,4,2} of the input vector u.sub.6 defines the set of information bit indices I, while the remaining indices, namely the set of indices {3,1,0}, form the set of frozen bit indices F.

(43) As it can be taken from table 1, the row selection algorithm according to embodiments of the invention, finds the set of information bit indices leading to the minimum distance as determined by the distance spectrum, and the code construction according to embodiments of the invention leads to a larger minimum distance than the code construction according to the criterion based on transmission reliability.

(44) For example, let us assume that a polar code c.sub.6 of dimension N=6 is generated by encoding an information bit (K=1) by means of the generator matrix G.sub.6 according to the formula:
c.sub.6=u.sub.6.Math.G.sub.6,
wherein u=(u.sub.0,u.sub.1,u.sub.2,u.sub.3,u.sub.4,u.sub.5) comprises the information bit and NK=5 frozen bits. According to the row selection algorithm implemented in embodiments of the invention, the fourth element of the vector u.sub.6 should correspond to the information bit, because the maximum value of the minimum distance (in this case 6) among all possible values of the minimum distance, a codeword can have, corresponds to the fourth element of the vector r.sub.6.

(45) Once the input vector u.sub.6 is encoded generating the polar code c.sub.6, then the channel encoder 110 can send the polar code c.sub.6 to the channel decoder 130 over the communication channel 120. The channel decoder 130 can be a successive cancellation (SC) decoder, configured to decode the polar code c.sub.6.

(46) In the SC decoder, input bits (on the left side of FIG. 3) are decoded successively from top to bottom by propagating the log-likelihood ratio (LLR) values from right to left and hard-decisions from left to right (e.g., see the work by Arikan). The LLRs L.sub.0.sup.(0), . . . , L.sub.0.sup.(5) appearing at the right side correspond to the channel observations. In particular, the code of length N=6 has s=2 stages. LLRs and hard-decisions can be computed according to update functions (e.g., see the work by Arikan). As an alternative to SC decoding, SC list decoding (see List decoding of polar codes, by Tal et al., in IEEE ISIT, July 2011) or similar methods may be applied at the channel decoder 130.

(47) Embodiments of the invention realize different advantages, such as the generation of multi-kernel polar codes based on a minimum distance criterion, and on the kernel T.sub.3. In order to lower the computational complexity of the construction of polar codes, a simple greedy algorithm is given in order to generate the set of information bit indices (and hence the set of frozen bit indices) of multi-kernel polar codes. In particular, the complexity of the algorithm according to embodiments of the invention is much lower than the complexity of state-of-the-art algorithms based on density evolution or similar methods. Therefore, embodiments of the invention lead to a lower encoding and decoding latency. Moreover, the encoding or decoding algorithm according to embodiments of the invention is more efficient compared to prior art algorithms (e.g., see aforementioned the work by Arikan), for which a mother code has to be punctured or shortened in order to get the same block length, and decoding has to be performed on a longer mother code.

(48) FIG. 4 shows a graph illustrating the performance of a polar code according to an embodiment. In this embodiment, the block error rate (BLER) of a polar code is shown as a function of the signal to noise ration E.sub.b/N.sub.0 in dB. In this embodiment, a multi-kernel polar code of size N=192 and dimension K=96 is decoded using the SC-list decoding method (see the aforementioned work of Tal et al.) with list size L=8 for a transmission with binary phase shift keying (BPSK) over an additive white Gaussian noise (AWGN) channel. In this embodiment, the generator matrix is given by G.sub.192=T.sub.2.sup..Math.6.Math.T.sub.3, i.e., there is only one T.sub.3 kernel at the rightmost of the Kronecker product, and the row selection algorithm is optimal. The performance (BLER) of the multi-kernel polar code according to embodiments of the invention is depicted as MK-dist and is compared to the performance of the multi-kernel polar codes generated on the basis of the conventional transmission reliability method, depicted as MK-rel. In particular, the case MK-dist refers to multi-kernel polar codes generated by using the row selection algorithm according to embodiments of the invention. Moreover, in FIG. 4, the performances of a polar code generated by means of a puncturing method and of a polar code generated by means of a shortening method are also depicted as reference cases. In particular, the shortened polar code is depicted as polar-short and corresponds to the one proposed in A Novel Puncturing Scheme for Polar Codes, Wang et. al., IEEE Comm. Lett., December 2014, while the punctured polar code, depicted as polar-punct, is the QUP construction proposed in Beyond Turbo Codes: Rate-Compatible Punctured Polar Codes, C. Kai et. al, IEEE ICC, June 2013.

(49) As it can be seen in FIG. 4, the multi-kernel polar code according to embodiments of the invention has a better performance, namely a lower BLER at a certain E.sub.b/N.sub.0, than the other polar codes.

(50) FIG. 5 shows a graph illustrating the performance of a polar code according to an embodiment. In this embodiment, analogously to FIG. 4, the block error rate (BLER) of a polar code is shown as a function of the signal to noise ration E.sub.b/N.sub.0 in dB. In this embodiment, a multi-kernel polar code of size N=144 and dimension K=72 is decoded using the SC-list decoding method with list size L=8. In this embodiment, the generator matrix is given by G.sub.144=T.sub.2.sup..Math.4 .Math.T.sub.3.sup..Math.2, i.e., there are two T.sub.3 kernels at the rightmost of the Kronecker product. In this embodiment, the row selection algorithm used to generate the multi-kernel polar code is not as optimal as the one used to generate the polar code described with reference to FIG. 4, in which only one T.sub.3 kernel is at the rightmost of the Kronecker product. The performance of the multi-kernel polar code (BLER) generated according to embodiments of the invention is compared to the performance of polar code generated using other methods as already described in the context of FIG. 4. In this case as well, the multi-kernel polar code according to embodiments of this invention (MK-dist) outperforms the other polar codes.

(51) FIG. 6 shows a graph illustrating the performance of a polar code according to an embodiment. In this embodiment, analogously to FIGS. 4 and 5, the block error rate (BLER) of a polar code is shown as a function of the signal to noise ration E.sub.b/N.sub.0 in dB. In this embodiment, a multi-kernel polar code of size N=40, dimension K=10 and rate

(52) $R = \frac{K}{N} = 0.4$
is decoded using the SC-list decoding method with list size L=8. In this embodiment, the generator matrix is given by G.sub.40=T.sub.2.sup..Math.3.Math.T.sub.5, wherein the kernel T.sub.5 is defined by:

(53) 0 $T_{5} = (\begin{matrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{matrix}) .$

(54) Since there is only a T.sub.5 kernel at the rightmost of the Kronecker product of the generator matrix, in this case as well, the row selection algorithm provided by embodiments of the invention is optimal. The kernel T.sub.5 as well complies with the assumptions on the kernel as described above, and, therefore, the multi-kernel polar code according to embodiments of this invention (MK-dist) outperforms the other polar codes.

(55) FIG. 7 shows a schematic diagram of a corresponding method 700 for generating a polar code according to an embodiment. In this embodiment, the polar code c.sub.N has a length N and dimension K and is generated on the basis of a generator matrix G.sub.N of size NN, wherein the generator matrix G.sub.N is based on a kernel T.sub.p of size pp, with pN, wherein the polar code c.sub.N is given by c.sub.N=u.sub.N.Math.G.sub.N, wherein u.sub.N=(u.sub.0, . . . , u.sub.N-1) is a vector of size N, u.sub.i, i=0, . . . N1, corresponding to an information bit if iI, I being a set of K information bit indices, and u.sub.i=0, if iF, F being a set of NK frozen bit indices. The method 700 comprises the following steps: generating 702 a distance spectrum vector d.sub.T.sub.p=(d.sub.T.sub.p(1), . . . , d.sub.T.sub.p(p)) of size p of the kernel T.sub.p, wherein d.sub.T.sub.p(h), h=1, . . . , p, corresponds to a maximum value among all possible minimum distances of all possible polar codes of size p and dimension h generated on the basis of the kernel T.sub.p; generating 704 a distance spectrum vector d.sub.G.sub.N of size N of the generator matrix G.sub.N on the basis of the distance spectrum vector d.sub.T.sub.p; determining 706 the set of K information bit indices I on the basis of the distance spectrum vector d.sub.G.sub.N; and generating 708 the polar code c.sub.N on the basis of the set of K information bit indices I.

(56) 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.

(57) 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.

(58) 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.

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

Apparatus and method for generating polar codes

Assignee

Inventors

Cpc classification

Classification Explorer

H03M13/033

ELECTRICITY

Classification Explorer

H03M13/13

ELECTRICITY

Classification Explorer

H03M13/616

ELECTRICITY

International classification

Classification Explorer

H03M13/00

ELECTRICITY

Classification Explorer

H03M13/13

ELECTRICITY

Classification Explorer

H03M13/03

ELECTRICITY

Abstract

Claims

Description