NOVEL IMPLEMENTATION METHOD OF MODULO 2N

MULTIPLICATION FOR DIGITAL SIGNAL PROCESSING

MOHAMED ARIF BIN NUN

Fakulti Kejuruteraan ElektrikUniversiti Teknologi Malaysia

RINGKASAN

Kertaskerja ini membentangkan satu cara baharu dalam mana satupendaraf modulo 2N dijelmakan secara isomorfik menjadi sepasangpenyampur modulo 2 dan modulo 2N-2. Bilangan penyampur­penyamp ur penuh yang diperlukan untuk perlaksanaan bertambahsecara linar dengan bertambahnya panjang perkataan N, dan tidakdengan secara eksponen, dan kelewatan pengantaran sistem tetappada asasnya tidak berubah dengan bertambahnya N.

ABSTRACT

This paper presents a novel method in which a modulo 2N mul­tiplier is transformed isomorphically into a pair of modulo 2 andmodulo 2N- L adders. The number of full-adders required for im­plementation increases linearly with increasing wordlength N, ratherthan exponentailly, and the system propagation delay remainsbasically constant with increasing N.

1. Introd uction

In the past few years there has been an increasing application of~umber-theoretic concepts to digital signal processing". In mostSIgnal processing algorithms the multiplier invariably forms one oft?e main computing elements, especially in hardware implementa­tions in which component cost and processing speed are essentialfor efficient and economic hardware structures. In this paper, wepresen t the main ~ncepts and results of a novel technique with:-Vhich a modulo 2 multiplier can be is~morphically transformedInto a pair of modulo 2 and modulo 2 - adders. It is shown thatt~e number of full-adders required for their implementation increaseslinearly with increasing wordlengths of the multiplier operands,

2. Modulo. 2N

Multiplication Using "Forced" Operands d P dCorrectIOn an ro uct

is The a~p~oach proposed is b~ed. on a reduced multiplier, whichthe original modulo 2N multIplIer whose operands and d

are constraIned to take on only the odd val f h pro uctues rom t e set

g : A---+A' = A + CA

and g : B--;oB' = B + dB

such that

C

A+B+lB

Ao

d

1o1o

c

11oo

o1o1

b

oo11

a

This leads to a very simple correction circu~ consisting of a modu­lo 2N adder which is just the conventional 2 adder with the carrydigit excluded, and two gating circuits, each consisting of (N-l)2·input A D gates and one inverter. The output C from this correc­tion unit is then subtracted from P' to obtain the actual product

Po'

3. Internal Algebraic Structure of Reduced Modulo 2N Multipliers

This congruance relationship expresses our proposed multip­lication scheme, in which (A' x B') describes the reduced multip­lication and C = (dA + cB + cd) the correction required to obtainthe actual product. The block diagram of the overall configurationis shown. in Fig. 1.

The VarIOUS values of C corresponding to all possible combinationsof a and b, the L.S.B's of A and B respectively, are given below.

In the following, we present only the main concepts and resultso&our study of the algebraic structure of a general reduced modulo2 multiplier. The corresponding detailed arguments and proofsare in Ref. 2.

3.0 The group under modulo 2N reduced multiplication

Let (Zo, ® 2N) be the multiplier modulo 2N whose operandsare constrained to odd values, i.e, from the set Zo .Theorem 1: - The set of odd integers, i.e. Zo = (x : x odd integer,1 ~ x ~ 2N - 1), forms an Abelian group under multiplicationmodulo 2N • This group, which we denote by G(2N ) , has orderG(2X

G(2N ) = 2N - 1

For the specific cases of our reduced multipliers moduli 20, 21

and 22 , we can prove, using elementary concepts in number theory~pages 123 to 125 in Ref. 2), that for each of these multipliers,Its algebraic structure can be directly described and the complete~ultiplication table can be generated by a single element x E Zo'If x is a primitive root of 2N , where N =0, 1 or 2.

(B + d) modulo 2NA'xB':: (A+c)

rather than exponentially as in most conventional I'm It'F h h P emen atiomurt ermore t e system propagation del . h ."b . II ' ay IS s own to rernan-

