Sequential logic
Encyclopedia
In digital circuit
theory, sequential logic is a type of logic circuit whose output depends not only on the present input but also on the history of the input. This is in contrast to combinational logic
, whose output is a function of, and only of, the present input. In other words, sequential logic has state
(memory) while combinational logic does not.
Sequential logic is therefore used to construct some types of computer
memory
, other types of delay and storage elements, and finite state machine
s. Most practical computer circuits are a mixture of combinational and sequential logic.
There are two types of finite state machine that can be built from sequential logic circuits:
Depending on regulations of functioning, digital circuits are divided into synchronous and asynchronous. In accordance with this, behavior of devices obeys synchronous or asynchronous logic.
.
The main advantage of synchronous logic is its simplicity. Every operation in the circuit must be completed inside a fixed interval of time between two clock pulses, called a 'clock cycle'. As long as this condition is met (ignoring certain other details), the circuit is guaranteed to be reliable.
Synchronous logic also has two main disadvantages, as follows:
For asynchronous logic it is sufficient to determine a sequence of switchings irrespective of any connections of the corresponding moments with real or virtual time.
Theoretical apparatus of sequential logic consists of mathematical instruments of sequention and venjunction as well as of logic-algebraic equations on their basis.
, where 
. By means of sequention a binary function 
is realized so that 
takes place in the case 
, and under such conditions that 
for all 
. (Sign 
marks leading relation). Sequential function turns into unity at unity values of arguments, whose setting occurs consecutively, starting by 
and finishing with 
. All other cases give 
.
, according to which logical connective 
takes a unity value in the case 
under such conditions that at the moment of 
setting equality 
already took place. True of venjunction is caused by switching 
on the background 
. Logical indetermination is expressed by means of venjunction: 
. Venjunction and minimal (two-element) sequention are functionally identical:
, where formula
represents a function of SR flip-flop. Sequentor is constructed on the basis of composition of venjunctors, which are connected in the definite way.
For example, formulae
or 
are applicable for realizing sequention 
.
, whose state changes only when a global clock signal changes, and whose next-state depends only on the current state and the inputs.
Nearly all digital electronic devices (microprocessors, digital clock
s, mobile phone
s, cordless telephone
s, electronic calculator
s, etc.) are designed as clocked sequential systems.
Notable exceptions include digital asynchronous logic systems.
In particular, nearly all computers are designed as clocked sequential systems.
Notable exceptions include analog computer
s and clockless CPUs.
Typically each bit of the "state" is contained in its own flip-flop
.
Combinational logic
decodes the state into the output signals.
More combinational logic encodes the current state and the inputs into the next-state signals.
The next-state signals are latched into the flipflops under the control of the global clock signal (a wire connected to every flip-flop).
A clocked sequential system is a kind of Moore machine
.
Digital circuit
Digital electronics represent signals by discrete bands of analog levels, rather than by a continuous range. All levels within a band represent the same signal state...
theory, sequential logic is a type of logic circuit whose output depends not only on the present input but also on the history of the input. This is in contrast to combinational logic
Combinational logic
In digital circuit theory, combinational 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 is in contrast to sequential logic, in which the output depends not only on the present input but also on the...
, whose output is a function of, and only of, the present input. In other words, sequential logic has state
State (computer science)
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
(memory) while combinational logic does not.
Sequential logic is therefore used to construct some types of computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
memory
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....
, other types of delay and storage elements, and finite state machine
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
s. Most practical computer circuits are a mixture of combinational and sequential logic.
There are two types of finite state machine that can be built from sequential logic circuits:
- Moore machineMoore machineIn the theory of computation, a Moore machine is a finite-state machine, whose output values are determined solely by its current state.-Name:The Moore machine is named after Edward F...
: the output depends only on the internal state. (The internal state only changes on a clock edge; the output thus only changes on a clock edge). - Mealy machineMealy machineIn the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. The outputs change asynchronously with respect to the clock, meaning that the outputs change at unpredictable times, making timing analysis...
: the output depends not only on the internal state, but also on the inputs.
Depending on regulations of functioning, digital circuits are divided into synchronous and asynchronous. In accordance with this, behavior of devices obeys synchronous or asynchronous logic.
Synchronous sequential logic
Nearly all sequential logic today is 'clocked' or 'synchronous' logic: there is a 'clock' signal, and all internal memory (the 'internal state') changes only on a clock edge. The basic storage element in sequential logic is the flip-flopFlip-flop (electronics)
In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information. The circuit can be made to change state by signals applied to one or more control inputs and will have one or two outputs. It is the basic storage element in sequential logic...
.
The main advantage of synchronous logic is its simplicity. Every operation in the circuit must be completed inside a fixed interval of time between two clock pulses, called a 'clock cycle'. As long as this condition is met (ignoring certain other details), the circuit is guaranteed to be reliable.
Synchronous logic also has two main disadvantages, as follows:
- 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 in the chip.
- The maximum possible clock rate is determined by the slowest logic path in the circuit, otherwise known as the critical path. This means that every logical calculation, from the simplest to the most complex, must complete in one clock cycle. One way around this limitation is to split complex operations into several simple operations, a technique known as 'pipelining'. This technique is prominent within microprocessor design, and helps to improve the performance of modern processors.
Asynchronous sequential logic
Asynchronous sequential logic expresses memorizing effect by fixing moments of time, when digital device changes its state. These moments are represented not in explicit form, but taking into account principle “before/after” in temporal relations of logical values.For asynchronous logic it is sufficient to determine a sequence of switchings irrespective of any connections of the corresponding moments with real or virtual time.
Theoretical apparatus of sequential logic consists of mathematical instruments of sequention and venjunction as well as of logic-algebraic equations on their basis.
Sequention
Sequention is a sequence of propositional elements represented by the ordered set, for example, where . By means of sequention a binary function is realized so that takes place in the case , and under such conditions that for all . (Sign marks leading relation). Sequential function turns into unity at unity values of arguments, whose setting occurs consecutively, starting by and finishing with . All other cases give .Venjunction
Venjunction is asymmetrical logic/dynamic operation, according to which logical connective takes a unity value in the case under such conditions that at the moment of setting equality already took place. True of venjunction is caused by switching on the background . Logical indetermination is expressed by means of venjunction: . Venjunction and minimal (two-element) sequention are functionally identical:-
.
Realization
Venjunctor is a basic operational memory element of sequential logic. It is realized on the basis of equality, where formula represents a function of SR flip-flop. Sequentor is constructed on the basis of composition of venjunctors, which are connected in the definite way.For example, formulae
or are applicable for realizing sequention .Clocked sequential system
In digital electronics, a clocked sequential system is a system whose output depends only on the current stateState (computer science)
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
, whose state changes only when a global clock signal changes, and whose next-state depends only on the current state and the inputs.
Nearly all digital electronic devices (microprocessors, digital clock
Digital clock
A digital clock is a type of clock that displays the time digitally, i.e. in cyphers, as opposed to an analog clock, where the time is displayed by hands. Digital clocks are often associated with electronic drives, but the "digital" description refers only to the display, not to the drive mechanism...
s, mobile phone
Mobile phone
A mobile phone is a device which can make and receive telephone calls over a radio link whilst moving around a wide geographic area. It does so by connecting to a cellular network provided by a mobile network operator...
s, cordless telephone
Cordless telephone
A cordless telephone or portable telephone is a telephone with a wireless handset that communicates via radio waves with a base station connected to a fixed telephone line, usually within a limited range of its base station...
s, electronic calculator
Calculator
An electronic calculator is a small, portable, usually inexpensive electronic device used to perform the basic operations of arithmetic. Modern calculators are more portable than most computers, though most PDAs are comparable in size to handheld calculators.The first solid-state electronic...
s, etc.) are designed as clocked sequential systems.
Notable exceptions include digital asynchronous logic systems.
In particular, nearly all computers are designed as clocked sequential systems.
Notable exceptions include analog computer
Analog computer
An analog computer is a form of computer that uses the continuously-changeable aspects of physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved...
s and clockless CPUs.
Typically each bit of the "state" is contained in its own flip-flop
Flip-flop (electronics)
In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information. The circuit can be made to change state by signals applied to one or more control inputs and will have one or two outputs. It is the basic storage element in sequential logic...
.
Combinational logic
Combinational logic
In digital circuit theory, combinational 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 is in contrast to sequential logic, in which the output depends not only on the present input but also on the...
decodes the state into the output signals.
More combinational logic encodes the current state and the inputs into the next-state signals.
The next-state signals are latched into the flipflops under the control of the global clock signal (a wire connected to every flip-flop).
A clocked sequential system is a kind of Moore machine
Moore machine
In the theory of computation, a Moore machine is a finite-state machine, whose output values are determined solely by its current state.-Name:The Moore machine is named after Edward F...
.
See also
- Synchronous circuitSynchronous circuitA synchronous circuit is a digital circuit in which the parts are synchronized by a clock signal.In an ideal synchronous circuit, every change in the logical levels of its storage components is simultaneous. These transitions follow the level change of a special signal called the clock...
- Asynchronous circuitAsynchronous circuitAn asynchronous circuit is a circuit in which the parts are largely autonomous. They are not governed by a clock circuit or global clock signal, but instead need only wait for the signals that indicate completion of instructions and operations. These signals are specified by simple data transfer...
- Combinational logicCombinational logicIn digital circuit theory, combinational 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 is in contrast to sequential logic, in which the output depends not only on the present input but also on the...
- Logic design
- Asynchronous logic (algebra)Asynchronous logic (algebra)Asynchronous logic is a sort of symbiosis of combinational logic and sequential logic. In digital circuit theory asynchronous logic differs from synchronous one because its propositional variables act asynchronously without common clocked regulation and control...
- Application-specific integrated circuitApplication-specific integrated circuitAn application-specific integrated circuit is an integrated circuit customized for a particular use, rather than intended for general-purpose use. For example, a chip designed solely to run a cell phone is an ASIC...