PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact



19I16 IJAET0916949 v6 iss4 1615to1621 .pdf



Original filename: 19I16-IJAET0916949_v6_iss4_1615to1621.pdf
Author: vr.lakshmigorty

This PDF 1.5 document has been generated by Microsoft® Word 2013, and has been sent on pdf-archive.com on 04/07/2014 at 08:09, from IP address 117.211.x.x. The current document download page has been viewed 389 times.
File size: 263 KB (7 pages).
Privacy: public file




Download original PDF file









Document preview


International Journal of Advances in Engineering & Technology, Sept. 2013.
©IJAET
ISSN: 22311963

MULTIPLICATION OF INTEGERS IN MIXED
RADIX NUMBER SYSTEM
H. B. Kekre1 and V. R. Lakshmi Gorty2
1

Senior Professor, Department of Computer Science
Mukesh Patel School of Technology Management & Engineering, Mumbai, India
2
Associate Professor, Department of Computer Science
Mukesh Patel School of Technology Management & Engineering, Mumbai, India

ABSTRACT
In this paper, two integers are considered with two radices and are represented with the multiplication of these
integers in the mixed radix form. In the second part of the paper, more than two radices are taken and obtained
the sum of the integers. A MATLAB code is generated to obtain the mixed radix form of these integers developed
during the study. The extension of the same procedure is done for n-integers and n-radices. The application of
the mixed radix system is used in signal, image processing for data compression and many other computer
applications.

KEYWORDS: Multiplication in Mixed radix system, integers, radices.

I.

INTRODUCTION

Let N be any integer consisting of radix r , then N  mn1r n1  ...  m2 r 2  m1r  m0 . In case of
mixed radix form general representation is: N  mn1rn1...r3r2 r1  ...  r2r1m2  r1m1  m0 , where

r1 , r2 , r3 ,..., rn1 are different radices and when r1  r2  r3  ...  rn1  r , then mixed radix reduces
to fixed radix system. Thus mixed radix is general and fixed radix is a special case of mixed radix
system. N in case of a fixed radix can be decomposed by dividing N by r successively to get
coefficients m0 , m1 , m2 ,..., mn1 as remainders. In case of mixed radix N can be decomposed by
dividing N by r1 to obtain m0 as a remainder and quotient can then be divided by r2 to obtain m1 as

remainder. The process can be continued till we obtain mn 1 . Thus n -tuple  mn1 ,..., m2 , m1 , m0  is
obtained representing number N .
Kekre and Lakshmi Gorty in [1] have given the addition of numbers in Mixed Radix system. They
have also generated a MATLAB code for the possible outcomes on addition of integers by mixed
radix system. The Author in [2] describes the magnitude comparison, sign detection and overflow
detection for the residue number system was facilitated by converting the residue representations into
the associated Mixed-Radix number system. In [3] applications have been shown for security using
Mixed Radix design flow. In [4] the author explains modulo mi addition time is independent of the
word length of operands. In [5] of his Doctoral Dissertation, presented a generic sign detection
algorithm based on Mixed Radix Conversion algorithm MRC-II and an optimum algorithm for sign
detection based on a special moduli set. The Author also presented a scaling algorithm based on
Mixed Radix Conversion.
The non-negative integers have been represented in standard radix representation in [6]. The author
also gave an alternate method for mixed-radix representation was used with some computational
advantages compared to standard radix representations, especially when applied to parallel
implementations. The applications to the mixed radix system of integers using radix 2 and radix 4
have been stated in the paper [7]. In 2004, author illustrated as in [8], an integer 0  X  M can be

1615

Vol. 6, Issue 4, pp. 1615-1621

International Journal of Advances in Engineering & Technology, Sept. 2013.
©IJAET
ISSN: 22311963
represented by N mixed radix digits. The digits can be generated sequentially through residue
subtraction. In [9] the design of residue number system (RNS) to binary converters was considered.
The moduli set uses moduli of uniform word length (n to n+1bits). It is derived from a previously
investigated four-moduli set. Three RNS-to-binary converters were proposed for this moduli set: one
using mixed radix conversion and the other two using Chinese Remainder Theorem. In [10] various
FFT processors, such as pipelined or memory-based architectures, have been proposed for different
applications have been shown. Authors designed Radix-2 FFT Algorithm and Radix-4 FFT Algorithm
of a system by using FFT controller. Authors in [11] present about how the 128-point mixed radix
FFT/IFFT algorithm implemented to power consumption and hardware cost also be saved. Memory
based FFT architecture decompose a larger FFT computation into several cascaded smaller FFTs and
utilizes a single FFT core to reduce the hardware cost. Section II gives developing Mixed Radix
system for any two integers using two radices. In Section III results and discussion for all possible
ways in which the mixed radix Multiplication takes place has been discussed. Section IV presents
conclusion and scope for the future work. Section V gives the applications in Computers.

