Apparatus and method for successive cancellation bit-flip decoding of polar code

Patent metadata

Field	Value
Publication number	US-11664827-B2
Application number	US-202117530999-A
Country	US
Kind code	B2
Filing date	Nov 19, 2021
Priority date	Feb 9, 2021
Publication date	May 30, 2023
Grant date	May 30, 2023

Abstract

A polar code decoding apparatus according to an embodiment includes a divider configured to generate a decoding tree in which a plurality of nodes including one or more critical sets for a polar-encoded codeword are formed in a hierarchical structure, and divide the decoding tree into one or more partitions, each partition equally including lowest nodes of the decoding tree, a determiner configured to determine a memory size for storing a primary decoding result based on a specific partition, the specific partition being selected from among the one or more partitions based on the number of critical sets included in each partition, and a decoder configured to decode the codeword primarily by using a successive cancellation (SC) decoding technique.

First claim

What is claimed is:

1. A method of decoding a polar code, comprising:
generating a decoding tree in which a plurality of nodes including critical sets for a polar-encoded codeword are formed in a hierarchical structure, wherein the critical sets represent sets of bits having a probability of occurrence of errors among information bits of the polar-encoded codeword in a successive cancellation-flip (SCF) decoding process;
dividing the decoding tree into one or more partitions, each partition equally including lowest nodes of the decoding tree;
determining a memory size for storing a primary decoding result based on a number of critical sets included in a specific partition, the specific partition being selected from among the one or more partitions based on the number of critical sets included in each partition, wherein the primary decoding result includes information based on at least one of shift operation on bits of the critical sets included in the specific partition; and
decoding, based on the critical sets included in the specific partition, the polar-encoded codeword primarily by using a successive cancellation (SC) decoding technique,
wherein the decoding includes:
obtaining the primary decoding result by performing the decoding of the polar-encoded codeword;
storing at least one of first information corresponding to a first bit of the critical sets and second information corresponding to a second bit of the critical sets in nodes of each of stages of a memory, as information of the primary decoding result for re-decoding, and
performing a cyclic redundancy check (CRC) detection,
wherein in the decoding, a bit with a lowest log likelihood ratio (LLR) value in the polar-encoded codeword is flipped based on the information for re-decoding and re-decoding is performed from the bit with the lowest log likelihood ratio value, when the cyclic redundancy check (CRC) detection fails.

2. The method of claim 1 , wherein the determining of the memory size includes selecting, from among the one or more partitions, a partition including a largest number of the critical sets as the specific partition.

3. The method of claim 1 , wherein the first information is state information about each of stages of the memory for performing successive cancellation decoding when the first bit is re-decoded, and the second information is state information about each of the stages of the memory for performing the successive cancellation decoding when the second bit is re-decoded.

4. The method of claim 1 , wherein the decoding includes storing the first information in a first node of each of the stages of the memory for storing the primary decoding result and storing the second information in a second node of each of the stages of the memory for storing the primary decoding result based on a result of performing a shift operation on each of the first bit and the second bit.

5. The method of claim 4 , wherein the decoding includes storing the second information in the second node when a result of a first shift operation on the first bit is different from a result of a second shift operation on the second bit.

6. The method of claim 5 , wherein the first shift operation is an operation of performing a right shift by as much as the stage of the memory for storing the primary decoding result in which the first information is to be stored, and the second shift operation is an operation for performing a right shift by as much as the stage of the memory storing the primary decoding result in which the second information is to be stored.

7. The method of claim 5 , wherein the decoding includes storing an accumulated value of the result of the first shift operation as the first information in the first node and an accumulated value of the result of the second shift operation as the second information in the second node, based on the result of the first shift operation and the result of the second shift operation.

8. The method of claim 7 , wherein the decoding includes storing the accumulated value of the result of the first shift operation and the accumulated value of the result of the second shift operation by adding, to the first node and the second node, respectively, a preset first value when the result of the first shift operation and the result of the second shift operation are the same, and a preset second value when the result of the first shift operation and the result of the second shift operation are different.

9. A polar code decoding apparatus comprising:
a divider configured to generate a decoding tree in which a plurality of nodes including critical sets for a polar-encoded codeword are formed in a hierarchical structure, and divide the decoding tree into one or more partitions, each partition equally including lowest nodes of the decoding tree, wherein the critical sets represent sets of bits having a probability of occurrence of errors among information bits of the polar-encoded codeword in a successive cancellation-flip (SCF) decoding process;
a determiner configured to determine a memory size for storing a primary decoding result based on a number of critical sets included in a specific partition, the specific partition being selected from among the one or more partitions based on the number of critical sets included in each partition, wherein the primary decoding result includes information based on at least one of shift operation on bits of the critical sets included in the specific partition; and
a decoder configured to decode, based on the critical sets included in the specific partition, the polar-encoded codeword primarily by using a successive cancellation (SC) decoding technique,
wherein the decoder obtains the primary decoding result by performing the decoding of the polar-encoded codeword, stores at least one of first information corresponding to a first bit of the critical sets and second information corresponding to a second bit of the critical sets in nodes of each of stages of a memory, as information of the primary decoding result for re-decoding, and performs a cyclic redundancy check (CRC) detection, and
wherein a bit with a lowest log likelihood ratio (LLR) value in the polar-encoded codeword is flipped based on the information for re-decoding and re-decoding is performed from the bit with the lowest log likelihood ratio value, when the decoder fails the cyclic redundancy check (CRC) detection in the decoding.

10. The polar code decoding apparatus of claim 9 , wherein the determiner selects, from among the one or more partitions, a partition including a largest number of the critical sets as the specific partition.

11. The polar code decoding apparatus of claim 9 , wherein the first information is state information about each of stages of the memory for performing successive cancellation decoding when the first bit is re-decoded, and the second information is state information about each of the stages of the memory for performing the successive cancellation decoding when the second bit is re-decoded.

12. The polar code decoding apparatus of claim 9 , wherein the decoder stores the first information in a first node of each of the stages of the memory for storing the primary decoding result and stores the second information in a second node of each of the stages of the memory for storing the primary decoding result based on a result of performing a shift operation on each of the first bit and the second bit.

13. The polar code decoding apparatus of claim 12 , wherein the decoder stores the second information in the second node when a result of a first shift operation on the first bit is different from a result of a second shift operation on the second bit.

Assignees

• Univ Ajou Ind Academic Coop Found
• Ajou Univ Industry—Academic Cooperation Foundation

Inventors

• Sunwoo Myung Hoon
• Lee U Seok

Classifications

• H03M13/6572

  Implementations using a tree structure, e.g. implementations in which the complexity is reduced by a tree structure from O(n) to O (log(n)) · CPC title

• H03M13/13 Primary

  Linear codes · CPC title

• H03M13/615

  Use of computational or mathematical techniques · CPC title

• H03M13/3753 Primary

  using iteration stopping criteria · CPC title

• H03M13/09

  Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit · CPC title