CS 3501 - Chapter 3 (3A and 10.2.2) Dr. Clincy Professor of CS Dr. Clincy Lecture Slide 1 Kmap Simplification for Four Variables Our model can be extended to accommodate the 16 minterms that are produced by a four-input function. This is the format for a 16-minterm Kmap. Dr. Clincy Lecture 2 Kmap Simplification Example for Four Variables

We have populated the Kmap shown below with the nonzero minterms from the function: Reduced to: Dr. Clincy Lecture 3 Kmap Simplification for Four Variables It is possible to have a choice as to how to pick groups within a Kmap, while keeping the groups as large as possible. The (different) functions that result from the groupings below are logically equivalent. Dr. Clincy

Lecture 4 Dont Care Conditions Real circuits dont always need to have an output defined for every possible input. For example, some calculator displays consist of 7segment LEDs. These LEDs can display 2 7 -1 patterns, but only ten of them are useful. If a circuit is designed so that a particular set of inputs can never happen, we call this set of inputs a dont care condition. They are very helpful to us in Kmap circuit simplification. Dr. Clincy Lecture 5 Dont Care Conditions

In a Kmap, a dont care condition is identified by an X in the cell of the minterm(s) for the dont care inputs, as shown below. In performing the simplification, we are free to include or ignore the Xs when creating our groups. Reduction using dont cares: Dr. Clincy Lecture 6 Could have the case where some input combinations do not need to be evaluated these input combinations are called dont cares For a k-map, use dont cares in the case of creating groups of 2, 4, 8, set of 1s use dont

cares as 1s to help minimize the circuit at least one 1 has to be in a group of dont cares Dont Care Example More Kmap Examples When adjacent squares contain 1s, indicates the possibility of an algebraic simplication Example of a 3variable k-map Inputs around edge and output in the boxes Half Adder Combinational Circuits Combinational logic circuits give us many useful devices. One of the simplest is the half adder, which finds the sum of two bits. We can gain some insight as to the construction of a half adder by looking at its truth table, shown at the right.

Dr. Clincy Lecture 9 Full Adder Combinational Circuits We can change our half adder into to a full adder by including gates for processing the carry bit. The truth table for a full adder is shown at the right. Dr. Clincy Lecture 10 Adders - Combinational Circuits Just as we combined half adders to make a full

adder, full adders can be connected in series. The carry bit ripples from one adder to the next; hence, this configuration is called a ripple-carry adder. Todays systems employ more efficient adders. Dr. Clincy Lecture 11 Decoder - Combinational Circuits Among other things, they are useful in selecting a memory location according to a binary value placed on the address lines of a memory bus. This is what a 2-to-4 decoder looks like on the inside. If x = 0 and y = 1, which output line is enabled? Output - Decoded message

Input - Encoded message Dr. Clincy Lecture 12 Decoder another example Dr. Clincy Lecture 13 Multiplexer - Combinational Circuits A multiplexer does just the opposite of a decoder. It selects a single output from several inputs. This is what a 4-to-1 multiplexer looks like on the inside. Depending the select input

combination, 1 of 4 data inputs is chosen for output Dr. Clincy Lecture If S0 = 1 and S1 = 0, which input is transferred to the 14 output? Multiplexer - Combinational Circuits Can also use multiplexers to implement logic functions Given this truth table, group X1,X2 being 00, 01, 10 and 11 notice what happens with X3 x1 x2 x 3

f 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1

0 0 1 1 0 1 0 1 0 1 0 1 0 x3 1 5-input truth table can be done with a 16-input mux Etc.. Dr. Clincy MUX

f 0 0 0 0 1 x3 1 0 1 1 1

x3 f x3 3-input truth table can be done with a 4-input mux 4-input truth table can be done with a 8-input mux x1 x2 x1 Figure A.39. x2 Multiplexer implementation of a logic function. Also explain how the Mux is used to implement data comms FDM and TDM Lecture

15 10.2.2 - Programmable Logic Devices (PLD) I1 x1 x2 xn Input buffers and inverters I2n All possible combinations of inputs ANDed

AND array P1 All possible combinations of ANDed inputs ORed Figure A.40. Pk f1 O1 OR array

Output buffers Om fm A block diagram for a PLD. Re-explain Sums of Products and relationship to PLDs Dr. Clincy Lecture 16 10.2.2 - Programmable Logic Array (PLA) Ability to program a PLD, is called a PLA

Dr. Clincy Lecture 17 10.2.2 - Programmable Array Logic (PAL) For a PLA, both the AND array and OR array are programmable For a PAL, the AND array is programmable and the OR array is fixed Dr. Clincy Lecture 18 PAL-like block PAL-like block

I/O block CPLDs are comprised of 2 or more PALs I/O block 10.2.2 - Complex Programmable Logic Devices (CPLDs) PAL-like block PAL-like block I/O block I/O block Interconnection wires Figure A.45. Structure of a complex programmable logic device (CPLD).

Dr. Clincy Lecture 19 10.2.2 - Field Programmable Gate Arrays (FPGAs) I/O block I/O block FPGA overcome this size limitation by using a general interconnection. I/O block PAL chips are somewhat limited in size due to the fact they have output pins for each sum-of-product circuit General interconnection PAL

I/O block Logic block Interconnection switch Dr. Clincy Figure A.46. Lecture A conceptual block diagram of an FPGA. 20