ECC polar coding and list decoding methods and codecs

Patent metadata

Field	Value
Publication number	US-9503126-B2
Application number	US-201313938609-A
Country	US
Kind code	B2
Filing date	Jul 10, 2013
Priority date	Jul 11, 2012
Publication date	Nov 22, 2016
Grant date	Nov 22, 2016

Abstract

A method of decoding data encoded with a polar code and devices that encode data with a polar code. A received word of polar encoded data is decoded following several distinct decoding paths to generate a list of codeword candidates. The decoding paths are successively duplicated and selectively pruned to generate a list of potential decoding paths. A single decoding path among the list of potential decoding paths is selected as the output and a single candidate codeword is thereby identified. In another preferred embodiment, the polar encoded data includes redundancy values in its unfrozen bits. The redundancy values aid the selection of the single decoding path. A preferred device of the invention is a cellular network device, (e.g., a handset) that conducts decoding in accordance with the methods of the invention.

First claim

The invention claimed is:

1. A method of decoding data encoded with a polar code, the method being implemented via code stored on a non-transient medium in a receiver and comprising:
receiving a word of polar encoded data from a channel and conducting decoding of the word by following several distinct decoding paths to generate codeword candidates;
list decoding by successively duplicating and pruning said decoding paths to generate a list of potential decoding paths,
selecting a single decoding path from the list of potential decoding paths and thereby identifying a single codeword output.

2. The method of claim 1 , wherein said duplicating and pruning splits a decoding path into two child paths to be examined for each decision on the value of an unfrozen bit.

3. The method of claim 2 , wherein the list decoding assigns child paths duplicate data structures each time a decoding path splits; each assigned duplicate data structure is flagged as belonging to multiple paths without copying the data structures at the time of assignment; and
a copy of an assigned duplicate data structure is made only when a selected decoding path requires access to an assigned duplicate data structure during decoding.

4. The method of claim 1 , wherein said duplicating and pruning doubles the number of decoding paths at each decoding step, and then performs pruning procedure to discard all but the L best paths.

5. The method of claim 1 , wherein the pruning is performed using an accumulated likelihood of each path.

6. The method of claim 1 , implemented in a cellular network device.

7. The method of claim 1 , wherein the word of polar coded data includes k-r unfrozen bits of k unfrozen bits as data bits and r bits of redundancy data; and
wherein the pruning uses the redundancy data for decoding decisions to prune the list of potential decoding paths.

8. The method of claim 7 , wherein said pruning discards all paths with incorrect cyclic redundancy check values.

9. A method for encoding and decoding data using polar codes, the method being implemented via code stored on a non-transient medium in a receiver and comprising:
reserving k-r unfrozen bits of k unfrozen bits available as data bits;
using the remaining r unfrozen bits to add redundancy to the data bits; and then using said redundancy to aid in the selection of a decoding path from a list of decoding paths generated during the decoding.

10. The method of claim 9 , wherein the redundancy bits are assigned to cyclic redundancy check (CRC) values of the data.

11. The method of claim 10 , wherein all the decoding paths with incorrect cyclic redundancy check values are discarded.

12. The method of claim 9 , implemented in a cellular network device.

13. A polar decoding device for receiving polar coded data from a channel, the decoding device comprising:
means for list decoding the polar coded data; and
means for successively duplicating and pruning decoding paths during decoding.

Assignees

• Univ California

Inventors

• Vardy Alexander
• Tal Ido

Classifications

• H03M13/13 Primary

  Linear codes · CPC title

• H03M13/451

  using a set of candidate code words, e.g. ordered statistics decoding [OSD] · CPC title

• H03M13/09

  Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit · CPC title