Back to EveryPatent.com
United States Patent | 6,163,870 |
Luby ,   et al. | December 19, 2000 |
An encoded message, includes a plurality of data items and a plurality of redundant data items. Each of the plurality of redundant data items corresponds to a number of the data items, with respective redundant data items corresponding to different numbers of data items.
Inventors: | Luby; Michael G. (Berkeley, CA); Mitzenmacher; Michael D. (Milpitas, CA); Shokrollahi; Mohammad Amin (Rapweiler, DE); Spielman; Daniel A. (Cambridge, MA); Stemann; Volker (Frankfurt, DE) |
Assignee: | Compaq Computer Corporation (Houston, TX) |
Appl. No.: | 965610 |
Filed: | November 6, 1997 |
Current U.S. Class: | 714/755 |
Intern'l Class: | H03M 013/00 |
Field of Search: | 714/755,756,758,752,787 |
4599722 | Jul., 1986 | Mortimer | 371/37. |
4958348 | Sep., 1990 | Berlekamp et al. | 714/775. |
4958350 | Sep., 1990 | Worley, III et al. | 714/785. |
5115436 | May., 1992 | McAuley | 371/35. |
5365530 | Nov., 1994 | Yoshida | 371/37. |
5440670 | Aug., 1995 | Frazier | 706/17. |
5544179 | Aug., 1996 | Hartwell | 714/798. |
5642365 | Jun., 1997 | Murakami et al. | 714/758. |
5719884 | Feb., 1998 | Roth et al. | 714/756. |
Daniel A. Spielman. Linear-Time 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. 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. Gallagher. 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-Time Encodable and Decodable Error-Correcting Codes--Conference Version. STOC 95. Massachusetts Institute of Technology. 10 pages. 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. 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. 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. 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 Caussian Channel--34th Allerton Conference on Communications, Control and Computing. Oct. 4, 1996. pp. 1-10. Zyablov et al. Decoding Complexity of Low-Density Codes For Transmission In A Channel With Erasures--Vol. 10. No. 1, pp. 1-021, 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. |