automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

, sequential logic is a type of

logic circuit A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gat ...

whose output depends on the present value of its input signals and on the

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...

of past inputs, the input history. This is in contrast to ''

combinational logic In automata theory, combinational logic (also referred to as time-independent logic or combinatorial logic) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only. This i ...

'', whose output is a function of only the present input. That is, sequential logic has ''

state State may refer to: Arts, entertainment, and media Literature * ''State Magazine'', a monthly magazine published by the U.S. Department of State * ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States * ''Our S ...

'' (''memory'') while combinational logic does not. Sequential logic is used to construct

finite-state machine A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

s, a basic building block in all digital circuitry. Virtually all circuits in practical digital devices are a mixture of combinational and sequential logic. A familiar example of a device with sequential logic is a

television set A television set or television receiver, more commonly called the television, TV, TV set, telly, tele, or tube, is a device that combines a tuner, display, and loudspeakers, for the purpose of viewing and hearing television broadcasts, or using ...

with "channel up" and "channel down" buttons. Pressing the "up" button gives the television an input telling it to switch to the next channel above the one it is currently receiving. If the television is on channel 5, pressing "up" switches it to receive channel 6. However, if the television is on channel 8, pressing "up" switches it to channel "9". In order for the channel selection to operate correctly, the television must be aware of which channel it is currently receiving, which was determined by past channel selections. The television stores the current channel as part of its ''

''. When a "channel up" or "channel down" input is given to it, the sequential logic of the channel selection circuitry calculates the new channel from the input and the current channel. Digital sequential logic circuits are divided into

synchronous Synchronization is the coordination of events to operate a system in unison. For example, the conductor of an orchestra keeps the orchestra synchronized or ''in time''. Systems that operate with all parts in synchrony are said to be synchronou ...

and asynchronous types. In synchronous sequential circuits, the state of the device changes only at discrete times in response to a clock signal. In asynchronous circuits the state of the device can change at any time in response to changing inputs.

Synchronous sequential logic

Nearly all sequential logic today is ''clocked'' or ''synchronous'' logic. In a synchronous circuit, an

electronic oscillator An electronic oscillator is an electronic circuit that produces a periodic, oscillation, oscillating electronic signal, often a sine wave or a square wave or a triangle wave. Oscillation, Oscillators convert direct current (DC) from a power supp ...

called a ''clock'' (or

clock generator A clock generator is an electronic oscillator that produces a clock signal for use in synchronizing a circuit's operation. The signal can range from a simple symmetrical square wave to more complex arrangements. The basic parts that all clock ge ...

) generates a sequence of repetitive pulses called the '' clock signal'' which is distributed to all the memory elements in the circuit. The basic memory element in sequential logic is the flip-flop. The output of each flip-flop only changes when triggered by the clock pulse, so changes to the logic signals throughout the circuit all begin at the same time, at regular intervals, synchronized by the clock. The output of all the storage elements (flip-flops) in the circuit at any given time, the binary data they contain, is called the ''

'' of the circuit. The state of the synchronous circuit only changes on clock pulses. At each cycle, the next state is determined by the current state and the value of the input signals when the clock pulse occurs. The main advantage of synchronous logic is its simplicity. The logic gates which perform the operations on the data require a finite amount of time to respond to changes to their inputs. This is called ''

propagation delay Propagation delay is the time duration taken for a signal to reach its destination. It can relate to networking, electronics or physics. ''Hold time'' is the minimum interval required for the logic level to remain on the input after triggering e ...

''. The interval between clock pulses must be long enough so that all the logic gates have time to respond to the changes and their outputs "settle" to stable logic values before the next clock pulse occurs. As long as this condition is met (ignoring certain other details) the circuit is guaranteed to be stable and reliable. This determines the maximum operating speed of the synchronous circuit. Synchronous logic has two main disadvantages: * The maximum possible clock rate is determined by the slowest logic path in the circuit, otherwise known as the critical path. Every logical calculation, from the simplest to the most complex, must complete in one clock cycle. So logic paths that complete their calculations quickly are idle much of the time, waiting for the next clock pulse. Therefore, synchronous logic can be slower than asynchronous logic. One way to speed up synchronous circuits is to split complex operations into several simple operations which can be performed in successive clock cycles, a technique known as '' pipelining''. This technique is extensively used in

microprocessor A microprocessor is a computer processor where the data processing logic and control is included on a single integrated circuit, or a small number of integrated circuits. The microprocessor contains the arithmetic, logic, and control circu ...

design and helps to improve the performance of modern processors. * The clock signal must be distributed to every flip-flop in the circuit. As the clock is usually a high-frequency signal, this distribution consumes a relatively large amount of power and dissipates much heat. Even the flip-flops that are doing nothing consume a small amount of power, thereby generating

waste heat Waste heat is heat that is produced by a machine, or other process that uses energy, as a byproduct of doing work. All such processes give off some waste heat as a fundamental result of the laws of thermodynamics. Waste heat has lower utility ...

in the chip. In battery-powered devices, additional hardware and software complexity is required to reduce the clock speed or temporarily turn off the clock while the device is not being actively used, in order to maintain a usable battery life.

Asynchronous sequential logic

Asynchronous sequential logic is not synchronized by a clock signal; the outputs of the circuit change directly in response to changes in inputs. The advantage of asynchronous logic is that it can be faster than synchronous logic, because the circuit doesn't have to wait for a clock signal to process inputs. The speed of the device is potentially limited only by the

s of the logic gates used. However, asynchronous logic is more difficult to design and is subject to problems not encountered in synchronous designs. The main problem is that digital memory elements are sensitive to the order that their input signals arrive; if two signals arrive at a flip-flop or latch at almost the same time, which state the circuit goes into can depend on which signal gets to the gate first. Therefore, the circuit can go into the wrong state, depending on small differences in the

s of the logic gates. This is called a

race condition A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is Sequential logic, dependent on the sequence or timing of other uncontrollable events. It becomes a software ...

. This problem is not as severe in synchronous circuits because the outputs of the memory elements only change at each clock pulse. The interval between clock signals is designed to be long enough to allow the outputs of the memory elements to "settle" so they are not changing when the next clock comes. Therefore, the only timing problems are due to "asynchronous inputs"; inputs to the circuit from other systems which are not synchronized to the clock signal. Asynchronous sequential circuits are typically used only in a few critical parts of otherwise synchronous systems where speed is at a premium, such as parts of microprocessors and

digital signal processing Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations. The digital signals processed in this manner are ...

circuits. The design of asynchronous logic uses different mathematical models and techniques from synchronous logic, and is an active area of research.

Synchronous sequential logic

Asynchronous sequential logic

See also

References

Further reading