# US 2018/0323809 A1 · Frozen bits based pruning and early termination for polar decoding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0323809 A1
- Document ID: US20180323809A1
- Status: Published application
- Kind: A1
- Application number: 15/967,592
- Filed: 2018-04-30
- Published: 2018-11-08
- Earliest claimed: 2017-05-05
- Assignees: QUALCOMM Incorporated
- Applicants: QUALCOMM Incorporated
- Inventors: Jamie Menjay Lin; Gabi Sarkis; Yang Yang
- Web page: https://patentgrep.com/patent/US20180323809A1

## CPC

- H03M 13/3738: {with judging correct decoding}
- H03M 13/13: Linear codes
- H04L 1/00: Arrangements for detecting or preventing errors in the information received {(correcting synchronisation H04L7/00)}
- H04L 1/0045: {Arrangements at the receiver end}
- H04L 1/0053: {specially adapted for power saving}
- H04L 1/0057: {Block codes (H04L1/0061, H04L1/0064 take precedence)}
- H03M 13/00: Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes (error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C)
- H03M 13/1102: {Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes}
- H03M 13/1108: {Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping}
- H03M 13/151: {using error location or error correction polynomials}
- H03M 13/1575: {Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance}
- H03M 13/2906: {using block codes (H03M13/2957 takes precedence)}
- H03M 13/45: Soft decoding, i.e. using symbol reliability information (H03M13/41 takes precedence)
- H03M 13/451: {using a set of candidate code words, e.g. ordered statistics decoding [OSD]}
- H03M 13/458: {by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result}
- H03M 13/6356: {by repetition or insertion of dummy data, i.e. rate reduction}
- H03M 13/6393: {Rate compatible low-density parity check [LDPC] codes}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Methods, systems, and devices for wireless communication are described. The examples described herein may enable a decoder to determine path metrics for various decoding paths based on identified frozen bit locations of a polar code. The path metric for a decoding path may be based on bit metrics determined for the identified frozen bit locations along the decoding path. Once the path metrics and bit metrics are determined, the decoder may compare these metrics to threshold criteria and determine whether to discard decoding paths based on the comparison. The techniques described herein for discarding decoding paths may allow the decoder to discard, prune, or disqualify certain decoding paths that are unlikely to provide an accurate representation of bits received from another device. Consequently, the decoder may be able to save power by terminating a decoding process early (i.e., early termination) if all paths are discarded, pruned, or disqualified.

## Claims

### Claim 1

A method for wireless communication, comprising:
receiving a candidate codeword via a communication channel;
identifying a decoding hypothesis for decoding the candidate codeword based at least in part on the candidate codeword being encoded using a polar code, the decoding hypothesis associated with a plurality of information bit locations of the polar code corresponding to a plurality of information bits and a plurality of frozen bit locations of the polar code corresponding to a plurality of frozen bits;
performing a decoding process for the candidate codeword based at least in part on the identified decoding hypothesis, the decoding process comprising, for each frozen bit location of at least a subset of the plurality of frozen bit locations:
determining frozen bit path metrics for a set of decoding paths based at least in part on bit metrics for the set of decoding paths for the each frozen bit location and preceding ones of the at least the subset of the plurality of frozen bit locations and independent of bit metrics for the plurality of information bit locations, and
discarding a subset of the set of decoding paths based at least in part on comparisons of the frozen bit path metrics for each of the set of decoding paths to a threshold frozen bit path metric; and
determining whether to process the information bits of the candidate codeword based at least in part on a result of the decoding process.

### Claim 2 (depends on 1)

The method of claim 1, wherein the performing the decoding process further comprises, for the each frozen bit location:
discarding a subset of the set of decoding paths based at least in part on comparisons of the bit metrics for the set of decoding paths for the each frozen bit location to a threshold bit metric.

### Claim 3 (depends on 2)

The method of claim 2, wherein the bit metrics for the set of decoding paths for the each frozen bit location are based at least in part on reliability information for the each frozen bit location or an aggregate of logarithmic-likelihood ratio (LLR) magnitudes for the candidate codeword.

### Claim 4 (depends on 1)

