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
- Hamming code
- Given the transmission data, find the errors (if any)
- Givne the data to send, encode with the Hamming algorithm
- 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)
- 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
- Machine Levels: level 0 through level n, computer architecture
- Knowledge of terms
- Such as: translation, interpretation
- software/hardware/virtual machine
- Chapter 2 - Computer Systems Organization
- CPU organization, data path of a von Neumann machine
- Instruction execution, fetch-decode-execute cycle
- 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
- Memory addresses, cells, ways of organizing an n-bit memory
- 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
- 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
- Input/output **
- CRT, raster scan, pixels, RGB
- Modems, synchronous/asynchronous transmission, start/stop bits
- Simplex, half duplex, full-duplex transmission
- Character codes
- ASCII
- Hexadecimal, binary, octal conversions
- Chapter 3 - The Digital Logic Level
- 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
- 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 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
- 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
- Homework problems: Chap. 1, 2 (2 assignments), 3 (first assignment)
- 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