METHOD FOR POLAR DECODING WITH DYNAMIC SUCCESSIVE CANCELLATION LIST SIZE AND POLAR DECODER

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 1-th bit is an information bit, calculating (310) a path metric for each of 2*L.sub.i-1 candidate paths at the i-th level, where L.sub.i-1 is an SCL size at the (i−1)-th level and L.sub.0=1; setting (320) an SCL size at the i-th level, L.sub.i, based on L.sub.i-1 and a statistical distribution of the path metrics calculated for the 2*L.sub.i-1 candidate paths; and selecting (330) L.sub.i surviving paths from the 2*L.sub.i-1 candidate paths based on their respective path metrics.

Claims

1. A method for polar decoding a received signal into a number, N, of bits with Successive Cancellation List, SCL, comprising: 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 a path metric for each of 2*L.sub.i-1 candidate paths at the i-th level, where L.sub.i-1 is an SCL size at the (i−1)-th level and L.sub.0=1; setting an SCL size at the i-th level, L.sub.i, based on L.sub.i-1 and a statistical distribution of the path metrics calculated for the 2*L.sub.i-1 candidate paths; and selecting L.sub.i surviving paths from the 2*L.sub.i-1 candidate paths based on their respective path metrics.

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

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

4. The method of claim 2, wherein L.sub.i is set to be larger than L.sub.i-1 only when L.sub.i-1 is smaller than a maximum allowable value of SCL size, and/or L.sub.i is set to be equal to M only when L.sub.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, wherein said calculating the path metric for each of 2*L.sub.i-1 candidate paths comprises, for each of the 2*L.sub.i-1 candidate paths: calculating a Logarithmic Likelihood Ratio, LLR, and calculating the path metric based on the LLR.

7. The method of claim 1, further comprising: when the i-th bit is a frozen bit: setting L.sub.i to be equal to L.sub.i-1; and determining L.sub.i surviving paths for the frozen bit.

8. The method of claim 1, further comprising: applying a Cyclic Redundancy Check, CRC, to each of the L.sub.N surviving paths at the N-th level; and when only one of the L.sub.N surviving paths passes the CRC: determining N decoded bits from the one surviving path; when two or more of the L.sub.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.sub.N surviving paths passes the CRC: determining N decoded bits from one of the L.sub.N surviving paths that has the largest path metric among the L.sub.N surviving paths.

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

10. A polar decoder comprising a processor and a memory, the memory comprising instructions executable by the processor whereby the polar decoder is operative to perform the method according to claim 1.

11. A computer program product comprising a non-transitory computer readable storage medium having computer program instructions stored thereon, the computer program instructions, when executed by a processor in a polar decoder, causing the polar decoder to perform the method according to claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0022] The above and other objects, features and advantages will be more apparent from the following description of embodiments with reference to the figures, in which:

[0023] FIG. 1 is a schematic diagram showing a block diagram of a communication system with polar coding;

[0024] FIG. 2 is a schematic diagram showing a binary decoding tree for SCL decoding;

[0025] FIG. 3 is a flowchart illustrating a method for polar decoding with dynamic SCL size according to an embodiment of the present disclosure;

[0026] FIG. 4 is a block diagram of a polar decoder according to an embodiment of the present disclosure;

[0027] FIG. 5 is a block diagram of a polar decoder according to another embodiment of the present disclosure; and

[0028] FIGS. 6-10 are schematic diagrams showing simulation results of polar decoding according to embodiments of the present disclosure, compared with some conventional polar decoding methods.

DETAILED DESCRIPTION

[0029] In the following, references in the specification to “one embodiment”, “an embodiment”, “an example embodiment” and the like indicate that the embodiment described may include a particular feature, structure, or characteristic, but it is not necessary that every embodiment includes the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to affect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described.

[0030] It shall be understood that although the terms “first” and “second” etc. may be used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another. For example, a first element could be termed a second element, and similarly, a second element could be termed a first element, without departing from the scope of example embodiments. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed terms. The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of example embodiments. As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises”, “comprising”, “has”, “having”, “includes” and/or “including”, when used herein, specify the presence of stated features, elements, and/or components etc., but do not preclude the presence or addition of one or more other features, elements, components and/or combinations thereof.

[0031] In the following description and claims, unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skills in the art to which this disclosure belongs.

[0032] FIG. 3 is a flowchart illustrating a method 300 for polar decoding with dynamic SCL size according to an embodiment of the present disclosure. The method 300 can be performed at a polar decoder, e.g., the polar decoder 133 in FIG. 1, for decoding a received signal into a number, N, of bits. The method 300 can include the following blocks at the i-th level of a binary tree for decoding the i-th bit of the N bits, where 1≤i≤.

