# Prologue to Computerized Rationale Outline Reference section An of CO&A Dr. Farag - PowerPoint PPT Presentation  Prologue to Computerized Rationale Outline Reference section An of CO&A Dr. Farag

## Prologue to Computerized Rationale Outline Reference section An of CO&A Dr. Farag

##### Presentation Transcript

1. Outline • Boolean Algebra • Gates • Combinational Circuits • Simplifications of Boolean Functions • Multiplexers, Decoders, PLA, ROM, Adders • Sequential Circuits • Flip-Flops • Registers • Counters

2. Boolean Algebra • Similar to traditional algebra but it defines a set of logical operations and variables • Basic operations: AND, OR, NOT (., +, _) • These operations are defined by their truth tables • Other operations can be derived from the basic ones. Ex: NAND, NOR, XOR, XNOR

3. Boolean Algebra (Cont) • It defines a set of postulates and another set of identities that can be derived from these postulates • A NAND E = NOT(AE) = Ā OR Ē. Proof?

4. Gates • To implement any logic function we need a functionally complete set of gates. Ex (AND, OR, NOT), (AND, NOT), (OR, NOT) (NAND), (NOR) • How to implement all basic functions by NAND?? Examine its truth table. Same for NOR • From manufacturing point of view, using only one type of gates to implement the circuit is very advantageous. Why? Regular -> Simple -> easy to design -> cheap • Gates are the basic building blocks of all digital systems. They are implemented using electronics components (transistors, diodes, resistors, etc.) • Different families are TTL, CMOS, ECL, etc. Not our problem

5. Combinational Logic Circuits • It is an interconnected set of gates whose output at any times depends solely on the input at that instant of time. (NOT on a previous output state) • These circuits have n inputs & m outputs. • They can be defined in terms of truth tables, circuits diagrams, or Boolean equations • Implement the following truth by using SOP or POS. Check equivalency

6. Combinational Logic Circuits (simplification) • Simplification: algebraic rules, karnaugh maps, or Quine-McKluskey tables • The output of Table 3 can be expressed: • F = A’BC’ + A’BC + ABC’ = B(A’+C’) ?? • Problem: algebraic rules depend mainly upon observation & experience • A more systematic way to simplify digital logic expressions is the use of karnaugh maps

7. Combinational Logic Circuits (Karnaugh) • The map is an array of 2n squares (n # of inputs) • How do you fill the map from a truth table?? • To use an expression, it should be in canonical form • General rules of using the map: • Combine ones into groups of (1, 2, 4, 8, …) squares • Form the largest group size • Form the min number of groups • Two group should not intersect unless this will enable a small group to be larger in size • Some input combinations shall not occur and in this situation we call the outputs, “do not care” conditions • These “ds” can be used as either 1 or 0 • Example: designing an incrementer for a BCD number, see Table 4 and Figure 10 in the following slide

8. Combinational Logic Circuits (Karnaugh) • Exercise: Design a 4-bit combinational circuit 2’s complementer (The output generates the 2’s complement of the input binary number)

9. Combinational Logic Circuits (QMA) • Quine-Mckluskey Algorithm is a systematic method to obtain the minimum form of a Boolean expression • The details of the algorithm are described in the handout • The algorithm is best described by an example • Minimize the following function • F(A, B, C, D) = Σ (1, 5, 6, 7, 11, 12, 13, 15) • This can be expresses as F = A’B’C’D + A’BC’D + A’BCD’ + A’BCD + AB’CD + ABC’D’ + ABC’D + ABCD • The minimal expression is F = A’C’D + A’BC + ABC’ + ACD • Quiz: Try it using the decimal approach

10. Applications of Combinational Logic Circuits • NAND and NOR implementation • Multiplexer: a circuit that has multiple inputs and only one output. At any time one of the input is selected as output based on the value on the select line(s) • Below is the truth table for a 4-to-1 multiplexer • Implementation?? Application ex: Inputs to PC

11. Applications of Combinational Logic (Cont) • A decoder has n input lines and 2n output lines. Only one output line is selected based on the input • Example: Instruction Op code decoding • With an additional input line, a decoder can be used as a demultiplexer which connects its single input to one of its outputs based on the value on the address lines • PLA (Programmable Logic Array) has the objective of developing a general purpose chip that can be readily adapted to specific purposes • It can be implemented by making every possible connection through a fuse. Undesired connections are removed by blowing their fuses • This kind is called field-PLA • See next slide

12. Applications of Combinational Logic (Cont)

13. Applications of Combinational Logic (Cont) • ROM is considered a combinational circuit because the outputs are a function only of the current inputs

14. Applications of Combinational Logic (Cont) • How to implement the function of ALU. The basic circuit is the binary adder • Sum = A’B’C + A’BC’ + ABC + AB’C’ • Carry = AB + AC + BC • Implementation??