State machines – a practical perspective

Hi friends, until now, we have learned how to write the RTL. We have also learned that RTL is the building block of digital system design. A well-written verilog code represents the complete system. We can also say that the verilog code represents the state machine of the system. But what is a state machine? As per the definition, a state machine consists of a set of states, a start state, an input and a transfer function that maps inputs and current state to next state. State machine designing is the heart of digital system design. All digital systems are state machines. We have learned how to write the RTL with the example of a clock as a system. In this post, we will discuss the state machines from a different perspective and try to build out understanding by representing our own clock as a state machine.

As we just discussed, each digital system is a state machine. It has an initial state, gets some inputs, moves to other states and provides some outputs. For example, consider a processor. Initially, it is in reset state. When reset is asserted, it comes out of reset state into stop/run state as described by a set of inputs defining mode of operation. It also fetches instructions from cache/RAM. This state can be termed as instruction fetching state. It goes into interrupted state upon receiving a request from a peripheral. In all these states, the processor also produces some outputs representing its states.

What corresponds a state in a digital design?  Each design is composed of a set of registers whose value is updated on every clock edge. Each edge corresponds to a state. The inputs/outpus and logic gates between registers ensure that the design state is updated every time a clock edge is encountered. All the registers have setup and hold checks that have to be met in order to ensure that the data is transferred appropriately between registers and right data is captured at every clock edge. Figure 1 below shows the state map for a design consisting of all positive edge-triggered registers. As is obvious, all the registers values are updated at each positive clock edge, hence, we say that the state machine updated its state at each positive clock edge.  In other words, we can say that at each clock edge, the state machine makes decisions based upon its inputs and present state and moves to next state.

Figure 1: Each clock edge corresponds to a state.

Digital clock as a state machine: We just discussed a simple example of a processor as a state machine. Now, let us discuss our own clock as a state machine. Repeating here the definition of a state machine, a state machine consists of a set of states, a start state, an input and a transfer function that maps inputs and current state to next state. Figure 1 below shows the block diagram of our digital clock. As is shown, it consists of

i)                    An up counter

ii)                   Different sets of registers (hour registers, minute registers and seconds registers)

iii)                 A group of adders and

iv)                 A control FSM.

Let us explore different aspects of our digital clock state machine.

State: A particular configuration of the different registers and control FSM represents a state of our state machine. The different states may be:

i)                    RESET state

ii)                   RUNNING state

iii)                 STOP state

Start State: The start state of our machine is either 00:00:00 (when the clock goes into RESET state) or REF_TIME (when REF_TIME input is provided).

Inputs: The inputs to our digital clock state machine are:

i)                    RESET and other control signals

ii)                   REF_TIME

Transfer function: The transfer function here is the condition that updates the state of our state machine. In other words, if RESET is asserted, output goes to zero, otherwise it increments by 1 second.

Outputs: The output here is the time that is displayed on the screen of the digital clock.

Figure 2: Digital clock block digram

Now, let us proceed towards getting the state diagram for our digital clock state machine, which is as shown below in figure 2. We can consider it as a state machine consisting of three states.

1. RESET state: When RESET input is asserted, the time goes to 00:00:00. As long as RESET input remains asserted, the state machine remains into RESET state.
2. RUN state: This is the normal state of our digital clock state machine. The output is the current time; i.e. current state of registers.
3. REF_IN state: When REF_IN input changes, the clock state machine output changes and becomes equal to REF_IN input applied. And the very next cycle, it returns to RUN state.

Figure 3: State machine corresponding to digital clock

Thus, in this post, we have discussed about how a state machine should be looked upon from a practical perspective and illustrated the same by considering a digital clock as a state machine. Stay tuned and learn with fun.

Verilog/RTL for Beginners: Stage 1

Hi friends, we all know how easier it is for anyone to ask you to deliver a SYNTHESIZABLE RTL based on any C/MATLAB etc. and you are stuck with a dilemma in guessing where to begin with. So in this post we will be laying down some fundamentals along with examples that may help you in getting it done right and easy. We have divided this tutorial into a set of stages each of which targets a specific aspect of RTL coding/design. These stages start from black box to detailed architecture level models as well extended but not limited to synthesizable RTL as well as gate level designs.

Our of the examples will include:

·         Basic digital designs: Adders, ALU, Comparators, Counters, Multipliers etc.

·         Memory Models      : ROMs, RAMs, 2-port memories, single port memories.

·         FSM Designs             : Mealy, Moore, One-hot.

·         Processor design     : RISC, CISC.

·         ASIC Cores                : FFT processors, DWT processors, FIRs Filters, Convolutors, Image/video codecs.

Stage 1 : Black Box and Block Diagrams

Before starting with examples and coding methods, let us first define the basic steps that you should take for implementing your code especially if you’re a novice.

1. Get the Black Box:     

