Codelucida, Inc.

Commissariat &#xc0; L'&#xc9;nergie Atomique Et Aux &#xc9;nergies Alternatives

Stmicroelectronics S.a.

Cy Cergy Paris Universite

Other

Centre National De La Recherche Scientifique

Ecole Nationale Superieure De L'elecronique Et De Ses Applications (ensea)

Politechnica University of Timisoara

Ecole Nationale Superieure De L'electronique Et Applications(ensea)

David Declercq

Benedict J Reynwar

Shiva Kumar Planjery

Valentin Savin

Bane Vasic

Vamsi Krishna Yella

Kiran Kumar Gunnam

Shashi Kiran Chilappagari

Pascal Urard

Marc P Fossorier

Oana Boncalo

Erbao Li

Adrian Voicila

François Verdier

Ludovic Chandesris

A method and apparatus for decoding quasi-cyclic LDPC codes using a vertical layered iterative message passing algorithm. The algorithm of the method improves the efficiency of the check node update by using one or more additional magnitudes, predicted with predictive magnitude maps, for the computation of messages and update of the check node states. The method allows reducing the computational complexity, as well as the storage requirements, of the processing units in the check node update. Several embodiments for the apparatus are presented, using one or more predictive magnitude maps, targeting significant savings in resource usage and power consumption, while minimizing the impact on the error correction performance loss.

Method and apparatus for vertical layered decoding of quasi-cyclic low-density parity check codes using predictive magnitude maps

This invention presents a method and apparatus for vertical layered finite alphabet iterative decoding of low-density parity-check codes (LDPC) which operate on parity check matrices that consist of blocks of sub-matrices. The iterative decoding involves passing messages between variable nodes and check nodes of the Tanner graph that associated with one or more sub-matrices constitute decoding blocks, and the messages belong to a finite alphabet. Various embodiments for the method and apparatus of the invention are presented that can achieve very high throughputs with low hardware resource usage and power.

Vertical layered finite alphabet iterative decoding

This invention presents a method and the corresponding hardware apparatus for decoding LDPC codes using a vertical layered (VL) iterative message passing algorithm. The invention operates on quasi-cyclic LDPC (QC-LDPC) codes, for which the non-zero circulant permutation matrices (CPMs) are placed at specific locations in the parity-check matrix of the codes, forming concentrated clusters of CPMs. The purpose of the invention is to take advantage of the organization of CPMs in clusters in order to derive a specific hardware architecture, consuming less power than the classical VL decoders. This is achieved by minimizing the number of read and write accesses to the main memories of the design.

Method and apparatus for vertical layered decoding of quasi-cyclic low-density parity check codes built from clusters of circulant permutation matrices

A method and apparatus for encoding low-density parity check codes uses parity check matrices composed of circulant blocks. The apparatus operates on a parity check matrix of a judiciously designed block structure, which permits low cost hardware implementation, and high encoding throughput.

Method and apparatus for encoding quasi-cyclic low-density parity check codes

A polar code decoding method in which a first decoding attempt by successive cancellation is performed and in the case where the decoded frame is erroneous, an ordered list of bit positions to be tested in the frame is generated, the order relation being given by a metric of first error, the value of this metric depending on the reliability of the decision about the bit as well as on the reliability of the decisions about the bits preceding it in the frame. For each of the positions of the list, an inversion of the bit and a decoding of the subsequent bits are undertaken, doing so as long as the list has not been exhausted or the frame has not been decoded without error. In case of failure, a new decoding attempt based on a double-inversion of bits can be envisaged.

Method for decoding a polar code with inversion of unreliable bits

An in-between layer partial syndrome stopping (IBL-PS) criterion for a layered LDPC decoder. The IBL-PS syndrome is obtained by applying the parity checks (H) of a couple of a first layer (r) and a second layer (r+1) on the variables after the first layer has been processed and before the second layer is processed by the decoder, the decoding being stopped if said in-between layer syndrome (s) is satisfied for at least a couple of consecutive layers.

Stopping criterion for decoding Quasi-Cyclic LDPC codes

Building and using sub-sets of configurations sets are provided to compute the check-nodes update by using a particular representation of the input messages, called here-after trellis-EMS (T-EMS). In a main aspect, the system provides a decoding method to compute doutput vectors of a non-binary parity-check (NBPC) equation decoding unit used for LDPC check codes defined in a NB space.

Decoding method and apparatus for non-binary, low-density, parity check codes

A string of K initial symbols is encoded with a code of the parity check type. The K initial symbols belong to a Galois field of order q strictly greater than 2. The code is defined by code characteristics representable by a graph (GRH) comprising N&#x2212;K first nodes (NC), each node satisfying a parity check equation defined on the Galois field of order q, N packets of intermediate nodes (NIT) and NI second nodes (NSS), each intermediate node being linked to a single first node and to several second nodes by way of a connection scheme. The string of K initial symbols is encoded by using the said code characteristics and a string of N encoded symbols is obtained, respectively subdivided into NI sub-symbols belonging respectively to mathematical sets whose orders are less than q, according to a subdivision scheme representative of the connection scheme (&#x3a0;).

Method and device for encoding symbols with a code of the parity check type and corresponding decoding method and device

In this invention, a new class of finite precision multilevel decoders for low-density parity-check (LDPC) codes is presented. These decoders are much lower in complexity compared to the standard belief propagation (BP) decoder. Messages utilized by these decoders are quantized to certain levels based on the number of bits allowed for representation in hardware. A message update function specifically defined as part of the invention, is used to determine the outgoing message at the variable node, and the simple min operation along with modulo 2 sum of signs is used at the check node. A general methodology is provided to obtain the multilevel decoders, which is based on reducing failures due to trapping sets and improving the guaranteed error-correction capability of a code. Hence these decoders improve the iterative decoding process on finite length graphs and have the potential to outperform the standard floating-point BP decoder in the error floor region. The description and apparatus of 3-bit decoders for column-weight three LDPC codes is also presented.

Growing community of inventors

Tucson, AZ, United States of America

David Declercq