The method of claim 1, wherein the determining the frozen bit path metrics for the set of decoding paths further comprises:
determining the frozen bit path metrics based at least in part on a number of bit locations corresponding to the each frozen bit location and the preceding ones of the at least the subset of the plurality of frozen bit locations, reliability information for bit locations corresponding to the each frozen bit location and the preceding ones of the at least the subset of the plurality of frozen bit locations, or an aggregate of logarithmic-likelihood ratio (LLR) magnitudes for the candidate codeword.

### Claim 5 (depends on 1)

The method of claim 1, wherein, for the each frozen bit location, the frozen bit path metrics are determined based at least in part on a sum of the bit metrics for the each frozen bit location and the preceding ones of the at least the subset of the plurality of frozen bit locations.

### Claim 6 (depends on 1)

The method of claim 1, wherein the performing the decoding process further comprises, for the each frozen bit location:
determining first candidate path metrics for each of the set of decoding paths that are not discarded.

### Claim 7 (depends on 6)

The method of claim 6, wherein the performing the decoding process further comprises, for an information bit location following the each frozen bit location:
determining second candidate path metrics for an extended set of decoding paths based at least in part on the first candidate path metrics and bit metrics for the information bit location; and
selecting a subset of the extended set of decoding paths based at least in part on the second candidate path metrics.

### Claim 8 (depends on 1)

The method of claim 1, wherein the determining whether to process the information bits comprises:
determining that all decoding paths of the set of decoding paths are discarded; and
terminating decoding of the candidate codeword.

### Claim 9 (depends on 1)

The method of claim 1, wherein the determining whether to process the information bits comprises:
determining, subsequent to the decoding process for all of the plurality of frozen bit locations, that at least one decoding path of the set of decoding paths is not discarded;
identifying the information bits based at least in part on the at least one decoding path; and
processing the information bits based at least in part on the identification.

### Claim 10 (depends on 1)

The method of claim 1, wherein the subset of the plurality of frozen bit locations are selected for evaluation based at least in part on the decoding hypothesis or reliability information for the plurality of frozen bit locations.

### Claim 11

A method for wireless communication, comprising:
receiving a candidate codeword having a codeword length via a communication channel;
identifying a decoding hypothesis for decoding the candidate codeword based at least in part on the candidate codeword being encoded using a polar code having a plurality of bit locations, the decoding hypothesis associated with a plurality of information bit locations of the polar code corresponding to a plurality of information bits and a plurality of frozen bit locations of the polar code corresponding to a plurality of frozen bits;
initiating a decoding process for the candidate codeword, the decoding process being performed according to the codeword length and the decoding hypothesis; and
determining whether to terminate the decoding process as having failed to obtain the plurality of information bits based at least in part on evaluating bit metric information associated with a subset of the plurality of bit locations, the subset of the plurality of bit locations selected from the plurality of frozen bit locations based at least in part on the decoding hypothesis.

### Claim 12 (depends on 11)

The method of claim 11, wherein the decoding process comprises successively decoding the plurality of bit locations.

### Claim 13 (depends on 12)

The method of claim 12, wherein the decoding process comprises a successive cancellation (SC) decoding process.

### Claim 14 (depends on 12)

The method of claim 12, wherein the decoding process comprises a successive cancellation list (SCL) decoding process.

### Claim 15

An apparatus for wireless communication, 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 candidate codeword via a communication channel;
identify a decoding hypothesis for decoding the candidate codeword based at least in part on the candidate codeword being encoded using a polar code, the decoding hypothesis associated with a plurality of information bit locations of the polar code corresponding to a plurality of information bits and a plurality of frozen bit locations of the polar code corresponding to a plurality of frozen bits;
perform a decoding process for the candidate codeword based at least in part on the identified decoding hypothesis, the decoding process comprising, for each frozen bit location of at least a subset of the plurality of frozen bit locations:
determine frozen bit path metrics for a set of decoding paths based at least in part on bit metrics for the set of decoding paths for the each frozen bit location and preceding ones of the at least the subset of the plurality of frozen bit locations and independent of bit metrics for the plurality of information bit locations, and
discard a subset of the set of decoding paths based at least in part on comparisons of the frozen bit path metrics for each of the set of decoding paths to a threshold frozen bit path metric; and
determine whether to process the information bits of the candidate codeword based at least in part on a result of the decoding process.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein the instructions are further executable by the processor to cause the apparatus to, for the each frozen bit location:
discard a subset of the set of decoding paths based at least in part on comparisons of the bit metrics for the set of decoding paths for the each frozen bit location to a threshold bit metric.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the bit metrics for the set of decoding paths for the each frozen bit location are based at least in part on reliability information for the each frozen bit location or an aggregate of logarithmic-likelihood ratio (LLR) magnitudes for the candidate codeword.

