Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Patent
1997-11-06
2000-06-27
Chung, Phung M.
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
G06F 1100
Patent
active
06081909&
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.
REFERENCES:
patent: 4958348 (1990-09-01), Berlekamp et al.
patent: 5115436 (1992-05-01), McAuley
Zyablov et al., Decoding Complexity of Low-Density Codes for Transmission in a Channel with Erasures--vol. 10, No. 1, pp. 10-21, last revision Aug. 20, 1973.
R. Michael Tanner, A Recursive Approach to Low Complexity Codes--Transactions on Information Theory, vol. IT-27, No. 5, Sep. 1981, pp. 533-547.
Jung-Fu Cheng, On the Construction of Efficient Multilevel Coded Modulations--IEEE Intl. Symposium on Information Theory, 1997, pp. 1-12.
MacKay et al., Good Codes based on Very Sparse Matrices--Cavendish Labs, Cambridge, U.K., 7 pages.
Alon et al., Construction of Asymptotically Good Low-Rate Error-Correcting Codes through Pseudo Random Graphs--IEEE Trans. on Information Theory, vol. 38, No. 2, Mar. 1992, pp. 509-516.
Cheng et al., Some High-Rate Near Capacity Codes for the Gaussian Channel--34th Allerton Conference on Communications, Control and Computing, Oct. 4, 1996, pp. 1-10.
Gelfand et al., On the Complexity of Coding--2nd Intl. Symposium on Information Theory, Tsahkadsor Armeia, USSR, Sep. 2-8, 1971, pp. 177-184.
Bassalygo et al., Problems of Complexity in the Theory of Correcting Codes--Plenum Publishing Corp., 1978, pp. 166-175.
Vvedenskaya et al., Systematic Codes That Can Be Realized by Simple Circuits--Plenum Publishing Corp., 1979, 246-254.
A. J. McAuley, Reliable Boardband Communication Using a Burst Erasure Correcting Code--Computer Communication Research Group, Morristown, NJ, pp. 297-306.
E. W. Biersack, Performance Evaluation of Forward Error Correction in ATM Networks--Institut EURECOM, France, Aug. 1992, pp. 248-257.
David J.C. MacKay, Good Error-Correcting Codes based on Very Sparse Matrices--Cavendish Labs, U.K. Nov. 2, 1996, pp. 1-50.
Daniel A. Spielman, Linear-Time Encodable and Decodable Error-Correcting Codes--Dept. of Computer Science, U.C. Berkeley, Berkeley, CA, pp, 1-20.
Sipser et al., Expander Codes--Massachusetts Institute of Technology, Cambridge, MA,, 12 pages.
G. David Forney, Jr., The Forward-Backward Algorithm--Motorola, Inc., Mansfield, MA, Oct. 1, 1986, pp. 432-446.
R. G. Gallager, Low-Density Parity-Check Codes--1963, M.I.T. Press, Cambridge, MA, 106 pages.
Sipser et al., Expander Codes--Journal Version, IEEE IT 1996, Massachusetts Institute of Technology, pp. 1-28.
Daniel A. Spielman, Linear-Tim Encodable and Decodable Error-Correcting Codes--Conference Version, STOC 95, Massachusetts Institute of Technology, 10 pages.
Daniel A. Spielman, Linear-Tim Encodable and Decodable Error-Correcting Codes--Journal Version, IEEE IT 96, Massachusetts Institute of Technology, pp. 1-20.
Daniel A. Spielman, Computationally Efficient Error-Correcting Codes and Holographic Proofs--Yale University (1992), Massachusetts Institute of Technology Jun. 1995, pp. 1-147.
Luigi Rizzo--Effective erassure codes for reliable computer communication protocols--University of Italy, Jan. 9, 1997, pp. 1-10.
Luigi Rizzo,--A Reliable Multicast data Distribution Protocol based on software FEC techniques--University of Italy, Feb. 20, 1997, pp. 1-6.
Luigi Rizzo--On the feasibility of software FEC--University of Italy, Jan. 31, 1997, pp. 1-16.
Luby Michael G.
Mitzenmacher Michael D.
Shokrollahi Mohammad Amin
Spielman Daniel A.
Stemann Volker
Chung Phung M.
Digital Equipment Corporation
LandOfFree
Irregularly graphed encoding technique does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Irregularly graphed encoding technique, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Irregularly graphed encoding technique will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1793621