Devices and methods for generating block punctured polar codes

Abstract

The device and method disclosed herein are configured for generating a polar code of length N and dimension K on the basis of an original polar code being defined by a code sequence S having N.sub.max bit indices sorted from least reliable to most reliable sub-channels. The device comprises a processing unit configured to: (a) generate an auxiliary code sequence having N.sub.max/2 bit indices by removing bit indices greater than or equal to N.sub.max/2 from the code sequence S; (b) remove from the auxiliary code sequence the last N.sub.R bit indices to generate a modified auxiliary code sequence; and (c) generate the polar code of length N and dimension K by puncturing the original polar code on the basis of a puncturing set defined by the last p=N.sub.max−N bit indices of the modified auxiliary code sequence.

Claims

1. A device for generating a polar code of length N and dimension K on the basis of an original polar code being defined by a code sequence S having N.sub.max bit indices, wherein the device comprises a processor configured to: generate an auxiliary code sequence having N.sub.max/2 bit indices by removing bit indices greater than or equal to N.sub.max/2 from the code sequence S; remove from the auxiliary code sequence the last N.sub.R bit indices to generate a modified auxiliary code sequence, wherein N.sub.R denotes the number of removed bits; determine the number of removed bits N.sub.R on the basis of N.sub.max, N and a predefined code rate R; and generate the polar code of length N and dimension K by puncturing the original polar code on the basis of a puncturing set defined by the last p=N.sub.max−N bit indices of the modified auxiliary code sequence.

2. The device of claim 1, wherein the processor is configured to determine the number of removed bits N.sub.R on the basis of the following equation:
N.sub.R=round(ap+b), wherein round( . . . ) denotes a rounding function and a and b denote parameters, which depend on N.sub.max and the predefined code rate R.

3. The device of claim 2, wherein the device further comprises a memory unit and wherein the processor is configured to determine the parameters a and b on the basis of a look-up table stored in the memory.

4. The device of claim 3, wherein the processor is configured to determine the parameters a and b on the basis of auxiliary parameters a′ and b′ provided in the look-up table and the following equations:
a=f(R)a′,
b=f(R)b′, wherein f(R) denotes a function of the predefined code rate R and wherein the auxiliary parameters a′ and b′ depend on N.sub.max.

5. The device of claim 4, wherein the processor is configured to determine the auxiliary parameters a′ and b′ on the basis of the look-up table and the look-up table is: TABLE-US-00003 N.sub.max b′ a′ 64 32.455 −0.87273 128 77.319 −1.2332 256 138.56 −1.1028 512 275.89 −1.1111 1024 572.83 −1.1649

6. The device of claim 4, wherein the processor is configured to determine the parameters a and b on the basis of the auxiliary parameters a′ and b′ provided in the look-up table and the following equations:
a=R.sup.2a′,
b=R.sup.2b′.

7. The device of claim 1, wherein the processor is configured to determine the number of removed bits N.sub.R on the basis of the following equation:
N.sub.R=max(0,round(ap+b)), wherein round( . . . ) denotes a rounding function, max( . . . ) denotes the maximum function and a and b denote parameters, which depend on N.sub.max and the predefined code rate R.

8. A method for generating a polar code of length N and dimension K on the basis of an original polar code being defined by a code sequence S having N.sub.max bit indices, wherein the method comprises: generating an auxiliary code sequence having N.sub.max/2 bit indices by removing bit indices greater than or equal to N.sub.max/2 from the code sequence S; removing from the auxiliary code sequence the last N.sub.R bit indices to generate a modified auxiliary code sequence, wherein N.sub.R denotes the number of removed bits and wherein the number of removed bits N.sub.R is determined on the basis of N.sub.max, N and a predefined code rate R; and generating the polar code of length N and dimension K by puncturing the original polar code on the basis of a puncturing set defined by the last p=N.sub.max−N bit indices of the modified auxiliary code sequence.

9. The method of claim 8, wherein the number of removed bits N.sub.R is determined on the basis of the following equation:
N.sub.R=round(ap+b), wherein round( . . . ) denotes a rounding function and a and b denote parameters, which depend on N.sub.max and the predefined code rate R.

10. The method of claim 9, wherein the parameters a and b are determined on the basis of a look-up table.

11. The method of claim 10, wherein the parameters a and b are determined on the basis of auxiliary parameters a′ and b′ provided in the look-up table and the following equations:
a=f(R)a′,
b=f(R)b′, wherein f(R) denotes a function of the predefined code rate R and wherein the auxiliary parameters a′ and b′ depend on N.sub.max.

