Galois field arithmetic processor

Details Galois field arithmetic processor Galois field arithmetic processor

1999-11-10

2003-02-18

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06523054

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Galois field arithmetic processor capable of performing various Galois field arithmetic operations.
2. Description of the Related Art
In recent years, error correction code techniques have been closely watched from the viewpoint of the digitization of communications and of improved reliability of storage devices. Error correction code techniques are currently used in modem communications and storing data in storage media such as CDs. Especially in the 21th century when the extension of the digital TV broadcasting is expected, error correction code techniques will become indispensable.
The nucleus of the error correction code technique is the arithmetic operation of the Galois field GF(2
8
). It is expected that the Reed-Solomon code of the Galois field GF(2
8
), for example, will be employed in the standard specification of ADSL and satellite broadcasting and further for digital TV systems using terrestrial transmission.
In common practice, the coder and decoder for performing a Galois arithmetic operation have conventionally been realized with a dedicated circuit. However, the dedicated circuit poses the problem that signals of different specifications cannot be handled successfully. The error correction code has different code lengths and different multiplicities for different applications, and therefore the use of a dedicated circuit for this purpose encounters difficulty in conforming with various specifications.
No available processor has a set of Galois field operation commands. In recent years, however, a Galois field arithmetic processor has been developed for performing a part of the process. This processor is incapable of decoding a Reed-Solomon code in its entirety but can only execute a part of the process. As a result, only one of either the multiplication of the Galois field vector expression or the multiplication of the exponential expression is supported, and the performance of the required process necessitates various pre-processing of the data input to the processor. For versatile programming to be possible with the processor instructions alone, both the performance and an instruction set capable of executing a program in its entirety are required. Cooperation between the processor and a dedicated circuit for performing a part of the process is difficult to control and encounters the problem of a reduced performance. In realizing the processing system for the Galois field operation with a processor, compatibility is required between an increased processing speed, a circuit scale must be reduced to less than the dedicated circuit and affinity to the existing pipelines must be provided.
For the power operation, on the other hand, the arithmetic operation between exponents with 255 as a modulus such as (&agr;
i
)
j
=&agr;
i*j
is a common practice. The syndrome operation, therefore, requires conversion of the operation result for use in the next operation. This process cannot be performed by the processor alone. When the power operation is performed by multiplication between exponents, an increased arithmetic unit size poses a problem. In other words, it is necessary to include a special circuit in the form of an arithmetic multiplier with 255 as a modulus in the Galois field FG (2
8
) arithmetic unit, resulting in a great disadvantage from the viewpoint of hardware utilization efficiency.
SUMMARY OF THE INVENTION
The object of the present invention is to realize a practical processor with a simple configuration which solves the problem points described above.
FIG. 1
is a diagram showing a first basic configuration of a Galois field arithmetic processor according to the invention. As shown in
FIG. 1
, the Galois field arithmetic processor according to the invention has the feature in that a data conversion circuit is arranged to perform the conversion of only one operand, and operands of different expressions can be processed as they are.
Specifically, a Galois field arithmetic processor according to this invention comprises an instruction decoder
1
, and an arithmetic unit including a Galois field vector adder
31
, a Galois field vector multiplier
32
, and a Galois field exponential adder-subtractor
33
for executing the Galois field operation on the first and second operands.
In the case where the arithmetic unit
30
includes at least the Galois field vector adder
31
and the Galois field vector multiplier
32
, for example, an exponent-vector conversion circuit
22
for converting the second operand from the exponential expression to the vectorial expression is provided with an instruction for performing the Galois field arithmetic operation on the first operand expressed vectorially and the second operand expressed exponentially. With this configuration, if it is assumed that the data expressed vectorially is input as the first operand and the data expressed exponentially is the second operand, the second operand is converted into a vectorial expression by the conversion circuit, after which the Galois field vector adder or the Galois field vector multiplier performs the arithmetic operation. This function is effective for arithmetically processing r*G&agr;
i
, for example, from the vectorial expression r and the exponential expression i, and a single instruction can be realized with which to execute the aforementioned operation of the processor.
If it is assumed that a selector
55
is provided for selecting the second operand or the output of the exponent-vector conversion circuit
22
and supplying the choice as a second operand to the arithmetic unit
30
, then, both the data vectorially expressed and the data exponentially expressed can be input as the second operand, and the processor can be provided with an instruction for performing the Galois field operation on the two vectorially expressed data. Further, providing a second input data selector
51
for selecting the second operand or the processing result and outputting the choice as the second operand, the arithmetic operation can be repeated on the operation result requiring the conversion.
Also, in the case where the arithmetic unit
30
includes at least a Galois field exponential adder-subtractor
33
, a vector-exponent conversion circuit
21
is provided for converting the second operand from a vectorial expression to an exponential expression, with an instruction for performing the Galois field operation on the exponentially expressed first operand and the vectorially expressed second operand. In this configuration, assume that the data exponentially expressed and the data vectorially expressed are input as the first operand and the second operand, respectively. The second operand is converted into an exponential expression by the conversion circuit, after which the Galois field exponential adder-subtractor performs the arithmetic operation. In the case of GF(2
8
), the addition-subtraction is conducted, for example, with 255 as a modulus in the following manner.
(100+30)
mod
255=(130)
mod
255=130
(200+57)
mod
255=(257)
mod
255=2
(57−200)
mod
255=(−143)
mod
255=112
This function is effective for processing i+Aj or i−Aj (addition-subtraction between exponents i and j), for example, from the vectorial expression a(&agr;
i
) and the exponential expression j, and the operation can be performed by giving a single instruction to the processor. Further, if j=0, the conversion is simply the one from a vectorial expression to an exponential expression.
In similar fashion, assume that a selector
55
is added for selecting either the second operand or the output of the vector-exponent conversion circuit
21
, and the result is supplied as the second operand to the arithmetic unit
30
. Then, either the exponentially expressed data or the vectorially expressed data can be input as the second operand, and an instruction to the processor can be provided for the Galois field operation on two exponentially expressed data.
I

Affiliated with

Also associated with

Rating

Galois field arithmetic processor 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 arithmetic processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Galois field arithmetic processor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3181927