685 results about "Ldpc decoding" patented technology

The disclosed technology provides a less resource intensive way to decode a parity check code using a modified min-sum algorithm. For a particular parity check constraint that includes n variable nodes, an LDPC decoder can compute soft information for one of the variable nodes based on combinations of soft information from other variable nodes, wherein each combination includes soft information from at most a number d of other variable nodes. In one embodiment, soft information from one of the other variable nodes is used in a combination only if it corresponds to a non-most-likely value for the other variable node.

Techniques for implementing message passing decoders, e.g., LDPC decoders, are described. To facilitate hardware implementation messages are quantized to integer multiples of ½ ln2. Messages are transformed between more compact variable and less compact constraint node message representation formats. The variable node message format allows variable node message operations to be performed through simple additions and subtractions while the constraint node representation allows constraint node message processing to be performed through simple additions and subtractions. Variable and constraint nodes are implemented using an accumulator module, subtractor module and delay pipeline. The accumulator module generates an accumulated message sum. The accumulated message sum for a node is stored and then delayed input messages from the delay pipeline are subtracted there from to generate output messages. The delay pipeline includes a variable delay element making it possible to sequentially perform processing operations corresponding to nodes of different degrees.

Embodiments of the present invention are methods for breaking one or more trapping sets in a near codeword of a failed graph-based decoder, e.g., an LDPC decoder. The methods determine, from among all bit nodes associated with one or more unsatisfied check nodes in the near codeword, which bit nodes, i.e., the suspicious bit nodes or SBNs, are most likely to be erroneous bit nodes. The methods then perform a trial in which the values of one or more SBNs are altered and decoding is re-performed. If the trial does not converge on the decoded correct codeword (DCCW), then other trials are performed until either (i) the decoder converges on the DCCW or (ii) all permitted combinations of SBNs are exhausted. The starting state of a particular trial, and the set of SBNs available to that trial may change depending on the results of previous trials.

Provided is an apparatus and method for transmitting / receiving data in a communication system using a structured Low Density Parity Check (LDPC) code. The transmitter performs structured LDPC coding on input information data using a structured LDPC code, parallel-converts a structured LDPC codeword generated by performing the structured LDPC coding, in units of groups having a predetermined size, and transmits data. The receiver receives a plurality of parallel data streams, serial-converts the received parallel data streams in units of groups having a predetermined size, and performs structured LDPC decoding on the data which was serial-converted group by group, using a structured LDPC code.

An iterative message passing decoder, e.g., an LDPC decoder, operating in conjunction with a soft input-soft output signal processing unit, e.g., an ISI detector, has an error floor performance region influenced by the decoder's sub-optimal message passing nature. Error floor reduction is achieved by a simple message re-initialization mechanism. Decoder edge states, e.g., constraint to variable node messages in decoder memory, are reinitialized, e.g., for an iteration, during the decoding after soft values provided by signal processing unit have improved. During the message re-initialization and for some subsequent amount of iterative decoder processing, extrinsic information fed back from the decoder to the signal processing unit and / or soft values delivered to the decoder from the signal processing unit, in an outer communications loop, is temporarily frozen, e.g., using a switch and a buffer. Then, the outer communications loop is restored as the decoding continues, achieving improved decoding performance.

In one embodiment, an LDPC decoder performs a targeted bit adjustment method to recover a valid codeword after the decoder has failed. In a first stage, a post processor initializes the decoder by saturating LLR values output by the decoder during the last (i.e., failed) iteration to a relatively small value. Then, two-bit trials are performed, wherein LLR values corresponding to two bits of the codeword are adjusted in each trial. Decoding is performed with the adjusted values, and if the number of unsatisfied check nodes exceeds a specified threshold, then a second stage is performed. The post processor initializes the decoder by saturating the LLR values output by the decoder during the last (i.e., failed) iteration of the first stage to a relatively small value. The second stage then performs single-bit adjustment trials, wherein one LLR value corresponding to one bit of the codeword is adjusted in each trial.