[0033] When the i-th bit is an information bit, at block 310, a path metric for each of 2*L.sub.i-1 candidate paths at the i-th level is calculated, where L.sub.i-1 is an SCL size at the (i−1)-th level and L.sub.0=1. In the block 310, for each of the 2*L.sub.i-1 candidate paths, a Logarithmic Likelihood Ratio (LLR) can be calculated and the path metric can be calculated based on the LLR. For example, the LLR and the path metric can be calculated in accordance with Equations (1) and (2) as described above.

[0034] At block 320, an SCL size at the i-th level, L.sub.i, is set based on L.sub.i-1 and a statistical distribution of the path metrics calculated for the 2*L.sub.i-1 candidate paths.

[0035] In the block 320, when a difference (e.g., absolute difference) between the largest and the smallest of the path metrics calculated for the 2*L.sub.i-1 candidate paths is smaller than a first predetermined threshold, Th1, L.sub.i can be set to be larger than L.sub.i-1. For example, let PM.sub.i(l), l=1, 2, . . . , 2*L.sub.i-1, denotes the path metrics calculated for the 2*L.sub.i-1 candidate paths. When the difference between the largest and the smallest of PM.sub.i(l) is sufficiently small (e.g., smaller than Th1), it means that these paths are so close that discarding even the worse candidate path would be risky. In this case, the SCL size can be increased. For example, all the 2*L.sub.i-1 candidate paths can be kept alive, i.e., L.sub.i=2*L.sub.i-1.

[0036] When a difference (e.g., absolute difference) between the largest and the smallest of the M+1 largest path metrics among the path metrics calculated for the 2*L.sub.i-1 candidate paths is larger than a second predetermined threshold, Th2, can be set to be equal to M, where M<L.sub.i-1. That is, when the difference between the largest and the smallest of the M+1 largest path metrics is sufficiently large (e.g., larger than Th2), the 2*L.sub.i-1−M worst candidate paths can be discarded as they are unlikely to be the correct path. In this case, the SCL size can be decreased. For example, M=L.sub.i-1/2.

[0037] Otherwise, the SCL size may remain unchanged, i.e., L.sub.i=L.sub.i-1.

[0038] In an example, a maximum allowable value of SCL size L.sub.max is introduced. L.sub.i is set to be larger than L.sub.i-1 only when L.sub.i-1<L.sub.max. On the other hand, L.sub.i is set to be smaller than L.sub.i-1 (i.e., equal to M) only when L.sub.i-1>1.

[0039] In an example, the first predetermined threshold Th1 can be smaller than the second predetermined threshold Th2, so as to avoid frequent changes in the SCL size. For example, Th1 and Th2 can be 4 and 6, respectively, for a BEC, or 10 and 15, respectively, for an AWGN.

[0040] At block 330, L.sub.i surviving paths are selected from the 2*L.sub.i-1 candidate paths based on their respective path metrics. For example, the L.sub.i candidate paths having the largest path metrics can be selected as the surviving paths.

[0041] Further, when the i-th bit is a frozen bit (e.g., 0), L.sub.i can be set to be equal to L.sub.i-1 and L.sub.i surviving paths (e.g., each associated with bit 0) can be determined for the frozen bit.

[0042] In example, the method 300 may further include: applying a CRC to each of the L.sub.N surviving paths at the N-th level; and when only one of the LN surviving paths passes the CRC: determining N decoded bits from the one surviving path; when two or more of the LN 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 LN surviving paths passes the CRC: determining N decoded bits from one of the LN surviving paths that has the largest path metric among the LN surviving paths.

[0043] Alternatively, the method 300 may further include: determining N decoded bits from one of the L.sub.N surviving paths that has the largest path metric, without applying a CRC.

[0044] Correspondingly to the method 300 as described above, a polar decoder is provided. FIG. 4 is a block diagram of a polar decoder 400 according to an embodiment of the present disclosure.

[0045] As shown in FIG. 4, the polar decoder 400 includes, a calculating unit 410 configured to, 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, calculate a path metric for each of 2*L.sub.i-1 candidate paths at the i-th level, where L.sub.i-1 is an SCL size at the (i−1)-th level and L.sub.0=1. The polar decoder 400 further includes a setting unit 420 configured to set an SCL size at the i-th level, L.sub.i, based on L.sub.i-1 and a statistical distribution of the path metrics calculated for the 2*L.sub.i-1 candidate paths. The polar decoder 400 further includes a selecting unit 430 configured to select L.sub.i surviving paths from the 2*L.sub.i-1 candidate paths based on their respective path metrics.

