Method and apparatus for decoding data

• US 7,783,952 B2
• Filed: 09/08/2006
• Issued: 08/24/2010
• Est. Priority Date: 09/08/2006
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Nimbalker, Ajit, Classon, Brian K., Blankenship, Yufei W.
• Primary Examiner(s): Lamarre; Guy J
• Application Number:
  US11/530,211
• Publication Number:
  US 20080072122A1
• Time in Patent Office: 1,446 Days
• Field of Search: 714/755, 714/786, 714/788, 714/762, 714/777
• US Class Current: 714/755
• CPC Class Codes: H03M 13/114 Shuffled, staggered, layered or turbo decoding schedules
• CPC Class Codes: H03M 13/1185 wherein the parity-check matrix comprises a part with a double-diagonal
• CPC Class Codes: H03M 13/1188 wherein in the part with the double-diagonal at least one column has an odd column weight equal or greater than three
• CPC Class Codes: H03M 13/1197 Irregular repeat-accumulate [IRA] codes
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

A method and apparatus for decoding data is provided herein to show how to turbo decode LDPC codes that contain a partial dual diagonal parity-check portion, and how to avoid memory access contentions in such a turbo decoder. During operation, a decoder will receive a signal vector corresponding to information bits and parity bits and separate the received signal vector into two groups, a first group comprising signals corresponding to the information bits and one or more parity bits, a second group comprising a remainder of the parity bits. The first group of received signals is passed to a first decoder and the second group of received signals is passed to a second decoder. The decoders are separated by an interleaver and a deinterleaver. Iterative decoding takes place by passing messages between the decoders, through the interleaver and the deinterleaver, and producing an estimate of the information bits from the output of the first decoder.

Claims

1. A method for estimating an information vector containing information bits at a receiver, the method comprising the steps of:

receiving a signal vector corresponding to information bits and parity bits;

separating the received signal vector into two groups, a first group comprising signals corresponding to the information bits and one or more parity bits, a second group corresponding to a remainder of the parity bits;

passing the first group to a first decoder;

passing the second group to a second decoder;

iteratively decoding by passing messages between the decoders, where the decoders are separated by an interleaver and a de-interleaver; and

producing an estimate of the information vector from the output of the first decoder.

2. The method of claim 1 wherein the first decoder is a repetition decoder.

3. The method of claim 1 wherein the second decoder is a SPC-Accumulator decoder.

4. The method of claim 1 wherein the interleaver and the de-interleaver are contention-free.

5. The method of claim 1 wherein the step of receiving a signal vector corresponding to information bits and parity bits comprises the step of receiving a signal vector corresponding to a codeword of a structured LDPC code using a structured parity-check matrix H with an expansion factor z, a base matrix H_b, and a model matrix H_bm.

6. The method of claim 5 wherein the received signal vector is passed to a decoder comprising one or more copies of repetition decoders, an interleaver, a de-interleaver corresponding to the interleaver, and one or more copies of SPC-Accumulator decoders, where

each repetition decoder has a same repetition factor Q_b obtained from the base matrix H_b, and the output messages of the repetition decoders are sent to the interleaver;

each SPC-Accumulator decoder has a same SPC parameter J_b obtained from the base matrix H_b, and the output messages of the SPC-Accumulator decoders are sent to the de-interleaver;

7. The method of claim 5 wherein the interleaver comprises

a set R_bm that stores a set of shift sizes from the model matrix H_bm for performing cyclic rotation within each message vector, and

a Permuter (ρ

) that is obtained from the base matrix H_b to permute the message vectors.

8. The method of claim 7 wherein

the cyclic shift of each individual message vector is an inter-window shuffling with a shuffle pattern

9. The method of claim 5 wherein each SPC-Accumulator decoder corresponds to an SPC-Accumulator that accumulates to zero.

10. The method of claim 5 wherein z=96 and H_bm=

11. An apparatus for estimating an information vector containing information bits at a receiver, the apparatus comprising:

a receiver receiving a signal vector corresponding to information bits and parity bits;

a channel LLR distributor separating the received signal vector into two groups, a first group comprising signals corresponding to the information bits and one or more parity bits, and a second group corresponding to a remainder of the parity bits;

a first decoder receiving the first group of signals;

a second decoder receiving the second group of signals; and

wherein the first and the second decoders iteratively decode the received signal vector by passing messages between the decoders, where the decoders are separated by an interleaver and a de-interleaver, and wherein the first decoder outputs an estimate of the information vector.

12. The apparatus of claim 11 wherein the first decoder is a repetition decoder.

13. The apparatus of claim 11 wherein the second decoder comprises a SPC-Accumulator decoder.

14. The apparatus of claim 11 wherein the interleaver and the de-interleaver are contention-free.

15. The apparatus of claim 11 wherein the signal vector corresponds to a codeword of a structured LDPC code using a structured parity-check matrix H with an expansion factor z, a base matrix H_b, and a model matrix H_bm.

16. The apparatus of claim 15 further comprising:

a plurality of repetition decoders receiving copies of the first group of received signals; and

a plurality of SPC-Accumulator decoders receiving copies of the second group of received signals, and wherein

each repetition decoder has a same repetition factor Q_b obtained from the base matrix H_b, and the output messages of the repetition decoders are sent to the interleaver;

each SPC-Accumulator decoder has a same SPC parameter J_b obtained from the base matrix H_b, and the output messages of the SPC-Accumulator decoders are sent to the de-interleaver.

17. The apparatus of claim 15 wherein the interleaver comprises

a set R_bm of shift sizes from the model matrix H_bm for performing cyclic rotation within each message vector, and

a Permuter (ρ

) that is obtained from the base matrix H_b to permute the message vectors.

18. The apparatus of claim 17 wherein

the cyclic shift of each individual message vector is an inter-window shuffling with a shuffle pattern

19. The apparatus of claim 15 wherein each SPC-Accumulator decoder corresponds to an SPC-Accumulator that accumulates to zero.

20. The apparatus of claim 15 wherein z=96 and H_bm=