One interesting fact is that you only need a single gate type to implement any electronic circuit. This gate is the NAND gate, shown below:
To prove that we can construct any boolean function using only NAND gates, we need only show how to build an inverter (NOT), AND gate, and OR gate from a NAND (since we can create any boolean function using only AND, NOT, and OR). Building an inverter is easy, just connect the two inputs together:
Once we can build an inverter, building an AND gate is easy - just invert the output of a NAND gate. After all, NOT (NOT (A AND B)) is equivalent to A AND B.
Of course, this takes two NAND gates to construct a single AND gate, but no one said that circuits constructed only with NAND gates would be optimal, only that it is possible to do.
The remaining gate we need to synthesize is the logical-OR gate. We can easily construct an OR gate from NAND gates by applying DeMorgan's theorems.
(A or B)' = A' and B' DeMorgan's Theorem. A or B = (A' and B')' Invert both sides of the equation. A or B = A' nand B' Definition of NAND operation.
By applying these transformations, you get the circuit:
Now you might be wondering why we would even bother with this. After all, why not just use logical AND, OR, and inverter gates directly? There are two reasons for this. First, NAND gates are generally less expensive to build than other gates. Second, it is also much easier to build up complex integrated circuits from the same basic building blocks than it is to construct an integrated circuit using different basic gates.
Note, by the way, that it is possible to construct any logic circuit using only NOR gates. The correspondence between NAND and NOR logic is orthogonal to the correspondence between the two canonical forms appearing in this chapter (sum of minterms vs. product of maxterms). While NOR logic is useful for many circuits, most electronic designs use NAND logic. See the exercises for more examples.
S = AB' + A'B Sum of A and B. C = AB Carry from addition of A and B.
These two boolean functions implement a half-adder. Electrical engineers call it a half adder because it adds two bits together but cannot add in a carry from a previous operation. A full adder adds three one-bit inputs (two bits plus a carry from a previous addition) and produces two outputs: the sum and the carry. The two logic equations for a full adder are
S = A'B'C + A'BC' + AB'C' + ABC Cout = AB + AC + BC
Although these logic equations only produce a single bit result (ignoring the carry), it is easy to construct an n-bit sum by combining adder circuits:
So, as this example clearly illustrates, we can use logic functions to implement arithmetic and boolean operations.
Another common combinatorial circuit is the seven-segment decoder. This is a combinatorial circuit that accepts four inputs and determines which of the seven segments on a seven-segment LED display should be on (logic one) or off (logic zero). Since a seven segment display contains seven output values (one for each segment), there will be seven logic functions associated with the display (segment zero through segment six). See the figure below for the segment assignments.
The figure below shows the segment assignments for each of the ten decimal values.
The four inputs to each of these seven boolean functions are the four bits from a binary number in the range 0..9. Let D be the H.O. bit of this number and A be the L.O. bit of this number. Each logic function should produce a one (segment on) for a given input if that particular segment should be illuminated. For example S4 (segment four) should be on for binary values 0000, 0010, 0110, and 1000. For each value that illuminates a segment, you will have one minterm in the logic equation:
S4 = D'C'B'A' + D'C'BA' + D'CBA' + DC'B'A'.
So, as a second example, is on for values zero, two, three, five, six, seven, eight, and nine. Therefore, the logic function for S0 is
S0 = D'C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'A' + DC'B'A
You can generate the other five logic functions in a similar fashion (see the exercises).
Combinatorial circuits are the basis for many components of a basic computer system. You can construct circuits for addition, subtraction, comparison, multiplication, division, and many other operations using combinatorial logic.
The S and R inputs are normally high. If you temporarily set the S input to zero and then bring it back to one (toggle the S input), this forces the Q output to one. Likewise, if you toggle the R input from one to zero back to one, this sets the Q output to zero. The Q' input is generally the inverse of the Q output.
Note that if both S and R are one, then the Q output depends upon Q. That is, whatever Q happens to be, the top NAND gate continues to output that value. If Q was originally one, then there are two ones as inputs to the bottom flip-flop (Q nand R). This produces an output of zero (Q'). Therefore, the two inputs to the top NAND gate are zero and one. This produces the value one as an output (matching the original value for Q).
If the original value for Q was zero, then the inputs to the bottom NAND gate are Q=0 and R=1. Therefore, the output of this NAND gate is one. The inputs to the top NAND gate, therefore, are S=1 and Q'=1. This produces a zero output, the original value of Q.
Suppose Q is zero, S is zero and R is one. This sets the two inputs to the top flip-flop to one and zero, forcing the output (Q) to one. Returning S to the high state does not change the output at all. You can obtain this same result if Q is one, S is zero, and R is one. Again, this produces an output value of one. This value remains one even when S switches from zero to one. Therefore, toggling the S input from one to zero and then back to one produces a one on the output (i.e., sets the flip-flop). The same idea applies to the R input, except it forces the Q output to zero rather than to one.
There is one catch to this circuit. It does not operate properly if you set both the S and R inputs to zero simultaneously. This forces both the Q and Q' outputs to one (which is logically inconsistent). Whichever input remains zero the longest determines the final state of the flip-flop. A flip-flop operating in this mode is said to be unstable.
The only problem with the S/R flip-flop is that you must use separate inputs to remember a zero or a one value. A memory cell would be more valuable to us if we could specify the data value to remember on one input and provide a clock input to latch the input value. This type of flip-flop, the D flip-flop (for data) uses the circuit;
Assuming you fix the Q and Q' outputs to either 0/1 or 1/0, sending a clock pulse that goes from zero to one back to zero will copy the D input to the Q output. It will also copy D' to Q'. The exercises at the end of this chapter will expect you to describe this operation in detail, so study this diagram carefully.
Although remembering a single bit is often important, in most computer systems you will want to remember a group of bits. You can remember a sequence of bits by combining several D flip-flops in parallel. Concatenating flip-flops to store an n-bit value forms a register. The electronic schematic in the figure below shows how to build an eight-bit register from a set of D flip-flops.
Note that the eight D flip-flops use a common clock line. This diagram does not show the Q' outputs on the flip-flops since they are rarely required in a register.
D flip-flops are useful for building many sequential circuits above and beyond simple registers. For example, you can build a shift register that shifts the bits one position to the left on each clock pulse. A four-bit shift register appears below:
You can even build a counter, that counts the number of times the clock toggles from one to zero and back to one using flip-flops. The circuit in the figure below implements a four bit counter using D flip-flops.
Surprisingly, you can build an entire CPU with combinatorial circuits and only a few additional sequential circuits beyond these.
if statement or while loop). By applying transformations like DeMorgan's theorems or a mapping optimization it is often possible to improve the performance of high level language code. Therefore, studying boolean functions is important even if you never intend to design an electronic circuit. It can help you write better code in a traditional programming language.if ((x=y) and (a <> b)) or ((x=y) and (c <= d)) then SomeStmt;
You can use the distributive law to simplify this to:
if ((x=y) and ((a <> b) or (c <= d)) then SomeStmt;
Likewise, we can use DeMorgan's theorem to reduce
while (not((a=b) and (c=d)) do Something;
to
while (a <> b) or (c <> d) do Something;
/************************************************************************/
/* */
/* This C program demonstrates how to write a generic logic function */
/* that can compute any logic function of four variables. Given C's */
/* bit manipulation operators, along with hexadecimal I/O, this is an */
/* easy task to accomplish in the C programming language. */
/* */
/************************************************************************/
#include <stdlib.h>
#include <stdio.h>
/* Generic logic function. The "Func" parameter contains the 16-bit */
/* logical function number. This is actually an encoded truth table */
/* for the function. The a, b, c, and d parameters are the inputs to */
/* the logic function. If we treat "func" as a 2x2x2x2 array of bits, */
/* this particular function selects bit "func[d,c,b,a]" from func. */
int
generic(int func, int a, int b, int c, int d)
{
/* Return the bit specified by a, b, c, and d */
return (func >> (a + b*2 + c*4 + d*8)) & 1;
}
/* Main program to drive the generic logic function written in C. */
main()
{
int func, a, b, c, d;
/* Repeat the following until the user enters zero. */
do
{
/* Get the function's number (truth table) */
printf("Enter function value (hex): ");
scanf("%x", &func);
/* If the user specified zero as the function #, stop */
/* the program. */
if (func != 0)
{
printf("Enter values for d, c, b, & a: ");
scanf("%d%d%d%d",
&d, &c, &b, &a);
printf("The result is %d\n", generic(func,a,b,c,d));
printf("Func = %x, A=%d, B=%d, C=%d, D=%d\n",
func, a, b, c, d);
}
} while (func !=0);
}
The following Pascal program is written for Standard Pascal. Standard Pascal does not provide any bit manipulation operations, so this program is lengthy since it has to simulate bits using an array of integers. Most modern Pascals (especially Turbo Pascal) provide built-in bit operations or library routines that operate on bits. This program would be much easier to write using such non-standard features.
program GenericFunc(input,output);
(* Since standard Pascal does not provide an easy way to directly man- *)
(* ipulate bits in an integer, we will simulate the function number *)
(* using an array of 16 integers. "GFTYPE" is the type of that array. *)
type
gftype = array [0..15] of integer;
var
a, b, c, d:integer;
fresult:integer;
func: gftype;
(* Standard Pascal does not provide the ability to shift integer data *)
(* to the left or right. Therefore, we will simulate a 16-bit value *)
(* using an array of 16 integers. We can simulate shifts by moving *)
(* data around in the array. *)
(* *)
(* Note that Turbo Pascal *does* provide shl and shr operators. How- *)
(* ever, this code is written to work with standard Pascal, not just *)
(* Turbo Pascal. *)
(* *)
(* ShiftLeft shifts the values in func on position to the left and in- *)
(* serts the shiftin value into "bit position" zero. *)
procedure ShiftLeft(shiftin:integer);
var i:integer;
begin
for i := 15 downto 1 do func[i] := func[i-1];
func[0] := shiftin;
end;
(* ShiftNibble shifts the data in func to the left four positions and *)
(* inserts the four bits a (L.O.), b, c, and d (H.O.) into the vacated *)
(* positions. *)
procedure ShiftNibble(d,c,b,a:integer);
begin
ShiftLeft(d);
ShiftLeft(c);
ShiftLeft(b);
ShiftLeft(a);
end;
(* ShiftRight shifts the data in func one position to the right. It *)
(* shifts a zero into the H.O. bit of the array. *)
procedure ShiftRight;
var i:integer;
begin
for i := 0 to 14 do func[i] := func[i+1];
func[15] := 0;
end;
(* ToUpper converts a lower case character to upper case. *)
procedure toupper(var ch:char);
begin
if (ch in ['a'..'z']) then ch := chr(ord(ch) - 32);
end;
(* ReadFunc reads a hexadecimal function number from the user and puts *)
(* this value into the func array (bit by bit). *)
function ReadFunc:integer;
var ch:char;
i, val:integer;
begin
write('Enter function number (hexadecimal): ');
for i := 0 to 15 do func[i] := 0;
repeat
read(ch);
if not eoln then begin
toupper(ch);
case ch of
'0': ShiftNibble(0,0,0,0);
'1': ShiftNibble(0,0,0,1);
'2': ShiftNibble(0,0,1,0);
'3': ShiftNibble(0,0,1,1);
'4': ShiftNibble(0,1,0,0);
'5': ShiftNibble(0,1,0,1);
'6': ShiftNibble(0,1,1,0);
'7': ShiftNibble(0,1,1,1);
'8': ShiftNibble(1,0,0,0);
'9': ShiftNibble(1,0,0,1);
'A': ShiftNibble(1,0,1,0);
'B': ShiftNibble(1,0,1,1);
'C': ShiftNibble(1,1,0,0);
'D': ShiftNibble(1,1,0,1);
'E': ShiftNibble(1,1,1,0);
'F': ShiftNibble(1,1,1,1);
else write(chr(7),chr(8));
end;
end;
until eoln;
val := 0;
for i := 0 to 15 do val := val + func[i];
ReadFunc := val;
end;
(* Generic - Computes the generic logical function specified by *)
(* the function number "func" on the four input vars *)
(* a, b, c, and d. It does this by returning bit *)
(* d*8 + c*4 + b*2 + a from func. *)
function Generic(var func:gftype; a,b,c,d:integer):integer;
begin
Generic := func[a + b*2 + c*4 + d*8];
end;
begin (* main *)
repeat
fresult := ReadFunc;
if (fresult <> 0) then begin
write('Enter values for D, C, B, & A (0/1):');
readln(d, c, b, a);
writeln('The result is ',Generic(func,a,b,c,d));
end;
until fresult = 0;
end.
The following code demonstrates the power of bit manipulation operations. This version of the code above uses special features present in the Turbo Pascal programming language that allows programmers to shift left or right and do a bitwise logical AND on integer variables:
program GenericFunc(input,output);
const
hex = ['a'..'f', 'A'..'F'];
decimal = ['0'..'9'];
var
a, b, c, d:integer;
fresult:integer;
func: integer;
(* Here is a second version of the Pascal generic function that uses *)
(* the features of Turbo Pascal to simplify the program. *)
function ReadFunc:integer;
var ch:char;
i, val:integer;
begin
write('Enter function number (hexadecimal): ');
repeat
read(ch);
func := 0;
if not eoln then begin
if (ch in Hex) then
func := (func shl 4) + (ord(ch) and 15) + 9
else if (ch in Decimal) then
func := (func shl 4) + (ord(ch) and 15)
else write(chr(7));
end;
until eoln;
ReadFunc := func;
end;
(* Generic - Computes the generic logical function specified by *)
(* the function number "func" on the four input vars *)
(* a, b, c, and d. It does this by returning bit *)
(* d*8 + c*4 + b*2 + a from func. This version re- *)
(* lies on Turbo Pascal's shift right operator and *)
(* its ability to do bitwise operations on integers. *)
function Generic(func,a,b,c,d:integer):integer;
begin
Generic := (func shr (a + b*2 + c*4 + d*8)) and 1;
end;
begin (* main *)
repeat
fresult := ReadFunc;
if (fresult <> 0) then begin
write('Enter values for D, C, B, & A (0/1):');
readln(d, c, b, a);
writeln('The result is ',Generic(func,a,b,c,d));
end;
until fresult = 0;
end.
Number of Web Site Hits since Jan 1, 2000: