Galois field arithmetic processor

• US 6,523,054 B1
• Filed: 11/10/1999
• Issued: 02/18/2003
• Est. Priority Date: 12/04/1998
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Kamijo, Shunsuke
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US09/437,473
• Time in Patent Office: 1,196 Days
• Field of Search: 708/492, 714/781, 714/784
• US Class Current: 708/492
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A practical Galois field arithmetic processor capable of high-speed operation with a simple configuration is disclosed. The processor comprises an instruction decoder, an arithmetic unit including a Galois field vector adder, a Galois field vector multiplier and a Galois exponent adder-subtractor for executing the Galois field arithmetic operation on first and second operands. In the case where the arithmetic unit includes at least a Galois field vector adder and a Galois field vector multiplier, an exponent-vector conversion circuit is provided for converting the second operand from an exponential expression into a vectorial expression, and an instruction is provided for performing the Galois field operation on the vectorially expressed first operand and the exponentially expressed second operand. With this configuration, in the case where the vectorially expressed data is input as the first operand and the exponentially expressed data is input as the second operand, the second operand is converted into a vectorial expression by the conversion circuit, after which the arithmetic operation is performed in the Galois field vector adder or the Galois vector multiplier.

Claims

1. A Galois field arithmetic processor comprising:

an instruction decoder providing an instruction for performing a Galois field arithmetic operation on a first operand which is vectorially expressed and a second operand which is exponentially expressed;

an exponent-vector conversion circuit for converting said second operand from an exponential expression to a vectorial expression; and

an arithmetic unit comprising a Galois field vector adder and a Galois field vector multiplier for executing a Galois field arithmetic operation on the first operand and the second operand.

2. A Galois field arithmetic processor according to claim 1, further comprising:

a selector for selecting one of said second operand which is exponentially expressed and an output of said exponent-vector conversion circuit, and supplying a result of selection to said arithmetic unit as said second operand;

wherein any one of said vectorially expressed data and said exponentially expressed data can be input as said second operand and an instruction is provided for performing the Galois field operation on both vectorially expressed operands.

3. A Galois field arithmetic processor according to claim 1:

wherein said first operand and said second operand are input to said Galois field vector multiplier, and an output of said Galois field vector multiplier and a third operand are applied to the said Galois field vector adder.

4. A Galois field arithmetic processor according to claim 3, further comprising:

a first arithmetic data selector for selecting one of said first operand and an output of said Galois field vector adder, and outputting the selected data to said Galois field vector multiplier as said first operand.

5. A Galois field arithmetic processor according to claim 3, further comprising:

a third arithmetic data selector for selecting one of said third operand and the output of said Galois field vector adder, and outputting a result of the selecting to said Galois field vector adder as said third operand.

6. A Galois field arithmetic processor according to claim 5:

wherein said operands have a data width of m×

n (m, n;

positive integers), said conversion circuit has n conversion circuits with a data width of m, said arithmetic unit uses n arithmetic operators with a data width of m, and n Galois field arithmetic operations with a data width of m can be carried out in parallel.

7. A Galois field arithmetic processor according to claim 6:

wherein said conversion circuit is a memory having n banks configured with n memory units having a data width of m, said memory is accessible as n memory units, said memory being supplied with a common address and also accessible as a memory having a data width of m×

n.

8. A Galois field arithmetic processor according to claim 3, further comprising:

an accumulator temporarily holding an output of said Galois field vector adder.

9. A Galois field arithmetic processor according to claim 8, further comprising:

a first data selector for selecting one of said first operand and an output of said accumulator and outputting a result of said selecting to said Galois field vector multiplier as said first operand.

10. A Galois field arithmetic processor according to claim 8, further comprising:

a third data selector for selecting one of said third operand and an output of said accumulator and outputting said selected data to said Galois field vector adder as said third operand.

11. A Galois field arithmetic processor according to claim 1,

wherein the operation is divided into a first stage for converting said second operand and a second stage, for processing in said arithmetic unit,

said processor further comprising temporary registers for temporarily holding the data of said first and second stages;

wherein said first and second stages are performed in parallel by pipelining.

12. A Galois field arithmetic processor according to claim 11, further comprising a feedback mechanism for feeding back the result of arithmetic operation as said second operand;

wherein said instruction decoder outputs control data for controlling said temporary registers, each of said selectors and said feedback mechanism;

the processor further comprising a control decision circuit adapted for transmitting said control data sequentially to each stage corresponding to each of said temporary registers, each of said selectors and said feedback mechanism, and determining whether said control data is the one for controlling the corresponding one of said temporary registers, the corresponding one of said selectors or said feedback mechanism thereby to control the corresponding temporary register, the corresponding selector or said feedback mechanism in accordance with the result of determination;

