Granted Patent B2

US 6,895,546 · App. 10/219,546 · Granted May 17, 2005

Abstract

Claims (63)

1. A method of transmitting original (2 (n−1) −1−2t) n-bit data words in a network, in order to provide an error-correcting capability of t number of bytes, comprising:

transforming the (2 (n−1) −1−2t) n-bit words into (2 (n−1) −1−2t) (n−1)-bit words;

encoding the (2 (n−1) −1−2t) (n−1)-bit words with a Reed-Solomon encoder to create 2t (n−1)-bit redundancy words; and

transmitting the 2t (n−1)-bit redundancy words and the original (2 (n−1) −1−2t) n-bit data words to a destination, thereby allowing for decoding.

2. The method of claim 1 , wherein the decoding comprises:

transforming the decoded (2 (n−1) −1−2t) n-bit words into decoded (2 (n−1) −1−2t) (n−1)-bit words;

decoding the (2 (n−1) −1−2t) (n−1)-bit words and the 2t (n−1)-bit redundancy words with a shortened Reed-Solomon decoder to obtain decoded (2 (n−1) −1−2t) (n-1)-bit decoded words;

transforming the (2 (n−1) −1−2t) (n−1)-bit decoded words into (2 (n−1) −1−2t) n-bit transformed decoded words by a predefined code definition; and

comparing the transformed decoded (2 (n−1) −1−2t) n-bit words to the received (2 (n−1) −1−2t) n-bit words to obtain the original (2 (n−1) −1−2t) n-bit words without transmission errors.

3. The method of claim 2 , wherein transforming the (2 (n−1) −1−2t) (n−1)-bit words into (2 (n−1) −1−2t) n-bit words comprises:

adding 0 as a most significant bit (MSB) to each decoded (n−1)-bit word to obtain a transformed decoded n-bit word.

4. The method of claim 2 , wherein comparing the transformed decoded (2 (n−1) −1−2t) n-bit words to the received (2 (n−1) −1−2t) n-bit words to obtain the estimated (2 (n−) −1−2t) n-bit words without transmission errors comprises:

XOR-ing the transformed decoded (2 (n−1) −1−2t) n-bit words to the received (2 (n−1 )−1−2t) n-bit words to obtain intermediary (2 (n−1) −1−2t) n-bit words;

determining whether the number of 1s in the intermediary (2 (n−) −1−2t) n-bit words is less than ┌(n−1)/2┐;

outputting the decoded n-bit word when the determination is positive; and

outputting the complementary of the decoded n-bit word when the determination is negative.

5. A method of transmitting original (L−1−2t) n-bit data words in a network, in order to provide an error-correcting capability of t number of bytes, wherein 0<L<2 (n−1), comprising:

transforming the (L−1−2t) n-bit words into (L−1−2t) (n−1)-bit words;

encoding the (L−1−2t) (n−1)-bit words with a Reed-Solomon encoder to create 2t (n−1)-bit redundancy words; and

transmitting the 2t (n−1)-bit redundancy words and the original (L−1−2t) n-bit data words to a destination, thereby allowing for decoding.

6. A method of transmitting original (2 n −1−2t) (m+n)-bit data words, with an error-correcting capability of t words, comprising:

transforming the (2 n −1−2t) (n+m)-bit words into (2 n −1−2t) pairs of n-bit words and m-bit words;

encoding the (2 n −1−2t) n-bit words with a shortened Reed-Solomon encoder to obtain 2t n-bit redundancy words; and

encoding the (2 n −1−2t) n-bit words and the 2t n-bit redundancy words to obtain (2 n −1−2t)(n+m+k)-bit words and 2t (n+m+k)-bit redundancy words such that each n-bit word is connected to 2 m group members, thereby allowing for decoding.

7. The method of claim 6 , wherein the decoding comprises:

detecting and signing illegal words from the (2 n −1−2t)(n+m+k)-bit words and the 2t (n+m+k)-bit redundancy words;

erasure decoding the (2 n −1−2t) n-bit words and the 2t n-bit redundancy words with a Reed-Solomon decoder using the signed words to obtain decoded (2 n−1−2 t) n-bit words; and

finding among the 2 m group members the (m+n+k)-bit word which has the minimum hamming distance to the received (m+n+k) word.

8. The method of claim 7 , wherein word limitations exist comprising at least one of a group consisting of:

an allowed number of 1s and 0s in the words; and

a required minimum number of transitions in the words.

9. A method of transmitting original (L−1−2t) (m+n)-bit data words, wherein 0<1<2 n , with an error-correcting capability of t words, comprising:

transforming the (L−1−2t) (n+m)-bit words into (L−1−2t) pairs of n-bit words and m-bit words;