asica y constant WIth increasing N The art' f h

:~~u~::~Nt:u~~f~~~~~:iO:~ cost-effective Pta:~~~~ ~t~cet~r:~s~~:

ZN = (0,1,2, .... , 2N -1)

Hence if A B and A' B' h' . '. " are t e operands to the ori . alreduced multIpliers respectively then A' B' Z h gm and, ,e D' were

ZD = (x: x odd integer, 1 ~ x ~ 2N - 1).

These modified operands may b d . d fb h e errve rom the originals

y t e mapping gA and gB' where

c = fo for A odd ~ for B odd

L1 for A even d =~ for Beven

Multiplying these 'forced' operands, we obtain,

P'o

- AB + dA + cB + cd modulo 2

!Ie~ce the required product PO:: A x B modulo 2N~~wen by AB = (A' x B') - (dA + cB + cd) mod.

52

S5

= gl.m modulo 2N, 1 ~ gl,m ~ 2N

-1,

where 1 = 0 or 1 and 0 ~ m < n.

From the corollary to Lemma 1, and the results in Lemma 2, thecomp onents 3m and xl, will go through 2N- 2 ~d 2. values res­pect ively before repeating themselves. Therefore this will generate(2N- 2) x 2 = 2N-1 different elements of G(2N

), the above cong-ruence describes gi uniquely.,m