wherein said control data of said feedback mechanism includes a stage flag for indicating the presence or absence of the processing in said first stage, said control decision circuit corresponding to said second operand generates a control signal for bypassing said processing in said first stage in accordance with said stage flag.

13. A Galois field arithmetic processor according to claim 1:

wherein said operands have a data width of m×

n (m, n;

positive integers), said conversion circuit has n conversion circuits with a data width of m, said arithmetic unit uses n arithmetic operators with a data width of m, and n Galois field arithmetic operations with a data width of m can be carried out in parallel.

14. A Galois field arithmetic processor according to claim 13, further comprising:

a flag storage register storing an n-bit flag in continuous areas indicating that the result of arithmetic operation of n arithmetic operators having a data width of m is zero.

15. A Galois field arithmetic processor according to claim 13 having an operation data width of m×

n, further comprising;

an accumulation flag calculating the logic sum of the output of said Galois field vector adder having a data width of m and the preceding output thereof and accumulating the zero flag; and

an intermediate copy register for storing at n points m arbitrary bit data indicated as an intermediate value of said second operand.

16. A Galois field arithmetic processor according to claim 13:

wherein said conversion circuit is a memory having n banks configured with n memory units having a data width of m, said memory is accessible as n memory units, said memory being supplied with a common address and also accessible as a memory having a data width of m×

n.

17. A Galois field arithmetic processor according to claim 1, further comprising:

an accumulation flag calculating the logic sum of the output of said Galois field vector adder and the preceding output thereof and accumulating the zero flag.

18. A Galois field arithmetic processor comprising:

an instruction decoder providing an instruction for performing a Galois field arithmetic operation on a first operand which is exponentially expressed and a second operand which is vectorially expressed;

a vector-exponent conversion circuit for converting said second operand from a vectorial expression to an exponential expression; and

an arithmetic unit comprising a Galois field exponent adder-subtractor for executing the Galois field arithmetic operation on the first operand and the second operand.

19. A Galois field arithmetic processor according to claim 18, further comprising:

a selector selecting one of said vectorially expressed second operand and the output of said vector-exponent conversion circuit and supplying a result of selection to said arithmetic unit as said second operand;

wherein one of said exponentially expressed data and said vectorially expressed data can be input as said second operand and an instruction is provided for performing the Galois field operation on the two exponentially expressed data.

20. A Galois field arithmetic processor according to claim 18, further comprising:

a first input selector for selecting said first and second operands, and a second input selector for selecting said first and second operands.

21. A Galois field arithmetic processor according to claim 18, wherein the operation is divided into a first stage for converting said second operand and a second stage for processing in said arithmetic unit,

said processor further comprising temporary registers for temporarily holding the data of said first and second stages;

wherein said first and second stages are performed in parallel by pipelining.

22. A Galois field arithmetic processor according to claim 21, further comprising:

a feedback mechanism for feeding back the result of arithmetic operation as said second operand; and

wherein said instruction decoder outputs control data for controlling said temporary registers, each of said selectors and said feedback mechanism;

the processor further comprising a control decision circuit adapted for transmitting said control data sequentially to each stage corresponding to each of said temporary registers, each of said selectors and said feedback mechanism, and determining whether said control data is the one for controlling the corresponding one of said temporary registers, the corresponding one of said selectors or said feedback mechanism thereby to control the corresponding temporary register, the corresponding selector or said feedback mechanism in accordance with the result of determination;

wherein said control data of said feedback mechanism includes a stage flag for indicating the presence or absence of the processing in said first stage, said control decision circuit corresponding to said second operand generates a control signal for bypassing said processing in said first stage in accordance with said stage flag.

23. A Galois field arithmetic processor comprising:

an arithmetic unit comprising a Galois field adder, a Galois field vector multiplier and a Galois field exponent adder-subtractor for executing the Galois field arithmetic operation on a first operand and a second operand; and

an instruction decoder providing an instruction for performing the Galois field arithmetic operation on an exponentially expressed operand and a vectorially expressed operand.

24. A Galois field arithmetic processor according to claim 23, further comprising:

an exponent-vector conversion circuit for converting said second operand from an exponential expression to a vectorial expression; and

a vector-exponent conversion circuit for converting said second operand from a vectorial expression to an exponential expression;

the instruction provided to the instruction decoder for performing the Galois field operation on the operands have alternate vectorial and exponential expressions.

25. A Galois field arithmetic processor according to claim 24, further comprising:

a selector for selecting one of said second operand before conversion, the output of said exponent-vector conversion circuit and the output of said vector-exponent conversion circuit, and supplying the result of selection to said arithmetic unit as said second operand;

wherein one of said vectorially expressed data and said exponentially expressed data can be input as said second operand.

