US 6,636,882 B1Granted

Means and method for performing multiplication

AssigneeVIA Technologies, Inc.

InventorsWei-Ming Su, Shin Yung Chen Banyan, Yi-Lin Lai

Life of this patent

Estimating the term…

Loading patent…

Abstract

A multiplier for obtaining the product of elements in a Galois Field. The multiplier performs the multiplication of two n-bit elements, A(an-1, an-2, . . . , a3, a2, a1, a0) and B(bn-1, bn-2, . . . , b3, b2, b1, b0) in the Galois Field to yield the product C(cn-1, cn-2, . . . , c3, c2, c1, c0), wherein n≧1 ai(i=0˜n-1), bj(j=0˜n-1), and ck(k=O˜n-1) are all binary bits. The multiplier includes: an AND planer, for performing an AND logic operation of every bit ai in A(an-1, an-2, . . . , a3, a2, a1, a0) and every bit bj in B(bn-1, bn-2, . . . , b3, b2, b1, b0) to obtain (an-1bn-1, an-1bn-2, . . . , an-1b0, an-2bn-1, an-2bn-2, . . . , an-2b0, a0bn-1, a0bn-2, . . . , a0b0); and an XOR planer, for performing an XOR logic operation of the output from the AND planer to obtain C(cn-1, cn-2, . . . , c3, c2, c1, c0).

Claims6

Dependent claims

A multiplier, for data decoding of an audio-video processor, which performs a multiplication operation of a first element and a second element in Galois Field to obtain a third element, wherein the first element has a plurality of first bits, the second element has a plurality of second bits, and the third element has a plurality of third bits, and wherein the multiplier comprises:

a first combination circuit, for performing an AND logic operation of the first bits and the second bits to obtain a plurality of fourth bits;
and
a second combination circuit, for performing an exclusive or (XOR) logic operation of the fourth bits outputted from the first combination circuit to yield the third bits;
wherein the multiplier takes substantially one cycle time to perform the AND logic operation and the XOR logic operation to yield the third bits;
wherein each of the first element, the second element and the third element has n bits;
the first bits are represented by (an−1, an−2, an−3, . . . , a4, a3, a2, a1, a0), and ai (i=0˜n−1) is a binary bit;
the second bits are represented by (bn−1, bn−2, bn−3, . . . , b4, b3, b2, b1, b0), and bj(j=0˜n−1) is a binary bit;
the third bits are represented by (cn−1, cn−2, cn−3, . . . , c4, c3, c2, c1, c0), and ck(k=0˜n−1) is a binary bit;
the fourth bits are represented by (an−1 bn−1, an−1bn−2, . . . , an−1b0, an−2bn−1, an−2bn−2, . . . , an−2b0, a0bn−1, a0bn−2, . . . , a0b0), and aibj(i=0˜n−1, j−0˜n−1) is a binary bit;
wherein n is equal to 8;
and wherein:
c0=b0a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b5a7⊕b6a6⊕b7a5⊕b6a7⊕b7a6⊕b7a7;
c1=b0a1⊕b1a0⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b6a7⊕b7a6⊕b7a7;
c2=b0a2⊕b1a1⊕b2a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3⊕b5a7⊕b6a6⊕b7a5⊕b6a7⊕b7a6;
c3=b0a3⊕b1a2⊕b2a1⊕b3a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b5a7⊕b6a6⊕b7a5;
c4=b0a4⊕b1a3⊕b2a2⊕b3a1⊕b4a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3⊕b7a7;
c5=b0a5⊕b1a4⊕b2a3⊕b3a2⊕b4a1⊕b5a0⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b3a7⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3;
c6=b0a6⊕b1a5⊕b2a4⊕b3a3⊕b4a2⊕b5a1⊕b6a0⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b5a7⊕b6a6⊕b7a5;
and
c7=b0a7⊕b1a6⊕b2a5⊕b3a4⊕b4a3⊕b5a2⊕b6a1⊕b7a0⊕b6a7⊕b7a6⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b5a7⊕b6a6⊕b7a5.

17 more elements

A method for obtaining a product of elements in Galois Field, wherein the method is used for data decoding in an audio-video processor, wherein the method is for multiplying a first element in the Galois Field by a second element in Galois Field to obtain a third element, wherein the first element has a plurality of first bits, the second element has a plurality of second bits, and the third element has a plurality of third bits, the method comprising:

performing an AND logic operation of the first bits and the second bits to obtain a plurality of fourth bits;
and
performing an XOR logic operation of the fourth bits to obtain the third bits;
wherein substantially one cycle time is taken to perform the AND logic operation and the XOR logic operation to obtain the third bits;
wherein each of the first element, the second element and the third element has n bits;
the first bits are represented by (an−1, an−2, an−3, · · · , a4, a3, a2, a1, a0), and ai (i=0˜n−1) is a binary bit;
the second bits are represented by (bn−1, bn−2, bn−3, · · · , b4, b3, b2, b1, b0), and bj(j=0˜n−1) is a binary bit;
the third bits are represented by (cn−1, cn−2, cn−3, · · · , c4, c3, c2, c1, c0), and ck(k=0˜n−1) is a binary bit;
the fourth bits are represented by (an−1 bn−1, an−1bn−2, · · · , an−1b0, an−2bn−1, an−2bn−2, · · · , an−2b0, a0bn−1, a0bn−2, · · · , a0b0), and aibj(i=0˜n−1, j−0˜n−1) is a binary bit;
wherein n is equal to 8;
and wherein:
c0=b0a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b5a7⊕b6a6⊕b7a5⊕b6a7⊕b7a6⊕b7a7;
c1=b0a1⊕b1a0⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b6a7⊕b7a6⊕b7a7;
c2=b0a2⊕b1a1⊕b2a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3⊕b5a7⊕b6a6⊕b7a5⊕b6a7⊕b7a6;
c3=b0a3⊕b1a2⊕b2a1⊕b3a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b5a7⊕b6a6⊕b7a5;
c4=b0a4⊕b1a3⊕b2a2⊕b3a1⊕b4a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3⊕b7a7;
c5=b0a5⊕b1a4⊕b2a3⊕b3a2⊕b4a1⊕b5a0⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b3a7⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3;
c6=b0a6⊕b1a5⊕b2a4⊕b3a3⊕b4a2⊕b5a1⊕b6a0⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b5a7⊕b6a6⊕b7a5;
and
c7=b0a7⊕b1a6⊕b2a5⊕b3a4⊕b4a3⊕b5a2⊕b6a1⊕b7a0⊕b6a7⊕b7a6⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b5a7⊕b6a6⊕b7a5.

17 more elements

Dependencies are inferred from the claim text.