Patent ID: 6081909
Filing Date: 2000-06-27
Classification: H03M

Abstract:
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; andforming 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.