Multiplier in a galois field

• US 4,918,638 A
• Filed: 10/09/1987
• Issued: 04/17/1990
• Est. Priority Date: 10/15/1986
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Murase, Kazuhiro, Matsumoto, Michihito
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US07/107,363
• Time in Patent Office: 921 Days
• Field of Search: 364/746.1, 364/754
• 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
• CPC Class Codes: H03M 13/033 Theoretical methods to calculate these checking codes
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials

Abstract

A circuit effects regular multiplicaton of two field elements in a Galois field GF (2^m). Each of the field elements is expressed by an m-bit binary number. The two field elements are applied to a binary multiplier array which generates (2m-1)-bit partial products. The partial products are divided by a generator polynomial of the Galois field to produce final m-bit binary products.

Claims

1. An apparatus for carrying out multiplication of field elements P=Σ

p_i ·

α

ⁱ, Q=Σ

q_i ·

α

ⁱ (i=0 through m-1) in a Galois field GF(2^m) whose generator polynomial is g(x)=x^m +Σ

k_i ·

xⁱ (i=0 through m-1, ki=binary coefficient) comprising;

a binary multiplier array supplied with the field elements P, Q for generating partial products R=Σ

r_n ·

α

ⁿ (n=0 through 2m-2) where r_n =Σ

p_u ·

q_v for all n=u+v (u=0 through m-1≦

n and v=0 through m-1≦

); and

a polynomial reducer supplied with the partial products R for generating final products S=Σ

s_i ·

α

ⁱ (i=0 through m-1, Si=binary component of S) through division of the partial products R by the generator polynomial.

2. An apparatus according to claim 1, wherein said binary multiplier array comprises AND gates each for effecting an AND operation of p_i ·

q_i and exclusive-OR gates for effecting bit addition of outputs from said AND gates.

3. An apparatus according to claim 1, wherein said polynomial reducer comprises a plurality of exclusive-OR gates for reducing terms of α

^2m-2 through α

^m of the partial products R to terms of α

^m-1 through α

⁰ thereof and effecting bit addition of the terms which have been reduced and the terms of α

^m-1 through α

⁰ of the partial products R.

4. An apparatus according to claim 1, wherein said polynomial reducer comprises a plurality of exclusive-OR gates arranged for reducing each term α

ⁿ of the partial products R to terms of α

^n-1 through α

^n-m thereof in repeated cycles from n=2m-2 to m, thereby reducing terms of α

^2m-2 through α

^m of the partial products R to terms of α

^m-1 through α

⁰ thereof.

5. An apparatus according to claim 4, wherein said polynomial reducer further includes AND gates connected so that one input of each of the AND gates is controlled by a coefficient k_i of the generator polynomial.