Encoders for block-circulant LDPC codes

1. An encoding apparatus to encode message input symbols in accordance with an accumulate-repeat-accumulate code with repetition four, the apparatus comprising:

a first multiplier to multiply a first portion of the input symbols with a first matrix, forming first intermediate symbols;

a second multiplier to multiply a second portion of the input symbols with a second matrix, forming second intermediate symbols;

a first adder to sum the first intermediate symbols with the second intermediate symbols, forming third intermediate symbols;

a third multiplier to multiply the third intermediate symbols with a third matrix, forming fourth intermediate symbols;

a fourth multiplier to multiply the third intermediate symbols with a fourth matrix, forming a first set of output symbols;

a second adder to sum the fourth intermediate symbols with the second portion of the input symbols, forming fifth intermediate symbols;

a permuter to permute the fifth intermediate symbols, forming permuted symbols; and

an accumulator to accumulate the permuted symbols, forming a second set of output symbols.

2. The apparatus of claim 1 , wherein the first portion of the input symbols corresponds to a first half of the input symbols and the second portion of the input symbols corresponds to a second half of the input symbols.

3. The apparatus of claim 1 , wherein output symbols are obtained by combining the first set of output symbols, the second set of output symbols, and the input symbols.

4. The apparatus of claim 1 , wherein each row of the first matrix has Hamming weight 2 , each row of the second matrix has Hamming weight 3 , each row of the third matrix has Hamming weight 3 , and each row of the fourth matrix has Hamming weight 2 .

5. The apparatus of claim 1 , wherein the first matrix, second matrix, third matrix and fourth matrix are block-circulant matrices.

6. A method for encoding message input symbols in accordance with an accumulate-repeat-accumulate code with repetition four, comprising:

multiplying a first portion of the input symbols with a first matrix, forming first intermediate symbols;

multiplying a second portion of the input symbols with a second matrix, forming second intermediate symbols;

adding the first intermediate symbols to the second intermediate symbols, forming third intermediate symbols;

multiplying the third intermediate symbols with a third matrix, forming fourth intermediate symbols;

multiplying the third intermediate symbols with a fourth matrix, forming a first set of output symbols;

adding the fourth intermediate symbols with the input symbols, forming fifth intermediate symbols;

permuting the fifth intermediate symbols, forming permuted symbols; and

accumulating the permuted symbols, forming a second set of output symbols.

7. The method of claim 6 , wherein output symbols are obtained by combining the first set of output symbols, the second set of output symbols, and the input symbols.

8. The method of claim 6 , wherein the first portion of the input symbols corresponds to a first half of the input symbols and the second portion of the input symbols corresponds to a second half of the input symbols.

9. The method of claim 6 , wherein each row of the first matrix has Hamming weight 2 , each row of the second matrix has Hamming weight 3 , each row of the third matrix has Hamming weight 3 , and each row of the fourth matrix has Hamming weight 2 .

10. The method of claim 6 , wherein the first matrix, second matrix, third matrix and fourth matrix are block-circulant matrices.

11. An encoding apparatus to encode message input symbols in accordance with an accumulate-repeat-accumulate code with repetition three, the apparatus comprising:

a puncturing device, puncturing k input symbols and outputting k/2 input symbols, forming a first set of output symbols;

a first multiplier to multiply the k input symbols with a first matrix, forming first intermediate symbols;

a second multiplier to multiply the k input symbols with a second matrix, forming a second set of output symbols;

a permuter to permute the first intermediate symbols, forming permuted symbols; and

an accumulator to accumulate the permuted symbols, forming a third set of output symbols.

12. The apparatus of claim 11 , wherein an output codeword is obtained by combining the first, second and third sets of output symbols.

13. The apparatus of claim 11 , wherein the first matrix is a block matrix of size k×k, comprising two on-diagonal sub-matrices each of size k/2 ×k/2 and two off-diagonal sub-matrices each of size k/2 ×k/2, and the second matrix is of size k×k/2, k being an integer.

14. The apparatus of claim 13 , wherein the two on-diagonal sub-matrices are zero and the two off-diagonal sub-matrices each have rows of Hamming weight 2 , and the second matrix has k/2 rows with Hamming weight 1 and k/2 rows with Hamming weight 2 .

15. The apparatus of claim 11 , wherein the first matrix and the second matrix are block-circulant matrices.

16. A method for encoding message input symbols in accordance with an accumulate-repeat-accumulate code with repetition three, comprising:

puncturing k input symbols and outputting k/2 input symbols, forming a first set of output symbols, k being an integer;

multiplying the k input symbols with a first matrix, forming first intermediate symbols;

multiplying the k input symbols with a second matrix, forming a second set of output symbols;

permuting the first intermediate symbols, forming permuted symbols; and

accumulating the permuted symbols, forming a third set of output symbols.

17. The method of claim 16 , further comprising combining the first, second and third sets of output symbols to obtain an output codeword.

18. The method of claim 16 , wherein the first matrix is a block matrix of size k×k, comprising two on-diagonal sub-matrices each of size k/2 ×k/2 and two off-diagonal sub-matrices each of size k/2 ×k/2, and the second matrix is of size k×k/2.

19. The method of claim 18 , wherein the two on-diagonal sub-matrices are zero and the two off-diagonal sub-matrices each have rows of Hamming weight 2 , and the second matrix has k/2 rows with Hamming weight 1 and k/2 rows with Hamming weight 2 .

20. The method of claim 16 , wherein the first and second matrix are block-circulant matrices.

21. An encoding apparatus to encode input symbols in accordance with a block-circulant low density parity check (LDPC) code, the apparatus comprising:

a plurality of recursive convolutional encoders, each recursive convolutional encoder comprising storage units, multipliers and adders to encode the input symbols; and

a plurality of circulant patterns to be fed to the recursive convolutional encoders, one set of patterns for each recursive convolutional encoder.

22. The apparatus of claim 21 , wherein the recursive encoders further comprise switches, each switch having a first condition where contents of a rightmost storage unit of a recursive convolutional encoder are sent back to that recursive convolutional encoder and a second condition where contents of a rightmost storage unit are sent towards the output.

23. The apparatus of claim 21 , wherein output symbols are obtained by combining the input symbols with the contents of the storage units within the recursive convolutional encoders.

24. A method for encoding input symbols in accordance with a block-circulant LDPC code, comprising:

providing a plurality of recursive convolutional encoders, each recursive convolutional encoder comprising storage units, multipliers and adders;

setting the storage units to a first binary value;

repeating the following operations:

i) computing a set of circulant patterns,

ii) providing each recursive convolutional encoder with a binary sequence of T message bits, each message bit sent to the output as a codeword symbol, and each message bit being multiplied with a circulant pattern, summed to the result of a previous multiplication, stored in a storage unit and shifted, until the T message bits have been encoded,

until kT message bits have been encoded; and

generating an output codeword by reading the contents of the storage units of the recursive convolutional encoders,

wherein k and T are integers.

25. The method of claim 24 , wherein the binary sequences are provided through an additional plurality of storage units.

26. The method of claim 24 , wherein the binary sequences are provided by combinatorial logic.

27. The method of claim 24 , wherein the binary sequences correspond to circulant patterns of a generator matrix.

28. The method of claim 24 , wherein the plurality of recursive convolutional encoders comprises n-k convolutional encoders, n being an integer, wherein n-k-l recursive convolutional encoders comprise a switch, the switch having a first condition where the contents of the rightmost storage unit of a recursive convolutional encoder are sent to the leftmost adder of that recursive convolutional encoder, and a second condition where the contents of the rightmost storage unit of a recursive convolutional encoder are sent towards the output.