Let us now express G(2 N) in terms of its cosets,i.e, G(2N)= {V0 ; V11 using subgroup K, and G(2

N)

::: {w .W . . \" . W } using the subgroup L.0 ' l' . . . . . , 'vi ' . . . . . .. n

If we con sider any two elements of G(2N), say gl' ,m' and gl" , m",

then, it can be shown (Ref. 2)

(Vl.O'VI 1'······, Vl,i'",=

and Wo = (Wo,o' WO,I) = L, WI = (Wl •O· WI,l)

. Wi = (Wi, o· Wi, 1)'

Where vd.i = xd 3i modulo 2N, d = 0 or 1, 0 ~ i ~ n

and W. = 3i xd modulo 2N, in which the value x is either xj orx as (i';scribed by Corollary (b) of Lemma 2.

k

In general, each element g of G(2N) can be presented by themodulo 2N product of po~~s of x and 3 via the following cong­

ruence, i.e.

4. APplicat ion of Theoretical Results

The subgroups K and L may be used to organise G(2N

) by for­ITling the relevant cosets in the usual way .

Let the cosets w.r.t. K be Vo and VI and those w.r.t. L be WOoVv •.. , .. ,Wj • • • • • • Wn ,

n 1= (2N - 2_1), given by

Vo = (Vo.O'VO.I'VO.2'····VO.i'···Vo .n)=

3.1 Detailed algebraic structure of reduced modulo 2N multipliers

Corollary. (a) The values xh

== 1 and xi == 2N - 1

+ 1 (modulo 2N) may be expressed as powers of 3 (modulo 2N).(b) The values xj == -1 and x

k== 2N-1 -1 (modulo 2N) can not

be powers of 3.

1. == xi modulo 2N, for i = 0, 1 .1~ The value of x is either x == -1 modulo 2N orx == 2N- I -1 (see Corollary (b) of Lemma 2).

54

As a result of the above-mentioned Lemmas, the algebraic structureof our modified or reduced modulo 2N multiplier, for N ~ 3, canbe described in detail via the following theorem.

Theorem 2:- The group G(2N), as described by Theorem 1, for~ 3, is isomorphic to the direct product group K x H, where

K and H are cyclic groups of orders 2N- 2 and 2 respectively.

In our following two lemmas and one theorem we extend theanalysis to cases where N ~ 3 and will show that the table of ageneral reduced modulo 2N multiplier, N ~ 3, can still be des-

cribed completely but this time two elements Z. Z. e ZD are. d to zenerate i I, JrequIre to generate It.

NLemma 1:- 32 = (2n+ 2) (x(n) ) + 1 for n ~ 1 where x(n) is anodd number for all n.

Corollary. The element 3 in Z2N has order 2N- 2 in G (2N).

Lemma 2:- There are four elements, ± 1 and ( 2N-I ±. 1), in G(2 N)having order 2

K = (k k I ••. k... k ), 0 ~ i < 2N - 2.0 , 1. m

m = 2N- 2_1, k j e. G(2N) and k, ::: 3i modulo 2N.Thus subgroup L is given by L::: (10' Ii) where 10' Ii E G(2N) and

The subgroup K is given by

=3.l,.f

g

(9 x 11) modulo 16

that, their product P is given by P = g. modulo 2N, where(1' + 1");; i modulo 2 and (m' + m") :=. I,

= j modulo 2N- 2.

Since the subscripts I and m denote the cosets w.r.t. the subgroupsK and L respectively, then we know that gl', m' E VI" and also

Wm' ; and gI ", m"E VI'" and also €. Wm"

Furthermore, their modulo 2N product g.. belongs to both cosetsVi and W. where i and j are the modulo 2:,Jand modulo 2N- 2 sumsf1 ' I"J d '" . Io , ,an m, m respective y.

Consequently, if we denote the operation (i.e. multiplication)between any two cosets (w.r.t.K] by Oland that between any two(w.r.t.) by Om then it is not difficult to see that

VI,o 1 VI ,, = V(I'+ I,,)modul02,andWm,o m

Wm" = W(m'+m,,)modul02N- 2

In other words, if each coset is mapped onto its correspondingindex, i.e. VI' --+ l' , VI" ---+1" and

Wm' ~m' , Wm" ~m", Then operations between cosetsmay be mapped onto modulo addition operations between indicesas shown by the two commutative diagrams below.

(a) VI " VI" 0 1 VI' 0 1 VI"

// ~= V.

1

I' I" G:)2 i = (1' + 1")) modulo 2

(b) Wm' Wm" 0 W 0 Wm m' m m"

1 1~

=W.

J,j ~ (m' + m"~m' , m" E)2N- 2

+ modulo 2 - 2

Finally, the complete reduced modulo 2N multiplication may bedescribed in a compact way as follows.

56

Let fg

and fp

be the mappings given by fg : gl ,m ~

(1,111) and fp :<» 2N ~ (}2,@ 2N- 2) where

~ G(2N ) , 1 E.(0,1), me-(0,1,2, 2N- 2 -1)gl,m

and 0 is the parallel component-wise operation between any twoordered-pairs (1' , m') and

(1" , m" ), i.e. ~

(1', m ') 0 (1", m") = t[ l' (±)2 1" ]

[ro' Gl2 N - 2 m"]) = (i,j).

Thus, for any two elements of G(2 N), say gl' rrt J

and g we have the following useful commutative diagramItt m tt

shown in Fig. 3:

It is now easily seen that the mapping-pair fg , f transforms theoriginal reduced multiplier into two adders, moduYo 2 and modulo2N- 2 respectively, operating in parallel.

To illustrate this isomorphism between the multiplier and the adder­pair, let N = 4. Two possible organisations ofG(24

) into sets of,c?setsare (a) G(2 4 ) = {( 1,3,9,11) ; (7,5,15,13)) and (b) G(~) =t(1,7 ) ; (3,5) ; (9,15) ; (11, 13)}. .Consider multiplying, modulo 16, the number 9 by 11: USl~g themapp ings shown in Tables 1 and 2, and the commutative diagram(3), we may substitute additions modulo 2 and modulo 4 for ouroriginal modulo 16 multiplication as shown below.

9 11I If f~g ~g

(0,2) ; (0,3)+0

(0,2)0(0 ,3) = [oG2

0] , [ 2G4 3] = (0,1)

~n practice, the results that we have deriv~d are easily app~e? to theIlllplementation of the general modulo 2 reduced multiplier, TheSUbgroup K is first generated by simply forming, modulo 2N, the

57

58

16

..,···.,

r,..J,

,I

I

",(a) ....I.

II

II

II

II

,,/

II

/

8

WORDLENGTH N(bits)

42o

100

Fig. 2 Complexity in full-adder requirement for (a) direct implf~mentation and (b) proposed implementation of modulo 2multiplier.

Novel implementation method of modulo 2N multiplication

In both approaches, the number of full -adders (F.A's) requiredCan give some indication of the overall hardware complexity. Withthe direct method we can easily work out that the number of F.A'sneeded is (1 + 2 + 3 + N-l). With the proposed approach,

we would need ( (N-2) + 1) F.A's for the modulo 2N - 2 and modulo2 adder-pair, along with (N-l) F.A's for each of the two (N-l)­bit adders used in the correction circuit, giving a total of 3( - 1)F.A's. The effect on the full-adder requirement with increasing word­length N is shown in the graph in Fig. 2. We see that with the methodproposed , the full-adder count increases linearly with N, while th atof th e direct approach is proportional to 2. For N > 6, the pro­posed implementation technique required considerably fewer full­adders.

Po

successive powers, up to the (2N -2 -1) th f 3 5 r a==1 31 32 , 0 or, e.g. K == 3, , , .

,- - - - - - - - - - - - - ---- -- -- - - - - - - - --- -- - -- - ---,I

32N - 2 -1 2N - 2 .,3 == 1, ei ther manually or by means of a straight

~~~r~ ~~,!!~utedrd program for large values of N. The resultinga er may be further structurall . IT d .

~~~h~~(~:~~~).-state machine technique for adder;d~~fo~;~ b~s:~;

IL "__ _ _ _ _ _ _ I

- -- - - - - - - - - - - - - - - - - - - - __ J

5. General Comparis With Th .2N M It' I' on I e DIrect Implementation of Modulou Jp iers

In making a detailed .. I' comparISon of our proposed method ofImp e:~ntll~ a modulo 2

Nmultiplier with that of the direct ap

proac In w ch the first N bits of the partial roducts are s .USIng rows of full-adders, the following observatfons are made.ummed

. I, ,,

L,,IA ,, I

LJ"",Cl A' I-i_ I

I

~ ~~~

REDUCED P' CORR'N,

, ~ 0 II U ® R=>, c.:: UNITI ~ 0

~ 2N v~

rV 0 ~ I, IB , B' ,,

DI, I,I

I II I.

I

Fig. 1 Block diagram of modulo 2N multiplication using 'forced'operands and product correction.

Table 2(a). Reduced multiplier table organised by subgroup (1,7).

Table 1(a). Reduced multiplication table organised by subgroup (1,3,9,11)

..-0 A'

~6 II 7 5 15 131 3 9 11 I

I 1 3 9 11 7 5 15 13

3 3 9 II 1 5 15 13 7

9 9 II 1 3 15 13 7 50

B' 11 11 1 3 9 13 7 5 IS

i

7 7 5 15 13 1 3 9 11I

5 IS 13 7 I 3 9 11 15 II

3I 15 15 13 7 5 I 9 11 1II

13 13 7 5 15 I 11 1 3 9l

10 11I

9 15 I 11 13

9 IS I 11 13II

15 9 I 13 11II

11 13 I 7II

13 11 I 7II

7 I 3 5

I7 I 5 3

3 5 I 9 15I

3I

15 95 II

A'

01

I3 5 I

3I

5 I

5 3

5 9 15 III

3 15 9 It

I15 11 13 I

I

9 13 111I

13 7

11 7

7

7

00

00

7 7

3 3

01

5 5

- B'9 9

10

15 15

11 1111

13 13

Furthermore, with the direct approach the propagation delaythrough the circuit, apart form the ripple delays through each rowof F.A's is dependent on 1. With our method, however, the systemdelay is basically constant, and is the Sum of the delays through thefirst correction adder, a circuit for encoding into partition blocks.the adder-pair, a circuit for decoding from the partition blocks, andthe final correction adder.

6. Conclusions

A novel method of implementing a general modulo 2N mul­tiplier has been presented, and consists of constraining the operandsto odd values for a modified or reduced multiplier and correctingthe output to obtain the actual modulo 2N product. Analysis of thealgebraic structure of the reduced multiplier shows that a reducedmodulo 2

Nmultiplier is isomorphic to two adders, modulo 2N - 2

and 2 respectively, operating in parallel. Finally, it was observedthat when compared with the direct way of implementing modulo2

Nmultipliers, the proposed approach leads to a circuit which

required considerably less full-adder units and possesses a basicallyconstant system propagation delay.

References

1. MoClellan, J .H., " umber theory In digital signal processing",(Prentice-Hall, 1979).

2. Bin un, M.A., "Modular decomposition techniques for stored­logic digital filters", Ph.D. Thesis, Dept. of Electronic and Elec­trical Engineering, Loughborough University of Technology.Leics., England, 1977.

3. Bin un, M.A., and Woodward, M.E., "Halfadders modulo 2N

using read-only memories", Electronics Letters, 30th. May 1974.Vol. 10No. 11.

60

Fig 3 C ive di. . ommutabve ragrarn for tra nsfonning a reduced multiplier modul 2N ,N 2 0 mto two

add ers, modulo 2 and moduJo 2 - respectively, operating in parallel.

i) B.Sc. (Estate Management) SouthbankPolytechnic London (1968 - 1972).

ii) A.R.I.C.S. (November 1973)

31hb.Januari,1940i) Peperiksaan iktisas the Royal Institution

of Chartered Surveyors, United King­dom - 1965

ii) Diploma Pentadbiran Awam, UniversitiMalaya - 1970

19hb. November, 1948

Professor Madya,Ketua J abatan Pengurusan Hartabenda danPenilaian, Fakulti Ukur, Universiti TeknologiMalaysia.

i) Pegawai Penilaian di Bahagian Penilaian,Perbendaharaan Malaysia.(julai 1965 - Oktober 1973)

ii) Pengarah Penilaian Kawasan di NegeriSernbilan/Melaka (1970 - 1973) danSelangor (April- Oktober 1973).

iii) Pensyarah Kanan ( sekarang ProfessorMadya), Universiti Teknologi Malaysia,(November 1973 hingga sekarang).

i) Fellow of the Royal Institution ofChartered Surveyors.

ii) Fellow of the Institution of Surveyors,Malaysia.

iii) Jurukur Berdaftar, LembagaJurukur Ma­laysia.

