Iterative forward error correction

• US 20070044005A1
• Filed: 03/07/2006
• Published: 02/22/2007
• Est. Priority Date: 09/11/2003
• Status: Active Grant

• Current Assignee: Runcom Technologies Ltd.
• Original Assignee: Bamboo Mediacasting Ltd. (Runcom Technologies Ltd.)
• Inventors: Amram, Noam, Entin, Leonid
• Granted Patent: US 7,831,896 B2
• Time in Patent Office: Days
• US Class Current: 714/776
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/293 with erasure setting
• CPC Class Codes: H03M 13/2948 Iterative decoding H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/353 Adaptation to the channel
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]

Abstract

A method of preparing data for transmission. The method includes providing a block of data, generating a plurality of first dimension code words including first dimension forward error correction FEC elements, the elements of each code word may be used interchangeably to reconstruct a data portion of the block corresponding to the code word, defining a plurality of second dimension source words formed of the generated elements and generating for at least two of the defined second dimension source words, different numbers of parity elements.

Claims

1. A method of preparing data for transmission, comprising:

providing a block of data;

arranging the data in at least a two-dimensional array;

generating a plurality of first dimension code words including first dimension forward error correction FEC elements, the first dimension elements of each code word may be used interchangeably to reconstruct a data portion of the block corresponding to the code word;

defining a plurality of second dimension source words formed of the generated first dimension FEC elements; and

generating for at least two of the defined second dimension source words, different numbers of parity elements.

2. A method according to claim 1, wherein at least some of the first dimension FEC elements are not included in second dimension code words for which second dimension parity elements are generated.

3. A method according to claim 1, wherein generating the first dimension code words comprises generating according to a systematic code.

4. A method according to claim 1, wherein second dimension parity elements are generated for fewer than half the first dimension elements.

5. A method according to claim 1, wherein generating second dimension parity elements comprises generating such that at least five of the defined second dimension source words have different code rates.

6. A method according to claim 1, wherein generating second dimension parity elements comprises generating such that each second dimension source word for which parity elements are generated, has a different number of elements.

7. A method according to claim 1, wherein generating second dimension parity elements comprises generating parity elements in accordance with each code rate for which parity elements are generated, for a same number of second dimension source words.

8. A method according to claim 1, wherein generating first dimension code words comprises generating code words including different numbers of elements.

9. A method according to claim 1, comprising transmitting all the generated first and second dimension elements to a receiver.

10. A method according to claim 1, comprising transmitting fewer than all the generated first and second dimension elements to a receiver.

11. A method according to claim 10, wherein first dimension elements belonging to second dimension source words for which parity elements were generated, are not transmitted.

12. A method according to claim 1, wherein transmitting the data comprises transmitting over a channel having a loss rate greater than 30%.

13. A method of according to claim 1, wherein each element comprises a data packet.

14. A method of according to claim 1, wherein each element comprises a single bit.

15. A method of transmitting data, comprising:

providing a block of data;

arranging the data in at least a two-dimensional array;

generating a plurality of first dimension code words of forward error correction FEC elements, the FEC elements of each code word may be used interchangeably to reconstruct a data portion of the block corresponding to the code word;

generating one or more second dimension code words, each second dimension code word including FEC elements from one or more of the first dimension code words;

transmitting FEC elements representing the data block to a receiver, the transmitted elements not including at least one FEC element belonging to both a first and second dimension code word.

16. A method according to claim 15, wherein transmitting the elements comprises transmitting all the elements of the second dimension code words that do not belong to first dimension code words.

17. A method according to claim 15, wherein generating the first dimension code words comprises generating code words including source elements and parity elements and wherein some of the parity elements are transmitted and some of the parity elements are not transmitted.

18. A method according to claim 17, wherein the source elements and the transmitted parity elements of each first dimension code word are of a number required to allow, on the average, reconstruction of between about 35-50% of the code words, without the non-transmitted parity elements, taking into account an expected loss rate during the transmission.

19. A method according to claim 15, wherein each first dimension code word includes a number of elements sufficient to allow, on the average, reconstruction of at least 95% of the first dimension code words based on transmission of the elements of the code words, taking into account an expected loss rate during the transmission.

20. A method according to claim 15, wherein each first dimension code word includes a number of elements sufficient to allow, on the average, reconstruction of less than 98% of the first dimension code words based on transmission of the elements of the code words, taking into account an expected loss rate during the transmission.

21. A method according to claim 20, wherein each first dimension code word includes a number of elements sufficient to allow, on the average, reconstruction of less than 95% of the first dimension code words based on transmission of the elements of the code words, taking into account an expected loss rate during the transmission.

22. A method according to claim 15, wherein more than 20% of the elements common to first and second dimension code words are not transmitted.

23. A method according to claim 15, wherein generating second dimension code words comprises generating a plurality of code words of different code rates.

