HARQ rate-compatible polar codes for wireless channels

1. A method of constructing hybrid automatic repeat request (HART) rate-compatible polar codes for wireless channels, the method comprising:

constructing, in a base polar code generator, a base polar code of length 2 n ; and

determining, in an m-bit puncture pattern generator, a sequence of m<2 n bits to puncture in the base polar code by testing a predetermined criterion at most (2 2n +2 n )/2−1 times, where n and m are each an integer.

2. The method of claim 1 , wherein determining the m bits to puncture in the base polar code by testing the predetermined criterion at most (2 2n +2 n )/2−1 times comprises:

setting, in the terminal, a counter i equal to 2 n ;

testing the predetermined design criterion i times;

selecting one bit to puncture;

decrementing i;

if i is not equal to 2 n −m, returning to the step of testing the predetermined design criterion i times; and

if i is equal to 2 n −m, terminating the method.

3. The method of claim 1 , further comprising:

searching, in the terminal, the base polar code for a puncturing sequence;

puncturing the base polar code according to the puncturing sequence; and

constructing a final polar code of length 2 n+t bits by encoding each of the 2 n bits in the punctured base polar code 2 t times.

4. The method of claim 3 , further comprising:

storing, in the terminal, the bits of the final polar code in an array of 2 n columns and 2 t rows;

arrange the columns of the array according to a known puncturing sequence;

reading the bits of final polar code column by column;

transmitting, by the terminal, the read bits of the final polar code;

receiving, by a receiver, the transmitted bits of the final polar code;

initializing an array to zeros by the receiver; and

storing the received bits of the final polar code in the initialized array, column by column;

combine bits that are received at the same array index; and

arrange the columns of the received array according to a known puncturing sequence.

5. The method of claim 1 , further comprising:

determining, in the terminal, if Chase combining or incremental redundancy is used for retransmission;

if Chase combining is used for retransmission, retransmitting, by the terminal, the bits of the final polar code that were initially transmitted;

if incremental redundancy is used for retransmission, transmitting, by the terminal, at least one additional bit;

receiving, by a receiver, the retransmitted bits; initializing an array to zeros by the receiver;

storing the retransmitted bits in the initialized array, column by column, starting at a column index corresponding to a transmission index;

combining bits that are received at the same index in the array within the same transmission or across different transmissions; and

arrange the columns of the received array according to a known puncturing sequence.

6. The method of claim 1 , further comprising:

using, by the terminal, a higher order q Quadrature Amplitude Modulation (q-QAM) with 2 q symbols, where each group of q bits is mapped to a symbol;

transmitting, by the terminal, q QAM transmissions with q/2 different channel types;

classifying, by the terminal, C columns of transmitted bits into q/2 groups, where each group include

⌈

C

/

(

q

/

2

)

⌉

columns; and

mapping, by the terminal, each two column-wise consecutive column bits to each symbol from each column group, where the two consecutive symbols are mapped to bit-indices of a same channel type.

7. The method of claim 1 , further comprising:

selecting, by the terminal, an information set and a puncturing pattern of the base polar code according to estimated channel error probabilities; and

setting the information set for each polar code in a family of polar codes.

8. An apparatus for constructing hybrid automatic repeat request (HARQ) rate-compatible polar codes for wireless channels, the apparatus comprising:

a base polar code generator including an input for receiving a value n, and an output; and

an m-bit puncture pattern generator including a first input connected to the output of the base polar code generator, a second input for receiving a design criterion, and an output, where n and m are each an integer.

9. The apparatus of claim 1 , further comprising:

a counter including a first input for receiving a value n, a second input for receiving a decrement signal, and an output;

a comparator including a first input connected to the output of the counter, a second input connected to a reference value, and an output;

a design criterion tester including a first input connected to the output of the comparator, a second input for receiving a design criterion, a first output connected to the second input of the counter, and a second output.

10. The apparatus of claim 1 further comprising:

a base polar code puncturer including a first input connected to the output of the base polar code generator, a second input connected to the output of the m-bit puncture pattern generator, and an output; and

a final polar code generator including a first input connected to or reading the output of the base polar code puncturer, a second input for receiving a value t, and an output.