KURIKULUM VITAE PENULIS

R. W. COUCHMAN

Kelulusan

Tarikh lahir

Pengalaman

Keahlian iktisas

MOHD. AZMl BIN ARlFFIN

Tarikh lahirKelulusan

Jawatan

] = (iJ )

fg

Table 2 (b). Operation between blocks.

Q ° 2 3

° ° 1 2 31 1 2 32 2 °

3 ° 13 3

° 1 2

616 ) ~(1,71----+°, (3,5) ~ 1(9,15)~ 2 and (l1,13)~ 3

(gl' , m ' ) X (gJ " , m") modulo 2N

1

°°1°

(1" ,m")

°1

gJ ' m'; gJ " ..

J~ Cg ' }

(1' ,m')

1°(1', m')o (I ", m") ={ [1' @2 I "] , [m'@ m"]

2N - 2

G6--_.....) ~(1,3,9 ,11) ) °

(7,5,15,1 3) ) 1

Table l(b). Operation between blocks

62

KHALID RASHID UPPAL

Professor Madya,FakuIti Ukur, Universiti Teknologi Malaysia.

i) PensyarahfPensyarah Kanan,Portsmouth Polytechnic (1972 - 1977)

ii) PensyarahfPensyarah Kanan,Hong Kong Polytechnic ( 1977 - 1979)