Various embodiments of the present invention provide systems and methods for processing information. For example, a decoding system is disclosed that includes a de-interleaver. The de-interleaver is operable to receive an interleaved codeword that includes two or more reduced codewords interleaved together. Further, the de-interleaver is operable to provide a representation of the two or more reduced codewords. The systems also include a decoder that is operable to decode the two or more reduced codewords. In some instances of the aforementioned embodiments, the decoder is an LDPC decoder that is tailored to the size of one or both of the two or more reduced codewords.

In one embodiment, a turbo equalizer is selectively operable in either first or second modes. In the first mode, layered (low-density parity-check (LDPC)) decoding is performed on soft-output values generated by a channel detector, where, for each full local decoder iteration, the updates of one or more layers of the corresponding H-matrix are skipped. If decoding fails to converge on a valid LDPC-encoded codeword and a specified condition is met, then LDPC decoding is performed in a second mode, where the updates of all of the layers of the H-matrix are performed for each full local decoder iteration, including the one or more layers that were previously skipped in the first mode. Skipping one or more layers in the first mode increases throughput of the decoder, while updating all layers in the second mode increases error correction capabilities of the decoder.

Various embodiments of the present invention provide systems and circuits that provide for LDPC decoding and / or error correcting. For example, various embodiments of the present invention provide LDPC decoder circuits that include a soft-input memory, a memory unit, and an arithmetic unit. The arithmetic unit includes a hardware circuit that is selectably operable to perform a row update and a column update. In such cases, a substantial portion of the circuitry of the hardware circuit used to perform the row update is re-used to perform the column update.

An LDPC decoder, applicable to LDPC codes including codes where check nodes within the same group are connected to a common bit node, successively processes groups of check nodes in a particular iteration, including updating bit nodes in that same iteration responsive to messages generated in response to processing a group of check nodes. Within an iteration, the LDPC decoder may also track the number of unresolved parity check equations, and cease iterating or output to an outer block decoder if that number reaches a local minima or standard minimum, falls below a predetermined threshold, or its rate of change falls below a predetermined threshold, indicating a lack of convergence or false convergence condition. The LDPC decoder may also provide a feedback assist to a demodulator. Also, a novel memory configuration may store messages generated by the decoder in the course of check node processing. The decoder may also employ a novel method for generating check node to bit node messages through a prescribed series of pair-wise computations.

Methods and apparatus for implementing memory efficient LDPC decodes are described. In accordance with the invention message information is stored in a compressed state for check node processing operations. The state for a check node is fully updated and then subject to an extraction process to generate check node to variable node messages. The signs of messages received from variable nodes may be stored by the check node processor module of the invention for use in message extraction. The check node processor can process messages in variable node order thereby allowing the variable node processor and check node processor to operate on messages in the same order reducing or eliminating the need to buffer and / or reorder messages passed between check nodes and variable nodes. Graph structures which allow check node processing on one graph iteration to proceed before the previous graph iteration has been completed are also described.

Disclosed herein is a receiving apparatus including a reception device configured to receive a code sequence coded in LDPC (Low Density Parity Check) and punctured at least partially as a target to be decoded; and an LDPC decoding device configured to perform a punctured matrix transform process including a first and a second process on an original parity check matrix noted to have punctured bits or symbols and used in the LDPC coding. The LDPC decoding device further performs the first process to carry out Galois field addition operations on those rows of the original parity check matrix to set the non-zero elements to zero. The LDPC decoding device further performs the second process to delete the columns rid of the non-zero elements. The LDPC decoding device uses the matrix resulting from the process as the parity check matrix for performing an LDPC decoding process on the code sequence.

An LDPC based TDS-OFDM receiver for demodulating an LDPC encoded TDS-OFDM modulated RF signal downconverted to an IF signal includes a synchronization block, an equalization block, an OFDM demodulation block and a FEC decoder block. The synchronization block generates a baseband signal from a digitized IF signal and performs correlation of a PN sequence in a signal frame of the received RF signal with a corresponding locally generated PN sequence to provide signals for performing carrier recovery, timing recovery and parameters for channel estimation. The equalization block performs channel estimation and channel equalization. The OFDM demodulation block performs demodulation on the baseband signal to recover OFDM symbols and converts the OFDM symbols to frequency domain. The FEC decoder block includes an LDPC decoder for decoding the OFDM symbols based on the LDPC code to generate a digital output signal indicative of the data content of the RF signal.