[0046] In an embodiment, the setting unit 420 can be configured to: set L.sub.i to be larger than L.sub.i-1 when a difference between the largest and the smallest of the path metrics calculated for the 2*L.sub.i-1 candidate paths is smaller than a first predetermined threshold, set L.sub.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.sub.i-1 candidate paths is larger than a second predetermined threshold, where M<L.sub.i-1, and set L.sub.i to be equal to L.sub.i-1 otherwise.

[0047] In an embodiment, the operation of setting L.sub.i to be larger than L.sub.i-1 may include setting L.sub.i=2*L.sub.i-1. The operation of setting L.sub.i to be equal to M may include setting L.sub.i=M=L.sub.i-1/2.

[0048] In an embodiment, L.sub.i can be set to be larger than L.sub.i-1 only when L.sub.i-1 is smaller than a maximum allowable value of SCL size, Lmax, and/or L.sub.i can be set to be equal to M only when L.sub.i-1>1.

[0049] In an embodiment, the first predetermined threshold may be smaller than the second predetermined threshold.

[0050] In an embodiment, the calculating unit 410 can be configured to, for each of the 2*L.sub.i-1 candidate paths: calculate a Logarithmic Likelihood Ratio (LLR) and calculate the path metric based on the LLR.

[0051] In an embodiment, when the i-th bit is a frozen bit, the setting unit 420 can be configured to set L.sub.i to be equal to L.sub.i-1, and the selecting unit 430 can be configured to determine L.sub.i surviving paths for the frozen bit.

[0052] In an embodiment, the polar decoder 400 may further include a decoding unit configured to apply a CRC to each of the L.sub.N surviving paths at the N-th level; and when only one of the LN surviving paths passes the CRC: determine N decoded bits from the one surviving path; when two or more of the LN surviving paths pass the CRC: determine 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 LN surviving paths passes the CRC: determine N decoded bits from one of the LN surviving paths that has the largest path metric among the LN surviving paths.

[0053] In an embodiment, the polar decoder 400 may further include a decoding unit configured to determine N decoded bits from one of the L.sub.N surviving paths that has the largest path metric.

[0054] The units 410˜430 can be implemented as a pure hardware solution or as a combination of software and hardware, e.g., by one or more of: a processor or a micro-processor and adequate software and memory for storing of the software, a Programmable Logic Device (PLD) or other electronic component(s) or processing circuitry configured to perform the actions described above, and illustrated, e.g., in FIG. 3.

[0055] FIG. 5 is a block diagram of a polar coder 500 according to another embodiment of the present disclosure.

[0056] The polar coder 500 includes a processor 510 and a memory 520. The memory 520 contains instructions executable by the processor 510 whereby the polar coder 500 is operative to perform the actions, e.g., of the procedure described earlier in conjunction with FIG. 3. Particularly, the memory 520 contains instructions executable by the processor 510 whereby the polar coder 500 is operative to: 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 a path metric for each of 2*L.sub.i-1 candidate paths at the i-th level, where L.sub.i-1 is an SCL size at the (i−1)-th level and L.sub.0=1; and setting an SCL size at the i-th level, L.sub.i, based on L.sub.i-1 and a statistical distribution of the path metrics calculated for the 2*L.sub.i-1 candidate paths; and selecting L.sub.i surviving paths from the 2*L.sub.i-1 candidate paths based on their respective path metrics.

[0057] In an embodiment, the operation of setting L.sub.i may include: setting L.sub.i to be larger than L.sub.i-1 when a difference between the largest and the smallest of the path metrics calculated for the 2*L.sub.i-1 candidate paths is smaller than a first predetermined threshold, setting L.sub.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.sub.i-1 candidate paths is larger than a second predetermined threshold, where M<L.sub.i-1, and setting L.sub.i to be equal to L.sub.i-1 otherwise.

[0058] In an embodiment, the operation of setting L.sub.i to be larger than L.sub.i-1 may include setting L.sub.i=2*L.sub.i-1. The operation of setting L.sub.i to be equal to M may include setting L.sub.i=M=L.sub.i-1/2.

[0059] In an embodiment, L.sub.i can be set to be larger than L.sub.i-1 only when L.sub.i-1 is smaller than a maximum allowable value of SCL size, and/or L.sub.i can be set to be equal to M only when L.sub.i-1>1.

[0060] In an embodiment, the first predetermined threshold may be smaller than the second predetermined threshold.

[0061] In an embodiment, the operation of calculating the path metric for each of 2*L.sub.i-1 candidate paths may include, for each of the 2*L.sub.i-1 candidate paths: calculating a Logarithmic Likelihood Ratio (LLR) and calculating the path metric based on the LLR.

