Structured Computer Organization, by Tanenbaum
Chapter 3: The Digital Logic Level (L0)

• The basic elements from which all digital computers are constructed are
  amazingly simple. Chapter 3 looks at these basic elements and also at the
  special two-valued algebra used to analyze them - Boolean Algebra.
  
  
• Digital circuits can be constructed from a small number of primitive
  elements by combining these elements in innumerable ways.
  
  
• A digital circuit is one in which only two logical values are present.
  
  • Binary 0: A signal between 0 and 1 volt
  • Binary 1: A signal between 2 and 5 volts
  • Voltages outside of these two ranges are not permitted
  
  
• Gates: tiny electronic devices that can compute various functions of these
  two-valued signals. These gates form the hardware basis on which all digital
  computers are built.
  
  
• Fig. 3-1: a bipolar transistor embedded in a simple circuit. The transistor has three connections to the outside world: the collector, the base, and the
  emitter
  • When the input voltage, Vin, is below a certain critical value, the
    transistor turns off and acts like an infinite resistance.
  • This causes the output of the circuit, Vout, to take on a value close to
    Vcc, an externally regulated voltage, typically +5 volts.
  • When Vin exceeds the critical value, the transistor switches on and acts
    like a wire, causing Vout to be pulled down to ground - by convention, 0 volts.
  
  
• When Vin is low, Vout is high, and vice versa.
  
  
• This circuit is an inverter, converting a logical 0 to a logical 1, and
  a logical 1 to a logical 0.
  
  
• The time required to switch from one state to the other is typically a
  a few nanoseconds.
  
  
• Fig. 3-1b: two transistors cascaded in series:a NAND gate.
  If both V1 and V2 are high, both transistors will conduct and Vout will be
  pulled low. If either input islow, the corresponding transistor will turn off,
  and the output will be high.
  
  
• NAND gate: Vout will be low if and only if both V1 and V2 are high.
  
  
• Fig3-1C: The two transistors are wired in parallel:NOR gate.
  If either input is high the corresponding transistor will turn on and pull
  the output down to ground. If both inputs are low, the output will remain high.
  
  
• NOT, NAND, NOR: These three circuits form the three simplest gates.
  
  
• AND gate: feed the output of a NAND gate into an inverter (NOT gate)
  AND gate is 1 if and only if both inputs are 1.
  
  
• OR gate: feed the output of a NOR gate into an inverter.
  OR gate is 1 if either or both inputs is 1, but 0 if both inputs are 0.
  
  
• NOT, NAND, NOR, AND, OR: These five gates are the principal building
  blocks of the digital logic level.
  
  
• NAND and NOR gates require two transistors each, NOT requires 1 transistor.
  AND and OR gates require three each.
  
  
• Boolean Algebra - To describe circuits that can be built by combining gates,
  a type of algebra is needed that can take on only the values 0 and 1.
  
  
• A Boolean function of n variables has only 2^n possible combinations of
  input values. This function can be completely described by giving a table
  2^n rows, each row telling the value of the function for a different
  combination of input values.
  
  
• This table is called a truth table.
  
  
• We agree to always list the rows of the truth table in numerical order (base 2)i,
  that is, for two variables in the order 00, 01, 10, and 11.
  
  
• The function can be completely described by the 2^n-bit binary number
  obtained by reading the result column of the truth table vertically.
  • NAND is 1110
  • NOR is 1000
  • AND is 0001
  • OR is 0111
  
  
• Only 16 Boolean functions of two variables exist, corresponding to the
  16 possible 4-bit result strings.
  
  
• Fig. 3-3(a): the truth table for the majority function for 3 variables.
  This function = 0 if a majority of its inputs are 0 and 1 if the majority
  of its inputs are 1.
  • There are 6 possible values: A,B,C, not A, not B, and not C
  • There are four AND gates with three inputs each
  • These four AND gates feed into an OR gate.
  • The four AND gates represent the four successful combinations where the
    output will be 1: not A, B, C OR A, not B, C OR A, B, not C OR A,B,C
  
  
• Implementing a circuit for any Boolean function
  • Write down the truth table for the function (see Fig.3-3)
  • Provide inverters to generate the complement of each input
  • Draw an AND gate for each term with a 1 in the result column
  • Wire the AND gates to the appropriate inputs
  • Feed the ouput of all the AND gates into an OR gate
  
  
• Circuit Equivalence: Circuit designers often try to reduce the number of
  gates in their products. To reduce the complexity of a circuit, the designer
  must find another circuit that computes the same function as the original
  but does so with fewer gates.
  
  
• Boolean Algebra can be a valuable tool in the search for equivalent circuits
  
  
• Example: AB + AC can be simplified to A(B + C) using the distributive property
  
  • AB + AC has two AND gates and one OR gate (three gates total)
    
    • AND gate #1 has inputs A,B
    • AND gate #2 has inputs A,C
    • OR gate has the two inputs from the two AND gates
  • A(B + C) has one AND gate and one OR gate (two gates total)
    
    • OR gate has inputs B, C
    • AND gate has the two inputs: A and the output from the OR gate (B + C)
  
  
• In general, a circuit designer starts with a Boolean function and applies
  the laws of Boolean algebra to it in an attempt to find a simpler but
  equivalent expression.
  
  
• Identities from Boolean algebra:
  • Duals: by interchanging AND and OR and also 0 and 1, either form
    can be produced from the other one.

  •  
        Name            AND form           OR form
    
    Identify law        1A = A             0 + A = A
    Null law            0A = 0             1 + A = 1
    Idempotent law      AA = A             A + A = A
    Inverse law         A~A = 0            A + ~A = 1
    Commutative law     AB = BA            A + B = B + A
    Associative law     (AB)C = A(BC)      (A + B) + C = A + (B + C)
    Distributive law   A + BC = (A + B)(A + C)    A(B + C) = AB + AC
    Absorbtion law     A(A + B) = A        A + AB = A
    DeMorgan's law     ~(AB) = ~A + ~B     ~(A + B) = ~A~B
    
      

  
  
• DeMorgan's law can be used to convert between NAND gates and NOR gates
  and also equivalent representations of AND and OR gates
  
  
• A NAND gate is equivalent to an OR gate with inverted inputs
  ~(AB) = ~A + ~B
  
  
• A NOR gate is equivalent to an AND gate with inverted inputs
  ~(A + B) = ~A~B
  
  
• An AND gate is equivalent to an OR gate with both inputs inverted and
  the output inverted
  AB = ~(~A + ~B) = ~~A~~B = AB
  
  
• An OR gate is equivalent to an AND gate with both inputs inverted and
  the output inverted
  A + B = ~(~A~B) = ~~A + ~~B = A + B
  
  