12. The method of claim 11, wherein the auxiliary parameters a′ and b′ are determined on the basis of the look-up table and the look-up table is: TABLE-US-00004 N.sub.max b′ a′ 64 32.455 −0.87273 128 77.319 −1.2332 256 138.56 −1.1028 512 275.89 −1.1111 1024 572.83 −1.1649

13. The method of claim 11, wherein the parameters a and b are determined on the basis of the auxiliary parameters a′ and b′ provided in the look-up table and the following equations:
a=R.sup.2a′,
b=R.sup.2b′.

14. The method of claim 8, wherein the number of removed bits N.sub.R is determined on the basis of the following equation:
N.sub.R=max(0,round(ap+b)), wherein round( . . . ) denotes a rounding function, max( . . . ) denotes the maximum function and a and b denote parameters, which depend on N.sub.max and the predefined code rate R.

15. A non-transitory computer storage medium storing a program code, wherein when the program code is executed by a computer, the program code causes the computer to perform: generating an auxiliary code sequence having N.sub.max/2 bit indices by removing bit indices greater than or equal to N.sub.max/2 from the code sequence S; removing from the auxiliary code sequence the last N.sub.R bit indices to generate a modified auxiliary code sequence, wherein N.sub.R denotes the number of removed bits and wherein the number of removed bits N.sub.R is determined on the basis of N.sub.max, N and a predefined code rate R; and generating the polar code of length N and dimension K by puncturing the original polar code on the basis of a puncturing set defined by the last p=N.sub.max−N bit indices of the modified auxiliary code sequence.

16. The computer storage medium of claim 15, wherein the number of removed bits N.sub.R is determined on the basis of the following equation:
N.sub.R=round(ap+b), wherein round( . . . ) denotes a rounding function and a and b denote parameters, which depend on N.sub.max and the predefined code rate R.

17. The computer storage medium of claim 16, wherein the parameters a and b are determined on the basis of a look-up table.

18. The computer storage medium of claim 17, wherein the parameters a and b are determined on the basis of auxiliary parameters a′ and b′ provided in the look-up table and the following equations:
a=f(R)a′,
b=f(R)b′, wherein f(R) denotes a function of the predefined code rate R and wherein the auxiliary parameters a′ and b′ depend on N.sub.max.

19. The computer storage medium of claim 18, wherein the auxiliary parameters a′ and b′ are determined on the basis of the look-up table and the look-up table is: TABLE-US-00005 N.sub.max b′ a′ 64 32.455 −0.87273 128 77.319 −1.2332 256 138.56 −1.1028 512 275.89 −1.1111 1024 572.83 −1.1649

20. The computer storage medium of claim 19, wherein the parameters a and b are determined on the basis of the auxiliary parameters a′ and b′ provided in the look-up table and the following equations:
a=R.sup.2a′,
b=R.sup.2b′.

21. The computer storage medium of claim 15, wherein the number of removed bits N.sub.R is determined on the basis of the following equation:
N.sub.R=max(0,round(ap+b)), wherein round( . . . ) denotes a rounding function, max( . . . ) denotes the maximum function and a and b denote parameters, which depend on N.sub.max and the predefined code rate R.

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 conventional BRV shortening;

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

(4) FIG. 3 shows a flow diagram illustrating different processing steps implemented in a device for generating a polar code according to an embodiment;

(5) FIG. 4 shows a schematic illustrating an example for the puncturing scheme implemented in a device for generating a polar code according to an embodiment;

(6) FIG. 5 shows a flow diagram illustrating different processing steps implemented in a device for generating a polar code according to an embodiment;

(7) FIG. 6 shows a schematic diagram of a communication system comprising a device for generating a polar code according to an embodiment;

(8) FIG. 7 shows a schematic diagram illustrating the performance of polar codes generated by a device for generating a polar code according to an embodiment;

(9) FIG. 8 shows a schematic diagram illustrating the performance of polar codes generated by a device for generating a polar code according to an embodiment; and

(10) FIG. 9 shows a flow diagram illustrating a method for generating a polar code according to an embodiment.

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

DETAILED DESCRIPTION OF EMBODIMENTS

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

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

(14) FIG. 2 shows a schematic diagram of a communication system 200 with a first communication apparatus 202 comprising a device 202b for generating a polar code according to an embodiment and a second communication apparatus 204 comprising a device 204b for generating a polar code according to an embodiment. In an embodiment, the first communication apparatus 202 and/or the second communication apparatus 204 could be mobile phones or other communication devices configured to communicate via a communication channel 203.

