University of California

The Royal Institution for the Advancement of Learning / Mcgill University

Alexander Vardy

Arman Fazeli Chaghooshi

Hanwen Yao

Kuangda Tian

Jack K Wolf

Paul Siegel

Ido Tal

Eitan Yaakobi

Gabi Sarkis

Warren Jeffrey Gross

Scott Kayser

Camille Leroux

Alexandre Raymond

Devices, systems and methods for list decoding of polarization-adjusted convolutional (PAC) codes are described. One example method for improving error correction in a decoder for data in a communication channel includes receiving a noisy codeword, the codeword having been generated using a polarization-adjusted convolutional (PAC) code and provided to the communication channel prior to reception by the decoder, and performing PAC list decoding on the noisy codeword, wherein an encoding operation of the PAC code comprises a convolutional precoding operation that generates one or more dynamically frozen bits, and wherein the PAC list decoding comprises extending, based on the one or more dynamically frozen bits, at least two paths of a plurality of paths in the PAC list decoding differently and independently.

List decoding of polarization-adjusted convolutional codes

Disclosed are devices, systems and methods for polar coding and decoding for correcting deletion and insertion errors caused by a communication channel. One exemplary method for error correction includes receiving a portion of a block of polar-coded symbols that includes d≥2 insertion or deletion symbol errors, the block comprising N symbols, the received portion of the block comprising M symbols; estimating, based on one or more recursive calculations in a successive cancellation decoder (SCD), a location or a value corresponding to each of the d errors; and decoding, based on estimated locations or values, the portion of the block of polar-coded symbols to generate an estimate of information bits that correspond to the block of polar-coded symbols, wherein the SCD comprises at least log(N)+1 layers, each comprising up to dN processing nodes arranged as N groups, each of the N groups comprising up to dprocessing nodes.

Polar coding and decoding for correcting deletion and/or insertion errors

Disclosed are devices, systems and methods for precoding and decoding polar codes using local feedback are described. One example method for improving an error correction capability of a decoder includes receiving a noisy codeword vector of length n, the codeword having been generated based on a concatenation of a convolutional encoding operation and a polar encoding operation and provided to a communication channel prior to reception by the decoder, performing a successive-cancellation decoding operation on the noisy codeword vector to generate a plurality of polar decoded symbols (n), generating a plurality of information symbols (k) by performing a convolutional decoding operation on the plurality of polar decoded symbols, wherein k/n is a rate of the concatenation of the convolutional encoding operation and the polar encoding operation, and performing a bidirectional communication between the successive-cancellation decoding operation and the convolutional decoding operation.

Pre-coding and decoding polar codes using local feedback

Devices, systems and methods for convolutional precoding and decoding of polar codes are disclosed. An example method for error correction in a data processing system includes receiving a noisy codeword, the codeword having been generated based on an outer stream decodable code and an inner polar code and provided to a communication channel or a storage channel prior to reception by the decoder, the stream decodable code characterized by a trellis, and performing, based on the trellis, a list-decoding operation on the noisy codeword vector to generate a plurality of information symbols, the list-decoding operation being configured to traverse through a plurality of states at one or more stages of a plurality of decoding stages.

Convolutional precoding and decoding of polar codes

Disclosed are devices, systems and methods for polar coding and decoding for correcting deletion and insertion errors caused by a communication channel. One exemplary method for error correction includes receiving a portion of a block of polar-coded symbols that includes d&#x2265;2 insertion or deletion symbol errors, the block comprising N symbols, the received portion of the block comprising M symbols; estimating, based on one or more recursive calculations in a successive cancellation decoder (SCD), a location or a value corresponding to each of the d errors; and decoding, based on estimated locations or values, the portion of the block of polar-coded symbols to generate an estimate of information bits that correspond to the block of polar-coded symbols, wherein the SCD comprises at least log(N)+1 layers, each comprising up to dN processing nodes arranged as N groups, each of the N groups comprising up to dprocessing nodes.

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.

ECC polar coding and list decoding methods and codecs

A polar code decoder includes: processing elements each receiving a pair of input values and applying a first or a second predetermined mathematical function depending on a provided function control signal; a first memory that stores at least one of the outputs from processing elements and a plurality of channel values relating to a received polar code to be decoded; a second memory that stores indices of a plurality of frozen bits each representing a bit within an information-bit vector of the polar code being decoded; and a computation block that receives a plurality of inputs from a portion of the processing elements and generates an output that is can be set to a predetermined frozen value or to a calculated value, depending on whether a current index of the bit being decoded is indicated as frozen or not frozen.

Methods and systems for decoding polar codes

The invention provides a family of 2-write WOM-codes, preferred embodiments of which provide improved WOM-rates. Embodiments of the invention provide constructs for linear codes C having a 2-write WOM-code. Embodiments of the invention provide 2-write WOM-codes that improve the best known WOM-rates known to the present inventors at the time of filing with two writes. Preferred WOM-codes are proved to be capacity achieving when the parity check matrix of the linear code C is chosen uniformly at random. Preferred embodiments of the invention provide an electronic device utilizing an efficient coding scheme of WOM-codes with two write capability. The coding method is based on linear binary codes and allows the electronic device to write information to the memory twice before erasing it. This method can be applied for any kind of memory systems, and in particular for flash memories. The method is shown to outperform all well-known codes.

Efficient two write WOM codes, coding methods and devices

The invention provides WOM coding methods and electronic devices with error correcting codes that provide single, double and triple error correction. In one coding, if the code corrects two/three errors, it has two/three parts of redundancy bits. For double error correction, if only one part of the redundancy bit has no errors then it is possible to correct one error. For triple error correction, if only one/two parts of the redundancy bits have no errors then it is possible to correct one/two errors. Codes that correct/detect a single, two and three cell-erasures are provided. A code that has three roots, &#x3b1;, &#x3b1;, &#x3b1;, each of which is a primitive element and where every pair of roots generates a double error correcting code, is provided. Codes and coding utilizing a triple error correcting WOM code that can correct an arbitrary number of errors are provided.

Growing community of inventors

Escondido, CA, United States of America

Alexander Vardy