Computer Architecture
Test 2 Topics
(this test is scheduled for the week of March 19)

  1. Mic 1 microcode
    • Translating a microinstruction into 32 bit microcode
    • Translating 32 bit microcode into a microinstruction
  2. Hamming code
    • Given the transmission data, find the errors (if any)
    • Given the data to send, encode with the Hamming algorithm

  3. Huffman data compression
  4. Hypercube question(s)
    • Finding the neighbors of given node(s)
    • Finding the path(s) from a Start node to a Destination node.

  5. Chapter 3 - The Digital Logic Level - Summary of figures to understand:
    • Fig.3-2: Basic symbols and truth tables
      NOT, NAND, NOR, AND, OR
    • Fig.3-3a: Truth table for the majority function
    • Fig.3-3b: Circuit drawing for the majority function
      • An AND gate for every 1 in column M (the result column)
      • A control line for every input variable, A,B,C
        (think of these as being used when the values for the
        variables are 1)
      • A control line for the NOT of every input variable
        (think of these as being used when the values for the
        variables are 0)
      • Each AND gate corresponds to a row in the truth table where
        the result column has a value of 1
      • For example, ~ABC represents 011, and A~BC represents 101
    • Fig. 3-4: Construction of NOT, AND, and OR gates using NAND and NOR
    • Fig 3-5: Constructing a truth table and a circuit diagram for a given
      Boolean function.
      In this case, the two Boolean functions are equivilant
    • Fig. 3-6: Identities in Boolean algebra
      and Duals (where 1s and 0s and *s and +s are switched)
      AND forms and OR forms for the same identity
    • Fig. 3-7: Alternative symbols for NAND, NOR, AND, OR
    • Fig. 3-8: Truth table for the XOR function
      and three sample circuits for XOR
    • Fig. 3-11: An eight input multiplexer circuit
      • Eight input lines: D0..D7
      • Three control lines for A,B,C (true when the values are 1)
      • Three control lines for ~A,~B,~C (true when the values are 0)
      • Eight AND gates for each combination of the three control
        lines:
        Ex. The AND gate for D0 will be true when A,B,C = 000
        The AND gate for D5 will be true when A,B,C = 101
        The AND gate for D7 will be true when A,B,C = 111
      • The setting of the control lines determine which data line
        will successfully pass through to the OR gate
    • Fig. 3-12b: A multiplexer diagram for the majority function on p. 121, Fig. 3-3
      • Three control lines for the input variables A,B,C
      • The rows in the truth table that have a 1 in the result column
        - Rows 3,5,6, and 7 - are wired to Vcc
      • The rows in the truth table that have a 0 in the result column
        - Rows 0,1,2, and 4 - are wired to ground
      • The particular combination of A,B,C select a given row
        ABC = 000 is row 0, ABC = 101 is row 5, etc.
    • Fig. 3-13: A 3 input to 8 output decoder
      This is similar to a demultiplexer circuit, where 1 input is routed
      to one of a series of output gates
    • Fig. 3-14: A 4-bit comparator. This circuit takes two 4-bit words
      as input and returns a 1 if the 4-bit words are equal and a 0 if they
      are not equal.
      - A0, A1, A2, A3 represent each bit of word A.
      - B0, B1, B2, B3 represent each bit of word B.
    • Fig. 3-16: A 1-bit left/right shifter. When the clock, C, is 1 the eight
      bits are shifted to the right 1 bit. When C is 0 the eight bits
      are shifted to the left.
    • Fig. 3-17: A Half adder. This circuit does not take a Carry in (see
      the Full adder). The half adder has two input bits and outputs
      Sum=0 if A and B are equal and Sum=1 if A and B are different (XOR)
      The Carry out = 1 if A and B are both 1 and 0 otherwise (AND)
    • Fig. 3-18: A Full adder. This circuit is based upon a half adder with
      the capability of recieving a Carry in from the previous additition
      of the bits in the previous column.
      There are three inputs: A, B, and Carry in.
    • Fig. 3-19: A 1-bit ALU
    • Fig. 3-22: An SR latch showing the two possible stable states for
      S=0, R=0. State 0 means output Q=0, State 1 means ouput Q=1.
      S=1, R=0 is a "set" to State 1.
      S=0, R=1 is a "reset" to State 0.
    • Fig. 3-23: A clocked SR latch. This circuit is based on the
      SR latch in from above. A "clock" is introduced to provide
      "write-protect" for the memory bit. When the clock=1, the
      latch can recieve the bit values from S and R. If clock=0,
      no input from S and R is allowed.
    • Fig. 3-24: A clocked D latch. This circuit assures that S and R will
      be opposite. The single input D goes to S, and the inverse of D
      goes to R. There is a clock to allow input or block input.
      (Clock=1 allows input, clock=0 no input allowed)
    • Fig. 3-26: A D flip flop
    • Fig. 3-28: Dual D flip-flop and an Octal flip-flop
    • Fig. 3-29: Logic diagram for a 4 X 3 memory. Each row is one of
      the four 3-bit words.
    • Fig. 3-31: Two ways of organizing a 4-Mbit memory chip

  6. Chapter 3, Boolean Logic Level - Summary of Topics for test
    • 5 basic gates
    • Boolean algebra
      • Circuit equivalence
      • Identities such as distributive, absorbtion, and De Morgan's
      • Duals
    • Implementation of Boolean functions
      • Circuit for the majority function
    • Circuit equivalence
    • XOR, NAND, NOR
    • Integrated circuits
      • SSI, MSI, LSI, VLSI
      • Increase gate to pin ratio
    • Combinational circuits
      • Multiplexer - 2^n data inputs, one data output, n control inputs us ed to select one of the data inputs
      • Demultiplexer - routs a single input signal to one of 2^n outputs, depending on the values of n control lines
    • MSI chips
      • Multiplexer
      • Majority function
      • Comparator
      • Programmed logic array
      • Shifter, adder, 1 bit ALU
    • Clocks
    • Memory
      • SR Latch
      • Clocked SR latch
      • Clocked D latch
      • Flip flops

  7. Bit Shifting, Masks
    • Masking 1 bit: AND with 00000001
      • Example: x = x & 0x01 will isolate the first bit
      • 0x01 is hexadecimal for 00000001
      Masking 4 bits: AND with 00001111
      • Example: x = x & 0x0f will isolate the rightmost 4 bits
      • 0x0f is hexadecimal for 00001111
    • Find the value of the 4th bit position: AND with 00001000
      • Example: x = x & 0x08
      • OR use: x = x >> 4; x = x & 0x01;
        (shift right 4 bit positions, then AND with 00000001
    • Count the number of 1s:
      • AND with 00000001, then shift right 1 place: x = x >> 1
      • repeat the operations: x = x & 0x01; x = x >> 1;
    • Bit Operators: &, |, ~, ^, >>, <<
    • OTHER "Tricks": Using mod, division, and multiplication (%,/,*)
      • mod by 2 (x = x % 2) will isolate the rightmost bit value
        Ex. 37 % 2 is 1, which is the rightmost bit of 00100101 (37 binary)
      • dividing by 2 (x = x/2) will shift the bits to the right one position
        Ex. 37/2 = 18: 00100101 / 2 = 00010010 (18)
        The bits have shifted 1 position to the right
      • multiplying by 2 (x = x*2) will shift the bits to the left one position
        Ex. 37*2 = 74: 00100101 * 2 = 01001010 (74)
        The bits have shifted 1 position to the left

  8. There may be a question with some surprise C code

  9. Summary of Programs so far
    • Byte/Word storage, little-endian and big-endian
    • Simulating the von Neuman Architecture, SISD machine
    • Hypercube network, MIMD and synchronization of multiple processes
    • Frequency chart for hexadecimal digits in a file.