(15) Generally, a polar code is a (N=2.sup.m, K) linear block code generated by K rows j.sub.i∈{0, . . . , N−1}\F, 0≤i<K of matrix

(16) $A_m={\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)}^{.Math.m},$
where S.sup..Math.m denotes the m-fold Kronecker product of the matrix S with itself. The encoding algorithm is as follows: c.sub.0.sup.N-1=u.sub.0.sup.N-1A.sub.log.sub.2.sub.N, where u.sub.i.sup.j=(u.sub.i, . . . , u.sub.j), u.sub.l=0 for l∈F and the remaining elements of the vector u are set by the payload symbols to be encoded. F is the set of frozen bits constructed, for instance, as the set of indexes l of low-capacity or high error probability synthetic bit subchannels.

(17) The first communication apparatus 202 comprises a channel encoder 202a, wherein the channel encoder 202a comprises the device 202b for generating a polar code of length N and dimension K on the basis of an original polar code being defined by a code sequence S having N.sub.max bit indices sorted from least reliable to most reliable sub-channels. N.sub.max is usually a power of 2, i.e. N.sub.max=2.sup.m, N and K can be arbitrary positive integers smaller than N.sub.max with N.sub.max=2.sup.[log.sup.2.sub.N] and 0<K≤N. The channel encoder 202a is configured to encode data using the generated polar code of length N and dimension K and provide the encoded data via the communication channel 203 to the second communication apparatus 204. Differently put, the channel encoder 202a is configured to encode an information message of size K into a codeword of size N on the basis of the polar code generated by the processing unit 202c of the device 202b.

(18) The second communication apparatus 204 comprises a channel decoder 204a, wherein the channel decoder 204a comprises a device 204b for generating a polar code of length N and dimension K on the basis of an original polar code being defined by a code sequence S having N.sub.max bit indices sorted from least reliable to most reliable sub-channels. The channel decoder 204a of the second communication apparatus 204 is configured to decode the encoded data provided by the first communication apparatus 202, for instance, on the basis of a successive-cancellation (SC) scheme or a successive-cancellation list (SCL) scheme. In an embodiment, the channel decoder 204a is configured to decode N log likelihood ratios of codeword bits into an information message of size K on the basis of the polar code generated by the processing unit 204c of the device 204b.

(19) As can be taken from FIG. 2, the device 202b of the first communication apparatus 202 comprises a processing unit 202c and the device 204b of the second communication apparatus 204 comprises a processing unit 204c. In the following the functionality of the processing unit 202c of the device 202b of the first communication apparatus 202 will be described in more detail with the understanding that the processing unit 204c of the device 204b of the second communication apparatus 204 provides the same functionality.

(20) As will be described in more detail further below, the processing unit 202c of the device 202b of the first communication apparatus 202 is configured to: (a) generate an auxiliary code sequence having N.sub.max/2 bit indices by removing bit indices greater than or equal to N.sub.max/2 from the code sequence S; (b) remove from the auxiliary code sequence the last N.sub.R bit indices to generate a modified auxiliary code sequence, wherein N.sub.R denotes the number of removed bits and wherein the processing unit 202c is configured to determine the number of removed bits N.sub.R on the basis of N.sub.max, N and a predefined code rate R; and (c) generate the polar code of length N and dimension K by puncturing the original polar code on the basis of a puncturing set defined by the last p=N.sub.max−N bit indices of the modified auxiliary code sequence.

(21) The above described construction of the puncturing set of bits or bit indices is illustrated in FIG. 3. Having a code sequence S of length N.sub.max (stage 301), all indices greater than or equal to N.sub.max/2 are removed from the code sequence S of length N.sub.max (stage 303). In a further stage 305, the last N.sub.R indices are removed from the code sequence of length N.sub.max/2. If S.sub.N.sub.R denotes sequence obtained after the stage 305, then the punctured bits in the c domain are the last elements of the sequence S.sub.N.sub.R. The scheme shown in FIG. 3 is illustrated by an example shown in FIG. 4 for a code sequence S of length 1024.

