UNIT I – BOOLEAN ALGEBRA AND COMBINATIONAL CIRCUITS
Boolean Variables & Truth Tables
Boolean algebra differs in a major way from ordinary algebra in that Boolean constants and variables are allowed to have only two possible values, 0 or 1.
Boolean 0 and 1 do not represent actual numbers but instead represent the state of a voltage variable, or what is called its logic level.
Boolean 0 and 1 do not represent actual numbers but instead represent the state of a voltage variable, or what is called its logic level.
Some common representation of 0 and 1 is shown in the following diagram.
In Boolean algebra, there are three basic logic operations: AND ,OR, and NOT.
These logic gates are digital circuits constructed from diodes, transistors, and resistors connected in such a way that the circuit output is the result of a basic logic operation (OR, AND, NOT) performed on the inputs.
These logic gates are digital circuits constructed from diodes, transistors, and resistors connected in such a way that the circuit output is the result of a basic logic operation (OR, AND, NOT) performed on the inputs.
Truth Table
A truth table is a means for describing how a logic circuit's output depends on the logic levels present at the circuit's inputs.
In the following twoinput logic circuit, the table lists all possible combinations of logic levels present at inputs A and B along with the corresponding output level X.
When either input A OR B is 1, the output X is 1. Therefore the "?" in the box is an OR gate.
OR Operation
The expression X = A + B reads as "X equals A OR B". The + sign stands for the OR operation, not for ordinary addition.
The OR operation produces a result of 1 when any of the input variable is 1.
The OR operation produces a result of 0 only when all the input variables are 0.
An example of three input OR gate and its truth table is as follows:
With the OR operation, 1 + 1 = 1, 1+ 1 + 1 = 1 and so on.
AND Operation
The expression X = A * B reads as "X equals A AND B".
The multiplication sign stands for the AND operation, same for ordinary multiplication of 1s and 0s.The AND operation produces a result of 1 occurs only for the single case when all of the input variables are 1.The output is 0 for any case where one or more inputs are 0
The multiplication sign stands for the AND operation, same for ordinary multiplication of 1s and 0s.The AND operation produces a result of 1 occurs only for the single case when all of the input variables are 1.The output is 0 for any case where one or more inputs are 0
An example of three input AND gate and its truth table is as follows:
With the AND operation, 1*1 = 1, 1*1*1 = 1 and so on.
NOT Operation
The NOT operation is unlike the OR and AND operations in that it can be performed on a single input variable. For example, if the variable A is subjected to the NOT operation, the result x can be expressed as x = A' where the prime (') represents the NOT operation. This expression is read as:
x equals NOT A
x equals the inverse of A
x equals the complement of A
x equals NOT A
x equals the inverse of A
x equals the complement of A
Each of these is in common usage and all indicate that the logic value of x = A' is o pposite to the logic value of A. The truth table of the NOT operation is as follows:
1'=0 because NOT 1 is 0
0' = 1 because NOT 0 is 1
0' = 1 because NOT 0 is 1
The NOT operation is also referred to as inversion or complementation, and these terms are used interchangeably.
NOR Operation
NOR and NAND gates are used extensively in digital circuitry. These gates combine the basic operations AND, OR and NOT, which make it relatively easy to describe then using Boolean algebra.
NOR gate symbol is the same as the OR gate symbol except that it has a small circle on the output. This small circle represents the inversion operation. Therefore the output expression of the two input NOR gate is:
X = (A + B)'
An example of three inputs OR gate can be constructed by a NOR gate plus a NOT gate:
NAND Operation
NAND gate symbol is the same as the AND gate symbol except that it has a small circle on the output. This small circle represents the inversion operation. Therefore the output expression of the two input NAND gate is:
X = (AB)'
Describing Logic Circuits Algebraically
Any logic circuit, no matter how complex, may be completely described using the Boolean operations, because the OR gate, AND gate, and NOT circuit are the basic building blocks of digital systems.
This is an example of the circuit using Boolean expression:
If an expression contains both AND and OR operations, the AND operations are performed first (X=AB+C: AB is performed first), unless there are parentheses in the expression, in which case the operation inside the parentheses is to be performed first (X= (A+B) +C: A+B is performed first).
Circuits containing Inverters
Whenever an INVERTER is present in a logiccircuit diagram, its output expression is simply equal to the input expression with a prime (') over it.
Evaluating Logic Circuit Outputs
Once the Boolean expression for a circuit output has been obtained, the output logic level can be determined for any set of input levels.
These are two examples of the evaluating logic circuit output:
Let A=0, B=1, C=1, D=1
X

= A'BC (A+D)'

= 0'*1*1* (0+1)'
 
= 1 *1*1* (1)'
 
= 1 *1*1* 0
 
= 0

Let A=0, B=0, C=1, D=1, E=1
X

= [D+ ((A+B)C)'] * E

= [1 + ((0+0)1 )'] * 1
 
= [1 + (0*1)'] * 1
 
= [1+ 0'] *1
 
= [1+ 1 ] * 1
 
= 1

In general, the following rules must always be followed when evaluating a Boolean expression:
1. First, perform all inversions of single terms; that is, 0 = 1 or 1 = 0.
2. Then perform all operations within parentheses.
3. Perform an AND operation before an OR operation unless parentheses indicate otherwise.
4. If an expression has a bar over it, perform the operations of the expression first and then invert the result.
1. First, perform all inversions of single terms; that is, 0 = 1 or 1 = 0.
2. Then perform all operations within parentheses.
3. Perform an AND operation before an OR operation unless parentheses indicate otherwise.
4. If an expression has a bar over it, perform the operations of the expression first and then invert the result.
Determining Output Level from a Diagram
The output logic level for given input levels can also be determined directly from the circuit diagram without using the Boolean expression.
Implementing Circuits from Boolean Expression
If the operation of a circuit is defined by a Boolean expression, a logiccircuit diagram can he implemented directly from that expression.
Suppose that we wanted to construct a circuit whose output is y = AC+BC' + A'BC. This Boolean expression contains three terms (AC, BC', A'BC), which are ORed together. This tells us that a threeinput OR gate is required with inputs that are equal to AC, BC', and A'BC, respectively.
Each ORgate input is an AND product term, which means that an AND gate with appropriate inputs can be used to generate each of these terms. Note the use of INVERTERs to produce the A' and C' terms required in the expression.
Boolean Theorems
Investigating the various Boolean theorems (rules) can help us to simplify logic expressions and logic circuits.
Multivariable Theorems
The theorems presented below involve more than one variable:
(9)

x + y = y + x (commutative law)

(10)

x * y = y * x (commutative law)

(11)

x+ (y+z) = (x+y) +z = x+y+z (associative law)

(12)

x (yz) = (xy) z = xyz (associative law)

(13a)

x (y+z) = xy + xz

(13b)

(w+x)(y+z) = wy + xy + wz + xz

(14)

x + xy = x [proof see below]

(15)

x + x'y = x + y

Proof of (14)
x + xy

= x (1+y)

= x * 1 [using theorem (6)]
 
= x [using theorem (2)]

DeMorgan's Theorem
DeMorgan's theorems are extremely useful in simplifying expressions in which a product or sum of variables is inverted. The two theorems are:
(16) (x+y)' = x' * y'
Theorem (16) says that when the OR sum of two variables is inverted, this is the same as inverting each variable individually and then ANDing these inverted variables.
(17) (x*y)' = x' + y'
Theorem (17) says that when the AND product of two variables is inverted, this is the same as inverting each variable individually and then ORing them.
Example
X

= [(A'+C) * (B+D')]'

= (A'+C)' + (B+D')' [by theorem (17)]
 
= (A''*C') + (B'+D'') [by theorem (16)]
 
= AC' + B'D

Three Variables DeMorgan's Theorem
(18) (x+y+z)' = x' * y' * z'
(19) (xyz)' = x' + y' + z'
Universality of NAND & NOR Gates
It is possible to implement any logic expression using only NAND gates and no other type of gate. This is because NAND gates, in the proper combination, can be used to perform each of the Boolean operations OR, AND, and INVERT.
In a similar manner, it can be shown that NOR gates can be arranged to implement any of the Boolean operations.
Alternate Logic Gate Representations
The left side of the illustration shows the standard symbol for each logic gate, and the right side shows the alternate symbol. The alternate symbol for each gate is obtained from the standard symbol by doing the following:
1. Invert each input and output of the standard symbol. This is done by adding bubbles (small circles) on input and output lines that do not have bubbles, and by removing bubbles that are already there.
2. Change the operation symbol from AND to OR, or from OR to AND. (In the special case of the INVERTER, the operation symbol is not changed.)
Several points should be stressed regarding the logic symbol equivalences:
1. The equivalences are valid for gates with any number of inputs.
2. None of the standard symbols have bubbles on their inputs, and all the alternate symbols do.
3. The standard and alternate symbols for each gate represent the same physical circuit: there is no difference in the circuits represented by the two symbols.
4. NAND and NOR gates are inverting gates, and so both the standard and alternate symbols for each will have a bubble on either the input or the output. AND and OR gates are noninverting gates, and so the alternate symbols for each will have bubbles on both inputs and output.
Concept of Active Logic Levels:
When an input or output line on a logic circuit symbol has no bubble on it, that line is said to be activeHIGH. When an input or output line does have a bubble on it, that line is said to be activeLOW. The presence or absence of a bubble, then, determines the activeHIGH/activeLOW status of a circuit's inputs and output, and is used to interpret the circuit operation.
Boolean Function
A Boolean function is an algebraic expression consists of binary variables, the
constants 0 & 1, and the Boolean operators.For a set of given values of the variables,
the function is evaluated to either 0 or 1
e.g. f = x • y + x • z'
The Boolean function f has 3 binaryvariables x, y and z
The function is 1 if x and y are both 1 or if x is 1 and z is 0. Otherwise, f = 0
Operator Precedence
The operator precedence is:
1. Parentheses
2. NOT
3. AND
4. OR
e.g. f = x • y + x • z'
Precedence: z', x • y, x • z', x • y + x • z'
e.g. f = (a +b) • (c+d')
Precedence: a+b, d', c+d', (a +b) • (c+d')
The parentheses precedence is the same as in normal algebra
Boolean Function Truth Table
Boolean function can be represented by truth table as well.If the function has n variables, its truth table will have 2^{n} rows
e.g. f = x • y + x • z'
f has 3 variables so 2^{3} combinations
f is 1 when the expression is evaluated to 1 otherwise it is 0.
Minterm
In a Boolean function, a binary variable (x) may appear either in its normal form (x) or in its complement form (x').Consider 2 binary variables x and y and an AND operation, there are 4 and only 4 possible combinations: x'•y', x'•y, x•y' & x•y
Each of the 4 product terms is called a MINTERM or STANDARD PRODUCT
By definition, a Minterm is a product which consists of all the variables in the normal form or the complement form but NOT BOTH.
e.g. for a function with 2 variables x and y:
x•y' is a minterm but x' is NOT a minterm
e.g. for a function with 3 variables x, y andz:
x'yz' is a minterm but xy' is NOT a minterm
Maxterm
Consider 2 binary variables x and y and an OR operation, there are 4 and only 4
possible combinations: x'+y', x'+y, x+y', x+y.Each of the 4 sum terms is called a
MAXTERM or STANDARD SUM.By definition, a Maxterm is a sum in which each variable appears once and only once either in its normal form or its complement
form but NOT BOTH.
Minterms and Maxterms for 3 Variables
Minterm Boolean Expression
Boolean functions can be expressed with minterms,
e.g.f1(x,y,z) = m1 + m4 + m6 = Î£m(1, 4, 6)
f2(x,y,z) = m2 + m4 + m6+ m7
= Î£m(2, 4, 6, 7)
Maxterm Boolean Expression
Boolean functions can also be expressed with maxterms,
e.g.f1' = x'y'z'+x'yz'+x'yz+xy'z+xyz
f1 = (x'y'z'+x'yz'+x'yz+xy'z+xyz)'
= (x+y+z)(x+y'+z)(x+y'+z')(x'+y+z')(x'+y'+z')
= M0•M2•M3•M5•M7
= Î M(0, 2, 3, 5, 7)
f2 = M0•M1•M3•M5
= Î M(0, 1, 3, 5)
Literal
A Literal is a variable in a product or sum term
xy' is a 2literal product term
x'yz has 3 literals
x' + xy' + x'yz is an expression of sum of products with 3 product terms.The 3 product terms have 1, 2 and 3 literals respectively
x'(x+y')(x'+y+z) is an expression of product of sums.The 3 sum terms have 1, 2 and 3 literals
Express Boolean Functions in Minterms
If product terms in a Boolean function are not minterms, they can be converted to minterms
e.g. f(a,b,c) = a' + bc' + ab'c
Function f has 3 variables, therefore, each minterm must have 3 literals
Neither a' nor bc' are minterms.They can be converted to minterm.ab'c is a minterm
Conversion to Minterms
e.g. f(a,b,c) = a' + bc' + ab'c
To convert a' to a minterm, the 2 variables (b, c) must be added, without changing its
functionality .Since a'=a'•1 & 1 = b+b', a'= a'(b + b') = a'b + a'b'
Similarly, a'b = a'b(c + c') = a'bc + a'bc' and a'b' = a'b'(c+c') = a'b'c + a'b'c'
bc' = bc'(a+a') = abc' + a'bc'
f = a'bc+a'bc'+a'b'c+a'b'c'+abc'+a'bc'+ab'c
Express Boolean Functions in Maxterms
By using the Distribution Law: x+yz = (x+y)(x+z), a Boolean function can
be converted to an expression in product of maxterms
e.g. f(a,b,c) = a'+bc'
= (a'+b)(a'+c') {not maxterms}
= (a'+b+cc')(a'+c'+bb') {cc'=0}
= (a'+b+c)(a'+b+c')(a'+c'+b)(a'+c'+b')
= (a'+b+c)(a'+b+c')(a'+c'+b')
Boolean Function Manipulation
Boolean functions can be manipulated with Boolean algebra.Manipulation can transform logic expressions, but still keep the same logic functionality.Manipulation can reduce the complexity, hence, easier to be implemented in hardware, i.e. fewer logic gates
Boolean Function Manipulation Example
f = xy' + xyz + x'z
= x(y' + yz) + x'z {common factor}
= x[(y'+y)(y'+z)] + x'z {Distribution law}
= x(y'+z) + x'z {y' + y = 1}
= xy' + xz + x'z {Distribution law}
= xy' + (x + x')z {common factor}
= xy' + z {x + x' = 1}
Simplify f1=abc+a'b+abc' and f2=(a+b)'(a'+b') to the minimum literals
f1 = abc+a'b+abc' = ab(c+c') + a'b = ab + a'b = (a+a')b = b
f2 =(a+b)'(a'+b') = a'b'(a'+b') {DeMorgan}
= a'b'a'+a'b'b'
= a'b' + a'b' = a'b'
QuineMcCluskey minimization method uses the same theorem to produce the solution as the Kmap method, namely X(Y+Y')=X
 The expression is represented in the canonical SOP form if not already in that form.
 The function is converted into numeric notation.
 The numbers are converted into binary form.
 The minterms are arranged in a column divided into groups.
 Begin with the minimization procedure.
 Each minterm of one group is compared with each minterm in the group immediately below.
 Each time a number is found in one group which is the same as a number in the group below except for one digit, the numbers pair is ticked and a new composite is created.
 This composite number has the same number of digits as the numbers in the pair except the digit different which is replaced by an "x".
 The above procedure is repeated on the second column to generate a third column.
 The next step is to identify the essential prime implicants, which can be done using a prime implicant chart.
 Where a prime implicant covers a minterm, the intersection of the corresponding row and column is marked with a cross.
 Those columns with only one cross identify the essential prime implicants. > These prime implicants must be in the final answer.
 The single crosses on a column are circled and all the crosses on the same row are also circled, indicating that these crosses are covered by the prime implicants selected.
 Once one cross on a column is circled, all the crosses on that column can be circled since the minterm is now covered.
 If any nonessential prime implicant has all its crosses circled, the prime implicant is redundant and need not be considered further.
 Next, a selection must be made from the remaining nonessential prime implicants, by considering how the noncircled crosses can be covered best.
 One generally would take those prime implicants which cover the greatest number of crosses on their row.
 If all the crosses in one row also occur on another row which includes further crosses, then the latter is said to dominate the former and can be selected.
 The dominated prime implicant can then be deleted.
Find the minimal sum of products for the Boolean expression,
f=(1,2,3,7,8,9,10,11,14,15), using QuineMcCluskey method.
Firstly these minterms are represented in the binary form as shown in the table below. The above binary representations are grouped into a number of sections in terms of the number of 1's as shown in the table below.
Binary representation of minterms
Minterms

U

V

W

X

1

0

0

0

1

2

0

0

1

0

3

0

0

1

1

7

0

1

1

1

8

1

0

0

0

9

1

0

0

1

10

1

0

1

0

11

1

0

1

1

14

1

1

1

0

15

1

1

1

1

Group of minterms for different number of 1's
No of 1's

Minterms

U

V

W

X

1

1

0

0

0

1

1

2

0

0

1

0

1

8

1

0

0

0

2

3

0

0

1

1

2

9

1

0

0

1

2

10

1

0

1

0

3

7

0

1

1

1

3

11

1

0

1

1

3

14

1

1

1

0

4

15

1

1

1

1

Any two numbers in these groups which differ from each other by only one variable can be chosen and combined, to get 2cell combination, as shown in the table below.
2Cell combinations
Combinations

U

V

W

X

(1,3)

0

0



1

(1,9)



0

0

1

(2,3)

0

0

1



(2,10)



0

1

0

(8,9)

1

0

0



(8,10)

1

0



0

(3,7)

0



1

1

(3,11)



0

1

1

(9,11)

1

0



1

(10,11)

1

0

1



(10,14)

1



1

0

(7,15)



1

1

1

(11,15)

1



1

1

(14,15)

1

1

1



From the 2cell combinations, one variable and dash in the same position can be combined to form 4cell combinations as shown in the figure below.
Combinations

U

V

W

X

(1,3,9,11)



0



1

(2,3,10,11)



0

1



(8,9,10,11)

1

0





(3,7,11,15)





1

1

(10,11,14,15)

1



1



The cells (1,3) and (9,11) form the same 4cell combination as the cells (1,9) and (3,11). The order in which the cells are placed in a combination does not have any effect. Thus the (1,3,9,11) combination could be written as (1,9,3,11).
From above 4cell combination table, the prime implicants table can be plotted as shown in table below.
Prime Implicants Table
Prime Implicants

1

2

3

7

8

9

10

11

14

15

(1,3,9,11)

X



X





X



X





(2,3,10,11)



X

X







X

X





(8,9,10,11)









X

X

X

X





(3,7,11,15)













X

X

X

X



X

X



X

X







X



The columns having only one cross mark correspond to essential prime implicants. A yellow cross is used against every essential prime implicant. The prime implicants sum gives the function in its minimal SOP form.
Y = V'X + V'W + UV' + WX + UW
Logic
Combinational logic blocks have the outputs depending on the combinations of the current inputs. Sequential logic blocks have the outputs depending on the current inputs as well as any previous inputs.
Binary Adder
Binary Adder is for binary number addition
Logic Circuit to be discussed:
§ Half Adder
§ Full Adder
§ Ripple Adder
§ Carry Look Ahead Adder
§
Half Adder
 Half adder is for addition of 2 single bits
 It has two 1bit inputs and two 1bit outputs
 The inputs are the 2 bits to be added (a, b)
 The outputs are 1bit sum (s) & 1bit carry (c)
The logic is:
Binary Addition
The half adder adds 2 singlebit inputs
It cannot complete a full addition
To complete a full addition, the adder needs to take in 3 inputs: a, b and the carry from the previous bit.
Full Adder
To carry the addition, an adder with 3 inputs is required. A Full Adder takes in 3 inputs (a, b and ci) and produces 2 outputs (s, co) a & b are the 2 bits to be added, ci is the carry input (carry over from the previous bit) and co is the carry output (to the next bit)
Logic for Full Adder
Logic equations derived from the truth table:
s = a Ã… b Ã… ci
co = ab + bci + aci
Full Adder
The below implementation shows implementing the full adder with ANDOR gates, instead of using XOR gates. The basis of the circuit below is from the above Kmap.
CircuitSUM
CircuitCARRY
Full adder can be built from 2 half adders
s = a Ã… b Ã… ci
co = ab+bci+aci
= ab+(a'bci+abci)+(abci+ab'ci)
= ab + abci + ci (a'b+ab') = ab + ci (a Ã… b)
nbit Ripple Adder
To perform an addition of 2 nbit numbers An1…A1A0 & Bn1…B1B0, where An1 & Bn1 are theMSB & A0B0 are the LSB, we need a nbit adder,which can be built from 'n 'fulladders
Ripple Adder: Carry ripples through the chain
CarryLookAhead Adder
The delay generated by an Nbit adder is proportional to the length N of the two numbers X and Y that are added because the carry signals have to propagate from one fulladder to the next. For large values of N, the delay becomes unacceptably large so that a special solution needs to be adopted to accelerate the calculation of the carry bits. This solution involves a "lookahead carry generator" which is a block that simultaneously calculates all the carry bits involved. Once these bits are available to the rest of the circuit, each individual threebit addition (X_{i}+Y_{i}+carryin_{i}) is implemented by a simple 3input XOR gate. The design of the lookahead carry generator involves two Boolean functions named Generate and Propagate. For each input bits pair these functions are defined as:
Gi = X_{i} . Y_{i}
Pi = X_{i} + Y_{i}
The carry bit cout(i) generated when adding two bits Xi and Yi is '1' if the corresponding function Gi is '1' or if the cout(i1)='1' and the function Pi = '1' simultaneously. In the first case, the carry bit is activated by the local conditions (the values of Xi and Yi). In the second, the carry bit is received from the less significant elementary addition and is propagated further to the more significant elementary addition. Therefore, the carry_out bit corresponding to a pair of bits Xi and Yi is calculated according to the equation:
carry_out(i) = Gi + Pi.carry_in(i1)
For a fourbit adder the carryouts are calculated as follows
carry_out0 = G_{0} + P_{0} . carry_in_{0}
carry_out1 = G_{1} + P_{1} . carry_out_{0} = G_{1} + P_{1}G_{0} + P_{1}P_{0} . carry_in_{0}
carry_out2 = G_{2} + P_{2}G_{1} + P_{2}P_{1}G_{0} + P_{2}P_{1}P_{0} . carry_in_{0}
carry_out3 = G_{3} + P_{3}G_{2} + P_{3}P_{2}G_{1} + P_{3}P_{2}P_{1}G_{0} + P_{3}P_{2}P_{1} . carry_in_{0}
The set of equations above are implemented by the circuit below and a complete adder with a lookahead carry generator is next. The input signals need to propagate through a maximum of 4 logic gate in such an adder as opposed to 8 and 12 logic gates in its counterparts illustrated earlier.
Pi is called Carry Propagate
Gi is called Carry Generate
With Pi and Gi, we obtain the sum & carry for the full adder:
Ci+1= Gi + PiCi
C1 = G0 + P0C0
C2 = G1 + P1C1
= G1 + P1(G0 + P0C0)
= G1 + P1G0 + P1P0C0
C3 = G2 + P2C2
= G2 + P2(G1 + P1G0 + P1P0C0)
= G2 + P2G1 + P2P1G0 + P2P1P0C0
Carry no longer depend on its previous stage
LookAhead Carry Generator
Speed: 2 gate delays for all carry
Cost: more gates
Sums can be calculated from the following equations, where carryout is taken from the carry calculated in the above circuit.
sum_out_{0} = X_{ 0} Y_{0} carry_out_{0}
sum_out_{1} = X_{ 1} Y_{1} carry_out_{1}
sum_out_{2} = X_{ 2} Y_{2} carry_out_{2}
sum_out_{3} = X_{ 3} Y_{3} carry_out_{3}
MSI Adder
Adders are available in Medium Scale Integration (MSI) devices
Both TTL and CMOS are available, e.g.
74183: TTL 1bit Full Adder
7482: TTL 4bit CarryLookAhead Adder
4008: CMOS 4bit CarryLookAhead Adder
74182: 4bit LookAhead Carry Generator
4bit Addition
To add 2 4bit numbers: Z = X + Y
8bit Addition
To add 2 8bit numbers: Z = X + Y
Subtractor
Subtractor circuits take two binary numbers as input and subtract one binary number input from the other binary number input. Similar to adders, it gives out two outputs, difference and borrow (carryin the case of Adder). There are two types of subtractors.
 Half Subtractor
 Full Subtractor
Half Subtractor
The halfsubtractor is a combinational circuit which is used to perform subtraction of two bits. It has two inputs, X (minuend) and Y (subtrahend) and two outputs D (difference) and B (borrow). The logic symbol and truth table are shown below.
Symbol
Truth Table
X

Y

D

B

0

0

0

0

0

1

1

1

1

0

1

0

1

1

0

0

From the above table we can draw the Kmap as shown below for "difference" and " borrow". The boolean expression for the difference and Borrow can be written.
From the equation we can draw the halfsubtractor as shown in the figure below.
Full Subtractor
A full subtractor is a combinational circuit that performs subtraction involving three bits, namely minuend, subtrahend, and borrowin. The logic symbol and truth table are shown below.
Symbol
Truth Table
X

Y

Bin

D

Bout

0

0

0

0

0

0

0

1

1

1

0

1

0

1

1

0

1

1

0

1

1

0

0

1

0

1

0

1

0

0

1

1

0

0

0

1

1

1

1

1

From above table we can draw the Kmap as shown below for "difference" and "borrow".
The boolean expression for difference and borrow can be written as
D = X'Y'Bin + X'YBin' + XY'Bin' + XYBin
= (X'Y' + XY)Bin + (X'Y + XY')Bin'
= (X Y)'Bin + (X Y)Bin'
= X Y Bin
Bout = X'.Y + X'.Bin + Y.Bin
From the equation we can draw the fullsubtractor as shown in figure below.
Fullsubtractor circuit is more or less same as a fulladder with slight modification.
Parallel Binary Subtractor
Parallel binary subtractor can be implemented by cascading several fullsubtractors. Implementation and associated problems are those of a parallel binary adder, seen before in parallel binary adder section.
Below is the block level representation of a 4bit parallel binary subtractor, which subtracts 4bit Y3Y2Y1Y0 from 4bit X3X2X1X0. It has 4bit difference output D3D2D1D0 with borrow output Bout.
A serial subtractor can be obtained by converting the serial adder using the 2's complement system. The subtrahend is stored in the Y register and must be 2's complemented before it is added to the minuend stored in the X register.
The circuit for a 4bit serial subtractor using fulladder is shown in the figure below.
Comparator
Comparator compares binary numbers.
Logic comparing 2 bits: a and b
Magnitude Comparator
Comparator compares binary numbers
4bit Magnitude Comparator:
Inputs: A3A2A1A0 & B3B2B1B0
Outputs: Y _{A>B}, Y _{A<B}, Y _{A=B}
For each bit, let:
Si = AiBi + Ai'Bi' = (AiBi' + Ai'Bi)'
Si is true when Ai = Bi
For A = B, we must have:
A3=B3 and A2=B2 and A1=B1 and A0=B0
Hence, Y _{A=B} = S3•S2•S1•S0 136
Logic For A > B
For A > B, there are 4 cases:
1. A_{3}B_{3} is 10 and A_{2}A_{1}A_{0 }& B_{2}B_{1}B_{0} can be anything:
A=1xxx, B=0xxx
2. A_{3}=B_{3 }and A_{2}B_{2} is 10 and A_{1}A_{0} & B_{1}B_{0} can be
anything: A=11xx, B=10xx or A=01xx, B=00xx
3. A_{3}=B_{3} and A_{2}=B_{2} and A_{1}B_{1}=10 and A_{0}B_{0} is xx: e.g.
A=011x, B=010x
4. A3=B3 and A2=B2 and A1=B1 and A0B0 is 10: e.g.
A=1011, B=1010
Y _{A>B}=A_{3}B_{3}'+S_{3}A_{2}B_{2}'+S_{3}S_{2}A_{1}B_{1}'+S_{3}S_{2}S_{1}A_{0}B_{0}'
Logic For A < B
For A < B, there are also 4 cases:
1) A_{3}B_{3 }is 01 and A_{2}A_{1}A_{0} & B_{2}B_{1}B_{0 }can be anything:
1. A=0xxx, B=1xxx
2) A_{3}=B_{3 }and A_{2}B_{2} is 01 and A_{1}A_{0} & B_{1}B_{0} can be
1. anything: A=10xx, B=11xx or A=00xx, B=01xx
3) A_{3}=B_{3} and A_{2}=B_{2} and A_{1}B_{1}=01 and A_{0}B_{0} is xx: e.g.
1. A=110x, B=111x
4) A3=B3 and A2=B2 and A1=B1 and A0B0 is 01: e.g.
1. A=1000, B=1001
Y _{A<B}=A_{3 }'B_{3}+S_{3}A_{2 }'B_{2}+S_{3}S_{2}A_{1 }' B_{1}+S_{3}S_{2}S_{1}A_{0 }' B_{0}
4bit Comparator Logic Circuit
MSI: 7485 4bit Magnitude Comparator
Comparison of 4bit Numbers
Comparison of 8  bit Numbers
Decoder
A decoder is a multipleinput, multipleoutput logic circuit that converts coded inputs into coded outputs, where the input and output codes are different.Binary Decoder has n inputs and 2^{n}outputs also called as nto2^{n} decoder. Inputs have all the 2^{n} combinations and the corresponding output will be activated for each input combinations.Decoding is necessary in applications such as data multiplexing, 7 segment display and memory address decoding. Enable inputs must be on for the decoder to function, otherwise its outputs assume a single "disabled" output code word. Figure below shows the pseudo block of a decoder.
A binary decoder has n inputs and 2^{n} outputs. Only one output is active at any one time, corresponding to the input value. Figure below shows a representation of Binary nto2^{n} decoder
e.g. 3to8 decoder has 3 inputs and 8 outputs
3to8 Decoder
Function Table
3to8 Decoder Logic Circuit
2to4 Decoder with Output Enable
Implement Logic Function with Decoder
 Any nvariable logic function, in canonical sumofminterms form can be implemented using a single nto2^{n} decoder to generate the minterms, and an OR gate to form the sum.
 The output lines of the decoder corresponding to the minterms of the function are used as inputs to the or gate.
 Any combinational circuit with n inputs and m outputs can be implemented with an nto2^{n} decoder with m OR gates.
Suitable when a circuit has many outputs, and each output function is expressed with few minterms.
(Ex) Full adder using decoder
S(x, y, z) = (1,2,4,7)
C(x, y, z) = (3,5,6,7)
Truth Table
X

Y

Z

C

S

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

0

0

0

1

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

From the truth table we know the values for which the sum (s) is active and also the carry (c) is active. Thus we have the equation as shown above and a circuit can be drawn as shown below from the equation derived.
Use a 3to8 decoder to implement:
f = x'y'z + xy'z + xyz
(m1 + m5 + m7)
MSI Decoders
 2to4 Decoder
 3to8 Decoder
 4to16 Decoder
 BCDtoDecimal Decoder
 BCDtoSevenSegment Decoder
e.g. Low Power Schottky TTL:
74LS138 3to8 Decoder where G1, G2A and G2B are enable pins
Logic Symbol
74LS138 3to8 Decoder
Implement Logic Function with74LS138
Use a 3to8 decoder to implement:
f = x'y'z + xy'z + xyz
(m1 + m5 + m7)
4to16 Decoder
Use 2 3to8 decoders
Inputs: D, C, B, A
Outputs: Y0 – Y15
When D = 0, top decoder is enabled
When D = 1,bottom decoderis enabled
En' is enable
Binary Encoders
An encoder is a combinational circuit that performs the inverse operation of a decoder. If a device output code has fewer bits than the input code has, the device is usually called an encoder. e.g. 2^{n}ton, priority encoders.
The simplest encoder is a 2^{n}ton binary encoder, where it has only one of 2^{n} inputs = 1 and the output is the nbit binary number corresponding to the active input. It can be built from OR gates
e.g. 4to2 Encoder
OctaltoBinary Encoder
OctaltoBinary take 8 inputs and provides 3 outputs, thus doing the opposite of what the 3to8 decoder does. At any one time, only one input line has a value of 1. The figure below shows the truth table of an Octaltobinary encoder.
Truth Table
I0

I1

I2

I3

I4

I5

I6

I7

Y2

Y1

Y0

1

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

1

0

0

1

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

1

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

0

1

0

0

1

0

1

0

0

0

0

0

0

1

0

1

1

0

0

0

0

0

0

0

0

1

1

1

1

For an 8to3 binary encoder with inputs I0I7 the logic expressions of the outputs Y0Y2 are:
Y0 = I1 + I3 + I5 + I7
Y1= I2 + I3 + I6 + I7
Y2 = I4 + I5 + I6 +I7
Based on the above equations, we can draw the circuit as shown below
Priority Encoder
If more then two inputs are active simultaneously, the output is unpredictable or rather it is not what we expect it to be.This ambiguity is resolved if priority is established so that only one input is encoded, no matter how many inputs are active at a given point of time. The priority encoder includes a priority function. The operation of the priority encoder is such that if two or more inputs are active at the same time, the input having the highest priority will take precedence.
e.g. 4to2 PriorityEncoder
A3 has the highest priority
A0 has the lower priority
74148 8to3 Priority Encoder
16to4 Priority Encoder
Cascade two 74148 8to3 priority encoders. The Input 15 has highest priority
Multiplexer
A multiplexer (MUX) is a digital switch which connects data from one of n sources to the output. A number of select inputs determine which data source is connected to the output. The block diagram of MUX with n data sources of b bits wide and s bits wide select line is shown in below figure.
MUX acts like a digitally controlled multiposition switch where the binary code applied to the select inputs controls the input source that will be switched on to the output as shown in the figure below. At any given point of time only one input gets selected and is connected to output, based on the select input signal.
The operation of a multiplexer can be better explained using a mechanical switch as shown in the figure below. This rotary switch can touch any of the inputs, which is connected to the output. As you can see at any given point of time only one input gets transferred to output.
2x1 MUX
A 2 to 1 line multiplexer is shown in figure below, each 2 input lines A to B is applied to one input of an AND gate. Selection lines S are decoded to select a particular AND gate. The truth table for the 2:1 mux is given in the table below.
Design of a 2:1 Mux
To derive the gate level implementation of 2:1 mux we need to have truth table as s hown in figure. And once we have the truth table, we can draw the Kmap as shown in figure for all the cases when Y is equal to '1'.
Combining the two 1' as shown in figure, we can drive the output y as shown below
Y = A.S' + B.S
Truth Table
B

A

S

Y

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

0

1

0

1

1

1

0

1
 
1

1

1

1

Kmap
Circuit
MSI MUX
74150: 16to1
74153: Dual 4to1
74157: Quad 2to1
74151: 8to1
16to1 MUX
Use two 74151
D = 0 enables top MUX
D = 1 enables bottom MUX
W = Y'
= (Y1+Y2)'
= (W1'+W2')'
= W1W2
Larger multiplexers can be constructed from smaller ones. An 8to1 multiplexer can be constructed from smaller multiplexers as shown below.
8to1 multiplexer from Smaller MUX
16to1 multiplexer from 4:1 mux
Quadruple 2to1 MUX
It is 2to1 MUX with 4 bits for each input
There is 1 output of 4 bits
There is 1 select signal
When 1 input is selected, the whole group of 4 bits goes to the output
Quad 2to1 MUX
Any nvariable logic function can be implemented using a smaller 2^{n1}to1 multiplexer and a single inverter (e.g 4to1 mux to implement 3 variable functions) as follows.
Express function in canonical sumofminterms form. Choose n1 variables as inputs to mux select lines. Construct the truth table for the function, but grouping inputs by selection line values (i.e select lines as most significant inputs).
Determine multiplexer input line i values by comparing the remaining input variable and the function F for the corresponding selection lines value i.
We have four possible mux input line i values:
· Connect to 0 if the function is 0 for both values of remaining variable.
· Connect to 1 if the function is 1 for both values of remaining variable.
· Connect to remaining variable if function is equal to the remaining variable.
· Connect to the inverted remaining variable if the function is equal to the remaining variable inverted
3variable Function Using 8to1 mux
Implement the function F(X,Y,Z) = S(1,3,5,6) using an 8to1 mux. Connect the input variables X, Y, Z to mux select lines. Mux data input lines 1, 3, 5, 6 that correspond to the function minterms are connected to 1. The remaining mux data input lines 0, 2, 4, 7 are connected to 0.
3variable Function Using 4to1 mux
Implement the function F(X,Y,Z) = S(0,1,3,6) using a single 4to1 mux and an inverter. We choose the two most significant inputs X, Y as mux select lines.
Truth Table
Select i

X

Y

Z

F

Mux Input i
 
0

0

0

0

1

1
 
0

0

0

1

1

1
 
1

0

1

0

0

Z
 
1

0

1

1

1

Z
 
2

1

0

0

0

0
 
2

1

0

1

0

0
 
3

1

1

0

1

Z'
 
3

1

1

1

0

Z'
 
We determine multiplexer input line i values by comparing the remaining input variable Z and the function F for the corresponding selection lines value i
· when XY=00 the function F is 1 (for both Z=0, Z=1) thus mux input0 = 1
· when XY=01 the function F is Z thus mux input1 = Z
· when XY=10 the function F is 0 (for both Z=0, Z=1) thus mux input2 = 0
· when XY=11 the function F is Z' thus mux input3 = Z'
Example for logic function implementation using MUX
Demultiplexers
They are digital switches which connect data from one input source to one of n outputs.Usually implemented by using nto2^{n} binary decoders where the decoder enable line is used for data input of the demultiplexer.The figure below shows a demultiplexer block diagram which has got sbitswide select input, one bbitswide data input and n bbitswide outputs.
The operation of a demultiplexer can be better explained using a mechanical switch as shown in the figure below. This rotary switch can touch any of the outputs, which is connected to the input. As you can see at any given point of time only one output gets connected to input.
1to4 Demultiplexer
Truth Table

UNIT II – SYNCHRONOUS SEQUENTIAL CIRCUIT
Introduction
Combinational logic refers to circuits whose output is strictly depended on the present value of the inputs. As soon as inputs are changed, the information about the previous inputs is lost, that is, combinational logics circuits have no memory. In many applications, information regarding input values at a certain instant of time is required at some future time. Although every digital system is likely to have combinational circuits, most systems encountered in practice also include memory elements, which require that the system be described in terms of sequential logic. Circuits whose outputs depends not only on the present input value but also the past input value are known as sequential logic circuits. The mathematical model of a sequential circuit is usually referred to as a sequential machine.
A general block diagram of a sequential circuit is shown below in Figure 1.
Figure 1. Block Diagram of Sequential Circuit.
The diagram consists of combinational circuit to which memory elements are connected to form a feedback path. The memory elements are devices capable of storing binary information within them. The combinational part of the circuit receives two sets of input signals: one is primary (coming from the circuit environment) and secondary (coming from memory elements). The particular combination of secondary input variables at a given time is called the present state of the circuit. The secondary input variables are also know as the state variables.
The block diagram shows that the external outputs in a sequential circuit are a function not only of external inputs but also of the present state of the memory elements. The next state of the memory elements is also a function of external inputs and the present state. Thus a sequential circuit is specified by a time sequence of inputs, outputs, and internal states.
Synchronous and Asynchronous Operation
Sequential circuits are divided into two main types: synchronous and asynchronous. Their classification depends on the timing of their signals.
Synchronous sequential circuits change their states and output values at discrete instants of time, which are specified by the rising and falling edge of a freerunning clock signal. The clock signal is generally some form of square wave as shown in Figure 2 below.
Figure 2. Clock Signal
From the diagram you can see that the clock period is the time between successive transitions in the same direction, that is, between two rising or two falling edges. State transitions in synchronous sequential circuits are made to take place at times when the clock is making a transition from 0 to 1 (rising edge) or from 1 to 0 (falling edge). Between successive clock pulses there is no change in the information stored in memory.
The reciprocal of the clock period is referred to as the clock frequency. The clock width is defined as the time during which the value of the clock signal is equal to 1. The ratio of the clock width and clock period is referred to as the duty cycle. A clock signal is said to be active high if the state changes occur at the clock's rising edge or during the clock width. Otherwise, the clock is said to be active low. Synchronous sequential circuits are also known as clocked sequential circuits.
The memory elements used in synchronous sequential circuits are usually flipflops. These circuits are binary cells capable of storing one bit of information. A flipflop circuit has two outputs, one for the normal value and one for the complement value of the bit stored in it. Binary information can enter a flipflop in a variety of ways, a fact which give rise to the different types of flipflops. For information on the different types of basic flipflop circuits and their logical properties, see the previous tutorial on flipflops.
In asynchronous sequential circuits, the transition from one state to another is initiated by the change in the primary inputs; there is no external synchronisation. The memory commonly used in asynchronous sequential circuits are timedelayed devices, usually implemented by feedback among logic gates. Thus, asynchronous sequential circuits may be regarded as combinational circuits with feedback. Because of the feedback among logic gates, asynchronous sequential circuits may, at times, become unstable due to transient conditions. The instability problem imposes many difficulties on the designer. Hence, they are not as commonly used as synchronous systems.
Summary of the Types of Flipflop Behaviour
Since memory elements in sequential circuits are usually flipflops, it is worth summarising the behaviour of various flipflop types before proceeding further.
All flipflops can be divided into four basic types: SR, JK, D and T. They differ in the number of inputs and in the response invoked by different value of input signals. The four types of flipflops are defined in Table 1.
Table 1. Flipflop Types
FLIPFLOP NAME

FLIPFLOP SYMBOL

CHARACTERISTIC TABLE

CHARACTERISTIC EQUATION

EXCITATION TABLE
 
SR


Q(next) = S + R'Q
SR = 0

 
JK


Q(next) = JQ' + K'Q

 
D


Q(next) = D

 
T


Q(next) = TQ' + T'Q


Each of these flipflops can be uniquely described by its graphical symbol, its characteristic table, its characteristic equation or excitation table. All flipflops have output signals Q and Q'.
The characteristic table in the third column of Table 1 defines the state of each flipflop as a function of its inputs and previous state. Q refers to the present state and Q(next) refers to the next state after the occurrence of the clock pulse. The characteristic table for the RS flipflop shows that the next state is equal to the present state when both inputs S and R are equal to 0. When R=1, the next clock pulse clears the flipflop. When S=1, the flipflop output Q is set to 1. The equation mark (?) for the next state when S and R are both equal to 1 designates an indeterminate next state.
The characteristic table for the JK flipflop is the same as that of the RS when J and K are replaced by S and R respectively, except for the indeterminate case. When both J and K are equal to 1, the next state is equal to the complement of the present state, that is, Q(next) = Q'.
The next state of the D flipflop is completely dependent on the input D and independent of the present state.
The next state for the T flipflop is the same as the present state Q if T=0 and complemented if T=1.
The characteristic table is useful during the analysis of sequential circuits when the value of flipflop inputs are known and we want to find the value of the flipflop output Q after the rising edge of the clock signal. As with any other truth table, we can use the map method to derive the characteristic equation for each flipflop, which are shown in the third column of Table 1.
During the design process we usually know the transition from present state to the next state and wish to find the flipflop input conditions that will cause the required transition. For this reason we will need a table that lists the required inputs for a given change of state. Such a list is called the excitation table, which is shown in the fourth column of Table 1. There are four possible transitions from present state to the next state. The required input conditions are derived from the information available in the characteristic table. The symbol X in the table represents a "don't care" condition, that is, it does not matter whether the input is 1 or 0.
State Tables and State Diagrams
We have examined a general model for sequential circuits. In this model the effect of all previous inputs on the outputs is represented by a state of the circuit. Thus, the output of the circuit at any time depends upon its current state and the input. These also determine the next state of the circuit. The relationship that exists among the inputs, outputs, present states and next states can be specified by either the state table or the state diagram.
State Table
The state table representation of a sequential circuit consists of three sections labelled present state, next state and output. The present state designates the state of flipflops before the occurrence of a clock pulse. The next state shows the states of flipflops after the clock pulse, and the output section lists the value of the output variables during the present state.
State Diagram
In addition to graphical symbols, tables or equations, flipflops can also be represented graphically by a state diagram. In this diagram, a state is represented by a circle, and the transition between states is indicated by directed lines (or arcs) connecting the circles. An example of a state diagram is shown in Figure 3 below.
Figure 3. State Diagram
The binary number inside each circle identifies the state the circle represents. The directed lines are labelled with two binary numbers separated by a slash (/). The input value that causes the state transition is labelled first. The number after the slash symbol / gives the value of the output. For example, the directed line from state 00 to 01 is labelled 1/0, meaning that, if the sequential circuit is in a present state and the input is 1, then the next state is 01 and the output is 0. If it is in a present state 00 and the input is 0, it will remain in that state. A directed line connecting a circle with itself indicates that no change of state occurs. The state diagram provides exactly the same information as the state table and is obtained directly from the state table.
Example: This example is taken from P. K. Lala, Practical Digital Logic Design and Testing, Prentice Hall, 1996, p.155.
Consider a sequential circuit shown in Figure 4. It has one input x, one output Z and two state variables Q1Q2 (thus having four possible present states 00, 01, 10, 11).
Figure 4. A Sequential Circuit
The behaviour of the circuit is determined by the following Boolean expressions:
Z = x*Q1

D1 = x' + Q1

D2 = x*Q2' + x'*Q1'

These equations can be used to form the state table. Suppose the present state (i.e. Q1Q2) = 00 and input x = 0. Under these conditions, we get Z = 0, D1 = 1, and D2 = 1. Thus the next state of the circuit D1D2 = 11, and this will be the present state after the clock pulse has been applied. The output of the circuit corresponding to the present state Q1Q2 = 00 and x = 1 is Z = 0. This data is entered into the state table as shown in Table 2.
Present State

Next State

Output
 



Table 2. State table for the sequential circuit in Figure 4.
The state diagram for the sequential circuit in Figure 4 is shown in Figure 5.
Figure 5. State Diagram of circuit in Figure 4.
State Diagrams of Various Flipflops
Table 3 shows the state diagrams of the four types of flipflops.
NAME

STATE DIAGRAM

SR
 
JK
 
D
 
T

All four flipflops have the same number of states and transitions. Each flipflop is in the set state when Q=1 and in the reset state when Q=0. Also, each flipflop can move from one state to another, or it can reenter the same state. The only difference between the four types lies in the values of input signals that cause these transitions.
A state diagram is a very convenient way to visualise the operation of a flipflop or even of large sequential components.
Analysis of Sequential Circuits
The behaviour of a sequential circuit is determined from the inputs, the outputs and the states of its flipflops. Both the output and the next state are a function of the inputs and the present state.
The suggested analysis procedure of a sequential circuit is set out in Figure 6 below.
Figure 6. Analysis procedure of sequential circuits.
We start with the logic schematic from which we can derive excitation equations for each flipflop input. Then, to obtain nextstate equations, we insert the excitation equations into the characteristic equations. The output equations can be derived from the schematic, and once we have our output and nextstate equations, we can generate the nextstate and output tables as well as state diagrams. When we reach this stage, we use either the table or the state diagram to develop a timing diagram which can be verified through simulation.
This example is taken from D. D. Gajski, Principles of Digital Design, Prentice Hall, 1997, p.230.
Example 1.1. Modulo4 counter
Derive the state table and state diagram for the sequential circuit shown in Figure 7.
Figure 7. Logic schematic of a sequential circuit.

SOLUTION:
STEP 1: First we derive the Boolean expressions for the inputs of each flipflops in the schematic, in terms of external input Cnt and the flipflop outputs Q1 and Q0. Since there are two D flipflops in this example, we derive two expressions for D1 and D0:
D0 = CntQ0 = Cnt'*Q0 + Cnt*Q0'

D1 = Cnt'*Q1 + Cnt*Q1'*Q0 + Cnt*Q1*Q0'

These Boolean expressions are called excitation equations since they represent the inputs to the flipflops of the sequential circuit in the next clock cycle.
STEP 2: Derive the nextstate equations by converting these excitation equations into flipflop characteristic equations. In the case of D flipflops, Q(next) = D. Therefore the next state equal the excitation equations.
Q0(next) = D0 = Cnt'*Q0 + Cnt*Q0'

Q1(next) = D1 = Cnt'*Q1 + Cnt*Q1'*Q0 + Cnt*Q1*Q0'

STEP 3: Now convert these nextstate equations into tabular form called the nextstate table.
Present State

Next State
 


Each row is corresponding to a state of the sequential circuit and each column represents one set of input values. Since we have two flipflops, the number of possible states is four  that is, Q1Q0 can be equal to 00, 01, 10, or 11. These are present states as shown in the table.
For the next state part of the table, each entry defines the value of the sequential circuit in the next clock cycle after the rising edge of the Clk. Since this value depends on the present state and the value of the input signals, the next state table will contain one column for each assignment of binary values to the input signals. In this example, since there is only one input signal, Cnt, the nextstate table shown has only two columns, corresponding to Cnt = 0 and Cnt = 1.
Note that each entry in the nextstate table indicates the values of the flipflops in the next state if their value in the present state is in the row header and the input values in the column header.
Each of these nextstate values has been computed from the nextstate equations in STEP 2.
STEP 4: The state diagram is generated directly from the nextstate table, shown in Figure 8.
Figure 8. State diagram
Each arc is labelled with the values of the input signals that cause the transition from the present state (the source of the arc) to the next state (the destination of the arc).
In general, the number of states in a nextstate table or a state diagram will equal 2^{m }, where m is the number of flipflops. Similarly, the number of arcs will equal 2^{m }x 2^{k} , where k is the number of binary input signals. Therefore, in the state diagram, there must be four states and eight transitions. Following these transition arcs, we can see that as long as Cnt = 1, the sequential circuit goes through the states in the following sequence: 0, 1, 2, 3, 0, 1, 2,.... On the other hand, when Cnt = 0, the circuit stays in its present state until Cnt changes to 1, at which the counting continues.
Since this sequence is characteristic of modulo4 counting, we can conclude that the sequential circuit in Figure 7 is a modulo4 counter with one control signal, Cnt, which enables counting when Cnt = 1 and disables it when Cnt = 0.
Below, we show a timing diagram, representing four clock cycles, which enables us to observe the behaviour of the counter in greater detail.
Figure 9. Timing Diagram

In this timing diagram we have assumed that Cnt is asserted in clock cycle 0 at t_{0} and is disasserted in clock cycle 3 at time t_{4}. We have also assumed that the counter is in state Q1Q0 = 00 in the clock cycle 0. Note that on the clock's rising edge, at t_{1}, the counter will go to state Q1Q0 = 01 with a slight propagation delay; in cycle 2, after t_{2}, to Q1Q0 = 10; and in cycle 3, after t_{3} to Q1Q0 = 11. Since Cnt becomes 0 at t_{4}, we know that the counter will stay in state Q1Q0 = 11 in the next clock cycle.
In Example 1.1 we demonstrated the analysis of a sequential circuit that has no outputs by developing a nextstate table and state diagram which describes only the states and the transitions from one state to the next. In the next example we complicate our analysis by adding output signals, which means that we have to upgrade the nextstate table and the state diagram to identify the value of output signals in each state.
This example is taken from D. D. Gajski, Principles of Digital Design, Prentice Hall, 1997, p.234.
Example 1.2
Derive the next state, the output table and the state diagram for the sequential circuit shown in Figure 10.
Figure 10. Logic schematic of a sequential circuit.
SOLUTION:
The input combinational logic in Figure 10 is the same as in Example 1.1, so the excitation and the nextstate equations will be the same as in Example 1.1.
Excitation equations:
D0 = CntQ0 = Cnt'*Q0 + Cnt*Q0'

D0 = Cnt'*Q1 + Cnt*Q1'*Q0 + Cnt*Q1*Q0'

Nextstate equations:
Q0(next) = D0 = Cnt'*Q0 + Cnt*Q0'

Q1(next) = D0 = Cnt'*Q1 + Cnt*Q1'*Q0 + Cnt*Q1*Q0'

In addition, however, we have computed the output equation.
Output equation: Y = Q1Q0
As this equation shows, the output Y will equal to 1 when the counter is in state Q1Q0 = 11, and it will stay 1 as long as the counter stays in that state.
Nextstate and output table:
Present State

Next State

Output
 



State diagram:
Figure 11. State diagram of sequential circuit in Figure 10.
Timing diagram:
Figure 12. Timing diagram of sequential circuit in Figure 10.
Note that the counter will reach the state Q1Q0 = 11 only in the third clock cycle, so the output Y will equal 1 after Q0 changes to 1. Since counting is disabled in the third clock cycle, the counter will stay in the state Q1Q0 = 11 and Y will stay asserted in all succeeding clock cycles until counting is enabled again.
Design of Sequential Circuits
The design of a synchronous sequential circuit starts from a set of specifications and culminates in a logic diagram or a list of Boolean functions from which a logic diagram can be obtained. In contrast to a combinational logic, which is fully specified by a truth table, a sequential circuit requires a state table for its specification. The first step in the design of sequential circuits is to obtain a state table or an equivalence representation, such as a state diagram.
A synchronous sequential circuit is made up of flipflops and combinational gates. The design of the circuit consists of choosing the flipflops and then finding the combinational structure which, together with the flipflops, produces a circuit that fulfils the required specifications. The number of flipflops is determined from the number of states needed in the circuit.
The recommended steps for the design of sequential circuits are set out below.
.State Reduction
Any design process must consider the problem of minimising the cost of the final circuit. The two most obvious cost reductions are reductions in the number of flipflops and the number of gates.
The number of states in a sequential circuit is closely related to the complexity of the resulting circuit. It is therefore desirable to know when two or more states are equivalent in all aspects. The process of eliminating the equivalent or redundant states from a state table/diagram is known as state reduction.
Example: Let us consider the state table of a sequential circuit shown in Table 6.
Table 6. State table
Present State

Next State

Output
 



It can be seen from the table that the present state A and F both have the same next states, B (when x=0) and C (when x=1). They also produce the same output 1 (when x=0) and 0 (when x=1). Therefore states A and F are equivalent. Thus one of the states, A or F can be removed from the state table. For example, if we remove row F from the table and replace all F's by A's in the columns, the state table is modified as shown in Table 7.
Table 7. State F removed
Present State

Next State

Output
 



It is apparent that states B and E are equivalent. Removing E and replacing E's by B's results in the reduce table shown in Table 8.
Table 8. Reduced state table
Present State

Next State

Output
 



The removal of equivalent states has reduced the number of states in the circuit from six to four. Two states are considered to be equivalent if and only if for every input sequence the circuit produces the same output sequence irrespective of which one of the two states is the starting state.
Design of Sequential Circuits
This example is taken from M. M. Mano, Digital Design, Prentice Hall, 1984, p.235.
Example 1.3 We wish to design a synchronous sequential circuit whose state diagram is shown in Figure 13. The type of flipflop to be use is JK.
Figure 13. State diagram
From the state diagram, we can generate the state table shown in Table 9. Note that there is no output section for this circuit. Two flipflops are needed to represent the four states and are designated Q0Q1. The input variable is labelled x.
Table 9. State table.
Present State

Next State
 


We shall now derive the excitation table and the combinational structure. The table is now arranged in a different form shown in Table 11, where the present state and input variables are arranged in the form of a truth table. Remember, the excitable for the JK flipflop was derive in
Table 10. Excitation table for JK flipflop
Output Transitions

Flipflop inputs
 


Table 11. Excitation table of the circuit
Present State

Next State

Input

Flipflop Inputs
 




In the first row of Table 11, we have a transition for flipflop Q0 from 0 in the present state to 0 in the next state. In Table 10 we find that a transition of states from 0 to 0 requires that input J = 0 and input K = X. So 0 and X are copied in the first row under J0 and K0 respectively. Since the first row also shows a transition for the flipflop Q1 from 0 in the present state to 0 in the next state, 0 and X are copied in the first row under J1 and K1. This process is continued for each row of the table and for each flipflop, with the input conditions as specified in Table 10.
The simplified Boolean functions for the combinational circuit can now be derived. The input variables are Q0, Q1, and x; the output are the variables J0, K0, J1 and K1. The information from the truth table is plotted on the Karnaugh maps shown in Figure 14.
Figure 14. Karnaugh Maps
The flipflop input functions are derived:
J0 = Q1*x' K0 = Q1*x

J1 = x K1 = Q0'*x' + Q0*x = Q0x

Note: the symbol is exclusiveNOR.
The logic diagram is drawn in Figure 15.
Figure 15. Logic diagram of the sequential circuit.
Design of Sequential Circuits
This example is taken from P. K. Lala, Practical Digital Logic Design and Testing, Prentice Hall, 1996, p.176.
Example 1.4 Design a sequential circuit whose state tables are specified in Table 12, using D flipflops.
Table 12. State table of a sequential circuit.
Present State

Next State

Output
 



Table 13. Excitation table for a D flipflop.
Output Transitions

Flipflop inputs
 


Next step is to derive the excitation table for the design circuit, which is shown in Table 14. The output of the circuit is labelled Z.
Table 14. Excitation table
Present State

Next State

Input

Flipflop Inputs

Output
 





Now plot the flipflop inputs and output functions on the Karnaugh map to derive the Boolean expressions, which is shown in Figure 16.
Figure 16. Karnaugh maps
The simplified Boolean expressions are:
D0 = Q0*Q1' + Q0'*Q1*x

D1 = Q0'*Q1'*x + Q0*Q1*x + Q0*Q1'*x'

Z = Q0*Q1*x

Finally, draw the logic diagram.
Figure 17. Logic diagram of the sequential circuit.
Design of Counters
A sequential circuit that goes through a prescribed sequence of states upon the application of input pulses is called a counter. The input pulses, called count pulses, may be clock pulses. In a counter, the sequence of states may follow a binary count or any other sequence of states. Counters are found in almost all equipment containing digital logic. They are used for counting the number of occurrences of an even and are useful for generating timing sequences to control operations in a digital system.
Of the various sequences a counter may follow, the straight binary sequence is the simplest and most straight forward. A counter that follows the binary sequence is called a binary counter. An nbit binary counter consists of n flipflops and can count in binary from 0 to 2^{n}  1.
Design of Counters
This example is taken from T. L. Floyd, Digital Fundamentals, Fourth Edition, Macmillan Publishing, 1990, p.395.
Example 1.5 A counter is first described by a state diagram, which is shows the sequence of states through which the counter advances when it is clocked. Figure 18 shows a state diagram of a 3bit binary counter.
Figure 18. State diagram of a 3bit binary counter.
The circuit has no inputs other than the clock pulse and no outputs other than its internal state (outputs are taken off each flipflop in the counter). The next state of the counter depends entirely on its present state, and the state transition occurs every time the clock pulse occurs. Figure 19 shows the sequences of count after each clock pulse.
Fig.19 Count sequence after each pulse
Once the sequential circuit is defined by the state diagram, the next step is to obtain the nextstate table, which is derived from the state diagram in Figure 18 and is shown in Table 15.
Table 15. State table
Present State

Next State
 


Since there are eight states, the number of flipflops required would be three. Now we want to implement the counter design using JK flipflops.
Next step is to develop an excitation table from the state table, which is shown in Table 16.
Table 16. Excitation table
Output State Transitions

Flipflop inputs
 
Present State

Next State
 



Now transfer the JK states of the flipflop inputs from the excitation table to Karnaugh maps to derive a simplified Boolean expression for each flipflop input. This is shown in Figure 20.
Figure 20. Karnaugh maps
The 1s in the Karnaugh maps of Figure 20 are grouped with "don't cares" and the following expressions for the J and K inputs of each flipflop are obtained:
J0 = K0 = 1

J1 = K1 = Q0

J2 = K2 = Q1*Q0

The final step is to implement the combinational logic from the equations and connect the flipflops to form the sequential circuit. The complete logic of a 3bit binary counter is shown in Figure 21.
Figure 21. Logic diagram of a 3bit binary counter
Design of Counters
This example is taken from M. M. Mano, Digital Design, Prentice Hall, 1984, p.243.
Example 1.6 Design a counter specified by the state diagram in Example 1.5 using T flipflops. The state diagram is shown here again in Figure 22.
Figure 22. State diagram of a 3bit binary counter.
The state table will be the same as in Example 1.5.
Now derive the excitation table from the state table, which is shown in Table 17.
Table 17. Excitation table.
Output State Transitions

Flipflop inputs
 
Present State

Next State
 



Next step is to transfer the flipflop input functions to Karnaugh maps to derive a simplified Boolean expressions, which is shown in Figure 23.
Figure 23. Karnaugh maps
The following expressions are obtained:
T0 = 1; T1 = Q0; T2 = Q1*Q0
Finally, draw the logic diagram of the circuit from the expressions obtained. The complete logic diagram of the counter is shown in Figure 24.
Figure 24. Logic diagram of 3bit binary counter.
Now that you have reached the end of the tutorial, you should be able to understand the basic concept of sequential circuits. You should be able to analyse and design a basic sequential circuit. Now you can practice some of the exercises using the analysis and design procedures shown in the examples.
Exercises
You can try some of these exercises which covers the analysis and design of sequential circuits.
Analysis of Sequential Circuits.
1. Derive a) excitation equations, b) next state equations, c) a state/output table, and d) a state diagram for the circuit shown in Figure 1.1. Draw the timing diagram of the circuit.
Figure 1.1
2. Derive a) excitation equations, b) next state equations, c) a state/output table, and d) a state diagram for the circuit shown in Figure 1.2.
Figure 1.2
3. Derive a) excitation equations, b) next state equations, c) a state/output table, and d) a state diagram for the circuit shown in Figure 1.3.
Figure 1.3
4. Derive the state output and state diagran for the sequential circuit shown in Figure 1.4.
Figure 1.4
5. A sequential circuit uses two D flipflops as memory elements. The behaviour of the circuit is described by the following equations:
D1 = Q1 + x'*Q2

