HARDWARE COMPLEXITY REDUCTION TECHNIQUE FOR SUCCESSIVE CANCELLATION LIST DECODERS

Abstract

A hardware complexity reduction method for successive cancellation list decoders (SCL) is provided. In path pruning stages of an SCL decoding, L paths with smallest path metrics out of 2L candidate paths are chosen as surviving candidate paths as in a conventional SCL algorithm. Moreover, path indexes of L surviving candidate paths are provided in a sorted manner according to indexes at an output of a sorter module. After a path pruning, instead of L-to-1 multiplexers, (L/2+1)-to-1 multiplexers are deployed to perform copying operations of any required elements stored in dedicated registers of the L surviving candidate paths.

Claims

1. (canceled)

2. (canceled)

3. (canceled)

4. (canceled)

5. A successive cancellation list decoder for polar codes, comprising: a sorter module, wherein the sorter module is configured to perform a sorting operation to 2L candidate path metrics to sort L surviving candidate paths according to path indexes of the L surviving candidate paths, wherein the path indexes are assigned to the L surviving candidate paths according to the path indexes of existing paths, wherein the L surviving candidate paths are split from the existing paths, at least one multiplexer bank; wherein a number of L (L/2+1)-to-1 multiplexers are deployed; and the at least one multiplexer bank is configured to perform copying operations of contents of dedicated storage elements, wherein the contents of the dedicated storage elements are used to store intermediate Log-Likelihood Ratio values, decoded bits, partial-sums and pointer registers for each path after a path pruning according to sorted path indexes of the L surviving candidate paths.

6. The successive cancellation list decoder according to claim 5; wherein the sorter module performs the sorting operation of the path indexes of the L surviving candidate paths in an ascending order.

7. The successive cancellation list decoder according to claim 5; wherein the sorter module performs the sorting operation of the path indexes of the L surviving candidate paths in a descending order.

8. The successive cancellation list decoder according to claim 5, wherein the at least one multiplexer bank has the number of L (L/2+1)-to-1 multiplexers configured to copy intermediate Log-Likelihood Ratio values of the existing paths, wherein the existing paths are split to form the L surviving candidate paths.

9. The successive cancellation list decoder according to claim 5, wherein the at least one multiplexer bank has the number of L (L/2+1)-to-1 multiplexers configured to copy the pointer registers of existing paths, wherein the existing paths are split to form the L surviving candidate paths.

10. The successive cancellation list decoder according to claim 5, wherein the at least one multiplexer bank has the number of L (L/2+1)-to-1 multiplexers configured to copy partial sum bits of the existing paths, wherein the existing paths are split to form the L surviving candidate paths.

11. The successive cancellation list decoder according to claim 5, wherein the at least one multiplexer bank has the number of L (L/2+1)-to-1 multiplexers configured to copy the decoded bits of the existing paths, wherein the existing paths are split to form the L surviving candidate paths.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0026] FIG. 1 shows flowchart of decision making procedure in conventional SCL decoding

[0027] FIG. 2 shows flowchart of path management method for conventional SCL decoding

[0028] FIG. 3 shows schematic view of sorter deployed in a conventional SCL decoder

[0029] FIG. 4 shows schematic view of extractor deployed in a conventional SCL decoder

[0030] FIG. 5 shows schematic view of multiplexer bank deployed in a conventional SCL decoder

[0031] FIG. 6 shows schematic view of the sorter module proposed by present invention

[0032] FIG. 7 shows schematic view of the multiplexer bank proposed by present invention

DESCRIPTION OF REFERENCE NUMBERS

[0033] 100. Sorter module [0034] 200. Extractor module [0035] 300. Multiplexer bank [0036] 400. Sorter module [0037] 500. Multiplexer bank

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0038] Hereinafter, the detailed descriptions of the embodiments of the present invention will be given with accompanying drawings.

[0039] SCL decoders keep L paths during decoding to improve the error performance. Paths are formed during the decision-making stages of SC decoding, where a SC decoder makes a hard decision and a SCL decoder splits into alternative decision paths. Decision making procedure in SCL decoding is depicted in FIG. 1.