iii) Pensyarah Kanan,Royal Agricultural College (1979 _1980)

iv) Professor Madya,Unive~siti Teknologi Malaysia (1980)

v) Berkhidrnat dengan The Ministry ofDefence Land Agent'S Office, Aldershot.

vi) Berkhidmat dengan Collier and Collier,Chartered Surveyors.

vii) Amalan perundingan secara persendirian.

Berkhidmat dengan Lembaga Peperiksa­an Malaysia sebagai Ketua Pasukan

iii)

Sarjana Sains (Kejuruteraan J entera),U.M.I.S.T. (Disember 1974)

i) Telah melibatkan diri dalam bidang aka­demik sejak 27hb. September, 1968.

ii) Sebagai Ketua Jabatan Oun 1975 ­Januari 1976) dan Timbalan Dekan(Februari 1976 - April 1980),Fakulti Kejuruteraan J entera,Universiti Teknologi Malaysia.

Sarjanamuda Kejuruteraan Oentera),Universiti Malaya. Oun 1968).

ii) Professor Madya,J abatan Kejuruteraan J entera,University of Engineering and Techno­logy,Lahore, Pakistan.Oun 1967 - Jun 1975)

22hb. Julai, 1946

Professor Madya,Fakulti Kejuruteraan Jentera,Universiti Teknologi Malaysia.i) Ahli Bersekutu, Institut Kejuruteraan