D2 = x*Q1' + x'*Q2

Z = x'*Q1*Q2 + x*Q1'*Q2'

Derive the state table and draw the state diagram of the circuit.
Design of Sequential Circuits.
6. Design a sequential circuit specified by Table 6.1, using JK flipflops.
Table 6.1
Present State

Next State

Output
 



7. Design the sequential circuit in question 6, using T flipflops.
8. Design a mod5 counter which has the following binary sequence: 0, 1, 2, 3, 4. Use JK flipflops.
9. Design a counter that has the following repeated binary sequence: 0, 1, 2, 3, 4, 5, 6, 7. Use RS flipflops.
10. Design a counter with the following binary sequence: 1, 2, 5, 7 and repeat. Use JK flipflops.
11. Design a counter with the following repeated binary sequence: 0, 4, 2, 1, 6. Use T flipflops.
12. Design a counter that counts in the sequence 0, 1, 3, 6, 10, 15, using four a) D, b) SR, c) JK and d) T flipflops.
Digital Logic Families
Logic families can be classified broadly according to the technologies they are
built with. The various technologies are listed below.
· DL : Diode Logic.
· RTL : Resistor Transistor Logic.
· DTL : Diode Transistor Logic.
· HTL : High threshold Logic.
· TTL : Transistor Transistor Logic.
· I^{2}L : Integrated Injection Logic.
· ECL : Emitter coupled logic.
· MOS : Metal Oxide Semiconductor Logic (PMOS and NMOS).
· CMOS : Complementary Metal Oxide Semiconductor Logic.
Among these, only CMOS is most widely used by the ASIC (Chip) designers.
 Fanin.
 Fanout.
 Noise Margin.
 Power Dissipation.
 Gate Delay.
 Wire Delay.
 Skew.
 Voltage threshold
