Error detection structure and method using partial polynomial check

Claim 2

Structure for detecting an error in a stream of bits comprising: at a transmit end: means for generating a transmit end error checkword from said stream of bits, said transmit end error checkword being updated in response to subsequent bits from said stream of bits, at least one bit of said transmit end error checkword being a function of previous bits in said stream of bits; means for generating a composite bit stream, said composite bit stream comprising: a first segment of said stream of bits, a subset of said transmit end error checkword updated in response to said first segment of bits from said stream of bits, said subset including said at least one bit; and at a receive end: means for receiving said composite bit stream and generating a receive end error checkword in response to said composite bit stream; means for testing said composite bit stream for errors comprising: means for recognizing an expected pattern in a subset of said receive end error checkword when said first segment and said subset of said transmit end error checkword updated in response to said first segment of bits have been received; in which said means for generating a transmit end error checkword comprising a first means for generating a transmit end error checkword and further comprising: at least a second means for generating a transmit end error checkword; and means for selecting from said first and second transmit end error checkwords.

Claim 3

Structure for detecting an error as in claim 1, in which said means for generating a transmit end error checkword is a CRC polynomial shift register having a plurality of XOR gates, each of which receives on one input lead the output from one stage of said shift register and provides an output which is input to a next stage of said shirt register; and means for selecting between applying a logical zero and a function of bits in said data stream to the other lead of each of said XOR gates.

Claim 4

Structure for detecting an error as in claim 1 in which one of said means for generating a transmit end error checkword is a CRC polynomial shift register and another of said means for generating a transmit end error checkword is means for detecting a selected string of bits at a particular location in said data stream.

Claim 5

Structure as in claim 1 in which said means for selecting from said first and second means for generating comprises a control register, said control register being located from said stream of bits and providing a select output, said select output controlling a multiplexer into which are input a plurality of alternative error detecting results.

Claim 6

Structure for detecting an error as in claim 1 in which said means for generating a transmit end error checkword is a CRS polynomial shift register having a plurality of XOR gates, each of which receives on one input lead the output from one stage of said shift register and provides an output which is input to a next stage of said shift register; and means for resetting said shift register to hold an initial value.

Claim 7

Method for detecting an error in a stream of data bits comprising the steps of: at a transmit end: generating from each successive data bit in said stream of data bits a transmit end error checkword, said transmit end error checkword having the property that a subset of said transmit end error checkword is a function of all previous bits in said stream of data bits; periodically forming transmission blocks each comprising a frame of data from said upstream of data bits and said subset of said transmit end error checkword; and transmitting each of said transmission blocks to a receive end; at said receive end: receiving said transmission blocks; calculating a receive end error checkword from said transmission blocks; and after receiving each of said transmission blocks, testing a subset of said receive end error checkword.

Claim 8

Method for detecting an error in a stream of data bits comprising the steps of: at a transmit end: generating from each successive data bit in said stream of data bits a transmit end error checkword, said transmit end error checkword having the property that a subset of said transmit end error checkword is a function of all previous bits in said stream of data bits; periodically forming transmission blocks each comprising a frame of data from said upstream of data bits and said subset of said transmit end error checkword; and transmitting each of said transmission blocks to a receive end; at said receive end: receiving said transmission blocks; calculating a receive end error checkword from said transmission blocks; and after receiving each of said transmission blocks, testing a subset of said receive end error checkword.

Claim 9

Method as in claim 6 in which said subset comprises a first subset, further comprising the steps of: at said transmit end: periodically inserting into said stream of bits a second subset of said transmit end error checkword, and at said receive end: at points where said second subset of said transmit end error checkword is inserted, testing said second subset of said receive end error checkword.

Claim 10

Method as in claim 7 in which said second subset is longer than said first subset of said second subset is checked less frequently than said first subset.

Claim 11

Method as in claim 8 in which said second subset is checked at the end of said stream of bits.

Claim 12

