Method for polar decoding with dynamic successive cancellation list size and polar decoder

Patent metadata

Field	Value
Publication number	US-11777533-B2
Application number	US-201817297012-A
Country	US
Kind code	B2
Filing date	Nov 27, 2018
Priority date	Nov 27, 2018
Publication date	Oct 3, 2023
Grant date	Oct 3, 2023

Abstract

It provides a method (300) for polar decoding a received signal into a number, N, of bits with Successive Cancellation List, SCL. The method (300) includes: at the i-th level of a binary tree for decoding the i-th bit of the N bits, where 1≤i≤N: when the i-th bit is an information bit, calculating (310) a path metric for each of 2*Li-1 candidate paths at the i-th level, where Li-1 is an SCL size at the (i−1)-th level and L0=1; setting (320) an SCL size at the i-th level, Li, based on Li-1 and a statistical distribution of the path metrics calculated for the 2*Li-1 candidate paths; and selecting (330) Li surviving paths from the 2*Li-1 candidate paths based on their respective path metrics.

First claim

The invention claimed is:

1. A method performed by a polar decoder for polar decoding the method comprising:
receiving, from a demodulator, a demodulated radio signal; and
decoding the demodulated radio signal into a number, N, of bits with Successive Cancellation List by:
determining, by a processor of the polar decoder, at the i-th level of a binary tree for decoding the i-th bit of the N bits, where 1≤i≤N, and when the i-th bit is an information bit by:
calculating, by the processor, a path metric for each of 2*L i-1 candidate paths at the i-th level, where L i-1 is an SCL size at the (i−1)-th level and L 0 =1, the calculating the path metric for each of 2*L i-1 candidate paths comprises, for each of the 2*L i-1 candidate paths: calculating a Logarithmic Likelihood Ratio, LLR, and calculating, by the processor, the path metric based on the LLR;
setting, by the processor, an SCL size at the i-th level, L i , based on and a statistical distribution of the path metrics calculated for the 2*L i-1 candidate paths; and
selecting, by the processor, L i surviving paths from the 2*L i-1 candidate paths based on their respective path metrics;
determining a difference between the largest and the smallest of the path metrics calculated for the 2*L i-1 candidate paths, and dynamically setting L i based on the difference; and
when the i-th bit is a frozen bit:
setting, by the processor, L i to be equal to L i-1 and determining Li surviving paths for the frozen bit.

2. The method of claim 1 , wherein said setting L i comprises:
setting L i to be larger than L i-1 when the difference between the largest and the smallest of the path metrics calculated for the 2*L i-1 candidate paths is smaller than a first predetermined threshold,
setting L i to be equal to M when a difference between the largest and the smallest of the M+1 largest path metrics among the path metrics calculated for the 2*L i-1 candidate paths is larger than a second predetermined threshold, where M<L i-1 , and
setting L i to be equal to L i-1 otherwise.

3. The method of claim 2 , wherein
setting L i to be larger than L i-1 comprises setting L i =2*L i-1 ; and/or
setting L i to be equal to M comprises setting L i =M=L i-1 /2.

4. The method of claim 2 , wherein L i is set to be larger than L i-1 only when L i-1 is smaller than a maximum allowable value of SCL size, and/or L i is set to be equal to M only when L i-1 >1.

5. The method of claim 2 , wherein the first predetermined threshold is smaller than the second predetermined threshold.

6. The method of claim 1 , further comprising:
applying a Cyclic Redundancy Check, CRC, to each of the LN surviving paths at the N-th level; and
when only one of the L N surviving paths passes the CRC:
determining N decoded bits from the one surviving path;

when two or more of the L N surviving paths pass the CRC:
determining N decoded bits from one of the two or more surviving paths that has the largest path metric among the two or more surviving paths; or

when none of the L N surviving paths passes the CRC:
determining N decoded bits from one of the L N surviving paths that has the largest path metric among the L N surviving paths.

7. The method of claim 1 , further comprising:
determining N decoded bits from one of the L N surviving paths that has the largest path metric.

8. A polar decoder comprising:
a processor; and
memory, the memory including instructions executable by the processor whereby the polar decoder is configured to perform a method for polar decoding a demodulated radio signal received from a demodulator into a number, N, of bits with Successive Cancellation List, SCL by:
determining at the i-th level of a binary tree for decoding the i-th bit of the N bits, where 1≤i≤N, and when the i-th bit is an information bit by:
calculating a path metric for each of 2*L i-1 candidate paths at the i-th level, where L i-1 is an SCL size at the (i−1)-th level and L 0 =1, the calculating the path metric for each of 2*L i-1 candidate paths comprises, for each of the 2*L i-1 candidate paths: calculating a Logarithmic Likelihood Ratio, LLR, and calculating the path metric based on the LLR;
setting an SCL size at the i-th level, L i , based on L i-1 and a statistical distribution of the path metrics calculated for the 2*L i-1 candidate paths; and
selecting L i surviving paths from the 2*L i-1 candidate paths based on their respective path metrics;
determining a difference between the largest and the smallest of the path metrics calculated for the 2*L i-1 candidate paths, and dynamically setting L i based on the difference; and
when the i-th bit is a frozen bit:
setting L i to be equal to L i-1 and determining Li surviving paths for the frozen bit.

9. A computer program product comprising a non-transitory computer readable storage medium having computer program instructions stored thereon, the computer program instructions comprising:
when executed by a processor in a polar decoder, causing the polar decoder to perform a method for polar decoding a demodulated radio signal received from a demodulator into a number, N, of bits with Successive Cancellation List, SCL, the method including:
determining at the i-th level of a binary tree for decoding the i-th bit of the N bits, where 1≤i≤N, and when the i-th bit is an information bit by:
calculating a path metric for each of 2*L i-1 candidate paths at the i-th level, where L i-1 is an SCL size at the (i−1)-th level and L 0 =1, the calculating the path metric for each of 2*L i-1 candidate paths comprises, for each of the 2*L i-1 candidate paths: calculating a Logarithmic Likelihood Ratio, LLR, and calculating the path metric based on the LLR;
setting an SCL size at the i-th level, L i , based on L i-1 and a statistical distribution of the path metrics calculated for the 2*L i-1 candidate paths; and
selecting L i surviving paths from the 2*L i-1 candidate paths based on their respective path metrics;
determining a difference between the largest and the smallest of the path metrics calculated for the 2*L i-1 candidate paths, and dynamically setting L i based on the difference; and
when the i-th bit is a frozen bit:
setting L i to be equal to L i-1 and determining Li surviving paths for the frozen bit.

Assignees

• Ericsson Telefon Ab L M
• Telefonaktiebolagget Lm Ericsson Publ

Inventors

• Feng Ang
• Xie Ailing
• Zhang Yushi

Classifications

• H03M13/6572 Primary

  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/09

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

• H03M13/1111

  Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms · CPC title

• H03M13/3927

  Log-Likelihood Ratio [LLR] computation by combination of forward and backward metrics into LLRs · CPC title

• H03M13/4161

  implementing path management · CPC title