- Details
- Published: Friday, 05 January 2018 18:47
- Hits: 618
Digital refers to high (power supply) and low (ground) signals. high is indicated by 1 and low by 0. Any circuit that is designed to operate on these high/low signals as inputs and generate high/low signals as outputs is referred as digital logic.
Using transistors, it's possible to design digital circuits which will compute AND, OR, XOR and many other complicated digital functions. Before getting into logic details, let's look at some basic digital concepts.
boolean algebra: A and B are digital (0 or 1)
AND = A.B
OR = A + B
NOT = ? = ~A
4 important logic reduction equations:
1. A + A.B = A => A.(1+B)=A
2. A + ?.B = A+B => A+A.B+?.B=A+(A+?).B=A+B
3. (A+B).(A+C) = A+B.C => A.A+A.C+A.B+B.C = A.(1+C+B)+B.C = A+B.C
4. (A+B).(?+C) = A.B + ?.C => A.?+B.?+A.C+B.C=
De Morgan's law: (can be extended to any number of variables, not limited to 2 variables)
1. ~(A+B+C+...X) = ~(A) . ~(B). ~(C). ... ~(X)
2. ~(A.B.C....X) = ~(A) + ~(B) + ~(C) + ... + ~(X)
Any logical eqn can be written as POS (product of Sum) or SOP (sum of product). SOP is referred as minterm while POS as maxterm.
SOP (AND-OR): F = x1.x2 + x3.x4
POS (OR-AND): F = (x1+x2).(x3+x4)
Shannon's expansion theorem: useful to compare logical equations
F(x1,x2,...,xn) = x1?.F(0,x2,...,xn) + x1.F(1,x2,....xn) = (x1?+F(1,x2,...,xn)).(x1+F(0,x2,...,xn))
Shannon's thm gives rise to canonical form: where there exists only form for each eqn. This is useful for comparing various eqn.
Minterm canonical representation: (SOP form)
F(x1,x2,...,xn) = F(0,0,...0).x1?.x2?...xn? + (It has 2^n minterms)
F(0,0,...1).x1?.x2?...xn +
........ +
F(1,1,...1).x1.x2...xn
Maxterm canonical representation: (POS form)
F(x1,x2,...,xn) = [F(0,0,...0) + x1 + x2 + ... + xn]. (It has 2^n maxterms)
[F(0,0,...1) + x1? + x2 + ... + xn].
........
[F(1,1,...1) + x1? + x2? + ... + xn?]
Digital basic blocks:
NAND gate: Y = ?(A.B)
NOR gate: Y = ?(A+B)
NOT gate: Y = ?A
NAND, NOR and NOT are called fundamental gates, as any logic function can be built using these 3 kinds of gates.
XOR gate: Y = A ? B
Adder: Adders are one of the fundamental logic blocks that are found in digital library along with other logic gates. Reason is because adders are used widely, so they are optimized and put in library
Half Adder (HA): adds 2 input bits and produces 2 outputs, Sum and Carry
S=A ? B
C=A.B
Full Adder (FA): adds 3 input bits and produces 2 outputs, Sum and Carry
S=A ? B ? Cin
C=A.B + Cin.(A+B)
optimizing logic functions:
There are combinatorial and sequential logic in any design. When we talk about optimizing design, it's means reducing the overall cost of design. Cost may be defined as area, speed, power, etc.
For any given logic function, firstly Truth tables are determined which describe what the output of a logic function is given it's input. These truth tables can be converted into equations with AND,OR etc implementing the functionality (i.e Y = A.B.C.D + ?.(C+E) + C.F). We can use logic reduction techniques (Karnaugh maps) to implement function using minimal logic. However K-maps are manual tools which are not very efficient for large logic equations. There are automated tools called synthesis tools, which produce such reduced logic. These tools determine prime implicant (PI) of the logic function, and then using Quine's Prime Implicant Therom, they select a subset of Prime Implicant that give minimal cost. If number of PI is very high, then heuristics are used to reduce run time. This may not give lowest cost, but are pretty close to being lowest cost solution for that function. Synthesis tool "Espresso" uses PI technique to optimize logic.
optimization of logic can be done by reducing eqn to 2 level logic either in SOP form (1st layer of AND gate followed by 2nd layer of OR gate) or in POS form (1st layer of OR gate followed by 2nd layer of AND gate). Although 2 level logic minimization is easy, but it may not give optimal cost, so multilevel logic minimization also done by tools.
ex: F = s.t.v+s.t.w.x+s.t.y.z+u.v+w.x+u.y.z => This is 2 level logic minimization. Can't be reduced any further in 2 levels. It uses 6 AND gates and 1 OR gate. However if factoring done, we get F = (s.t+u).(v+w.y+y.z) => This is 3 level logic minimization (since it has 3 levels = AND at 1st level, OR at 2nd level and AND at 3rd level). It uses 4 AND gates and 2 OR gate. So, it uses 1 less gate, and fanin of gates is also lower resulting in much smaller area, delay and power. However, we would not have arrived at this optimal solution if we confined ourselves to 2 level logic. This multilevel optimization is done via factoring (where prime divisors are found and boolean division done)
After optimizing combinatorial logic, we need to optimize sequential logic (flops, latches) too. However, there isn't much to optimize there as the number of flops is fixed by design requirement. The only place where flops can be optimized in in finite state machine (FSM). Synthesis tools optimize this by choosing lowest number of flops and gates to implement FSM.