Reduced-stage polar decoding

• US 10,447,435 B2
• Filed: 07/17/2017
• Issued: 10/15/2019
• Est. Priority Date: 08/19/2016
• 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: Shi, Wuxian, Ge, Yiqun
• Primary Examiner(s): Nguyen, Thien
• Application Number:
  US15/651,390
• Publication Number:
  US 20180054278A1
• Time in Patent Office: 820 Days
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing
• CPC Class Codes: H03M 13/6505 Memory efficient implementations
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 1/0058 Block-coded modulation
• CPC Class Codes: H04W 88/02 Terminal devices
• CPC Class Codes: H04W 88/08 Access point devices

Abstract

In reduced-stage polar decoding, a received word that is based on an N-bit codeword of a polar code is decoded using fewer than log₂N Log Likelihood Ratio (LLR) stages. Decoding uses a reduced stage decoding configuration. In an embodiment, such a configuration includes at least one higher-order LLR stage with nodes implementing functions that are based on a combination of lower-order polar code kernels.

Claims

1. A method comprising:

receiving from a transmitter, over a physical channel, a word that is based on an N-bit codeword of a polar code;

decoding the received word using Successive Cancellation (SC) decoding and fewer than log₂N Log Likelihood Ratio (LLR) stages, the LLR stages comprising an LLR stage including nodes that implement functions combining more than two inputs, the inputs to each node comprising LLR values, or LLR values and a partial sum of previously decoded bits of the received word; and

outputting decoded bits, from decoding the received word, for further processing,

wherein the decoding using SC decoding and fewer than log₂N LLR stages provides reduced latency and reduced memory space requirements relative to decoding using SC decoding and log₂N LLR stages.

2. The method of claim 1, wherein the LLR stage including nodes that each implement functions combining more than two inputs comprises a higher-order LLR stage with the nodes implementing the functions based on a combination of lower-order polar code kernels.

3. The method of claim 2, wherein the lower-order polar code kernels are 2-by-2 polar code kernels.

4. The method of claim 3, wherein the functions comprise one or more of the following A, B, C, and D functions or equivalent functions consistent therewith:

A-function;

llr0′

=sgn(llr0)·

sgn(llr1)·

sgn(llr2)·

sgn(llr3)·

min(|llr0|,|llr1|,|llr2|,|llr3|)

B-function;

llr1′

=(llr1)·

sgn(llr3)·

min(|llr1|,|llr3|)+sgnb(û

₀)sgn(llr0)·

sgn(llr2)·

min(|llr0|,|llr2|), or equivalently

5. The method of claim 2, wherein the functions comprise one or more of the following A8 functions or equivalent functions consistent therewith:

A8_0 function;

llr0′

=sgn(llr0)*sgn(llr1)*sgn(llr2)*sgn(llr3)*sgn(llr4)*sgn(llr5)*sgn(llr6)*sgn(llr7)*min{|llr0|,|llr1|,|llr2|,|llr3|,|llr4|,|llr5|,|llr6|,|llr7|}

A8_1 function;

llr1′

=sgnb(û

₀)*sgn(llr0)*sgn(llr2)*sgn(llr4)*sgn(llr6)*min{|llr0|,|llr2|,|llr4|,|llr6|}+sgn(llr1)*sgn(llr3)*sgn(llr5)*sgn(llr7)*min{|llr1|,|llr3|,|llr7|}

A8_2 function;

temp1=sgnb(û

₀⊕

û

₁)·

[sgn(llr0)·

sgn(llr4)·

min(|llr0|,|llr4|)]+sgn(llr2)·

sgn(llr6)·

min(|llr2|,|llr6|)

temp2=sgnb(û

₁)·

[sgn(llr1)·

sgn(llr5)·

min(|llr1|,|llr5|)]+sgn(llr3)·

sgn(llr7)·

min(|llr3|,|llr7|)

llr2′

=sgn(temp1)·

sgn(temp2)·

min(|temp1|,|temp2|)

A8_3 function;

6. The method of claim 1, wherein the LLR stages further comprise an LLR stage with f and g nodes, which respectively apply the following functions or equivalent functions consistent therewith:

