Flip Flop Design procedure in C

• Download FULL_F.zip - 70,888 KB
• Download BGI.zip - 111,090 KB

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:

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 3ⁿ/n. If n = 32 there may be over 6.5 * 10¹⁵, 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:

f_A,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.