CHANNEL INTERLEAVING METHOD AND APPARATUS

• US 20200136655A1
• Filed: 12/27/2019
• Published: 04/30/2020
• Est. Priority Date: 06/27/2017
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: SHEN, Hui, LI, Bin, GU, Jiaqi, TONG, Wen
• Granted Patent: US 11,082,070 B2
• Time in Patent Office: Days
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/27 using interleaving techniques
• CPC Class Codes: H03M 13/2792 Interleaver wherein interleaving is performed jointly with another technique such as puncturing, multiplexing or routing
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

The present invention provides channel interleaving method of a polar (Polar) code. The method includes: determining an M__r-row and M__c-column matrix used for interleaving, and permutating, based on permutation patterns of the column sequence numbers and/or permutation patterns of the row sequence numbers, the matrix into which the to-be-interleaved bits are written. The permutation patterns of the column sequence numbers are represented by: [P_c(0), P_c(1), . . . , P_c(i_c), . . . , P_c(M__c−1)]. P_c(i_c) is obtained by performing pruned bit reverse (PBR, pruned bit reverse)-based mapping on the column sequence number i_c. The permutation patterns of the row sequence numbers are represented by: [P_r(0), P_r(1), . . . , P_r(i_r), . . . , P_r(M__r−1)]. P_r(i_r) is obtained by performing pruned bit reverse (PBR, pruned bit reverse)-based mapping on the row sequence number i_r; and reading interleaved bits from the permutated matrix.

Claims

1. A channel interleaving method of a polar (Polar) code, comprising:

determining an M__r-row and M__c-column matrix used for interleaving, wherein

column sequence numbers of the matrix are represented by;

[0, 1, . . . , i_c, . . . , M__c−

1], wherein i_c is greater than or equal to 0, and is less than or equal to M__c−

1; and

row sequence numbers of the matrix are represented by;

[0, 1, . . . , i_r, . . . , M__r−

1], wherein i_r is greater than or equal to 0, and is less than or equal to M__r−

1;

writing to-be-interleaved bits into the matrix; and

permutating, based on permutation patterns of the column sequence numbers and/or permutation patterns of the row sequence numbers, the matrix into which the to-be-interleaved bits are written, wherein

the permutation patterns of the column sequence numbers are represented by;

[P_c(0), P_c(1), . . . , P_c(i_c), . . . , P_c(M__c−

1)], wherein P_c(i_c) is obtained by performing pruned bit reverse (PBR, pruned bit reverse))-based mapping on column sequence number i_c; and

the permutation patterns of the row sequence numbers are represented by;

[P_r(0), P_r(1), . . . , P_r(i_r), . . . , P_r(M__r−

1)], wherein P_r(i_r) is obtained by performing pruned bit reverse (PBR, pruned bit reverse)-based mapping on row sequence number i_r; and

reading interleaved bits from the permutated matrix.

2. The method according to claim 1, wherein determining the M__r-row and M__c-column matrix used for interleaving comprises:

obtaining a preset column quantity M__c corresponding to a bit quantity M of the to-be-interleaved bits; and

determining the row quantity M__r based on a formula M__r=ceil(M/M__c); and

determining the column quantity M__c based on a formula M__c=ceil(M/M__r).

3. The method according to claim 2, wherein the preset column quantity M__c or row quantity M__r corresponding to the bit quantity M of the to-be-interleaved bits comprises one of at least one of the following rows:

4. The method according to claim 1, wherein determining the M__r-row and M__c-column matrix used for interleaving comprises:

obtaining a preset column quantity M__c corresponding to a bit quantity M of the to-be-interleaved bits;

obtaining the preset row quantity M__r corresponding to a bit quantity M of the to-be-interleaved bits; and

determining the column quantity M__c based on a formula M__c=ceil(M/M__r).

5. The method according to claim 1, wherein the method further comprises:

determining the permutation patterns of the column sequence numbers and/or the permutation patterns of the row sequence numbers.

6. The method according to claim 5, wherein determining the permutation patterns of the column sequence numbers comprises:

obtaining the permutation patterns of the column sequence numbers corresponding to the preset column quantity M__c;

or

obtaining the permutation patterns of the row sequence numbers corresponding to the preset row quantity M__r.

7. The method according to claim 6, wherein the permutation patterns of the column sequence numbers corresponding to the preset column quantity M__c or the permutation patterns of the row sequence numbers corresponding to the preset row quantity M__r comprise at least one of the following rows:

