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 time-shared 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 time-shared 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 time-multiplexed way. There are several options for the controller, but this chapter covers a hardwired state machine-based 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 time-critical 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 one-hot state machine uses one flip-flop 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 field-programmable gate arrays (FPGAs) that are rich in flip-flops. If the objective is to conserve the number of flip-flops of a state register, a binary-coded 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 algorithm-like 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 algorithm-like, whereas in many instances the digital design methodology requires a representation that is better suited for an algorithm-like structure.

The algorithmic state machine (ASM) notation is explained. This is a flowchart-like graphical notation to describe the cycle-by-cycle 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 first-in first-out (FIFO).