Loss resilient decoding technique
OwnerMichael G. Luby, Mohammad Amin Shokrollahi +3inventors
InventorsMichael G. Luby, Mohammad Amin Shokrollahi, Volker Stemann, Michael D. Mitzenmacher, Daniel A. Spielman
Life of this patent
Estimating the term…
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.
Claims16
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.
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.sup.i +1, where i equals an integer.
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.
Dependencies are inferred from the claim text.