代写代考 EEL3701C Fall 2022

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