Online Postgraduate Courses for the Electronics Industry

Provided By The University of Bolton

• Home
• About Us
• Questions & Answers
• Courses
• Students
• Links

Useful Tools

Digital Integrated Circuit Design

Unit 2 : Control Circuitry Design

This unit introduces the concepts of finite state machine design using the Algorithmic State Machine (ASM) method. A typical design flow is considered detailing specification, state sequence definition, logic equation extraction and synthesis to a range of target technologies.

Unit Contents

• 2.1 Introduction
• 2.2 The Finite State Machine
• 2.3 The Algorithmic State Machine Method
• 2.4 Case Study
• 2.5 FSM Design Exercise

2.1 Introduction

A typical digital system will comprise dataflow and control elements as shown below.

Figure 2.1 A typical digital system

The dataflow elements will be combinational and sequential components such as adders, multiplexors, registers, counters etc. There could be some data flowing in and some data flowing out. The components within the dataflow will require controlling so that the movement of data occurs in the required direction at the required time. The dataflow will therefore require control signals for this purpose and will typically generate status symbols to indicate the present state of the system.

The control elements can be implemented as a finite state machine. The machine will require a system clock for sequencing and a system reset for state initialisation. Typically it will need to interface with input control signals from other system components and generate output control signals in response. In turn it will provide the necessary control signals to the dataflow and monitor the dataflow status signals for possible modification of the control sequence.

A good example of this type of digital circuit construction is a computer processor which contains both a control unit and a dataflow unit. The control unit decodes the opcode from each instruction and defines the necessary control sequences for execution. It will require inputs from and generate outputs to other components  in the system e.g. memory and input/output units. The dataflow unit typically contains data and address registers, an arithmetic/logic unit (ALU), a shifter, data and address buses and the necessary multiplexors to connect these items together. The registers will require enable signals, the ALU will require a function select (e.g. ADD, SUBTRACT, AND, OR etc), the shifter will require a shift mode (e.g. RIGHT, LEFT, LOGICAL, ROTATE etc) and the multiplexors will need input selects. Additionally the dataflow unit will generate status signals e.g. CARRY, OVERFLOW, ZERO and SIGN conditions. Data in and data out will flow from and to the system data and address buses.

2.2 The Finite State Machine

Finite state machines are designed using the same basic principles as digital counters. Conventionally a counter will comprise a set of state latches to store the present state and combinational steering logic to predict the next state. The interaction of these two elements is detailed below.

Figure 2.2 The Finite State Machine

In its present form the counter will sequence through a specific binary pattern defined by the construction of the components in the steering logic. By adding combinational circuitry to the output of the state latches we can generate a set of control signals that will be activated at various points of the count sequence.

Example:

To switch on an LED in states 5 and 7 and a motor in state 3 we would construct the following logic:-

Figure 2.3 The Finite State Machine

Generally for control purposes we require the counter to define a set of different count sequences so that different control signals can be generated or the same control signals activated at different times. To achieve this it is necessary to incorporate status signals into the steering logic so that the next state in the sequence now becomes conditional not only on the current state but on the value of one or more of these signals.

Example:

The next state of latch A will be a logic 1 with ABC in states 4, 5 or 7 and ALARM = 0 but logic 0 if ALARM = 1

Figure 2.4 The Finite State Machine

The inclusion of both output circuitry to generate control signals and status signals in the steering logic of a conventional counter defines the general construction of a finite state machine, as shown below.

Figure 2.5 The Finite State Machine

[Back to top]

2.3 The Algorithmic State Machine Method

The Algorithmic State Machine (ASM) method is a formalised technique for designing finite state machines. It provides the following advantages over more ad hoc methods:

• reduces design errors
• produces robust designs
• self documenting
• easy to automate

1) System Specification

The control and status signals for the state machine and associated dataflow are defined together with any required interface protocols.

2) ASM Chart Definition

The ASM chart is constructed to define the required control sequence. The chart appears similar in construction to a conventional software flow diagram and utilises the following three symbols:

3) Assignment of State Codes