[0040] In the first step, an existing path is split into two candidate paths. Splitting is performed when an information bit is decoded. Splitting is performed by considering both bit values of ‘0’ and ‘1’ as bit decisions for the two candidate paths.

[0041] In the second step, path metrics are calculated for each candidate path. Path metrics of candidate paths are calculated from path metrics of existing paths from which the candidate paths are formed.

[0042] In the last step, a subset of candidate paths is chosen as surviving candidate paths for further calculations. A maximum number of paths is defined as L. If the number of candidate paths is less than L, all candidate paths survive. If the number of candidate paths exceeds L, a SCL decoder performs path pruning. In path pruning, L paths with smallest path metrics are chosen as surviving candidate paths.

[0043] Each existing path in a SCL decoder has a path metric. Each candidate path in a SCL decoder has a path metric as well. Path metrics of candidate paths are calculated from path metrics of existing paths which the candidate paths are formed from.

[0044] Each existing path in a SCL decoder has intermediate LLR values. Each candidate path in a SCL decoder has intermediate LLR values as well. Intermediate LLR values of candidate paths are the same as those of existing from which the candidate paths are formed.

[0045] Each existing path in a SCL decoder has decoded bits. Each candidate path in a SCL decoder has decoded bits as well. Decoded bits of candidate paths are the same as those of existing paths from which the candidate paths are formed, except for most recently decoded bit.

[0046] Each existing path in a SCL decoder has partial-sum bits. Each candidate path in a SCL decoder has partial-sum bits as well. Partial-sum bits of candidate paths are calculated from those of existing paths from which the candidate paths are formed.

[0047] Because of path pruning, new paths are formed from existing paths. After path pruning, an existing path is either terminated, is duplicated or continues to exist, as shown in FIG. 2. An existing path is terminated if no surviving candidate paths are formed from the existing path. An existing path is duplicated if both candidate paths that are formed from the existing path survive. An existing path continues if only one candidate path that is formed from the existing path survives.

[0048] If an existing path is terminated, its intermediate LLR values, decoded bits and partial-sum bits are discarded. If an existing path is duplicated, its intermediate LLR values, decoded bits, and partial-sum bits are duplicated to the two surviving candidate paths that are formed from this path. If an existing path continues, its intermediate LLR values, decoded bits and partial-sum bits are copied to those of the surviving candidate path that is formed from this path.

[0049] In an example hardware implementation of a conventional SCL decoder, in path pruning, a sorter module (100) sorts the path metrics of 2L candidate paths in an ascending order (FIG. 3). L candidate paths with path metrics which are the first L path metrics at the output of a sorter module (100) are chosen as surviving candidate paths. L surviving candidate path indexes are sorted in ascending order of their path metrics.

[0050] In another example hardware implementation of a conventional SCL decoder, in path pruning, an extractor module (200) extracts L smallest path metrics among 2L path metrics (FIG. 4). L candidate paths with path metrics which are the first L path metrics at the output of an extractor module are chosen as surviving candidate paths. L surviving candidate path indexes are not sorted in ascending order of their path metrics.

[0051] In an example hardware implementation of a conventional SCL decoder, each path has dedicated storage and processing elements. After path pruning, intermediate LLR values, partial-sums and decoded bits of an existing path, from which one or two surviving paths are formed, need to be copied from its dedicated storage elements to the dedicated storage elements that are assigned to the specific surviving path. Copying operation after path pruning is performed according to the ordering of surviving candidate paths. Herein, the ordering depends on whether a sorter or an extractor module is employed to determine surviving candidate paths.

[0052] In an example hardware implementation of a conventional SCL decoder wherein a sorter module (100) is employed, after path pruning, intermediate LLR values, partial-sums and decoded bits of existing paths, from which one or two surviving paths are formed, are copied from their dedicated storage elements to dedicated storage elements assigned to L surviving candidate paths that are sorted in ascending order of their path metrics.

[0053] In another example hardware implementation of a conventional SCL decoder wherein an extractor module (200) is employed, after path pruning, intermediate LLR values, partial-sums and decoded bits of existing paths, from which one or two surviving paths are formed, are copied from their dedicated storage elements to dedicated storage elements assigned to L surviving candidate paths that are sorted according to ordering at the output of extractor module (200).

