Multiple-field based code generator and decoder for communications systems

• US 9,270,414 B2
• Filed: 02/13/2007
• Issued: 02/23/2016
• Est. Priority Date: 02/21/2006
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Shokrollahi, M. Amin, Luby, Michael G., Watson, Mark, Minder, Lorenz
• Primary Examiner(s): Washburn, Daniel
• Assistant Examiner(s): HUGHES, EBONI N
• Application Number:
  US11/674,655
• Publication Number:
  US 20070195894A1
• Time in Patent Office: 3,297 Days
• Field of Search: 375/222, 375/265, 375/260, 375/261, 375/342, 375/340, 714/756, 714/759, 714/781, 714/784, 714/789, 714/790, 714/792, 714/800
• US Class Current: 1/1
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0065 Serial concatenated codes

Abstract

A method of encoding data for transmission from a source to a destination over a communications channel is provided. The method operates on an ordered set of input symbols and includes generating a plurality of redundant symbols from the input symbols based on linear constraints. The method also includes generating a plurality of output symbols from a combined set of symbols including the input symbols and the redundant symbols based on linear combinations, wherein at least one of the linear constraints or combinations is over a first finite field and at least one other of the linear constraints or combinations is over a different second finite field, and such that the ordered set of input symbols can be regenerated to a desired degree of accuracy from any predetermined number of the output symbols.

Claims

1. A method of encoding data for transmission from a source to a destination over a communications channel that is expected to perform as an erasure channel at least partially, the method comprising:

obtaining an ordered set of input symbols representing the data to be encoded;

selecting a plurality of field arrays of values, wherein each field array is derived from a finite field array and at least two different finite field arrays are represented;

generating a data structure that represents a coefficient matrix having entries of at least two of the field arrays derived from different finite field arrays, wherein a majority of the entries of the coefficient matrix are from a smaller finite field array, and a remainder of the entries of the coefficient matrix are from a larger finite field array;

generating output symbols as linear combinations of input symbols with coefficients taken from the data structure that represents the coefficient matrix; and

using the generated output symbols and an encoding for the data.

2. The method of claim 1, wherein the data structure that represents a coefficient matrix is a two-dimensional array of cell values, each cell value representing a coefficient of one input symbol in the generation of one output symbol such that when a coefficient is not zero or zero modulo some base, the value of the corresponding output symbol depends on the value of the corresponding input symbol.

3. The method of claim 1, wherein the data structure that represents a coefficient matrix is a set of rules that specify coefficient values, and further wherein when a rule indicates that a coefficient is not zero or zero modulo some base, the value of the corresponding output symbol depends on the value of the corresponding input symbol.

4. The method of claim 1, wherein the number of unique output symbols that can be generated from the set of input symbols, for any set of fixed values for the input symbols, is independent of the field array sizes.

5. The method of claim 1, wherein the generation of a data structure that represents a coefficient matrix having entries of at least two of the field arrays derived from different finite field arrays is a generation that uses a first field array derived from a first finite field array and a second field array derived from a second finite field array, wherein the first finite field array and the second finite field array are different, and further wherein the first finite field and the second finite field are each selected from the field set consisting of GF(2), GF(4), GF(16), GF(256).

6. The method of claim 5, wherein the first finite field array is GF(2) and the second finite field array is GF(256).

7. The method of claim 5, wherein the first finite field array is GF(2) and the second finite field array is GF(4).

8. The method of claim 5, wherein the first finite field array is GF(4) and the second finite field array is GF(16).

9. The method of claim 5, wherein the first finite field array is GF(16) and the second finite field array is GF(256).

10. A method of decoding data from a transmission received at a destination from a source over a communications channel that is expected to perform as an erasure channel at least partially, the method comprising:

receiving at least some of a plurality of output symbols generated from an ordered set of input symbols that were encoded into the plurality of output symbols wherein each output symbol was generated as a linear combination of one or more of the input symbols with coefficients chosen from finite fields, wherein at least one coefficient is a member of a first finite field and at least one other coefficient is a member of a second finite field that is larger than the first finite field; and

regenerating the ordered set of input symbols to a desired degree of accuracy from reception of any predetermined number of the output symbols,

wherein a majority of the coefficients are chosen from the smaller first finite field, and a remainder of the coefficients are chosen from the larger second finite field.

11. The method of claim 10, wherein the number of unique output symbols that could have been generated from the set of input symbols, for any set of fixed values for the input symbols, was independent of the field array sizes.

12. The method of claim 10, wherein the finite fields are such that a first finite field array and a second finite field array are different and the first finite field and the second finite field are each selected from the field set consisting of GF(2), GF(4), GF(16), GF(256).