A memory system having a memory card configured to store frame data composed of a plurality of pieces of sector data and a host configured to send and receive the frame data to and from the memory card, the memory card includes: an ECC1 decoder configured to perform BCH decoding processing with a hard decision code on a sector data basis; an ECC2 decoder configured to perform LDPC decoding processing with an LDPC code on a frame data basis; a sector error flag section configured to store information about presence or absence of error data in the BCH decoding processing; and an ECC control section configured to perform, in the LDPC decoding processing, control of increasing a reliability of sector data containing no error data based on the information in the sector error flag section.

This disclosure relates generally to low power data decoding, and more particularly to low power iterative decoders for data encoded with a low-density parity check (LDPC) encoder. Systems and methods are disclosed in which a low-power syndrome check may be performed in the first iteration or part of the first iteration during the process of decoding a LDPC code in an LDPC decoder. Systems and methods are also disclosed in which a control over the precision of messages sent or received and / or a change in the scaling of these messages may be implemented in the LDPC decoder. The low-power techniques described herein may reduce power consumption without a substantial decrease in performance of the applications that make use of LDPC codes or the devices that make use of low-power LDPC decoders.

A receiving apparatus includes: an LDPC decoding device configured such that when an LDPC-coded data signal, LDPC representing Low Density Parity Check, and an LDPC-coded transmission control signal are transmitted in multiplexed fashion, the LDPC decoding device can decode both the data signal and the transmission control signal; a holding device configured to be located upstream of the LDPC decoding device and to hold at least the transmission control signal upon receipt of the data signal and the transmission control signal; and a control device configured to control the LDPC decoding device to decode the data signal while the transmission control signal is being accumulated in the holding device and to interrupt the current decoding so as to control the LDPC decoding device to decode the transmission control signal when the transmission control signal has been accumulated in the holding device.

Various embodiments of the present invention provide systems and methods for decoding encoded information. For example, a method for post processing error correction in a decoder system is disclosed. The method includes receiving and iteratively decoding a soft input to generate a hard output associated with the soft input. The method further includes post processing when a plurality of parity checks fail. At least one bit of the hard output is identified as being potentially incorrect. The identified bit is modified, and the plurality of parity checks is thereafter repeated.

The present disclosure relates generally to data decoding, and more particularly to non-binary iterative decoders. Non-binary LDPC codes and LDPC decoders that may be used to decode non-binary LDPC codes are disclosed. Systems and methods are also disclosed that compute messages related to non-binary LDPC codes, in a LLRV form and in a metric vector form and to process these messages in non-binary LDPC decoders. Systems and methods are additionally disclosed that convert messages between the LLRV form and the metric vector form. The implementation and use of non-binary low density parity check code decoders, the computation of messages in the LLRV and metric vector forms, and the use of message conversion systems and methods, according to this disclosure, may provide increased information relating groups of codeword bits, increased computational efficiency, and improved application performance.

Configurable permutators in an LDPC decoder are provided. A partially-parallel architecture combined with the proposed permutators is used to mitigate the increase in implementation complexity for the multi-mode function. To overcome the difficulty in efficient implementation of a high-throughput decoder, the variable nodes are partitioned into several groups, and each group is processed sequentially in order to shorten the critical-path delay and, hence, increase the maximum operating frequency. In addition, shuffled message-passing decoding can be adopted in decoders according to the invention to increase the convergence speed, which reduces the number of iterations required to achieve a given bit-error-rate performance.

This disclosure relates generally to data decoding, and more particularly to iterative decoders for data encoded with a low-density parity check (LDPC) encoder. LDPC decoders are disclosed that use reduced-complexity circular shifters that may be used to decode predefined or designed QC-LDPC codes. In addition, methods to design codes which may have particular LDPC code performance capabilities and which may operate with such decoders using reduced-complexity circular shifters are provided. The generation of quasi-cyclic low density parity check codes and the use of circular shifters by LDPC decoders, may be done in such a way as to provide increased computational efficiency, decreased routing congestion, easier timing closure, and improved application performance.

