Computer Architecture
Test 2 Topics
(this test is scheduled for the week of March 19)
- Mic 1 microcode
- Translating a microinstruction into 32 bit microcode
- Translating 32 bit microcode into a microinstruction
- Hamming code
- Given the transmission data, find the errors (if any)
- Given the data to send, encode with the Hamming algorithm
- 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
- See:
- Hypercube question(s)
- Finding the neighbors of given node(s)
- Finding the path(s) from a Start node to a Destination node.
- 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
- 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
- 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 may be a question with some surprise C code
- 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.