[0062] In an embodiment, the memory 520 may further contain instructions executable by the processor 510 whereby the polar coder 500 is operative to: when the i-th bit is a frozen bit: set L.sub.i to be equal to L.sub.i-1; and determine L.sub.i surviving paths for the frozen bit.

[0063] In an embodiment, the memory 520 may further contain instructions executable by the processor 510 whereby the polar coder 500 is operative to: apply a CRC to each of the L.sub.N surviving paths at the N-th level; and when only one of the LN surviving paths passes the CRC: determine N decoded bits from the one surviving path; when two or more of the LN surviving paths pass the CRC: determine 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 LN surviving paths passes the CRC: determine N decoded bits from one of the LN surviving paths that has the largest path metric among the LN surviving paths.

[0064] In an embodiment, the memory 520 may further contain instructions executable by the processor 510 whereby the polar coder 500 is operative to: determine N decoded bits from one of the L.sub.N surviving paths that has the largest path metric.

[0065] FIGS. 6-8 show simulation results of running time and Block Error Rate (BLER) versus erasure rates to decode 64-bit (N=64), 128-bit (N=128) and 256-bit (N=256) codewords (Code Rate=1/2) over BECs, respectively. It is assumed that Lmax=8, Th1=4 and Th2=6. It is further assumed that LLR of received bits to be {−1, 0, 1}, where 0 denotes an erasure while 1 and −1 correspond to received 0 and 1 separately. Six polar decoding schemes are simulated: conventional SCL (with fixed SCL size), conventional SCL with CRC, dynamic SCL according to the present disclosure, dynamic SCL according to the present disclosure with CRC, conventional SC, and conventional SC with CRC. As shown in each of FIGS. 6-8, the polar decoding schemes according to the present disclosure (i.e., dynamic SCL and dynamic SCL with CRC) can achieve substantially the same BLER performance as the conventional SCL and conventional SCL with CRC, while only consume less than ⅓ of the running time of the conventional SCL and conventional SCL with CRC. The running time of the dynamic SCL and dynamic SCL with CRC is close to that of the conventional SC and conventional SC with CRC, respectively.

[0066] FIGS. 9-10 show simulation results of running time and BLER versus Eb/N0 to decode 64-bit (N=64) and 256-bit (N=256) codewords (Code Rate=1/2) over AWGN channels, respectively. It is assumed that Lmax=8, Th1=10 and Th2=15. Six polar decoding schemes are simulated: conventional SCL (with fixed SCL size), conventional SCL with CRC, dynamic SCL according to the present disclosure, dynamic SCL according to the present disclosure with CRC, conventional SC, and conventional SC with CRC. As shown in each of FIGS. 9-10, the polar decoding schemes according to the present disclosure (i.e., dynamic SCL and dynamic SCL with CRC) can achieve substantially the same BLER performance as the conventional SCL and conventional SCL with CRC, while only consume significantly less running time than the conventional SCL and conventional SCL with CRC. The running time of the dynamic SCL and dynamic SCL with CRC gets closer to that of the conventional SC and conventional SC with CRC, respectively, as the value of Eb/NO increases.

[0067] The present disclosure also provides at least one computer program product in the form of a non-volatile or volatile memory, e.g., a non-transitory computer readable storage medium, an Electrically Erasable Programmable Read-Only Memory (EEPROM), a flash memory and a hard drive. The computer program product includes a computer program. The computer program includes: code/computer readable instructions, which when executed by the processor 510 causes the polar coder 500 to perform the actions, e.g., of the procedure described earlier in conjunction with FIG. 3.

[0068] The computer program product may be configured as a computer program code structured in computer program modules. The computer program modules could essentially perform the actions of the flow illustrated in FIG. 3.

[0069] The processor may be a single CPU (Central processing unit), but could also comprise two or more processing units. For example, the processor may include general purpose microprocessors; instruction set processors and/or related chips sets and/or special purpose microprocessors such as Application Specific Integrated Circuits (ASICs). The processor may also comprise board memory for caching purposes. The computer program may be carried by a computer program product connected to the processor. The computer program product may comprise a non-transitory computer readable storage medium on which the computer program is stored. For example, the computer program product may be a flash memory, a Random-access memory (RAM), a Read-Only Memory (ROM), or an EEPROM, and the computer program modules described above could in alternative embodiments be distributed on different computer program products in the form of memories.

[0070] The disclosure has been described above with reference to embodiments thereof. It should be understood that various modifications, alternations and additions can be made by those skilled in the art without departing from the spirits and scope of the disclosure. Therefore, the scope of the disclosure is not limited to the above particular embodiments but only defined by the claims as attached.