Introduction
This project having implementation of all 4 type of flip flop. These take input as the state machine diagram and producing the flip flop inputs. then using the Tabulation Method, circuit expression is calculated and then displayed using AND,OR Logic Gates.
Logic Gates
A logic gate is an elementary building block of a digital circuit. Most logic gates have two inputs and one output. At any given moment, every terminal is in one of the two binarylowhigh
(1), represented by different voltage levels. The logic state of a
terminal can, and generally does, change often, as the circuit
processes data. In most logic gates, the low state is approximately
zero volts (0 V), while the high state is approximately five volts
positive (+5 V). (0) or conditions
There are seven basic logic gates: AND, OR, XOR, NOT, NAND, NOR, and XNOR.
But with our application we are using only AND OR gate.
The AND gate is so named because, if 0 is called "false" and 1
is called "true," the gate acts in the same way as the logical "and"
operator. The following illustration and table show the circuit symbol
and logic combinations for an AND gate. (In the symbol, the input
terminals are at left and the output terminal is at right.) The output
is "true" when both inputs are "true." Otherwise, the output is "false."
AND gate
| Input 1 | Input 2 | Output |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The OR gate
gets its name from the fact that it behaves after the fashion of the
logical inclusive "or." The output is "true" if either or both of the
inputs are "true." If both inputs are "false," then the output is
"false."
OR gate
| Input 1 | Input 2 | Output |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Flip Flop
Sequential logic is a form of binary circuit design that employs one or
more inputs and one or more outputs, whose states are related by
defined rules that depend, in part, on previous states. Each of the
inputs and output(s) can attain either of two states: logic 0 (low) or
logic 1 (high).
A common example of a circuit employing sequential logic is the
flip-flop, also called a bistable gate. A simple flip-flop has two
stable states. The flip-flop maintains its states indefinitely until an
input pulse called a trigger is received. If a trigger is received, the
flip-flop outputs change their states according to defined rules, and
remain in those states until another trigger is received.
There are several different kinds of flip-flop circuits, with
designators such as D, T, J-K, and R-S. Flip-flop circuits are
interconnected to form the logic gates that comprise digital integrated
circuits (
ICs) such as memory chips and microprocessors.
RS Flip Flop
(Or "RS flip-flop") A "set/reset" {flip-flop} in
which activating the "S" input will switch it to one stable
state and activating the "R" input will switch it to the other
state.
The outputs of a basic SR flip-flop change whenever its R or S
inputs change appropriately. A clocked SR flip-flop has an
extra clock input which enables or disables the other two
inputs. When they are disabled the outputs remain constant.
If we connect two clocked SR flip-flops so that the Q and /Q
outputs of the first, "master" flip-flop drive the S and R
inputs of the second, "slave" flip-flop, and we drive the
slave's clock input with an inverted version of the master's
clock, then we have an {edge-triggered} RS flip-flop. The
external R and S inputs of this device are latched on one edge
(transition) of the clock (e.g. the falling edge) and the
outputs will only change on the next opposite (rising) edge.
If both R and S inputs are active (when enabled), a {race
condition} occurs and the outputs will be in an indeterminate
state. A {JK flip-flop} avoids this possibility.
JK Flip Flop
An {edge triggered} {SR flip-flop} with extra logic
such that only one of the R and S inputs is enabled at any
time. This prevents a {race condition} which can occur when
both inputs of an RS flip-flop are active at the same time.
In a JK flip-flop the R and S inputs are renamed J and K
(after {Jack Kilby}). The set input (J) is only enabled when
the flip-flop is reset and K when it is set.
If both J and K inputs are held active then the outputs will
change ("togle") on each falling edge of the clock. JK
flip-flops can be used to build a {binary counter} with a
reset input.
D Flip Flop
A digital logic device that stores the status of
its "D" input whenever its clock input makes a certain
transition (low to high or high to low). The output, "Q",
shows the currently stored value.
T Flip Flop
A digital logic device that stores the status of
its "T" input whenever its clock input makes a certain
transition (low to high or high to low). The output will be same as clock input, if clock iinput is 0, else toggle the clock input.
Excitation Table
The excitation table rearranges the order of characteristic table.
Instead of the truth table inputs being the control bit(s) of the flip
flop and Q, and the output being Q+, the
truth table inputs are now Q and Q+, and the
"outputs" is the control bit(s) of the flip flop.
S-R flip-flop design:
Q Q* S R
-------------
0 0 0 X
0 1 1 0
1 0 0 1
1 1 X 0
J-K flip-flop design:
Q Q* J K
-------------
0 0 0 X
0 1 1 X
1 0 X 1
1 1 X 0
D flip-flop design:
Q Q* D
-----------
0 0 0
0 1 1
1 0 0
1 1 1
T flip-flop design:
Q Q* T
-----------
0 0 0
0 1 1
1 0 1
1 1 0 Tabulation Method
The Quine–McCluskey algorithm (or the method of prime implicants) is a method used for minimization of boolean functions.
It is functionally identical to Karnaugh mapping,
but the tabular form makes it more efficient for use in computer
algorithms, and it also gives a deterministic way to check that the
minimal form of a Boolean function has been reached. It is sometimes
referred to as the tabulation method.
The method involves two steps:
- Finding all prime Implicants of the function.
- Use those prime implicants in a prime implicant chart to
find the essential prime implicants of the function, as well as other
prime implicants that are necessary to cover the function.
Complexity
Although more practical than Karnaugh mapping when dealing with more
than four variables, the Quine-McCluskey algorithm also has a limited
range of use since the problem it solves is NP-hard: the runtime of the Quine-McCluskey algorithm grows exponentially with the input size. It can be shown that for a function of n variables the upper bound on the number of prime implicants is 3n/n. If n = 32 there may be over 6.5 * 1015, prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal heuristic methods, of which the Espresso heuristic logic minimizer is the de-facto world standard.
Example
Step 1: finding prime implicants
Minimizing an arbitrary function:
A B C D f
m0 0 0 0 0 0
m1 0 0 0 1 0
m2 0 0 1 0 0
m3 0 0 1 1 0
m4 0 1 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 x
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 x
m15 1 1 1 1 1
One can easily form the canonical sum of products expression from this table, simply by summing the minterms (leaving out don't-care terms) where the function evaluates to one:
- fA,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD
Of course, that's certainly not minimal. So to optimize, all
minterms that evaluate to one are first placed in a minterm table.
Don't-care terms are also added into this table, so they can be
combined with minterms:
Number of 1s Minterm Binary Representation
--------------------------------------------
1 m4 0100
m8 1000
--------------------------------------------
2 m9 1001
m10 1010
m12 1100
--------------------------------------------
3 m11 1011
m14 1110
--------------------------------------------
4 m15 1111
At this point, one can start combining minterms with other minterms.
If two terms vary by only a single digit changing, that digit can be
replaced with a dash indicating that the digit doesn't matter. Terms
that can't be combined any more are marked with a "*". When going from
Size 2 to Size 4, treat '-' as a third bit value. Ex: -110 and -100 or
-11- can be combined, but not -110 and 011-. (Trick: Match up the '-'
first.)
Number of 1s Minterm 0-Cube | Size 2 Implicants | Size 4 Implicants
------------------------------|-------------------|----------------------
1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--*
m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0*
------------------------------| m(8,10) 10-0 |----------------------
2 m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-*
m10 1010 |-------------------|
m12 1100 | m(9,11) 10-1 |
------------------------------| m(10,11) 101- |
3 m11 1011 | m(10,14) 1-10 |
m14 1110 | m(12,14) 11-0 |
------------------------------|-------------------|
4 m15 1111 | m(11,15) 1-11 |
| m(14,15) 111- |
Step 2: prime implicant chart
None of the terms can be combined any further than this, so at this
point we construct an essential prime implicant table. Along the side
goes the prime implicants that have just been generated, and along the
top go the minterms specified earlier. The don't care terms are not
placed on top - they are omitted from this section because they are not
necessary inputs.
| 4 | 8 | 10 | 11 | 12 | 15 | |
| m(4,12)* | X | | | | X | | -100 |
| m(8,9,10,11) | | X | X | X | | | 10-- |
| m(8,10,12,14) | | X | X | | X | | 1--0 |
| m(10,11,14,15)* | | | X | X | | X | 1-1- |
Here, each of the essential prime implicants has been starred
- the second prime implicant can be 'covered' by the third and fourth,
and the third prime implicant can be 'covered' by the second and first,
and is thus neither an essential. If a prime implicant is essential
then, as would be expected, it is necessary to include it in the
minimized boolean equation. In some cases, the essential prime
implicants do not cover all minterms, in which case additional
procedures for chart reduction can be employed. The simplest
"additional procedure" is trial and error, but a more systematic way is
Petrick's Method.
In the current example, the essential prime implicants do not handle
all of the minterms, so, in this case, one can combine the essential
implicants with one of the two non-essential ones to yield one of these
two equations:
Both of those final equations are functionally equivalent to this original (very area-expensive) equation:
Points of Interest
Implementation of the real time application and grip of the subject.
Updation
Please copy the "BGI" folder on the location of "C:\TC\". And make sure that path is "C:\TC\BGI", because this project needs graphics application.
