Parts of tool flows are debugged by verifying the outputs of simulated logic against expected inputs. The test tools take computer files with sets of inputs and outputs, and highlight discrepancies between the simulated behavior and the expected behavior.
Once the input data is believed correct, the design itself must still be verified for correctness. Some tool flows verify designs by first producing a design, and then scanning the design to produce compatible input data for the tool flow. If the scanned data matches the input data, then the tool flow has probably not introduced errors.
The functional verification data are usually called test vectors. The functional test vectors may be preserved and used in the factory to test that newly constructed logic works correctly. However, functional test patterns dont discover common fabrication faults. Production tests are often designed by software tools called test pattern generators. These generate test vectors by examining the structure of the logic and systematically generating tests for particular faults. This way the fault coverage can closely approach 100%, provided the design is properly made testable see next section.Once a design exists, and is verified and testable, it often needs to be processed to be manufacturable as well. Modern integrated circuits have features smaller than the wavelength of the light used to expose the photoresist. Manufacturability software adds interference patterns to the exposure masks to eliminate opencircuits, and enhace the masks resolution and contrast.
A large logic machine say, with more than a hundred logical variables can have an astronomical number of possible states. Obviously, in the factory, testing every state is impractical if testing each state takes a microsecond, and there are more states than the number of microseconds since the universe began. Unfortunately, this ridiculoussounding case is typical.Fortunately, large logic machines are almost always designed as assemblies of smaller logic machines. To save time, the smaller submachines are isolated by permanentlyinstalled design for test circuitry, and are tested independently.
One common test scheme known as scan design moves test bits serially one after another from external test equipment through one or more serial shift registers known as scan chains. Serial scans have only one or two wires to carry the data, and minimize the physical size and expense of the infrequentlyused test logic.After all the test data bits are in place, the design is reconfigured to be in normal mode and one or more clock pulses are applied, to test for faults e.g. stuckat low or stuckat high and capture the test result into flipflops andor latches in the scan shift registers. Finally, the result of the test is shifted out to the block boundary and compared against the predicted good machine result.In a boardtest environment, serial to parallel testing has been formalized with a standard called JTAG named after the Joint Test Action Group that proposed it.Another common testing scheme provides a test mode that forces some part of the logic machine to enter a test cycle. The test cycle usually exercises large independent parts of the machine.
Several numbers determine the practicality of a system of digital logic. Engineers explored numerous electronic devices to get an ideal combination of fanout, speed, low cost and reliability.The cost of a logic gate is crucial. In the 1930s, the earliest digital logic systems were constructed from telephone relays because these were inexpensive and relatively reliable. After that, engineers always used the cheapest available electronic switches that could still fulfill the requirements.The earliest integrated circuits were a happy accident. They were constructed not to save money, but to save weight, and permit the Apollo Guidance Computer to control an inertial guidance system for a spacecraft. The first integrated circuit logic gates cost nearly $50 in 1960 dollars, when an engineer earned $10,000year. To everyones surprise, by the time the circuits were massproduced, they had become the leastexpensive method of constructing digital logic. Improvements in this technology have driven all subsequent improvements in cost.
With the rise of integrated circuits, reducing the absolute number of chips used represented another way to save costs. The goal of a designer is not just to make the simplest circuit, but to keep the component count down. Sometimes this results in slightly more complicated designs with respect to the underlying digital logic but nevertheless reduces the number of components, board size, and even power consumption.For example, in some logic families, NAND gates are the simplest digital gate to build. All other logical operations can be implemented by NAND gates. If a circuit already required a single NAND gate, and a single chip normally carried four NAND gates, then the remaining gates could be used to implement other logical operations like logical and. This could eliminate the need for a separate chip containing those different types of gates.
The reliability of a logic gate describes its mean time between failure MTBF. Digital machines often have millions of logic gates. Also, most digital machines are optimized to reduce their cost. The result is that often, the failure of a single logic gate will cause a digital machine to stop working.Digital machines first became useful when the MTBF for a switch got above a few hundred hours. Even so, many of these machines had complex, wellrehearsed repair procedures, and would be nonfunctional for hours because a tube burnedout, or a moth got stuck in a relay. Modern transistorized integrated circuit logic gates have MTBFs of nearly a trillion 1x10^12 hours, and need them because they have so many logic gates.
Fanout describes how many logic inputs can be controlled by a single logic output. The minimum practical fanout is about five. Modern electronic logic using CMOS transistors for switches have fanouts near fifty, and can sometimes go much higher.
The switching speed describes how many times per second an inverter an electronic representation of a logical not function can change from true to false and back. Faster logic can accomplish more operations in less time. Digital logic first became useful when switching speeds got above fifty hertz, because that was faster than a team of humans operating mechanical calculators. Modern electronic digital logic routinely switches at five gigahertz 5x109 hertz, and some laboratory systems switch at more than a terahertz 1x1012 hertz.
Design started with relays. Relay logic was relatively inexpensive and reliable, but slow. Occasionally a mechanical failure would occur. Most famously, a moth was caught in an early relay computer, and gave rise to the terms bug in the program, and Debugging. Fanouts were typically about ten, limited by the resistance of the coils and arcing on the contacts from high voltages.Later, vacuum tubes were used. These were very fast, but generated heat, and were unreliable because the filaments would burn out. Fanouts were typically five to seven, limited by the heating from the tubes current. In the 1950s, special computer tubes were developed with filaments that omitted volatile elements like silicon. These ran for hundreds of thousands of hours.
The first semiconductor logic family was Resistortransistor logic. This was a thousand times more reliable than tubes, ran cooler, and used less power, but had a very low fanin of three. Diodetransistor logic improved the fanout up to about seven, and reduced the power. Some DTL designs used two powersupplies with alternating layers of NPN and PNP transistors to increase the fanout.Transistor transistor logic TTL was a great improvement over these. In early devices, fanout improved to ten, and later variations reliably achieved twenty. TTL was also fast, with some variations achieving switching times as low as twenty nanoseconds. TTL is still used in some designs.Another contender was emitter coupled logic. This is very fast but uses a lot of power. Its now used mostly in radiofrequency circuits.Modern integrated circuits mostly use variations of CMOS, which is acceptably fast, very small and uses very little power. Fanouts of forty or more are possible, with some speed penalty.
It is possible to construct nonelectronic digital mechanisms. In principle, any technology capable of representing discrete states and representing logic operations could be used to build mechanical logic. Danny Hillis, coauthor of The Connection Machine, once built a working computer from Tinker toys, string, a brick, and a sharpened pencil, which is supposed to be in the Houston Museum of Natural Science.
Hydraulic, pneumatic and mechanical versions of logic gates exist and are used in situations where electricity cannot be used. The first two types are considered under the heading of fluidics. One application of fluidic logic is in military hardware that is likely to be exposed to a nuclear electromagnetic pulse nuclear EMP, or NEMP that would destroy electrical circuits.
Mechanical logic is frequently used in inexpensive controllers, such as those in washing machines. Famously, the first computer design, by Charles Babbage, was designed to use mechanical logic. Mechanical logic might also be used in very small computers that could be built by nanotechnology.Another example is that if two particular enzymes are required to prevent the construction of a particular protein, this is the equivalent of a biological NAND gate.The discovery of superconductivity has enabled the development of Rapid Single Flux Quantum RSFQ circuit technology, which uses Josephson junctions instead of transistors. Most recently, attempts are being made to construct purely optical computing systems capable of processing digital information using nonlinear optical elements.
Electronics Combinatorial logic Boolean algebra Fuzzy electronics Logic analyzer Logic gate Glitch Ringing Programmable logic device Reconfigurable system Register.
Boolean algebra or Boolean logic is a logical calculus of truth values, developed by George Boole in the late 1830s. It resembles the algebra of real numbers as taught in high school, but with the numeric operations of multiplication xy, addition x y, and negation x replaced by the respective logical operations of conjunction xy, disjunction xy, and complement ¬x. The Boolean operations are these and all other operations that can be built from these such xyz. These turn out to coincide with the set of all operations on the set 0,1 that take only finitely many arguments there are 22n such operations when there are n arguments.
The laws of Boolean algebra can be defined axiomatically as certain equations called axioms together with their logical consequences called theorems, or semantically as those equations that are true for every possible assignment of 0 or 1 to their variables. The axiomatic approach is sound and complete in the sense that it proves respectively neither more nor fewer laws than the semantic approach.Boolean algebra is the algebra of two values. These are usually taken to be 0 and 1, as we shall do here, although F and T, false and true, etc. are also in common use. For the purpose of understanding Boolean algebra any Boolean domain of two values will do.Regardless of nomenclature, the values are customarily thought of as essentially logical in character and are therefore referred to as truth values, in contrast to the natural numbers or the reals which are considered numerical values. On the other hand the algebra of the integers modulo 2, while ostensibly just as numeric as the integers themselves, was shown to constitute exactly Boolean algebra, originally by I.I. Zhegalkin in 1927 and rediscovered independently in the west by Marshall Stone in 1936. So in fact there is some ambiguity in the true nature of Boolean algebra it can be viewed as either logical or numeric in character.
More generally Boolean algebra is the algebra of values from any Boolean algebra as a model of the laws of Boolean algebra. For example the bit vectors of a given length, as with say 32bit computer words, can be combined with Boolean operations in the same way as individual bits, thereby forming a 232element Boolean algebra under those operations. Any such combination applies the same Boolean operation to all bits simultaneously. This passage from the Boolean algebra of 0 and 1 to these more general Boolean algebras is the Boolean counterpart of the passage from the algebra of the ring of integers to the algebra of commutative rings in general. The twoelement Boolean algebra is the prototypical Boolean algebra in the same sense as the ring of integers is the prototypical commutative ring. Boolean logic as the subject matter of this article is independent of the choice of Boolean algebra the same equations hold of every nontrivial Boolean algebra hence, there is no need here to consider any Boolean algebra other than the twoelement one. The article on Boolean algebra structure treats Boolean algebras themselves.
After values, the next ingredient of any algebraic system is its operations. Whereas elementary algebra is based on numeric operations multiplication xy, addition x y, and negation x, Boolean algebra is customarily based on logical counterparts to those operations, namely conjunction xy AND, disjunction xy OR, and complement or negation ¬x NOT. In electronics, the AND is represented as a multiplication, the OR is represented as an addition, and the NOT is represented with an overbar x y and x y, therefore, become xy and x y.Conjunction is the closest of these three to its numerical counterpart, in fact on 0 and 1 it is multiplication. As a logical operation the conjunction of two propositions is true when both propositions are true, and otherwise is false. The first column of Figure 1 below tabulates the values of xy for the four possible valuations for x and y such a tabulation is traditionally called a truth table.
Disjunction, in the second column of the figures, works almost like addition, with one exception the disjunction of 1 and 1 is neither 2 nor 0 but 1. Thus the disjunction of two propositions is false when both propositions are false, and otherwise is true. This is just the definition of conjunction with true and false interchanged everywhere because of this we say that disjunction is the dual of conjunction.
Logical negation however does not work like numerical negation at all. Instead it corresponds to incrementation ¬ x1 mod 2. Yet it shares in common with numerical negation the property that applying it twice returns the original value , just as x x. An operation with this property is called an involution. The set 0,1 has two permutations, both involutary, namely the identity, no movement, corresponding to numerical negation mod 2 since 1 1 mod 2, and SWAP, corresponding to logical negation. Using negation we can formalize the notion that conjunction is dual to disjunction via De Morgans laws, and . These can also be construed as definitions of conjunction in terms of disjunction and vice versa. Figure 2 shows the symbols used in digital electronics for conjunction and disjunction the input ports are on the left and the signals flow through to the output port on the right. Inverters negating the input signals on the way in, or the output signals on the way out, are represented as circles on the port to be inverted.
Other Boolean operations are derivable from these by composition. For example implication xy IMP, in the third column of the figures, is a binary operation which is false when x is true and y is false, and true otherwise. It can be expressed as xy ¬xy the ORgate of Figure 2 with the x input inverted, or equivalently ¬x¬y its De Morgan equivalent in Figure 3. In logic this operation is called material implication, to distinguish it from related but nonBoolean logical concepts such as entailment and relevant implication. The idea is that an implication xy is by default true the weaker truth value in the sense that false implies true but not vice versa unless its premise or antecedent x holds, in which case the truth of the implication is that of its conclusion or consequent y.
Although disjunction is not the exact counterpart of numerical addition, Boolean algebra nonetheless does have an exact counterpart, called exclusiveor XOR or parity, xy. As shown in the fourth column of the figures, the exclusiveor of two propositions is true just when exactly one of the propositions is true equivalently when an odd number of the propositions is true, whence the name parity. Exclusiveor is the operation of addition mod 2. The exclusiveor of any value with itself vanishes, xx 0, since the arguments have an even number of whatever value x has. Its digital electronics symbol is shown in Figure 2, being a hybrid of the disjunction symbol and the equality symbol. The latter reflects the fact that the negation which is also the dual of XOR, ¬xy, is logical equivalence, EQV, being true just when x and y are equal, either both true or both false. XOR and EQV are the only binary Boolean operations that are commutative and whose truth tables have equally many 0s and 1s. Exclusiveor together with conjunction constitute yet another complete basis for Boolean algebra, with the Boolean operations reformulated as the Zhegalkin polynomials.