Back to results
US 11,664,828 B1Granted
Systems and methods for multithreaded successive cancellation list polar decoding
AssigneeApple Inc.
InventorsHadi Afshar, Steve Hengchen Hsu
Life of this patent
Estimating the term…
Abstract
A polar decoder circuit can execute successive cancellation list polar decoding on multiple threads concurrently. An LLR update engine of the polar decoder circuit and a sort engine of the polar decoder circuit can operate concurrently, with the LLR update engine computing updated path metrics for one codeword while the sort engine sorts candidates for one or more other codewords according to path metrics already computed by the LLR update engine. Threads corresponding to different codewords can cycle sequentially between the LLR update engine and the sort engine.
Claims20
A polar decoder comprising:
- a log likelihood ratio (LLR) memory having a plurality of storage areas configured to store LLRs associated with nodes in a binary tree representing a space of possible decoded codewords corresponding to a received codeword, wherein different storage areas store LLRs for different received codewords;
- a multithreaded LLR update engine coupled to the LLR memory and configured to:
- update the LLRs stored in the storage areas of the LLR memory;
- compute path metrics for a plurality of candidate paths through a portion of the binary tree corresponding to a current decoding stage;
- and
- write updated path metrics for the plurality of candidate paths for the current decoding stage to a first set of registers;
- a sort engine coupled to the LLR update engine and having one or more sort stages configured to operate sequentially to sort the plurality of candidate paths from the first set of registers based on the path metrics and to write the sorted candidate paths to a second set of registers,
- wherein the LLR update engine and the sort engine operate iteratively to traverse the binary tree during a series of decoding stages to generate a final list of candidates for a decoded codeword corresponding to a received encoded codeword;
- and
- synchronization logic coupled to the LLR update engine and the sort engine, the synchronization logic configured to generate synchronization signals such that the multithreaded LLR update engine and the one or more sort stages of the sort engine operate concurrently on different threads of a plurality of threads corresponding to different received codewords.
7 more elements
A cellular modem processor comprising:
- a decoder pipeline, the decoder pipeline including a polar decoder circuit, wherein the polar decoder circuit includes:
- a log likelihood ratio (LLR) memory having a plurality of storage areas configured to store LLRs associated with nodes in a binary tree representing a space of possible decoded codewords corresponding to a received codeword, wherein different storage areas store LLRs for different received codewords;
- a multithreaded LLR update engine coupled to the LLR memory and configured to:
- update the LLRs stored in the storage areas of the LLR memory;
- compute path metrics for a plurality of candidate paths through a portion of the binary tree corresponding to a current decoding stage;
- and
- write updated path metrics for the plurality of candidate paths for the current decoding stage to a first set of registers;
- a sort engine coupled to the LLR update engine and having one or more sort stages configured to operate sequentially to sort the plurality of candidate paths from the first set of registers based on the path metrics and to write the sorted candidate paths to a second set of registers,
- wherein the LLR update engine and the sort engine operate iteratively to traverse the binary tree during a series of decoding stages to generate a final list of candidates for a decoded codeword corresponding to a received encoded codeword;
- and
- synchronization logic coupled to the LLR update engine and the sort engine, the synchronization logic configured to generate synchronization signals such that the multithreaded LLR update engine and the one or more sort stages of the sort engine operate concurrently on different threads of a plurality of threads corresponding to different received codewords.
8 more elements
A method of operating a polar decoder circuit having a log likelihood ratio (LLR) update engine and a sort engine having one or more sort stages, the method comprising:
- computing, in the LLR update engine, path metrics for a set of candidate paths for a first codeword;
- concurrently with computing the path metrics, sorting, in the sort engine, respective sets of candidate paths for one or more additional codewords including a second codeword;
- responsive to completion of computing the path metrics for the set of candidate paths for the first codeword and sorting of the set of candidate paths for the one or more additional codewords, advancing the set of candidate paths for the first codeword to the sorting engine and advancing the set of candidate paths for the second codeword to the LLR update engine;
- thereafter
- computing, in the LLR update engine, updated path metrics for an updated set of candidate paths for the second codeword;
- and
- concurrently with computing the updated path metrics, sorting, in the sort engine, a set of candidate paths for one or more additional codewords including the first codeword.
4 more elements
Dependencies are inferred from the claim text.