CS计算机代考程序代写 ER algorithm COMP3222/9222 Digital Circuits & Systems

COMP3222/9222 Digital Circuits & Systems
8. Digital System Design

Objectives
• Apply design techniques to comprehensive digital design

problems
– Consider the datapath components needed, the finite state machines

required for their control and their description in VHDL
• Learn how digital systems comprising datapaths and control

circuits can be derived from an ASM chart
• Look at a number of practical issues to do with real system inputs

and outputs

20T3 COMP3222/9222 Digital System Design L08/S2

Digital system

Datapath

Controller

status
signals

control
signals

Digital system

inputs outputsComposed of adders,muxes, registers,
counters, decoders
etc.

Comprising a finite
state machine

• A digital system comprises a datapath, which transforms the data as
required by a specification, and a controller (control unit, control path),
which supervises the operation of the datapath by monitoring its
status and setting control signals

• The behaviour of both parts is conveniently modelled in an integrated
manner using an Algorithmic State Machine (ASM) chart (see later)

20T3 COMP3222/9222 Digital System Design L08/S3

Design Example 1 (pp 438-450):
A digital system with k registers

20T3 COMP3222/9222 Digital System Design L08/S4

Recall details for connecting registers to a bus
• Consider two 2-bit registers

– 3-state (tri-state) buffers used to avoid “tying” outputs together

20T3 COMP3222/9222 Digital System Design L08/S5

Control circuit design
• Consider the control required to swap the contents of R1 and R2

using R3 for temporary storage
– What are the individual register transfers required to effect the swap?
– Which control signals need to be asserted for each transfer?
– When & how should the control signals be sequenced?

In successive steps:
1. R3 <= R2 2. R2 <= R1 3. R1 <= R3 : R3in <= ‘1’; R2out <= ‘1’ : R2in <= ‘1’; R1out <= ‘1’ : R1in <= ‘1’; R3out <= ‘1’ 20T3 COMP3222/9222 Digital System Design L08/S6 A shift-register based control circuit • Swapping the contents of R1 and R2 using R3 for temporary storage – Could use one-hot control to enable 3-state buffers and loading of registers – Suffers delay of 1 cycle after input w asserted – Assumes w is deasserted for at least two clock cycles after the period during which it is asserted 20T3 COMP3222/9222 Digital System Design L08/S7 Code for an n-bit register with enable Rin LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY regne IS GENERIC ( N : INTEGER := 8 ) ; PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ; Rin, Clock : IN STD_LOGIC ; Q : OUT STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ; END regne ; ARCHITECTURE Behavior OF regne IS BEGIN PROCESS BEGIN WAIT UNTIL Clock'EVENT AND Clock = '1' ; IF Rin = '1' THEN Q <= R ; END IF ; END PROCESS ; END Behavior ; 20T3 COMP3222/9222 Digital System Design L08/S8 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY trin IS GENERIC ( N : INTEGER := 8 ) ; PORT ( X : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ; E : IN STD_LOGIC ; F : OUT STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ; END trin ; ARCHITECTURE Behavior OF trin IS BEGIN F <= (OTHERS => ‘Z’) WHEN E = ‘0’ ELSE X ;
END Behavior ;

Code for an n-bit 3-state buffer

20T3 COMP3222/9222 Digital System Design L08/S9

LIBRARY ieee ;
USE ieee.std_logic_1164.all ;

ENTITY shiftr IS — left-to-right shift register with async reset
GENERIC ( K : INTEGER := 4 ) ;
PORT ( Resetn, Clock, w : IN STD_LOGIC ;

Q : BUFFER STD_LOGIC_VECTOR(1 TO K) ) ;
END shiftr ;

ARCHITECTURE Behavior OF shiftr IS
BEGIN

PROCESS ( Resetn, Clock )
BEGIN

IF Resetn = ‘0’ THEN
Q <= (OTHERS => ‘0’) ;

ELSIF Clock’EVENT AND Clock = ‘1’ THEN
Genbits: FOR i IN K DOWNTO 2 LOOP

