13,247,911 members (47,654 online)
alternative version

Stats

43.9K views
13 bookmarked
Posted 10 Dec 2007

Flip Flop Design procedure in C

, 11 Dec 2007
 Rate this:
Design Digital Circuits using all 4 types of flip flop

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.

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:

1. Finding all prime Implicants of the function.
2. 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:

$f(A,B,C,D) =\sum m(4,8,10,11,12,15) + d(9,14) \,$
     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:

$f_{A,B,C,D} = BC'D' + AB' + AC \$
$f_{A,B,C,D} = BC'D' + AD' + AC \$

Both of those final equations are functionally equivalent to this original (very area-expensive) equation:

$f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD \$

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.

Share

 Software Developer (Senior) India
Started my career with Working on C# Winform application and C++ application development and later moved to ASP.NET MVC.

You may also be interested in...

 First Prev Next
 Where is the source code? Atul Agarwal4-Apr-08 23:15 Atul Agarwal 4-Apr-08 23:15
 Last Visit: 31-Dec-99 19:00     Last Update: 17-Nov-17 20:25 Refresh 1