Binary Division Algorithm and Implementation in VHDL
Ing. Filip ADAMEC, Ing. Tomáš FRYZA, Ph.D.
Dept. of Radio Electronics, Brno University of Technology, Purkyňova 118, 612 00 Brno, Czech Republic
xadame24@stud.feec.vutbr.cz, fryza@feec.vutbr.cz
Abstract. This article describes a basic algorithm for a
division operation. Its performance and consideration of
the implementation in VHDL are discussed. There are
described three possible implementations, the maximum
performance in FPGAs, e.g. propagation delays and
number of necessary steps to enumerate the correct result.
In the conclusion the performance and necessary number
of steps are compared.
Keywords
Division operation, VHDL, FPGA, implementation.
1. Introduction
In many applications it is necessary to divide the
integer numbers. There are some algorithms to do it. It can
be done by basic algorithm learnt in elementary school
which using an operation of subtraction. The next possible
algorithm is using the multiplication and there are some
other possible solutions, which use algorithm developed for
real numbers divisions. This algorithm is very fast, but
seems to be very complicated.
The proposed algorithm is not one of the fastest, but is
one of the simplest algorithms what is important. The
algorithm can be implemented in two of ways. One way is
sequential, which is better suited for application where the
division is not very frequent and the space inside FPGA or
PLD is critical issue. The other way is a parallel
implementation respectively pipelined implementation.
However, the solution need much more space in device. On
other hand, the division can be executed in one clock when
pipeline is filled. This solution is better suited for
application where division operation is basic issues
respectively is very frequent.
We searched for some standalone implementation of
division in VHDL language but with no success. This is the
main reason for creating proposed implementation, which
can be used in microprocessors as a division unit or in
other applications as standalone division unit for 32 bits
numbers and can be easily modified for other integers
lengths.
2. Description of division algorithm
2.1 Division by subtraction
This algorithm is very simple because it is used in the
elementary school for division and it is well known. This
algorithm is described below and additional description can
be found in [1, 2 and 3].
1. Align the divisor with the most significant bit of
dividend and mark this value like a div. Set i
according to number of shifts. Set remainder R to
zero.
2. T = R – div.
If T >= 0 set Q(0) and R = T.
If T < 0 clear Q(0).
3. Shift Q one bit right and div one bit left.
4. if i = -1 Q is quotient and R is remainder.
This algorithm has many variations, but its function is
always the same.
2.2 Division by multiplying
This algorithm is described mainly in [1] and is using
multiplication and comparing/subtraction. If the 32bit
division is desired, it must be used 32bit multiplication
with 64bit result. This algorithm is described below.
1. Set the initial value of Q(8-n) = 1 and the bits right
of Q(8-n) to 0.
2. Calculate D*Q.
3. Calculate N-(D*Q) or compare.
a. If D*Q >= 0, N > (D*Q), set Q(8-n) to 1.
b. If D*Q < 0, N < (D*Q), set Q(8-n) to 0.
4. Increment n and repeat until n >= 0 from point 2.
As mentioned above this algorithm is need for 32bit
multipliers with 64bit result what is not very good solution
for FPGA. However if division of 32b long integer is not
978-1-4244-3538-8/09/$25.00 ©2009 IEEE