Serial concatenation of interleaved convolutional codes forming turbo-like codes

DC CAFC

US 7,421,032 B2
Filed: 10/03/2006
Issued: 09/02/2008
Est. Priority Date: 05/18/2000
Status: Expired due to Term

- Alert
- Pin

Associated Cases

Associated Defendants

First Claim

Patent Images

1. A method comprising:

receiving a collection of message bits having a first sequence in a source data stream;

generating a sequence of parity bits, wherein each parity bit “

x_j”

in the sequence is in accordance with the formula $x_{j} = x_{j - 1} + \sum_{i = 1}^{λ} v_{(j - 1) λ + i},$

where

“

x_j−

1”

is the value of a parity bit “

j−

1,” and

$`` \sum_{i = 1}^{a} v_{(j - 1) a + 1} ″$ is the value of a sum of “

a”

randomly chosen irregular repeats of the message bits; and

making the sequence of parity bits available for transmission in a transmission data stream.

View all claims

1 Assignment

Timeline View

Assignment View

Litigations

5 Petitions

Accused Products

Abstract

A serial concatenated coder includes an outer coder and an inner coder. The outer coder irregularly repeats bits in a data block according to a degree profile and scrambles the repeated bits. The scrambled and repeated bits are input to an inner coder, which has a rate substantially close to one.

20 Citations

View as Search Results

23 Claims

1. A method comprising:
- receiving a collection of message bits having a first sequence in a source data stream;
  
  generating a sequence of parity bits, wherein each parity bit “
  
  x_j”
  
  in the sequence is in accordance with the formula $x_{j} = x_{j - 1} + \sum_{i = 1}^{λ} v_{(j - 1) λ + i},$
  
  where
  
  “
  
  x_j−
  
  1”
  
  is the value of a parity bit “
  
  j−
  
  1,” and
  
  $`` \sum_{i = 1}^{a} v_{(j - 1) a + 1} ″$ is the value of a sum of “
  
  a”
  
  randomly chosen irregular repeats of the message bits; and
  
  making the sequence of parity bits available for transmission in a transmission data stream.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
- - 2. The method of claim 1, wherein the sequence of parity bits is generated is in accordance with “
    - a”
      
      being constant.
  - 3. The method of claim 1, wherein the sequence of parity bits is generated is in accordance with “
    - a”
      
      varying for different parity bits.
  - 4. The method of claim 1, wherein generating the sequence of parity bits comprises performing recursive modulo two addition operations on the random sequence of bits.
  - 5. The method of claim 1, wherein generating the sequence of parity bits comprises:
    - generating a random sequence of bits that repeats each of the message bits one or more times with the repeats of the message bits being distributed in a random sequence, wherein different fractions of the message bits are each repeated a different number of times and the number of repeats for each message bit is irregular; and
      
      XOR summing in linear sequential fashion a predecessor parity bit and “
      
      a”
      
      bits of the random sequence of bits.
  - 6. The method of claim 5, wherein generating the random sequence of bits comprises coding the collection of message bits using a low-density generator matrix (LDGM) coder.
  - 7. The method of claim 5, wherein generating the random sequence of bits comprises:
    - producing a block of data bits, wherein different message bits are each repeated a different number of times in a sequence that matches the first sequence; and
      
      randomly permuting the different bits to generate the random sequence.
  - 8. The method of claim 1, further comprising transmitting the sequence of parity bits.
  - 9. The method of claim 8, wherein transmitting the sequence of parity bits comprises transmitting the sequence of parity bits as part of a nonsystematic code.
  - 10. The method of claim 8, wherein transmitting the sequence of parity bits comprises transmitting the sequence of parity bits as part of a systematic code.

11. A device comprising:
- an encoder configured to receive a collection of message bits and encode the message bits to generate a collection of parity bits in accordance with the following Tanner graph;
- View Dependent Claims (12, 13, 14, 15, 16, 17)
- - 12. The device of claim 11, wherein the encoder is configured to generate the collection of parity bits as if a number of inputs into nodes v_iwas not constant.
  - 13. The device of claim 11, wherein the encoder comprises:
    - a low-density generator matrix (LDGM) coder configured to perform an irregular repeat on message bits having a first sequence in a source data stream to output a random sequence of repeats of the message bits; and
      
      an accumulator configured to XOR sum in linear sequential fashion a predecessor parity bit and “
      
      a”
      
      bits of the random sequence of repeats of the message bits.
  - 14. The device of claim 12, wherein the accumulator comprises a recursive convolutional coder.
  - 15. The device of claim 14, wherein the recursive convolutional coder comprises a truncated rate-1 recursive convolutional coder.
  - 16. The device of claim 14, wherein the recursive convolutional coder has a transfer function of 1/(1+D).
  - 17. The device of claim 12, further comprising a second accumulator configured to determine a second sequence of parity bits that defines a second condition that constrains the random sequence of repeats of the message bits.

18. A device comprising:
- a message passing decoder configured to decode a received data stream that includes a collection of parity bits, the message passing decoder comprising two or more check/variable nodes operating in parallel to receive messages from neighboring check/variable nodes and send updated messages to the neighboring variable/check nodes, wherein the message passing decoder is configured to decode the received data stream that has been encoded in accordance with the following Tanner graph;
- View Dependent Claims (19, 20, 21, 22, 23)
- - 19. The device of claim 18, wherein the message passing decoder is configured to decode the received data stream that includes the message bits.
  - 20. The device of claim 18, wherein the message passing decoder is configured to decode the received data stream as if a number of inputs into nodes v_iwas not constant.
  - 21. The device of claim 18, wherein the message passing decoder is configured to decode in linear time at rates that approach a capacity of a channel.
  - 22. The device of claim 18, wherein the message passing decoder comprises a belief propagation decoder.
  - 23. The device of claim 18, wherein the message passing decoder is configured to decode the received data stream without the message bits.

Specification

Resources

Litigation Campaign Assessment

Litigation Data

Current Assignee
California Institute of Technology
Original Assignee
California Institute of Technology
Inventors
McEliece, Robert J., Jin, Hui, Khandekar, Aamod
Primary Examiner(s)
Ha, Dac V.

Application Number

US11/542,950
Publication Number

US 20070025450A1
Time in Patent Office

700 Days
Field of Search

375/259, 375/262, 375/265, 375/285, 375/296, 375/341, 375/346, 375/348, 714/746, 714/752, 714/755, 714/756, 714/786, 714/792, 714794-796, 341/51, 341/52, 341/56, 341/102, 341/103
US Class Current

375/262
CPC Class Codes

H03M 13/1102   Codes on graphs and decodin...

H03M 13/1197   Irregular repeat-accumulate...

H03M 13/2939   using convolutional codes H...

H03M 13/2972   Serial concatenation using ...

Serial concatenation of interleaved convolutional codes forming turbo-like codes

First Claim

1 Assignment

Litigations

5 Petitions

Accused Products

Abstract

20 Citations

23 Claims

Specification

Solutions

Use Cases

Quick Links

Serial concatenation of interleaved convolutional codes forming turbo-like codes

First Claim

1 Assignment

Subscription Required

Subscription Required

Litigations

5 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

20 Citations

23 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links