Structure for detecting an error in a stream of bits comprising: at a transmit end: means for generating a multiple bit transmit end error checkword from said stream of bits; means for generating a composite bit stream, said composite bit stream comprising: a first segment of said stream of bits, a subset of said transmit end error checkword updated in response to said first segment of bits from said stream of bits; said transmit end error checkword being retained and updated in response to subsequent bits from said stream of bits, such that said transmit end error checkword becomes a function of said first segment of said stream of bits and a second segment of said stream of bits; and at a receive end: means for receiving said composite bit stream and generating a receive end error checkword in response to said composite bit stream; means for testing said composite bit stream for errors comprising: means for recognizing an expected pattern in a subset of said receive end error checkword when said first segment and said subset of said transmit end error checkword updated in response to said first segment of bits have been received.

Claim 13

Structure for detecting an error in a stream of bits comprising: at a transmit end: means for generating a multiple bit transmit end error checkword from said stream of bits; means for generating a composite bit stream, said composite bit stream comprising: a first segment of said stream of bits, a subset of said transmit end error checkword updated in response to said first segment of bits from said stream of bits; said transmit end error checkword being retained and updated in response to subsequent bits from said stream of bits, such that said transmit end error checkword becomes a function of said first segment of said stream of bits and a second segment of said stream of bits; and at a receive end: means for receiving said composite bit stream and generating a receive end error checkword in response to said composite bit stream; means for testing said composite bit stream for errors comprising: means for recognizing an expected pattern in a subset of said receive end error checkword when said first segment and said subset of said transmit end error checkword updated in response to said first segment of bits have been received.

Claim 14

Structure for detecting an error as in claim 10 in which said means for generating said transmit and receive end error checkwords each comprises a CRC polynomial generator.

Claim 15

Structure for detecting an error as in claim 10 in which said means for generating said transmit and receive end error checkwords each comprises a checksum generator.

Claim 16

Structure for detecting an error as in claim 11 or 12 in which said means for generating a transmit end error checkword further comprising means for loading an initial value into said means for generating a transmit end error checkword.

Claim 17

Structure as in claim 13 in which said initial value is zero.

Claim 18

Structure for detecting an error as in claim 10 in which elements in said composite bit stream are transmitted in the following order: said first segment of said stream of bits; said subset of said transmit end error checkword updated in response to said first segment of bits from said stream of bits; said second segment of said stream of bits; and said subset of said transmit end error checkword updated in response to said first and second segments of bits from said stream of bits.

Claim 19

Structure as in claim 10 further comprising: at said receive end: a shift register; means for loading said shifting register with said composite bit stream; and means for causing said means for recognizing an expected pattern when said first segment and said subset have been received to test for said expected pattern when a selected sequence of bits appears at a particular location in said shift register.

Claim 20

Structure for detecting an error in a stream of bits comprising: at a transmit end: means for generating a transmit end error checkword from said stream of bits, said transmit end error checkword being updated in response to subsequent bits from said stream of bits, at least one bit of said transmit end error checkword being a function of previous bits in said stream of bits; means for generating a composite bit stream, said composite bit stream comprising: a first segment of said stream of bits, a subset of said transmit end error checkword updated in response to said first segment of bits from said stream of bits, said subset including said at least one bit; and at a receive end: means for receiving said composite bit stream and generating a receive end error checkword in response to said composite bit stream; means for testing said composite bit stream for errors comprising: means for recognizing an expected pattern in a subset of said receive end error checkword when said first segment and said subset of said transmit end error checkword updated in response to said first amount of bits have been received; in which said composite bit stream further comprises: a second segment of said stream of bits, and a subset of said transmit end error checkword updated in response to said first and second segments of bits from said stream of bits, said subset including said at least one bit; and in which said means for recognizing further recognizes an expected pattern in a subset of said receive end error checkword when said first segment, said subset updated in response to said first segment, said second segment, and said subset updated in response to said first and second segments have been received.

Claim 21

