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

A method of decoding bits of information, comprising:

• receiving a codeword;
• determining, in a polar decoding tree associated with a code size and a coding rate, a set of internal nodes where one or more non-payload bits are distributed, wherein a distribution of the non-payload bits is 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
• decoding the codeword at least by performing ML decoding on the internal nodes in the set of internal nodes.

An apparatus for encoding bits of information, comprising:

• at least one processor configured to:
• obtain a payload to be transmitted;
• determine, 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;
• form 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
• generate a codeword by encoding the information stream using a Polar code;
• and
• a memory coupled with the at least one processor.

An apparatus for decoding bits of information, comprising:

• at least one processor configured to:
• receive a codeword;
• determine, in a polar decoding tree associated with a code size and a coding rate, a set of internal nodes where one or more non-payload bits are distributed, wherein a distribution of the non-payload bits is 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
• decode the codeword at least by performing ML decoding on the internal nodes in the set of internal nodes;
• and
• a memory coupled with the at least one processor.