[0054] In hardware implementations of a conventional SCL decoder, at least one multiplexer bank (300) having a total number of L L-to-1 multiplexers are deployed to copy storage elements of each path after path pruning according to sorted path indexes of L surviving candidate paths (FIG. 5).

[0055] In an example hardware implementation of a conventional SCL decoder, multiplexer bank (300) having a total number of L L-to-1 multiplexers are required to copy intermediate LLR values of existing paths. In an example hardware implementation, input widths of such L-to-1 multiplexers are NQ bits. Herein, Q represents the quantization bit number for intermediate LLR values.

[0056] In another example hardware implementation of a conventional SCL decoder, pointer registers are employed to map intermediate LLR RAM blocks to paths. A multiplexer bank (300) having a total number of L L-to-1 multiplexers is deployed to copy pointer registers of existing paths. In an example hardware implementation, input widths of such L-to-1 multiplexers are log 2L(log 2N−1) bits.

[0057] In yet another example hardware implementation of a conventional SCL decoder, a multiplexer bank (300) having a total number of L L-to-1 multiplexers is deployed to copy partial-sum bits of existing paths. In an example hardware implementation, inputs of such L-to-1 multiplexers are N bits. In another example hardware implementation, input widths of such L-to-1 multiplexers are N/2 bits.

[0058] In another example hardware implementation of a conventional SCL decoder, pointers are employed to map partial-sum RANI blocks to paths. Pointers are stored in registers. A multiplexer bank (300) having a total number of L L-to-1 multiplexers is deployed to copy LLR pointers of existing paths. In an example hardware implementation, input widths of such L-to-1 multiplexers are log 2L(log 2N−1) bits.

[0059] In an example hardware implementation of a conventional SCL decoder, a multiplexer bank (300) having a total number of L L-to-1 multiplexers is deployed to copy decoded bits of existing paths. In an example hardware implementation, input widths of such L-to-1 multiplexers are N bits. In another hardware example implementation, input widths of such L-to-1 multiplexers are K bits.

[0060] In an example hardware implementation of a conventional SCL decoder, intermediate LLR values of each path are stored in RANI blocks. LLR pointers, decoded bits and partial-sums of each path are stored in registers. LLR pointers are stored in L registers of log 2L(log 2N−1) bits. Decoded bits are stored in L registers of N bits. Partial-sums are stored in L registers of N/2 bits. A total number of L L-to-1 multiplexers with input widths of log 2L(log 2N−1) bits are used to copy LLR pointers. A total number of L L-to-1 multiplexers with input widths of N bits are used to copy decoded bits. A total number of L L-to-1 multiplexers with input widths of N/2 bits are used to copy partial-sum bits.

[0061] In the present invention, in path pruning, L paths with smallest path metrics out of 2L candidate paths are chosen as surviving candidate paths. As illustrated in FIG. 6, the path indexes of L surviving candidate paths are provided in a sorted manner according to the indexes at the output of a sorter module (400). Path index sorting of L surviving candidate paths may be in ascending or descending order.

[0062] In the present invention, after path pruning, instead of L-to-1 multiplexers, (L/2+1)-to-1 multiplexers are deployed to perform copying operations of any required elements stored in dedicated registers of paths. Copying operations after path pruning can be performed by a multiplexer bank (500) as depicted in FIG. 7. Reduction in multiplexer inputs is obtained by limiting the paths that can be copied to a specific path after path pruning by sorting the surviving candidate path indexes.

[0063] In an exemplary embodiment, L is equal to 4. Candidate paths 2i−1 and 2i are split from existing path i at decision stages, for 1≤i≤4. Copying operations to path 1 are considered. Surviving candidate path indexes are sorted in ascending order. For the case where, surviving candidate paths are the candidate paths with indexes 5, 6, 7 and 8, copying operations will be performed from existing paths with indexes 3 and 4. Therefore, copying operations to paths 1, 2, 3 and 4 will be performed from paths 3, 3, 4 and 4, respectively. For any other cases, the existing path indexes to be copied to path 1 will be smaller than 3. This means that no copying operations to path 1 can be performed from path 4 in any case. Therefore, copying operations to path 1 can only be performed from paths 1, 2 and 3 in any case.