• Fig. 3-8: Three different circuits for computing the XOR function.
  • Fig B: 1's in the right-hand column of the truth table occur for
    ~A and B, also A and ~B. These two pairs of inputs are put through
    AND gates and OR'd together.
  • Fig C: Same as Fig B, except the AND outputs are inverted (NAND, and then
    inverted again as inputs to the OR (NOR)
  • Fig C. The NOR gate with two inverted inputs is equivalent to a NAND gate
    - see Fig. 3-7
  
  
• Integrated Circuits - Gates are not sold individually but rather in units
  called Integrated Circuits, called ICs or chips.
  
  
• DIPS - the packages with two rows of pins outside and ICs inside are
  Dual Inline Packages (DIPS)
  
  
• Classes of chips:
  1. SSI (Small Scale Integrated) circuit: 1 to 10 gates
  2. MSI (Medium Scale Integrated) circuit: 10 to 100 gates
  3. LSI (Large Scale Integrated) circuit: 100 to 100,000 gates
  4. VLSI (Very Large Scale Integrated) circuit: > 100,000 gates
  
  
• Combinationsl Circuits - a circuit with multiple inputs and multiple
  outputs in which the outputs are uniquely determined by the current inputs.
  
  
• Multiplexer - a circuit with 2^n data inputs, one data output, and
  n control inputs that select one of the data inputs.
  
  
• Fig. 3-11: An eight-input multiplexer
  • 2^3 = 8 inputs (n = 3)
  • 3 control lines (n control lines)
  • The 3 control lines, A, B, and C encode a 3-bit number that specifies
    which of the eight input lines is gated to the OR gate (the output)
  • 000 selects Data input 0, D0
    001 selects Data input 1, D1
    010 selects Data input 2, D2
    011 selects Data input 3, D3
    etc.
  
  
• Fig. 3-12: a multiplexer for the majority function. For each combination of
  A,B,and C, one of the data input lines is selected.
  • 000 selects D0, 001 selects D1, 010 selects D2, etc.
  • Data lines D0, D1, D2, and D4 output 0 and are connected to ground
  • Data lines D3, D5, D6, and D7 output 1 and are connected to Vcc
  • See the truth table on p. 121
  
  
• Demultiplexer - inverse of the multiplexer: routes its single input signal
  to one of 2^n outputs, depending on the values of the n control lines.
  If the binary value on the control lines is k, output k is selected.
  
  
• Decoder: a circuit that takes an n-bit number as input and uses it to
  select (set to 1) exactly one of the 2^n output lines.
  
  
• Fig 3-13: a decoder where n = 3, this takes a 3-bit number as input
  and selects one of the 2^3 = 8 ouputs lines
  
  
• Comparator - compares two input words
  
  
• Fig 3-14: a comparator that takes two inputs, each of length 4 bits.
  Produces 1 if they are equal and a 0 if they are not equal.
  • The circuit is based on the XOR gate.
  • If the two inputs are equal, all four of the XOR gates output 0.
  • These results are ORed together.
  • If the output is 0, the input words are equal.
  • A NOR gate is used to reverse the sense of the test: 1 is equal, 0 is not
  
  
• Arithmetic Circuits - shifters and adders
  
  
• Fig. 3-16: An eight-input, eight-output shifter.
  • Eight bits of input are on lines D0..D7.
  • The output is the input shifted 1 bit. The output is on lines S0..S7
  • The control line, C, determines the direction of the shift, 0 for left
    and 1 for right.
  • When C = 1, the right member of each pair is turned on. The right
    AND gate is wired to the input of the OR gate to its right, a right
    shift is performed.
  • When C = 0, the left member of the AND gate pair turns on, doing a
    left shift.
  
  
• Adders - A hardware circuit for performing addition is an essential part
  of every CPU.
  
  
• See the truth table for addition on 1-bit integers, Fig3-17
• Two outputs are present:
  • The sum of the inputs
  • The carry to the next (leftward) position
  
  
• Half-adder, Fig. 3-17b: a circuit for computing both the sum bit and
  the carry bit.
  
  
• The half-adder does not handle the carry into the position from the right.
  
  
• The full-adder handles the carry from the right. A full adder is built
  up from two half adders.
  • The Sum ouput line is 1 if
    • either A and B are both 1 (left input to the
      OR gate
    • or exactly one of them is 1 and the Carry in bit is also 1.
    
    
  • Together, the two half adders generate both the sum and the carry bits
  
  
  
• To build an adder for two 16-bit words, replicate the circuit of
  Fig. 3-18b 16 times. The carry out of a bit is used as the carry into
  its left neighbor. The carry into the rightmost bit is wired to 0.
  • This type of adder is called a ripple carry adder
  • In the worst case, adding a 1 to 111...111, the addition doesn't
    complete until the carry has rippled all the way from the rightmost to the
    leftmost bit.
  • Faster adders are ones without this delay (a different design)
  
  
• Arithmetic Logic Units, Fig 3-19: A 1-bit ALU
  • This can compute one of four functions:
    • A AND B, A OR B, ~B, A + B (sum)
  • The four functions are selected by the two function-select input lines,
    F0 and F1, which contain:
    • 00 for AB, 01 for A+B (OR), 10 for ~B, and 11 for A + B (sum)
  
  
• Clocks: See Chap. 3 pt. 2