Reducing the search space of maximum-likelihood decoding for polar codes

Patent metadata

Field	Value
Publication number	US-10340950-B2
Application number	US-201715682387-A
Country	US
Kind code	B2
Filing date	Aug 21, 2017
Priority date	Aug 21, 2017
Publication date	Jul 2, 2019
Grant date	Jul 2, 2019

Abstract

Certain aspects of the present disclosure generally relate to techniques for encoding, generally including obtaining a payload, determining a set of internal nodes to distribute one or more non-payload bits to based, at least in part, on a target maximum likelihood (ML) search space size for internal nodes in a polar decoding tree, a search space size of each of the internal nodes, and an available number of the non-payload bits left to distribute, forming an information stream by interleaving the non-payload bits with bits of the payload by, for each internal node in the set of internal nodes, assigning one or more non-payload bits to one or more leaf nodes in a subtree rooted at that internal node in the set of internal nodes, and generating a codeword by encoding the information stream using a Polar code.

First claim

The invention claimed is:

1. A method of encoding bits of information, comprising:
obtaining a payload to be transmitted;
determining, in a polar decoding tree associated with a code size and a coding rate, a set of internal nodes to distribute one or more non-payload bits to based, at least in part, on a target maximum likelihood (ML) search space size for internal nodes in the polar decoding tree, a search space size of each of the internal nodes in the set of internal nodes, and an available number of the non-payload bits left to distribute;
forming an information stream by interleaving at least one or more of the non-payload bits with bits of the payload, wherein interleaving comprises, for each internal node in the set of internal nodes, assigning one or more non-payload bits to one or more leaf nodes in a subtree rooted at that internal node in the set of internal nodes; and
generating a codeword by encoding the information stream using a Polar code.

2. The method of claim 1 , wherein the one or more non-payload bits reduce the search space size of each of the internal nodes in the set of internal nodes to which the one or more non-payload bits are assigned, and wherein reducing the search space size of each of the internal nodes in the set of internal nodes decreases latency of decoding the codeword.

3. The method of claim 1 , wherein the target ML search space size indicates a threshold at or below which ML decoding can be performed on nodes in the polar decoding tree at a decoder.

4. The method of claim 1 , wherein the one or more non-payload bits comprise at least one of frozen bits, punctured bits, shortened bits, or outer-code bits, wherein outer-code bits comprise one of cyclic redundancy check (CRC) bits, low-density parity check (LDPC) bits, or parity bits.

5. The method of claim 4 , wherein the one or more non-payload bits comprise outer-code bits, and wherein the outer-code bits assigned to the one or more leaf nodes rooted at a first internal node are derived entirely and uniquely from at least one of:
bits that would be decoded before a decoder reaches the first internal node and a remaining number of payload bits in a subcode corresponding to the first internal node.

6. The method of claim 4 , wherein the one or more non-payload bits comprise outer-code bits and only a subset of a total number of outer-code bits are assigned.

7. The method of claim 4 wherein:
the one or more non-payload bits comprise both frozen and outer-code bits; and
wherein assigning comprises:
assigning frozen bits to internal nodes in the set of internal nodes whose subcodes are decoded before a threshold number of payload bits will have been decoded in a decoder; and
assigning outer-code bits to internal nodes whose subcodes are decoded after the threshold number of payload bits.

8. The method of claim 1 , further comprising:
including, in the set of internal nodes, internal nodes of the polar decoding tree whose code rate is greater than zero but less than one; and
excluding, from the set of internal nodes, any internal nodes in the polar decoding tree whose code rate is zero or one.

9. The method of claim 8 , further comprising excluding, from the set of internal nodes, any internal nodes in the polar decoding tree having a rate-one child node.

10. The method of claim 1 , further comprising:
excluding, from the set of internal nodes, any internal node in the polar decoding tree that is rooted at a parent node with a search space size at or below the target ML search space size; and
excluding, from the set of internal nodes, any internal node in the polar decoding tree that is rooted at a parent node that is already included in the set of internal nodes.

11. The method of claim 1 , further comprising:
considering internal nodes of the polar decoding tree for inclusion in the set of internal nodes starting from a root of the polar decoding tree, and proceeding down the polar decoding tree, m levels at a time, where m is an integer greater than or equal to 1;
at each level in the polar decoding tree, sorting the internal nodes in order of increasing effective code rate or increasing number of information bits;
including, in the set of internal nodes, an internal node whose search space size can be reduced to the target ML search space size by assigning one or more of the available number non-payload bits to this internal node; and
excluding, from the set of internal nodes, an internal node whose search space size cannot be reduced to the target ML search space size even if all of the available number non-payload bits are assigned to this internal node.

12. The method of claim 1 , wherein assigning the one or more non-payload bits to the internal nodes in the set of internal nodes comprises:
assigning the one or more non-payload bits to bit indices, in the information stream, corresponding to the one or more leaf nodes of subtrees rooted at the internal nodes in the set of internal nodes.

13. The method of claim 12 , wherein:
the polar decoding tree comprises a plurality of degrees corresponding to levels in the polar decoding tree;
a child node comprises a node having a degree one less than a corresponding parent node; and
leaf nodes comprise degree-zero nodes in the polar decoding tree and the internal nodes are node with a degree greater than zero in the polar decoding tree.

14. The method of claim 12 , wherein the bit indices to which non-payload bits are assigned, correspond to the leaf nodes with the lowest reliabilities in a subtree rooted at that internal node.

15. The method of claim 1 , further comprising determining how many non-payload bits to assign to a first internal node in the set of internal nodes based, at least in part, on the target ML search space size, a search space size of the first internal node, and the available number of the non-payload bits left to assign.

16. The method of claim 15 , wherein:
assigning one or more non-payload bits to the first internal node reduces the size of the search space of the internal node; and
determining how many non-payload bits to assign to the first internal node is based further on a comparison of how many non-payload bits are needed to reduce the size of the search space of the first internal node to the target ML search space size.

17. The method of claim 1 , wherein:
the one or more non-payload bits comprise frozen bits; and
assigning the one or more non-payload bits to the internal nodes in the set of internal nodes comprises:
exchanging information bits associated with the internal nodes in the set of internal nodes with frozen bits.

18. The method of claim 1 , wherein:
the one or more non-payload bits comprise additional frozen bits added to the information stream instead of information bits to reduce a coding rate of the codeword; and
assigning the one or more non-payload bits to the internal nodes in the set of internal nodes comprises replacing information bits associated with the internal nodes in the set of internal nodes with frozen bits.

19. The method of claim 1 , further comprising:
performing rate-matching on the information stream by adding frozen bits to the information stream, wherein assigning the one or more non-payload bits to the internal nodes in the set of internal nodes comprises assigning the added frozen bits to the internal nodes in the set of internal nodes.

20. The method of claim 1 wherein the one or more non-payload bits are only assigned to internal nodes having degree d less than some

Assignees

• Qualcomm Inc

Inventors

• Klein Aaron
• Sridhar Abhinav

Classifications

• H04L1/0065

  Serial concatenated codes · CPC title

• H04L1/0041

  Arrangements at the transmitter end · CPC title

• H03M13/15

  Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes (H03M13/17 takes precedence) · CPC title

• H03M13/05

  using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits {(H03M13/2906 takes precedence)} · CPC title

• H03M13/13

  Linear codes · CPC title