13. The method of claim 12, wherein the first finite field array is GF(2) and the second finite field array is GF(256).

14. The method of claim 12, wherein the first finite field array is GF(2) and the second finite field array is GF(4).

15. The method of claim 12, wherein the first finite field array is GF(4) and the second finite field array is GF(16).

16. The method of claim 12, wherein the first finite field array is GF(16) and the second finite field array is GF(256).

17. A method of encoding data for transmission from a source to a destination over a communications channel that is expected to perform as an erasure channel at least partially, the method comprising:

obtaining an ordered set of input symbols representing the data to be encoded;

selecting a plurality of field arrays of values, wherein each field array is derived from a finite field array and at least two different finite field arrays are represented;

generating a plurality of redundant symbols from the ordered set of input symbols, wherein each redundant symbol is generated based on a set of linear constraints over one or more of the input symbols and other redundant symbols with coefficients over finite fields, wherein the finite fields are such that a first finite field array and a second finite field array are different, a majority of the coefficients are chosen from a smaller of the first finite field array and the second finite field array, and a remainder of the coefficients are chosen from a larger of the first finite field array and the second finite field array;

generating a plurality of output symbols from the combined set of input and redundant symbols, wherein each output symbol is generated as a linear combination of one or more of the combined set of input and redundant symbols with coefficients chosen from finite fields;

using the generated output symbols and an encoding for the data.

18. The method of claim 17, wherein the number of redundant symbols that can be generated from the set of input symbols, for any set of fixed values for the input symbols, is independent of the field array sizes.

19. The method of claim 17, wherein the first finite field and the second finite field are each selected from the field set consisting of GF(2), GF(4), GF(16), GF(256).

20. A method of decoding data from a transmission received at a destination from a source over a communications channel that is expected to perform as an erasure channel at least partially, the method comprising:

receiving at least some of the plurality of output symbols generated from a combined set of input and redundant symbols, wherein each output symbol is generated as a linear combination of one or more of a combined set of input and redundant symbols with coefficients chosen from finite fields,

wherein the plurality of redundant symbols is generated from the ordered set of input symbols, wherein each redundant symbol is generated based on a set of linear constraints over one or more of the input symbols and other redundant symbols with coefficients over finite fields,

wherein at least one coefficient is a member of a first finite field and at least one other coefficient is a member of a second finite field that is larger than the first finite field, a majority of the coefficients are chosen from the smaller first finite field, and a remainder of the coefficients are chosen from the larger second finite field; and

regenerating the ordered set of input symbols to a desired degree of accuracy from reception of any predetermined number of the output symbols.

21. The method of claim 20, wherein the number of unique output symbols that could have been generated from the set of input symbols, for any set of fixed values for the input symbols, was independent of the field array sizes.

22. The method of claim 20, wherein the first finite field is GF(2).

23. The method of claim 20, wherein the second finite field is GF(256).

24. The method of claim 20, wherein the second finite field is GF(4).

25. The method of claim 20, wherein the first finite field is GF(4).

26. The method of claim 20, wherein the first finite field is GF(16).

27. The method of claim 20, wherein the second finite field is GF(16).

28. An apparatus for encoding data for transmission from a source to a destination over a communications channel, the apparatus comprising:

memory; and

a processor;

the memory and processor configured to perform operations comprising;

obtaining an ordered set of input symbols representing the data to be encoded;

selecting a plurality of field arrays of values, wherein each field array is derived from a finite field array and at least two different finite field arrays are represented;

generating a data structure that represents a coefficient matrix having entries of at least two of the field arrays derived from different finite field arrays, wherein a majority of the entries of the coefficient matrix are from a smaller finite field array, and a remainder of the entries of the coefficient matrix are from a larger finite field array;

generating output symbols as linear combinations of input symbols with coefficients taken from the data structure that represents the coefficient matrix; and

using the generated output symbols and an encoding for the data.

29. The apparatus of claim 28, wherein the data structure that represents a coefficient matrix is a two-dimensional array of cell values, each cell value representing a coefficient of one input symbol in the generation of one output symbol such that when a coefficient is not zero or zero modulo some base, the value of the corresponding output symbol depends on the value of the corresponding input symbol.

30. The apparatus of claim 28, wherein the data structure that represents a coefficient matrix is a set of rules that specify coefficient values, and further wherein when a rule indicates that a coefficient is not zero or zero modulo some base, the value of the corresponding output symbol depends on the value of the corresponding input symbol.

31. The apparatus of claim 28, wherein the number of unique output symbols that can be generated from the set of input symbols, for any set of fixed values for the input symbols, is independent of the field array sizes.

