Title
Vector-Valued Representation of Quaternary Logic Functions
Author(s)
Nakao, Zensho
Citation
琉球大学工学部紀要(30): 41-47
Issue Date
1985-09
URL
http://hdl.handle.net/20.500.12000/1983
Bull. Faculty of Engineering. Univ. of the Ryukyus, No.30.1985
Vector-Valued Representation of Quaternary Logic Functions Zensho NAKAO *
41
Abstract
The elements of the four-element Galois field GF(4) are represented by
concatenating two bits from left to right without any unused combinations: GFH) {(U.0).(1.0).(l).l).(l.l)} . It is shown that all quaternary logic functions on CrF(4) can be represented as vector-valued functions whose components are binary polynomial functions over the two-element Galois field GF(2)=
{»>.l} . With this representation of quaternary logic functions, the design
of corresponding logic circuits is reduced to that of the well-known Boolean circuits.
1. Introduction
It is often necessary to express logic functions in simple canonical form before their designs are attempted. In this note quaternary logic functions over GF(4) will be represented by vector-valued functions whose components are binary polynomial functions over GF{2), and then some concrete conversion fomulas of quaternary polynomials to binary ones are derived; also the corresponding binary logic designs are obtained.
2. Preliminaries
On the set {0,1 } of two symbols 0,1, define two binary operations x + y, x*y (or
juxtaposition: xy) by the following tables:
(1) + I) 1 0 0 1 1 1 0 • 0 1 0 0 0 1 0 1
Figure 1. Tables for addition and multiplication in GF(2)
Received: April 30, 1985
42 Vector Valued Representation of Quaternary Logic Functions: NAK.AO
Then the algebraic system ({0,1} ; ■{-,') is a finite field— Galois field of two elements GF(2). The Boolean algebraic structure ( {0,1} ;/. /, ; and that of GF(2) are related by the following transfrjrmation formulas:
x /\y xy xy x / y
(2) x \/ y x I y \ xy x \ y (x Ay) / (x / y) x x t 1
Consider the polynomial p(x)--- x2 \-\-v 1 over GF(2). then, by actual substitution of the elements of GF(2), we find easily that p(x) is irreducible over GF(2). Let a be a solution of the equation p(x)- (I in an extension field of GF(2). Then the extension field obtained by adjoining a to GF{2) is a two dimensional vector space over GF(2) with the base fl.ff) , where a2 1 I a. Recall a fuel from field theory: a! a 0. i.e.. a a for all elements in any extension field of GR2). We denote the resulting extension field by GF(4) which has elements !l).l.a-,l Ya\ . VVr use1 two bits to express four elements,
thus:
CO 0 ()• 1 I (I • a (0.(1).] I • 1 I I) • a (1.0) *■-••■()• 1 t 1 • a M0.1U* I • J hi • tf-(l.l)
Note that we are expressing the elements of GF(-1) in base a with the higer place value
on the second (i.e.. right) bit.
Summarizing, we have GF(4)= {(0.0).(l.0),(0.1).(l,l)} ; the field structure is shown
by the following tables:
(4) + (0.0) (1.0) (0.1) (1.1) (0. (0. (]. (0. (1. 0) 0) 0) 1) 1) (1 (1 (0 (1 (0 .0) .0) .0) .1) .1) (0.1) (0.1) (1.1) ((1.0) (1.0) (1.1) (1.1) (0.1) (1.0) (0.0) * (0.0) (1.0) (0.1) (1.1) (0.0) (0.0) (0.0) (0.0) (0.0) (1.0) (0.0) (1.0) (0.1) (1.1) (0.1) (0.0) (0.1) (1.1) (1.0) (1.1) (0.0) (1.1) (1.0) (0.1)
Figure 2 . Tables for addition and multiplication in GF(4)
A close look at the tables for GF(4) reveals that they can be built by applying the
binary operations given in (1) (i.e.. Galois field operations) component-wise on the vector
elements in GF(4):
(5)
(x,.x2).(y1,y2)eGF(4),x,,y1eGF(2) «* (xI,x8)+(y1,y2) = (xI+y1.
(x1.x2)(y1,y2)=(x,y,+x2y2,x1y2 + x2y1
The important formulas on the components (i.e.. the elements of GF(2)) of any element
Bull. Faculty of Engineering, Univ. of the. Rytikyus. No.30,1985
(6) x,2 =
2x, =
lC GF(2) .e GF(2)
Using (5). we will show that logic circuits for (x.^ + fy,^) and (x,,x,)(y ,,y2), where
(x wXj),(y,y 2) € GF(4), can be easily designed with two standard Boolean logic gates:
:f>- (AND) and L'£>- (XOR). By the transformation formulas between GF(2)
and Boolean algebra, we can immediately express (x ,y ,) and (x, + y,) in terms of (AND) and (XOR). To reiterate, we let:
43
(x + y) = (xy) =
Figure 3. Circuit symbols for (x + y) and (xy) in GF(2) Logic gates for the field operators for GF(4) are now given by:
(7) (8) x = y ~ x+y Figure 4. (x + y) gate
Figure 5. (xy) gate
3. Formula Translation
In [Nj, we showed that every quaternary logic function can be expressed in polynomial form over Galois field GF(4) with several examples. We now translate all those quaternary polynomial functions studied in (N) to vector form which we can manipulate component-wise using (5) and (6).
For translation of formulas, it is more efficient to have conversion formulas for each monomial of total degree at most six into new forms. Note that it is not necessary to go
44 Vector-Valued Representation of Quaternary Logic Functions: NAKAO
beyond x 3 or y 3 due to the finite field structure which requires x4 = x, x5 = x2, .... y'
y* = y2 etc. The following set of formulas is useful for making the translation:
(9) x J==(xI,x2)8=( 2 (
x3 = (x2)x = (x, + x2)x2)(x,,x2) = (x, 4- x,x2 + x2.0)
y3 = (y*)y=(y > + y2ty2)(yi,y2) = (y.+yty2 + ya,0)
xy2 = (x,,x2)(y, + y2ly2) = (x,y, 4- x,y2 + x2y2,x2y, + x,y2) x3y = x(x2y) = (x,,x2)<xly,4-x2y,4-x2y2,x2y14x,y2)
x*y8 = (x, -f x2lx2)(y, +y,,y2)
x,y2lx2y,-i-x2y2-t-x2y,y2)
x'y2 = (x3y)y-(x,y, + x,x2y, +x2y,,x,y24-x2y2 I-x,x2y2)(y,,y2)
= (x,y, + x,x2y, + x2y, -I- x,y2 + x2y2 + x,x2y2lx,y2 + x2y2 + x,x2y2)
a. Min (x,y ] =Min C(x,,x2),(y,,y2)J
A polynomial expression for Min (x,y) given in (N) is: Min(x,y] =Min ((x^XzUy,^)) =2x
= 2 [xy2 + xys+x2y + xJy) +x2y2+3
By using (5), (6) and (9) repeatedly, we can change (10) to the following form: (11) MinCx.yJ =(0,1) ((x,y, 4-xIy2-hx2y2.x2yI+x,y2) + (xlyl+x,y1y2 + x1y2,x2y1 + x
x2y,y2) + (xly14-xJyl-fx2y2,x2y1 + xly2) + (x1y,-l-xlx2y1+x2
x2y2)) +-(xly1-fx,y2 + x2y1,x2y1 + x1y2 + x2y2) + (l,l) ((x,y,+x,y,y8+x,y2 + x
= (x2y,y2H-x,x2y2 4-x,y,+x,y,y2-I-x,x2y! + x2y,+x,yz,x2y2)
Rewriting as a polynomial in elementary symmetric functions of two variables
among the components, we get:
02) MinCx,y) =Min ((x,,Xa),(y,,y2)) =((xl4-X2
+ x,y2tx2y2)
Bull. Faculty of Engineering. Unit: of the Ryukyus. No.30.1985 45
x ~
= Min (x,y]
Figure 6 . Min (x,y) gate
b. Max (x,y) =Max {(xltx2),(yuy2))
Making lengthy computations using (5),(6) and (9) as is done with Min (x,y) ,we can transform the polynomial function for Max (x,y) obtained in fN) :
(14) Max [x,y] =Max 3x2y3
+x2y2 +x2y3)
+ x,x2y, + x2y, + x
+ x2y2)
Expressing as a polynomial in symmetric functions, we get:
(15)
Max (x,y) =Max i(\ltx2),{yuyz)) =((xl + yj
+ ya) +yiy2 Cxi+x2), (x2+y2J H-x2y2)
[y,
46 Vector-Valued Representation of Quaternary Logic Functions: NAKAO
X
—-v c^
-Max [x.y]
Figure 7. Max (x.y) gate
£ y 102} _ (y~ v \ j02} {2)\* (2\f \
w • A ""VA1»A2^ i X— IX|,A2J
We continue transforming poltnomial functions, and we next take:
<W
x <M»=(x,.x2) {0Zi =3 + 2x + x2,
and
08) (z>x = '2'(xlpx2)=2 + x, which are both derived in (N)
Now. we can change (17) into the following:
= (l,l)4-(x2,x,-f-x2) + (x, + x2,x2)
Similarly, from (18), we obtain the following:
Bull. Fncnlly of Engineering. Unit: of ///<• Ryukyus. No.30,1985 47
1 + x,
1 + x,
Figure 8 . Logic gate for x ;Di2'
Xi
Figure 9. Logic gate for <z)x
4 . Conclusions
By representing the four elements of Galois field GF(4) by a combination of two elements of GF(2), we can express all quaternary logic functions as vector-valued functions with binary polynomial components.
The design of quaternary logic circuits can be made by use of Boolean theory due to the reduction of GF(4) logic to GF(2) logic; also the manipulation of binary polynomial expressions is much simpler.
To support the claim, several concrete computations are made with quaternary logic functions, and their logic designs are also included.
References
(N J Nakao, Z: Logic functions over Galois field GF(4), Bull. Faculty of Engineering,