11. The apparatus of claim 10 , further comprising:

a 2″×2′ array generator including an input connected to the output of the final polar code generator, and an output;

a transmitter including an input connected to the output of the 2″×2′ array generator, and an output connected to a first antenna;

a receiver including an input connected to a second antenna, and an output; and

a 2″×2′ initialised array generator including an input connected to the output of the receiver, and an output.

12. The apparatus of claim 10 , further comprising:

a Chase combining/incremental redundancy determiner including a first input for selecting between Chase combining and incremental redundancy, a second input for receiving an initial transmission, a first output that outputs the initial transmission, and a second output that outputs an enable signal;

a combining including a first input connected to the first output of the Chase combining/incremental redundancy determiner, a second input connected to the second output of the Chase combining/incremental redundancy determiner, a third input for receiving at least one additional bit, and an output; and

a transmitter including a first input connected to the first output of the Chase combining/incremental redundancy determiner, a second input connected to the output of the combiner, and an output.

13. The apparatus of claim 11 , wherein the transmitter uses a higher order q Quadrature Amplitude Modulation with 2 q symbols, where each group of q bits is mapped to a symbol, and transmits q QAM transmissions with q/2 different channel types, and further comprising:

a column classifier including an input for receiving the q QAM transmissions, and an output that outputs C columns classified into q/2 groups, where each group constitutes ceiling(C/(q/2)) columns; and

a column-wise mapper including an input connected to the output of the column classifier, and an output where each two column-wise consecutive column bits are mapped to each symbol from each column group, where the two consecutive symbols are mapped to bit-indices of a same channel type.

14. The apparatus of claim 8 , further comprising:

an information set/puncturing pattern selector including an input for selecting an information set and a puncturing pattern, and having an output; and

a family polar code setter including an input connected to the output of the information set/puncturing pattern selector, and an output that outputs the selected information set and the puncturing pattern for all polar codes in a family.

15. A chipset for constructing hybrid automatic repeat request (HARQ) rate-compatible polar codes for wireless channels, the chipset configured to:

construct, in a base polar code generator, a base polar code of length 2 n ; and

determine, in an m-bit puncture pattern generator, a sequence of m<2 n bits to puncture in the base polar code by testing a predetermined criterion at most (2 2n +2 n )/2−1 times, where n and m are each an integer.

16. The chipset of claim 15 , further configured to:

set a counter i equal to 2 n ;

test the predetermined design criterion i times;

select one bit to puncture;

decrement i;

if i is not equal to 2 n −m, return to test the predetermined design criterion i times; and

if i is not equal to 2 n −m, terminate determining the m bits to puncture.

17. The chipset of claim 15 , further configured to:

search the base polar code for a puncturing pattern;

puncture the base polar code according to the puncturing pattern; and

construct a final polar code of length 2 n+t bits by encoding each of the 2 n bits in the punctured base polar code 2 t times.

18. The chipset of claim 17 , further configured to:

store the bits of the final polar code in an array of 2 n columns and 2 t rows;

arrange the 2 n columns of the array according to a known puncturing sequence;

read the bits of final polar code column by column;

transmit the read bits of the final polar code;

receive the transmitted bits of the final polar code;

initialize an array to zeros;

store the received bits of the final polar code in the initialized array, column by column;

combine bits that are received at the same array index; and

arrange the columns of the received array according to a known puncturing sequence.

19. The chipset of claim 15 , further configured to:

determine if Chase combining or incremental redundancy is used for retransmission; if Chase combining is used for retransmission, retransmit the bits of the final polar code that were initially transmitted;

if incremental redundancy is used for retransmission, transmit at least one additional bit; receive the retransmitted bits; initialize an array to zeros;

store the retransmitted bits in the initialized array, column by column, starting at a column index corresponding to a transmission index;

combine bits that are received at the same index in the array within the same transmission or across different transmissions; and

arrange the columns of the received array according to a known puncturing sequences.

20. The chipset of claim 15 , further configured to:

select an information set and a puncturing pattern of the base polar code according to estimated channel error probabilities; and

set the information set for each polar code in a family of polar codes.