Burst/slip correction decoder and method

Claim 2

In a machine implemented process for use in a data communications system having decoding apparatus for decoding on a first-in-first-out basis n' received data characters encoded in a shortened cyclic block code of the type (n,k), n being the total number of characters and k being the number of information characters, by the use of a generating polynomial having an exponent E, the received data characters having been subjected to an error inducing environment such that the data can contain a burst error of b characters having a slip error of d characters, the process comprising the steps of: 1. determining the slip error d of the received characters; 2. storing the received n' characters in a first register means; 3. generating and storing an initial syndrome in a second register means, said initial syndrome being computed using the generating polynomial and the received data characters; 4. generating an intermediate syndrome from said generated initial syndrome by rotating and feeding back pursuant to the syndrome generating polynomial the characters stored in said second register means; 5. selectively combining parts of the received n' characters stored in said first register means with selected characters of said generated intermediate syndrome to generate further characters; and 6. testing said generated further characters to determine if said received data characters have undergone a burst error.

Claim 3

A machine implemented as claimed in claim 1 where the process also outputs decoded data characters, the process further comprising the additional steps of: 7. combining in decoded character selection means selected characters from said first register means with a selected character from said second register means for generating a decoded output character; and 8. repeating steps 5 through 7 for each decoded character until an entire n character codeword has been decoded and outputted.

Claim 4

A machine implemented process as claimed in claim 1 wherein the slip error d is determined by counting the number n' of received data characters in counter means and comparing the count in said counter means with the number n of encoded data character.

Claim 5

A machine implemented process as claimed in claim 3 and further comprising testing d ≦ D, where D is a maximum preselected slip error, and outputting an excessive slip slgnal if | d| > D.

Claim 6

A machine implemented process as claimed in claim 4 wherein said first register means comprises a shift register and said excessive slip is outputted, said process further comprising shifting said shift register n' times and serially outputting the contents of said shift register, said contents being the same as the received data word.

Claim 7

A machine implemented process as claimed in claim 1 wherein said first register means comprises a serial input, serial output shift register having E stages and wherein said second register means comprises a first syndrome register having n-k stages and wherein said received n' characters are serially loaded into said first register and wherein said initial syndrome is computed by serially loading the received data characters into said first syndrome concurrently with said loading of said shift register.

Claim 8

A machine implemented process as claimed in claim 6 wherein said second register means further comprises a second syndrome register serially connected to said first syndrome register, said process further including the step of transferring said generated initial syndrome from said first syndrome register to said second syndrome register and wherein said intermediate syndrome is generated in said second syndrome register by shifting said second syndrome register E-n' number of times.

Claim 9

A machine implemented process as claimed in claim 7 and further comprising determining whether the slip error d is a slip insertion wherein n' > n or whether the slip error d is a slip deletion wherein n' < n, and generating a first signal for a slip insertion and a second signal for a slip deletion and wherein said combined parts are stored in said shift register and comprise two characters spaced d stages apart, and said selective combination of said parts comprises modulo two adding said two characters and shifting said shift register once, then performing said testing step which comprises testing said further characters for a selected zero condition; and repeating said adding, shifting and testing steps until said zero condition is generated.

Claim 10

A machine implemented method for detecting slippage errors in shortened cyclic block data of the type (n,k) where n is the correct bit length of a bit string and k is the number of information bits in the bit string, the data encoded by a generating polynomial and subjected to error causing signals that can affect a bit string portion of b bits where b ≦ B ≦ n-k, said method comprising the steps of: 1. entering a first bit string comprising a plurality of n' bits into an R-register and determining the value of n', where n' = n ± d bits and d is the slippage error and represents the number of bits inserted or deleted from the correct bit string, and wherein said bit string has a most significant bit (MSB) position at one end and a least significant bit (LSB) position at the other end; 2. generating and storing an error syndrome comprising a second bit string in an S-register having a most significant bit (MSB) position at one end thereof and a least significant bit (LSB) position at the other end thereof, and syndrome representing a modulo 2 division of the modulo 2 product of said first bit string and the binary representation of the number 2 B by the generating polynomial, where B is a predetermined integer number representing the maximum burst length; 3. comparing the value of n' with the value of n and generating a first signal when n' > n which represents a bit insertion case and generating a second signal when n' < n which represents a bit deletion case; 4a. testing if said first signal has been generated and if true, then modulo 2 adding the bit in a first bit position corresponding to the location in said R-register of said MSB position of said bit string where said first bit string is initially located with the bit in a second bit position corresponding to the location in said R-register that is spaced d bit positions from said first bit position in the direction of said LSB position of said bit string; 4b. testing if said second signal has been generated and if true, then selecting the bit in said first bit position unless d selections have been previously made, then modulo two adding the bit presently in said first bit position with the bit that was in said first bit position d number of times previously; 5. modulo two adding the result of said addition or selection with the bit that is in the bit position corresponding to the location in said S-register that is spaced B bit positions from said LSB position of said S-register; 6. shifting said first and second bit strings one bit position in said R-register and S-register, respectively, in the direction of the corresponding MSB position, the bit in the S-register bit location corresponding to the bit position spaced B + 1 bit positions from the LSB position of said second bit string with the sum of said modulo two addition of step 5; and if the bit in the MSB position of said second bit string is a 1 immediately prior to said shifting of said second bit string, then modulo 2 adding the binary representation of the generating polynomial to said shifted second bit string subsequent to the shifting of said second bit string and if the bit in the MSB of said second bit string is a 0 immediately prior to said shifting of said second bit string, then adding a zero as the LSB position of second bit string, 7. conducting a zero condition test to determine if a correctable error condition exists in the entered data by testing if the most significant n-k-B bits of said S-Register are all zeros when said second signal has been generated or by testing if the most significant n-k-B bits of said S-Register are all zeros when said second signal has been generated or by testing if the most significant n-k-B bits and the least significant d bit of said S Register are all zeros when said first signal has been generated; 8. if no zero condition is determined repeating steps 4a and 5 through 7 if said first signal has been generated and repeating steps 4b and 5 through 7 if said second signal has been generated.

