Chapter 9
This chapter looks at digital designs in which hardware computational units are shared or timemultiplexed
to execute different operations of the algorithm. To highlight the difference between timeshared and fully dedicated architecture (FDA), the chapter first examines examples while assuming that the circuit clock is at least twice as fast as the sampling clock. It is explained that, if instances of these applications are mapped on a dedicated fully parallel architecture, they will not utilize the HW in every clock cycle. Time sharing is the logical design decision for mapping these applications in HW. These designs use the minimum required HW computational resources and then share them for multiple computations of the algorithm in different clock cycles. The examples pave the way to generalize the discussion to timeshared architecture.
A synchronous digital design that shares HWbuilding blocks for computations in different cycles requires a controller. The controller implements a scheduler that directs the use of resources in a timemultiplexed way. There are several options for the controller, but this chapter covers a hardwired state machinebased controller that cannot be reprogrammed.
The chapter describes both Mealy and Moore state machines.With the Mealy machine the output and next state are functions of the input and current state, whereas with the Moore machine the input and current state only compute the next state and the output only depends on the current state. Moore machines provide stable control input to the datapath for one complete clock cycle. In designs using the Mealy machine, the output can change with the change of input and may not remain stable for one complete cycle. For digital design of signal processing systems, these output signals are used to select the logic in the datapath. Therefore these signals are timecritical and they should be stable for one complete cycle. Stable output signals can also be achieved by registering output from a Mealy machine.
The current state is latched in a state register in every clock cycle. There are different state encoding methods that affect the size of the state register. A onehot state machine uses one flipflop per state. This option is attractive because it results in simple timing analysis, and addition and deletion of newer states is also trivial. This machine is also of special interest to fieldprogrammable gate arrays (FPGAs) that are rich in flipflops. If the objective is to conserve the number of flipflops of a state register, a binarycoded state machine should be used.
The chapter gives special emphasis to RTL coding guidelines for state machine design and lists RTL Verilog code for examples. The chapter then focuses on digital design for complex signal processing applications that need a finite state machine to generate control signals for the datapath and have algorithmlike functionality. The conventional bubble representation of a state machine is described, but it is argued that this is not flexible enough for describing complex behavior in many designs. Complex algorithms require gradual refinement and the bubble diagram representation is not appropriate. The bubble diagram is also not algorithmlike, whereas in many instances the digital design methodology requires a representation that is better suited for an algorithmlike structure.
The algorithmic state machine (ASM) notation is explained. This is a flowchartlike graphical notation to describe the cyclebycycle behavior of an algorithm. To demonstrate the differences, the chapter represents in ASM notation the same examples that are described using a bubble diagram. The methodology is illustrated by an example of a firstin firstout (FIFO).