Fan – in:
Fanin is the number of inputs a gate has, like a two input AND gate has fanin of two, a three input NAND gate as a fanin of three. So a NOT gate always has a fanin of one. The figure below shows the effect of fanin on the delay offered by a gate for a CMOS based gate. Normally delay increases following a quadratic function of fanin.
Fan – out:
The number of gates that each gate can drive, while providing voltage levels in the guaranteed range, is called the standard load or fanout. The fanout really depends on the amount of electric current a gate can source or sink while driving other gates. The effects of loading a logic gate output with more than its rated fanout has the following effects.
 In the LOW state the output voltage VOL may increase above VOLmax.
 In the HIGH state the output voltage VOH may decrease below VOHmin.
 The operating temperature of the device may increase thereby reducing the reliability of the device and eventually causing the device failure.
 Output rise and fall times may increase beyond specifications
 The propagation delay may rise above the specified value.
Normally as in the case of fanin, the delay offered by a gate increases with the increase in fanout.
Gate Delay
Gate delay is the delay offered by a gate for the signal appearing at its input, before it reaches the gate output. The figure below shows a NOT gate with a delay of "Delta", where output X' changes only after a delay of "Delta". Gate delay is also known as propagation delay.
Gate delay is not the same for both transitions, i.e. gate delay will be different for low to high transition, compared to high to low transition.Low to high transition delay is called turnon delay and High to low transition delay is called turnoff delay.
Wire Delay
Gates are connected together with wires and these wires do delay the signal they carry, these delays become very significant when frequency increases, say when the transistor sizes are submicron. Sometimes wire delay is also called flight time (i.e. signal flight time from point A to B). Wire delay is also known as transport delay.
The same signal arriving at different parts of the design with different phase is known as skew. Skew normally refers to clock signals. In the figure below, clock signal CLK reaches flipflop FF0 at time t0, so with respect to the clock phase at the source, it has at FF0 input a clock skew of t0 time units. Normally this is expressed in nanoseconds.
The waveform below shows how clock looks at different parts of the design.
Logic levels
Logic levels are the voltage levels for logic high and logic low.
· VO_{Hmin} : The minimum output voltage in HIGH state (logic '1'). VO_{Hmin} is 2.4 V for TTL and 4.9 V for CMOS.
· VO_{Lmax} : The maximum output voltage in LOW state (logic '0'). VO_{Lmax} is 0.4 V for TTL and 0.1 V for CMOS.
· VI_{Hmin} : The minimum input voltage guaranteed to be recognised as logic 1. VI_{Hmin} is 2 V for TTL and 3.5 V for CMOS.
· VI_{Lmax} : The maximum input voltage guaranteed to be recognised as logic 0. VI_{Lmax} is 0.8 V for TTL and 1.5 V for CMOS.
Current levels
· IO_{Hmin}: The maximum current the output can source in HIGH state while still maintaining the output voltage above VO_{Hmin}.
· IO_{Lmax} : The maximum current the output can sink in LOW state while still maintaining the output voltage below VO_{Lmax}.
· I_{Imax} : The maximum current that flows into an input in any state (1ÂµA for CMOS).
Noise Margin
Gate circuits are constructed to sustain variations in input and output voltage levels. Variations are usually the result of several different factors.
· Batteries lose their full potential, causing the supply voltage to drop
· High operating temperatures may cause a drift in transistor voltage and current characteristics
· Spurious pulses may be introduced on signal lines by normal surges of current in neighbouring supply lines.
All these undesirable voltage variations that are superimposed on normal operating voltage levels are called noise. All gates are designed to tolerate a certain amount of noise on their input and output ports. The maximum noise voltage level that is tolerated by a gate is called noise margin. It derives from I/PO/P voltage characteristic, measured under different operating conditions. It's normally supplied from manufacturer in the gate documentation.
· LNM (Low noise margin): The largest noise amplitude that is guaranteed not to change the output voltage level when superimposed on the input voltage of the logic gate (when this voltage is in the LOW interval). LNM=VI_{Lmax}VO_{Lmax}.
· HNM (High noise margin): The largest noise amplitude that is guaranteed not to change the output voltage level if superimposed on the input voltage of the logic gate (when this voltage is in the HIGH interval). HNM=VO_{Hmin}VI_{Hmin}
t_{r} (Rise time)
The time required for the output voltage to increase from V_{IL}max to V_{IH}min.
t_{f} (Fall time)
The time required for the output voltage to decrease from V_{IH}min to V_{IL}max.
t_{p} (Propagation delay)
The time between the logic transition on an input and the corresponding logic transition on the output of the logic gate. The propagation delay is measured at midpoints.
Each gate is connected to a power supply VCC (VDD in the case of CMOS). It draws a certain amount of current during its operation. Since each gate can be in a High, Transition or Low state, there are three different currents drawn from power supply.
· ICCH: Current drawn during HIGH state.
· ICCT: Current drawn during HIGH to LOW, LOW to HIGH transition.
· ICCL: Current drawn during LOW state.
For TTL, ICCT the transition current is negligible, in comparison to ICCH and ICCL. If we assume that ICCH and ICCL are equal then,
Average Power Dissipation = Vcc * (ICCH + ICCL)/2
For CMOS, ICCH and ICCL current is negligible, in comparison to ICCT. So the Average power dissipation is calculated as below.
Average Power Dissipation = Vcc * ICCT.
So for TTL like logics family, power dissipation does not depend on frequency of operation, and for CMOS the power dissipation depends on the operation frequency.
Power Dissipation is an important metric for two reasons. The amount of current and power available in a battery is nearly constant. Power dissipation of a circuit or system defines battery life: the greater the power dissipation, the shorter the battery life. Power dissipation is proportional to the heat generated by the chip or system; excessive heat dissipation may increase operating temperature and cause gate circuitry to drift out of its normal operating range; will cause gates to generate improper output values. Thus power dissipation of any gate implementation must be kept as low as possible.
Moreover, power dissipation can be classified into Static power dissipation and Dynamic power dissipation.
· Ps (Static Power Dissipation): Power consumed when the output or input are not changing or rather when clock is turned off. Normally static power dissipation is caused by leakage current. (As we reduce the transistor size, i.e. below 90nm, leakage current could be as high as 40% of total power dissipation).
· Pd (Dynamic Power Dissipation): Power consumed during output and input transitions. So we can say Pd is the actual power consumed i.e. the power consumed by transistors + leakage current.
Thus
Total power dissipation = static power dissipation + dynamic power dissipation.
Diode Logic
In DL (diode logic), all the logic is implemented using diodes and resistors. One basic thing about the diode is that diode needs to be forward biased to conduct. Below is the example of a few DL logic circuits.
When no input is connected or driven, output Z is low, due to resistor R1. When high is applied to X or Y, or both X and Y are driven high, the corresponding diode get forward biased and thus conducts. When any diode conducts, output Z goes high.
Resistor Transistor Logic
In RTL (resistor transistor logic), all the logic are implemented using resistors and transistors. One basic thing about the transistor (NPN), is that HIGH at input causes output to be LOW (i.e. like a inverter). Below is the example of a few RTL logic circuits.
A basic circuit of an RTL NOR gate consists of two transistors Q1 and Q2, connected as shown in the figure above. When either input X or Y is driven HIGH, the corresponding transistor goes to saturation and output Z is pulled to LOW.
Diode Transistor Logic
In DTL (Diode transistor logic), all the logic is implemented using diodes and transistors. A basic circuit in the DTL logic family is as shown in the figure below. Each input is associated with one diode. The diodes and the 4.7K resistor form an AND gate. If input X, Y or Z is low, the corresponding diode conducts current, through the 4.7K resistor. Thus there is no current through the diodes connected in series to transistor base. Hence the transistor does not conduct, thus remains in cutoff, and output out is high.
If all the inputs X, Y, Z are driven high, the diodes in series conduct, driving the transistor into saturation. Thus output out is Low.
Transistor Transistor Logic
In Transistor Transistor logic or just TTL, logic gates are built only around transistors. TTL was developed in 1965. Through the years basic TTL has been improved to meet performance requirements. There are many versions or families of TTL.
· Standard TTL.
· High Speed TTL
· Low Power TTL
· Schhottky TTL
TTL families have three configurations for outputs.
· Totem  Pole output.
· Open Collector Output.
· Tristate Output.
The input stage, which is used with almost all versions of TTL, consists of an input transistor and a phase splitter transistor. Input stage consists of a multi emitter transistor as shown in the figure below. When any input is driven low, the emitter base junction is forward biased and input transistor conducts. This in turn drives the phase splitter transistor into cutoff.
Totem  Pole Output
Below is the circuit of a totempole NAND gate, which has got three stages.
· Input Stage
· Phase Splitter Stage
· Output Stage
Input stage and Phase splitter stage have already been discussed. Output stage is called TotemPole because transistor Q3 sits upon Q4.
Q2 provides complementary voltages for the output transistors Q3 and Q4, which stack one above the other in such a way that while one of these conducts, the other is in cutoff.
Q4 is called pulldown transistor, as it pulls the output voltage down, when it saturates and the other is in cutoff (i.e. Q3 is in cutoff). Q3 is called pullup transistor, as it pulls the output voltage up, when it saturates and the other is in cutoff (i.e. Q4 is in cutoff).
Diodes in input are protection diodes which conduct when there is large negative voltage at input, shorting it to the ground.
Tristate Output.
Normally when we have to implement shared bus systems inside an ASIC or externally to the chip, we have two options: either to use a MUX/DEMUX based system or to use a tristate base bus system.
In the latter, when logic is not driving its output, it does not drive LOW neither HIGH, which means that logic output is floating. Well, one may ask, why not just use an open collector for shared bus systems? The problem is that open collectors are not so good for implementing wireANDs.
The circuit below is a tristate NAND gate; when Enable En is HIGH, it works like any other NAND gate. But when Enable En is driven LOW, Q1 Conducts, and the diode connecting Q1 emitter and Q2 collector, conducts driving Q3 into cutoff. Since Q2 is not conducting, Q4 is also at cutoff. When both pullup and pulldown transistors are not conducting, output Z is in highimpedance state.
Emitter coupled logic
Emitter coupled logic (ECL) is a non saturated logic, which means that transistors are prevented from going into deep saturation, thus eliminating storage delays. Preventing the transistors from going into saturation is accomplished by using logic levels whose values are so close to each other that a transistor is not driven into saturation when its input switches from low to high. In other words, the transistor is switched on, but not completely on. This logic family is faster than TTL.
Voltage level for high is 0.9 Volts and for low is 1.7V; thus biggest problem with ECL is a poor noise margin.
A typical ECL OR gate is shown below. When any input is HIGH (0.9v), its connected transistor will conduct, and hence will make Q3 off, which in turn will make Q4 output HIGH.
When both inputs are LOW (1.7v), their connected transistors will not conduct, making Q3 on, which in turn will make Q4 output LOW.
MOS or Metal Oxide Semiconductor logic uses nmos and pmos to implement logic gates. One needs to know the operation of FET and MOS transistors to understand the operation of MOS logic circuits.
The basic NMOS inverter is shown below: when input is LOW, NMOS transistor does not conduct, and thus output is HIGH. But when input is HIGH, NMOS transistor conducts and thus output is LOW.
Normally it is difficult to fabricate resistors inside the chips, so the resistor is replaced with an NMOS gate as shown below. This new NMOS transistor acts as resistor.
Complementary Metal Oxide Semiconductor Logic
CMOS or Complementary Metal Oxide Semiconductor logic is built using both NMOS and PMOS. Below is the basic CMOS inverter circuit, which follows these rules:
· NMOS conducts when its input is HIGH.
· PMOS conducts when its input is LOW.
So when input is HIGH, NMOS conducts, and thus output is LOW; when input is LOW PMOS conducts and thus output is HIGH.
Field Programmable Gate Arrays(FPGA)
Field Programmable Gate Arrays are two dimensional arrays of logic blocks and flipflops with a electrically programmable interconnections between logic blocks.
The interconnections consist of electrically programmable switches which is why FPGA differs from Custom ICs, as Custom IC is programmed using integrated circuit fabrication technology to form metal interconnections between logic blocks.

