The use of linear block codes for error detection and correction in digital data transmission is well-known. Such codes act on information in blocks, each block forming an information word to be transmitted or stored. In the case of cyclic linear block codes, a codeword uniquely related to each information word is produced during the encoding scheme, this codeword being divisible by a fixed generator word. At the receiver, a received codeword is divided by the generator word. If a non-zero remainder results from this division, then errors have occurred during transmission. Moreover, this remainder, or syndrome, is uniquely related to an error pattern which is then corrected.
Suitable codewords for such schemes have been generated in a variety of ways. For systematic encoding of cyclic codes, one such method utilizes serial data input/output wherein each information word is applied to an (n-k)-stage shift register with feedback connections based on a generator polynomial. After the information bits are shifted into the register and simultaneously into the communication channel, the n-k parity bits formed in the register are shifted into the channel, thus forming the complete codeword. This approach, however, is incompatible with parallel data input/output. To overcome this problem, suitable codewords have also been generated by table look-up encoding schemes which serve to map the k bits of each information work to n-k parity bits. These n-k parity bits are then appended to the k bits of each information word to define the codeword uniquely associated with each information word.
Standard look-up table encoding, however, requires memory devices with 2.sup.k address locations. Such encoding schemes are thus impractical for medium length information words, and prohibitively complex and expensive when k is large. There is therefore a need for an efficient table look-up encoding scheme for linear block codes which obviates such large memory requirements.
USPTO Backgrounds
USPTO Backgrounds