32. The apparatus of claim 28, wherein the generation of a data structure that represents a coefficient matrix having entries of at least two of the field arrays derived from different finite field arrays is a generation that uses a first field array derived from a first finite field array and a second field array derived from a second finite field array, wherein the first finite field array and the second finite field array are different, and further wherein the first finite field and the second finite field are each selected from the field set consisting of GF(2), GF(4), GF(16), GF(256).

33. The apparatus of claim 32, wherein the first finite field array is GF(2) and the second finite field array is GF(256).

34. The apparatus of claim 32, wherein the first finite field array is GF(2) and the second finite field array is GF(4).

35. The apparatus of claim 32, wherein the first finite field array is GF(4) and the second finite field array is GF(16).

36. The apparatus of claim 32, wherein the first finite field array is GF(16) and the second finite field array is GF(256).

37. An apparatus for decoding data from a transmission received at a destination from a source over a communications channel, the apparatus comprising:

memory; and

a processor;

the memory and processor configured to perform operations comprising;

receiving at least some of a plurality of output symbols generated from an ordered set of input symbols that were encoded into the plurality of output symbols wherein each output symbol was generated as a linear combination of one or more of the input symbols with coefficients chosen from finite fields, wherein at least one coefficient is a member of a first finite field and at least one other coefficient is a member of a second finite field that is larger than the first finite field; and

regenerating the ordered set of input symbols to a desired degree of accuracy from reception of any predetermined number of the output symbols,

wherein a majority of the coefficients are chosen from the smaller first finite field, and a remainder of the coefficients are chosen from the larger second finite field.

38. The apparatus of claim 37, wherein the number of unique output symbols that could have been generated from the set of input symbols, for any set of fixed values for the input symbols, was independent of the field array sizes.

39. The apparatus of claim 37, wherein the finite fields are such that a first finite field array and a second finite field array are different and the first finite field and the second finite field are each selected from the field set consisting of GF(2), GF(4), GF(16), GF(256).

40. The apparatus of claim 39, wherein the first finite field array is GF(2) and the second finite field array is GF(256).

41. The apparatus of claim 39, wherein the first finite field array is GF(2) and the second finite field array is GF(4).

42. The apparatus of claim 39, wherein the first finite field array is GF(4) and the second finite field array is GF(16).

43. The apparatus of claim 39, wherein the first finite field array is GF(16) and the second finite field array is GF(256).

44. An apparatus for encoding data for transmission from a source to a destination over a communications channel, the apparatus comprising:

memory; and

a processor;

the memory and processor configured to perform operations comprising;

obtaining an ordered set of input symbols representing the data to be encoded;

selecting a plurality of field arrays of values, wherein each field array is derived from a finite field array and at least two different finite field arrays are represented;

generating a plurality of redundant symbols from the ordered set of input symbols, wherein each redundant symbol is generated based on a set of linear constraints over one or more of the input symbols and other redundant symbols with coefficients over finite fields, wherein the finite fields are such that a first finite field array and a second finite field array are different, a majority of the coefficients are chosen from a smaller of the first finite field array and the second finite field array, and a remainder of the coefficients are chosen from a larger of the first finite field array and the second finite field array;

generating a plurality of output symbols from the combined set of input and redundant symbols, wherein each output symbol is generated as a linear combination of one or more of the combined set of input and redundant symbols with coefficients chosen from finite fields;

using the generated output symbols and an encoding for the data.

45. The apparatus of claim 44, wherein the number of redundant symbols that can be generated from the set of input symbols, for any set of fixed values for the input symbols, is independent of the field array sizes.

46. The apparatus of claim 44, wherein the first finite field and the second finite field are each selected from the field set consisting of GF(2), GF(4), GF(16), GF(256).

47. An apparatus for decoding data from a transmission received at a destination from a source over a communications channel, the apparatus comprising:

memory; and

a processor;

the memory and processor configured to perform operations comprising;

receiving at least some of the plurality of output symbols generated from a combined set of input and redundant symbols, wherein each output symbol is generated as a linear combination of one or more of a combined set of input and redundant symbols with coefficients chosen from finite fields,

wherein the plurality of redundant symbols is generated from the ordered set of input symbols, wherein each redundant symbol is generated based on a set of linear constraints over one or more of the input symbols and other redundant symbols with coefficients over finite fields,

wherein at least one coefficient is a member of a first finite field and at least one other coefficient is a member of a second finite field that is larger than the first finite field, a majority of the coefficients are chosen from the smaller first finite field, and a remainder of the coefficients are chosen from the larger second finite field; and

regenerating the ordered set of input symbols to a desired degree of accuracy from reception of any predetermined number of the output symbols.

48. The apparatus of claim 47, wherein the number of unique output symbols that could have been generated from the set of input symbols, for any set of fixed values for the input symbols, was independent of the field array sizes.

49. The apparatus of claim 47, wherein the first finite field is GF(2).

50. The apparatus of claim 47, wherein the second finite field is GF(256).

51. The apparatus of claim 47, wherein the second finite field is GF(4).

52. The apparatus of claim 47, wherein the first finite field is GF(4).

53. The apparatus of claim 47, wherein the first finite field is GF(16).

54. The apparatus of claim 47, wherein the second finite field is GF(16).

55. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor to perform a method for encoding data for transmission from a source to a destination over a communications channel, the method comprising:

obtaining an ordered set of input symbols representing the data to be encoded;

selecting a plurality of field arrays of values, wherein each field array is derived from a finite field array and at least two different finite field arrays are represented;

generating a data structure that represents a coefficient matrix having entries of at least two of the field arrays derived from different finite field arrays, wherein a majority of the entries of the coefficient matrix are from a smaller finite field array, and a remainder of the entries of the coefficient matrix are from a larger finite field array;

generating output symbols as linear combinations of input symbols with coefficients taken from the data structure that represents the coefficient matrix; and

using the generated output symbols and an encoding for the data.

56. The non-transitory processor-readable storage medium of claim 55, wherein the data structure that represents a coefficient matrix is a two-dimensional array of cell values, each cell value representing a coefficient of one input symbol in the generation of one output symbol such that when a coefficient is not zero or zero modulo some base, the value of the corresponding output symbol depends on the value of the corresponding input symbol.

57. The non-transitory processor-readable storage medium of claim 55, wherein the data structure that represents a coefficient matrix is a set of rules that specify coefficient values, and further wherein when a rule indicates that a coefficient is not zero or zero modulo some base, the value of the corresponding output symbol depends on the value of the corresponding input symbol.

58. The non-transitory processor-readable storage medium of claim 55, wherein the number of unique output symbols that can be generated from the set of input symbols, for any set of fixed values for the input symbols, is independent of the field array sizes.

59. The non-transitory processor-readable storage medium of claim 55, wherein the generation of a data structure that represents a coefficient matrix having entries of at least two of the field arrays derived from different finite field arrays is a generation that uses a first field array derived from a first finite field array and a second field array derived from a second finite field array, wherein the first finite field array and the second finite field array are different, and further wherein the first finite field and the second finite field are each selected from the field set consisting of GF(2), GF(4), GF(16), GF(256).

60. The non-transitory processor-readable storage medium of claim 59, wherein the first finite field array is GF(2) and the second finite field array is GF(256).

61. The non-transitory processor-readable storage medium of claim 59, wherein the first finite field array is GF(2) and the second finite field array is GF(4).

62. The non-transitory processor-readable storage medium of claim 59, wherein the first finite field array is GF(4) and the second finite field array is GF(16).

63. The non-transitory processor-readable storage medium of claim 59, wherein the first finite field array is GF(16) and the second finite field array is GF(256).

64. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor to perform a method for decoding data from a transmission received at a destination from a source over a communications channel, the method comprising:

receiving at least some of a plurality of output symbols generated from an ordered set of input symbols that were encoded into the plurality of output symbols wherein each output symbol was generated as a linear combination of one or more of the input symbols with coefficients chosen from finite fields, wherein at least one coefficient is a member of a first finite field and at least one other coefficient is a member of a second finite field that is larger than the first finite field; and

regenerating the ordered set of input symbols to a desired degree of accuracy from reception of any predetermined number of the output symbols,

wherein a majority of the coefficients are chosen from the smaller first finite field, and a remainder of the coefficients are chosen from the larger second finite field.

65. The non-transitory processor-readable storage medium of claim 64, wherein the number of unique output symbols that could have been generated from the set of input symbols, for any set of fixed values for the input symbols, was independent of the field array sizes.

66. The non-transitory processor-readable storage medium of claim 64, wherein the finite fields are such that a first finite field array and a second finite field array are different and the first finite field and the second finite field are each selected from the field set consisting of GF(2), GF(4), GF(16), GF(256).

67. The non-transitory processor-readable storage medium of claim 66, wherein the first finite field array is GF(2) and the second finite field array is GF(256).

68. The non-transitory processor-readable storage medium of claim 66, wherein the first finite field array is GF(2) and the second finite field array is GF(4).

69. The non-transitory processor-readable storage medium of claim 66, wherein the first finite field array is GF(4) and the second finite field array is GF(16).