In an FPGA logic blocks are implemented using mutliple level low fanin gates, which gives it a more compact design compared to an implementation with twolevel ANDOR logic. FPGA provides its user a way to configure:
1. The intersection between the logic blocks and
2. The function of each logic block.
Logic block of an FPGA can be configured in such a way that it can provide functionality as simple as that of transistor or as complex as that of a microprocessor. It can used to implement different combinations of combinational and sequential logic functions. Logic blocks of an FPGA can be implemented by any of the following:
1. Transistor pairs
2. combinational gates like basic NAND gates or XOR gates
3. ninput Lookup tables
4. Multiplexers
5. Wide fan in AndOR structure.
Figure 1: Simplefied version of FPGA internal architecture.
Routing in FPGAs consists of wire segments of varying lengths which can be interconnected via electrically programmable switches. Density of logic block used in an FPGA depends on length and number of wire segments used for routing. Number of segments used for interconnection typically is a tradeoff between density of logic blocks used and amount of area used up for routing.
The ability to reconfigure functionality to be implemented on a chip gives a unique advantage to designer who designs his system on an FPGA It reduces the time to market and significantly reduces the cost of production.
Why do we need FPGAs ?
By the early 1980's Large scale integrated circuits (LSI) formed the back bone of most of the logic circuits in major systems. Microprocessors, bus/IO controllers, system timers etc were implemented using integrated circuit fabrication technology. Random "glue logic" or interconnects were still required to help connect the large integrated circuits in order to :
1. generate global control signals (for resets etc.)
2. data signals from one subsystem to another sub system.
Systems typically consisted of few large scale integrated components and large number of SSI (small scale integrated circuit) and MSI (medium scale integrated circuit) components.
Intial attempt to solve this problem led to development of Custom ICs which were to replace the large amount of interconnect. This reduced system complexity and manufacturing cost, and improved performance.However, custom ICs have their own disadvantages. They are relatively very expensive to develop, and delay introduced for product to market (time to market) because of increased design time. There are two kinds of costs involved in development of Custom ICs:
1. cost of development and design
2. cost of manufacture
( A tradeoff usually exists between the two costs)
1. cost of development and design
2. cost of manufacture
( A tradeoff usually exists between the two costs)
Therefore the custom IC approach was only viable for products with very high volume, and which were not time to market sensitive.
FPGAs were introduced as an alternative to custom ICs for implementing entire system on one chip and to provide flexibility of reporogramability to the user. Introduction of FPGAs resulted in improvement of density relative to discrete SSI/MSI components (within around 10x of custom ICs). Another advantage of FPGAs over CustomICs is that with the help of computer aided design (CAD) tools circuits could be implemented in a short amount of time (no physical layout process, no mask making, no IC manufacturing)
Figure 2: FPGA comparative analysis.
Logic Block
Logic Block
Logic block in an FPGA can be implemented in ways that differ in number of inputs and outputs, amount of area consumed, complexity of logic functions that it can implement, total number of transistors that it consumes. This section will describe some important implementations of logic blocks.

