Simplification of Boolean functions

1 Draft notes or 22C: 0402 Simplification of Boolean functionsUsing the theorems of Boolean Algebra, the algebraicforms of functions can often be simplified, which leads tosimpler (and cheaper) 1F = + + (B + B) + How many gates do you save= + from this Simplification ?=A + FBFCCD raft notes or 22C: 0403 Example 2F= + + + + + + + + ( + ) + ( + ) + ( + )=(A + A). + (B + B). + (C + C). + + 3 Show that A + = AA + AB= + (1 + B)=A. 1=ADraft notes or 22C: 0404 Simplification using Karnaugh MapsAB01101K-map of 2-variable OR function011 BCA000111100 11111K-map of majority functionFollow the class lectures to understand how tosimplify Boolean functions using K-maps.

2 Severalexamples will be worked out in the notes or 22C: 0405 Other types of gatesAA A+BBNAND gateNOR gateBe familiar with the truth tables of these + B = + OR (XOR) gateDraft notes or 22C: 0406 NAND and NOR are universal gatesAny function can be implemented using only NANDor only NOR gates. How can we prove this?(Proof for NAND gates)Any Boolean functioncan be implemented using AND, OR and NOT if AND, OR and NOT gates can be implementedusing NAND gates only, then we prove our Implement NOT using NANDA ADraft notes or 22C: 04072. Implementation of AND using NANDA A1.

3 Implementation of OR using NANDAA = A+BBB (Exercise) Prove that NOR is a universal notes or 22C: 0408 Example (to be worked out in class)How to convert any circuit that uses AND, OR and NOTgates to a version that uses NAND (or NOR gates only)?Additional properties of XORXOR is also called modulo-2 addition. Why?ABCF0000A B = 1 only when there are an0011odd number of 1 s in (A,B). The0101same is true for A B C 1 A = AWhy? 0 A = ADraft notes or 22C: 0409 Logic Design ExerciseHalf AdderABSCASum (S)0000 BCarry (C)01101010S = A B1101C = notes or 22C: 04010 Full Adder Sum (S)AB CSCoutA00000B00110 Cin Carry (Cout)010100110110010101011100111111S = A B CinCout = + + can you add two 32-bit numbers?

4 It will bediscussed in the notes or 22C: 04011 Combinational vs. Sequential CircuitsCombinational output depends only on the current values ofthe inputs and not on the past values. Examples areadders, subtractors, and all the circuits that we havestudied so farSequential output depends not only on the current valuesof the inputs, but also on their past values. These holdthe secret of how to memorize information. We will studysequential circuits notes or 22C: 04012 DecodersA typical decoder has n inputs and 2n D0000001A D1010010B D2100100 D3111000A 2-to-4 decoder and its truth = Draw the circuit of this = = decoder works per specsD0 = (Enable = 1).

5 When Enable = 0,all the outputs are a 3-to-8 notes or 22C: 04013 EncodersA typical encoder has 2n inputs and n 100000D1 A010001D2 B001010D3 000111A 4-to-2 encoder and its truth = D1 + D3B = D2 + D3 Draft notes or 22C: 04014 MultiplexorIt is a many-to-one switch, also called a FS = 0, F = AB1S = 1, F = BControl SSpecifications of the muxA 2-to-1 muxF = S. A + S. a 4-to-1 notes or 22C: 04015 Another design of a decoderAB FCDSE xercise 1. Design a 2-to-4 decoder using 1-to-2 decoders 2. Design a 4-to-1 multiplexor using 2-1 multiplexors be discussed in the D1 D2 D32-to-4 decoderDraft notes or 22C: 04016 DemultiplexorsA demux is a one-to-many switch.

6 0XS = 0, X = AA 1YS = 1, Y = B SA 1-to-2 demux, and its , X = S. A, and Y = S. BExercise. Design a 1-4 will discuss the design of a 1-bit ALU in class.