(22) FIG. 5 illustrates how the construction of the puncturing set of bit indices shown in FIG. 3 is implemented in the device 202b, 204b for generating a polar code of length N and dimension K on the basis of an original polar code being defined by a code sequence S having N.sub.max bit indices sorted from least reliable to most reliable sub-channels. After the construction of the puncturing set of bit indices P (stage 300), all bit indices of the puncturing set of bit indices P are removed from the code sequence S (stage 503). Thereafter, the first N−K indices of the code sequence S are set as frozen bits (stage 505).

(23) In an embodiment, the processing unit 202c of the device 202b of the first communication apparatus 202 is configured to determine the number of removed bits N.sub.R on the basis of the following equation:
N.sub.R=round(ap+b),
wherein round( . . . ) denotes a rounding function and a and b denote parameters, which depend on N.sub.max and the predefined code rate R. In an embodiment, the rounding function can be a ceiling function or a floor function. In an embodiment, the processing unit 202c of the device 202b of the first communication apparatus 202 is configured to determine the number of removed bits N.sub.R on the basis of the following equation:
N.sub.R=max(0,round(ap+b)),
wherein max( . . . ) denotes the maximum function.

(24) In an embodiment, the device 202b of the first communication apparatus 202 (and likewise the device 204b of the second communication apparatus 204) can further comprise a memory unit, wherein the processing unit 202c is configured to determine the parameters a and b on the basis of a look-up table stored in the memory unit.

(25) In an embodiment, the processing unit 202c of the device 202b of the first communication apparatus 202 is configured to determine the parameters a and b on the basis of auxiliary parameters a′ and b′ provided in the look-up table and the following equations:
a=f(R)a′,
b=f(R)b′,
wherein f(R) denotes a function of the predefined code rate R and wherein the auxiliary parameters a′ and b′ depend on N.sub.max.

(26) In an embodiment, the processing unit 202c of the device 202b of the first communication apparatus 202 is configured to determine the auxiliary parameters a′ and b′ on the basis of the following look-up table:

(27) TABLE-US-00002 N.sub.max b′ a′ 64 32.455 −0.87273 128 77.319 −1.2332 256 138.56 −1.1028 512 275.89 −1.1111 1024 572.83 −1.1649

(28) In an embodiment, the processing unit 202c of the device 202b of the first communication apparatus 202 is configured to determine the parameters a and b on the basis of the auxiliary parameters a′ and b′ provided in the look-up table and the following equations:
a=R.sup.2a′,
b=R.sup.2b′.

(29) In an embodiment, the channel encoder 202a of the first communication apparatus 202 is configured to use as a set of frozen bits the bits defined by the N.sub.max−N bit indices of the code sequence S defined by the puncturing set and the first N−K bit indices of the code sequence S without the puncturing set for encoding an information message of size K into a codeword of size N on the basis of the polar code generated by the processing unit 202c of the device 202b.

(30) Likewise, in an embodiment, the channel decoder 204a of the second communication apparatus is configured to use as a set of frozen bits the bits defined by the N.sub.max−N bit indices of the code sequence S defined by the puncturing set and the first N−K bit indices of the code sequence S without the puncturing set for decoding N log likelihood ratios of codeword bits into an information message of size K on the basis of the polar code generated by the processing unit 204c of the device 204b.

(31) In the following, some of the embodiments described above are summarized in an algorithmic form.

(32) The scheme for generating the puncturing set P as implemented in the device 202a, 204a according to an embodiment can be summarized as the following Algorithm 1:

(33) Input:

(34) Code sequence S of length N.sub.max;

(35) Number of punctured bits p;

(36) Lookup table LT (as described above);

(37) Code rate R.

(38) Output:

(39) Set P of bits to be punctured.

(40) 1. Set S.sub.2 to be vector of size N.sub.max/2;

(41) 2. j=0;

(42) 3. For i from 0 to N.sub.max−1: a. If S[i]<N.sub.max/2 then: i. S.sub.2[j]=S[i]; ii. j=j+1.

(43) 4. Based on N.sub.max and lookup table LT, set a′, b′;

(44) 5. a=a′R.sup.2, b=b′R.sup.2;

(45) 6. N.sub.R=round(ap+b) or N.sub.R=max(0,round(ap+b));

(46) 7. P=S.sub.2[N.sub.max−N.sub.R−p, . . . , N.sub.max−N.sub.R−1];

(47) The scheme for encoding an information message of length K into a codeword of length N, using a (N.sub.max=2.sup.[log.sup.2.sup.N], K) polar code as implemented in the channel encoder 202a according to an embodiment can be summarized as the following Algorithm 2:

(48) Input:

(49) Bit sequence I of length K;

(50) Required codeword length N, N.sub.max=2.sup.[log.sup.2.sup.N];

(51) Code sequence S of length N.sub.max;

(52) Lookup table LT (as described above).

(53) Output:

(54) Codeword C of length N.

(55) 1. Using Algorithm 1, determine set of punctured bits P of size p=N.sub.max−N;

(56) 2. S=S\P;

(57) 3. Frozen bits set F=S[0, . . . , N−K−1]∪P;

(58) 4. Encode message l into codeword C using (N.sub.max, K) Polar code, with frozen channels defined in accordance with set F;

(59) 5. C=C[{0, . . . , N.sub.max−1}\P].

(60) The scheme for decoding the codeword obtained using Algorithm 2 as implemented in the channel decoder 204a according to an embodiment can be summarized as the following Algorithm 3:

(61) Input:

(62) Vector L of log likelihood ratios (LLRs) of codeword bits of length N, N.sub.max=2.sup.[log.sup.2.sup.N];

(63) Required information message length K;

(64) Code sequence S of length N.sub.max;

(65) Lookup table LT (as described above).

(66) Output:

(67) Information message I of length K.

(68) 1. Using Algorithm 1, determine set of punctured bits P of size p=N.sub.max−N;

(69) 2. Set L.sub.F to be vector of size N.sub.max consisting of all zeroes;

(70) 3. j=0;

(71) 4. For i from 0 to N.sub.max−1: a. If i∈P then continue; b. L.sub.F[i]=L[j]; c. j=j+1;

(72) 5. S=S\P;

(73) 6. Frozen bits set F=S[0, . . . , N−K−1]∪P;

(74) 7. Decode codeword defined by LLRs vector L.sub.F into information message I using (N.sub.max, K) Polar code, with frozen channels defined in accordance with set F.

(75) FIG. 6 shows a further embodiment of the communication system 200 of FIG. 2. In the embodiment shown in FIG. 6, the first communication apparatus 202 further comprises a modulator 202d for transforming the codeword into channel symbols and the second communication apparatus 204 further comprises a demodulator 204d for generating a plurality of LLRs on the basis of the noisy channel symbols received via the communication channel 203 from the first communication apparatus 202 and providing the plurality of LLRs to the channel decoder 204a for retrieving the decoded information message.

(76) The puncturing scheme implemented in embodiments of the invention allows constructing polar codes of any length, which demonstrate a better or similar performance in comparison with polar codes generated by rate matching schemes. Corresponding simulation results for code rates 1/3, 1/4, . . . , 1/8 are presented in FIG. 7. Results for cases relevant to ultra-reliable low latency channel (URLLC) communication are presented in FIG. 8.

(77) In FIG. 7 each curve corresponds to some fixed code rate. The solid curves correspond to the scheme adopted for the future 5G enhanced mobile broadband (eMBB) control channel. The dashed lines correspond to the puncturing scheme implemented in embodiments of the invention. The dimension is plotted along the X axis and the SNR needed to achieve a Frame Error Rate (FER) of 10.sup.−3 is plotted along the Y axis. The results have been obtained using a CA-SCL decoder with list size 8 and CRC 11.

(78) In FIG. 8 each curve corresponds to some fixed dimension. The solid curves correspond to the scheme adopted for the future 5G eMBB control channel. The dashed lines correspond to the puncturing scheme implemented in embodiments of the invention. The code length is plotted along the X axis, while the SNR needed to achieve a Frame Error Rate of 10.sup.−5 is plotted along the Y axis. The results have been obtained using a CA-SCL decoder with list size 8 and CRC 24.

(79) FIG. 9 illustrates a corresponding method 900 for generating a polar code of length N and dimension K on the basis of an original polar code being defined by a code sequence S having N.sub.max bit indices sorted from least reliable to most reliable sub-channels. The method 900 comprises the steps of: (a) generating 901 an auxiliary code sequence having N.sub.max/2 bit indices by removing bit indices greater than or equal to N.sub.max/2 from the code sequence S; (b) removing 903 from the auxiliary code sequence the last N.sub.R bit indices to generate a modified auxiliary code sequence, wherein N.sub.R denotes the number of removed bits and wherein the number of removed bits N.sub.R are determined on the basis of N.sub.max, N and a predefined code rate R; and (c) generating 905 the polar code of length N and dimension K by puncturing the original polar code on the basis of a puncturing set defined by the last p=N.sub.max−N bit indices of the modified auxiliary code sequence.

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

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

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

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