Book contents
- Frontmatter
- Contents
- Preface
- Part 1 Preliminaries
- Part 2 Combinational logic
- Part 3 Finite-state machines
- 9 Introduction to synchronous sequential circuits and iterative networks
- 10 Capabilities, minimization, and transformation of sequential machines
- 11 Asynchronous sequential circuits
- 12 Structure of sequential machines
- 13 State-identification experiments and testing of sequential circuits
- 14 Memory, definiteness, and information losslessness of finite automata
- 15 Linear sequential machines
- 16 Finite-state recognizers
- Index
15 - Linear sequential machines
from Part 3 - Finite-state machines
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- Part 1 Preliminaries
- Part 2 Combinational logic
- Part 3 Finite-state machines
- 9 Introduction to synchronous sequential circuits and iterative networks
- 10 Capabilities, minimization, and transformation of sequential machines
- 11 Asynchronous sequential circuits
- 12 Structure of sequential machines
- 13 State-identification experiments and testing of sequential circuits
- 14 Memory, definiteness, and information losslessness of finite automata
- 15 Linear sequential machines
- 16 Finite-state recognizers
- Index
Summary
Linear sequential machines constitute a subclass of linear systems in which the input vector, output vector, and state transitions occur in discrete steps. Consequently, the tools and techniques available for the analysis and synthesis of linear systems can be applied to linear machines as well. The numerous applications of linear machines give further incentive to the investigation of their properties and to the development of efficient synthesis procedures.
In the first few sections we present an intuitive, though well-justified, approach that requires only a limited knowledge of modem algebra. In subsequent sections (i.e., Sections 15.4 through 15.6) a matrix formulation is presented, and methods for minimizing and detecting linear machines are developed.
Introduction
A linear sequential machine (also called a linear machine) is a network that has a finite number of input and output terminals and is composed of interconnections of three types of basic components, to be introduced shortly. The input signals applied to the machine are elements of a finite field GF(p) = {0, 1, …, p – 1}, and the operations performed by the basic components on their inputs are carried out according to the rules of GF(p). A block-diagram representation of a linear machine with l input terminals and m output terminals is shown in Fig. 15.1.
For a machine to be linear, its response to a linear combination of inputs must preserve the scale factor and the principle of superposition.
- Type
- Chapter
- Information
- Switching and Finite Automata Theory , pp. 523 - 569Publisher: Cambridge University PressPrint publication year: 2009