Spectral Logic and Its Applications for the Design of Digital Devices

CHAPTER 7

SPECTRAL METHODS OF SYNTHESIS OF SEQUENTIAL MACHINES

In the previous chapters we discussed the elements of the theory of discrete transforms and methods for their application to the analysis, synthesis, and optimization of digital devices implementing logical functions (combinational networks). In this chapter we consider their application to the synthesis of digital devices with memory.

In particular, we will investigate the problem of constructing optimal state assignments for input signals and internal states for Haar based implementations of sequential devices by the corresponding finite automata.

7.1 REALIZATION OF FINITE AUTOMATA BY SPECTRAL METHODS

7.1.1 Finite Structural Automata

A Finite Automaton (FA) or a state transition machine is a model of the operation of a digital device with memory.

The operation of any device may be modeled at two levels, abstract and structural. The appropriate mathematical models are respectively known as abstract automata and structural finite automata.

An abstract finite automaton is defined as a set of six objects

TABLE 7.1.1 Next-State Function for the Automaton in Example 7.1.2.

where X is the (finite) set of input signals, A the (finite) set of internal states, Y the (finite) set of output signals, a₀ the initial state, ϕ(x, a ...