8. The method according to claim 5, wherein the determining the permutation patterns of the column sequence numbers and/or the permutation patterns of the row sequence numbers comprises:

obtaining the permutation patterns of the column sequence numbers and/or the permutation patterns of the row sequence numbers through PBR-based mapping.

9. The method according to claim 8, wherein a value of PBR(i_c, M__c) is represented by P_c(i_c), and a value of PBR(i_r, M__r) is represented by P_r(i_r), wherein PBR(i, M_) comprises PBR(i_c, M__c) or PBR(i_r, M__r);

P(i) comprises P_c(i_c) or P_r(i_r); and

M_ comprises M__c or M__r; and

the PBR-based mapping comprises at least one of the following algorithms;

Algorithm 1;

(1) determining a parameter n of PBR, wherein n=ceil(log₂(M_));

(2) initialization;

i=0, and j=0;

(3) defining x as a decimal digit corresponding to a binary digit obtained through reverse of a binary digit represented by n bits of j;

(4) if x<

M_,

P(i)=x; and

i=i+1;

(5) j=j+1; and

(6) if (i<

M_), performing step (3);

Algorithm 2;

if M_ is not an integer power of 2, using Algorithm 1;

or

if M_ is an integer power of 2, in other words, M_=2ⁿ, simplifying PBR(i, M_) as bit reverse (Bit Reverse)-based mapping, wherein the simplifying comprises;

(a) representing i by a binary digit represented by n bits;

(b) reversing the binary digit to obtain a reversed binary digit; and

(c) converting the reversed binary digit into a decimal digit, wherein the decimal digit is P(i);

Algorithm 3;

(i) determining a parameter n of PBR, wherein n=ceil(log₂(M_));

(ii) determining a decimal digit corresponding to a binary digit obtained through reverse of a binary digit represented by n bits of each element in [0, 1, . . . , 2ⁿ], to obtain a sequence [a₀, a₁, . . . , a_2n]; and

(iii) removing (which may also be referred to as pruning) an element whose value is greater than or equal to M_ in [a₀, a₁, . . . , a_2n], to obtain a sequence [P(0), . . . , P(M_)];

Algorithm 4;

(*) determining a maximum value M_Max of a column quantity of each to-be-interleaved matrix, and determining a maximum value of a parameter n_max of PBR, wherein n_max=ceil(log₂(M_Max));

(**) generating or pre-storing (generating) a decimal digit corresponding to a binary digit obtained through reverse of a binary digit represented by n_max bits of each element in [0, 1, . . . , 2^nmax], to obtain a sequence [a₀, a₁, . . . , a_2nmax]; and

(***) removing an element whose value is greater than or equal to M_ in [a₀, a₁, . . . , a_2nmax], to obtain an M_-column sequence [P(0), . . . , P(M_)]; and

Algorithm 5;

obtaining the permutation patterns of the column sequence numbers through PBR permutation of M_ bits with a cyclic shift by t1, wherein

P(i)=PBR(mod(i+t1,M_),M_), whereini=0,1,2, . . . , or M_−

1.

18. A communications apparatus, comprising:

a memory, configured to store a program; and

a processor, configured to execute the program stored in the memory, wherein when the program is executed, the processor is configured to perform the step according to claim 1.

10. A communications apparatus, comprising hardware modules including:

a determining module, configured to determine an M__r-row and M__c-column matrix used for interleaving, wherein

column sequence numbers of the matrix are represented by;

[0, 1, . . . , i_c, . . . , M__c−

1], wherein i_c is greater than or equal to 0, and is less than or equal to M__c−

1; and

row sequence numbers of the matrix are represented by;

[0, 1, . . . , i_r, . . . , M__r−

1], wherein i_r is greater than or equal to 0, and is less than or equal to M__r−

1;

a writing module, configured to write to-be-interleaved bits into the matrix;

a permutation module, configured to permutate, based on permutation patterns of the column sequence numbers and/or permutation patterns of the row sequence numbers, the matrix into which the to-be-interleaved bits are written, wherein

the permutation patterns of the column sequence numbers are represented by;

[P_c(0), P_c(1), . . . , P_c(i_c), . . . , P_c(M__c−

1)], wherein P_c(i_c) is obtained by performing pruned bit reverse (PBR, pruned bit reverse)-based mapping on column sequence number i_c; and

the permutation patterns of the row sequence numbers are represented by;

