click below
click below
Normal Size Small Size show me how
CIS 240 MT1
Question | Answer |
---|---|
What is a computer? | A computer is a machine, which is built with a collection of switches and logic. The machine does whatever software does it to do; software is a series of instructions. |
What instructions does a computer need? | - Arithmetic: add, subtract, multiply, divide, etc. - Memory Access: reading/writing - Conditional: booleans |
What is computer architecture? | A computer architecture specifies the hardware's interface, permitting us to write and run software on it. - Defines instructions implemented by hardware - Defines number of storage locations |
Five Classic Components of a Computer | Control, Datapath, Memory, Input, Output |
Bit | Basic unit of information in a computer ("binary" & "digit) BASE TWO: One bit represents two symbols (0, 1) N bits represent 2^n symbols |
Sign Magnitude Rules for Bit Representation | Use leftmost bit to indicate + (0) or - (1) Note that while the conversion is easy and it's conceptually simple, it's harder to compute (adding, subtracting), and you have a positive & negative zero, which isn't ideal. +17 = 010001 -17 = 110001 |
1s Complement Rules for Bit Representation | Positive binary numbers represent negative integers (negate a number by inverting each bit) Again, harder to compute, and positive & negative zero. 0000 = 0 0001 = 1 ... 0111 = 7 1000 = -7 1001 = -6 ... 1111 = -0 |
2s Complement Rules for Bit Representation | Positive binary numbers represent negative integers (convert between positive & negative by inverting bits and adding 1) MOST IDEAL! No negative zero, ideal for operations. 0000 = 0 0001 = 1 ... 0111 = 7 1000 = -8 1001 = -7 ... 1111 = -1 |
Precision Extension | You can extend preciseness of a number in 2s complement via sign bit extension. For example, represent "14" in two ways: 14 in 6-bit: 001110 14 in 12-bit: 000000001110 -14 in 6-bit: 110010 -14 in 12-bit: 111111110010 For unsigned, just add 0s |
Binary Addition | Just like standard decimal addition, except instead of on a 10 scale, on a 2 scale. Remember to carry 1s whenever necessary, and just add (1+1 = 0 - carry 1, 1+0 = 1, 0+0 = 0, 1+1+1=1 - carry 1) 00011101 +00101011 --------------- 01001000 |
Integer Overflow | When you are adding and a value is larger than permissible in 8-bit representation. For unsigned numbers: If adding produces a carry bit For 2s complement: adding two positives and getting a negative adding two negatives and getting a positive |
Binary Subtraction | In 2s complement, it's easy! A - B = A + (-B) -B = B (with reverse bits) + 1 |
Representation with IEEE Floating Point | +/- 1.YYYYY X 2^(N-127) Features: Implicit 1 before binary point 1-bit sign (+ = 0, - = 1) 8-bit biased exponent (N-127) 23-bit mantissa(YYYYY...) |
Floating Point to Binary Example #1: Represent 5.625 in binary | 101.101 = 4 + 1 + 1/2 + 1/8 = 5.625 Normalize: 1.01101 X 2^2 Sign Bit: 0 (positive #) Exponent bits: 127 + 2 = 129: 1000 0001 Mantissa bits: 0110 1000 0000 0000 0000 000 Answer: 0100 0000 1011 0100 0000 0000 0000 0000 Hexadecimal: 0x40B40000 |
Hexadecimal System | 0 = 0000 1 = 0001 2 = 0010 3 = 0011 4 = 0100 5 = 0101 6 = 0110 7 = 0111 8 = 1000 9 = 1001 A = 1010 B = 1011 C = 1100 D = 1101 E = 1110 F = 1111 |
Hexadecimal to Floating Point Example: What floating point number is 0xC1580000? | Convert hexadecimal to binary: 1100 0001 0101 1000 0000 0000 0000 0000 Find the Parts: Sign - first bit, 1 (negative) Exponent bits: Next 8 bits - 130, 130-127 = 3 Mantissa bits: whatever's remaining: 1011 Convert: -1.1011X2^3 = -1101.1 = -13.5 |
How do you represent 0.0 in IEEE Floating Point? | Trick Question! 0.0 = 000000... It's the denormalized exponent, so it's 000000000 only |
Other Weird Floating-Point Numbers | Non-Standard Exponent: 1111 1111 When mantissa = 0, encoding +/- infinity When mantissa ≠ 0, encoding NaN |
Binary Representations for Characters | Encode symbols: N bits encode 2^N symbols, X symbols requires log_2(X) bits ASCII: Encodes 2^7 =128 symbols |
Boolean Functions | NOT (negation): !A = ~A = Ā AND (both true): A&B = A*B = A • B = AB = A ∧ B = A && B OR (at least one true): A | B = A + B = A ∨ B = A || B XOR (strictly one true): A ^ B = A ⊕ B Other: NAND (flipped AND), NOR (flipped OR), XNOR (A = B), etc. |
Truth Tables | One column per input and the output column. Enumerate inputs by counting in binary, then compute outputs based on expression. |
Given a truth table, how do we find a Boolean expression? | Write down every "true" case and OR the cases together; then, use Sum of Products (ugly expression, but able to be simplified) |
Boolean Algebra & Simplification | Boolean expressions can be simplified with the following rules: A & A = A A & 0 = 0 A & 1 = 1 A & !A = 0 A | A = A A | 0 = A A | 1 = 1 A | !A = 1 !!A = A A & (B | C) = (A & B) | (A & C) A | (A & B) = A |
DeMorgan's Laws | ! (A & B) = (!A) | (!B) ! (A | B) + (!A) & (!B) |
Simplify the following: ! (!A | !(A & (B|C))) | !!A & !! (A & (B | C)) (distributing the not, apply DeMorgan's) A & (A & (B | C)) (eliminate double negation) (A & A) & (B | C) (associativity of &) A & (B | C) |
Simplify the following: (!A & !B & !C) | (!A & B & !C) | (A & !B & C) | (A & B & C) | (!A & !B & !C) | (!A & B & !C) simplifies to (!A & !C) (A & !B & C) | (A & B & C) simplifies to (A & C) This leaves us with (!A & !C) | (A & C) |
Transistors | Control the flow of electrons Presence of voltage: 1 Absence of voltage: 0 |
What's the difference between nMOS and pMOS? | nMOS - On when gate voltage is high (logical 1), negative charge pMOS - On when gate voltage is low (logical 0), positive charge |
Boolean Gates | Electronic devices that implement simple Boolean functions |
Implementing Functions with Gates | For Combinational Logic: Multiple inputs - compose multiple two-input gates, or implement a new CMOS gate Arbitrary Functions - simplify expression & implement with gates Delays exist between changing gate input and updating gate output |
Programmable Logic Array (PLA) | Taking all outputs equal to 1, grouping them in terms of AND operators individually, then connecting them all to an OR Brute force implementation, but not very efficient, and usually not "minimal" amount of gates for a truth table |
Multiplexor (Mux) - Two Inputs | Select from multiple inputs (2-to-1 mux selects b/w two inputs) With a truth table, S input is a selector (if S = 0, select A, else S =1, select B) Two inputs require 1 select, four requires 2, N requires log_2(N) |
Simplify the following: (!A & B & S) | (A & !B & !S) | (A & B & !S) | (A & B & S) | (A & !S) | (B & S) |
Pull Up Network (PUNs) vs Pull Down Network (PDNs) | PUNs pull UP the voltage - connects to power, uses pMOS PDNs pull DOWN the voltage - connects to ground, uses nMOS |
Transistors in series are a logical... | AND |
Transistors in parallel are a logical... | OR |
Steps to construct CMOS | 1. Simplify expression to Boolean Expression (ex. A+B*C) 2. Construct PDN w/Expression (uses nMOS) 3. Negate Expression 4. Construct PUN (using pMOS) 5. Verify that Negatation was correct by applying both ways 6. Construct Truth Table 7. Draw CMOS |
Perform the operation x << 3 on x = 0000 1011 | x = 0101 1000 |
Perform the operation x >> 2 on x = 0000 1011 | x = 0000 0010 |
Half Adder | Circuit that adds two bits together. A and B are the bits being added, S is the sum we output, Cout is the carryout bit |
Incrementer | Adds 1 to any number input, an example of an application of a half adder |
Full Adder | Two half adders; includes a carry in bit as well now, which accounts for if a previous addition step relies on it for the addition. |
Subtractor | Two’s complement is awesome, since A - B = A + (~B + 1). Therefore, use an n-bit adder in order to do subtraction. When sub = 1, the XOR gates flip all of B’s gates. In that case, 1 is fed into the first full adder circuit |
Multiplier | Uses adders and muxes |
Sequential Logic | Output is Boolean functions of inputs and state (stored value) Permits feedback loop, computes & stores outputs, uses stored outputs as inputs for further computation, and requires circuits for storage |
Ideal Storage | We want storage that can hold 1 bit (we can add more to hold more bits) We also want to be able to control when the value the storage holds changes Finally, we want robust storage (resistant to improper inputs) |
Set-Reset (SR) Latch | The most simple storage circuit When only the S (set) signal is 1, Q outputs a 1; when only the R (reset) signal is 1, Q outputs a 0. When R & S are 0, Q doesn't change, and the system breaks when R and S are both 1 |
Data (D) Latch | We want to "protect" the inputs going into the latch, so we will use an AND gate to make it impossible for both R and S to be 1 at the same time. So, when E is 0, both AND gates are 0 |
The CLOCK | By adding a clock, or a signal that goes from 0 to 1, we provide an enable signal for memory on a consistent basis. On each cycle, memory should take in new data, store it, and output it Clock period > max delay in circuit |
Problem with D-Latches & Clocks | D-Latches are level triggered, so they take in new values as long as the CLOCK is 1. Thus, if logic finishes when the CLOCK is 1, there's no way of knowing when the value you want is there |
D Flip Flop | Two D-Latches, but left latch only writes when CLOCK=0, right latch only writes when CLOCK=1. Leads to edge-triggered behavior |
Edge Triggered vs. Level Triggered | Level-triggered latch captures new value at clock level (high or low), while edge-triggered latch captures new value at clock edge (rising or falling) |
Register | Provides storage for binary word (32-bit value) Can be made with 32 DFFs |
Register File | A collection of registers (32 32-bit values) |
Writing Register | Specify register number, need to select the register, and need to enable only selected register |
Reading Register | Specify register number, need to select the register, but the 32-input mux is too slow... |
Decoders for Register File | Convert register number to "one-hot" enable signal (N bit input, 2^N bit output of which one bit matching the input is high , the rest are low) Implement with AND gates for each output |
High Impedance (Z) | Expand from {0, 1} to {0, 1, Z}; output is not driven to a defined value Prevents charge from flowing (neither pumps charge in nor drains charge out) Leads to the Tri-State Buffer, a gate that outputs {0, 1, Z} |
Tri-State Buffers | Connect multiple outputs to single wire (only output can drive signal, all but one output must be outputting Z at any given time) |
Multiplexor w/Tri-State Buffers | Much more efficient for large number of inputs |
Register File Ports | Adding Read Port(s): Each permits one read per clock cycle, needs decoder, tri-states, and output bus Adding Write Port(s): Each permits one write per clock cycle, each needs muxes to select write data |