College Performance Data
Digital Logic And Computing Systems
Copyright By PowCoder代写 加微信 powcoder
Chapter 06 – RTL Components
EEL3701C Fall 2022
DEPARTMENT OR UNIT NAME. DELETE FROM MASTER SLIDE IF N/A
Department of Electrical & Computer Engineering
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Register-Transfer Level (RTL)
Transistors
Logic Circuits
Micro Architecture
(Register-Transfer Level)
Instruction set Architecture
Complex circuit components are made from simple elements
Information flows are represented, processed, transported and stored as words in registers.
Information flow from register to
register through combinational units:
Register-Transfer
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Word (bundle)gates
Multiplexer / Demultiplexer
Encoder / Decoder
Arithmetic Circuits
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Group of n 1 signals
n is the width of the bus in bit
Graphical Representation:
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
At RT-Level, buses are used to connect system components.
Advantages compared to point-to-point:
Low hardware overhead: all components used the same bus.
scalability: easy to add new components without the need to redesign.
Easy “broadcasting”: one component writes, all others read.
Drawbacks compared to point-to-point:
Sequential communication.
Single point of failure.
Technology must allow multiple outputs on single line (“Tri-State”).
Component 1
Component 2
Component n
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
N-bit (Word) gate
A n-bit (word) gate is a grouping of n 1 independent gates
Inputs and outputs are n-bit buses
Graphical representation:
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplexer
A Multiplexer (n :1 MUX) connects one of n inputs to a single output at a time.
Also known as data selector
n data inputs xn-1,…x0, 1 data output z
k select input (address inputs) ak-1,…a0, n 2k (usually: n = 2k)
Logic function:
mj=mj(ak-1,…,a0) is the j-th minterm
of k variables.
ak-1,…,a0 “addresses” the input data:
address = i z=xi .
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplexer
m-bit input and output m times n:1 MUX.
Enable-Input EN;
EN=0 z = 0 regardless of the data and select input.
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplexer
4:1, 2-bit MUX with enable input.
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Demultiplexer
A demultiplexer (1: n DEMUX) connects 1 single input to one of n outputs at a time.
A DEMUX is the “Inverse” of a MUX.
Logic function and circuit.
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
A n-bit Binary-Encoder has …
a n-bit word X input, of which maximum one bit xi can be 1.
a k-bit Word Z output, which corresponds to index i binary coded;
Encoder have an additional output IA (Input Active), used to recognized cases where all input are 0.
If all xi = 0 IA = 0, otherwise IA = 1.
EN=0 Z=0..0, regardless of X.
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Example: 8-bit Binary-Encoder.
Priority-Encoder: many inputs xi can be at 1 simultaneously.
The output is the binary code of the biggest Index i for xi = 1,
i.e inputs have “priorities”: xn-1 has the highest priority and x0 the lowest.
0 1 2 3 4 5 6 7
X0 X1 X2 X3 X4 X5 X6 X7 z2 z1 z0 IA
0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0 1 1
0 0 1 0 0 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 0 1 1 1
0 0 0 0 1 0 0 0 1 0 0 1
0 0 0 0 0 1 0 0 1 0 1 1
0 0 0 0 0 0 1 0 1 1 0 1
0 0 0 0 0 0 0 1 1 1 1 1
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
A 1-of-n decoder has …
a binary-coded n-bit word X as input.
a k-bit word Z, k = 2n, as output,
zi = 1, if and only if X represents the number i
EN=0 Z=0..0.
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Example: 1-of-4 decoder.
In general: En/Decoder are used to change codes.
Conversion to binary Binary encoder.
Conversion from binary Binary decoder.
X0 X1 z3 z2 z1 z0
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 0 0 0
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Arithmetic Components
Fixpoint Adder/ multiplier
Fixpoint divider
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Adder / adders
2-level normal form (SOP)
Vector function with n+1 function of 2n+1 variables
truth table with 2(2n+1) entries
Hardware overhead: exponential (!) with n
Not feasible, even for very small n
Delay: 2tpd (tpd … Gate propagation time)
Fastest possible adder
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Full Adder
n-bit Adder cam be built as cascade of 1-bit adders
The basic element, a 1-bit adder, is called full adder
xi yi ci-1 si ci
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Truth Table
Logic functions
2-level logic
Hardware overhead: 5 gates. Delay: 2tpd
Full Adder
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Ripple-Carry Adder
A Ripple-Carry Adder is built as cascade of n full adders
Hardware overhead: 5n gates, very cheap
Delay: 2ntpd, very slow
The carry-signal cn-1 has the highest delay, since it must go through all addition stages
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Ripple-Carry Adder
Example: 4-bit Ripple-Carry Adder
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Ripple Carry Adder in VHDL
architecture ripple_carry of add is
constant n : integer := … ;
signal X, Y, S, C : std_logic_vector (n-1 downto 0);
signal OVL, CARRY_IN : Std_logic;
for i in 1 to n-1 loop
S(i) <= X(i) xor Y(i) xor C(i-1);
C(i) <= (X(i) and Y(i)) or (X(i) and C (i-1)) or (Y(i) and C(i-1));
end loop ;
S(0) <= X(0) xor Y(0) xor CARRY_IN;
C(0) <= (X(0) and Y(0)) or (X(0) and CARRY_IN) or (Y(0) and CARRY_IN);
OVL <= C(n-1);
end ripple_carry;
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Sequential Adder (Bit-serial)
A single full adder is used
The addition is done stepwise
The carry is saved in a flip flop
Parallel to serial converter is needed at the inputs
Serial to parallel converter at the output
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Bit-Serial Adder: VHDL-Code
architecture bit_serial of add is
constant n : integer := ... ;
signal XREG, YREG, SREG : std_logic_vector (n-1 downto 0);
signal X, Y, S, CI, CO : std_logic_vector;
X <= XREG(0); Y <= YREG(0);
S <= X xor Y xor CI;
CO <= (X and Y) or (X and CI) or (Y and CI);
sch_r: process (CLK)
if (CLK‘event & CLK = ´1´) then
XREG <= ´0´ & XREG (n-1 downto 1) ; -- shift left
YREG <= ´0´ & YREG (n-1 downto 1) ;
SREG <= S & SREG (n-1 downto 1) ;
end process ;
end bit_seriell ;
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Carry-Lookahead Adder
How can we speed up the slow carry signal?
Introduction of two help functions
gi ..."generate carry": gi =1 a carry will be generated in position i (ci=1), regardless of ci-1
pi ... "propagate carry": pi =1, i will be propagated (ci=1); otherwise, the carry will be absorbed
Full adder-equations
Advantage? the right expression for ci is simple
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Carry-Lookahead Adder
A 2-level circuit that generates all carry simultaneously is called Carry-Lookahead Generator
Carry-logic for ripple-carry adder
Carry-logic for carry-lookahead Adder
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Carry-Lookahead Adder
4-bit Carry-Lookahead Adder
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Carry-Lookahead Adder
Hardware overhead
Carry-Lookahead Generator
logic function for ci has i+2 product terms, with one literal. It can therefore be realized with i+2 gates.
Sum of all product terms ci:
Generation of help functions pi and gi: 2n gates
Computing the sums si: n gates
Total hardware overhead:
Delay: 4tpd
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Combinational Adder
Side-by-side comparison of combinational n-bit adder
Ripple-Carry Carry-Lookahead 2-Level Logic
Hardware overhead [#gates] 5n
Delay [tpd] 2n 4 2
16-bit adder, tpd= 0.1 ns
Ripple-Carry: 80 gates, 3.2 ns delay
Carry-Lookahead: 200 gates, 0.4 ns delay
2-level logic: 130000 gates, 0.2 ns delay
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Combinational Adder
Adder for large bit width
Carry-lookahead adders are expensive: quadratic hardware overhead for large n is not practical
Alternative:
Realize carry-lookahead generator in multiple level logic
Hybrid adder combines various adders such as ripple-carry and carry-lookahead.
4-bit 3-level logic adder
with carry-lookahead adders
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Subtractors
Subtractors are built in the same way as adders
1-bit full subtractor:
Like adders, there is ripple-borrow and borrow-lookahead subtractors
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Adder / Subtractor
Adder/Subtractor for 2-complement numbers
In 2’s complement representation subtraction is done through addition
Adder/Subtraction circuit
with following operations:
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplier
Array-Multipliers: combinational circuit to perform multiplication
Principle “shift and add”: result is the sum of partial shifted sums
Start with the most significant bit and shift right, or
Start with the least significant bit and shift left
Hardware overhead: O(n2) gates
n2 2-bit multiplications: n2 2-AND gates
n n-bit additions: n(n-1) full adder
Delay: O(n)
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Array-Multiplier
Example: 3 x 3 bit array-multiplication Z=X*Y
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Sequential Multiplier
Partial sums are accumulated stepwise
Shift & Add Algorithm
1. load X,Y
2. C←0, P←0
3. Iterate n-times:
then P←P+X
else P←P+0
shift (C,P,Y) 1 digit left
4. Result is in (P,Y)
- Y is stored in a partial sum register -> save 1 register
– “logic shift”, i.e. fill right with 0s
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Example: n=4, X= 1410=1110, Y=710=0111
C P Y next step Operation
0 0000 0111
+ 1110
0 1110 0111
0 0111 0011
+ 1110
1 0101 0011
0 1010 1001
1 1000 1001
0 1100 0100
0 1100 0100
0 0110 0010
Sequential Multiplier: Shift & Add
Iteration 1: Y(0) = 1 add X
Shift right
Iteration 2: Y(0) = 1 add X
Shift right
Iteration 3: Y(0) = 1 add X
Shift right
Iteration 4: Y(0) = 0 add 0
Shift right
Result 01100010 = 9810
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Sequential Multiplier– VHDL Code
constant n : integer := . . .
variable X, Y : std_logic_vector (n-1 downto 0);
variable P : std_logic_vector (n-1 downto 0);
variable C : std_logic;
P := “0 … 0“; C := ´0´
for i in 0 to n-1 loop
if Y(0) = ‘1‘ then
P := (P(n-1 downto 0) + X);
else NULL;
P := C & P(n-1 downto 1);
Y := P(0) & Y (n-1 downto 1);
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplication with Signed Numbers
Case 1: sign and magnitude representation
Compute magnitude and sign
Multiply the magnitudes
Compute the sign of the result
Negate the result if negative
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplication with Signed Numbers
Case 2: sequential multiplication (shift & add) with 2-complement operands
“Arithmetic shift” (signed shift, sign extension) : shift left with sign instead of 0
Sign in position pn-1; on overflow in cn-1 shift pn-1+cn-1
Then is what was computed
We need to subtract through P←P–X to get the correct result
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Sequential Multiplier
C P Y Iteration Operation
0 0000 0101 Iteration 1: Y(0) = 1 Add X
+ 1001
0 1001 0101 shift right
0 1100 1010 Iteration 2: Y(0) = 0 Add 0
+ 0000
0 1100 1010 shift right
0 1110 0101 Iteration 3: Y(0) = 1 Add X
1 0111 0101 shift right
0 1011 1010 Iteration 4: Y(0) = 0 Add 0
0 1011 1010 shift right
0 1101 1101 Result: 11011101 = -3510
Example 1: n=4, X= -710=1001, Y=510=0101
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplication with Signed Numbers- VHDL Code
constant n : integer := …;
variable P, X, Y : std_logic_vector (n-1 downto 0);
variable YS, C : std_logic;
P := 0; C := 0; YS := Y (n-1);
for i in 0 to n-1 loop
if Y (0) = ‘1′ then
C & P := (P(n-1 downto n) + X);
else null;
P & Y := (C or P (n-1)) & P & Y (n-1 downto 1);
if YS = ‘1‘ then P := P – X; else null; end if;
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplication with Signed Numbers
0000 0101
1110 1010
1 1100 0101
1 1101 0101
Iteration 1: Y(0)=1, Add X
1111 0101
1110 0010
1111 0001
Iteration 2: Y(0)=0, Add 0
Iteration 3: Y(0)=1, Add X
1110 1010
Iteration 4: Y(0)=0, shift 4 (add 0 + shift)
1111 0001
0000 |1110 (1s compl)
0000 |1111 (2s compl)
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplication with Signed Numbers
0000 1011
0001 1101
0100 1101
0011 1011
0010 0110
0001 0011
0100 0011
1111 0001
– X : + 1101
0010 0001
Iteration 1: Y(0)=1, Add X
Iteration 2: Y(0)=1, Add X
Iteration 3: Y(0)=0, shift 3
Iteration 4: Y(0)=1, Add X
Y < 0, correction: subtract 2nX
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Multiplication with Signed Numbers
0000 1011
1110 1101
1 1011 1101
Iteration 2: Y(0)=1, Add X
Iteration 1: Y(0)=1, Add X
1101 1110
1110 1111
1 1011 1111
Iteration 4: Y(0)=1, Add X
0000 1111
- X : + 0011
1101 1111
1101 1011
Iteration 3: Y(0)=0, Shift 3
Y < 0, correction: subtract 2nX
Final Result
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Booth Multiplier
Observations
No need to add when Y is equal ‘0’. Shift only!
It is not necessary to perform (m+1) additions when there is a chain of (m+1) 1‘s in Y.
We just need to subtract X at the begin of the chain and add X back at the end of the chain:
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Booth Multiplier
Booth Recoding: Y is translated into Y'
Y is extended by y-1= 0
Y‘ is built as follows yi'= yi-1–yi
Meaning of y':
y'= 0 : shift right
y'= –1 (rsp. "S"): P←P–X, right shift (Begin of a chain of 1s)
y'= 1 (rsp. "A") : P←P+X, right shift (End of a chain of 1s)
Y= 011111100111
011111100111 0
Y' = A00000S0A00S
Needs 9 additions
needs 4 additions/subtraction
0101010101010
0111011101110
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Booth Multiplier
0 00000 00000 Iteration 1: Y'(0) = S subtract X
- 01011
1 10101 00000 right shift
0 11010 10000 Iteration 2: Y'(1) = 0 right shift
0 11101 01000 Iteration 3: Y'(2) = 0 right shift
0 11110 10100 Iteration 4: Y'(3) = 0 right shift
0 11111 01010 Iteration 5: Y'(4) = A add X
1 01010 01010 right shift
0 00101 00101 Result: 0010100101 = 16510
Make sure the shift (arithmetic/logic) is done correctly
for 2-complement numbers
Example: n=5, X= 1110= 01011, Y = 1510= 01111 Y'= A000S
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Division (X = Q.Y+R) after "Restoring Algorithm"
Classic method, assuming always yi=1
Then subtract the divisor.
If the result is positive then move to the next digit
If the result is negative, then set yi=0 and add the divisor back (i.e. cancel subtraction)
Example: n=3, X=310, Y=210
0 0 0 1 1 / 010 =
– 0 1 0
1 1 1 0
0 0 0 1
– 0 1 0
1 1 1 1
0 0 1 1
– 0 1 0
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
An Array-Divider performs the division as combinational circuit
1 subtractor (Ex. ripple-borrow subtractor) is needed per row
How to perform correction in case of negative result?
The result is negative when the borrow (left most bit) is equal '1'
Idea: feed the borrow back (right) as signal a .
a=0, the subtraction was correct, no need to correct
a=1, instead of the difference, use the minuend
Special full-subtractor "D-Box":
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Array-Divider
Example: n=3: (x2,x1,x0) / (y2,y1,y0) = (q2,q1,q0) +(r2,r1,r0) / (y2,y1,y0)
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Sequential Divider – Restoring Algorithm
Quotient is computed stepwise
1. Load operand register Y
2. AC←0, Q←X
3. Iterate n-times:
shift (AC,Q) one position left
then AC←AC+Y
else Q(0)←1
4. Quotient is in Q, Rest in AC
- “logic shift“ Fill left with 0
- AC and Y are (n+1)-bit numbers in
2-complement
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Sequential Divider – Restoring Algorithm
X= 1410=1110,
Y=610=0110
00000 1110
00001 1100
11011 1100
00001 1100
00011 1000
11101 1000
+ 00110
00011 1000
00111 0000
00001 0000
00001 0001
00010 0010
11100 0010
00010 0010
Iteration 1: Left shift
Subtract Y
add Y back
Iteration 2: Left shift
Subtract Y
add Y back
Iteration 3: Left shift
Subtract Y
Iteration 4: Left shift
Subtract Y
add Y back
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
Restoring Algorithm: VHDL-Code
Computes Q = X/Y, Quotient in Q, Rest in AC
constant n : integer := . . .;
signal X, Y, AC, Q : std_logic_vector (n-1 downto 0);
AC <= 0; Q <= X;
for i in 1 to n loop
AC & Q <= (AC & Q) sll 1; -- sll: shift logic left
AC <= AC -Y;
if AC < 0 then
AC <= AC + Y ;
else Q(0) <= ‘1‘ ;
end loop ;
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
DEPARTMENT OF ELECTRICAL & COMPUTER ENGINEERING
xn-1x0x1zak-1a1a0N:1 Multiplexer
N:1 Multiplexer
xn-1x0x1mmmmzak-1a1a0N:1, m-bit MUXEN
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com