Structure for detecting an error in a stream of bits comprising: at a transmit end: means for generating a transmit end error checkword from said stream of bits, said transmit end error checkword being updated in response to subsequent bits from said stream of bits, at least one bit of said transmit end error checkword being a function of previous bits in said stream of bits; means for generating a composite bit stream, said composite bit stream comprising: a first segment of said stream of bits, a subset of said transmit end error checkword updated in response to said first segment of bits from said stream of bits, said subset including said at least one bit; and at a receive end: means for receiving said composite bit stream and generating a receive end error checkword in response to said composite bit stream; means for testing said composite bit stream for errors comprising: means for recognizing an expected pattern in a subset of said receive end error checkword when said first segment and said subset of said transmit end error checkword updated in response to said first amount of bits have been received; in which said composite bit stream further comprises: a second segment of said stream of bits, and a subset of said transmit end error checkword updated in response to said first and second segments of bits from said stream of bits, said subset including said at least one bit; and in which said means for recognizing further recognizes an expected pattern in a subset of said receive end error checkword when said first segment, said subset updated in response to said first segment, said second segment, and said subset updated in response to said first and second segments have been received.

Claim 22

Structure for detecting an error as in claim 17 in which said subset of said transmit end error checkword updated in response to said first and second segments of bits from said stream of bits is updated in response to said first segment of bits; said subset of said transmit end error checkword updated in response to said first segment of bits; and said second segment of bits.

Claim 23

Structure for detecting an error as in claim 10 or 17 or 18 in which said subset comprises a first subset, and further comprising means for recognizing an expected pattern in a second subset of said receive end error checkword.

Claim 24

Structure for detecting an error as in claim 19 in which said second subset is longer than said first subset.

Claim 25

Structure as in claim 20 in which said second subset includes all bits of said first subset.

Claim 26

Structure for detecting an error as in claim 20 in which said second subset comprises all of said error checkword.

Claim 27

Structure for detecting an error in a stream of bits comprising: at a transmit end: means for generating a transmit end error checkword from said stream of bits, said transmit end error checkword being updated in response to subsequent bits from said stream of bits, at least one bit of said transmit end error checkword being a function of previous bits in said stream of bits; means for generating a composite bit stream, said composite bit stream comprising: a first segment of said stream of bits, a subset of said transmit end error checkword updated in response to said first segment of bits from said stream of bits, said subset including said at least one bit; and at a receive end: means for receiving said composite bit stream and generating a receive end error checkword in response to said composite bit stream; means for testing said composite bit stream for errors comprising: means for recognizing an expected pattern in a subset of said receive end error checkword when said first segment and said subset of said transmit end error checkword updated in response to said first segment of bits have been received; and further comprising: a counter; means for loading said counter with a count from said stream of bits; and means for causing said means for recognizing an expected pattern when said first segment and said subset have been received to test for said expected pattern when said count equals a number of bits received from said composite bit stream.

Claim 28

Structure for detecting an error in a stream of bits comprising: at a transmit end: means for generating a transmit end error checkword from said stream of bits, said transmit end error checkword being updated in response to subsequent bits from said stream of bits, at least one bit of said transmit end error checkword being a function of previous bits in said stream of bits; means for generating a composite bit stream, said composite bit stream comprising: a first segment of said stream of bits, a subset of said transmit end error checkword updated in response to said first segment of bits from said stream of bits, said subset including said at least one bit; and at a receive end: means for receiving said composite bit stream and generating a receive end error checkword in response to said composite bit stream; means for testing said composite bit stream for errors comprising: means for recognizing an expected pattern in a subset of said receive end error checkword when said first segment and said subset of said transmit end error checkword updated in response to said first segment of bits have been received; and further comprising: a counter; means for loading said counter with a count from said stream of bits; and means for causing said means for recognizing an expected pattern when said first segment and said subset have been received to test for said expected pattern when said count equals a number of bits received from said composite bit stream.