Crosspoint FPGA: consist of two types of logic blocks. One is transistor pair tiles in which transistor pairs run in parallel lines as shown in figure below:
second type of logic blocks are RAM logic which can be used to implement random access memory.
Plessey FPGA: basic building block here is 2input NAND gate which is connected to each other to implement desired function.
Both Crosspoint and Plessey are fine grain logic blocks. Fine grain logic blocks have an advantage in high percentage usage of logic blocks but they require large number of wire segments and programmable switches which occupy lot of area.
Actel Logic Block: If inputs of a multiplexer are connected to a constant or to a signal, it can be used to implement different logic functions. for example a 2input multiplexer with inputs a and b, select , will implement function ac + bc´. If b=0 then it will implement ac, and if a=0 it will implement bc´.
Typically an Actel logic block consists of multiple number of multiplexers and logic gates.
Xilinx Logic block:
In Xilinx logic block Look up table is used to implement any number of different functionality. The input lines go into the input and enable of lookup table. The output of the lookup table gives the result of the logic function that it implements. Lookup table is implemented using SRAM. A kinput logic function is implemented using 2^k * 1 size SRAM. Number of different possible functions for k input LUT is 2^2^k. Advantage of such an architecture is that it supports implementation of so many logic functions, however the disadvantage is unusually large number of memory cells required to implement such a logic block in case number of inputs is large. Figure below shows 5input LUT based implementation of logic block.Xilinx  LUT based
LUT based design provides for better logic block utilization. A kinput LUT based logic block can be implemented in number of different ways with tradeoff between performance and logic density.
An nlut can be shown as a direct implementation of a function truthtable. Each of the latch holds the value of the function corresponding to one input combination. For Example: 2lut shown in figure below implements 2 input AND and OR functions.
Altera Logic Block
Altera's logic block has evolved from earlier PLDs. It consists of wide fan in (up to 100 input) AND gates feeding into an OR gate with 38 inputs. If floating gate transistor based programmable switch is provide any vertical wire passing near AND gate can be used as input to the AND gate. IF each input signal is present both original and complemented form functional capability of block increases significantly. The advantage of large fan in AND gate based implementation is that few logic blocks can implement the entire functionality thereby reducing the amount of area required by interconnects. On the other hand disadvantage is the low density usage of logic blocks in a design that requires fewer input logic.
Another disadvantage is the use of pull up devices (AND gates) that consume static power. To improve power manufacturers provide low power consuming logic blocks at the expense of delay. Such logic blocks have gates with high Threshold as a result they consume less power. Such logic blocks can be used in noncritical paths.
Altera, Xilinx are coarse grain architecture.
Tradeoff  Size of Logic block Vs Performance
Size of logic block plays an important role in deciding density of logic blocks and area utilization in an FPGA. It also effects the performance of the FPGA.
 A large size logic block implements more logic and hence requires less number of logic blocks to implement a functionality on the FPGA. On the other hand a large logic block will consume more space on the FPGA. So optimal size of logic block is one that optimally uses lesser number of logic blocks for functionality implementation while consuming as little space as possible.
 Active logic area is generally less than total logic area due to presence of programmable connections. Total logic area is sum of active logic area and area consumed by programmable connections.
 Routing area in an FPGA is typically more than the active area. It is 70 to 90 percent of total area in an FPGA.
 In case of Lookup table based FPGA, a 4input lookup table gives best results in terms of logic synthesised and area consumed.
 Granularity of logic block has influence on performance of an FPGA. Typically higher granularity level results in lesser delay between input and output. As the granularity of logic block increases, number of levels of logic in critical path decreases, and hence delay in critical path decreases. On the flip side with increase in granularity level average fan out increases and number of switches also increases as each block has more pins. Also the length of wires increases with increase in size of logic block.
