초록 ▼

Apparatus and methods for generating checksums may process two or more segments of a message in parallel, and may be used with a communications channel having time slots. An apparatus may include a cumulative checksum generator to generate a cumulative checksum for a message, a partial checksum gene

Apparatus and methods for generating checksums may process two or more segments of a message in parallel, and may be used with a communications channel having time slots. An apparatus may include a cumulative checksum generator to generate a cumulative checksum for a message, a partial checksum generator to generate one or more partial checksums from one or more respective message segments, and a speculative checksum generator to generate a speculative checksum for each of one or more time slots. In one aspect, a partial checksum corresponding with an initial segment of the message may be generated from at least an initialization vector. A speculative checksum selector may select a first speculative checksum for use in determining whether the message was transmitted without error. The generating of partial and speculative checksums results in a maximally pipe-lined architecture with speed limited only by a minimal cumulative CRC calculation that is fundamentally unavoidable.

대표청구항 ▼

1. An apparatus for generating checksums for detecting message transmission errors in a communications channel having time slots for transmitting units of data, the messages having one or more message segments, the apparatus comprising: a cumulative checksum generator to generate a cumulative checks

1. An apparatus for generating checksums for detecting message transmission errors in a communications channel having time slots for transmitting units of data, the messages having one or more message segments, the apparatus comprising: a cumulative checksum generator to generate a cumulative checksum for a message, the cumulative checksum generator including: a selecting part to select one or more inputs to include in the cumulative checksum, the inputs being selected from a previously generated cumulative checksum and one or more partial checksums;a state determining part to determine a number of states to advance an input selected for inclusion in the cumulative checksum;an input vector generating part to generate an input vector for each input selected for inclusion in the cumulative checksum by advancing the selected input by the determined number of states; anda superposition part to superimpose the input vectors. 2. The apparatus of claim 1, further comprising a partial checksum generator to generate the one or more partial checksums from one or more respective message segments, wherein a partial checksum corresponding with an initial segment of the message is generated from at least an initialization vector, the initialization vector being generated by superimposing the initial segment and an initialization value. 3. The apparatus of claim 1, further comprising a partial checksum generator to generate the one or more partial checksums, each partial checksum being generated by advancing the state of a corresponding segment of the message. 4. The apparatus of claim 1, further comprising a partial checksum generator to generate the one or more partial checksums from one or more respective message segments, wherein the cumulative checksum is n bits, each partial checksum is n bits and is generated from a corresponding n-bit segment of the message by advancing the segment by n states. 5. The apparatus of claim 1, further comprising a partial checksum generator to generate the one or more partial checksums from one or more respective message segments, wherein the cumulative checksum is n bits, each partial checksum is n bits and is generated from a corresponding m-bit segment of the message by advancing the segment by m states, m being equal to an integer multiple of n. 6. The apparatus of claim 1, further comprising a partial checksum generator to generate one or more partial checksums, wherein the cumulative checksum is n bits, each partial checksum is generated from a corresponding m-bit message segment of the message by generating a first component vector by advancing a first component of the message by n states, generating a second component vector by advancing a second component of the message by m states, and superimposing the first and second component vectors, m being equal to an integer multiple of n. 7. The apparatus of claim 6, wherein the one or more partial checksums includes four partial checksums. 8. The apparatus of claim 6, further comprising: a speculative checksum generator to generate a speculative checksum for each of one or more time slots, the speculative checksum generator including: a selecting component to select one or more inputs to include in the speculative checksum, the inputs being selected from the previously generated cumulative checksum and the one or more partial checksums;a state determining component to determine a number of states to advance an input selected for inclusion in the speculative checksum;a generating component to generate a speculative input vector for each input selected for inclusion in the speculative checksum by advancing the selected input by the determined number of states; anda superimposing component to superimpose the speculative input vectors; anda speculative checksum selector to select a first speculative checksum for use in determining whether the message was transmitted without error if the first speculative checksum was generated for a time slot following a final segment of the message. 9. The apparatus of claim 1, wherein the selecting part: selects the previously generated cumulative checksum for inclusion in the cumulative checksum if the previously generated cumulative checksum was generated from the message, and otherwise excludes the previously generated cumulative checksum from the cumulative checksum. 10. The apparatus of claim 1, wherein the selecting part: selects a partial checksum for inclusion in the cumulative checksum if the partial checksum was generated from a segment of the message, and otherwise excludes the previously generated cumulative checksum from the cumulative checksum. 11. The apparatus of claim 1, further comprising a receiver to receive the message and a checksum generated for the message from the communications channel. 12. The apparatus of claim 1, wherein the state determining part: determines to advance a particular partial checksum by a number of states proportionate to a number of other partial checksums of the one or more partial checksums selected for inclusion in the cumulative checksum that were generated from segments of the message following a segment of the message from which the particular partial checksum was generated. 13. The apparatus of claim 1, wherein the state determining part: determines to advance the previously generated cumulative checksum by a number of states proportionate to a number of partial checksums of the one or more partial checksums selected for inclusion in the cumulative checksum. 14. The apparatus of claim 1, wherein each unit of data is one of a message data unit or a non-message data unit, further comprising: a speculative checksum generator to generate a speculative checksum for each of one or more time slots, the speculative checksum generator including: a selecting component to select one or more inputs to include in the speculative checksum, the inputs being selected from the previously generated cumulative checksum and the one or more partial checksums;a state determining component to determine a number of states to advance an input selected for inclusion in the speculative checksum;a generating component to generate a speculative input vector for each input selected for inclusion in the speculative checksum by advancing the selected input by the determined number of states; anda superimposing component to superimpose the speculative input vectors. 15. The apparatus of claim 14, wherein the selecting component: selects the previously generated cumulative checksum for inclusion in the speculative checksum for a particular time slot if none of the one or more time slots preceding the particular time slot includes a data unit that is an initial segment of a message, and the particular time slot includes a non-message data unit. 16. The apparatus of claim 15, wherein the selecting component: selects a particular partial checksum for inclusion in the speculative checksum for a particular time slot if none of the one or more time slots preceding the particular time slot includes a data unit that is an initial segment of a message, and the particular time slot includes a non-message data unit. 17. The apparatus of claim 15 wherein, the selecting component: selects a particular partial checksum for inclusion in the speculative checksum for a particular time slot if one of the one or more time slots includes a time slot having a data unit that is an initial segment of a message, the time slot having the data unit that is an initial segment of a message precedes the particular time slot, and the particular time slot includes a non-message data unit. 18. The apparatus of claim 15, wherein the state determining component: determines to advance a particular partial checksum by a number of states proportionate to a number of other partial checksums of the one or more partial checksums selected for inclusion in the speculative checksum that were generated from segments of the message following a segment of the message from which the particular partial checksum was generated. 19. The apparatus of claim 15, wherein the state determining component: determines to advance the previously generated cumulative checksum by a number of states proportionate to a number of partial checksums of the one or more partial checksums selected for inclusion in the speculative checksum. 20. The apparatus of claim 15, further comprising a speculative checksum selector to select a first speculative checksum for use in determining whether the message was transmitted without error if the first speculative checksum was generated for a time slot following a final segment of a message. 21. A method for detecting message transmission errors in a communications channel having time slots for transmitting units of data, the messages having one or more message segments, the method comprising: generating a cumulative checksum for a message, the generating of the cumulative checksum including: selecting one or more inputs to include in the cumulative checksum, the inputs being selected from a previously generated cumulative checksum and one or more partial checksums;determining a number of states to advance an input selected for inclusion in the cumulative checksum;generating an input vector for each input selected for inclusion in the cumulative checksum by advancing the selected input by the determined number of states; andsuperimposing the input vectors. 22. The method of claim 21, further comprising generating the one or more partial checksums from one or more respective message segments, wherein a partial checksum corresponding with an initial segment of the message is generated from at least an initialization vector, the initialization vector being generated by superimposing the initial segment and an initialization value. 23. The method of claim 21, further comprising generating the one or more partial checksums, each partial checksum being generated by advancing the state of a corresponding segment of the message. 24. The method of claim 21, further comprising generating the one or more partial checksums from one or more respective message segments, wherein the cumulative checksum is n bits, each partial checksum is n bits and is generated from a corresponding n-bit segment of the message by advancing the segment by n states. 25. The method of claim 21, further comprising generating the one or more partial checksums from one or more respective message segments, wherein the cumulative checksum is n bits, each partial checksum is n bits and is generated from a corresponding m-bit segment of the message by advancing the segment by m states, m being equal to an integer multiple of n. 26. The method of claim 21, further comprising generating one or more partial checksums, wherein the cumulative checksum is n bits, each partial checksum is generated from a corresponding m-bit segment of the message by generating a first component vector by advancing a first component of the message by n states, generating a second component vector by advancing a second component of the message by m states, and superimposing the first and second component vectors, m being equal to an integer multiple of n. 27. The method of claim 26, wherein the one or more partial checksums includes four partial checksums. 28. The method of claim 21, wherein the selecting of one or more inputs to include in the cumulative checksum includes: selecting the previously generated cumulative checksum for inclusion in the cumulative checksum if the previously generated cumulative checksum was generated from the message, and otherwise excluding the previously generated cumulative checksum from the cumulative checksum. 29. The method of claim 21, wherein the selecting of one or more inputs to include in the cumulative checksum includes: selecting a partial checksum for inclusion in the cumulative checksum if the partial checksum was generated from a segment of the message, and otherwise excludes the previously generated cumulative checksum from the cumulative checksum. 30. The method of claim 21, further comprising receiving the message and a checksum generated for the message from the communications channel. 31. The method of claim 21, wherein the determining a number of states to advance an included input includes: determining to advance a particular partial checksum by a number of states proportionate to a number of other partial checksums of the one or more partial checksums selected for inclusion in the cumulative checksum that were generated from segments of the message following a segment of the message from which the particular partial checksum was generated. 32. The method of claim 21, wherein the determining a number of states to advance an included input includes: determining to advance the previously generated cumulative checksum by a number of states proportionate to a number of partial checksums of the one or more partial checksums selected for inclusion in the cumulative checksum. 33. The method of claim 21, further comprising transmitting the message and a checksum generated for the message in the communications channel. 34. The method of claim 21, wherein each unit of data is one of a message data unit or non-message data unit, further comprising: generating a speculative checksum for each of one or more time slots, the generating of a speculative checksum including: selecting one or more inputs to include in the speculative checksum, the inputs being selected from the previously generated cumulative checksum and the one or more partial checksums;determining a number of states to advance an input selected for inclusion in the speculative checksum;generating a speculative input vector for each input selected for inclusion in the speculative checksum by advancing the selected input by the determined number of states; andsuperimposing the speculative input vectors. 35. The method of claim 34, wherein the selecting of one or more inputs to include in a speculative checksum includes: selecting the previously generated cumulative checksum for inclusion in the speculative checksum for a particular time slot if none of the one or more time slots preceding the particular time slot includes a data unit that is an initial segment of a message, and the particular time slot includes a non-message data unit. 36. The method of claim 34, wherein the selecting of one or more inputs to include in a speculative checksum includes: selecting a particular partial checksum for inclusion in the speculative checksum for a particular time slot if none of the time slots of one or more time slots preceding the particular time slot includes a data unit that is an initial segment of a message, and the particular time slot includes a non-message data unit. 37. The method of claim 34, wherein the selecting of one or more inputs to include in a speculative checksum includes: selecting a particular partial checksum for inclusion in the speculative checksum for a particular time slot if one of the one or more time slots includes a time slot having a data unit that is an initial segment of a message, wherein the time slot having the data unit that is an initial segment of a message precedes the particular time slot, and the particular time slot includes a non-message data unit. 38. The method of claim 34, wherein the determining the number of states to advance an input selected for inclusion in the speculative checksum includes: determining to advance a particular partial checksum by a number of states proportionate to a number of other partial checksums of the one or more partial checksums selected for inclusion in the speculative checksum that were generated from segments of the message following a segment of the message from which the particular partial checksum was generated. 39. The method of claim 34, wherein the determining the number of states to advance an input selected for inclusion in the speculative checksum includes: determining to advance the previously generated cumulative checksum by a number of states proportionate to a number of partial checksums of the one or more partial checksums selected for inclusion in the speculative checksum. 40. The method of claim 34, further comprising selecting a first speculative checksum for use in determining whether the message was transmitted without error if the first speculative checksum was generated for a time slot following a final segment of a message.