Transcript Main presentation title goes here.

Combinatorial logic
with loops
4th November 2009
Denis A Nicole
A quick note of solidarity
Scientists should be on tap and not on top
Patrick Cormack MP (C South Staffordshire)
commenting in the House on Prof Nutt’s sacking
2
Some History
Suppose you live in a world in which positive logic (AND, OR) is cheap but
inverters (NOT) are very expensive.
It was once rather like that. You can make AND and OR gates out of diodes
but inverters need transistors:
OR
AND
NOT
3
You can make a diode
You just need a little fool’s gold
4
Transistors are harder
5
Some simple stuff
• Boolean functions take a vector of {0,1} inputs and return a vector of
outputs:
Y = f(X)
• There is an obvious partial order on the Boolean vectors
Y  X  i : Yi  X i
• Give-or take the availability of constants 0 and 1, we can clearly
implement any monotonic function with just AND and OR gates using
disjunctive normal form
Y1  X1 X 2 | X1 X 3 | X 4
• If we invert all inputs, we can easily generate any function
Y1  X1 X 2 | X1 X 3
6
Modern implementation
• Generic functions are implemented in
ROM.
• Fast, semi-structured, functions are
implemented in PLAs; The DNF is
created by programming the Xs in the
AND array to connect (or not) to the
horizontal OR inputs. The OR array is
fixed.
• Transistors are now very cheap.
• Wire is often not cheap.
7
What can go wrong?
Glitches
• In a real circuit, there are delays everywhere; much of the delay in a
modern system is in the wires. These delays can also be very different
for 0→1 and 1 → 0 transitions.
• In the “selector” circuit,
Y  X1 X 2 | X 1 X 3
What happens if X2 = 1, X3 = 1 when X1 makes a transition?
There might be a short 0 pulse on the output.
This might not matter; if the output is to be latched on a later clock
transition, we can ignore the glitch.
If, however, the circuit connected to Y is counting transitions,
something will go wrong.
• If necessary, we prevent glitches with additional terms:
Y  X1 X 2 | X1 X 3 | X 2 X 3
8
What can go wrong?
Fan-in, fan-out and depth
• In most logic families, gates are designed with a fixed number of inputs;
they can also drive only a bounded number of outputs.
• In all families, signal delay, which is usually an important performance
metric, increases with the number of gate layers through which the
signal flows.
• In modern CMOS, power consumption and RFI are roughly
proportional to both the number of gates which switch and their
switching frequency.
• Laying out the wires can be difficult if there is a complex topology;
these are embeddings into 2D which are very non-planar (requiring
many “vias” which increase cost and reduce reliability) or have poor
locality (delay from long wires).
9
Lets minimise NOTs
We’ll introduce a threshold gate:
the output is high if enough inputs are high. For example, a 7 input gate
with a threshold of 4 is just the OR of all 7!/(4!3!) permutations of four
ANDed inputs. A threshold gate is monotonic; it needs no inverters:
you could use 4-input AND gates and one big OR.
We can easily binary encode 7 inputs using three threshold gates and two
inverters
Markov, 1957
10
Minimising inverters
• Now we have the binary encoding, we can uniquely select
each term in the disjunction by ANDing the required
positive inputs and also ANDing the correct count. For
example, we can invert three inputs with two inverters:
11
12
So you only need two inverters
• The construction makes three inverters from two.
• Apply it recursively.
• You only need two inverters for any logic circuit.
• So optimising inverters is not, on its own, sensible.
13
Combinatorial logic with loops
What can go wrong?
• State: the output may depend on history
• Metastability: the output may take a long time in a nonlogic state, between 1 and 0.
• Oscillation: the output may make many transitions. Note
that the oscillation may be infinite, or may take place
within a glitch.
14
Modern work is by Marc Riedel
15
Invert two signals with one inverter?
16
Circuits with feedback
17
Halving total logic with feedback
Marc Riedel
18
Heritage
• AA Markov
• DA Huffman
• Best Caltech thesis 2004
19
A/D Converter
A/D Converter
Vin
D1 Vin
D1
GND
D4 GND
D4
Vref
Vref
Sign
Sign
ENB
ENB
20