[0064] In another exemplary embodiment, L is equal to 4. Candidate paths 2i−1 and 2i are split from existing path i at decision stages, for 1≤i≤4. Copying operations to path 1 are considered. Surviving candidate path indexes are sorted in descending order. For the case where, surviving candidate paths are the candidate paths with indexes 4, 3, 2 and 1, copying operations will be performed from existing paths with indexes 1 and 2. Therefore, copying operations to paths 1, 2, 3 and 4 will be performed from paths 2, 2, 1 and 1, respectively. For any other cases, the existing path indexes to be copied to path 1 will be larger than 2. This means that no copying operations to path 1 can be performed from path 1 in any case. Therefore, copying operations to path 1 can only be performed from paths 2, 3 and 4 in any case.

[0065] In an exemplary embodiment, L is equal to 8. Candidate paths 2i−1 and 2i are split from existing path i at decision stages, for 1≤i≤8. Copying operations to path 1 are considered. Surviving candidate path indexes are sorted in ascending order. For the case where surviving candidate paths are the candidate paths with indexes 9, 10, 11, 12, 13, 14, 15 and 16, copying operations will be performed from existing paths with indexes 5, 6, 7 and 8. Therefore, copying operations to paths 1, 2, 3, 4, 5, 6, 7 and 8 will be performed from decoding paths 5, 5, 6, 6, 7, 7, 8 and 8, respectively. In any other cases, the existing path indexes to be copied to path 1 will be smaller than 5. This means that no copying operations to path 1 can be performed from paths 6, 7 and 8 in any case. Therefore, copying operation to path 1 can only be performed from paths 1, 2, 3, 4 and 5 in any case.

[0066] In another exemplary embodiment, L is equal to 8. Candidate paths 2i−1 and 2i are split from existing path i at decision stages, for 1≤i≤8. Copying operations to path 1 are considered. Surviving candidate path indexes are sorted in descending order. For the case where surviving candidate paths are the candidate paths with indexes 8, 7, 6, 5, 4, 3, 2 and 1, copying operations will be performed from existing paths with indexes 1, 2, 3 and 4. Therefore, copying operations to paths 1, 2, 3, 4, 5, 6, 7 and 8 will be performed from decoding paths 4, 4, 3, 3, 2, 2, 1 and 1, respectively. In any other cases, the existing path indexes to be copied to path 1 will be larger than 4. This means that no copying operations to path 1 can be performed from paths 1, 2 and 3 in any case. Therefore, copying operation to path 1 can only be performed from paths 4, 5, 6, 7 and 8 in any case.

[0067] From above examples, path indexes from which copying is possible to a specific path vary with the index of specific path. Thus, instead of using L-to-1 multiplexers, L/2+1 multiplexers can be deployed without any performance loss.

[0068] In an example implementation to validate present invention, a SCL decoder is implemented in a semi-parallel architecture with P=32 processing elements. LLR pointers, partial-sums and decoded bits are stored in registers. LLR pointers are stored in L registers of log 2L(log 2N−1) bits, decoded bits are stored in L registers of N bits, partial-sums are stored in L registers of N/2 bits. Sorting operation is carried out by a bitonic extractor for 2L inputs, serially concantenated with another bitonic sorter for L inputs. Bitonic extractor is employed to extract L surviving candidate paths with smallest path metrics out of 2L candidate paths. Outputs of the first bitonic extractor for 2L inputs are path indexes and path metrics of L surviving candidate paths, which are also inputs of second bitonic sorter for L inputs. Second bitonic sorter is employed to sort L surviving candidate paths according to their path indexes. Implementation results are given in below table:

TABLE-US-00002 Implementation Results (Xilinx Zynq XC7Z100FFG900-2) fop TP Decoder N L LUT FF BRAM [MHz] Latency [Mbps] Conventional 4096 4 98029 27352 20.5 90.9 12928 28.8 Proposed 4096 4 73701 27350 20.5 75.8 12928 24.0 Conventional 4096 8 201590 54371 40.5 40.5 12928 12.8 Proposed 4096 8 151901 54371 40.5 36.6 12928 11.6 Conventional 4096 16 665569 108605 — — 12928 — Proposed 4096 16 524478 108604 — — 12928 —