FPGA Routing Techniques
Routing architecture comprises of programmable switches and wires. Routing provides connection between I/O blocks and logic blocks, and between one logic block and another logic block.
The type of routing architecture decides area consumed by routing and density of logic blocks.
Routing technique used in an FPGA largely decides the amount of area used by wire segments and programmable switches as compared to area consumed by logic blocks.

A wire segment can be described as two end points of an interconnect with no programmable switch between them. A sequence of one or more wire segments in an FPGA can be termed as a track.
Typically an FPGA has logic blocks, interconnects and Input/Output blocks. Input Output blocks lie in the periphery of logic blocks and interconnect. Wire segments connect I/O blocks to wire segments through connection blocks. Connection blocks are connected to logic blocks, depending on the design requirement one logic block is connected to another and so on.
Xilinx Routing architecture
In Xilinx routing, connections are made from logic block into the channel through a connection block. As SRAM technology is used to implement Lookup Tables, connection sites are large. A logic block is surrounded by connection blocks on all four sides. They connect logic block pins to wire segments. Pass transistors are used to implement connection for output pins, while use of multiplexers for input pins saves the number of SRAM cells required per pin. The logic block pins connecting to connection blocks can then be connected to any number of wire segments through switching blocks.
there are four types of wire segments available :

Actel routing methodology
Actel's design has more wire segments in horizontal direction than in vertical direction. The input pins connect to all tracks of the channel that is on the same side as the pin. The output pins extend across two channels above the logic block and two channels below it. Output pin can be connected to all 4 channels that it crosses. The switch blocks are distributed throughout the horizontal channels. All vertical tracks can make a connection with every incidental horizontal track. This allows for the flexibility that a horizontal track can switch into a vertical track, thus allowing for horizontal and vertical routing of same wire. The drawback is more switches are required which add up to more capacitive load.
Altera routing methodology
Altera routing architecture has two level hierarchy. At the first level of the hierarchy, 16 or 32 of the logic
blocks are grouped into a Logic Array Block, structure of the LAB is very similar to a traditional PLD. the connection is formed using EPROM like floatinggate transistors. The channel here is set of wires that run vertically along the length of the FPGA. Tracks are used for four types of connections :
blocks are grouped into a Logic Array Block, structure of the LAB is very similar to a traditional PLD. the connection is formed using EPROM like floatinggate transistors. The channel here is set of wires that run vertically along the length of the FPGA. Tracks are used for four types of connections :
 connections from output of all logic blocks in LAB.
 connection from logic expanders.
 connections from output of logic blocks in other LABs
 connections to and from Input output pads
