US6073250A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Loss resilient decoding technique
Assignee: Compaq Computer Corp
•
Filing: 1997-11-06
•
Granted: 2000-06-06
•
Expires: 2017-11-06
Abstract
Abstract An encoded message includes a plurality of data items and a plurality of redundant data items. Each of the redundant data items is associated with more than one of the data items. To decode the encoded message, a reduced first redundant data item is reduced to correspond to only one data item. This data item is replaced with the reduced first redundant data item. A second redundant data item is reduced, using the replaced data item, to correspond to only a second of data item. The second data item is replaced with the second redundant data item to decode the encoded message.
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 02:06
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0056; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/17; H03M13/63; H03M13/6312; H03M7/00; H03M7/30; H04L1/0045
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
185 words
A method of decoding an encoded message which includes a plurality of data items and a plurality of redundant data items each associated with more than one of the plurality of data items, comprising the steps of: reducing a first of the plurality of redundant data items to correspond to only a first of the plurality of data items; replacing the first of the plurality of data items with the reduced first of the plurality of redundant data items; reducing a second of the plurality of redundant data items, to correspond to only a second of the plurality of data items; and replacing the second of the plurality of data items with the reduced second of the plurality of redundant data items to decode the encoded message; wherein each of the plurality of data items is associated with a number of the plurality of redundant data items, the number being different for different ones of the plurality of data items; and each of the plurality of redundant data items is associated with particular one of the plurality of data items and the association is random.
Claim 2
Independent Claim
185 words
A method of decoding an encoded message which includes a plurality of data items and a plurality of redundant data items each associated with more than one of the plurality of data items, comprising the steps of: reducing a first of the plurality of redundant data items to correspond to only a first of the plurality of data items; replacing the first of the plurality of data items with the reduced first of the plurality of redundant data items; reducing a second of the plurality of redundant data items, to correspond to only a second of the plurality of data items; and replacing the second of the plurality of data items with the reduced second of the plurality of redundant data items to decode the encoded message; wherein each of the plurality of data items is associated with a number of the plurality of redundant data items, the number being different for different ones of the plurality of data items; and each of the plurality of redundant data items is associated with particular one of the plurality of data items and the association is random.
Claim 3
Dependent Claim
124 words
A method of decoding according to claim 1, wherein: each of the plurality of redundant data items has a value equal to a correct value of a combination of its associated data items; the reduction of the first of the plurality of redundant data items is performed by combining its value with a value of a combination of its associated data items, the combination excluding the first of the plurality of data items; and the reduction of the second of the plurality of redundant data items is performed by combining its value with a value of the combination of its associated data items, the combination including the first of the plurality of data items and excluding the second of the plurality of data items.
Claim 4
Dependent Claim
14 words
A method of decoding according to claim 2, wherein the combination is an exclusive-or.
Claim 5
Dependent Claim
124 words
A method of decoding according to claim 1, wherein: a maximum number of the plurality of redundant data items associated with each of the plurality of data items equals D+1; a numeric N=1+(1/D) a first number of the plurality of redundant data items associated with the plurality of data items equals i; a second number of the plurality of redundant data items associated with the plurality of data items equals i'; a first fractional portion of the plurality of data items associated with the first number of the plurality of redundant data items is computed by N/[i(i-1)]; and a second fractional portion of the plurality of data items associated with the second number of the plurality of redundant data items is computed by N/[i'(i'-1)].
Claim 6
Dependent Claim
109 words
A method of decoding according to claim 1, wherein: each of the plurality of redundant data items within a first fractional portion of the plurality of redundant data items is associated with a first number of the plurality of data items and each of the plurality of redundant data items within a second fractional portion of the plurality of redundant data items is associated with a second number of the plurality of data items and a number of the plurality of redundant data items within each of the first fractional portion and the second fractional portion of the plurality of reduced data items is based upon a Poisson distribution.
Claim 7
Dependent Claim
108 words
A method of decoding according to claim 1, wherein: each of the plurality of redundant data items within a first fractional portion of the plurality of redundant data items is associated with a first number of the plurality of data items and each of the plurality of redundant data items within a second fractional portion of the plurality of redundant data items is associated with a second number of the plurality of data items and a number of the plurality of redundant data items within each of the first fractional portion and the second fractional portion of the plurality of redundant data items is determined using linear programming.
Claim 8
Dependent Claim
51 words
A method of decoding according to claim 1, wherein: respective ones of the plurality of data items are associated with differing numbers of the plurality of redundant data items; and the differing numbers of the plurality of redundant data items is determined by 2 i +1, where i equals an integer.
Claim 9
Dependent Claim
33 words
A method of decoding according to claim 7, wherein: respective fractional portions of the plurality of data items are associated with each of the differing numbers of the plurality of redundant data items.
Claim 10
Dependent Claim
51 words
A method of decoding according to claim 1, wherein: respective portions of the plurality of data items are associated with each of a differing number of the plurality of redundant data items, the respective portions being proportional to one divided by an associated number of the plurality of redundant data items.
Claim 11
Dependent Claim
173 words
A method of decoding according to claim 1, wherein the plurality of redundant data items is a plurality of first redundant data items, the encoded message further includes a plurality of second redundant data items each associated with more than one of the plurality of first redundant data items, and further comprising the steps of: reducing a first of the plurality of second redundant data items to correspond to only a third of the plurality of first redundant data items; replacing the third of the plurality of first redundant data items with the reduced first of the plurality of second redundant data items; reducing a second of the plurality of second redundant data items, using the replaced third of the plurality of first redundant data items, to correspond to only a fourth of the plurality of first redundant data items; and replacing the fourth of the plurality of first redundant data items with the reduced second of the plurality of second redundant data items to decode the plurality of first redundant data items.
Claim 12
Dependent Claim
72 words
A method of decoding according to claim 10, wherein: the plurality of data items consist of a first number of data item; the plurality of first redundant data items consist of a second number of data items; the plurality of second redundant data items consist of a third number of data items; and the first number is greater than the second number and the second number is greater than the third number.
Claim 13
Dependent Claim
36 words
A method of decoding according to claim 11, wherein: the first number is greater than the second number by a factor and the second number is greater than the third number by a substantially similar factor.
Claim 14
Dependent Claim
15 words
A method of decoding according to claim 12, wherein the factor is a non-integer number.
Claim 15
Independent Claim
170 words
A method of decoding an encoded message which includes a plurality of data items and a plurality of redundant data items each associated with more than one of the plurality of data items, comprising the steps of: reducing a first of the plurality of redundant data items to correspond to only a first of the plurality of data items; replacing the first of the plurality of data items with the reduced first of the plurality of redundant data items; reducing a second of the plurality of redundant data items, to correspond to only a second of the plurality of data items; and replacing the second of the plurality of data items with the reduced second of the plurality of redundant data items to decode the encoded message; wherein respective ones of the plurality of data items are associated with differing numbers of the plurality of redundant data items; and the differing numbers of the plurality of redundant data items is determined by 2 i +1, where i equals an integer.
Claim 16
Independent Claim
170 words
A method of decoding an encoded message which includes a plurality of data items and a plurality of redundant data items each associated with more than one of the plurality of data items, comprising the steps of: reducing a first of the plurality of redundant data items to correspond to only a first of the plurality of data items; replacing the first of the plurality of data items with the reduced first of the plurality of redundant data items; reducing a second of the plurality of redundant data items, to correspond to only a second of the plurality of data items; and replacing the second of the plurality of data items with the reduced second of the plurality of redundant data items to decode the encoded message; wherein respective ones of the plurality of data items are associated with differing numbers of the plurality of redundant data items; and the differing numbers of the plurality of redundant data items is determined by 2 i +1, where i equals an integer.
Claim 17
Independent Claim
170 words
A method of decoding an encoded message which includes a plurality of data items and a plurality of redundant data items each associated with more than one of the plurality of data items, comprising the steps of: reducing a first of the plurality of redundant data items to correspond to only a first of the plurality of data items; replacing the first of the plurality of data items with the reduced first of the plurality of redundant data items; reducing a second of the plurality of redundant data items, to correspond to only a second of the plurality of data items; and replacing the second of the plurality of data items with the reduced second of the plurality of redundant data items to decode the encoded message; wherein respective portions of the plurality of data items are associated with each of a differing number of the plurality of redundant data items, the respective portions being proportional to one divided by an associated number of the plurality of redundant data items.
Claim 18
Independent Claim
170 words
A method of decoding an encoded message which includes a plurality of data items and a plurality of redundant data items each associated with more than one of the plurality of data items, comprising the steps of: reducing a first of the plurality of redundant data items to correspond to only a first of the plurality of data items; replacing the first of the plurality of data items with the reduced first of the plurality of redundant data items; reducing a second of the plurality of redundant data items, to correspond to only a second of the plurality of data items; and replacing the second of the plurality of data items with the reduced second of the plurality of redundant data items to decode the encoded message; wherein respective portions of the plurality of data items are associated with each of a differing number of the plurality of redundant data items, the respective portions being proportional to one divided by an associated number of the plurality of redundant data items.
Claim 19
Dependent Claim
61 words
A method of decoding according to claim 15, wherein: each of the plurality of data items is associated with a number of the plurality of redundant data items, the number being different for different ones of the plurality of data items; and each of the plurality of redundant data items is associated with particular data items and the association is random.
References Cited (Backward Citations)
US4564945A
Cited
US4653052A
Cited
US4958348A
Cited
US4989211A
Cited
US5134583A
Cited
US5115436A
Cited
US5265104A
Cited
US5684810A
Cited
US5712861A
Cited
US5617541A
Cited
US5719884A
Cited
US5819001A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-06-06 | 2003-12-06 | 2004-06-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-06-06 | 2007-12-06 | 2008-06-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-06-06 | 2011-12-06 | 2012-06-06 | $7700.00 | Window Closed / Lapsed |