### Claim 18 (depends on 15)

The apparatus of claim 15, wherein the instructions are further executable by the processor to cause the apparatus to:
determine the frozen bit path metrics based at least in part on a number of bit locations corresponding to the each frozen bit location and the preceding ones of the at least the subset of the plurality of frozen bit locations, reliability information for bit locations corresponding to the each frozen bit location and the preceding ones of the at least the subset of the plurality of frozen bit locations, or an aggregate of logarithmic-likelihood ratio (LLR) magnitudes for the candidate codeword.

### Claim 19 (depends on 15)

The apparatus of claim 15, wherein, for the each frozen bit location, the frozen bit path metrics are determined based at least in part on a sum of the bit metrics for the each frozen bit location and the preceding ones of the at least the subset of the plurality of frozen bit locations.

### Claim 20 (depends on 15)

The apparatus of claim 15, wherein the instructions are further executable by the processor to cause the apparatus to, for the each frozen bit location:
determine first candidate path metrics for each of the set of decoding paths that are not discarded.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein the instructions are further executable by the processor to cause the apparatus to, for an information bit location following the each frozen bit location:
determine second candidate path metrics for an extended set of decoding paths based at least in part on the first candidate path metrics and bit metrics for the information bit location; and
select a subset of the extended set of decoding paths based at least in part on the second candidate path metrics.

### Claim 22 (depends on 15)

The apparatus of claim 15, wherein the instructions are further executable by the processor to cause the apparatus to:
determine that all decoding paths of the set of decoding paths are discarded; and
terminate decoding of the candidate codeword.

### Claim 23 (depends on 15)

The apparatus of claim 15, wherein the instructions are further executable by the processor to cause the apparatus to:
determine, subsequent to the decoding process for all of the plurality of frozen bit locations, that at least one decoding path of the set of decoding paths is not discarded;
identify the information bits based at least in part on the at least one decoding path; and
process the information bits based at least in part on the identification.

### Claim 24 (depends on 15)

The apparatus of claim 15, wherein the subset of the plurality of frozen bit locations are selected for evaluation based at least in part on the decoding hypothesis or reliability information for the plurality of frozen bit locations.

### Claim 25

An apparatus for wireless communication, 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 candidate codeword having a codeword length via a communication channel;
identify a decoding hypothesis for decoding the candidate codeword based at least in part on the candidate codeword being encoded using a polar code having a plurality of bit locations, the decoding hypothesis associated with a plurality of information bit locations of the polar code corresponding to a plurality of information bits and a plurality of frozen bit locations of the polar code corresponding to a plurality of frozen bits;
initiate a decoding process for the candidate codeword, the decoding process being performed according to the codeword length and the decoding hypothesis; and
determine whether to terminate the decoding process as having failed to obtain the plurality of information bits based at least in part on evaluating bit metric information associated with a subset of the plurality of bit locations, the subset of the plurality of bit locations selected from the plurality of frozen bit locations based at least in part on the decoding hypothesis.

### Claim 26 (depends on 25)

The apparatus of claim 25, wherein the decoding process comprises successively decoding the plurality of bit locations.

### Claim 27 (depends on 26)

The apparatus of claim 26, wherein the decoding process comprises a successive cancellation (SC) decoding process.

### Claim 28 (depends on 26)

The apparatus of claim 26, wherein the decoding process comprises a successive cancellation list (SCL) decoding process.