List management for parallel operations of polar codes

Patent metadata

Field	Value
Publication number	US-10601450-B2
Application number	US-201815937503-A
Country	US
Kind code	B2
Filing date	Mar 27, 2018
Priority date	Mar 29, 2017
Publication date	Mar 24, 2020
Grant date	Mar 24, 2020

Abstract

Techniques are described to address run-time issues and other considerations of data structure reorganization operations executed while decoding a polar code. A receiving entity (e.g., a user equipment or a base station) partitions an array, or other data structure, into sections. The array is used during a list decoding operation of a polar code. As the array is populated with path elements for candidate paths, each section is organized and a permutation pattern is calculated for each section. Upon identifying a section reorganization event, the array or subsections of the array are reorganized according the permutation patterns determined for each section.

First claim

What is claimed is:

1. A method for wireless communication, comprising:
receiving a codeword over a wireless channel, the codeword being encoded using a polar code;
determining bit-channel metrics for a plurality of bit-channels of the polar code based on the codeword;
partitioning an array of candidate path elements into one or more list sections, the array of candidate path elements comprising a first dimension associated with a list size for decoding of the received codeword and a second dimension associated with a length of the plurality of bit-channels;
performing a list traversal over the plurality of bit-channels based on path metrics derived from the bit-channel metrics to obtain a plurality of candidate paths, the list traversal comprising determining a sectional permutation pattern for each list section, the sectional permutation pattern identifying a nested permutation of the candidate path elements over the each list section based on selecting the list size of candidate paths according to path metrics for each bit-channel of the each list section;
reorganizing the array of candidate path elements based on the sectional permutation patterns such that each of the plurality of candidate paths comprises a vector of the array of candidate path elements aligned in the first dimension; and
outputting at least one of the plurality of candidate paths.

2. The method of claim 1 , wherein the reorganizing the array of candidate path elements comprises:
identifying a section reorganization event that occurs prior to completion of the performing of the list traversal over the plurality of bit-channels; and
reorganizing a first subset of the array of candidate path elements based on a first subset of the sectional permutation patterns.

3. The method of claim 2 , further comprising:
updating a progress index reflecting reorganization of the first subset of the array of candidate path elements;
identifying a second section reorganization event; and
reorganizing a second subset of the array of candidate path elements based on a second subset of the sectional permutation patterns after the progress index.

4. The method of claim 2 , wherein:
the section reorganization event comprises a parity check operation or a bit traversal threshold.

5. The method of claim 1 , wherein:
the reorganizing the array of candidate path elements based on the sectional permutation patterns comprises: reorganizing, based at least in part on a respective sectional permutation pattern of a given list section, the candidate path elements associated with each list section having a lower list section index than the given list section.

6. The method of claim 1 , wherein:
the performing the list traversal comprises: reorganizing, for each bit-channel of a given list section, the candidate path elements within the given list section having a lower bit-channel index based on the selecting of the candidate paths for the each bit-channel.

7. The method of claim 1 , further comprising:
performing an error check operation on the at least one of the plurality of candidate paths.

8. The method of claim 1 , wherein:
the first dimension comprises rows of the array of candidate path elements and the second dimension comprises columns of the array of candidate path elements.

9. The method of claim 1 , wherein:
the determining of at least one bit-channel metric for at least one of the plurality of bit-channels of the polar code is performed after at least one operation of the list traversal.

10. An apparatus for wireless communication, comprising:
means for receiving a codeword over a wireless channel, the codeword being encoded using a polar code;
means for determining bit-channel metrics for a plurality of bit-channels of the polar code based on the codeword;
means for partitioning an array of candidate path elements into one or more list sections, the array of candidate path elements comprising a first dimension associated with a list size for decoding of the received codeword and a second dimension associated with a length of the plurality of bit-channels;
means for performing a list traversal over the plurality of bit-channels based on path metrics derived from the bit-channel metrics to obtain a plurality of candidate paths, the list traversal comprising determining a sectional permutation pattern for each list section, the sectional permutation pattern identifying a nested permutation of the candidate path elements over the each list section based on selecting the list size of candidate paths according to path metrics for each bit-channel of the each list section;
means for reorganizing the array of candidate path elements based on the sectional permutation patterns such that each of the plurality of candidate paths comprises a vector of the array of candidate path elements aligned in the first dimension; and
means for outputting at least one of the plurality of candidate paths.

11. The apparatus of claim 10 , wherein the means for reorganizing the array of candidate path elements:
identifies a section reorganization event that occurs prior to completion of the performing of the list traversal over the plurality of bit-channels; and
reorganizes a first subset of the array of candidate path elements based on a first subset of the sectional permutation patterns.

12. The apparatus of claim 11 , wherein the means for reorganizing the array of candidate path elements:
updates a progress index reflecting reorganization of the first subset of the array of candidate path elements;
identifies a second section reorganization event; and
reorganizes a second subset of the array of candidate path elements based on a second subset of the sectional permutation patterns after the progress index.

13. The apparatus of claim 11 , wherein:
the section reorganization event comprises a parity check operation or a bit traversal threshold.

14. The apparatus of claim 10 , wherein:
the reorganizing the array of candidate path elements based on the sectional permutation patterns comprises: reorganizing, based at least in part on a respective sectional permutation pattern of a given list section, the candidate path elements associated with each list section having a lower list section index than the given list section.

15. The apparatus of claim 10 , wherein:
the performing the list traversal comprises: reorganizing, for each bit-channel of a given list section, the candidate path elements within the given list section having a lower bit-channel index based on the selecting of the candidate paths for the each bit-channel.

16. The apparatus of claim 10 , further comprising:
means for performing an error check operation on the at least one of the plurality of candidate paths.

17. The apparatus of claim 10 , wherein:
the first dimension comprises rows of the array of candidate path elements and the second dimension comprises columns of the array of candidate path elements.

18. The apparatus of claim 10 , wherein:
the determining of at least one bit-channel metric for at least one of the plurality of bit-channels of the polar code is performed after at least one operation of the list traversal.

19. An apparatus for wireless communication, in a system comprising:
a processor;
memory in electronic communication with the processor; and
instructions stored in the memory and operable, when executed by the processor, to cause the apparatus to:
receive a codeword over a wireless channel, the codeword being encoded using a polar code;
determine bit-channe

Assignees

• Qualcomm Inc

Inventors

• Lin Jamie Menjay
• Yang Yang
• Sarkis Gabi
• Cooper Rotem
• Smee John Edward

Classifications

• H03M13/6502

  Reduction of hardware complexity or efficient processing · CPC title

• H03M13/3746 Primary

  with iterative decoding · CPC title

• H04L1/0041

  Arrangements at the transmitter end · CPC title

• H04L1/0057

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

• H03M13/13

  Linear codes · CPC title