Computer Systems Fundamentals Cheat Sheet

Computer Systems Fundamentals Cheat Sheet

Number Systems

• Binary (Base 2): Digits 0 and 1.
• Hexadecimal (Base 16): Digits 0–9 and A–F.
• Decimal (Base 10): Digits 0–9.

Conversions

• Binary to Decimal: Multiply each bit by 2^n from the right.
• Decimal to Binary: Divide by 2 and record the remainders.
• Hex to Binary: Replace each hex digit with its 4-bit binary equivalent.

Two's Complement (Signed Numbers)

• Positive numbers: Same as unsigned.
• Negative numbers: Invert all bits and add 1.
• Range (n bits): -2^(n-1) to 2^(n-1) - 1.
• Overflow: Occurs if carry into the sign bit ≠ carry out.

Boolean Algebra Rules

• Identity: A + 0 = A, A * 1 = A
• Null: A + 1 = 1, A * 0 = 0
• Idempotent: A + A = A, A * A = A
• Inverse: A + NOT A = 1, A * NOT A = 0
• Distributive: A(B + C) = AB + AC
• Absorption: A + AB = A
• DeMorgan's Laws: NOT(A * B) = NOT A + NOT B, NOT(A + B) = NOT A * NOT B

Logic Gates

• NOT: Inverts the input.
• AND: A * B (True if both inputs are 1).
• OR: A + B (True if any input is 1).
• NAND: NOT(A * B).
• NOR: NOT(A + B).
• XOR: A XOR B = A(NOT B) + (NOT A)B.
• XNOR: NOT(A XOR B).

Karnaugh Maps (K-Maps)

• Group 1’s into rectangles (sizes of 1, 2, 4, 8...).
• Bigger groups result in simpler expressions.
• Cover all 1’s with the fewest groups possible.

Latches and Flip-Flops

• SR Latch: Level-sensitive memory (Set/Reset).
• D Latch: Level-sensitive, stores a single bit.
• D Flip-Flop: Edge-triggered, stores a bit on the clock edge.

Finite State Machines (FSM)

• Mealy Machine: Output depends on both state and input.
• Moore Machine: Output depends on state only.

Multiplexers (MUX)

• Select 1 of many inputs based on selector lines.
• Formula (2-to-1 MUX): F = S * D1 + (NOT S) * D0.

Decoders

• n inputs produce 2^n outputs.
• Only one output is high at a time.

Adders

Half Adder

• Sum: A XOR B.
• Carry: A * B.

Full Adder

• Sum: A XOR B XOR Cin.
• Carry-out: AB + ACin + BCin.

Transistor Costs (Common Gates)

• NOT: 2 transistors.
• AND (2-input): 6 transistors.
• OR (2-input): 6 transistors.
• NAND (2-input): 4 transistors.
• NOR (2-input): 4 transistors.
• XOR (2-input): 8 transistors.
• XNOR (2-input): 8 transistors.

General Tips

• Look for patterns in truth tables.
• Group like terms in Boolean expressions.
• Use K-Maps for minimizing expressions.
• Think modularly when designing circuits (using MUXes, decoders, etc.).
• Always check for overflow in binary arithmetic.