Computer Architecture
Test 1 Topics
(** means the topic is not covered in detail on the first test)

• The "3 H's": Hamming code, Hypercube, Huffman compression
  1. Hamming code
     • Given the transmission data, find the errors (if any)
     • Givne the data to send, encode with the Hamming algorithm
  2. Hypercube
     • Label the adjacent nodes in "n" dimensions to a given node (XOR)
     • Given the start and goal node, find a path using XOR
       (source XOR destination - see Hypercube website)
  3. Huffman data compression
     • Given the frequency of data in a file, draw the tree AND create the
       Huffman code for that data
     • Given the Huffman code and a transmission, decode the transmission
  
  
• 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
  
  
• There will be a question with some surprise C code
  
  
• Chapter 1 - Introduction
  1. Machine Levels: level 0 through level n, computer architecture
  2. Knowledge of terms
     • Such as: translation, interpretation
  3. software/hardware/virtual machine
  
  
• Chapter 2 - Computer Systems Organization
  1. CPU organization, data path of a von Neumann machine
  2. Instruction execution, fetch-decode-execute cycle
  3. Parallel instruction execution: SISD, SIMD, MIMD
     • Pipeline machine, parallel processing with SISD
     • Array processor, vector machine: SIMD
     • Multiprocessor, multicomputer: MIMD
     • Also see:
       • p. 551-553:Taxonomy of Parallel Computers,
         Fig. 8-13 and 8-14
       • p. 554-557: SIMD computers
       • p. 609 Summary
  4. Memory addresses, cells, ways of organizing an n-bit memory
  5. Byte ordering: big endian, little endian **
     • Sequential byte numbering left to right or right to left
     • 32 bit word example
     • Character string vs. integer storage
  6. Error correcting codes
     • Hamming code
       • Parity bits, even parity, odd parity
       • Given a Hamming encoded bit stream, find the error
       • Given a bit stream of data, put it into a Hamming encoded
         bit stream with data bits and parity bits
  7. Input/output **
     • CRT, raster scan, pixels, RGB
     • Modems, synchronous/asynchronous transmission, start/stop bits
     • Simplex, half duplex, full-duplex transmission
  8. Character codes
     • ASCII
     • Hexadecimal, binary, octal conversions
  
  
• Chapter 3 - The Digital Logic Level
  1. Summary of figures to understand so far:
     • 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
  2. 5 basic gates
  3. Boolean algebra
     • Circuit equivalence
     • Identities such as distributive, absorbtion, and De Morgan's
     • Duals
  4. Implementation of Boolean functions
     • Circuit for the majority function
  5. Circuit equivalence
  6. XOR, NAND, NOR
  7. Integrated circuits **
     • SSI, MSI, LSI, VLSI
     • Increase gate to pin ratio
  8. Combinational circuits **
     • Multiplexer - 2^n data inputs, one data output, n control inputs used 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
  9. MSI chips
     • Multiplexer
     • Majority function
     • Comparator **
     • Programmed logic array **
     • Shifter, adder, 1 bit ALU **
  10. Clocks **
  11. Memory **
      • SR Latch
      • Clocked SR latch
      • Clocked D latch
      • Flip flops
  
  
• Homework problems: Chap. 1, 2 (2 assignments), 3 (first assignment)
  
  
• Summary of Programs so far
  1. Byte/Word storage, little-endian and big-endian
  2. Simulating the von Neuman Architecture, SISD machine
  3. Hypercube network, MIMD and synchronization of multiple processes