CYCLIC CODE GENERATION AND ERROR CORRECTION USING SUM OF REMAINDERS

摘要

Cyclic redundancy code check bits are generated from a binary integer by obtaining a remainder from division by a generator polynomial for each "1" bit of the integer and modulo 2 summing all of the remainders. An error in a received binary integer can be identified and corrected by generating (44) check bits for the received integer and comparing (46) them to the received check bits. When the comparison results correspond to a unique remainder for a single erroneous bit, correction occurs by complementing (40) the bit. The presence of two or more errors is recognized and causes the integer to be discarded. Preferably, a parallel exclusive-OR circuit is provided in which the remainder values for adjacent bits are summed (Fig. 2) and the adjacent sums are summed (Fig. 3) to obtain the check bits. The check bits may be used in an asynchronous transfer mode (ATM) cell header.