all four types of tracks connect to every logic block in the array block. The connection block makes sure that every such track can connect to every logic block pin. Any track can connect to into any input which makes this routing simple. The intraLAB routing consists of segmented channel, where segments are as long as possible. Global interconnect structure called programmable interconnect array(PIA) is used to make connections among LABs. Its internal structure is similar to internal routing of a LAB. Advantage of this scheme is that regularity of physical design of silicon allows it to be packed tightly and efficiently. The disadvantage is the large number of switches required, which adds to capacitive load.
FPGA Structural Classification
There is a constant effort on the part of system designers to design systems with improved performance, efficiency and flexibility.
Today, if one wants to make effective and competitive use of these general purpose blocks, then one of the better ways is to use reconfigurable hardware that allows user programmability.

The first form of reconfigurable device was Programmable Logic Devices which consisted of arrays of AND and OR gates with programmable metal paths as interconnection between them. They could be programmed to into a single chip to meet specific requirements. PLDs later evolved into what was later known as FPGAs.
Basic structure of an FPGA includes logic elements, programmable interconnects and memory. Arrangement of these blocks is specific to particular manufacturer. On the basis of internal arrangement of blocks FPGAs can be divided into three classes:
This architecture consists of logic elements(called CLBs) arranged in rows and columns of a matrix and interconnect laid out between them. This symmetical matrix is surrounded by I/O blocks which connect it to outside world. Each CLB consists of ninput Lookup table and a pair of programmable flip flops. I/O blocks also control functions such as tristate control, output transition speed. Interconnects provide routing path. Direct interconnects between adjacent logic elements have smaller delay compared to general purpose interconnet.
Row based architecture consists of alternating rows of logic modules and programmable interconnect tracks. Input output blocks are located in the periphery of the rows. One row may be connected to adjacent rows via vertical interconnect. Logic modules can be implemented in various combinations. Combinatorial modules contain only combinational elements which Sequential modules contain both combinational elements along with flip flops. This sequential modules can implement complex combinatorialsequential functions. Routing tracks are divided into smaller segments connected by antifuse elements between them.
This architecture is designed in hierarchical manner with top level containing only logic blocks and interconnects. Each logic block contains number of logic modules. And each logic module has combinatorial as well as sequential functional elements. Each of these functional elements is controlled by the programmed memory. Communication between logic blocks is achieved by programmable interconnect arrays. Input output blocks surround this scheme of logic blocks and interconnects.
Programming Methodology
Electrically programmable switches are used to program an FPGA. Performance of an FPGA in terms of area and logic density is a function of properties of these switches.
Properties of these programmable switches that make difference are onresistance, parasitic capacitance, volatility, reprogrammability, size etc.
Various approaches to provide user programmability are :

