Galois field computer

Abstract

Errors are corrected in a cyclic encoded data stream, consisting of sequential groups of data bits and check bits, by means of a novel digital computer. The computer employs a stored program and is organized into three distinct substructures, each having an independent internal addressable memory and all capable of synchronous concurrent operation. An arithmetic unit substructure including a data memory implements finite field arithmetic operations upon received data. The arithmetic unit includes a Galois field manipulative subunit for producing finite field products and sums over the field GF(2 5 ) from operands selected from three registers which derive data from the memory of the arithmetic unit, another register, or the result of a currently executed Galois field operation. The preferred embodiment is especially suitable for correcting data encoded in the Reed-Solomon (31,15) code. An address generator realizes address modification in the Galois field GF(2 7 ), whereby consecutive addresses in data memory are characterized by a shift register sequence. The address generator includes a counter memory array and an equality test facility. Counter memory words of the address generator may selectably retain either the modified or non-modified address. A control unit substructure includes a control memory for storage and execution of the instruction sequence, branching logic for determining the transfer of control in response to logical functions of up to 16 logical variables, and select means and gating means for execution of instructions in all three substructures. Provision for data dependent arithmetic function selection, not employed for decoding the (31,15) Reed Solomon Code, permits the operation of the apparatus to yield solutions at high speed to simultaneous linear binary equations.