Provided are an LDPC encoder and decoder, and LDPC encoding and decoding methods. The LDPC encoder includes: a code generating circuit that includes a memory storing a first parity check matrix and sums a first row which is at least one row of the first parity check matrix and a second row which is at least one of the remaining rows of the first parity check matrix to output a second parity check matrix; and an encoding circuit receiving the second parity check matrix and an information word to output an LDPC-encoded code word. Also the LDPC decoder includes: a code generating circuit including a memory which stores a first parity check matrix and summing a first row which is at least one row of the first parity check matrix and a second row which is at least one of the remaining rows of the first parity check matrix to output a second parity check matrix; and a decoding circuit receiving the second parity check matrix and a code word to output an LDPC-decoded information word.

Decoding LDPC (Low Density Parity Check) code with new operators based on min* operator. New approximate operators are provided that may be employed to assist in calculating one or a minimum value (or a maximum value) when decoding various coded signals. In the context of LDPC decoding that involves both bit node processing and check node processing, either of these new operators (i.e., the min† (min-dagger) operator or the min′ (min-prime) operator) may be employed to perform the check node processing that involves updating the edge messages with respect to the check nodes. Either of these new operators, min† operator or min′ operator, is shown herein to be a better approximate operator to the min** operator.

As a result of transmitting a low-density parity-check (LDPC) codeword (b) having a number (N) of codeword bits consisting of K information bits and N parity bits, for the received An LDPC decoder for decoding a codeword (Y), comprising: a memory for receiving codeword bits of a noisy codeword (Y), storing the codeword bits from the received noisy codeword (Y) and from The a priori estimate (Qv) of the predetermined value of the predetermined parameter of the communication channel; the generalized check node processing unit, iteratively calculates the messages on the edge of the bipartite graph according to the serial scheduling, and in each iteration, the check for the bipartite graph Node (C), all adjacent variable nodes (V) connected to the check node (C), calculate the input message (Qvc) from the adjacent variable node (V) to the check node (C) and from Output message (RCV) from a check node (C) to a neighboring variable node (V).

In one embodiment, a signal-processing receiver has an upstream processor and a low-density parity-check (LDPC) decoder for decoding LDPC-encoded codewords. The upstream processor generates a soft-output value for each bit of the received codewords. The LDPC decoder is implemented to process the soft-output values without having to wait until all of the soft-output values are generated for the current codeword. Further, the LDPC code used to encode the codewords is arranged to support such processing. By processing the soft-output values without having to wait until all of the soft-output values are generated for the current codeword, receivers of the present invention may have a lower latency and higher throughput than prior-art receivers that wait until all of the soft-output values are generated prior to performing LDPC decoding. In another embodiment, the LDPC decoder processes the soft-output values as soon as, and in the order that, they are generated.

Efficient design to implement LDPC decoder. The efficient design presented herein provides for a solution that is much easier, smaller, and has less complexity than other possible solutions. The use of a ping-pong memory structure (or pseudo-dual port memory structure) in conjunction with a metric generator near the decoder's front end allows parallel bit / check node processing. An intelligently operating barrel shifter operates with a message passing memory that is operable to store updated edges messages with respect to check nodes as well as updated edges messages with respect to bit nodes. Using an efficient addressing scheme allows the same memory structure to store the two types of edges messages with respect to bit nodes: (1) corresponding to information bits and (2) corresponding to parity bits. In addition, an intelligently designed hardware macro block may be instantiated a number of times into the decoder design to support ever greater design efficiency.

A non-volatile memory controller for a solid state drive includes a soft-decision LDPC decoder. The soft-decision LDPC decoder includes a probability generation module. A processor reads collected statistics collated from decoded frames and tunes the performance of the soft-decision LDPC decoder performance. Additional parameters may also be taken into account, such as the scramble seed and the type of non-volatile memory. An asymmetry in errors may also be detected and provided to a hard-decision LDPC decoder to adjust its performance.

The invention relates to low density parity check decoding. A method for decoding an encoded data block is described. Decoding is performed in a pipelined manner using a layered belief propagation technique and scalable resources, which are configurable to accommodate at least two codeword lengths and at least two code rates. A computer program product, apparatus and device are also described.

Various embodiments of the present invention are related to methods and apparatuses for decoding data, and more particularly to methods and apparatuses for multi-level layered LDPC decoding with out-of-order processing.