26. A Galois field arithmetic processor according to claim 25, further comprising:

a first input selector for selecting said first and second operands and a second input selector for selecting said first and second operands;

wherein a division instruction is provided by the vectorially expressed input data.

27. A Galois field arithmetic processor according to claim 23,

wherein the operation is divided into a first stage for converting said second operand and a second stage for processing in said arithmetic unit,

said processor further comprising temporary registers for temporarily holding the data of said first and second stages;

wherein said first and second stages are performed in parallel by pipelining.

28. A Galois field arithmetic processor according to claim 27, further comprising:

a feedback mechanism for feeding back the result of arithmetic operation as said second operand; and

wherein said instruction decoder outputs the control data for controlling said temporary registers, each of said selectors and said feedback mechanism;

the processor further comprising a control decision circuit adapted for transmitting said control data sequentially to each stage corresponding to each of said temporary registers, each of said selectors and said feedback mechanism, and determining whether said control data is the one for controlling the corresponding one of said temporary registers, the corresponding one of said selectors or said feedback mechanism thereby to control the corresponding temporary register, the corresponding selector or said feedback mechanism in accordance with the result of determination;

wherein said control data of said feedback mechanism includes a stage flag for indicating the presence or absence of the processing in said first stage, said control decision circuit corresponding to said second operand generates a control signal for bypassing said processing in said first stage in accordance with said stage flag.

29. A Galois field arithmetic processor according to claim 24:

wherein said first and second operands have a data width of m×

n (m, n;

positive integers), said conversion circuits have n conversion circuits with a data width of m, said arithmetic unit uses n arithmetic operators with a data width of m, and n Galois field arithmetic operations with a data width of m can be carried out in parallel.

30. A Galois field arithmetic processor according to claim 29, further comprising:

a flag storage register storing a n-bit flag in continuous areas indicating that the result of arithmetic operation of n arithmetic operators having a data width of m is zero.

31. A Galois field arithmetic processor according to claim 29 having an operation data width of m×

n, further comprising;

an accumulation flag for calculating the logic sum of the output of said Galois field vector adder having a data width of m and the preceding output thereof and accumulating the zero flag; and

an intermediate copy register for storing at n points m arbitrary bit data indicated as an intermediate value of said second operand.

32. A Galois field arithmetic processor according to claim 29:

wherein said conversion circuit is a memory having n banks configured with n memory units having a data width of m, said memory is accessible as n memory units, said memory being supplied with a common address and also accessible as a memory having a data width of m×

n.

33. A Galois field arithmetic processor according to claim 23, further comprising:

an accumulation flag calculating the logic sum of the output of said Galois field vector adder and the preceding output thereof and accumulating the zero flag.

34. A Galois field arithmetic processor comprising:

an arithmetic unit comprising a Galois field vector adder, a Galois field vector multiplier and a Galois field exponential adder-subtractor;

an exponent-vector conversion circuit for converting data from an exponential expression to a vectorial expression; and

a vector-exponent conversion circuit for converting data from a vectorial expression to an exponential expression;

an instruction decoder providing an instruction for executing on the arithmetic unit a Galois field operation on the vectorially expressed input data and the exponentially expressed input data, and the exponential expression 2^m−

1 and the vectorial expression 0 correspond to each other, data sent to the arithmetic unit is processed using either or both of the conversion circuits.

35. A Galois field arithmetic processor according to claim 34, wherein said Galois field exponent adder-subtractor outputs 2^m−

1 when the input is 2^m−

1.

36. A Galois field arithmetic processor comprising:

an instruction decoder;

an arithmetic unit comprising a first Galois field vector multiplier having the two inputs thereof supplied with a first operand and a second Galois field vector multiplier having one input thereof supplied with said first operand and the other input thereof supplied with a result of arithmetic operation;

a one-bit shifter for counting a number of times indicated by a second operand;

an accumulator temporarily holding an output of said second Galois field vector multiplier and supplying said output constituting the result of arithmetic operation to the other input of said second Galois field vector multiplier;

a first input selector selecting said first operand and an output of said first Galois field vector multiplier; and

a second input selector for selecting said second operand and an output of said one-bit shifter and outputting a result of selection as said second operand.

37. Galois field arithmetic processor according to claim 36,

wherein said first and second operands, said accumulator and said first and second input selectors have a data width of m× n (m, n;

positive integers); and

wherein said arithmetic unit uses n first Galois field vector multipliers and n second Galois field vector multipliers having a data width of m.

38. A Galois field arithmetic processor according to claim 36, a source element α

of a vectorial expression is input as said first operand, and an exponent p is input as said second operand, so that a converter can convert exponentially expressed data into a vectorially expressed data which is input into the arithmetic unit.