f-function;

llr0′

=sgn(llr0)·

sgn(llr1)·

min(|llr0|,|llr1|)

g-function;

llr1′

=llr1+sgnb(û

₀)·

llr0,

where

û

₀ is an estimated bit value;

llrx are input LLR values;

llrx′

are output LLR values; and

min( ) is minimum.

7. The method of claim 1, wherein the decoding comprises List decoding.

8. An apparatus comprising:

a receiver for receiving from a transmitter, over a physical channel, a word that is based on an N-bit codeword of a polar code; and

a decoder, coupled to the receiver, to decode the received word using Successive Cancellation (SC) decoding and fewer than log₂N Log Likelihood Ratio (LLR) stages, the LLR stages comprising an LLR stage including nodes that implement functions combining more than two inputs, the inputs to each node comprising LLR values, or LLR values and a partial sum of previously decoded bits of the received word, and to output decoded bits, from decoding the received word, for further processing,

wherein decoding using SC decoding and fewer than log₂N LLR stages provides reduced latency and reduced memory space requirements relative to decoding using SC decoding and log₂N LLR stages.

9. The apparatus of claim 8, wherein the LLR stage including nodes that each implement functions combining more than two inputs comprises a higher-order LLR stage with the nodes implementing the functions based on a combination of lower-order polar code kernels.

10. The apparatus of claim 8, wherein the lower-order polar code kernels are 2-by-2 polar code kernels.

11. The apparatus of claim 10, wherein the functions comprise one or more of the following A, B, C, and D functions or equivalent functions consistent therewith:

A-function;

llr0′

=sgn(llr0)·

sgn(llr1)·

sgn(llr2)·

sgn(llr3)·

min(|llr0|,|llr1|,|llr2|,|llr3|)

B-function;

llr1′

=sgn(llr1)·

sgn(llr3)·

min(|llr1|,|llr3|)+sgnb(û

₀)sgn(llr0)·

sgn(llr2)·

min(|llr0|,|llr2|), or equivalently

12. The apparatus of claim 9, wherein the functions comprise one or more of the following A8 functions or equivalent functions consistent therewith:

A8_0 function;

llr0′

=sgn(llr0)*sgn(llr1)*sgn(llr2)*sgn(llr3)*sgn(llr4)*sgn(llr5)*sgn(llr6)*sgn(llr7)*min{|llr0|,|llr1|,|llr2|,|llr3|,|llr4|,|llr5|,|llr6|,|llr7|}

A8_1 function;

llr1′

=sgnb(û

₀)*sgn(llr0)*sgn(llr2)*sgn(llr4)*sgn(llr6)*min{|llr0|,|llr2|,|llr4|,|llr6|}+sgn(llr1)*sgn(llr3)*sgn(llr5)*sgn(llr7)*min{|llr1|,|llr3|,|llr7|}

A8_2 function;

temp1=sgnb(û

₀⊕

û

₁)·

[sgn(llr0)·

sgn(llr4)·

min(|llr0|,|llr4|)]+sgn(llr2)·

sgn(llr6)·

min(|llr2|,|llr6|)

temp2=sgnb(û

₁)·

[sgn(llr1)·

sgn(llr5)·

min(|llr1|,|llr5|)]+sgn(llr3)·

sgn(llr7)·

min(|llr3|,|llr7|)

llr2′

=sgn(temp1)·

sgn(temp2)·

min(|temp1|,|temp2|)

A8_3 function;

13. The apparatus of claim 8, wherein the LLR stages further comprise an LLR stage with f and g nodes, which respectively apply the following functions or equivalent functions consistent therewith:

f-function;

llr0′

=sgn(llr0)·

sgn(llr1)·

min(|llr0|,|llr1|)

g-function;

llr1′

=llr1+sgnb(û

₀)·

llr0,

where

û

₀ is an estimated bit value;

llrx are input LLR values;

llrx′

are output LLR values; and

min( ) is minimum.

14. The apparatus of claim 8, wherein the decoder comprises a List decoder.

15. User equipment comprising the apparatus of claim 8.

16. Communication network equipment comprising the apparatus of claim 8.