encoding the (L−1−2t) n-bit words with a shortened Reed-Solomon encoder to obtain 2t n-bit redundancy words; and

encoding the (L−1−2t) n-bit words and the 2t n-bit redundancy words to obtain (L−1−2t)(n+m+k)-bit words and 2t (n+m+k)-bit redundancy words such that each n-bit word is connected to 2 m group members, thereby allowing for decoding.

10. A computer program product comprising a computer usable medium having control logic stored therein for causing a computer to transmit original (2 (n−1) −1−2t) n-bit data words, with an error-correcting capability of t number of bytes, comprising encode transmission words, comprising:

first computer readable program code means for transforming the (2 (n−1) −1−2t) n-bit words into (2 (n−1) −1−2t) (n−1)-bit words;

second computer readable program code means for encoding the (2 (n−1) −1−2t) (n−1)-bit words with a Reed-Solomon encoder to create 2t (n−1)-bit redundancy words;

third computer readable program code means for transmitting the 2t (n−1)-bit redundancy words and the original (2 (n−1) −1−2t) n-bit data words to a destination;

fourth computer readable program code means for transforming the (2 (n−1) −1−2t) n-bit words into (2 (n−1) −1−2t) (n−1)-bit words;

fifth computer readable program code means for decoding the (2 (n−1) −1−2t) (n−1)-bit words and the 2t (n−1)-bit redundancy words with a Reed-Solomon decoder to obtain decoded (2 (n−1) −1−2t) (n−1)-bit words;

sixth computer readable program code means for transforming the decoded (2 (n−1) −1−2t) (n−1)-bit words into transformed decoded (2 (n−1) −1−2t) n-bit words; and

seventh computer readable program code means for comparing the transformed decoded (2 (n−1) −1−2t) n-bit words to the received (2 (n−1) −1−2t) n-bit words to obtain the estimated (2 (n−1) −1−2t) n-bit words without transmission errors.

11. The computer program product of claim 10 , wherein the sixth computer readable program code means comprises:

adding 0 as a most significant bit (MSB) to each (n−1)-bit non-transformed word to obtain a n-bit transformed word.

12. The computer program product of claim 11 , wherein the seventh computer readable program code means comprises:

XOR-ing the transformed decoded (2 (n−1) −1−2t) n-bit words to the received (2 (n−1) −1−2t) n-bit words to obtain intermediary (2 (n−1) −1−2t) n-bit words;

determining if the number of 1s in the intermediary (2 (n−) −1−2t) n-bit words is less than ┌(n−1)/2┐;

outputting the transformed n-bit word when the number of 1s in the intermediary n-bit word is less than ┌(n−1)/2┐; and

outputting the complement of the transformed decoded n-bit word when the number of 1s in the intermediary word is not less than ┌(n−1)/2┐.

13. A computer program product comprising a computer usable medium having control logic stored therein for causing a computer to transmit original (2 n −1−2t) (n+m)-bit data words, with an error-correcting capability of t number of bytes, comprising:

first computer readable program code means for causing the computer to transform the (2 n −1−2t) (n+m)-bit words into (2 n −1−2t) (n+m)-bit words;

second computer readable program code means for dividing the (2 n −1−2t) (n+m)-bit words into (2 n −1−2t) n-bit words and (2 n −1−2t) m-bit words;

third computer readable program code means for encoding the (2 n −1−2t) (m+n)-bit words with a Reed-Solomon encoder to obtain 2t n-bit redundancy words;

fourth computer readable program code means for encoding the (2 n −1−2t) n-bit words and the 2t n-bit redundancy words to obtain (2 n −1−2t)(n+m+k)-bit words and 2t (n+m+k)-bit redundancy words;

fifth computer readable program code means for transmitting the (2 n −1−2t)(n+m+k)-bit words and the 2t (n+m+k)-bit redundancy words;

sixth computer readable program code means for checking and signing the (2 n −1−2t)(n+m+k)-bit words and the 2t (n+m+k)-bit redundancy words for illegal words;

seventh computer readable program code means for transforming the (2 n −1−2t) (n+m+k)-bit words into n-bit words;

eighth computer readable program code means for decoding the (2 n −1−2t) n-bit words and the 2t n-bit redundancy words with a Reed-Solomon decoder to obtain decoded (2 n −1−2t) n-bit words; and

ninth computer readable program code means for choosing group member words from the 2 m groups that have the smallest hamming distance to the receive (n+m+k)-bit received words to obtain the original (2 n −1−2t) n-bit words without transmission errors.

14. The computer program product of claim 13 , wherein word limitations exist comprising at least one of a group consisting of:

an allowed number of 1s and 0s in the words; and

a required minimum number of transitions in the words.

Assignments (9)