Combined-replica group-shuffled iterative decoding for error-correcting codes

1. A method for generating a combined-replica group-shuffled iterative decoder, comprising:

receiving an error-correcting code and an iterative decoder for an error-correcting code;

constructing multiple group-shuffled sub-decoders for the error-correcting code based on the iterative decoder;

partitioning, for each group-shuffled sub-decoder, estimates for symbols into groups;

assigning, for each group-shuffled sub-decoder, a schedule for the updating;

updating the estimates according to the schedule; and

combining the multiple group-shuffled sub-decoders into a combined-replica group-shuffled iterative decoder.

2. The method of claim 1 , in which the error-correcting code is binary, and the symbols are bits.

3. The method of claim 2 , in which the group-shuffled sub-decoders use belief propagation and the estimates are messages, and the messages represent log-likelihoods that the bits are either a 0 or a 1.

4. The method of claim 2 , in which the group-shuffled sub-decoders use bit-flipping, and the estimates are states of the bits of the code-word.

5. The method of claim 1 , in which the error-correcting code is a binary low-density parity check code.

6. The method of claim 1 , in which the groups are of equal size.

7. The method of claim 1 , in which the group-shuffled sub-decoder uses belief propagation and the groups are formed using a vertical partition.

8. The method of claim 1 , in which the group-shuffled sub-decoder uses belief propagation and the groups are formed using a horizontal partition.

9. The method of claim 1 , in which the schedule defines an order in which the groups are updated.

10. The method of claim 1 , in which the groups are partitioned identically in the sub-decoders.

11. The method of claim 1 , in which the groups are partitioned differently in the sub-decoders.

12. The method of claim 1 , in which the schedule for each group-shuffled sub-decoder is different.

13. The method of claim 1 , in which each estimate is updated by at least one of the group-shuffled sub-decoders.

14. The method of claim 1 , in which the group-shuffled iterative sub-decoders update the estimates synchronously.

15. The method of claim 1 , further comprising:

using most reliable symbol estimates during the updating.

16. The method of claim 15 , in which the most reliable symbol estimates are obtained from a particular sub-decoder that updated the estimate most recently.

17. The method of claim 1 , in which the error-correcting code is a turbo code.

18. The method of claim 17 , in which the turbo-code is a concatenation of two binary systematic convolutional codes.

19. The method of claim 18 , in which four sub-decoders are used in the combined decoder.

20. The method of claim 19 , in which one sub-decoder decodes the first convolutional code using Bahl, Cocke, Jelinek and Raviv (BCJR) decoding with a forward sweep followed by a backward sweep, a second sub-decoder decodes the first convolutional code using the BCJR decoding with a backward sweep followed by a forward sweep, a third sub-decoder decodes the second convolutional code using the BCJR decoding with a forward sweep followed by a backward sweep, and the fourth sub-decoder decodes the second convolutional code using the BCJR decoding with a backward sweep followed by a forward sweep.

21. The method of claim 1 , in which the error-correcting code is a turbo product code.

22. The method of claim 21 , in which the turbo-product code is a product of horizontal and vertical codes.

23. The method of claim 22 , in which four sub-decoders are used in the combined decoder.

24. The method of claim 23 , in which a first sub-decoder decodes the horizontal codes from top to bottom, a second sub-decoder decodes the horizontal codes from bottom to top, a third sub-decoder decodes the vertical codes from left to right, and a fourth sub-decoder decodes the vertical codes from right to left.

25. The method of claim 1 , in which the error-correcting code is an irregular low density parity check code.

26. The method of claim 1 , in which the error-correcting code is a repeat-accumulate code.

27. The method of claim 1 , in which the error-correcting code is a Luby Transform (LT) code.

28. The method of claim 1 , in which the error-correcting code is a Raptor code.

29. The method of claim 1 , in which the error-correcting code is an iteratively decodable code.

30. The method of claim 1 , in which the error-correcting code is a non binary codes.

31. The method of claim 1 , in which the symbols are taken from an arbitrary alphabet.

32. A combined-replica group-shuffled iterative decoder, comprising:

a plurality of group-shuffled sub-decoders constructed from an iterative decoder for an error-correcting code, each group-shuffled sub-decoder configured to receive channel information;

a control block connected to each of the group-shuffled sub-decoders, the control block further comprising:

a reliability assigner, the reliability checker configured to receiver bit estimates from each of the group-shuffled sub-decoders, and to output to each group-shuffled sub-decoder most reliable bit estimates;

means for assigning an updating schedule to each of the group-shuffled sub-decoders; and

a termination checker configured to output the most reliable bit estimates corresponding to the channel information when a termination condition has been reached.

33. The decoder of claim 32 , in which the error-correcting code is a turbo-code constructed from a concatenation of a plurality of convolutional codes.

34. The decoder of claim 32 , in which a first sub-decoder updates only messages from a first convolutional code using a forward sweep of the schedule followed by a backward sweep of the schedule, a second sub-decoder updates only the messages from the first convolutional code using the backward sweep followed by the forward sweep, a third decoder updates messages from a second convolutional code using the forward sweep followed by the backward sweep, and a fourth sub-decoder updates the messages from the second convolutional code using the backward sweep followed by the forward sweep.

35. The decoder of claim 32 , in which the updating schedule is different for each of the group-shuffled sub-decoders.