This course gives you a complete insight into the modern design of digital systems fundamentals from an eminently practical point of view. Unlike other more "classic" digital circuits courses, our interest focuses more on the system than on the electronics that support it. This approach will allow us to lay the foundation for the design of complex digital systems. You will learn a set of design methodologies and will use a set of (educational-oriented) computer-aided-design tools (CAD) that will allow you not only to design small and medium size circuits, but also to access to higher level courses covering so exciting topics as application specific integrated circuits (ASICs) design or computer architecture, to give just two examples. Course topics are complemented with the design of a simple processor, introduced as a transversal example of a complex digital system. This example will let you understand and feel comfortable with some fundamental computer architecture terms as the instruction set, microprograms and microinstructions. After completing this course you will be able to: * Design medium complexity digital systems. * Understand the description of digital systems using high-level languages such as VHDL. * Understand how computers operate at their most basic level (machine language).
L4.1 Arithmetic blocks
Loading...
来自 Universitat Autònoma de Barcelona 的课程
Digital Systems: From Logic Gates to Processors
184 个评分
从本节课中
Arithmetic components + Introduction to VHDL
<b><font size=4 color=#B22222><b>Click on "v More" to read the purpose of this module</b></font> </b><br/><br/>Arithmetic circuits are an essential part of many digital circuits and thus deserve a particular treatment. <ul><li> The first part of this module presents some implementations of the basic arithmetic operations. Only operations with naturals (non-negative integers) are considered. </li><li>The second part of this module introduces the basics of VHDL with the goal of providing enough knowledge to understand its usage throughout this course and start developing basic hardware models.</li></ul>
与讲师见面
Elena ValderramaProfessor
Departamento de Microelectrónica y Sistemas Electrónicos. UAB.
Jean-Pierre DeschampsProfessor
Lluis TerésProfessor
Centro Nacional de Microelectrónica del CSIC
Merce RullanProfesoraTitular
Departamento de Microelectrónica y Sistemas Electrónicos. UAB.
Joaquín Saiz AlcaineIngeniero Informático
Departamento de Microelectrónica y Sistemas Electrónicos. UAB.
David BañeresProfesor Agregado
Estudios de Informática, Multimedia y Telecomunicación. UOC.
Juan Antonio MartínezCollaborator
APSI - UAB
[MUSIC]
This lesson deals with a particular type of circuits, the
arithmetic components. Arithmetic components are an important
part of practically any digital circuit, and so deserve a particular treatment.
In this lesson, we will present an implementation of every basic operation,
that is to say, addition, subtraction, multiplication
and division. Actually, n-bit binary adders have
already been described several times in preceding lessons,
so that we will just recall that a possible implementation is this one:
an interative circuit, made up of n 1-bit adders.
1-bit adders are generally called "full adders".
The circuit computes X plus
Y plus an initial CARRY,
and the result, S is an (n+1)-bit
number, whose most significant
bit is the output CARRY of the last cell of
the last full adder. Second basic operation,
subtraction. Given to number X and Y, n-bit
numbers, and an initial BORROW, we want to compute
the difference X minus Y minus BORROW. In this case,
the result is smaller than or equal to 2**n - 1,
which is the case, when X has its maximum value 2**n - 1
and when both Y and the BORROW and are equal to 0.
But in this case, the result could also be negative.
And the minimum value of the difference is -2**n,
the value that we get when X is equal
to 0, Y is equal to the maximum value 2**n - 1
and when the BORROW is equal to 1.
Then, how can we represent D? If D is non-negative,
it's an n-bit number that can be
representated in binary, and if D
is negative but greater than or equal to -2**n
then it can be represented with an additional
bit whose weight is negative, that is to say that
Dn has a weight equal to -2**n.
Then, how works the classical pencil and paper
method to compute the difference between two numbers:
at each step, we are going to compute two bits,
a difference bit and a borrow,
an output borrow bit. Actually, the real value
of the difference can be equal to
1, 0, -1 or -2. Then,
we define the borrow, an output borrow,
and a bit d of the difference. If the
result, the real result, is 1 no problem: there is no borrow, and d =1.
If the result is 0, the same: dout = 0
and d = 0. Then, if the result is
negative, first case: the result is -1; then you
could write or say that -1 = -2 + 1.
So, we will choose a bit of the difference equals 1,
but then transmit the borrow to the next step,
with a weight equal to the present weight multiplied by 2,
so that in this case the borrow
- the output borrow - will be equal to 1. You must think
that this borrow actually has a negative weight.
This is 1 and this is -1 with the weight equal to 2.
It's the same as -2.
In the same way, in the case where the real result is -2, we will say that -2
is -2 + 0. So, here the bit
of the difference is 0, and the borrow is equal
to 1, actually it is a negative weight.
Observe now that d is equal to the real
difference computed modulo 2,
because when the real result is odd,
the corresponding bit is 1 and when the
real result is even, the corresponding
bit is 0. And the output borrow
bit is equal to 0, when the real
result is non-negative, and equal to 1 when the real result
is negative. Another comment: the value of
x - y - bin modulo 2 is exactly
the same as the value of x + y + bin modulo 2,
because modulo 2, -1 is the same as 1.
Both numbers are
odd numbers. Let us see an example:
First we compute 12 (decimal 12) minus 9; then
we compute in a step by step way: 0 minus 1 is equal
to -1. Then the difference bit is 1
and the borrow bit is also 1;
0 minus 0 minus 1 once again is equal to minus 1.
Then, here the difference bit is 1 and the borrow bit
is 1, with a negative weight;
next step: 1 - 1 = 0; next step: 1 - 1 = 0,
so that the result is this one (in decimal 3).
Now, let us compute, 9 minus 12: 1 - 0 = 1;
0 - 0 = 0; 0 - 1 is -1; then
here, the difference bit is 1 and there
is a borrow to the next step; 1 - 1 - 1 = -1;
once again, difference bit
equal to 1 and borrow equal to -1, so that
the result is this one, but now the first 1
has a negative weight, and this number
is equal to minus 16 plus 8
plus 4 plus 1 and
this is minus 3. This type of
representation is called
2's complement representation
of the negative number.
This is the algorithm: it's an iteration (a loop)
where at each step, we compute a difference bit,
the modulo 2 sum of the three incoming bits,
two bits of the operands and one borrow input,
and we compute the sign of the difference
x(i) minus y(i) minus b(i). Here
is the algorithm that we can modify. We can
replace this modular 2 sum by the
exclusive or sum of x(i), y(i) and b(i),
exactly in the same way as in the adders that we have seen
before and, as regards the borrow, the
computation of the output borrow, we see that it is
equal to 1 when (three cases): the bit
of x is 0 and the bit of y is 1, or when
the bit of x is 0 and the input borrow is 1,
or when both the bit of y and the input
borrow are equal to 1. In all of those cases,
the result of this operation is negative so that the borrow
must be equal to 1. The corresponding circuit is
this one: an iterative one made up on n identical
components, 1-bit subtractors, that are also called
full subtractors, and every component, every full
subtractor implements those Boolean functions.
Now, an exercise: define a circuit
that generate the difference, x minus y,
without initial borrow in this case, under the
classical form with sign and magnitude, that is to
say the result D (the difference)
is equal to + or -
some absolute value (the magnitude of the difference).
Then, the proposed method is quite simple.
Compute, at the same time, the difference x - y and y - x.
If x - y is non-negative, then the sign
in equal to 0 and the result is this one.
In the contrary case,
if x - y is negative, then
y - x will be non-negative, and the
sign bit will be equal to 1. Here
is a possible solution: we use two
subtractors, that work in parallel; one computes x - y
and the other one computes y - x.
If the sign of x - y is 0, then the sign of
D is equal to 0, and we select as a magnitude
the value D' of the first substractor.
In the contrary case, then we will get here a 1,
the sign of x minus y is equal to 1.
The sign of the result D is equal to 1 also,
and we select, as absolute value (as magnitude
of the difference) the output of the other subtractor
that computes y minus x. Third operation: the multiplication.
Given an n-bit number X
and an m-bit number Y, we want to compute
P equal to X time Y. Then the
maximum value of P is smaller than 2**(n+m)
so that the result P is
a binary number that can be expressed with, at most, n + m bits.
Assume now that Y is expressed in
binary under this form; then P can be written
under this form, and this suggests a
very simple algorithm: we compute a set
of partial products; P(0) is equal to X·Y(0);
P(1) is equal to X·Y(1)·2,
and so on, up to P(m-1) equal to
X·Y(m-1)·2**(m-1),
and once we have computed all those partial products, it
remains to add up all the partial product.
Actually, the computation of the partial products
is very easy: the multiplication
of X by bit (for example) Y(2) along
can be done with a set of AND gates. Here you have
the bits of X, here is the bit Y(i), Y(2) for example.
and then we get, at the output of the AND gates,
all the bits of X multiplied by Y(2) (for example).
And the multiplication
by the power of 2 amounts to adding some
number of 0's to the right of the corresponding number.
To multiply by 2 in binary is as multiplying by 10 in decimal;
it is just a matter of adding a 0 on the right side of the number.
Let us see an example: assume that we define
X = 101101 and Y = to 1011. Then,
first partial product: 1 multiplied by X is equal to X.
Second partial product: 1 multiplied by X is also
equal to X, but with 0 on the right side,
that corresponds to multiplying by 2. Third partial
product: 0 times 101101 is equal to 0, with two 0's
and, finally, 1 multiplied by X is 101101 with three 0's.
So, it's very easy to compute all those artial products, and then,
it's necessary to compute
the sum of all those products, and we get finally
the result of the multiplication. Thus, the
algorithm is this one: at each step (it's an iteration once
again) at each step we must compute the
sum of some value ACC plus the product of X
by a bit of the second operator Y, and multiply
this product by some power of 2,
and we already know that this amounts to shifting
or to adding 0's to the right of the number.
And the result of
this computation, is the new value of the variable ACC.
Then the corresponding circuit is an iterative one, and at each step
we compute (and so on))
this sum, that is to say, adding ACC_IN to X, to some X,
multiplied by a bit y
of the second operand, and this gives us the new value of variable
ACC_OUT. The second operand of every cell
is (first time) X, (second time) X·2, X·4, and
so on, up to X·2**(m-1).
Last operation: division. First, we must
define what we call "quotient", "remainder" and "accuracy" of the
division. Consider two naturals X
and Y, such that X is smaller than Y.
Then we must compute the quotient Q
and the remainder R, such that X
is equal to Q time Y plus the remainder.
Furthermore, Q must be a multiple of 2**(-p),
where p is the accuracy of the division, accuracy expressed
in number of fractional
bits of the result, and the
remainder R must be smaller than Y multiplied
by the same value 2**(-p).
A previous operand alignment may be necessary, in order
that this condition is satisfied. Assume that
X is greater than Y. Thus, what we must do is to substitute
Y by Y multiplied by some
power of 2, so that the condition
(this one) holds true; then we compute X divided by
Y multiplied by 2**k, obtain some result and
finally we multiply the result by 2**k.
In order that the result is obtained
with an accuracy of p fractionary bits,
this computation must be realized with a precision of p + k
fractionary bits. This definition is
equivalent to this one: if we divided here by
Y, we get that X divided by Y is equal
to Q (the quotient) plus R
divided by Y, where the quotient is a multiple of
2**(-p), and where the error
(the error is the difference between the real value of the division of X
by Y and the quotient) this difference
is R divided by Y and, according to this condition, is
smaller than 2**(-p)).
Here is an algorithm that allows to compute the quotient and the remainder.
An initial remainder r(0) is equal to
X (to the dividend). Then, it's an iteration.
At each step, we compute the difference between two times
the preceding remainder and the divisor.
If the difference is negative, then the corresponding quotient bit is 0
and the new remainder is 2 times the preceding one,
but if d is non-negative, then the quotient is 1, and the
new remainder is the difference. Then we get the result under this form:
Q is equal to the number, expressed in binary with the set
of quotient bits that have been computed, multiplied by
2**(-p). In other words, in binary Q is
0.q(1) q(2) ··· q(p)
and R is the last
obtained remainder when i is
equal to p, also multiplied by
this negative power.
Let us see an example. Assume that X is equal to 21,
Y equal 35, and we want an
accuracy of 6 factional units. Then we
compute, 2 times the remainder: 2 times 21
is equal to 42, is greater than Y. So
I can write that 42 is equal to 35 plus 7.
First quotient bit 1 and the new remainder is 7.
Next step: 2 times the preceding remainder, 2 times 7,
14, is smaller than the divisor;
so I can write that 14 is 0 times 35, plus
the difference 14, and we follow up: 2 times 14, 28,
is smaller than 35, so I write that 2 times 14 is
equal to 0 times 35 plus 28 and so on.
The result is that Q is the number (in binary) equal to 100110
(that) multiplied by 2 to the power -6
or, in other words, divided (in decimal)
by 64, so that the quotient is 38
divided by 64, and in binary
it's written under this form, that is to
say 100110, but with 0. here on the left side.
The remainder is 14
multiply by 2 to the power -6. In other words, 14
divided by 64. In binary: this number,
and you can check that, actually,
Q times the divisor, 35, plus
the remainder divided by 64 is
equal to 21 and that the remainder
satisfies this condition.
Corresponding circuit: once again
is an iterative circuit; at each step
we must compute a bit of the quotient
and a new remainder. It's
very easy: we must multiply the preceding remainder
by 2; that means to add
a 0 on the right side of this number, and then to compute the difference
between 2R and Y; if the sign is equal to 0,
that means that 2R is greater than or equal (that the result is non-negative)
in which case the quotient bit is equal to 1,
and the new value of the remainder is the difference.
In the other case, if the sign bit of this difference is equal to 1,
it means that the difference is negative, then the quotient bit is equal to 0
and the new value of the remainder is the preceeding value multiply by 2.
And that's all. Summary of this lesson:
We have described circuits that execute the
basic arithmetic operations, that means addition, subtraction,
multiplication and division, with natural operands
(non-negative integers), and we have given some information
about 2's complement representation of negative numbers.
[BLANK_AUDIO]