Claim 11

A machine implemented method for detecting slippage errors in shortened cyclic block data of the type (n,k) where n is the correct bit length of a bit string and k is the number of information bits in the bit string, the data encoded by a generating polynomial and subjected to error causing signals that can affect a bit string portion of b bits where b ≦ B ≦ n-k, said method comprising the steps of: 1. entering a first bit string comprising a plurality of n' bits into an R-register and determining the value of n', where n' = n ± d bits and d is the slippage error and represents the number of bits inserted or deleted from the correct bit string, and wherein said bit string has a most significant bit (MSB) position at one end and a least significant bit (LSB) position at the other end; 2. generating and storing an error syndrome comprising a second bit string in an S-register having a most significant bit (MSB) position at one end thereof and a least significant bit (LSB) position at the other end thereof, and syndrome representing a modulo 2 division of the modulo 2 product of said first bit string and the binary representation of the number 2 B by the generating polynomial, where B is a predetermined integer number representing the maximum burst length; 3. comparing the value of n' with the value of n and generating a first signal when n' > n which represents a bit insertion case and generating a second signal when n' < n which represents a bit deletion case; 4a. testing if said first signal has been generated and if true, then modulo 2 adding the bit in a first bit position corresponding to the location in said R-register of said MSB position of said bit string where said first bit string is initially located with the bit in a second bit position corresponding to the location in said R-register that is spaced d bit positions from said first bit position in the direction of said LSB position of said bit string; 4b. testing if said second signal has been generated and if true, then selecting the bit in said first bit position unless d selections have been previously made, then modulo two adding the bit presently in said first bit position with the bit that was in said first bit position d number of times previously; 5. modulo two adding the result of said addition or selection with the bit that is in the bit position corresponding to the location in said S-register that is spaced B bit positions from said LSB position of said S-register; 6. shifting said first and second bit strings one bit position in said R-register and S-register, respectively, in the direction of the corresponding MSB position, the bit in the S-register bit location corresponding to the bit position spaced B + 1 bit positions from the LSB position of said second bit string with the sum of said modulo two addition of step 5; and if the bit in the MSB position of said second bit string is a 1 immediately prior to said shifting of said second bit string, then modulo 2 adding the binary representation of the generating polynomial to said shifted second bit string subsequent to the shifting of said second bit string and if the bit in the MSB of said second bit string is a 0 immediately prior to said shifting of said second bit string, then adding a zero as the LSB position of second bit string, 7. conducting a zero condition test to determine if a correctable error condition exists in the entered data by testing if the most significant n-k-B bits of said S-Register are all zeros when said second signal has been generated or by testing if the most significant n-k-B bits of said S-Register are all zeros when said second signal has been generated or by testing if the most significant n-k-B bits and the least significant d bit of said S Register are all zeros when said first signal has been generated; 8. if no zero condition is determined repeating steps 4a and 5 through 7 if said first signal has been generated and repeating steps 4b and 5 through 7 if said second signal has been generated.

Claim 12

A decoder for use in a data communications system for decoding on a first-in-first-out basis n' received data characters encoded in a shortened cyclic block code of the type (n,k), n being the total number of characters and k being the number of information characters, by the use of a generating polynomial having an exponent E, the received data characters having been subjected to an error inducing environment such that the data can contain a burst error of b characters having a slip error of d characters, the decoder comprising: means for determining the slip error d of the received characters; first register means for storing the received n' characters; second register means for generating an initial syndrome that is computed using the generating polynomial and the received data characters, said generating means storing said initial syndrome in said second register means; means for generating an intermediate syndrome from said generated initial syndrome by rotating and feeding back pursuant to the syndrome generating polynomial the characters stored in said second register means an E - n' number of times; means for selectively combining parts of the received n' characters stored in said first register means with selected characters of said generated intermediate syndrome to generate further characters; and means for testing said generated further characters to determine if said received data characters have undergone a burst error.

Claim 13

A decoder for use in a data communications system for decoding on a first-in-first-out basis n' received data characters encoded in a shortened cyclic block code of the type (n,k), n being the total number of characters and k being the number of information characters, by the use of a generating polynomial having an exponent E, the received data characters having been subjected to an error inducing environment such that the data can contain a burst error of b characters having a slip error of d characters, the decoder comprising: means for determining the slip error d of the received characters; first register means for storing the received n' characters; second register means for generating an initial syndrome that is computed using the generating polynomial and the received data characters, said generating means storing said initial syndrome in said second register means; means for generating an intermediate syndrome from said generated initial syndrome by rotating and feeding back pursuant to the syndrome generating polynomial the characters stored in said second register means an E - n' number of times; means for selectively combining parts of the received n' characters stored in said first register means with selected characters of said generated intermediate syndrome to generate further characters; and means for testing said generated further characters to determine if said received data characters have undergone a burst error.