Q(i) <= Q(i-1) ; END LOOP ; Q(1) <= w ; END IF ; END PROCESS ; END Behavior ; Code for L-R shift register with reset 20T3 COMP3222/9222 Digital System Design L08/S10 LIBRARY ieee ; USE ieee.std_logic_1164.all ; PACKAGE components IS COMPONENT regne -- register GENERIC ( N : INTEGER := 8 ) ; PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ; Rin, Clock : IN STD_LOGIC ; Q : OUT STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ; END COMPONENT ; COMPONENT shiftr -- left-to-right shift register with async reset GENERIC ( K : INTEGER := 4 ) ; PORT ( Resetn, Clock, w : IN STD_LOGIC ; Q : BUFFER STD_LOGIC_VECTOR(1 TO K) ) ; END component ; COMPONENT trin -- 3-state buffers GENERIC ( N : INTEGER := 8 ) ; PORT ( X : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ; E : IN STD_LOGIC ; F : OUT STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ; END COMPONENT ; END components ; Package and component declarations 20T3 COMP3222/9222 Digital System Design L08/S11 The digital system from L08/S6 used to swap R1 and R2 via R3 LIBRARY ieee ; USE ieee.std_logic_1164.all ; USE work.components.all ; ENTITY swap IS PORT ( Data : IN STD_LOGIC_VECTOR(7 DOWNTO 0) ; Resetn, w : IN STD_LOGIC ; Clock, Extern : IN STD_LOGIC ; RinExt : IN STD_LOGIC_VECTOR(1 TO 3) ; -- allows regs to be externally loaded BusWires : BUFFER STD_LOGIC_VECTOR(7 DOWNTO 0) ) ; END swap ; ARCHITECTURE Structure OF swap IS SIGNAL Rin, Rout, Q : STD_LOGIC_VECTOR(1 TO 3) ; SIGNAL R1, R2, R3 : STD_LOGIC_VECTOR(7 DOWNTO 0) ; BEGIN control: shiftr GENERIC MAP ( K => 3 )

PORT MAP ( Resetn, Clock, w, Q ) ;
Rin(1) <= RinExt(1) OR Q(3) ; Rin(2) <= RinExt(2) OR Q(2) ; Rin(3) <= RinExt(3) OR Q(1) ; Rout(1) <= Q(2) ; Rout(2) <= Q(1) ; Rout(3) <= Q(3) ; tri_ext: trin PORT MAP ( Data, Extern, BusWires ) ; reg1: regn PORT MAP ( BusWires, Rin(1), Clock, R1 ) ; reg2: regn PORT MAP ( BusWires, Rin(2), Clock, R2 ) ; reg3: regn PORT MAP ( BusWires, Rin(3), Clock, R3 ) ; tri1: trin PORT MAP ( R1, Rout(1), BusWires ) ; tri2: trin PORT MAP ( R2, Rout(2), BusWires ) ; tri3: trin PORT MAP ( R3, Rout(3), BusWires ) ; END Structure ; Q(1) Q(2) Q(3) C on tr ol le r D at ap at h C on tr ol le r Datapath Timing simulation for the code of L08/S12 Stimuli (external signals) Response (internal signals) Code and waveform inputs to generate this waveform are available from the course website 20T3 COMP3222/9222 Digital System Design L08/S13 Using multiplexers to implement a bus • More typical to use MUXes instead of 3-state buffers since programmable devices (such as FPGAs) don’t usually have many 3-state resources • Both MUX and 3-state approaches are equally valid 20T3 COMP3222/9222 Digital System Design L08/S14 Using multiplexers for swap LIBRARY ieee ; USE ieee.std_logic_1164.all ; USE work.components.all ; ENTITY swapmux IS PORT (Data : IN STD_LOGIC_VECTOR(7 DOWNTO 0) ; Resetn, w : IN STD_LOGIC ; Clock : IN STD_LOGIC ; RinExt : IN STD_LOGIC_VECTOR(1 TO 3) ; BusWires : BUFFER STD_LOGIC_VECTOR(7 DOWNTO 0) ) ; END swapmux ; ARCHITECTURE Mixed OF swapmux IS SIGNAL Rin, Q : STD_LOGIC_VECTOR(1 TO 3) ; SIGNAL R1, R2, R3 : STD_LOGIC_VECTOR(7 DOWNTO 0) ; BEGIN control: shiftr GENERIC MAP ( K => 3 )

PORT MAP ( Resetn, Clock, w, Q ) ;
Rin(1) <= RinExt(1) OR Q(3) ; Rin(2) <= RinExt(2) OR Q(2) ; Rin(3) <= RinExt(3) OR Q(1) ; reg1: regn PORT MAP ( BusWires, Rin(1), Clock, R1 ) ; reg2: regn PORT MAP ( BusWires, Rin(2), Clock, R2 ) ; reg3: regn PORT MAP ( BusWires, Rin(3), Clock, R3 ) ; muxes: WITH Q SELECT BusWires <= Data WHEN "000", R2 WHEN ”100", R1 WHEN ”010", R3 WHEN OTHERS ; END Mixed ; 20T3 COMP3222/9222 Digital System Design L08/S15 Design Example 2 (pp 450-462): A simple processor Register file Datapath Control unit 20T3 COMP3222/9222 Digital System Design L08/S16 Operations performed by the processor L08/S17 Control signals asserted in each operation/ time step (during each “micro- instruction”) Control Signals Operation Function Time Step 1 Time Step 2 Time Step 3 I0: Load Rx, Data Rx ¬ Data Extern, Rin = X, Done I1: Move Rx, Ry Rx ¬ Ry Rin = X, Rout = Y, Done I2: Add Rx, Ry Rx ¬ Rx + Ry Rout = X, Ain Rout = Y, Gin, AddSub = 0 Gout, Rin = X, Done I3: Sub Rx, Ry Rx ¬ Rx – Ry Rout = X, Ain Rout = Y, Gin, AddSub = 1 Gout, Rin = X, Done Keeping track of the instruction step • In Example 1 we used a shift register to keep track of which cycle we were in • This time, let’s use a counter, and decode it to obtain the instruction step • T0Þ not currently executing an instruction • Clear the instruction counter when Reset or Done or when in T0 and w not asserted: Clear = wT0 + Done + Reset Reset Up-counter Clear w 0 En y 0 w 1 y 1 y 2 y 3 1 T 1 T 2 T 3 2-to-4 decoder Q 1 Q 0 Clock T0 20T3 COMP3222/9222 Digital System Design L08/S19 In order to simplify derivation of control signals, save the function and decode its fields Clock Function Register FRin f 1 f 0 Rx1 Rx0 Ry 1 Ry 0 Function X 0 w w 0 En y 0 w 1 y 1 y 2 y 3 1 X 1 X 2 X 3 2-to-4 decoder Y 0 w En y 0 w 1 y 1 y 2 y 3 1 Y 1 Y 2 Y 3 2-to-4 decoder I 0 En y 0 y 1 y 2 y 3 1 I 1 I 2 I 3 2-to-4 decoder w 0 w w 1 0 20T3 COMP3222/9222 L08/S20 Load Function Register when w is asserted in T0 : FRin = wT0 Derivation of control equations (1) a) Clear instruction counter when Reset or Done or when in T0 and w not asserted: Clear = wT0 + Done + Reset b) Load Function Register when w is asserted in T0: FRin = wT0 c) All other control signals are derived from the table on slide L08/S18 depending upon the instruction being executed and the current time step, e.g. Extern is only asserted in I0 (Load) during T1 i.e. Extern = I0T1 d) Done is asserted at the end of T1 for Load & Move and at the end of T3 for Add & Sub: Done = (I0 + I1)T1 + (I2 + I3)T3 Control Signals Operation Function Time Step 1 Time Step 2 Time Step 3 I0: Load Rx, Data Rx ¬ Data Extern, Rin = X, Done I1: Move Rx, Ry Rx ¬ Ry Rin = X, Rout = Y, Done I2: Add Rx, Ry Rx ¬ Rx + Ry Rout = X, Ain Rout = Y, Gin, AddSub = 0 Gout, Rin = X, Done I3: Sub Rx, Ry Rx ¬ Rx – Ry Rout = X, Ain Rout = Y, Gin, AddSub = 1 Gout, Rin = X, Done 20T3 COMP3222/9222 L08/S21 Derivation of control equations (2) e) Ain = Gin = Gout = AddSub = f) R0..R3 are determined from X0..X3 or Y0..Y3. In the table from L08/S18, Rin = X means the register corresponding to the asserted X value should be loaded. Thus we can derive: R0in = (I0 + I1)T1X0 + (I2 + I3)T3X0 and R0out = I1T1Y0 + (I2 + I3)(T1X0 + T2Y0) Similar expressions can be derived for R1in..R3in and R1out..R3out. Control Signals Operation Function Time Step 1 Time Step 2 Time Step 3 I0: Load Rx, Data Rx ¬ Data Extern, Rin = X, Done I1: Move Rx, Ry Rx ¬ Ry Rin = X, Rout = Y, Done I2: Add Rx, Ry Rx ¬ Rx + Ry Rout = X, Ain Rout = Y, Gin, AddSub = 0 Gout, Rin = X, Done I3: Sub Rx, Ry Rx ¬ Rx – Ry Rout = X, Ain Rout = Y, Gin, AddSub = 1 Gout, Rin = X, Done (I2 + I3)T1 (I2 + I3)T2 (I2 + I3)T3 I3 20T3 COMP3222/9222 Digital System Design L08/S22 LIBRARY ieee ; USE ieee.std_logic_1164.all ; USE ieee.std_logic_unsigned.all ; ENTITY upcount IS PORT ( Clear, Clock : IN STD_LOGIC ; Q : BUFFER STD_LOGIC_VECTOR(1 DOWNTO 0) ) ; END upcount ; ARCHITECTURE Behavior OF upcount IS BEGIN upcount: PROCESS ( Clock ) BEGIN IF (Clock'EVENT AND Clock = '1') THEN IF Clear = '1' THEN Q <= "00" ; ELSE Q <= Q + '1' ; END IF ; END IF; END PROCESS; END Behavior ; Code for a two-bit up-counter with synchronous reset 20T3 COMP3222/9222 Digital System Design L08/S23 Code for the processor (Part a) • This code is for a 3-state, bus-based processor LIBRARY ieee ; USE ieee.std_logic_1164.all ; USE ieee.std_logic_signed.all ; USE work.subccts.all ; ENTITY proc IS PORT ( Data: IN STD_LOGIC_VECTOR(7 DOWNTO 0) ; Reset, w : IN STD_LOGIC ; Clock: IN STD_LOGIC ; F, Rx, Ry: IN STD_LOGIC_VECTOR(1 DOWNTO 0) ; Done: BUFFER STD_LOGIC ; BusWires: BUFFER STD_LOGIC_VECTOR(7 DOWNTO 0)); END proc ; ARCHITECTURE Mixed OF proc IS SIGNAL Rin, Rout : STD_LOGIC_VECTOR(0 TO 3) ; SIGNAL Clear, High, AddSub : STD_LOGIC ; SIGNAL Extern, Ain, Gin, Gout, FRin : STD_LOGIC ; SIGNAL Count : STD_LOGIC_VECTOR(1 DOWNTO 0) ; SIGNAL T, I, X, Y : STD_LOGIC_VECTOR(0 TO 3) ; SIGNAL R0, R1, R2, R3 : STD_LOGIC_VECTOR(7 DOWNTO 0) ; SIGNAL A, Sum, G : STD_LOGIC_VECTOR(7 DOWNTO 0) ; SIGNAL Func, FuncReg : STD_LOGIC_VECTOR(1 TO 6) ; BEGIN High <= '1' ; Clear <= Reset OR Done OR (NOT w AND T(0)) ; counter: upcount PORT MAP ( Clear, Clock, Count ) ; decT: dec2to4 PORT MAP ( Count, High, T ); Func <= F & Rx & Ry ; FRin <= w AND T(0) ; functionreg: regn GENERIC MAP ( N => 6 )

PORT MAP ( Func, FRin, Clock, FuncReg ) ;
decI: dec2to4 PORT MAP ( FuncReg(1 TO 2), High, I ) ;
decX: dec2to4 PORT MAP ( FuncReg(3 TO 4), High, X ) ;
decY: dec2to4 PORT MAP ( FuncReg(5 TO 6), High, Y ) ;

Extern <= I(0) AND T(1) ; Done <= ((I(0) OR I(1)) AND T(1)) OR ((I(2) OR I(3)) AND T(3)); Ain <= (I(2) OR I(3)) AND T(1) ; Gin <= (I(2) OR I(3)) AND T(2) ; Gout <= (I(2) OR I(3)) AND T(3) ; AddSub <= I(3) ; … continued in Part b. Controller (continued on next page) 20T3 COMP3222/9222 Digital System Design L08/S24 RegCntl: FOR k IN 0 TO 3 GENERATE Rin(k) <= ((I(0) OR I(1)) AND T(1) AND X(k)) OR ((I(2) OR I(3)) AND T(3) AND X(k)) ; Rout(k) <= (I(1) AND T(1) AND Y(k)) OR ((I(2) OR I(3)) AND ((T(1) AND X(k)) OR (T(2) AND Y(k)))) ; END GENERATE RegCntl ; tri_extern: trin PORT MAP ( Data, Extern, BusWires ) ; reg0: regn PORT MAP ( BusWires, Rin(0), Clock, R0 ) ; reg1: regn PORT MAP ( BusWires, Rin(1), Clock, R1 ) ; reg2: regn PORT MAP ( BusWires, Rin(2), Clock, R2 ) ; reg3: regn PORT MAP ( BusWires, Rin(3), Clock, R3 ) ; tri0: trin PORT MAP ( R0, Rout(0), BusWires ) ; tri1: trin PORT MAP ( R1, Rout(1), BusWires ) ; tri2: trin PORT MAP ( R2, Rout(2), BusWires ) ; tri3: trin PORT MAP ( R3, Rout(3), BusWires ) ; regA: regn PORT MAP ( BusWires, Ain, Clock, A ) ; alu: WITH AddSub SELECT Sum <= A + BusWires WHEN '0', A - BusWires WHEN OTHERS ; regG: regn PORT MAP ( Sum, Gin, Clock, G ) ; triG: trin PORT MAP ( G, Gout, BusWires ) ; END Mixed ; Datapath Controller Code for the processor (Part b) 20T3 COMP3222/9222 Digital System Design L08/S25 Alternative code for a MUX-based processor (Part a) • Uses the same entity description as before • Note that the table from slide L08/S18 is implemented directly controlsignals: PROCESS ( T, I, X, Y ) BEGIN Extern <= '0' ; Done <= '0' ; Ain <= '0' ; Gin <= '0' ; Gout <= '0' ; AddSub <= '0' ; Rin <= "0000" ; Rout <= "0000" ; CASE T IS WHEN "00" => — no signals asserted in time step T0
WHEN “01” => — define signals asserted in time step T1

CASE I IS
WHEN “00” => — Load

Extern <= '1' ; Rin <= X ; Done <= '1' ; WHEN "01" => — Move

Rout <= Y ; Rin <= X ; Done <= '1' ; WHEN OTHERS => — Add, Sub

Rout <= X ; Ain <= '1' ; END CASE ; … continued in Part b ARCHITECTURE Mixed OF proc IS SIGNAL X, Y, Rin, Rout : STD_LOGIC_VECTOR(0 TO 3) ; SIGNAL Clear, High, AddSub : STD_LOGIC ; SIGNAL Extern, Ain, Gin, Gout, FRin : STD_LOGIC ; SIGNAL Count, T, I : STD_LOGIC_VECTOR(1 DOWNTO 0) ; SIGNAL R0, R1, R2, R3 : STD_LOGIC_VECTOR(7 DOWNTO 0); SIGNAL A, Sum, G : STD_LOGIC_VECTOR(7 DOWNTO 0) ; SIGNAL Func, FuncReg, Sel : STD_LOGIC_VECTOR(1 TO 6); BEGIN High <= '1' ; Clear <= Reset OR Done OR (NOT w AND NOT T(1) AND NOT T(0)) ; counter: upcount PORT MAP ( Clear, Clock, Count ) ; T <= Count ; Func <= F & Rx & Ry ; FRin <= w AND NOT T(1) AND NOT T(0) ; functionreg: regn GENERIC MAP ( N => 6 )

PORT MAP ( Func, FRin, Clock, FuncReg );
I <= FuncReg(1 TO 2) ; decX: dec2to4 PORT MAP ( FuncReg(3 TO 4), High, X ) ; decY: dec2to4 PORT MAP ( FuncReg(5 TO 6), High, Y ) ; Controller T, I not decoded to simplify CASE selection in controlsignals PROCESS ALL outputs cleared by default at start of PROCESS to avoid risk of implying memory 20T3 COMP3222/9222 Digital System Design L08/S26 Alternative code for a MUX-based processor (Part b) • Both versions have equivalent functionality • However, the behavioural style used to capture the control signalling in the second version is less prone to error in deriving and coding the control equations WHEN "10" => — define signals asserted in time step T2
CASE I IS

WHEN “10” => — Add
Rout <= Y ; Gin <= '1' ; WHEN "11" => — Sub
Rout <= Y ; AddSub <= '1' ; Gin <= '1' ; WHEN OTHERS => — Load, Move
END CASE ;

WHEN OTHERS => — define signals asserted in time step T3
CASE I IS

WHEN “00” => — Load
WHEN “01” => — Move
WHEN OTHERS => — Add, Sub

Gout <= '1' ; Rin <= X ; Done <= '1' ; END CASE ; END CASE ; END PROCESS ; reg0: regn PORT MAP ( BusWires, Rin(0), Clock, R0 ) ; reg1: regn PORT MAP ( BusWires, Rin(1), Clock, R1 ) ; reg2: regn PORT MAP ( BusWires, Rin(2), Clock, R2 ) ; reg3: regn PORT MAP ( BusWires, Rin(3), Clock, R3 ) ; regA: regn PORT MAP ( BusWires, Ain, Clock, A ) ; alu: WITH AddSub SELECT Sum <= A + BusWires WHEN '0', A - BusWires WHEN OTHERS ; regG: regn PORT MAP ( Sum, Gin, Clock, G ) ; Sel <= Rout & Gout & Extern ; WITH Sel SELECT BusWires <= R0 WHEN "100000", R1 WHEN "010000", R2 WHEN "001000", R3 WHEN "000100", G WHEN "000010", Data WHEN OTHERS ; END Mixed ; DatapathController 20T3 COMP3222/9222 Digital System Design L08/S27 Functional simulation of the MUX-based processor load R0, #2A Response (internal signals) Stimuli (external signals) • Code and waveform inputs to generate this waveform are available from the course website 20T3 COMP3222/9222 Digital System Design L08/S28 load R1, #55 Response (internal signals) Stimuli (external signals) Functional simulation of the MUX-based processor • Code and waveform inputs to generate this waveform are available from the course website 20T3 COMP3222/9222 Digital System Design L08/S29 load R2, #22 Response (internal signals) Stimuli (external signals) Functional simulation of the MUX-based processor • Code and waveform inputs to generate this waveform are available from the course website 20T3 COMP3222/9222 Digital System Design L08/S30 add R1, R0 Response (internal signals) Stimuli (external signals) Functional simulation of the MUX-based processor • Code and waveform inputs to generate this waveform are available from the course website 20T3 COMP3222/9222 Digital System Design L08/S31 mov R3, R1 Response (internal signals) Stimuli (external signals) Functional simulation of the MUX-based processor • Code and waveform inputs to generate this waveform are available from the course website 20T3 COMP3222/9222 Digital System Design L08/S32 sub R3, R2 Response (internal signals) Stimuli (external signals) Functional simulation of the MUX-based processor • Code and waveform inputs to generate this waveform are available from the course website 20T3 COMP3222/9222 Digital System Design L08/S33 Mapping the processor to our board library ieee; use ieee.std_logic_1164.all; use work.subccts.all; use work.proc_pkg.all; entity mapproc is port (sw: in std_logic_vector(9 downto 0); key: in std_logic_vector(2 downto 0); ledr: out std_logic_vector(9 downto 0); --DE1 hex0: out std_logic_vector(0 to 6); hex1: out std_logic_vector(0 to 6); hex2: out std_logic_vector(0 to 6); hex3: out std_logic_vector(0 to 6)); end mapproc; architecture structural of mapproc is signal done, reset, w, clock: std_logic; signal buswires: std_logic_vector(3 downto 0); signal r0,r1,r2,r3: std_logic_vector(3 downto 0); begin clock <= not key(0); reset <= not key(1); w <= not key(2); ledr(9) <= done; --DE1 ledr(3 downto 0) <= buswires; --DE1 proc0: proc generic map (L => 4)
port map(Data => sw(3 downto 0),

Reset => reset, w => w,
Clock => clock,
F => sw(9 downto 8),
RX => sw(7 downto 6),
RY => sw(5 downto 4),
Done => done, BusWires => buswires,
R0 => r0, R1 => r1, R2 => r2,
R3 => r3);

dig0: seg7 PORT map ( r0, hex0);
dig1: seg7 PORT map ( r1, hex1);
dig2: seg7 PORT map ( r2, hex2);
dig3: seg7 PORT map ( r3, hex3);

end structural;
20T3 COMP3222/9222 Digital System Design L08/S34

Change DE1 lines to “ledg” for DE0

Simulating the mapping

20T3 COMP3222/9222 Digital System Design L08/S35

Algorithmic state machines
• Algorithmic state machines (ASMs) are a type of flowchart

– They are used to represent more complex (larger) FSMs that are
impractical to represent using state diagrams and state tables

– They can be used to represent the state transitions and generated
outputs for an FSM

– They can be used to capture datapath activity
• There are three types of elements in ASM charts

20T3 COMP3222/9222 Digital System Design L08/S36

Output signals
or actions

(Moore type)

State name:

Conditional
expression

0 (False) 1 (True)

Conditional outputs
or actions (Mealy type)

(a) Named state box (b) Decision box

Elements used in ASM charts

B&V3, Figure 8.86

20T3 COMP3222/9222 Digital System Design L08/S37

ASM chart for the FSM of L06/S10

B&V3, Figure 8.87

w
0 1

Reset

C z 1 = ⁄

Reset

B z 0 = ⁄ A z 0 = ⁄ w 0 =

w 1 =

w 0 =

w 0 = w 1 =

20T3 COMP3222/9222 Digital System Design L08/S38

w
0 1

Reset

ASM chart for the FSM of L06/S23

B&V3, Figure 8.88

w 0 = z 0 = ⁄

w 1 = z 1 = ⁄ B w 0 = z 0 = ⁄

Reset
w 1 = z 0 = ⁄

1
w

Reset

20T3 COMP3222/9222 Digital System Design L08/S39

Design Exercise 1:
pp 679 – 683, B&V3
• Devise a circuit that will count the number of ON bits in a data

word

20T3 COMP3222/9222 Digital System Design L08/S40

Pseudo-code for a bit counter (popcount)

B&V3, Figure 10.9

B = 0
while A ≠ 0 do

if a0 = 1 then
B = B + 1

end if
right shift A

end while

input: A — the word whose ON bits are to be counted
output: B — the count of the number of ON bits in A

1. What datapath components do we need to
perform the computation?

2. How do we control the computation?

3. How do we transfer inputs/outputs?

20T3 COMP3222/9222 Digital System Design L08/S41

Done

B B 1 + ¬

B 0 ¬

Load A

a 0

Reset

0
1

A 0 = ?

Shift right A

ASM chart for the pseudo-code

B&V3, Figure 10.10

Note use of a “start” signal, s, to
indicate when input is available,
and a Done signal to indicate
when computation has finished
Þ handshake protocol used to

communicate with the environment
or “user” circuit

Take careful note of the state
actions – particularly for S2
Þ since the “Shift right” action is a

Moore-like state output, it won’t
occur until the first active clock
edge after S2 has been entered,
even if that edge causes transition
to S3

B = 0
while A ≠ 0 do

if a0 = 1 then
B = B + 1

end if
right shift A

end while

Note that the ASM chart describes
control and datapath aspects of
the system in an integrated way

20T3 COMP3222/9222 Digital System Design L08/S42

Datapath for the ASM chart

B&V3, Figure 10.11

L
E Counter

w
L
E

Shift right
LB
EBLA

Clock

B z a
0

Data

log2n

20T3 COMP3222/9222 Digital System Design L08/S43

In COMP3222/9222:

Label every wire = name every signal
and specify the bitwidth of each multibit signal

ASM chart for the bit counter control circuit

B&V3, Figure 10.12

The ASM chart for the pseudocode
is refined according to the FSM reqs

L
E Counter

w
L
E

Shift
LB
EBLA

Clock

B z a
0

Data

log2n

Note: In this case it is assumed that
the circuit “user” loads A by asserting
LA before asserting the start signal s,
and that the user does not deassert s
until after the count value has been
read

EB z

a
0

Reset

1
s

Done

Reset

s s

S2 S3

EA Done

EB z

20T3 COMP3222/9222 Digital System Design L08/S44

VHDL code for the bit-counting circuit (Part a)

B&V3, Figure 10.13

LIBRARY ieee ;
USE ieee.std_logic_1164.all ;
USE ieee.std_logic_unsigned.all ;
USE work.components.shiftrne ;

ENTITY bitcount IS
PORT( Clock, Resetn : IN STD_LOGIC ;

LA, s : IN STD_LOGIC ;
Data : IN

STD_LOGIC_VECTOR(7 DOWNTO 0) ;
B : BUFFER

INTEGER RANGE 0 to 8 ;
Done : OUT STD_LOGIC ) ;

END bitcount ;

ARCHITECTURE Behavior OF bitcount IS
TYPE State_type IS ( S1, S2, S3 ) ;
SIGNAL y : State_type ;
SIGNAL A : STD_LOGIC_VECTOR(7 DOWNTO 0) ;
SIGNAL z, EA, LB, EB, low : STD_LOGIC ;

BEGIN
FSM_transitions: PROCESS ( Resetn, Clock )
BEGIN

IF Resetn = ‘0’ THEN
y <= S1 ; ELSIF (Clock'EVENT AND Clock = '1') THEN CASE y IS WHEN S1 =>
IF s = ‘0’ THEN y <= S1 ; ELSE y <= S2 ; END IF ; WHEN S2 =>
IF z = ‘0’ THEN y <= S2 ; ELSE y <= S3 ; END IF ; WHEN S3 =>
IF s = ‘1’ THEN y <= S3 ; ELSE y <= S1 ; END IF ; END CASE ; END IF ; END PROCESS ; … continued in Part b L E Counter w L E Shift LB EBLA EA 0 Clock 0 B z a 0 Data n A n log2n log2n EA EB z LB s a 0 Reset S3 0 1 0 1 0 1 s S2 S1 0 1 Done S1 LB s s 1 0 0 1 S2 S3 EA Done EB z a0 1 1 0 0 Reset ; 20T3 COMP3222/9222 Digital System Design L08/S45 VHDL code for the bit-counting circuit (Part b) B&V3, Figure 10.13 FSM_outputs: PROCESS ( y, A(0) ) BEGIN EA <= '0' ; LB <= '0' ; EB <= '0' ; Done <= '0' ; CASE y IS WHEN S1 =>
LB <= '1' WHEN S2 =>
EA <= '1' ; IF A(0) = '1' THEN EB <= '1' ; END IF ; WHEN S3 =>
Done <= '1' ; END CASE ; END PROCESS ; -- The datapath circuit is described below upcount: PROCESS ( Resetn, Clock ) BEGIN IF Resetn = '0' THEN B <= 0 ; ELSIF (Clock'EVENT AND Clock = '1') THEN IF LB = '1' THEN B <= 0 ; ELSIF EB = '1' THEN B <= B + 1 ; END IF ; END IF; END PROCESS; low <= '0' ; ShiftA: shiftrne GENERIC MAP ( N => 8 )

PORT MAP ( Data, LA, EA, low, Clock, A ) ;
z <= '1' WHEN A = "00000000" ELSE '0' ; END Behavior ; L E Counter w L E Shift LB EBLA EA 0 Clock 0 B z a 0 Data n A n log2n log2n EA EB z LB s a 0 Reset S3 0 1 0 1 0 1 s S2 S1 0 1 Done S1 LB s s 1 0 0 1 S2 S3 EA Done EB z a0 1 1 0 0 Reset 20T3 COMP3222/9222 Digital System Design L08/S46 Simulation results for the bit-counting circuit B&V3, Figure 10.14 20T3 COMP3222/9222 Digital System Design L08/S47 (a) Single-pole single-throw switch Data V DD R Data S R V DD R V DD R (b) Single-pole double-throw switch with a basic SR latch Practical Issue: Input switch debouncing B&V3, Figure 10.48 When an input switch is thrown, it can bounce for up to 10ms and thus give rise to an undesirable sequence of pulses on Data when wired as depicted ⇒ One approach to avoiding misreads is to use a latch to trap the switch value. ⇒ Another is to wait the 10ms bounce period before sampling Data. 20T3 COMP3222/9222 Digital System Design L08/S48 Debounce code 1 synchronise: process (clk) 2 begin 3 wait until clk'event and clk = '1’; -- rising clock edge 4 input_prev <= input_switch; -- save the current switch setting -- The following counter counts time that the inputs have been steady -- The input signal must be steady for approx. 10 milliseconds 5 if input_switch /= input_prev then -- if the switch has bounced 6 sync_count <= (others => ‘0’); — reset a counter
7 elsif sync_count /= x”80000″ then — otherwise, count ~10ms worth of clock
8 sync_count <= sync_count + 1; -- pulses at 50MHz (assumed clock freq.) 9 end if; -- If the full time is reached, update the input signals 10 if sync_count = x”80000" then 11 input_value <= input_switch; -- switch has stopped bouncing 12 end if; 13 end process synchronise; 20T3 COMP3222/9222 Digital System Design L08/S49 D Q Q Clock Asynchronous data e.g. external real-world event D Q Q Synchronous data Practical Issue: Asynchronous inputs B&V3, Figure 10.47 When an asynchronous input fails to satisfy setup or hold times, the flip-flop can enter a metastable state (intermediate/indeterminate value) and not recover for an indefinite period of time. Using a pair of flip-flops in series significantly reduces the likelihood that any synchronous system reading Data will observe such a metastable value • COTS (Commercial, Off-The-Shelf) devices typically specify a maximum period of metastability • as long as the clock period in the circuit above exceeds this value, the FF on the right will not also enter a metastable state when the FF on the left does • cost is one clock period of delay or latency in the arrival of the data input 20T3 COMP3222/9222 Digital System Design L08/S50 D Q Q Data Clock E Practical Issue: Clock enable circuit B&V3, Figure 10.43 While seemingly attractive, clock gating to enable a flip-flop is to be avoided as it contributes to clock skew. 20T3 COMP3222/9222 Digital System Design L08/S51 Better solution: A flip-flop with an enable input It is often desirable to control when a flip-flop or register is loaded with a new value D Q Q Q R Clock E 0 1 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY rege IS PORT ( R, Resetn, E, Clock : IN STD_LOGIC ; Q : BUFFER STD_LOGIC ) ; END rege ; ARCHITECTURE Behavior OF rege IS BEGIN PROCESS ( Resetn, Clock ) BEGIN IF Resetn = '0' THEN Q <= '0' ; ELSIF Clock'EVENT AND Clock = '1' THEN IF E = '1' THEN Q <= R ; ELSE Q <= Q ; END IF ; END IF ; END PROCESS ; END Behavior ; B&V3, Figure 10.1 20T3 COMP3222/9222 Digital System Design L08/S52 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY regne IS GENERIC ( N : INTEGER := 4 ) ; PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ; Resetn : IN STD_LOGIC ; E, Clock : IN STD_LOGIC ; Q : OUT STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ; END regne ; ARCHITECTURE Behavior OF regne IS BEGIN PROCESS ( Resetn, Clock ) BEGIN IF Resetn = '0' THEN Q <= (OTHERS => ‘0’) ;

ELSIF Clock’EVENT AND Clock = ‘1’ THEN
IF E = ‘1’ THEN

Q <= R ; END IF ; END IF ; END PROCESS ; END Behavior ; VHDL code for a n-bit register with an enable input B&V3, Figure 10.2 20T3 COMP3222/9222 Digital System Design L08/S53 A shift register with parallel-load and enable control inputs B&V3, Figure 10.3 20T3 COMP3222/9222 Digital System Design L08/S54 Code for a right-to-left shift register with an enable input B&V3, Figure 10.4 LIBRARY ieee ; USE ieee.std_logic_1164.all ; -- right-to-left shift register with parallel load and enable ENTITY shiftlne IS GENERIC ( N : INTEGER := 4 ) ; PORT( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ; L, E, w : IN STD_LOGIC ; Clock : IN STD_LOGIC ; Q : BUFFER STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ; END shiftlne ; ARCHITECTURE Behavior OF shiftlne IS BEGIN PROCESS BEGIN WAIT UNTIL Clock'EVENT AND Clock = '1' ; IF L = '1' THEN Q <= R ; ELSIF E = ‘1’ THEN Q(0) <= w ; Genbits: FOR i IN 1 TO N-1 LOOP Q(i) <= Q(i-1) ; END LOOP ; END IF ; END PROCESS ; END Behavior ; 20T3 COMP3222/9222 Digital System Design L08/S55 Component declaration statements assumed for remaining design problems (Part a) B&V3, Figure 10.5 LIBRARY ieee ; USE ieee.std_logic_1164.all ; PACKAGE components IS -- 2-to-1 multiplexer COMPONENT mux2to1 PORT ( w0, w1 : IN STD_LOGIC ; s : IN STD_LOGIC ; f : OUT STD_LOGIC ) ; END COMPONENT ; -- D flip-flop with 2-to-1 multiplexer connected to D COMPONENT muxdff PORT ( D0, D1, Sel, Clock : IN STD_LOGIC ; Q : OUT STD_LOGIC ) ; END COMPONENT ; -- n-bit register with enable COMPONENT regne GENERIC ( N : INTEGER := 4 ) ; PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ; Resetn : IN STD_LOGIC ; E, Clock : IN STD_LOGIC ; Q : OUT STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ; END COMPONENT ; -- n-bit right-to-left shift register with parallel load and enable COMPONENT shiftlne -- shift left (towards msb)–mult by 2 GENERIC ( N : INTEGER := 4 ) ; PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ; L, E, w : IN STD_LOGIC ; Clock : IN STD_LOGIC ; Q : BUFFER STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ; END COMPONENT ; … continued in Part b 20T3 COMP3222/9222 Digital System Design L08/S56 Component declaration statements for digital systems building blocks (Part b) B&V3, Figure 10.5 -- n-bit left-to-right shift register with parallel load and enable COMPONENT shiftrne -- shift right (towards lsb)–div by 2 GENERIC ( N : INTEGER := 4 ) ; PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ; L, E, w : IN STD_LOGIC ; Clock : IN STD_LOGIC ; Q : BUFFER STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ; END COMPONENT ; -- up-counter that counts up from initial value R to modulus-1 COMPONENT upcount GENERIC ( modulus : INTEGER := 8 ) ; PORT ( Resetn : IN STD_LOGIC ; Clock, E, L : IN STD_LOGIC ; R : IN INTEGER RANGE 0 TO modulus-1 ; Q : BUFFER INTEGER RANGE 0 TO modulus-1 ) ; END COMPONENT ; -- down-counter that counts from modulus-1 down to 0 COMPONENT downcnt GENERIC ( modulus : INTEGER := 8 ) ; PORT ( Clock, E, L : IN STD_LOGIC ; Q : BUFFER INTEGER RANGE 0 TO modulus-1 ) ; END COMPONENT ; END components ; 20T3 COMP3222/9222 Digital System Design L08/S57 • Implement a binary multiplier circuit (a) Manual method Multiplicand, A1 1 Product, P Multiplier, B1 0 0 1 1 1 1011 0000 1011 01 Binary 13 11 13 13 143 Decimal Design Exercise 2: pp 683 – 692, B&V3 B&V3, Figure 10.15 1011 0 0 1 1 1 1 (b) Pseudo-code P = 0 for i = 0 to n-1 do if bi = 1 then P = P + A end if left shift A end for 1. How is the computation performed? 2. What datapath components are required? 3. How are they to be controlled? How is their timing to be controlled? 20T3 COMP3222/9222 Digital System Design L08/S58 Shift left A , Shift right B Done P P A + ¬ B 0 = ? P 0 ¬ s Load A b 0 Reset S3 0 1 0 1 0 1 s S1 S2 1 0 Load B ASM chart for the multiplier B&V3, Figure 10.16 A: multiplicand B: multiplier P: product P = 0 for i = 0 to n-1 do if bi = 1 then P = P + A end if left shift A end for 20T3 COMP3222/9222 Digital System Design L08/S59 Datapath circuit for the multiplier B&V3, Figure 10.17 E L E L E 0 DataA LA EA A Clock P DataP Register EP Sum 0 z B b 0 DataB LB EB + 2n n n Shift-left register Shift-right register n n 2n 2n Psel 1 0 2n 2n Shift left A , Shift right B Done P P A + ¬ B 0 = ? P 0 ¬ s Load A b 0 Reset S3 0 1 0 1 0 1 s S1 S2 1 0 Load B How should the ASM chart be refined? 20T3 COMP3222/9222 Digital System Design L08/S60 For complete documentation, and to simplify coding, take care to label every wire (name every signal) and to specify its bitwidth when ≠ 1 ASM chart for the multiplier control circuit B&V3, Figure 10.18 E L E L E 0 DataA LA EA A Clk P DataP Register EP Sum 0 z B b 0 DataB LB EB + 2n n n Shift-left register Shift-right register n n 2n 2n Psel 1 0 2n 2n EP z b 0 Reset S3 0 1 0 1 s 0 1 Done Psel 0 = EP, s 0 1 S1 S2 Psel 1 = EA EB, , Reset S1 Psel = 0, EP s s 1 0 0 1 S2 S3 Psel = 1, EA, EB Done EP b0 1 1 0 0 z 20T3 COMP3222/9222 Digital System Design L08/S61 Shift left A , Shift right B Done P P A + ¬ B 0 = ? P 0 ¬ s Load A b 0 Reset S3 0 1 0 1 0 1 s S1 S2 1 0 Load B VHDL code for the multiplier circuit (Part a) B&V3, Figure 10.19 LIBRARY ieee ; USE ieee.std_logic_1164.all ; USE ieee.std_logic_unsigned.all ; USE work.components.all ; ENTITY multiply IS GENERIC ( N : INTEGER := 8; NN : INTEGER := 16 ) ; PORT ( Clock : IN STD_LOGIC ; Resetn : IN STD_LOGIC ; LA, LB, s : IN STD_LOGIC ; DataA : IN STD_LOGIC_VECTOR(N–1 DOWNTO 0) ; DataB : IN STD_LOGIC_VECTOR(N–1 DOWNTO 0) ; P : BUFFER STD_LOGIC_VECTOR(NN–1 DOWNTO 0) ; Done : OUT STD_LOGIC ) ; END multiply ; ARCHITECTURE Behavior OF multiply IS TYPE State_type IS ( S1, S2, S3 ) ; SIGNAL y : State_type ; SIGNAL Psel, z, EA, EB, EP, Zero : STD_LOGIC ; SIGNAL B, N_Zeros : STD_LOGIC_VECTOR(N–1 DOWNTO 0) ; SIGNAL A, Ain, DataP, Sum : STD_LOGIC_VECTOR(NN–1 DOWNTO 0) ; BEGIN FSM_transitions: PROCESS ( Resetn, Clock ) BEGIN IF Resetn = '0’ THEN y <= S1 ; ELSIF (Clock'EVENT AND Clock = '1') THEN CASE y IS WHEN S1 =>
IF s = ‘0’ THEN y <= S1 ; ELSE y <= S2 ; END IF; WHEN S2 =>
IF z = ‘0’ THEN y <= S2 ; ELSE y <= S3 ; END IF; WHEN S3 =>
IF s = ‘1’ THEN y <= S3 ; ELSE y <= S1 ; END IF; END CASE ; END IF ; END PROCESS ; … continued in Part b EP z b 0 Reset S3 0 1 0 1 s 0 1 Done Psel 0 = EP, s 0 1 S1 S2 Psel 1 = EA EB, , Reset S1 Psel = 0, EP s s 1 0 0 1 S2 S3 Psel = 1, EA, EB Done EP b0 1 1 0 0 z 20T3 COMP3222/9222 Digital System Design VHDL code for the multiplier circuit (Part b) B&V3, Figure 10.19 FSM_outputs: PROCESS ( y, B(0) ) BEGIN EP <= '0' ; EA <= '0' ; EB <= '0' ; Done <= '0' ; Psel <= '0'; CASE y IS WHEN S1 =>
EP <= '1‘ ; WHEN S2 =>
EA <= '1' ; EB <= '1' ; Psel <= '1‘ ; IF B(0) = '1' THEN EP <= '1' ; END IF ; WHEN S3 =>
Done <= '1‘ ; END CASE ; END PROCESS ; -- Define the datapath circuit Zero <= '0' ; N_Zeros <= (OTHERS => ‘0’ ) ;
Ain <= N_Zeros & DataA ; ShiftA: shiftlne GENERIC MAP ( N => NN )

PORT MAP ( Ain, LA, EA, Zero, Clock, A ) ;
ShiftB: shiftrne GENERIC MAP ( N => N )

PORT MAP ( DataB, LB, EB, Zero, Clock, B ) ;
z <= '1' WHEN B = N_Zeros ELSE '0' ; Sum <= A + P ; -- Define the 2n 2-to-1 multiplexers for DataP GenMUX: FOR i IN 0 TO NN–1 GENERATE Muxi: mux2to1 PORT MAP ( Zero, Sum(i), Psel, DataP(i) ) ; END GENERATE; RegP: regne GENERIC MAP ( N => NN )

PORT MAP ( DataP, Resetn, EP, Clock, P ) ;
END Behavior ;

L
E

0 DataA LA

A
Clock

DataP

Sum
0

b 0

DataB LB

n n

Shift-left
register

Shift-right
register

2n 2n

Psel 1 0

EP z

b
0

Reset

1
s

Done

Psel 0 = EP,

Psel 1 = EA EB, ,

Reset

Psel = 0, EP

0
1

S2 S3

Psel = 1, EA, EB Done

20T3 COMP3222/9222 Digital System Design

Simulation results for the multiplier circuit

B&V3, Figure 10.20

1 2 3 4 5 60

20T3 COMP3222/9222 Digital System Design L08/S64

9 140
9
50
45
5

(a) An example using decimal numbers

R = 0 ;
for i = 0 to n 1 do

Left-shift R ||A ;
if R ³ B then

qn-1-i = 1 ;
R = R B ;

else
q n-1-i = 0 ;

end if;
end for;

–

Design Exercise 3: Division
pp 692 – 702, B&V3

B&V3, Figure 10.21

1. How is the computation performed?
2. What datapath components are required?
3. How are they to be controlled?

100

10
10

011001001
00001111

1001
001

01
10000

1001
1110
1001
101

Q: Quotient
A: DividendB: Divisor

R: Remainder

(b) Using binary numbers

20T3 COMP3222/9222 Digital System Design L08/S65

ASM chart for the divider

B&V3, Figure 10.22

R B ³ ?

R 0 ¬ C n 1 –¬ ,

s
0 1

Load A
Load B

Shift left R||A

C C 1 -¬

Shift 0 into Q Shift 1 into Q
R R B –¬

C 0 = ?

1 0

Reset

Done

0
1

R = 0 ;
for i = 0 to n 1 do

Left-shift R ||A ;
if R ³ B then

qn-1-i = 1 ;
R = R B ;

else
q n-1-i = 0 ;

end if;
end for;

–

Answering the question:
How is the computation performed?

And confirming the type of
datapath components required

Note the need
for a counter

How will we know
that R >= B?

A: Dividend
B: Divisor
Q: Quotient
R: Remainder

Why count down
to 0 not up to n-1?

What is the value
of count in S4?

Why decrement count
after shift not before?

20T3 COMP3222/9222 Digital System Design L08/S66

Datapath circuit for the divider

B&V3, Figure 10.23
Is this everything?
How are the datapath
components controlled?

E
L
E

L
E

DataB

LR
ER

Clock

EB
0

DataALA

+
E cout cin 1

Rsel
n

Left-shift
register

n n

Left-shift
register

an 1- A

01
DataR n

Sum

20T3 COMP3222/9222 L08/S67

ASM chart for the divider
control circuit

B&V3, Figure 10.24

Rsel 0 = LR LC, ,

0 1

Done

EQ Rsel 1 = EC, ,

1 0

Reset

ER EA,

c
out

0 1 0

R B ³ ?

R 0 ¬ C n 1 –¬ ,

s
0 1

Load A
Load B

Shift left R||A

C C 1 -¬

Shift 0 into Q Shift 1 into Q
R R B –¬

C 0 = ?

1 0

Reset

Done

0
1 s

ELE
L
E

DataB

LR
ER

Clock
Q

EB
0

DataALA

+
E cout cin 1

Rsel
n

Left-shift
register

n n

Left-shift
register

an 1- A

01
DataR n

Sum

Reset

Rsel = 0, LR, LC

s
0 1

ER, EA

EQ, Rsel = 1, EC

0
s

1 0
cout

LR Done

1 0
z

Digital System Design L08/S68

An example of division using n = 8 clk cycles
One drawback of the divider we’ve designed is that it takes two cycles per iteration to
(i) shift R||A, and (ii) update R←R – B when required.
• A possible enhancement is to perform a shift and a subtraction in a single clock

cycle. [write the results of the subtraction to rn-1..r0||write the new an-1 to a flip-flop, rr0]
• A second enhancement is to reuse the redundant bits of the shift register for A to store Q.

Load A, B 0
0
0
1

0
0
1
1

0
1
2
3 1

0
0

0
0
0

4
5
6 0 0
7

1
0
0
0
1
1
0
0

Clock cycle

0 0
8

A/ Q

0
1
1
0

1
1
0
0

0
0
0

0 0
0 0

1
0
0
0

0
0
0
0

0
0
0

0 1
1 1

0
0
0
0
0
0
1
1
1

0 0 0 0 1 1 1 1

rr0 R

0
0
0
0

0
0
0

0 0

0
0
0
0
0
0
0
0

0 0 0

0
0
0
0

0
1
1

1
0
0

1 0
0 1

0
0
0
1

0
0
1
0

0
0
0

0 0
1 1

0
1
0
0
0
1
1
0
0

0 0 0 0 1 0 1 0

0
0
0
0
0
0
0
0
0
0

100011001001 A B

Shift left

Subtract , Q 0 1 ¬

Shift left, Q 0 0 ¬
Shift left, Q 0 0 ¬
Shift left, Q 0 0 ¬

Subtract, Q 0 1 ¬
Subtract, Q 0 1 ¬
Subtract , Q 0 1 ¬

Shift left, Q 0 0 ¬

B&V3, Figure 10.25
20T3 COMP3222/9222 Digital System Design L08/S69

ASM chart and datapath circuit for the enhanced divider

B&V3, Figure 10.26 & 10.27

L
E

DataB

LR
ER

Clock
Register

DataA LA

+
c out c in 1

Rsel
n

Left-shift
register

n n

a n 1 –

0 1

D Q

ER0

0
1

n 1 –

[r n 2 – … r ]0

n n

rr
0

Sum

DataR

[r
n

2 –
…

r
r

r
]

0
0

Rsel 0 = LC ER, ,

s
0 1

1 0

Reset

EA, ER0

c
out

ER ER0 EA Rsel 1 = , , ,

LR ECDone

1 0

Reset

Rsel = 0, LC

s
0 1

ER0, EA

ER, ER0, EA, Rsel = 1

0
s

1 0
cout

LR Done

1 0
z

20T3 COMP3222/9222 Digital System Design

VHDL code for the enhanced divider circuit
(Part a)

B&V3, Figure 10.28

20T3 COMP3222/9222 Digital System Design L08/S71

B&V3, Figure 10.28

VHDL code for the enhanced divider circuit
(Part b)

Rsel 0 = LC ER, ,

s
0 1

1 0

Reset

EA, ER0

c
out

ER ER0 EA Rsel 1 = , , ,

LR ECDone

1 0

Reset

Rsel = 0, LC

s
0 1

ER0, EA

ER, ER0, EA, Rsel = 1

0
s

1 0
cout

LR Done

1 0
z

20T3 COMP3222/9222 Digital System Design L08/S72

B&V3, Figure 10.28

LR <= ‘0’; EA <= ‘0’; VHDL code for the enhanced divider circuit (Part c) Rsel 0 = LC ER, , s 0 1 S1 S2 LR 1 0 Reset EA, ER0 c out z 1 0 ER ER0 EA Rsel 1 = , , , LR ECDone s S3 1 0 Reset S1 Rsel = 0, LC s 0 1 LR ER0, EA S2 ER, ER0, EA, Rsel = 1 0 s 1 0 cout 1 LR Done 1 0 z EC S3 20T3 COMP3222/9222 Digital System Design L08/S73 B&V3, Figure 10.28 VHDL code for the enhanced divider circuit (Part d) E L E L E DataB LR ER Clock Register EB 0 R DataA LA EA + c out c in 1 B w Rsel n Left-shift register n Left-shift register n n n n n a n 1 – Q 0 1 D Q Q ER0 0 1 0 n 1 – n [r n 2 – …r ]0 w n n rr 0 A Sum DataR [r n 2 – … r r r ] 0 0 20T3 COMP3222/9222 Digital System Design Simulation results for the enhanced divider circuit B&V3, Figure 10.29 20T3 COMP3222/9222 Digital System Design L08/S75 Design Ex 4: Finding the mean of k numbers pp 702 – 708, B&V3 B&V3, Figure 10.30 (b) ASM chart Sum 0 ¬ C k 1 –¬, s 0 1 S1 S2 Done s Reset 1 0 Sum Sum R C+ ¬ S4 C 0 = ? M Sum k ⁄ ¬ C C 1 –¬ 0 1 S3 Load registers Sum = 0 ; for i = k 1 downto 0 do Sum = Sum + R ;i end for; M = Sum ÷k ; (a) Pseudo-code – 20T3 COMP3222/9222 Digital System Design L08/S76 Finding the mean of k numbers – datapath B&V3, Figure 10.30 (b) ASM chart Sum 0 ¬ C k 1 –¬, s 0 1 S1 S2 Done s Reset 1 0 Sum Sum R C + ¬ S4 C 0 = ? M Sum k ⁄ ¬ C C 1 –¬ 0 1 S3 Load registers B&V3, Figure 10.31 E Register + E Register E Register E Register ERRAdd E L Down-counterE Register B EB A LA R Q Done s Divider ES 0 Ssel EC LC Div k EB LA zz Sum M Data Clock z k 1 “ n n n n n n n w 0 En y 0 w 1 y 1 y 2 y 3 2-to-4 k-1 E E E E E LE B EB A LA R Q Done s w1 w0 y0 y1 y2 y3 En E 0 1 2 3 01 E 2-to-4 RAdd ER Register Register Register Data Clock 0 Ssel ES Register Down counter EC LC k EB Sum n n LA Divider Div n n n zzM n + n z 20T3 COMP3222/9222 Digital System Design L08/S77 Smux Datapath & controlpath ASM for the mean operation , B&V3, Figure 10.31 E Register + E Register E Register E Register ERRAdd E L Down-counterE Register B EB A LA R Q Done s Divider ES 0 Ssel EC LC Div k EB LA zz Sum M Data Clock z k 1 “ n n n n n n n w 0 En y 0 w 1 y 1 y 2 y 3 2-to-4 k-1 E E E E E LE B EB A LA R Q Done s w1 w0 y0 y1 y2 y3 En E 0 1 2 3 01 E 2-to-4 RAdd ER Register Register Register Data Clock 0 Ssel ES Register Down counter EC LC k EB Sum n n LA Divider Div n n n zzM n + n z EC LC Ssel 0 = ES, , , s 0 1 S1 S2 Div, Done s Reset 1 0 Ssel 1 = ES, S5 LA EB, EC 0 1 S3 z Div zz S4 0 1 EC , , Reset S1 LC, Ssel = 0, ES s 0 1 Ssel = 1, ES S2 EC z 0 1 LA, EB S3 Div S4 S5 Div, Done zz 0 1 s 0 1 B&V3, Figure 10.32 20T3 COMP3222/9222 Digital System Design L08/S78 Smux Schematic of the mean circuit with an SRAM block B&V3, Figure 10.33 20T3 COMP3222/9222 Digital System Design L08/S79 Simulation results for the mean circuit using SRAM B&V3, Figure 10.34 Results are for finding the mean of numbers 0..15 20T3 COMP3222/9222 Digital System Design L08/S80 Prob 10.6: show a modified ASM chart that combines S3 and S4 into a single state Tell us about your experience and shape the future of education at UNSW. Click the link in Moodle Please be mindful of the UNSW Student Code of Conduct as you provide feedback. At UNSW we aim to provide a respectful community and ask you to be careful to avoid any language that is sexist, racist or likely to be hurtful. You should feel confident that you can provide both positive and negative feedback but please be considerate in how you communicate. https://student.unsw.edu.au/conduct Design Ex 5: Sort k words pp 708 – 718, B&V3 B&V3, Figure 10.35 // selection sort 1D array of data for i = 0 to k-2 do A = Ri; for j = i+1 to k-1 do B = Rj; if B < A then // swap elements Rj = A; Ri = B; // place smallest of [i+1, k-1] in Ri A = Ri; end if; end for; end for; 20T3 COMP3222/9222 Digital System Design L08/S82 1 2 13 10 18 27 13 11 Ri Rj 0 1 2 3 4 5 6 7 8 9 Rj 45 Rj ASM chart for the sort operation B&V3, Figure 10.36 for i = 0 to k-2 do A = Ri; for j = i+1 to k-1 do B = Rj; if B < A then Rj = A; Ri = B; A = Ri; end if; end for; end for; B A < ? C i 0 ¬ s 0 1 S1 S2 Done s Reset A R i ¬ C j C i ¬, C i C i 1 + ¬ S4 S5 0 1 S3 C j C j 1 + ¬ B R j ¬ R j A ¬ R i B ¬ A R i ¬ C j k 1 –= ? C j C j 1 + ¬ C i k 2 –= ? 0 1 0 1 Load registers 0 1 S9 S7 S6 S8 20T3 COMP3222/9222 Digital System Design L08/S83 E E E E Clock DataIn WrInit Rin 3 Rin 2 Rin 1 Rin 0 E E Bin Ain DataOut Rd ABData Imux B

Related Posts