US6081918A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Loss resilient code with cascading series of redundant layers
Assignee: Individual
•
Filing: 1997-11-06
•
Granted: 2000-06-27
•
Expires: 2017-11-06
Abstract
Abstract An encoded loss resilient message includes data items, first redundant data items, and second redundant data items. Each of the first redundant data items corresponds to one or more associated data items. Each of the second redundant data items corresponds to one or more associated first redundant data items. The number of data items is greater than the number of first redundant data items which is in turn greater than the number of second redundant data items, thereby providing a cascading series of redundant data items.
Inventors
- 👤 Daniel A. Spielman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 11:40
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0045; H03; H03M; H03M13/00; H03M13/03; H04L1/0056
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
81 words
An encoded loss resilient message, comprising: a first number of data items; a second number of first erasure correcting redundant data items, each of the first redundant data items corresponding to one or more associated data items within the first number of data items; and a third number of second erasure correcting redundant data items, each of the second redundant data items corresponding to one or more associated first redundant data items within the second number of first redundant data items.
Claim 2
Dependent Claim
81 words
An encoded loss resilient message, comprising: a first number of data items; a second number of first erasure correcting redundant data items, each of the first redundant data items corresponding to one or more associated data items within the first number of data items; and a third number of second erasure correcting redundant data items, each of the second redundant data items corresponding to one or more associated first redundant data items within the second number of first redundant data items.
Claim 3
Dependent Claim
19 words
An encoded loss resilient message according to claim 1, wherein the first number is greater than the second number.
Claim 4
Dependent Claim
20 words
An encoded loss resilient message according to claim 1, wherein the third number is no greater than the second number.
Claim 5
Dependent Claim
29 words
An encoded loss resilient message according to claim 1, wherein the first number of data items is substantially equal to a total number of erasure correcting redundant data items.
Claim 6
Dependent Claim
52 words
An encoded loss resilient message according to claim 1, wherein: each of the first redundant data items corresponds to an equal number, greater than 1, of the data items; and and each of the second redundant data items corresponds to an equal number, greater than 1, of the first redundant data items.
Claim 7
Dependent Claim
45 words
An encoded loss resilient message according to claim 1, wherein: respective of the first redundant data items are associated with different numbers of the data items; and respective of the second redundant data items are associated with different numbers of the first redundant data items.
Claim 8
Dependent Claim
43 words
An encoded loss resilient message according to claim 1, wherein: each of the first redundant data items corresponds to randomly selected of the data items; and each of the second redundant data items corresponds to randomly selected of the first redundant data items.
Claim 9
Dependent Claim
37 words
An encoded loss resilient message according to claim 1, wherein the first number is larger than the second number by a factor and the second number is larger than the third number by a substantially similar factor.
Claim 10
Dependent Claim
16 words
An encoded loss resilient message according to claim 8, wherein the factor is a non-integer number.
Claim 11
Dependent Claim
54 words
An encoded loss resilient message according to claim 1, wherein: a first of the first redundant data items corresponds to a fourth number of the data items; a second of the first redundant data items corresponds to a fifth number of the data items; and the fifth number is different than the fourth number.
Claim 12
Dependent Claim
58 words
An encoded loss resilient message according to claim 10, wherein: a first of the second redundant data items corresponds to a sixth number of the first redundant data items; a second of the second redundant data items corresponds to a seventh number of the first redundant data items; and the seventh number is different than the sixth number.
Claim 13
Dependent Claim
55 words
An encoded loss resilient message according to claim 1, wherein a value of each of the first redundant data items represents a combination of data within its associated data items, and a value of each of the second redundant data items represents a combination within the associated values within its associated first redundant data items.
Claim 14
Dependent Claim
15 words
An encoded loss resilient message according to claim 12, wherein the combination is an exclusive-or.
Claim 15
Dependent Claim
26 words
An encoded loss resilient message according to claim 1, wherein the correspondence between the first redundant data items and the second redundant data items is sparse.
Claim 16
Dependent Claim
26 words
An encoded loss resilient message according to claim 14, wherein the correspondence between the second redundant data items and the third redundant data items is sparse.
Claim 17
Dependent Claim
29 words
An encoded loss resilient message according to claim 1, wherein: one of the second redundant data items corresponds to only its associated one or more first redundant data items.
Claim 18
Independent Claim
103 words
A method of encoding a loss resilient message including a first number of data items, comprising the steps of: forming a second number of first erasure correcting redundant data items, each of the first redundant data items corresponding to associated data items, the second number being less than the first number; forming a third number of second erasure correcting redundant data items, each of the second redundant data items corresponding to associated first redundant data items; and combining the data items, the first redundant data items, and the second redundant data items, to form an encoded loss resilient message in a cascading series.
Claim 19
Independent Claim
103 words
A method of encoding a loss resilient message including a first number of data items, comprising the steps of: forming a second number of first erasure correcting redundant data items, each of the first redundant data items corresponding to associated data items, the second number being less than the first number; forming a third number of second erasure correcting redundant data items, each of the second redundant data items corresponding to associated first redundant data items; and combining the data items, the first redundant data items, and the second redundant data items, to form an encoded loss resilient message in a cascading series.
Claim 20
Dependent Claim
17 words
A method according to claim 17, wherein the third number is no greater than the second number.
Claim 21
Dependent Claim
34 words
A method according to claim 17, wherein the first number is larger than the second number by a factor and the second number is larger than the third number by a substantially similar factor.
Claim 22
Dependent Claim
13 words
A method according to claim 19, wherein the factor is a non-integer number.
Claim 23
Dependent Claim
55 words
A method according to claim 17, wherein: a first of the first redundant data items is associated with a fourth number of the data items; a second of the first redundant data items is associated with a fifth number of the plurality of data items; and the fourth number is different than the fifth number.
Claim 24
Dependent Claim
57 words
A method according to claim 21, wherein: a first of the second redundant data items is associated with a sixth number of the first redundant data items; a second of the second redundant data items is associated with a seventh number of the first redundant data items; and the sixth number is different than the seventh number.
Claim 25
Dependent Claim
51 words
A method according to claim 17, wherein a value of each of the first redundant data items represents an exclusive-or of data within its associated data items, and the value of each of the second redundant data items represents an exclusive-or of the values of its associated first redundant data items.
Claim 26
Dependent Claim
55 words
A method according to claim 17, wherein: the data items, the first redundant data items and the second redundant data items are combined to form an encoded loss resilient message; and the combined data items are in a sequence with the data items, the first redundant data items and the second redundant data items interleaved.
Claim 27
Dependent Claim
23 words
A method according to claim 17, wherein the correspondence of the first redundant data items with the data items is a sparse graphing.
Claim 28
Dependent Claim
23 words
A method according to claim 17, wherein the correspondence of the second redundant data items with the data items is a sparse graphing.
Claim 29
Dependent Claim
42 words
A method of encoding a loss resilient message according to claim 17, wherein: the second redundant data items include a particular second redundant data item; and the particular second redundant data item is formed using only its associated first redundant data items.
Claim 30
Dependent Claim
79 words
An encoded loss resilient message, comprising: a plurality of data items; and multiple layers of redundant data items; wherein each redundant data item within a first of the multiple layers of erasure correcting redundant data items corresponds to one or more data items, and each redundant data item within others of the multiple layers of redundant data items corresponds to one or more redundant data items in a preceding adjacent one of the multiple layers of redundant data items.
Claim 31
Dependent Claim
79 words
An encoded loss resilient message, comprising: a plurality of data items; and multiple layers of redundant data items; wherein each redundant data item within a first of the multiple layers of erasure correcting redundant data items corresponds to one or more data items, and each redundant data item within others of the multiple layers of redundant data items corresponds to one or more redundant data items in a preceding adjacent one of the multiple layers of redundant data items.
Claim 32
Dependent Claim
26 words
An encoded loss resilient message, according to claim 28, wherein the multiple layers of redundant data items exceeds two layers of erasure correcting redundant data items.
Claim 33
Dependent Claim
30 words
An encoded loss resilient message, according to claim 28, wherein the multiple layers of redundant data items includes an arbitrarily selected number of layers of erasure correcting redundant data items.
Claim 34
Dependent Claim
29 words
A method according to claim 28, wherein the first of the multiple layers of redundant data items is graphed to the plurality of data items using a sparse graph.
Claim 35
Dependent Claim
42 words
An encoded loss resilient message according to claim 28, wherein one of the redundant data items within the other multiple layers of redundant data items is determined from only its corresponding one or more redundant data items in the preceding adjacent layer.
Claim 36
Independent Claim
97 words
A method of encoding a loss resilient message including a plurality of data items, comprising the steps of: forming a first layer of erasure correcting redundant data items such that each redundant data item within the first layer of redundant data items corresponds to one or more data items; and forming at least one other layer of erasure correcting redundant data items such that each redundant data item within each of the at least one other layer of redundant data items corresponds to one or more redundant data items within an adjacent layer of redundant data items.
Claim 37
Independent Claim
97 words
A method of encoding a loss resilient message including a plurality of data items, comprising the steps of: forming a first layer of erasure correcting redundant data items such that each redundant data item within the first layer of redundant data items corresponds to one or more data items; and forming at least one other layer of erasure correcting redundant data items such that each redundant data item within each of the at least one other layer of redundant data items corresponds to one or more redundant data items within an adjacent layer of redundant data items.
Claim 38
Dependent Claim
35 words
A method of encoding a loss resilient message, according to claim 33, wherein the at least one other layer of redundant data items is at least two other layers of erasure correcting redundant data items.
Claim 39
Dependent Claim
30 words
A method of encoding a loss resilient message, according to claim 33, further comprising the step of: arbitrarily selecting a total number of layers of erasure correcting redundant data items.
Claim 40
Dependent Claim
29 words
A method of encoding a loss resilient message, according to claim 33, wherein the first layer of redundant data items is sparsely mapped to the plurality of data items.
Claim 41
Dependent Claim
47 words
A method of encoding a loss resilient message according to claim 33, wherein: the at least one other layer of redundant data items includes a particular redundant data item; and the particular redundant data item is formed using only its corresponding one or more redundant data items.
References Cited (Backward Citations)
US5014274A
Cited
US4958384A
Cited
US5136592A
Cited
US5115436A
Cited
US5325371A
Cited
US5491701A
Cited
US5671237A
Cited
US5517508A
Cited
US5838696A
Cited
US5872799A
Cited
US5870414A
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 |