US6081909A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Irregularly graphed encoding technique
Assignee: Compaq Computer Corp
•
Filing: 1997-11-06
•
Granted: 2000-06-27
•
Expires: 2017-11-06
Abstract
Abstract A method of encoding a message including a plurality of data items, includes identifying maximum and minimum numbers of first edges to be associated with data items. A first distribution of different numbers of first edges, ranging from the maximum to the minimum number of first edges, to be associated with the data items is computed. A first associated number of first edges, within the range, is established for each data item, the different numbers of first edges being associated with the data items according to the computed first distribution. A maximum and minimum number of second edges to be associated with redundant data items are identified. A second distribution of numbers of second edges, ranging from the maximum to the minimum number of second edges, to be associated with the redundant data items is computed. An associated number of second edges, within the range, is established for each redundant data item, the different numbers of second edges being associated with the redundant data items according to the determined second distribution. A threshold number of potentially lost/corrupted data items is established. An encoded message is formed with the redundant data items associated with the data items according to the first distribution and with the data items associated with the redundant data items according to the second distribution only if the number of data items which are recoverable or correctable exceeds the threshold.
Inventors
- 👤 Michael G. Luby
- 👤 Mohammad Amin Shokrollahi
- 👤 Volker Stemann
- 👤 Michael D. Mitzenmacher
- 👤 Daniel A. Spielman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 19:31
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
378 words
A method of encoding a message including a plurality of data items, comprising the steps of: identifying a maximum number of first edges and a minimum number of first edges to be associated with the plurality of data items, the maximum number and the minimum number being different positive integer values; computing a first distribution of different numbers of first edges, ranging from the maximum number of first edges to the minimum number of first edges, to be associated with the plurality of data items; establishing a first associated number of first edges for each data item within the plurality of data items, the different numbers of first edges being associated with the plurality of data items according to the computed first distribution; identifying a maximum number of second edges and a minimum number of second edges to be associated with a plurality of redundant data items, the maximum number and the minimum number being different positive integer values; computing a second distribution of different numbers of second edges, ranging from the maximum number of second edges to the minimum number of second edges, to be associated with the plurality of redundant data items; establishing an associated number of second edges for each redundant data item within the plurality of redundant data items, the different numbers of second edges being associated with the plurality of redundant data items according to the determined second distribution; determining a number of the plurality of data items which are one of (i) recoverable if lost and (ii) correctable if corrupted, from an encoded message formed of the plurality of data items and the plurality of redundant data items, with each of the plurality of redundant data items corresponding to a number of the plurality of data items equal to the associated number of second edges; establishing a threshold number of lost/corrupted data items; and forming an encoded message having the plurality of redundant data items corresponding to the plurality of data items according to the first distribution and having the plurality of data items corresponding to the plurality of redundant data items according to the second distribution only if the number of the plurality of data items which are determined to be one of (i) recoverable and (ii) correctable exceeds the threshold.
Claim 2
Independent Claim
378 words
A method of encoding a message including a plurality of data items, comprising the steps of: identifying a maximum number of first edges and a minimum number of first edges to be associated with the plurality of data items, the maximum number and the minimum number being different positive integer values; computing a first distribution of different numbers of first edges, ranging from the maximum number of first edges to the minimum number of first edges, to be associated with the plurality of data items; establishing a first associated number of first edges for each data item within the plurality of data items, the different numbers of first edges being associated with the plurality of data items according to the computed first distribution; identifying a maximum number of second edges and a minimum number of second edges to be associated with a plurality of redundant data items, the maximum number and the minimum number being different positive integer values; computing a second distribution of different numbers of second edges, ranging from the maximum number of second edges to the minimum number of second edges, to be associated with the plurality of redundant data items; establishing an associated number of second edges for each redundant data item within the plurality of redundant data items, the different numbers of second edges being associated with the plurality of redundant data items according to the determined second distribution; determining a number of the plurality of data items which are one of (i) recoverable if lost and (ii) correctable if corrupted, from an encoded message formed of the plurality of data items and the plurality of redundant data items, with each of the plurality of redundant data items corresponding to a number of the plurality of data items equal to the associated number of second edges; establishing a threshold number of lost/corrupted data items; and forming an encoded message having the plurality of redundant data items corresponding to the plurality of data items according to the first distribution and having the plurality of data items corresponding to the plurality of redundant data items according to the second distribution only if the number of the plurality of data items which are determined to be one of (i) recoverable and (ii) correctable exceeds the threshold.
Claim 3
Dependent Claim
20 words
A method of encoding a message according to claim 1, further comprising the step of: transmitting the formed encoded message.
Claim 4
Dependent Claim
42 words
A method of encoding a message according to claim 1, further comprising the step of: prior to forming the encoded message, randomly selecting those of the plurality of data items to which each of the plurality of redundant data items will corresponds.
Claim 5
Dependent Claim
48 words
A method of encoding a message according to claim 1, wherein: the plurality of data items includes a number of data items; the plurality of redundant data items includes a number of redundant data items; and the number of data items exceeds the number of redundant data items.
Claim 6
Independent Claim
283 words
A method of encoding a message including a plurality of data items and a plurality of redundant data items, comprising the steps of: associating each data item within the plurality of data items with a number of first edges, within a first set of different numbers of first edges, the different numbers of first edges being associated with the plurality of data items according to a first distribution; associating each redundant data item within the plurality of redundant data items with a number of second edges, within a second set of different numbers of second edges, the different numbers of second edges being associated with the plurality of redundant data items according to a second distribution; determining a number of the plurality of data items within an encoded message which are one of (i) recoverable if lost and (ii) correctable if corrupted, from an encoded message formed of the plurality of data items and a plurality of redundant data items, each of the plurality of redundant data items corresponding to a number of the plurality of data items equal to the associated number of second edges; establishing a threshold number of lost/corrupted data items; determining a number of the plurality of data items which are one of (i) recoverable and (ii) correctable; and forming an encoded message having the plurality of redundant data items corresponding to the plurality of data items according to the first distribution and having the plurality of data items corresponding to the plurality of redundant data items according to the second distribution only if the number of the plurality of data items which are one of (i) recoverable and (ii) correctable is determined to equal or exceed the threshold.
Claim 7
Independent Claim
283 words
A method of encoding a message including a plurality of data items and a plurality of redundant data items, comprising the steps of: associating each data item within the plurality of data items with a number of first edges, within a first set of different numbers of first edges, the different numbers of first edges being associated with the plurality of data items according to a first distribution; associating each redundant data item within the plurality of redundant data items with a number of second edges, within a second set of different numbers of second edges, the different numbers of second edges being associated with the plurality of redundant data items according to a second distribution; determining a number of the plurality of data items within an encoded message which are one of (i) recoverable if lost and (ii) correctable if corrupted, from an encoded message formed of the plurality of data items and a plurality of redundant data items, each of the plurality of redundant data items corresponding to a number of the plurality of data items equal to the associated number of second edges; establishing a threshold number of lost/corrupted data items; determining a number of the plurality of data items which are one of (i) recoverable and (ii) correctable; and forming an encoded message having the plurality of redundant data items corresponding to the plurality of data items according to the first distribution and having the plurality of data items corresponding to the plurality of redundant data items according to the second distribution only if the number of the plurality of data items which are one of (i) recoverable and (ii) correctable is determined to equal or exceed the threshold.
Claim 8
Dependent Claim
53 words
A method of encoding a message according to claim 5 wherein: the number of the plurality of data items which are recoverable, expressed as a fraction, is α and is determined by applying the formula ρ(1-αλ(1-x))>x for all xε[0,1], where ρ corresponds to the second distribution and λ corresponds to the first distribution.
Claim 9
Dependent Claim
260 words
A method of encoding a message according to claim 5, wherein the first set of different numbers of first edges is bounded by a maximum number of first edges and a minimum number of first edges, and further comprising the steps of: changing the maximum number of first edges; associating each data item within the plurality of data items with a second associated number of first edges, within a second set of different numbers of first edges bounded by the changed maximum number of first edges, the different numbers of first edges within the second set being associated with the plurality of data items according to a third distribution different than the first distribution; associating each redundant data item within the plurality of redundant data items with a second associated number of second edges, within a fourth set of different numbers of second edges, the different numbers within the fourth set of second edges being associated with the plurality of redundant data items according to a fourth distribution different than the second distribution; determining a number of the plurality of data items which are one of (i) recoverable and (ii) correctable; and forming an encoded message having the plurality of redundant data items corresponding to the plurality of data items according to the third distribution and having the plurality of data items corresponding to the plurality of redundant data items according to the fourth distribution only if the number of the plurality of data items which are one of (i) recoverable and (ii) correctable is determined to exceed the threshold.
Claim 10
Dependent Claim
101 words
A method of encoding a message according to claim 7, wherein the encoded message having the plurality of redundant data items corresponding to the plurality of data items according to the first distribution and the plurality of data items corresponding to the plurality of redundant data items according to the second distribution has a length different than the length of the encoded message having the plurality of redundant data items corresponding to the plurality of data items according to the third distribution and the plurality of data items corresponding to the plurality of redundant data items according to the fourth distribution.
Claim 11
Dependent Claim
46 words
A method of encoding a message according to claim 7, wherein the sum of the number of first edges associated with the plurality of data items is different than the sum of the second associated number of first edges associated with the plurality of data items.
Claim 12
Dependent Claim
48 words
A method of encoding a message according to claim 7, wherein the sum of the number of second edges associated with the plurality of redundant data items is different than the sum of the second associated number of second edges associated with the plurality of redundant data items.
Claim 13
Dependent Claim
48 words
A method of encoding a message according to claim 5, wherein: the plurality of data items includes a number of data items; the plurality of redundant data items includes a number of redundant data items; and the number of data items exceeds the number of redundant data items.
Claim 14
Independent Claim
288 words
A method of encoding a message, comprising the steps of: identifying a maximum number of first edges and a minimum number of first edges to be associated with a plurality of data items, the maximum number and the minimum number being different positive integer values; determining a distribution of different numbers of first edges, ranging from the maximum number of first edges to the minimum number of first edges, to be associated with the plurality of data items; establishing an associated number of first edges for each data item within the plurality of data items, the different numbers of first edges being associated with the plurality of data items according to the distribution; identifying a maximum number of second edges and a minimum number of second edges to be associated with a plurality of redundant data items, the maximum number and the minimum number being different positive integer values; determining a Poisson distribution of different numbers of second edges, ranging from the maximum number of second edges to the minimum number of second edges, to be associated with the plurality of redundant data items; establishing an associated number of second edges for each redundant data item within the plurality of redundant data items, the different numbers of second edges being associated with the plurality of redundant data items according to the Poisson distribution; connecting each second edge to a respective first edge; forming the plurality of redundant data items such that each of the plurality of redundant data items represents those of the plurality of data items to which the redundant data item is connected by first and second edges; and forming an encoded message including the plurality of data items and the plurality of redundant data items.
Claim 15
Independent Claim
288 words
A method of encoding a message, comprising the steps of: identifying a maximum number of first edges and a minimum number of first edges to be associated with a plurality of data items, the maximum number and the minimum number being different positive integer values; determining a distribution of different numbers of first edges, ranging from the maximum number of first edges to the minimum number of first edges, to be associated with the plurality of data items; establishing an associated number of first edges for each data item within the plurality of data items, the different numbers of first edges being associated with the plurality of data items according to the distribution; identifying a maximum number of second edges and a minimum number of second edges to be associated with a plurality of redundant data items, the maximum number and the minimum number being different positive integer values; determining a Poisson distribution of different numbers of second edges, ranging from the maximum number of second edges to the minimum number of second edges, to be associated with the plurality of redundant data items; establishing an associated number of second edges for each redundant data item within the plurality of redundant data items, the different numbers of second edges being associated with the plurality of redundant data items according to the Poisson distribution; connecting each second edge to a respective first edge; forming the plurality of redundant data items such that each of the plurality of redundant data items represents those of the plurality of data items to which the redundant data item is connected by first and second edges; and forming an encoded message including the plurality of data items and the plurality of redundant data items.
Claim 16
Dependent Claim
19 words
A method of encoding a message according to claim 12, wherein the minimum number of first edges is 2.
Claim 17
Dependent Claim
52 words
A method of encoding a message according to claim 12, wherein: the maximum number of first edges is D+1; a constant N equals 1+1/D; and the distribution of numbers of first edges is computed by N/i(i-1), where i is a number of first edges within the range of numbers of first edges.
Claim 18
Dependent Claim
83 words
A method of encoding a message according to claim 12, wherein: the plurality of data items includes a first number of data items; the plurality of redundant data items includes a second number of redundant data items; the first number is larger than the second number; and the maximum number of second edges is equal to the maximum number of first edges multiplied by a factor, the numerator of which is the first number and the denominator of which is the second number.
Claim 19
Dependent Claim
19 words
A method of encoding a message according to claim 12, wherein the minimum number of second edges is 1.
Claim 20
Dependent Claim
111 words
A method of encoding a message according to claim 12, wherein: the associated number of first edges for each data item within the plurality of data items is established by random assignment of the different numbers of first edges to respective of the plurality of data items so as to provide the distribution of the numbers of first edges; and the associated number of second edges for each redundant data items within the plurality of redundant data items is established by random assignment of the numbers of second edges to respective of the plurality of redundant data items so as to provide the Poisson distribution of the numbers of second edges.
Claim 21
Dependent Claim
25 words
A method of encoding a message according to claim 12, wherein each second edge is randomly connected to a respective one of the first edges.
Claim 22
Dependent Claim
44 words
A method of encoding a message according to claim 12, wherein each of the plurality of redundant data items is an exclusive-or of the those of the plurality of data items to which the redundant data item is connected by first and second edges.
Claim 23
Independent Claim
219 words
A method of encoding a message, comprising the steps of: determining a first distribution of different numbers of first edges ranging from a maximum number of first edges to a minimum number of first edges, to be associated with a plurality of data items; establishing an associated number of first edges for each data item within the plurality of data items, the different numbers of first edges being associated with the plurality of data items according to the first distribution; determining a second distribution of different numbers of second edges, ranging from a maximum number of second edges to a minimum number of second edges, to be associated with the plurality of redundant data items; establishing an associated number of second edges for each redundant data item within the plurality of redundant data items, the different numbers of second edges being associated with the plurality of redundant data items according to the second distribution; connecting each second edge to a respective first edge; forming the plurality of redundant data items such that each of the plurality of redundant data items represents those of the plurality of data items to which the redundant data item is connected by first and second edges; and forming an encoded message including the plurality of data items and the plurality of redundant data items.
Claim 24
Independent Claim
219 words
A method of encoding a message, comprising the steps of: determining a first distribution of different numbers of first edges ranging from a maximum number of first edges to a minimum number of first edges, to be associated with a plurality of data items; establishing an associated number of first edges for each data item within the plurality of data items, the different numbers of first edges being associated with the plurality of data items according to the first distribution; determining a second distribution of different numbers of second edges, ranging from a maximum number of second edges to a minimum number of second edges, to be associated with the plurality of redundant data items; establishing an associated number of second edges for each redundant data item within the plurality of redundant data items, the different numbers of second edges being associated with the plurality of redundant data items according to the second distribution; connecting each second edge to a respective first edge; forming the plurality of redundant data items such that each of the plurality of redundant data items represents those of the plurality of data items to which the redundant data item is connected by first and second edges; and forming an encoded message including the plurality of data items and the plurality of redundant data items.
Claim 25
Dependent Claim
19 words
A method of encoding a message according to claim 20, wherein the minimum number of first edges is 2.
Claim 26
Dependent Claim
41 words
A method of encoding a message according to claim 20, wherein: the distribution of numbers of first edges is computed by 2 i +1, where i is a number of first edges within the range of different numbers of first edges.
Claim 27
Dependent Claim
53 words
A method of encoding a message according to claim 20, wherein: the maximum number of first edges is D+1; a constant N equals +1/D; and the distribution of numbers of first edges is computed by N/i(i-1) where i is a number of first edges within the range of different numbers of first edges.
Claim 28
Dependent Claim
23 words
A method of encoding a message according to claim 20, wherein: the numbers of first edges includes 3, 5, 9, 17 and 33.
Claim 29
Dependent Claim
19 words
A method of encoding a message according to claim 20, wherein: the numbers of first edges are distributed equally.
Claim 30
Dependent Claim
112 words
A method of encoding a message according to claim 20, wherein: the associated number of first edges for each data item within the plurality of data items is established by random assignment of the different numbers of first edges to respective of the plurality of data items so as to provide the first distribution of the numbers of first edges; and the associated number of second edges for each redundant data item within the plurality of redundant data items is established by random assignment of the different numbers of second edges to respective of the plurality of data items so as to provide the second distribution of the numbers of second edges.
Claim 31
Dependent Claim
70 words
A method of encoding a message according to claim 20, wherein: the second distribution of different numbers of second edges is determined by computing ρ using the formula ρ(1-αλ(1-x))>x for all xε[0,1], where ρ corresponds to the second distribution of different numbers of second edges, λ corresponds to the first distribution of different numbers of first edges, and α corresponds to the maximum number of data items which are recoverable.
Claim 32
Dependent Claim
41 words
A method of encoding a message according to claim 27, wherein the computation of ρ is performed using a standard binary search for α using linear programming to determine if there is a ρ corresponding to α for a fixed λ.
Claim 33
Dependent Claim
27 words
A method of encoding a message according to claim 27, wherein the computation of ρ is limited to a selected range of different numbers of second edges.
Claim 34
Dependent Claim
27 words
A method of encoding a message according to claim 27, wherein the computation of ρ is limited to a selected number of different numbers of second edges.
Claim 35
Dependent Claim
43 words
A method of encoding a message according to claim 27, wherein: ρ is initially computed using a first number of x values and is then computed using a second number of x values; and the second number is greater than the first number.
Claim 36
Dependent Claim
32 words
A method of encoding a message according to claim 20, wherein the second distribution of different numbers of second edges is determined such that a maximum number of data items are recoverable.
Claim 37
Dependent Claim
83 words
A method of encoding a message according to claim 20, wherein: the plurality of data items includes a first number of data items; the plurality of redundant data items includes a second number of redundant data items; the first number being larger than the second number; and the maximum number of second edges is equal to the maximum number of first edges multiplied by a factor, the numerator of which is the first number and the denominator of which is the second number.
Claim 38
Dependent Claim
25 words
A method of encoding a message according to claim 20, wherein each second edge is randomly connected to a respective one of the first edges.
Claim 39
Dependent Claim
41 words
A method of encoding a message according to claim 20, wherein each of the plurality of redundant data items is an exclusive-or of the plurality of data items to which the redundant data item is connected by first and second edges.
References Cited (Backward Citations)
US4958348A
Cited
US5115436A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-06-27 | 2003-12-27 | 2004-06-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-06-27 | 2007-12-27 | 2008-06-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-06-27 | 2011-12-27 | 2012-06-27 | $7700.00 | Window Closed / Lapsed |