Efficient survivor memory architecture for successive cancellation list decoding of channel polarization codes

Patent metadata

Field	Value
Publication number	US-10523367-B2
Application number	US-201715680661-A
Country	US
Kind code	B2
Filing date	Aug 18, 2017
Priority date	Aug 18, 2017
Publication date	Dec 31, 2019
Grant date	Dec 31, 2019

Abstract

A method of storing survivor data generated while decoding channel polarization codes in a memory module includes setting a list size that corresponds to a number of decoder units used to decode the channel polarization codes, inputting a stream of input bits to the decoder units, and sequentially decoding the input bits. Each input bit is decoded using all previous input bits decoded before the each input bit. The method further includes selecting a plurality of survivor bits from among the decoded input bits, and storing the selected survivor bits in the memory module in a binary tree configuration. The number of edges in each level of the binary tree configuration does not exceed the list size.

First claim

What is claimed is:

1. A method of storing survivor data generated while decoding channel polarization codes in a memory module, comprising:
setting a list size, by a processor, wherein the list size corresponds to a number of decoder units used to decode the channel polarization codes;
inputting, under control of the processor, a stream of input bits to the decoder units;
sequentially decoding the input bits, by the decoder units, wherein each input bit is decoded using all previous input bits decoded before the each input bit;
selecting, by the processor, a plurality of survivor bits from among the decoded input bits; and
storing, under control of the processor, the selected survivor bits in the memory module in a binary tree configuration, wherein a number of edges in each level of the binary tree configuration does not exceed the list size.

2. The method of claim 1 , wherein the input bits are sequentially decoded using a list successive cancellation decoding technique.

3. The method of claim 2 , wherein sequentially decoding the input bits using the list successive cancellation decoding technique comprises:
computing a plurality of intermediate values, wherein the intermediate values are computed by decoding the each input bit based on a plurality of guesses of the values of the previous input bits decoded before the each input bit, wherein each guess corresponds to a bit value being equal to 0 or being equal to 1.

4. The method of claim 3 , further comprising:
selecting a plurality of most probable guesses from among the plurality of guesses using a log-likelihood ratio (LLR) technique;
retaining the selected most probable guesses in the memory module; and
discarding the guesses from among the plurality of guesses that are not selected as the most probable guesses.

5. The method of claim 3 , wherein storing the selected survivor bits in the memory module in the binary tree configuration comprises:
comparing a first group of intermediate values from among the plurality of intermediate values with a second group of intermediate values from among the plurality of intermediate values,
wherein the first and second groups are separated into subgroups, each subgroup corresponding to intermediate values obtained during one of a plurality of stages of the sequential decoding process,
wherein the comparison is made on a stage-by-stage basis,
wherein each stage corresponds to one of the levels of the binary tree configuration; and
generating the edges in each of the levels of the binary tree configuration based on the comparison result.

6. The method of claim 5 , wherein generating the edges in each of the levels of the binary tree configuration based on the comparison result comprises:
comparing intermediate values from a subgroup of the first group with corresponding intermediate values from a subgroup of the second group;
generating only a left edge at a vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 1 and an intermediate value in the subgroup of the second group that is equal to 0;
generating only a right edge at the vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 0 and an intermediate value in the subgroup of the second group that is equal to 1;
generating both the left edge and the right edge at the vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 1 and an intermediate value in the subgroup of the second group that is equal to 1; and
generating neither the left edge nor the right edge at the vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 0 and an intermediate value in the subgroup of the second group that is equal to 0,
wherein the vertex corresponds to the compared intermediate values.

7. The method of claim 6 , wherein the left edges represent a value of 0 and the right edges represent a value of 1.

8. The method of claim 6 , wherein the left edges represent a value of 1 and the right edges represent a value of 0.

9. The method of claim 5 , wherein generating the edges in each of the levels of the binary tree configuration based on the comparison result comprises:
comparing intermediate values from a subgroup of the first group with corresponding intermediate values from a subgroup of the second group;
generating only a left edge at a vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 0 and an intermediate value in the subgroup of the second group that is equal to 1;
generating only a right edge at the vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 1 and an intermediate value in the subgroup of the second group that is equal to 0;
generating both the left edge and the right edge at the vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 1 and an intermediate value in the subgroup of the second group that is equal to 1; and
generating neither the left edge nor the right edge at the vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 0 and an intermediate value in the subgroup of the second group that is equal to 0,
wherein the vertex corresponds to the compared intermediate values.

10. The method of claim 9 , wherein the left edges represent a value of 0 and the right edges represent a value of 1.

11. The method of claim 9 , wherein the left edges represent a value of 1 and the right edges represent a value of 0.

12. The method of claim 5 , wherein generating the edges in each of the levels of the binary tree configuration based on the comparison result comprises:
comparing intermediate values from a subgroup of the first group with corresponding intermediate values from a subgroup of the second group;
generating only a left edge at a vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 1 and an intermediate value in the subgroup of the second group that is equal to 0;
generating only a right edge at the vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 0 and an intermediate value in the subgroup of the second group that is equal to 1;
generating both the left edge and the right edge at the vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 0 and an intermediate value in the subgroup of the second group that is equal to 0; and
generating neither the left edge nor the right edge at the vertex when the compared intermediate values include an intermediate value in the subgroup of the first group that is equal to 1 and an intermediate value in the subgroup of the second group that is equal to 1,
wherein the vertex corresponds to the compared intermediate values.

13. The method of claim 5 , wherein generating the edges in each of the levels of the binary tree configuration based on the comparison result comprises:
comparing intermediate values from a subgroup of the first group with corresponding intermediate values from a subgroup of the second group;
generating only a left edge at a vertex when the compared intermediate values include an intermediate value in the subgroup of the fir

Assignees

• Samsung Electronics Co Ltd

Inventors

• Hof Eran
• Twitto Moshe
• Kong Jun Jin

Classifications

• H04L1/0054

  Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms · CPC title

• H04L1/0057

  Block codes (H04L1/0061, H04L1/0064 take precedence) · CPC title

• H03M13/3746

  with iterative decoding · CPC title

• H04L1/0058 Primary

  Block-coded modulation · CPC title

• H03M13/458

  by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result · CPC title