Error detection for multi-stream communications

• US 7,036,067 B2
• Filed: 03/28/2003
• Issued: 04/25/2006
• Est. Priority Date: 03/28/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: ArrayComm LLC (Ygomi LLC)
• Inventors: Roy, Pulakesh, Boros, Tibor, Bhora, Veerendra
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Abraham, Esaw T.
• Application Number:
  US10/402,717
• Publication Number:
  US 20040193993A1
• Time in Patent Office: 1,124 Days
• Field of Search: 714/752, 714/758, 714/755, 714/781, 714/786
• US Class Current: 714/758
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation
• CPC Class Codes: H04L 1/0059 Convolutional codes
• CPC Class Codes: H04L 1/0061 Error detection codes

Abstract

According to an embodiment of the invention, a method and apparatus are described for error detection for multi-stream communication. Under an embodiment of the invention, a method for producing an error word for a data stream comprises computing an intermediate error word for each of a plurality of data sub-streams, the data stream being equivalent to a concatenation of the plurality of data sub-streams; and combining the intermediate error words to produce the error word for the data stream.

Claims

1. A machine-readable medium having stored thereon data representing sequences of instructions that, when executed by one or more processors, cause the processors to perform operations comprising:

dividing a data stream into a plurality of data sub-streams, the data stream being equivalent to a concatenation of the plurality of data sub-streams;

computing an intermediate error word for each of the plurality of data sub-streams; and

combining the intermediate error words to produce an error word for the data stream.

2. The medium of claim 1, wherein a first data sub-stream is of a different length than a second data sub-stream.

3. The medium of claim 1, wherein the data sub-streams arrive at arbitrary times.

4. The medium of claim 1, wherein the data sub-streams arrive in a different order than the original order of the data sub-streams in the data stream.

5. The medium of claim 1, wherein the error word and the intermediate error words are produced using a linear code.

6. The medium of claim 5, wherein combining the intermediate error words comprises:

applying a linear operator to each intermediate error word by a factor to produce a result; and

adding the results together to produce the error word.

7. The medium of claim 6, wherein the error word and the intermediate error words comprise cyclic redundancy check (CRC) words.

8. The medium of claim 7, wherein combining the intermediate CRC words comprises calculation of:

$c=\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br>B_j<br><br>c_j$

where c is the CRC word, M is the number of data sub-streams, B_j is an operator for the j^th data sub-stream, and c_j is the intermediate CRC word for the j^th data sub-stream.

9. The medium of claim 8, wherein:

the operator B_j for the jth data sub-stream comprises;

$B_j=A^{\underset{i=j+1}{\overset{M}{\sum <br><br>}}<br><br>N_i}$

where A is a state transition matrix for the CRC word generator and N_i is the length of the ith data sub-stream; and

the factor B_M for the M^th data sub-stream of M data sub-streams comprises;

B_M=I_P

wherein I_P is an identity matrix of size P×

P.

10. An error word generator comprising:

a plurality of intermediate error word generators, each intermediate word generator receiving a data sub-stream and producing an intermediate error word for the data sub-stream;

a plurality of linear operators, each linear operator to receive an intermediate error word and produce a result; and

an operator to add the results of the linear operators to produce an error word for a data stream, wherein the data stream is equivalent to a concatenation of the received data sub-streams.

11. The error word generator of claim 10, wherein a first data sub-stream received by the error word generator is of a different length than a second data sub-stream received by the error word generator.

12. The error word generator of claim 10, wherein the data sub-streams received by the error word generator arrive at arbitrary times.

13. The error word generator of claim 10, wherein the data sub-streams received by the error word generator arrive in a different order than the original order of the data sub-streams in the data stream.

14. The error word generator of claim 10, wherein the error word and intermediate error words are CRC words.

15. The error word generator of claim 10, wherein adding the results of the linear operators comprises calculation of:

$c=\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br>B_j<br><br>c_j$

where c is the CRC word, M is the number of data sub-streams, B_j is an operator for the jth data sub-stream, and c_j is the intermediate CRC word for the jth data sub-stream.

16. The error word generator of claim 15, wherein:

the operator B_j for the j^th data sub-stream comprises;

$B_j=A^{\underset{i=j+1}{\overset{M}{\sum <br><br>}}<br><br>N_i}$

where A is a state transition matrix for the CRC word generator and N_i is the length of the i^th data sub-stream; and

the factor B_M for the M^th data sub-stream of M data sub-streams comprises;

B_M=I_P

wherein I_P is an identity matrix of size P×

P.

17. A method for producing an error word for a data stream comprising:

producing a first error word for a data stream;

dividing the data stream into a plurality of data sub-streams;

transmitting the plurality of data sub-streams and the first error word;

receiving the plurality of data sub-streams and the first error word;

producing an intermediate error word for each of the plurality of data sub-streams; and

combining the intermediate error words to produce a second error word for the data stream.

18. The method of claim 17, further comprising comparing the first error word with the second error word.

19. The method of claim 17, wherein a first data sub-stream is of a different length than a second data sub-stream.

20. The method of claim 17, wherein the data sub-streams arrive at arbitrary times.

21. The method of claim 17, wherein the data sub-streams arrive in a different order than the original order of the data sub-streams in the data stream.

22. The method of claim 17, wherein the error word and the intermediate error words are produced using a linear code.

23. The method of claim 22, wherein combining the intermediate error words comprises:

