Error detection for multi-stream communications
View Patent ↗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.
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
=
∑
j
=
1
M
B
j
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
∑
i
=
j
+
1
M
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
=
∑
j
=
1
M
B
j
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
∑
i
=
j
+
1
M
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
=
∑
j
=
1
M
B
j
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
∑
i
=
j
+
1
M
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
=
∑
j
=
1
M
B
j
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
∑
i
=
j
+
1
M
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 1 =A N 2
where A is a state transition matrix for generation of a CRC word and N 2 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
=
∑
j
=
1
M
B
j
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
∑
i
=
j
+
1
M
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.