Jentera, U.K.ii) Chartered Engineer - C.E.I.

iii) Ahli Bersekutu, InstitutJurutera Malaysiaiv) Jurutera Profesyenal, Lernbaga Jurutera

Malaysia.

iii) Professor,Fakulti Kejuruteraan Jentera,Universiti Teknologi Malaysia,Kuala Lumpur.oun 1975 hingga sekarang)

Jawatan

Kelulusan

K.S. KANNAN

Pengalaman

Tarikh lahir

Keahlian iktisas

196019661968

Techno'

5hb. Mei, 1938

Professor,FakuIti Kejuruteraan J entera,Universiti Teknologi Malaysia.

P.Eng., Mem.I.E. Malaysia,C. Eng., F.I. Mech. E. (Lond),C.B.S.T., Mem. C.I.B.S. (Lond),Mem, A.S.M.E. (NY),Mem. A.S.H.R.A.E. (NY).

B.Sc. (Mech. Eng) (Pb)M.Sc. (Thermo) (Birm)Ph.D (Mech. Eng) (Birm)

i) Pensyarah,J abatan Kejuruteraan J entera,University of Engineering andlogy,Lahore, Pakistan.(September 1960 - Jun 1967)

Pengalaman

Jawatan

Kelulusan

Keahlian iktisas

Tarikh lahir

Pengalarnan

Jawatan

64

MOHAMED ARIF BIN NUN

MOHD ZAIN BIN HAJI YUSUF

Penglibatan dalam prosesan isyarat, teoriautomata, pengantaran data, KejuruteraanKomputer dan pemeroses mikro.

67

Ketua J abatan Kejuru teraan Perhubungandan

Ketua Makrnal Sistem Komputermini,

Fakulti Kejuruteraan Elektrik,Univcrsiti Teknologi Malaysia.

pengaIaman

Jawatan

29hb. Julai, 1945

B.Sc. Hons. (University of London - 1971 )M.Sc. (Loughborough University - 1972)Ph.D. [Loughborough University - 1977)

10hb. April, 1949

i) KetuaJabatan Tanah dan Geologi,Fakulti Kejuruteraan Awam,Universiti Teknologi Malaysia.(Mei 1978 - September 1980)

(bagi pemeriksaan kertas soalan danpenggubal kertas soalan).

iv) Ahli Majlis,Institut J urutera Malaysia.

Timbalan Dekan,Fakulti Kejuruteraan Awam,Universiti Teknologi Malaysia.

v) Berkhidmat dengan Tentera Laut DiRaja Malaysia sebagai Pegawai Teknikdalam Pasukan Simpanan.

ii) Timbalan Dekan,Fakulti Kejuruteraan Awam,Universiti Teknologi Malaysia,(Oktober 1980 hingga sekarang)

i) Diploma Kejuruteraan Awam, MaktabTeknik - Mei 1971.

ii) Sarjanamuda Kejuruteraan Awam,University of Strathclyde - Mei 1974

iii) Sarjana Kejuruteraan Awam (Geotekni­kal)University of Mississippi,U.S.A. - Mei 1978.

Tarikh lahir

Kelulusan

Kelulusan

Tarikh lahir

Pengalaman

Jawatan

66