Sequential logic


Sequential logic

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 machines. 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 machine: 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 machine: 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.

Contents

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-flop.

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:

  1. 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.
  2. 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 (Latin: sequentia – sequence) is a sequence of propositional elements represented by the ordered set, for example \left\langle x\right\rangle = \left\langle x_1\,x_2\,\ldots\, x_\mathrm n\right\rangle, where x_i\in\left \{0,1\right \}. By means of sequention a binary function z=\varphi\left(\left\langle x\right\rangle\right) is realized so that \,z=1 takes place in the case \left(x_1\land x_2\land\,\ldots\, x_\mathrm n\right)=1, and under such conditions that \left(x_i=1\right)\prec\left(x_j=1\right) for all \mathrm{\,i<j}. (Sign \prec marks leading relation). Sequential function turns into unity at unity values of arguments, whose setting occurs consecutively, starting by \,x_1 and finishing with \,x_\mathrm n . All other cases give \,z=0.

Venjunction

Venjunction is asymmetrical logic/dynamic operation \angle, according to which logical connective x\,\angle\,y takes a unity value in the case x\,\land\,y=1 under such conditions that at the moment of \,x=1 setting equality \,y=1 already took place. True of venjunction is caused by switching \,x=0/1 on the background \,y=1. Logical indetermination is expressed by means of venjunction: 1\,\angle\,1. Venjunction and minimal (two-element) sequention are functionally identical:

x\,\angle\,y \ = \left \langle y\,x \right \rangle .

Realization

Venjunctor is a basic operational memory element of sequential logic. It is realized on the basis of equality x \land \left ( \bar{x} \lor x\,\angle\, y \right ) = x\,\angle\, y , where formula

\left ( \bar{x} \lor x\,\angle\, y \right ) 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 v\, \angle\, \left (u\, \angle\, \left (z\, \angle\, \left (y\, \angle\, x \right ) \right ) \right )    or    \left \langle x\,y \right \rangle \land \left \langle y\,z \right \rangle \land \left \langle z\,u \right \rangle \land \left \langle u\,v \right \rangle are applicable for realizing sequention \left \langle x\, y\, z\, u\, v \right \rangle .

Clocked sequential system

In digital electronics, a clocked sequential system is a system whose output depends only on the current state, 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 clocks, mobile phones, cordless telephones, electronic calculators, 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 computers 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.

See also

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • sequential logic — noun Said of a digital circuit block: that the current outputs depend not only on the current inputs, but also on a memory of past inputs and states. Ant: combinational logic …   Wiktionary

  • Logic optimization — a part of logic synthesis, is the process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. Generally the circuit is constrained to minimum chip area meeting a prespecified delay.… …   Wikipedia

  • Logic gate — A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal… …   Wikipedia

  • Logic design — In electronic design, logic design is a step in the standard design cycle in which the functional design of an electronic circuit is converted into the representation which captures logic operations, arithmetic operations, control flow, etc. A… …   Wikipedia

  • Logic programming — is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy s [1958] advice taker proposal, logic is used as a purely declarative… …   Wikipedia

  • Logic synthesis — is a process by which an abstract form of desired circuit behavior (typically register transfer level (RTL) or behavioral) is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDLs,… …   Wikipedia

  • Sequential function chart — (SFC) is a graphical programming language used for PLCs. It is one of the five languages defined by IEC 61131 3 standard. The SFC standard is defined in IEC 848, Preparation of function charts for control systems , and was based on GRAFCET.It can …   Wikipedia

  • Sequential manual transmission — A sequential manual transmission (or sequential manual gearbox) is a type of manual transmission used on motorcycles and high performance cars or auto racing, where gears are selected in order, and direct access to specific gears is not… …   Wikipedia

  • Combinational logic — Not to be confused with combinatory logic, a topic in mathematical logic. In digital circuit theory, combinational logic (sometimes also referred to as combinatorial logic) is a type of digital logic which is implemented by boolean circuits,… …   Wikipedia

  • Programmable logic device — A programmable logic device or PLD is an electronic component used to build reconfigurable digital circuits. Unlike a logic gate, which has a fixed function, a PLD has an undefined function at the time of manufacture. Before the PLD can be used… …   Wikipedia