Burst/slip correction decoder and method

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 .ltoreq. B .ltoreq. 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.sup.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.

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.