applying a linear operator to each intermediate error word by a factor to produce a result; and

adding the results together to produce the error word.

24. The method of claim 23, wherein the first and second error words and the intermediate error words comprise cyclic redundancy check (CRC) words.

25. The method of claim 17, wherein combining the intermediate error words comprises calculation of:

$c=\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br>B_j<br><br>c_j$

where c is the second CRC word, M is the number of data sub-streams, B_j is an operator for the jth data sub-stream, and c_j is the intermediate CRC word for the jth data sub-stream.

26. The method of claim 25, wherein:

the operator B_j for the j^th data sub-stream comprises;

$B_j=A^{\underset{i=j+1}{\overset{M}{\sum <br><br>}}<br><br><br><br>N_i}$

where A is a state transition matrix for the CRC word generator and N_i is the length of the i^th data sub-stream; and

the factor B_M for the Mth data sub-stream of M data sub-streams comprises;

B_M=I_P

wherein I_P is an identity matrix of size P×

P.

27. An error detection system comprising:

a first error word generator to produce a first error word for a data stream; and

a second error word generator to produce a second error word for the data stream, the second error word generator comprising;

a plurality of intermediate error word generators, each intermediate word generator to receive a portion of the data stream and produce an intermediate error word for the portion of the data stream,

a plurality of linear operators, each linear operator to receive an intermediate error word from an intermediate error word generator and produce a result, and

an operator to add the results from the plurality of linear operators to produce a second error word.

28. The error detection system of claim 27, further comprising a comparator to compare the first error word with the second error word.

29. The error detection system of claim 27, wherein the first and second error words and the intermediate error words are cyclic redundancy (CRC) words.

30. The error detection system of claim 27, wherein adding the results from the plurality of linear operators comprises calculation of:

$c=\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>B_j<br><br>c_j$

where c is the second error word, M is the number of data sub-streams, B_j is an operator for the j^th data sub-stream, and c_j is the intermediate error word for the j^th data sub-stream.

31. The error detection system of claim 30, wherein:

the operator B_j for the j^th data sub-stream comprises;

$B_j=A^{\underset{i=j+1}{\overset{M}{\sum <br><br>}}<br><br><br><br>N_i}$

where A is a state transition matrix for the first error word generator and N_i is the length of the i^th data sub-stream; and

the factor B_M for the Mth data sub-stream of M data sub-streams comprises;

B_M=I_P

wherein I_P is an identity matrix of size P×

P.

32. A method for error detection for a data stream comprising:

calculating a first CRC word for a set of data and appending the first CRC word to the set of data to form a data stream;

dividing the data stream into a first data sub-stream and a second data sub-stream;

transmitting the first data sub-stream and the second data sub-stream;

receiving the first data sub-stream and the second data sub-stream and recovering the first CRC word;

calculating a first intermediate CRC word for the first data sub-stream and a second intermediate CRC word for the second data sub-stream;

multiplying the first intermediate CRC word by a first factor to produce a first product; and

summing the first product and the second intermediate CRC word to produce a second CRC word.

33. The method of claim 32, further comprising comparing the first CRC word with the second CRC word.

34. The method of claim 32, wherein the first data sub-stream is of a different length than the second data sub-stream.

35. The method of claim 32, wherein the first and second data sub-streams arrive at arbitrary times.

36. The method of claim 32, wherein the first and second data sub-streams arrive in a different order than the original order of the data sub-streams in the data stream.

37. The method of claim 32, wherein the first factor comprises:

B₁=A^N2

where A is a state transition matrix for generation of a CRC word and N₂ is the length of the second data sub-stream.

38. An interchangeable computer adapter card comprising:

a master control unit to control operations performed on the card;

a radio section to transmit and receive radio signals to and from the card;

a physical layer processor comprising an error word generator, the error word generator comprising;

a plurality of intermediate error word generators, each intermediate word generator receiving a data sub-stream and producing an intermediate error word for the data sub-stream;

a plurality of linear operators, each linear operator to receive an intermediate error word and produce a result; and

an operator to add the results of the linear operators to produce an error word for a data stream that is equivalent to a concatenation of the received data sub-streams.

39. The adapter card of claim 38, wherein a first data sub-stream received by the error word generator is of a different length than a second data sub-stream received by the error word generator.

40. The adapter card of claim 38, wherein the data sub-streams received by the error word generator arrive at arbitrary times.

41. The adapter card of claim 38, wherein the data sub-streams received by the error word generator arrive in a different order than the original order of the data sub-streams in the data stream.

42. The adapter card of claim 38, wherein the error word and intermediate error words are CRC words.

43. The adapter card of claim 38, wherein adding the results of the linear operators comprises calculation of:

$c=\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>B_j<br><br>c_j$

where c is the CRC word, M is the number of data sub-streams, B_j is an operator for the jth data sub-stream, and c_j is the intermediate CRC word for the jth data sub-stream.

44. The adapter card of claim 43, wherein:

the operator B_j for the j^th data sub-stream comprises;

$B_j=A^{\underset{i=j+1}{\overset{M}{\sum <br><br>}}<br><br><br><br>N_i}$

where A is a state transition matrix for the CRC word generator and N_i is the length of the i^th data sub-stream; and

the factor B_M for the M^th data sub-stream of M data sub-streams comprises;

B_M=I_P

wherein I_P is an identity matrix of size P×

P.