Circuit for the inner or scalar product computation in galois fields

• US 20030068037A1
• Filed: 10/10/2001
• Published: 04/10/2003
• Est. Priority Date: 10/10/2001
• Status: Active Grant

• Current Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Inventors: Fragneto, Pasqualina, Bertoni, Guido, Breveglieri, Luca
• Granted Patent: US 7,206,410 B2
• Time in Patent Office: Days
• US Class Current: 380/30
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A circuit for computing the inner of scalar product of two vectors in a finite Galois field defined by a generator polynomial, wherein each vector includes at least two elements belonging to said finite field, comprises one or more look-up tables storing digital words indicative of said possible combinations and said possible reductions. The digital words in question are defined as a function of the second elements of said vectors and the generator polynomial of the field. The input register(s) and the look-up table(s) are configured to co-operate in a plurality of subsequent steps to generate at each step a partial product result identified by at least one of digital word addressed in a corresponding look-up table as a function of the digital signals stored in the input register(s). The circuit also includes an accumulator unit for adding up the partial results generated at each step to give a final product result deriving from accumulation of said partial results.

Claims

1. A circuit for computing the inner or scalar product of at least two vectors in a finite Galois field identified by a generator polynomial, wherein each said vector includes at least a first and a second element belonging to said finite field, said first and second elements having a plurality of possible combinations and related reductions, the circuit including:

at least one input register for storing digital signals representative of the first elements of said vectors,

at least one look-up table storing digital words indicative of said possible combinations and said possible reductions, said digital words being defined as a function of the second elements of said vectors and said generator polynomial,

wherein said at least one input register and said at least one look-up table are configured to co-operate in a plurality of subsequent steps to generate at each step a partial product result identified by at least one of said digital words addressed in said at least one look-up table as a function of said digital signals stored in said at least one input register,

and wherein the circuit also includes an accumulator unit for adding up said partial results to give a final product result deriving from accumulation of said partial results.

2. The circuit of claim 1, wherein said at least one input register is configured to be scanned and to detect the condition of scanning of said digital signals representative of the first elements of said vectors, and wherein said at least one input register and said at least one look-up table are configured to co-operate in said plurality of subsequent steps until said scanning of said digital signals is completed, whereby upon completion of said scanning said accumulator unit contains said final product result.

3. The circuit of claim 1, including distinct input registers for storing each digital signal representative of a respective first element of one of said vectors.

4. The circuit of claim 1 including:

a first look-up table storing first digital words generated as a function of the second element of one of said vectors and said generator polynomial,

a second look-up table for storing second digital words generated as a function of the second element of another of said vectors and said generator polynomial,

a third look-up table for third digital words generated as a function of said generator polynomial and corresponding to said reductions,

said first, second and third look-up tables being configured to co-operate with said at least one input register in order that at each said step;

a first address for said first look-up table is generated as a function of one said digital signals representative of the first element of one of said vectors stored in said at least one input register and a first digital word is read out from said first lookup table at said first address,

a second address for said second look-up table is generated as a function of another of said digital signals representative of the first element of one of said vectors stored in said at least one input register and a second digital word is read out from said second look-up table at said second address,

a third address for said third look-up table is generated as a function of the contents of said accumulator unit and a third digital word is read out from said third look-up table at said third address, and

said first, second and third digital words are added to the contents of said accumulator unit.

5. The circuit of claim 4, wherein said first, second and third addresses are generated as a result of a shift operation in said at least one input register and in said accumulator unit.

6. The circuit of claim 4, including a first input register and a second input register each for storing a digital signal representative of a respective first element of one of said vectors.

7. The circuit of claim 1 including:

a first look-up table storing first combined digital words respectively representative of all the possible two-by-two sums of first digital words generated as a function of the second element of one of

said vectors and said generator polynomial and second digital words generated as a function of the second element of another of said vectors and said generator polynomial,

a second look-up table for storing second digital words generated as a function of said generator polynomial and corresponding to said reductions, said first and second look-up tables being configured to co-operate with said at least one input register in order that at each said step;

a first address for said first look-up table is generated as a function of the concatenation of two digital signals stored in said at least one input register, said two digital signals being respectively representative of the first elements of one and another of said vectors and a first digital word is read out from said first look-up table at said first address,

a second address for said second look-up table is generated as a function of the contents of said accumulator unit and a second digital word is read out from said second look-up table at said second address, and

said first and second digital words are added to the contents of said accumulator unit.

8. The circuit of claim 7, wherein said first and second addresses are generated as a result of a shift operation in said at least one input register and in said accumulator unit.

9. The circuit of claim 7, including a first input register and a second input register each for storing a digital signal representative of a respective first element of one of said vectors.

10. The circuit of claim 1 including:

a single look-up table storing consolidated combined digital words respectively representative of all the possible three-by-three sums of first digital words generated as a function of the second element of one of said vectors and said generator polynomial, second digital words generated as a function of the second element of another of said vectors and said generator polynomial, and third digital words generated as a function of said generator polynomial and corresponding to said reductions,

said single look-up table being configured to cooperate with said at least one input register in order that at each said step;

a first address generating word is generated as a function of the concatenation of two digital signals stored in said at least one input register, said two digital signals being respectively representative of the first elements of one and another of said vectors and a first digital word is read out from said first look-up table at said first address,

a second address generating word is generated as a function of the contents of said accumulator unit and a second digital word is read out from said second look-up table at said second address,

a single address is generated by concatenating said first and second address generating words and a single digital word is read out of said single look-up table at said single address, and

said single digital word is added to the contents of said accumulator unit.

11. The circuit of claim 10, wherein said first and second address generating words are generated as a result of a shift operation in said at least one input register and in said accumulator unit.

12. The circuit of claim 10, including a first input register and a second input register each for storing a digital signal representative of a respective first element of one of said vectors.