Bit serial encoder

• US 4,410,989 A
• Filed: 12/11/1980
• Issued: 10/18/1983
• Est. Priority Date: 12/11/1980
• Status: Expired due to Term

• Current Assignee: Cyclotomics, Inc.
• Original Assignee: Cyclotomics, Inc.
• Inventors: Berlekamp, Elwyn R.
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US06/215,361
• Time in Patent Office: 1,041 Days
• Field of Search: 371/40, 371/37, 371/39, 371/45
• US Class Current: 714/762
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence

Abstract

An encoder for Reed Solomon codes employs structure for producing interleaved code wherein redundancy bits are realized by a bit serial multiplicative procedure. Operations are accomplished with respect to the dual basis to the conventional polynomial representational basis as coefficients of successive powers of an element of a finite field. Code bits are generated and interleaved by a feedback shift register constructed from standard RAM chips. The structure is simplified by selection of a generator polynomial from a class which exhibits symmetry whereby the number of independent coefficients for representing the generator polynomial is halved.

Claims

1. Encoding apparatus for accepting a message block comprising message symbols comprising groups of bits, creating from said message symbols codewords and check bits derived from said message symbols in accord with a cyclic code for output to an information channel, said apparatus comprising

(a) first codeword shift register for assembling bits of of an input message symbol received from a data source, said message symbol represented in a first representation in the form of an ordered set of coefficients of corresponding powers of an element of the finite field GF(2^m),

(b) second shift register for receiving said assembled message symbol by parallel transfer from said first codeword shift register,

(c) binary matrix network means for generating from the content of the respective bits of said second shift register, the traces of the respective matrix products of the content of said second shift register and the bits of a selected generator polynomial, said matrix representing a coefficient of a product of said generator polynomial and the content of said second shift register in the dual representation of said first representation,

(d) feedback shift register means for processing each said product of a coefficient, comprising an initial memory element, a final memory element and a plurality of sequences of memory elements, each said sequence separated by summing junctions, each said summing junction comprising means for performing the binary addition of the content of one adjacent memory element with the respective said trace of said matrix product and transferring the resulting sum to the next adjacent memory element, the initial memory element receiving the trace of the lowest order of said matrix products, the final memory element of said shift register communicating with said binary network means during the acceptance of said message block and thereafter emitting check bits for transmission to said information channel as part of said codeword,

(e) synchronization means for controlling the assembly of a message character in said first shift register, strobing the content of said first shift register in parallel to said second shift register and to control the propagation of information through said feedback shift register.

2. The encoder of claim 1 wherein the coefficients of said selected generator polynomial comprises a pallindrone.

3. The encoder of claim 1 or 2 wherein said feedback shift register comprises at least three random access memory arrays, each said memory array comprising a plurality of ordered memory elements, adjacent said memory elements comprising respective first and second said memory arrays and said final memory element comprising a third said memory array.

4. The feedback shift register means of claim 1 comprising means for interleaving successive coefficients in said feedback shift register means in accord with a selected interleaving index.

5. The feedback shift register of claim 3 comprising addressing means for indexing said memory elements in each said arrays to accommodate at least two said sequences of memory elements in any of said arrays and a selected interleaving depth for the content of said arrays.

6. A feedback shift register for serially propagating and algebraically operating on a stream of bits, said bits comprising a stream of characters, said feedback shift register comprising a plurality of stages, each said stage having a capacity for a first plurality of bits, said feedback shift register comprising at least two random access memory arrays, adjacent stages of said feedback shift register comprising respective first and second said random access memory arrays, a plurality of adder means, each said adder means electrically arranged between each adjacent said pair of shift register stages for computing the sum of the content of the kth stage of said feedback shift register with an algebraic quantity and supplying said sum to the k+1 stage, first and second addressing means for addressing respective said memory arrays, clock means comprising means for generating at least 4 distinguishable pulses, means responsive to each successive said clock pulse for initiating the respective operations of writing and reading between adjacent stages whereby communication between memory arrays is facilitated for the plurality of stages contained in each said array.

7. The feedback shift register of claim 6 further comprising a final stage, said final stage having a capacity less than said first plurality of bits by a second plurality of bits comprising at least one character.

8. The feedback shift register of claim 7 comprising an initial stage and combinatorial means for introducing a function of the content of said final stage to said initial stage.

9. The method of generating check bits from an input message word represented in a basis wherein symbols comprising said message word are represented as coefficients of a polynomial in powers of an element of a finite field comprising

(a) transforming the coefficients of said first representation basis of said message word to a second basis, said second basis dual to said first basis,

(b) performing the serial multiplication of said dual basis represented message word with a selected generator polynomial to obtain said check bits,

(c) appending said check bits to said message word.

10. The method of claim 9 comprising selecting a generator polynomial in the dual basis wherein the coefficients of said generator polynomial form a pallindrone.

11. Apparatus for obtaining the product of a variable, said variable represented in a first basis as a set of m coefficients of a polynomial in successive powers of an element of the finite field GF (2^m), with an ordered set of n≦

m coefficients of a constant polynomial, said apparatus comprising

(a) first means for receiving said variable from a data source,

(b) a plurality of means for combining each of a corresponding plurality of selected subsets of said first set of m coefficients to obtain therefrom bits comprising the product of said variable with a single coefficient of said constant polynomial,

(c) shift register means for receiving said product bits of said single coefficient,

(d) transformation means for performing m-1 successive linear transformations of the content of said first register means, said first register means retaining the transformed quantity as a result thereof,

(e) means for causing the occurrence of said transformation at m-1 succeeding intervals and shifting the content of said shift register for the assembly of said product in a portion of said shift register.

12. The apparatus of claim 11 wherein said combining means comprises means for computing a single parity check on said selected subset of the binary coefficients of said variable.

13. The apparatus of claim 12 wherein each said plurality of combining means comprises a gating network.

14. The apparatus of claim 13 wherein each said gating means comprises an XOR gate.

15. The apparatus of claim 12 wherein said first register means is a shift register and the actuation of said transformation means causes the content of said shift register to be multiplied, modulo m, by a selected element of said finite field.

16. The apparatus of claim 15 wherein said plurality of combining means is structured to represent said product coefficients in a second basis, said second basis the dual of said first basis.

17. The apparatus of claim 11 or 16 wherein the coefficients of said ordered set are invariant with respect to the inverse ordering thereof.