70. The non-transitory processor-readable storage medium of claim 66, wherein the first finite field array is GF(16) and the second finite field array is GF(256).

71. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor to perform a method for encoding data for transmission from a source to a destination over a communications channel, the method comprising:

obtaining an ordered set of input symbols representing the data to be encoded;

selecting a plurality of field arrays of values, wherein each field array is derived from a finite field array and at least two different finite field arrays are represented;

generating a plurality of redundant symbols from the ordered set of input symbols, wherein each redundant symbol is generated based on a set of linear constraints over one or more of the input symbols and other redundant symbols with coefficients over finite fields, wherein the finite fields are such that a first finite field array and a second finite field array are different, a majority of the coefficients are chosen from a smaller of the first finite field array and the second finite field array, and a remainder of the coefficients are chosen from a larger of the first finite field array and the second finite field array;

generating a plurality of output symbols from the combined set of input and redundant symbols, wherein each output symbol is generated as a linear combination of one or more of the combined set of input and redundant symbols with coefficients chosen from finite fields;

using the generated output symbols and an encoding for the data.

72. The non-transitory processor-readable storage medium of claim 71, wherein the number of redundant symbols that can be generated from the set of input symbols, for any set of fixed values for the input symbols, is independent of the field array sizes.

73. The non-transitory processor-readable storage medium of claim 71, wherein the first finite field and the second finite field are each selected from the field set consisting of GF(2), GF(4), GF(16), GF(256).

74. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor to perform a method for decoding data from a transmission received at a destination from a source over a communications channel, the method comprising:

receiving at least some of the plurality of output symbols generated from a combined set of input and redundant symbols, wherein each output symbol is generated as a linear combination of one or more of a combined set of input and redundant symbols with coefficients chosen from finite fields,

wherein the plurality of redundant symbols is generated from the ordered set of input symbols, wherein each redundant symbol is generated based on a set of linear constraints over one or more of the input symbols and other redundant symbols with coefficients over finite fields,

wherein at least one coefficient is a member of a first finite field and at least one other coefficient is a member of a second finite field that is larger than the first finite field, a majority of the coefficients are chosen from the smaller first finite field, and a remainder of the coefficients are chosen from the larger second finite field; and

regenerating the ordered set of input symbols to a desired degree of accuracy from reception of any predetermined number of the output symbols.

75. The non-transitory processor-readable storage medium of claim 74, wherein the number of unique output symbols that could have been generated from the set of input symbols, for any set of fixed values for the input symbols, was independent of the field array sizes.

76. The non-transitory processor-readable storage medium of claim 74, wherein the first finite field is GF(2).

77. The non-transitory processor-readable storage medium of claim 74, wherein the second finite field is GF(256).

78. The non-transitory processor-readable storage medium of claim 74, wherein the second finite field is GF(4).

79. The non-transitory processor-readable storage medium of claim 74, wherein the first finite field is GF(4).

80. The non-transitory processor-readable storage medium of claim 74, wherein the first finite field is GF(16).

81. The non-transitory processor-readable storage medium of claim 74, wherein the second finite field is GF(16).

82. An apparatus for decoding data from a transmission received at a destination from a source over a communications channel, the apparatus comprising:

means for receiving at least some of a plurality of output symbols generated from an ordered set of input symbols that were encoded into the plurality of output symbols wherein each output symbol was generated as a linear combination of one or more of the input symbols with coefficients chosen from finite fields, wherein at least one coefficient is a member of a first finite field and at least one other coefficient is a member of a second finite field that is larger than the first finite field; and

means for regenerating the ordered set of input symbols to a desired degree of accuracy from reception of any predetermined number of the output symbols,

wherein a majority of the coefficients are chosen from the smaller first finite field, and a remainder of the coefficients are chosen from the larger second finite field.

83. An apparatus for decoding data from a transmission received at a destination from a source over a communications channel, the apparatus comprising:

means for receiving at least some of the plurality of output symbols generated from a combined set of input and redundant symbols, wherein each output symbol is generated as a linear combination of one or more of a combined set of input and redundant symbols with coefficients chosen from finite fields,

wherein the plurality of redundant symbols is generated from the ordered set of input symbols, wherein each redundant symbol is generated based on a set of linear constraints over one or more of the input symbols and other redundant symbols with coefficients over finite fields,

wherein at least one coefficient is a member of a first finite field and at least one other coefficient is a member of a second finite field that is larger than the first finite field, a majority of the coefficients are chosen from the smaller first finite field, and a remainder of the coefficients are chosen from the larger second finite field; and

means for regenerating the ordered set of input symbols to a desired degree of accuracy from reception of any predetermined number of the output symbols.