II.

MIXED RADIX SYSTEM

Considering N1 and N 2 as any integers consisting of radices r1 , r2 , then general representation of any
integer is given below as:

N1  r2 r1m2  r1m1  m0
N2  r2 r1n2  r1n1  n0
N1  N2   r2 r1m2  r1m1  m0    r2r1n2  r1n1  n0 

(1)
(2)
(3)

log  N1  N2   log   r2 r1m2  r1m1  m0    r2 r1n2  r1n1  n0  

log  N1  N2   log  r2 r1m2  r1m1  m0   log  r2 r1n2  r1n1  n0 

(4)

Applying antilog to the both sides of (4), the value of N1  N 2 is obtained.
In Mixed Radix the combination can be

r1  2; r2  3 then m1  0,1; m2  0,1, 2
r1  2; r2  5 then m1  0,1, 2; m2  0,1, 2,3
r1  2; r2  7 then m1  0,1, 2,3; m2  0,1, 2,3, 4
and so on as shown in [1].
There can be four cases for the integers in the mixed radix form represented:
Case 1: If N1  even; N2  even, the output of results with all possible values of m1 , m2 , n1 , n2 are
considered under the criteria of Mixed Radix applicability with the help of a code generated in
MATLAB and obtained the possible values of N1 and N2 , along with N1 * N2 .
% N1 is even and N2 is even (multiplication)
syms r1 r2 m1 m2 n1 n2 m0 n0 N1 N2;
x=1;
r1=2;r2=3;
for m1=0:1:(r1-1)
for n1=0:1:(r1-1)
for m2=0:1:(r2-1)
for n2=0:1:(r2-1)
n0=0;
m0=0;
N1=r1.*r2.*m2+r1.*m1+m0;
N2=r1.*r2.*n2+r1.*n1+n0;
fprintf('\n m2
m1
m0
n2
n1
n0
N1
N2
N1*N2\n')
fprintf('\n %3.4f %3.4f %3.4f %3.4f %3.4f %3.4f %3.4f %3.4f
%3.4f\n',m2,m1,m0,n2,n1,
n0, N1, N2, N1*N2)

1616

Vol. 6, Issue 4, pp. 1615-1621

International Journal of Advances in Engineering & Technology, Sept. 2013.
©IJAET
ISSN: 22311963
x=x+1;
end
end
end
end
Case 2: If N1  even; N2  odd, the output of results with all possible values of m1 , m2 , n1 , n2 are
considered under the criteria of Mixed Radix applicability with the help of a code generated in
MATLAB and obtained the possible values of N1 and N2 , along with N1  N2 .
% N1 is even and N2 is odd
syms r1 r2 m1 m2 n1 n2 m0 n0 N1 N2;
x=1;
for m1=0:1:(r1-1)
for n1=0:1:(r1-1)
n0=1;
for m2=0:1:(r2-1)
for n2=0:1:(r2-1)
n0=1;
m0=0;
N1=r1.*r2.*m2+r1.*m1+m0;
N2=r1.*r2.*n2+r1.*n1+n0;
fprintf('\n m2 m1
m0 n2
n1
n0
N1
N2
N1xN2\n')
fprintf('\n %3.4f %3.4f %3.4f %3.4f %3.4f %3.4f %3.4f %3.4f
%3.4f\n',m2,m1,m0,n2,n1, n0, N1, N2, N1xN2)
x=x+1;
end
end
end
end
Case 3: If N1  odd; N2  even, the output of results with all possible values of m1 , m2 , n1 , n2 are
considered under the criteria of Mixed Radix applicability with the help of a code generated in
MATLAB and obtained the possible values of N1 and N2 , along with N1  N2 .
% N1 is odd and N2 is even
syms r1 r2 m1 m2 n1 n2 m0 n0 N1 N2;
x=1;
for m1=0:1:(r1-1)
for n1=0:1:(r1-1)
for m2=0:1:(r2-1)
for n2=0:1:(r2-1)
n0=0;
m0=1;
N1=r1.*r2.*m2+r1.*m1+m0;
N2=r1.*r2.*n2+r1.*n1+n0;
fprintf('\n m2 m1 m0
n2
n1
n0
N1
N2
N1xN2\n')
fprintf('\n %3.4f %3.4f %3.4f %3.4f %3.4f
%3.4f
%3.4f %3.4f
%3.4f\n',m2,m1,m0,n2,n1, n0, N1, N2, N1xN2)
x=x+1;
end
end
end
end

1617

Vol. 6, Issue 4, pp. 1615-1621

International Journal of Advances in Engineering & Technology, Sept. 2013.
©IJAET
ISSN: 22311963
Case 4: If N1  odd; N2  odd, the output of results with all possible values of m1 , m2 , n1 , n2 are
considered under the criteria of Mixed Radix applicability with the help of a code generated in
MATLAB and obtained the possible values of N1 and N2 , along with N1  N2 .
% N1 is odd and N2 is odd
syms r1 r2 m1 m2 n1 n2 m0 n0 N1 N2;
x=1;
for m1=0:1:(r1-1)
for n1=0:1:(r1-1)
for m2=0:1:(r2-1)
for n2=0:1:(r2-1)
n0=1;
m0=1;
N1=r1.*r2.*m2+r1.*m1+m0;
N2=r1.*r2.*n2+r1.*n1+n0;
fprintf('\n m2 m1 m0
n2
n1
n0
N1
N2
N1xN2\n')
fprintf('\n %3.4f %3.4f %3.4f %3.4f %3.4f
%3.4f
%3.4f %3.4f
%3.4f\n',m2,m1,m0,n2,n1, n0, N1, N2, N1xN2)
x=x+1;
end
end
end
end
Multiplication of three natural numbers with mixed radix:

N1  r2 r1m2  r1m1  m0
N2  r2 r1n2  r1n1  n0
N3  r2 r1 p2  r1 p1  p0
N1  N2  N3   r2 r1m2  r1m1  m0    r2r1n2  r1n1  n0    r2r1 p2  r1 p1  p0 

(5)

log  N1  N2  N3   log   r2 r1m2  r1m1  m0    r2r1n2  r1n1  n0    r2r1 p2  r1 p1  p0  

log  N1  N 2  N3 
 log  r2 r1m2  r1m1  m0   log  r2 r1n2  r1n1  n0   log  r2 r1 p2  r1 p1  p0 

(6)

In the similar manner, if N1  even; N2  even; N3  even. The output of results with all possible
values of m1 , m2 , n1 , n2 , p1 , p2 are considered under the criteria of Mixed Radix applicability with the
help of a code generated in MATLAB and obtained the possible values of N1 , N2 and N3 , along
with N1  N2  N3 .
% N1 is even , N2 is even and N3 is even
syms r1 r2 m1 m2 n1 n2 m0 n0 p1 p2 p0 N1 N2 N3;
x=1;
for m1=0:1:(r1-1)
for n1=0:1:(r1-1)
for p1=0:1:(r1-1)
for m2=0:1:(r2-1)
for n2=0:1:(r2-1)
for p2=0:1:(r2-1)
n0=0;
m0=0;
p0=0;
N1=r1.*r2.*m2+r1.*m1+m0;
N2=r1.*r2.*n2+r1.*n1+n0;

1618

Vol. 6, Issue 4, pp. 1615-1621

International Journal of Advances in Engineering & Technology, Sept. 2013.
©IJAET
ISSN: 22311963
N3=r1.*r2.*p2+r1.*p1+p0;
fprintf('\n m2
m1 m0 n2
n1 n0
p0
p1 p2 N1 N2 N3
N1xN2xN3\n')
fprintf('\n %3.4f %3.4f %3.4f %3.4f %3.4f
%3.4f
%3.4f %3.4f %3.4f
%3.4f
%3.4f %3.4f
%3.4f\n',m2,m1,m0,n2,n1, n0, p0,p1,p2,N1, N2, N3,N1xN2xN3)
x=x+1;
end
end
end
end
end
end

III.

RESULTS AND DISCUSSION

All other possible ways in which the mixed radix Multiplication can be in the following manners:

N1  even ; N 2  even, N 3  odd
N1  even ; N 2  odd, N 3  odd
N1
N1
N1
N1
N1

 odd ; N 2  even, N 3  odd
 odd ; N 2  even, N 3  even
 odd ; N 2  odd, N 3  odd
 even ; N 2  odd, N 3  even
 odd ; N 2  odd, N 3  even

A code has been generated in the similar manner and all values for the initial radices are obtained.
And in the similar manner values of the sum of the possible integers were obtained. These
representations can be extended to n-numbers and find the possible sum of these numbers by
considering the possible values of a2 , a1 , a0 , b2 , b1 , b0 ,... in the same way. As taken in [1],

N1  r2 r1a2  r1a1  a0
N2  r2 rb
1 2  rb
1 1  b0
N3  r2 rc
1 2  rc
1 1  c0
N4  r2 r1d2  r1d1  d0
.
.
.

Nn  r2 r1n2  r1n1  n0
.
.
.
Now considering the numbers in more than three radices:

N1  r4 r3r2 r1m4  r3r2 r1m3  r2 r1m2  r1m1  m0
N 2  r4 r3r2 r1n4  r3r2 r1n3  r2 r1n2  r1n1  n0
  r4 r3r2 r1m4  r3r2 r1m3  r2 r1m2  r1m1  m0 

N1  N 2  

  r4 r3r2 r1n4  r3r2 r1n3  r2 r1n2  r1n1  n0  

 log  r4 r3r2 r1m4  r3r2 r1m3  r2 r1m2  r1m1  m0 

log  N1  N 2   

 log  r4 r3r2 r1n4  r3r2 r1n3  r2 r1n2  r1n1  n0  


(7)
(8)

As shown earlier cases antilog is applied to the equation (8).
All other possible ways in which the mixed radix Multiplication can be in the following manners:

1619

Vol. 6, Issue 4, pp. 1615-1621

International Journal of Advances in Engineering & Technology, Sept. 2013.
©IJAET
ISSN: 22311963
% N1 is even , N2 is even;
syms r1 r2 m1 m2 n1 n2 m0 n0 N1 N2;
x=1;
for m1=0:1:(r1-1)
for n1=0:1:(r1-1)
for m2=0:1:(r2-1)
for n2=0:1:(r2-1)
for m3=0:1:(r3-1)
for n3=0:1:(r3-1)
for m4=0:1:(r4-1)
for n4=0:1:(r4-1)
n0=0;
m0=0;
N1=r1.*r2.*r3.*r4.*m4+r1.*r2.*r3.*m3+r1.*r2.*m2+r1.*m1+m0;
N2=r1.*r2.*r3.*r4.*m4+r1.*r2.*r3.*m3+r1.*r2.*m2+r1.*m1+m0;
fprintf('\n m4 m3 m2 m1 m0 n4 n3 n2
n1 n0 N1 N2
N1XN2\n')
fprintf('\n %3.4f %3.4f %3.4f %3.4f %3.4f
%3.4f %3.4f %3.4f %3.4f
%3.4f
%3.4f %3.4f
%3.4f\n',m4,m3,m2,m1,m0,n4,n3,n2,n1, n0, N1, N2, N1XN2)
x=x+1;
end
end
end
end
end
end
end
end
Thus in general the numbers are calculated and its numbers by mixed radix method for a given set of
radices.
General representation is:
N  mn1rn1...r3r2 r1  ...  r4 r3r2 r1m4  r3r2 r1m3  r2 r1m2  r1m1  m0 , where r1 , r2 , r3 ,..., rn1 are
different radices.

IV.

CONCLUSION AND FUTURE WORK

In this paper, a simple to understand and easily applied mixed radix system for multiplication of
integers with known radices is developed. Integers with more than two radices can be multiplied and
obtained with all the possible results of the multiplication of integers represented as a result of mixed
radix system. Due to developed MATLAB code also the process becomes simpler and readily
available to use. The addition, subtraction of the mixed radix integers have been studied by the
authors in their past work. In the future work the division of mixed radix integers will be developed.
The work is already in progress.

V.

APPLICATION

This method is very much useful in computer applications, in reading or sorting a particular number
N from the multidimensional array or sequence of numbers from its specified location.

REFERENCES
[1].
[2].
[3].

1620

Kekre, H. B. and Lakshmi Gorty, V. R., June (2013): Addition of integers in Mixed Radix System,
International Journal of Computer Applications, Vol. 72, No. 3, 40-44.
Israel K., (1993): Computer Arithmetic Algorithms, Prentice Hall PTR.
Rafiev A., September (2011): Mixed Radix Design Flow for Security. Applications, Technical
Report Series.

Vol. 6, Issue 4, pp. 1615-1621

International Journal of Advances in Engineering & Technology, Sept. 2013.
©IJAET
ISSN: 22311963
[4].
[5].
[6].
[7].
[8].
[9].

Shugang W., September 4–7, (2005): Number Conversions between RNS and Mixed Radix Number
System Based on Modulo (2p − 1) Signed Digit Arithmetic, SBCCI’05.
Mohammed Zakaria Akkal, (2008): Non-modular-operation algorithms in residue number system
based on mixed radix conversion. Doctoral Dissertation.
Imad Bako M., (2010): Using Mixed-Radix Method for Representing and Processing Numbers in
Parallel Manner, IASJ, 52-62.
Elisardo Antelo, Javier D. Bruguera, and Emilio L. Zapata, September (1996): Unified Mixed Radix
2-4 Redundant CORDIC Processor, IEEE transactions on Computers, vol. 45, no. 9, 1068-1073.
Wai Kai Chen, (2004): The Electrical Engineering Handbook.
Pemmaraju V. Ananda Mohan, September (2007): RNS-To-Binary Converter for a New Three-





Moduli set 2n1  1, 2n , 2n  1 , IEEE transactions on circuits and systems-II, vol. 54, no. 9, 775-779.
[10]. Badukolu. Yadagiri, A. Gopala Sharma, (2013): Design and Implementation of VLSI, Architecture
for A generalized Mixed-Radix (GMR) algorithm of FFT, International Journal of Latest Trends in
Engineering and Technology, Vol. 2, Issue 3, 293-302.
[11]. Radhika, R., Ramesh, R., (2013): FFT/IFFT Mixed Radix Processor for Wireless Applications,
International journal of innovative research & development, Volume 2, Issue 3, 525-532.

AUTHORS
H. B. Kekre has received B.E (Hons.) in Telecomm. Engineering from Jabalpur University
in 1958 M.Tech (Industrial Electronics) from IIT Bombay in 1960 M. S. Engg (Electrical
Engg.) from University of Ottawa Canada in 1965 and Ph.D. (System Identification) from
IIT Bombay in 1970. He has worked as Faculty of Electrical Engg. and then HOD
Computer Science and Engg. at IIT Bombay. After serving IIT for 35 years he retired in
1995. After retirement from IIT for 13 years he was working as a professor and head in the
Department of Computer Engg. and Vice Principal at Thadomal Shahani Engineering
College Mumbai. Now he is Senior Professor at MPSTME SVKM’s NMIMS University.
He has guided 17 Ph. Ds more than 100 M.E./M. Tech and several B.E./ B.Tech projects
while in IIT and TSEC. His areas of interest are Digital Signal processing Image Processing
and Computer Networking. He has more than 450 papers in National / International
Journals and Conferences to his credit. He was Senior Member of IEEE. Presently He is
Fellow of IETE Life Member of ISTE and Senior Member of International Association of
Computer Science and Information Technology (IACSIT). Recently fifteen students
working under his guidance have received best paper awards. Currently eight research
scholars working under his guidance have been awarded Ph. D. by NMIMS (Deemed to be
University). At present eight research scholars are pursuing Ph.D. program under his
guidance.
V. R. Lakshmi Gorty has overall eighteen years service. Initially she worked with in
Engineering Colleges under Mumbai University and now at SVKM’s NMIMS University,
MPSTME. She has done her Ph.D. from University of Pune. She has attended many seminars
and workshops. She published twenty three papers at national and international journals and
conferences. She has been a resource person for MATLAB in state and national level and
visited many colleges with this Performa. She is member of many professional bodies like
IAIAM, ISTE, INS and IMS. She is also Congress Member of IAENG. She was the co-chair
of ICTSM (International Conference) 2011 held at SVKM’s NMIMS University, MPSTME.
She worked as an editor of Springer series, where the selected papers of peer reviewed were
published. She worked coordinator of the International conference ICATE 2013, sponsored
by IEEE X-plore digital library. She is editor of Indian journal of science, engineering &
technology management, approved with an ISSN 0975-525 X, Techno Path (National
Journal) since its first issue (vol. I), January 2009.

1621

Vol. 6, Issue 4, pp. 1615-1621


Related documents


19i16 ijaet0916949 v6 iss4 1615to1621
2i20 ijaet0520821 v7 iss2 308 317
ijetr011743
ijeas0406019
ijeas0407005
table of content volume 6 issue 6 jan2014


Related keywords