[P_r(0), P_r(1), . . . , P_r(i_r), . . . , P_r(M__r−

1)], wherein P_r(i_r) is obtained by performing pruned bit reverse (PBR, pruned bit reverse)-based mapping on row sequence number i_r; and

a reading module, configured to read interleaved bits from the permutated matrix.

11. The apparatus according to claim 10, wherein the determining module is configured to:

obtain a preset column quantity M__c corresponding to a bit quantity M of the to-be-interleaved bits; and

determine the row quantity M__r based on a formula M__r=ceil(M/M__c);

or configured to;

obtain the preset row quantity M__r corresponding to a bit quantity M of the to-be-interleaved bits; and

determine the column quantity M__c based on a formula M__c=ceil(M/M__r).

12. The apparatus according to claim 11, wherein the preset column quantity M__c or row quantity M__r corresponding to the bit quantity M of the to-be-interleaved bits comprises one of at least one of the following rows:

13. The apparatus according to claim 10, wherein the determining module is configured to determine the permutation patterns of the column sequence numbers and/or the permutation patterns of the row sequence numbers.

14. The apparatus according to claim 13, wherein the determining module is configured to

obtain the permutation patterns of the column sequence numbers corresponding to the preset column quantity M__c;

or

obtain the permutation patterns of the row sequence numbers corresponding to the preset row quantity M__r.

15. The apparatus according to claim 14, wherein the permutation patterns of the column sequence numbers corresponding to the preset column quantity M__c comprise at least one of the following rows:

16. The apparatus according to claim 13, wherein the determining module is configured to obtain the permutation patterns of the column sequence numbers and/or the permutation patterns of the row sequence numbers through PBR-based mapping.

17. The apparatus according to claim 16, wherein a value of PBR(i_c, M__c) is represented by P_c(i_c), and a value of PBR(i_r, M__r) is represented by P_r(i_r), wherein PBR(i, M_) comprises PBR(i_c, M__c) or PBR(i_r, M__r);

P(i) comprises P_c(i_c) or P_r(i_r); and

M_ comprises M__c or M__r; and

the PBR-based mapping comprises at least one of the following algorithms;

Algorithm 1;

(1) determining a parameter n of PBR, wherein n=ceil(log₂(M_));

(2) initialization;

i=0, and j=0;

(3) defining x as a decimal digit corresponding to a binary digit obtained through reverse of a binary digit represented by n bits of j;

(4) if x<

M_,

P(i)=x; and

i=i+1;

(5) j=j+1; and

(6) if (i<

M_), performing step (3);

Algorithm 2;

if M_ is not an integer power of 2, using Algorithm 1;

or

if M_ is an integer power of 2, in other words, M_=2ⁿ, simplifying PBR(i, M_) as bit reverse (Bit Reverse)-based mapping, wherein the simplifying specifically comprises;

(a) representing i by a binary digit represented by n bits;

(b) reversing the binary digit to obtain a reversed binary digit; and

(c) converting the reversed binary digit into a decimal digit, wherein the decimal digit is P(i);

Algorithm 3;

(i) determining a parameter n of PBR, wherein n=ceil(log₂(M_));

(ii) determining a decimal digit corresponding to a binary digit obtained through reverse of a binary digit represented by n bits of each element in [0, 1, . . . , 2ⁿ], to obtain a sequence [a₀, a₁, . . . , a_2n]; and

(iii) removing (which may also be referred to as pruning) an element whose value is greater than or equal to M_ in [a₀, a₁, . . . , a_2n], to obtain a sequence [P(0), . . . , P(M_)];

Algorithm 4;

(*) determining a maximum value M_Max of a column quantity of each to-be-interleaved matrix, and determining a maximum value of a parameter n_max of PBR, wherein n_max=ceil(log₂(M_Max));

(**) generating or pre-storing (generating) a decimal digit corresponding to a binary digit obtained through reverse of a binary digit represented by n_max bits of each element in [0, 1, . . . , 2^nmax], to obtain a sequence [a₀, a₁, . . . , a_2nmax]; and

(***) removing an element whose value is greater than or equal to M__c in [a₀, a₁, . . . , a_2nmax,], to obtain an M_-column sequence [P(0), . . . , P(M_)]; and

Algorithm 5;

obtaining the permutation patterns of the column sequence numbers through PBR permutation of M_ bits with a cyclic shift by t1, wherein

P(i)=PBR(mod(i+t1,M_),M_), wherein i=0,1,2, . . . , or M_−

1.