Galois field linear transformer

Details Galois field linear transformer Galois field linear transformer

2002-01-18

2003-07-01

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06587864

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to a Galois field linear transformer and more particularly to such a Galois field linear transformer which achieves multiple cycle transformations in a single cycle.
BACKGROUND OF THE INVENTION
Conventional arithmetic logic circuits used for error correction and detection, communications, encoding and decoding and general bit manipulation using Galois field linear transformations may be implemented in hardware or software. Hardware implementations are expensive, require significant chip space and energy and are not generally programmable. Software implementations avoid some of these disadvantages but have their own shortcomings. For example software implementation can require many instructions per bit for processing. Thus for an implementation requiring four instructions (cycles) per bit a sixteen bit input would consume 64 cycles of machine time. More realistically in a typical software implementation which processes 6 million bits per second using four or five instructions (cycles) per bit 24-30 million instructions or cycles are needed. When as is often the case more than one circuit is used, four or five, then the cycles required increase to 120 to 150 million. And this is doubled for systems using both a transmitter and receiver. This is a substantial portion of the capacity of conventional processors.
BRIEF SUMMARY OF THE INVENTION
It is therefore an object of this invention to provide an improved Galois field linear transformer for e.g., bit manipulation, error correction and detection, communications, encoding and decoding, encryption and decryption, scrambling and descrambling and cyclical redundancy checking using polynomials.
It is a further object of this invention to provide such an improved Galois field linear transformer which accomplishes multiple cycle Galois field linear transformations in a single cycle.
The invention results from the realization that a fast, effective, economical, Galois field linear transformer for accomplishing multi-bit, multi-cycle transformation in a single cycle can be achieved with a matrix including a plurality of cells, each cell including an exclusive OR gate, an AND gate having an output connected to the exclusive OR gate and a programmable storage device for providing an input to its associated AND gate for setting the matrix to obtain a multi-cycle Galois field linear transformation in a single cycle.
This invention features a Galois field linear transformer including a matrix responsive to a number of input bits in one or more bit streams and having a plurality of outputs for providing the Galois field linear transformation of those bits. The matrix includes a plurality of cells each cell including an exclusive OR logic circuit and AND logic circuit having an output connected to the exclusive OR logic circuit and an input connected to one of the input bits and a programmable storage device providing an input to its associated AND logic circuit for setting the matrix to obtain a multi-cycle Galois field linear transformation of the inputs in a single cycle.
In a preferred embodiment each exclusive OR logic circuit may have its output connected to the input of the next successive exclusive OR logic circuit except for the last exclusive OR logic circuit whose output is connected to the output of the matrix and the first exclusive OR logic circuit whose input is connected to a zero level. The programmable storage device may include a number of storage units each one programmed for enabling a different Galois field linear transformation. The inputs to the matrix may include state inputs representative of previous state conditions of the Galois field linear outputs for the matrix the state inputs may be fed back from the previous state conditions represented by the Galois field linear outputs of the matrix.


REFERENCES:
patent: 3805037 (1974-04-01), Ellison
patent: 5689452 (1997-11-01), Cameron

Affiliated with

Also associated with

Rating

Galois field linear transformer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Galois field linear transformer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Galois field linear transformer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3082421