US 4,162,480 AGranted

Galois field computer

AssigneeCyclotomics, Inc.

InventorElwyn R. Berlekamp

Life of this patent

Estimating the term…

Loading patent…

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

Claims17

Dependent claims

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.

3 more elements

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.

3 more elements

Dependencies are inferred from the claim text.