Logic redundancy
Encyclopedia
Logic redundancy occurs in a digital gate
network containing circuitry that does not affect the static logic function. There are several reasons why logic redundancy may exist. One reason is that it may have been added deliberately to suppress transient glitches (thus causing a race condition
) in the output signals by having two or more product terms overlap with a third one.
Consider the following equation:
The third product term
is redundant. If 
switches from 1 to 0 while 
and 
, 
remains 1. During the transition of signal 
in logic gates, both the first and second term may be 0 momentarily. The third term prevents a glitch since its value of 1 in this case is not affected by the transition of signal 
.
Another reason for logic redundancy is poor design practices which unintentionally results in logically redundantly terms. This causes an unnecessary increase in network complexity, and possibly hampering the ability to test manufactured designs using traditional test methods (single stuck-at fault models). (Note: testing might be possible using IDDQ
models.)
Redundancy, by definition, requires extra parts (in this case: logical terms) which raises the cost of implementation (either actual cost of physical parts or CPU time
to process).
Logic redundancy can be removed by several well known techniques such as Karnaugh map
s, the Quine–McCluskey algorithm
, and the heuristic computer method
.
In some cases it may be desirable to add logic redundancy. One of those cases is to avoid race condition
s whereby an output can fluctuate because different terms are "racing" to turn off and on. To explain this in more concrete terms the Karnaugh map
to the right shows the minterms and maxterms for the following function:
The boxes represent the minimal AND/OR terms needed to implement this function:
The k-map visually shows where race condition
s occur in the minimal expression by having gaps between minterms or gaps between maxterms. For example, the gap between the blue and green rectangles. If the input
were to change to 
then a race will occur between 
turning off and 
turning off.
If the blue term switches off before the green turns on then the output will fluctuate and may register as 0.
Another race condition is between the blue and the red for transition of
to 
.
The race condition is removed by adding in logic redundancy, which is contrary to the aims of using a k-map in the first place.
Both minterm race conditions are covered by addition of the yellow term
.
(The maxterm race condition is covered by addition of the green-bordered grey term
.)
In this case, the addition of logic redundancy has stabilized the output to avoid output fluctuations because terms are racing each other to change state.
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 logic gate, one that has for instance zero rise time and...
network containing circuitry that does not affect the static logic function. There are several reasons why logic redundancy may exist. One reason is that it may have been added deliberately to suppress transient glitches (thus causing a race condition
Race condition
A race condition or race hazard is a flaw in an electronic system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events...
) in the output signals by having two or more product terms overlap with a third one.
Consider the following equation:
The third product term
is redundant. If switches from 1 to 0 while and , remains 1. During the transition of signal in logic gates, both the first and second term may be 0 momentarily. The third term prevents a glitch since its value of 1 in this case is not affected by the transition of signal .Another reason for logic redundancy is poor design practices which unintentionally results in logically redundantly terms. This causes an unnecessary increase in network complexity, and possibly hampering the ability to test manufactured designs using traditional test methods (single stuck-at fault models). (Note: testing might be possible using IDDQ
Iddq testing
Iddq testing is a method for testing CMOS integrated circuits for the presence of manufacturing faults. It relies on measuring the supply current in the quiescent state...
models.)
Removing logic redundancy
Logic redundancy is, in general, not desired.Redundancy, by definition, requires extra parts (in this case: logical terms) which raises the cost of implementation (either actual cost of physical parts or CPU time
CPU time
CPU time is the amount of time for which a central processing unit was used for processing instructions of a computer program, as opposed to, for example, waiting for input/output operations. The CPU time is often measured in clock ticks or as a percentage of the CPU's capacity...
to process).
Logic redundancy can be removed by several well known techniques such as Karnaugh map
Karnaugh map
The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...
s, the Quine–McCluskey algorithm
Quine–McCluskey algorithm
The Quine–McCluskey algorithm is a method used for minimization of boolean functions which was developed by W.V. Quine and Edward J. McCluskey...
, and the heuristic computer method
Espresso heuristic logic minimizer
The Espresso logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital electronic gate circuits. Espresso was developed at IBM by Robert Brayton. Rudell later published the variant Espresso-MV in 1986 under the title...
.
Adding logic redundancy
Race condition
A race condition or race hazard is a flaw in an electronic system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events...
s whereby an output can fluctuate because different terms are "racing" to turn off and on. To explain this in more concrete terms the Karnaugh map
Karnaugh map
The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...
to the right shows the minterms and maxterms for the following function:
The boxes represent the minimal AND/OR terms needed to implement this function:
The k-map visually shows where race condition
Race condition
A race condition or race hazard is a flaw in an electronic system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events...
s occur in the minimal expression by having gaps between minterms or gaps between maxterms. For example, the gap between the blue and green rectangles. If the input
were to change to then a race will occur between turning off and turning off.If the blue term switches off before the green turns on then the output will fluctuate and may register as 0.
Another race condition is between the blue and the red for transition of
to .Both minterm race conditions are covered by addition of the yellow term
.(The maxterm race condition is covered by addition of the green-bordered grey term
.)In this case, the addition of logic redundancy has stabilized the output to avoid output fluctuations because terms are racing each other to change state.