The finite state machine latches will sequence through a defined set of state codes. In a normal binary sequence there are transitions where two or more bits in the code change simultaneously. The latch outputs would therefore be changing at slightly different points in time since a flip-flop always switches to a logic 0 faster than to a logic 1. Consequently the logic decoding these values is quite likely to produce snigs and glitches on its control signal outputs .The effect is particularly troublesome if the control signals are feeding other sequential logic components where, for example, a glitch on a flip-flop clock input could spuriously change the state of the device.

Example:

A code assignment of 00 --> 01 --> 10 -->11  is potentially hazardous changing from 01 --> 10.

The occurrence of snigs and glitches can be minimised by attempting to allocate a Gray code sequence to the state codes such that only one bit in the code changes for each transition. On occasions where this is not possible  the code assignment should be constrained to the minimum number of bit changes.
 

A useful technique for assigning state codes is to plot the state numbers in adjacent squares on a Karnaugh map, then read off the corresponding values of the latches (A, B and C in this example).

Figure Figure 2.8 Assignment of State Codes

4) FSM Specification

The required operation of the finite state machine can be specified in one of two ways:-

Figure 2.9 Constrction of an ASM Table

The table details all possible transitions from one state A  B C  (the latch Q outputs) to the next DA DB DC (the latch D inputs), the input signal values that are relevant to each transition and the corresponding output control signals that have to be generated.

So in the above example the table indicates:

A transition from state 1 back to state 1 if Z=0, generating control signals LOAD =0, ADD=1 and SHIFT =0.

A transition from state 1 to state 2 if Z=1, generating control signals LOAD=1 ADD=0, SHIFT=1.

Inputs X and Y are not relevant to this particular transition (indicated by -).

States 1 and 2 have been allocated codes  000 and 101 respectively on the state machine latches.
 

b) Construction of a VHDL Functional Description

The VHDL code will define a process detailing each possible state transition and associated input signal values and a set of concurrent statements specifying the required output control signals values for each state.
 

5) Logic Synthesis

The translation of the FSM specification into the required target technology can be accomplished either by the manual derivation from the ASM table of logic equations for the next state conditions and control signals and subsequent implementation in logic or by running the VHDL code through a logic synthesiser.

[Back to top]

2.4 Case Study An 8 bit Multiplier Unit Controller

The following case study details the design flow for implementing the controller of an 8 bit multiplier unit as a finite state machine.

Figure 2.10 System Specification

Figure 2.11 System Specification

Notes:

1. The dataflow performs multiplication by repetitively adding the multiplicand to the product register.
2. The multiplier is used as a decrementing count to control the number of additions.
3. The dataflow unit receives operands from and supplies results to the system data bus.
4. The LOAD signal is used as a register enable on the multiplicand and multiplier registers and also serves to initialise the product register to zero.
5. The multiplier register is configured as a binary down counter with zero detection logic.
6. The ADD signal enables the product register.

Figure 2.12 ASM Chart Definition

An appropriate assignment would be:

Figure 2.13 Assignment of State Codes

Note that it is not possible to achieve a 1 bit code change for every transition in this sequence. With the above assignment there will be a two bit change from state 2 to state 4.

FSM Specification

a) ASM Table

Figure 2.14 a) ASM Table

b) VHDL Code

library IEEE;
use IEEE.std_logic_1164.all;

entity MULT_CTRL is
port (CLK, RESET, OA, PA, CZ : in std_logic;

LOAD, ADD, DEC, MC :out std_logic);

end MULT_CTRL;

architecture BEHAVIOUR of MULT_CTRL is

type STATE_TYPE is (ONE,TWO,THREE,FOUR);
signal STATE: STATE_TYPE;

begin
FSM : process (CLK, RESET)
begin
if RESET = '1' then

STATE <= ONE;

elsif CLK'event and CLK ='1' then
case STATE is

when ONE =>

if OA = '0'

then STATE <= ONE;

elsif OA = '1' then

STATE <= TWO;

end if;

when TWO =>

if CZ ='0' then