What is claimed is: 
     
       1. A stored program digital computer for correcting errors in cyclic encoded streams of data elements, comprising: (a) an arithmetic unit for performing arithmetic and logical operations upon portions of said data streams to decode said portions of data streams, said arithmetic unit comprising data memory means having addressable elements for retaining said data elements, multiplier means to supply an operand for multiplication, multiplier register means to supply another operand for multiplication, addend register means for holding an operand for addition, data memory addressng means for retrieving selected data elements to supply a selected one of said operands, Galois field logic means selectably operable upon said multiplier and multiplicand registers to generate a finite field product, and said Galois field logic means selectably operable on said addend register to form a finite field sum with said product, said data memory means adapted to also retain the results of said Galois field logic means operation and said multiplier means adapted to supply said operand selectably from the result of a prior Galois field logic operation;     (b) an address generator for developing address information for transmittal to said arithmetic unit to address the data memory of said arithmetic unit, said address generator comprising address generator memory means having addressable elements for retaining information from which addresses are developed for said data memory of said arithmetic unit, address register means for retaining information derived from said address generator memory means, means for transferring the information content of a selected element of said address generator memory means to said address register means, means to modify the content of address register means in accord with a shift register sequence, test register means for retaining a datum and comparator means to detect equality of the content of said address register means with the content of said test register means, and     (c) a control unit for controlling the sequence of operations performed by said arithmetic unit and said address generator, said control unit comprising control memory means for storing the instructions defining the sequence of operations required for effecting corrections in said data streams, said control memory means having addressable elements and means for addressing said control memory means, said control memory addressing means adapted to sequentially address said control memory means, said sequence referenced from a selectable base address, means for selecting said base address, control register means for retaining the content of an elememt of said control memory means, said control memory element controlling the state of said computer, and means for transferring a portion of the content of said address generator in response to a signal defined by said control register content.     
     
     
       2. The computer of claim 1 wherein the information transfer between said control unit and said address generator comprise a first signal forming a digital datum originating from said control unit and   a second signal originating from the comparator means of said address generator.   
     
     
       3. The computer of claim 2 wherein said means for selecting said base address is responsive to said equality condition. 
     
     
       4. The computer of claim 3 wherein the information transfer between said address generator and said arithmetic unit comprises a third signal for transmitting the content of said address register means to said data memory addressing means of said arithmetic unit.   
     
     
       5. The computer of claim 4 wherein said data memory means and said registers of said arithmetic unit and said address generator memory means and said registers of said address generator each further comprise enabling means to enable information transfer to respective memory means and register means and wherein a first plurality of control signal paths originate in said control unit for actuating said enabling means of selected said registers and memories and wherein a second plurality of control signal paths originate in said control unit for initiating said selected operations of said Galois field logic means of said arithmetic unit and for initiating modification of the content of said address register of said address generator. 
     
     
       6. The computer of claim 5 wherein said arithmetic unit further comprises input means for accepting said data from an external source for storage in said data memory and output means for supplying error-corrected data to an external data sink from said data memory. 
     
     
       7. The computer of claim 6 wherein said input means is adapted to provide a signal indicative of the incidence of input data at said input means and said output means is adapted to provide a signal indicative of the incidence of output data at said output means, wherein said means for altering said base address is responsive to each said logic signal. 
     
     
       8. The computer of claim 1 wherein said arithmetic unit further comprises means for re-setting the content of said multiplier register to the square of the previous content of said register. 
     
     
       9. In a method of addressing a digital memory having 2 n  -1 addressable elements and having addressing means whereby the content of a selected memory element is retrieved in response to an address provided by said addressing means, the method of memory addressing comprising the steps of initializing an address register with selected digital content   modifying the content of said address register in accord with a sequence characteristic of an n bit shift register of maximum period;   transferring the content of said address register to said addressing means, whereby said selected memory element to be retrieved is characterized by an address modified in accord with said shift register sequence.   
     
     
       10. The method of claim 9 wherein said step of modifying includes the step of incrementing said address register wherein the content of said register is shifted in an ascending sense. 
     
     
       11. The method of claim 10 wherein said step of modifying includes the step of decrementing said address register wherein the content of said register is shifted in a descending sense. 
     
     
       12. The method of claim 11 wherein the step of incrementing and the step of decrementing are commutative, whereby the content of said address register is returned to said first value as a result of an equal number of said steps of incrementing and said steps of decrementing. 
     
     
       13. In an information processing system comprising 2 n  -1 elements of addressable memory and addressing means for developing consecutively incremented memory addresses, the improvement wherein said addressing means comprises a feedback shift register of period 2 n  -1, said shift register comprising n bits whereby an address sequence is developed in accord with the numeric sequence developed by said feedback shift register. 
     
     
       14. The apparatus of claim 13 wherein said addressing means further comprises means for consecutively decrementing addresses in accord with said numeric sequence. 
     
     
       15. The apparatus of claim 14 wherein said memory elements comprise independent words and said numeric sequence developed said shift register is characterized by the irreducible generator polynomial of the field GF (2 n ). 
     
     
       16. The apparatus of claim 15 wherein n=7. 
     
     
       17. A stored program digital computer for correcting errors in cyclic encoded streams of data elements, comprising: (a) an arithmetic unit for performing arithmetic and logical operations upon portions of said data streams to decode said portions of data streams, said arithmetic unit comprising data memory means having addressable elements for retaining said data elements, multiplier means to supply an operand for multiplication, multiplier register means to supply another operand for multiplication, addend register means for holding an operand for addition, data memory addressing means for retrieving selected data elements to supply a selected one of said operands, Galois field logic means selectably operable upon said multiplier and multiplicand registers to generate a finite field product, and said Galois field logic means selectably operable on said addend register to form a finite field sum with said product, said selectable operability being responsive to a portion of the operand supplied by said multiplier means, said data memory means adapted to also retain the results of said Galois field logic means operation and said multiplier means adapted to supply said operand selectably from the result of a prior Galois field logic means operation;     (b) an address generator developing address information for transmittal to said arithmetic unit to address the data memory of said arithmetic unit, said address generator comprising address generator memory means having addressable elements for retaining information from which addresses are developed for said data memory of said arithmetic unit, address register means for retaining information derived from said address generator memory means, means for transferring the information content of a selected element of said address generator memory means to said address register means, means to modify the content of address register means in accord with a shift register sequence, test register means for retaining a datum and comparator means to detect equality of the content of said address register means with the content of said test register means, and     (c) a control unit for controlling the sequence of operations performed by said arithmetic unit and said address generator, said control unit comprising control memory means for storing the instructions defining the sequence of operations required for effecting corrections in said data streams, said control memory means having addressable elements and means for addressing said control memory means, said control memory addressing means adapted to sequentially address said control memory means, said sequence referenced from a selectable base address, means for selecting said base address, control register means for retaining the content of an element of said control memory means, said control memory element controlling the state of said computer, and means for transferring a portion of the content of said address generator in response to a signal defined by said control register content.