Break the code as black box entity that takes something as an input and outputs something.

Example:

      Suppose you want to make a digital clock. Then it can simply be treated as a black box that simply outputs the time with some control (for adjusting time) and reference signal (a digital oscillator clock) as inputs. 

     2. Pen is Mightier than Code: 

The next step is to get the hang of the functionality that this black box is supposed to do. Take the function itself that the code is meant for and use it on a very simple test case but rather than using the code use a pen and paper solve it instead. This is the only way you will understand the code and identify your true problem statement

Example:

Consider the same clock problem as above. How will you write the same function as the clock on a paper? Simple:

·         Consider the current time as A (hours : minutes : seconds)

·         Write three variables HR=0 MIN= 0 and SEC= 0.

·         Now keep checking your reference watch/clock and after each second/tick (take 5 if you can’t write quick: P ) add 1 (or 5 if you followed the previous advice)  to SEC.

·         Now by doing so a point will come when after adding SEC = 60, at this instance add 1 to MIN and change SEC=0.

·         Do the same for HR when MIN=60.

·         For getting the output time simply add the reference time A to the calculated time HR:MIN:SEC ( be careful while adding time it’s not 0-100 but 0-60)

·         And there you go the clock is working on paper.

     3. Break the Black Box:  

                        

So far you should have got a hang on things regarding what and how the function is supposed to do things. The next step is to break this functionality into smaller and simpler groups and the best way to this is to take inspiration from your own rough work. Refer to the paper on which you solved the problem itself and identify each type of secondary function you had to do/use in order to write stuff on that paper. This helps you in creating solutions for multiple simpler problems instead of a complex one. But enough said, this is a statement we’ve all heard people say but what they ever tell us about is how to do it exactly. So here’s what you have to do.

Example:

The first thing that you will notice on the paper is the very first column titled tick. This column is simply used to track the number of ticks that have occurred after reference time A. In digital domain you can simply realize this by using a synchronous up-counter operating at 1Hz clock frequency (every 1second the counter increments by 1).

 So there you have the very first sub-block of your system i.e. an up-counter block A. Leave the counter specifications like size and reset limits for now, we shall discuss this at a later stage.

The next 3 columns show 3 internal variables that you use for keeping track of time count. In digital domain variables can simply be realized by using registers as they can be loaded as well as read. In addition, each of these variables is always incremented by 1 and resets to 0 when its value reaches 60 (except for HR which may be limited to 12/24).

Thus they can be modeled using three registered variables along with an adder (adds +1) which is the second sub-block inside the black box name block B.

The 5^th column A is simply a reference variable and it never changes, so you can simply use it as a direct input. The last variable is simply an added version of previous 4 columns and hence can be realized using simple adders as a block C. And this completes the breaking of the black box as follows:

     4. Link the Blocks: 

                       

After identifying the key sub-blocks of your concerned design/code/function the next step is to link the logical exchange of info amongst these blocks as well as the external world. To do so identify the dependency of each block and simply use arrows to denote those dependencies. This will help us in understanding the inputs and outputs of each of these sub-blocks and thus understand the actual flow of information.

Example:

Let us start with block A. It is an up-counter and an up-counter primarily depends on the reference clock that keeps on triggering it. Thus block A only has a dependency on external reference clock signal.

Block B has three registers which are either added one or reset to zero. The addition however is driven by certain conditions from both the counter values as well as register values themselves. Thus the dependency of adder unit inside block B is only the register outputs while the registers have three dependencies, first from the output of adders, the second from the up-counter and the third from the other register like HR is dependent on MIN, MIN is dependent on SEC and SEC is dependent on up-counter. 

Block C is rather a much simpler block that only adds the three registers of block B to input reference time. Thus it only has a dependency on input reference time and three block B registers. The important thing about this block though is that the output of this block is in fact the output result itself.

     5. The Missing Link:        

At this point you should have more or less identified all the major data processing requirements of your design. However, the key entity missing in these links is the control and synchronization block. This is the block that decides the what, when and how the data flows across all these connection links shown above so that the desired functionality is obtained.

The concept of a Finite state machine or FSM is one of the most commonly used techniques to model this control block. The key idea behind FSM is that at any moment each section the design will be doing some work. However, this work will always be of repetitive nature and sequence of work performed will also be of finite order like a counting sequence with limited upper value which goes like 1,2,3,…9,1,2,3,..8, 9, 1 & so on.

We will discuss the concept of FSM in more details later but for now let us assume that this FSM block is the main control unit that synchronizes each and every block of your design. The inputs to this block will be the output of each block and/or input that is required for determining the next sequence of action and the outputs are function enabling signals like a memory chip-select or reset signal. The FSM is also similar to a counter and hence this will also use a reference clock for its operation. 

And there you have it folks, from black box to top level block diagram for your RTL right from the scratch.