STATE <= THREE;

elsif CZ ='1'

then STATE <= FOUR;

end if;

when THREE =>

STATE <= TWO;

when FOUR =>

if PA ='0' then

STATE <= FOUR;

else if PA ='1' then

STATE <= ONE;

end case;
end if;
end process FSM;

LOAD <= '1' when (STATE = ONE) and (OA = '1') else '0';
ADD <= '1' when (STATE = THREE) else '0';
DEC <= '1' when (STATE = THREE) else '0';
MC <= '1' when (STATE = FOUR ) else '0';
end BEHAVIOUR;

configuration CONFIG_MULT_CTRL of MULT_CTRL is
for BEHAVIOUR
end for;
end CONFIG_MULT_CTRL;
 

Logic Synthesis

a) From the ASM Table

We require logic equations for the next state conditions (DA, DB and DC) and the output control signals (LOAD, ADD, DEC and MC). The procedure is to construct a separate Karnaugh Map for each function. The present state conditions and input signals are allocated as the map variables and the required values of each function plotted from the ASM table.

Since it is difficult to deal with Karnaugh Maps of more than 4 variables we choose to allocate some of the map variables as Map Entered Variables i.e. they appear in the map squares. The choice of variable allocation and size of map is arbitrary. We will choose A, B and OA as the map variables, PA and CZ as the map entered variables and plot on a three variable Karnaugh Map. The procedure is to scan the ASM table for lines where the required function is a logic 1. If the corresponding map entered variables are don't care values then enter an unconditional 1 in the appropriate square. If there is a relevant map entered variable then enter the variable. If there is more than one relevant map entered variable then enter an appropriate Boolean function for the variables. The remaining squares are either don't care (if they are unused codes) or logic 0.

Figure 2.15 Logic Synthesis

• From state 2 to state 3 when A=1, B=0 and DA is required to be a logic 1, CZ=0 so is entered as '(CZ) in all squares where A=1 and B=0. Therefore when CZ=0 these squares will assume the logic 1 value, when CZ=1 they will assume a logic 0 providing the correct value for DA as specified by the ASM table.
• From state 2 to state 3 and state 2 to state 4 when A=1, B=0 and DB is required to be a logic 1, CZ is both a logic 0 and a logic 1.

Rules for minimising from the map

1. Set the map entered variables to logic 0 and minimise for the logic ones in the normal way.
2. Restore the map entered variables and set the logic ones to don't care conditions. Minimise for the map entered variables. The don't care conditions in adjacent squares to the map entered variables can be set equal to the variables to obtain the most efficient minimisation.
3. Combine the logic expressions obtained in 1) and 2) to obtain the final logic expression.

Therefore for DA and DB :-

Similarly for the conditional and unconditional output control signals.

Figure 2.16 Logic Synthesis

The logic expressions for DA and DB are used to implement the steering logic, those for LOAD, ADD, DEC and MC for the output control signal logic.

b) From the VHDL code

The input of the VHDL code to a logic synthesiser would be expected to produce a circuit construction based on the standard FSM architecture.

[Back to top]

Exercise

2.5  FSM Design Exercise

Use the ASM method to design a finite state machine traffic light controller to the following specification:

1) Construct an appropriate ASM chart.

2) Derive the ASM table.

3) Derive suitable logic equations for the steering and output logic.

Figure 2.17 FSM Design Exercise

The system provides the normal traffic light sequencing. An automatic mode and a manual mode are provided. In manual mode spotlights are used to illuminate a policeman controlling traffic at the junction.

NSRED, NSAMBER, NSGREEN feed lights in the north-south direction.
EWRED, EWAMBER, EWGREEN feed lights in the east-west direction.

AUTO = 1 defines automatic sequencing.
AUTO = 0 defines manual operation in which the sequence halts at the next NSRED-EWRED combination.

SPOT_CTRL effective only when AUTO=0.
SPOTLIGHTS are activated when SPOT_CTRL =1in a NSRED-EWRED combination.

Show Solution

[Back to top]

Site Search

Powered by Google
Site Map