24. A method according to claim 15, wherein generating second dimension code words comprises generating a plurality of code words with same code rates.

25. A method according to claim 15, wherein all the common elements of first and second dimension code words of at least one code word are not transmitted.

26. A method according to claim 15, wherein generating second dimension code words comprises generating at least one second dimension code word having one element from each of the first dimension code words.

27. A method according to claim 15, comprising generating and transmitting elements of a third dimension code word.

28. A method according to claim 15, wherein generating the code words comprises generating according to a block code.

29. A method according to claim 15, wherein generating the code words comprises generating according to a convolution code.

30. A method according to claim 15, wherein transmitting the elements comprises transmitting over a plurality of different channels.

31. A method according to claim 30, wherein transmitting the elements comprises transmitting over a plurality of channels with different expected loss rates.

32. A method according to claim 30, wherein elements belonging to second dimension code words but not to the first dimension code word are transmitted on a separate channel from elements of first dimension code words.

33. A method according to claim 32, wherein elements belonging to second dimension code words but not to the first dimension code words are transmitted on a channel having a lower loss rate than a channel used for elements of first dimension code words.

34. A method of transmitting data, comprising:

providing a block of data;

generating a plurality of FEC elements of one or more dimensions that represent the block of data; and

transmitting the plurality of FEC segments over a plurality of different channels concurrently, the channels carrying sequences of elements that are not identical.

35. A method according to claim 34, wherein generating the plurality of FEC elements comprises generating elements according to a single dimension FEC method.

36. A method according to claim 34, wherein generating the plurality of FEC elements comprises generating elements according to a multi-dimension FEC method.

37. A method according to claim 34, wherein transmitting the plurality of FEC segments comprises transmitting all elements belonging to a same code word on a single channel.

38. A method according to claim 34, wherein transmitting the plurality of FEC segments comprises transmitting elements belonging to at least one single code word on a plurality of channels.

39. A method according to claim 34, wherein transmitting the plurality of FEC segments comprises transmitting on a plurality of channels having same loss rates.

40. A method according to claim 34, wherein transmitting the plurality of FEC segments comprises transmitting on a plurality of channels having different loss rates.

41. A method according to claim 40, wherein transmitting the plurality of FEC segments comprises transmitting on a plurality of channels having different loss rates due to different transmission methods.

42. A method according to claim 34, wherein transmitting the plurality of FEC segments comprises transmitting only systematic FEC elements on at least one of the channels.

43. A method according to claim 34, wherein generating the FEC elements comprises generating code words of one or more first dimensions and parity elements of one or more second dimensions and wherein transmitting the plurality of FEC segments comprises transmitting such that one or more channels do not carry the parity elements of the one or more second dimensions.

44. A method according to claim 43, wherein one or more channels carry only the parity elements of the one or more second dimensions.

45. A method according to claim 34, comprising receiving the transmitted plurality of segments by a plurality of receivers, at least one of the receivers receives segments on fewer than all the channels on which the FEC segments are transmitted.

46. A method according to claim 34, comprising receiving the transmitted plurality of segments by a plurality of receivers, at least one of the receivers having the capability to listen concurrently to all the channels and at least one of the receivers not having the capability to listen concurrently to all the channels.

47. A method according to claim 34, wherein the sequences of elements of different channels differ in at least some of the elements they contain.

48. A method according to claim 47, wherein the sequences of elements of at least two channels do not include any common elements.

49. A method according to claim 34, wherein the sequences of elements of at least two channels include at least 50% elements in common but in different orders.

50. A method of receiving data, comprising:

tuning onto a plurality of channels;

receiving FEC elements on each of the plurality of channels; and

reconstructing a data block using one or more FEC elements received over each of the plurality of channels.

51. A method according to claim 50, wherein the plurality of channels include at least two channels having different loss rates.

52. A method according to claim 50, wherein receiving the FEC elements comprises receiving only parity elements on at least one of the channels.

53. A method according to claim 50, wherein receiving the FEC elements comprises receiving only systematic elements on at least one of the channels.

54. A method according to claim 50, wherein receiving the FEC elements comprises receiving elements of a single code word on at least two different channels.

55. A multicast transmission unit, comprising:

an input interface for receiving blocks of data;

a processor adapted to generate a plurality of first dimension code words including first dimension forward error correction FEC elements, the first dimension elements of each code word may be used interchangeably to reconstruct a data portion of the block corresponding to the code word, to define a plurality of second dimension source words formed of the generated first dimension FEC elements and to generate for at least two of the defined second dimension source words, different numbers of parity elements; and

a transmitter for transmitting FEC elements generated by the processor.

56. A transmission unit according to claim 55, wherein the transmitter is adapted to transmit FEC elements generated by the processor for a single block on a plurality of channels.