SRAM programming technology
Static RAM cells are used to control pass gates or multiplexers. To use pass gate as closed switch, boolean one is stored in SRAM cell. When zero is stored pass transistor provides high resistance between two wire segments. Figure a depicts this usage of SRAM.
To use SRAM as multiplexer, state of control values stored in SRAM decides which of the multiplexer inputs are connected to the output as shown in figure b.
Advantage of SRAM is that it provides fast reprogrammability and integrated circuit fabrication technology is required to build it. While disadvantage is the space it consumes as minimum five transistors are required to implement a memory cell.
Floating Gate Programming
Technology found in ultaviolet erasable EPROM and electrically erasable EEPROM devices is used in FPGA from Altera. The programmable switch is a transistor that permanently be disabled.
Here again the advantage is reprogrammability but there is another advantage no external permanent memory source is need to program it at powerup. However it requires three additional processing steps over CMOS technology. Other disadvantages are high static power consumption due to pull up resistor and high ONresistance of EPROM transistor.
Electrically programmable EPROM is used by AMD and Lattice. Use of EEPROM gives advantage of easy reprogrammability. However EEPROM cell is twice as large as EPROM cell.
Antifuse programming methodology
An Antifuse is a two terminal device with an unprogrammed state providing very high resistance between its terminals. To create a low resistance link between the two terminals high voltage is applied accross the terminals to blow the antifuse. Extra bit of circuitry is required to program an antifuse. Antifuse technology is used by FPGA's from Actel, QuickLogic and Crosspoint.
Advantage of Antifuse is relatively small size and hence area reduction which is anulled by area consumed by extra circuitry to program it. Another big advantage is low series resistance and low parasitic capacitance.
FPGA Design Flow
One of the most important advantages of FPGA based design is that users can design it using CAD tools provided by design automation companies.
Generic design flow of an FPGA includes following steps:

System Design
At this stage designer has to decide what portion of his functionality has to be implemented on FPGA and how to integrate that functionality with rest of the system.
I/O integration with rest of the system
Input Output streams of the FPGA are integrated with rest of the Printed Circuit Board, which allows the design of the PCB early in design process. FPGA vendors provide extra automation software solutions for I/O design process.
Design Description
Designer describes design functionality either by using schema editors or by using one of the various Hardware Description Languages(HDLs) like Verilog or VHDL.
Synthesis
Once design has been defined CAD tools are used to implement the design on a given FPGA. Synthesis includes generic optimization, slack optimizations, power optimizations followed by placement and routing. Implementation includes Partition, Place and route. The output of design implementation phase is bitstream file.
Design Verification
Bit stream file is fed to a simulator which simulates the design functionality and reports errors in desired behavior of the design. Timing tools are used to determine maximum clock frequency of the design. Now the design is loading onto the target FPGA device and testing is done in real environment.
Example :
Below given circuit consists of gates and flip flops. Combinational elements of the circuit are covered by a 4input Look up table(4LUT). Sequential elements in the input circuit map to flip flops on the FPGA. Placement of these elements is done in such a way as to minimize wiring during routing.