CSSE2010 — Week 1 Notes

Lecture 1 — Course Introduction; Bits, Bytes and Binary

See csse2010 for staff, assessment, and course logistics — this note covers the technical content from Lecture 1.

Today’s outline

  • Course intro, organisation and admin
  • Assessment details
  • Technical content — binary numbers

Levels of abstraction

A computer can be understood at several levels of increasing abstraction (from Tanenbaum’s Structured Computer Organisation):

  1. Level 0 — Digital Logic level (gates, circuits) — this course starts here
  2. Level 1 — Microarchitecture level
  3. Level 2 — Instruction set architecture level
  4. Level 3 — Operating system machine level
  5. Level 4 — Assembly language level
  6. Level 5 — Problem-oriented language level

The course roughly climbs this stack over the semester: hardware/digital logic first, then low-level (assembly) software, then high-level software.

Computers and binary numbers

Computers represent everything — inputs, instructions, and outputs — as binary data internally, e.g. 101001010110101001111010101001011100011010101.

See binary-number-representations for the full reference on bits, bytes, unsigned number representation, converting between decimal/binary/octal/hex, and radix notation conventions — all introduced in this lecture.

Reminders

  • Sign up to a pair of lab sessions (P2, P1).
  • Labs start from Thursday of week 1 (P1 sessions only — no P2 sessions in week 1).
  • From week 2, both P2 and P1 sessions run.
  • Lab 1 covers different binary representation formats for signed numbers (two’s complement etc. — not covered in this lecture).
  • A summary recording on binary numbers will be posted by the end of week 1.
  • Lab sign-on issues: email eait.mytimetable@uq.edu.au.

Lecture 2 — Intro to Logic Gates

See logic-gates and boolean-algebra for the reference definitions/tables this lecture introduces.

Today’s outline

  • Introduction to Logic Gates
  • Logic Diagrams
  • Boolean Algebra and Logic Expressions

Digital logic

  • Digital circuits only have two logical levels present (binary): logic ‘0’ (~0V) and logic ‘1’ (~0.8-5V, depending on the logic family/transistor type).
  • Logic gates are the building blocks of computers: each has one or more inputs and exactly one output, and performs a logic operation.
  • 7 basic gate types: NOT, AND, OR, NAND, NOR, XOR, XNOR — see logic-gates for symbols and truth tables.
  • Every logic function can be described four equivalent ways: logic symbol, truth table, Boolean expression, timing diagram.

Quiz: 3-input NAND truth table

Given four candidate truth tables, which one is the 3-input NAND?

Reasoned from the definition (NAND = NOT(AND), and AND is 1 only when all inputs are 1): the correct table is the one where \(X = 1\) for every combination except \(A=B=C=1\) (where \(X=0\)).

Quiz: 3-input XOR truth table

XOR is the “odd function” — \(X=1\) exactly when an odd number of inputs are 1.

Reasoned from that definition, the correct table (in order \(ABC = 000, 001, 010, 011, 100, 101, 110, 111\)) is: \[X = 0, 1, 1, 0, 1, 0, 0, 1\]

Boolean algebra conventions

See boolean-algebra for the full notation conventions, laws/identities table, and De Morgan’s law diagrams introduced in this lecture.

Logic diagram conventions

  • A filled dot at a wire junction indicates an electrical connection; wires that cross without a dot are not connected.
  • Inputs are conventionally drawn on the left, outputs on the right.

Gates on ICs

  • Example: the 74HCT00 IC has four 2-input NAND gates in a single 14-pin DIP package.
  • Vcc = power (e.g. 5V), GND = ground (0V). Pin spacing 0.1”×0.3”; chip ~15mm long.

Logic function implementation (sum of products)

Any logic function can be implemented as the OR of AND combinations of its inputs — called sum of products: for each row where the output is 1, write the AND of the inputs (complemented where 0) that produces that row, then OR all those terms together.

Worked example — truth table for \(M\):

A B C M
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

\[M = \bar A BC + A\bar B C + AB\bar C + ABC\]

Equivalent functions (simplification)

Sum-of-products doesn’t necessarily give the minimum number of gates — Boolean algebra laws (see boolean-algebra) can be used to manipulate an expression into an equivalent, simpler one.

Example: \(Z = AB + AC = A(B+C)\) (distributive law) — the right-hand form needs fewer gates.

Universal (complete) gates

All circuits can be built from NAND-only or NOR-only gates (called complete/universal gates) — NOT, AND, and OR can each be constructed purely from NAND gates (or purely from NOR gates). This matters in practice because NAND and NOR gates are easier to build from transistors than AND/OR directly.

Reminders

  • Attend Learning Lab sessions for the second half of this week — only the session you’re signed up to.
  • From week 2, you’ll have both P2 (Mon-Tue) and P1 (Thu-Fri) lab sessions.

Week 1 Exercises — Bits, Bytes & Binary; Intro to Logic Gates

Practice exercises for week 1, covering 2026-07-27-course-intro-bits-bytes-binary and 2026-07-30-intro-to-logic-gates. Many are taken from or based on Tanenbaum, Structured Computer Organisation, 5th edition, Appendix A and Appendix B. See binary-number-representations and logic-gates for the reference material needed to solve these.

On the HTML site, fill in each blank with your answer (as a quoted string, e.g. "1010"), then click Run Code to check it. In the PDF, the Working callout is shown as a static answer key instead (interactive checking needs a browser).

Q1 — Decimal to binary conversion

Convert the following decimal numbers to binary (unsigned representation): 1984, 4000, 8192.

1984 →

4000 →

8192 →

Repeatedly divide by 2, reading the remainders bottom-to-top (or subtract the largest power of 2 not exceeding the remaining value) — see binary-number-representations#converting-decimal-to-binary.

  • \(1984 = 1024+512+256+128+64 = 2^{10}+2^9+2^8+2^7+2^6 \Rightarrow\) 11111000000
  • \(4000 = 2048+1024+512+256+128+32 = 2^{11}+2^{10}+2^9+2^8+2^7+2^5 \Rightarrow\) 111110100000
  • \(8192 = 2^{13} \Rightarrow\) 10000000000000 (a 1 followed by 13 zeros)

Q2 — Binary to decimal, octal, hexadecimal

What is \(1001101001\) (binary, unsigned) in decimal? In octal? In hexadecimal?

Decimal →

Octal →

Hexadecimal →

Sum the powers of 2 where a bit is set: \(1001101001_2 = 2^9+2^6+2^5+2^3+2^0 = 512+64+32+8+1 = 617_{10}\).

  • Octal: \(617 \div 8 = 77\) r\(1\); \(77 \div 8 = 9\) r\(5\); \(9 \div 8 = 1\) r\(1\); \(1 \div 8 = 0\) r\(1\) → 1151 (check: \(1\cdot512+1\cdot64+5\cdot8+1\cdot1=617\)).
  • Hex: \(617 \div 16 = 38\) r\(9\); \(38 \div 16 = 2\) r\(6\); \(2 \div 16 = 0\) r\(2\) → 269 (check: \(2\cdot256+6\cdot16+9=617\)).

Q3 — Counting \(k\)-digit radix-\(r\) numbers

How many different positive integers can be expressed in \(k\) digits using radix \(r\) numbers?

With \(k\) digits in radix \(r\), every combination from all-zeros to all-\((r-1)\)s is representable, giving \(r^k\) distinct values total (including 0). Excluding 0 leaves \(r^k - 1\) positive integers.

Q4 — Radix-32 (Manchester Mark 1)

One of the earliest computers (the Manchester Mark 1, 1949) was programmed with a radix-32 number system, with digits \(0, 1, \dots 9, A, B, \dots U, V\) (10 numerals + 22 letters = 32 symbols).

  1. Describe how a binary number can be converted into a radix-32 number.
  2. Describe how a decimal number can be converted into a radix-32 number.
  3. Convert the decimal numbers 1300 and 2300 to radix-32 representations.

1300 →

2300 →

  • (a) Binary → radix-32: since \(32=2^5\), group the binary digits into 5-bit groups starting from the least significant bit (pad the leftmost group with leading zeros if needed), then convert each 5-bit group (a value 0–31) to the corresponding single radix-32 digit (0–9, then A=10 … V=31).
  • (b) Decimal → radix-32: repeatedly divide by 32, recording each remainder (converting remainders 10–31 to A–V); the radix-32 digits are the remainders read in reverse (last remainder computed = most significant digit) — the same repeated-division method used for decimal → binary/octal/hex.
  • (c):
    • \(1300 \div 32 = 40\) r\(20\); \(40 \div 32 = 1\) r\(8\); \(1 \div 32 = 0\) r\(1\) → digits \(1, 8, 20\)(=K) → 18K. Check: \(1\cdot1024+8\cdot32+20=1300\).
    • \(2300 \div 32 = 71\) r\(28\); \(71 \div 32 = 2\) r\(7\); \(2 \div 32 = 0\) r\(2\) → digits \(2,7,28\)(=S) → 27S. Check: \(2\cdot1024+7\cdot32+28=2300\).

Q5 — Largest unsigned integer

What’s the largest unsigned integer that can be represented in:

  1. 10 bits
  2. 9 decimal digits
  3. 8 hexadecimal digits

(a) 10 bits →

(b) 9 decimal digits →

(c) 8 hexadecimal digits →

The largest value in \(n\) digits of radix \(r\) is \(r^n - 1\) (all digits at their maximum):

    1. \(2^{10}-1 = 1023\)
    1. \(10^9-1 = 999{,}999{,}999\)
    1. \(16^8-1 = 4{,}294{,}967{,}295\) (note: 8 hex digits = 32 bits, so this equals \(2^{32}-1\))

Q6 — Finger counting

What’s the largest number that can be counted to on ten fingers, if each finger can be considered to have two positions? Compare your answer to that in 5(a).

Ten fingers, each with 2 possible positions, is exactly 10 bits of information: \(2^{10}-1 = 1023\) — identical to 5(a), since “10 things each with 2 states” is a 10-bit binary number.

Q7 — Signed number formats

For each of the following decimal numbers, write down the 8-bit binary representation using signed magnitude, one’s complement, two’s complement, and excess-128 formats:

  1. \(-1\)
  2. \(-16\)
  3. \(-99\)

Answer as four comma-separated 8-bit codes, in the order signed-magnitude,ones-complement,twos-complement,excess-128 (e.g. "10000000,11111111,00000000,10000000" for 0).

(a) −1 →

(b) −16 →

(c) −99 →

Formats (see binary-number-representations): signed magnitude = sign bit + 7-bit \(|n|\); one’s complement (negative) = invert every bit of \(|n|\)’s 8-bit form; two’s complement (negative) = \(128+n\) as a 7-bit value, prefixed with a 1; excess-128 = \(n+128\) as a plain 8-bit unsigned value.

\(n\) Signed magnitude One’s complement Two’s complement Excess-128
−1 10000001 11111110 11111111 01111111
−16 10010000 11101111 11110000 01110000
−99 11100011 10011100 10011101 00011101

Q8 — Signed format ranges

What are the smallest and largest integers that can be represented in the following binary representations:

  1. 16-bit two’s complement
  2. \(n\)-bit one’s complement
  3. excess \(2^{m-1}\)
  • (a) 16-bit two’s complement: smallest \(=-2^{15}=-32768\), largest \(=2^{15}-1=32767\).
  • (b) \(n\)-bit one’s complement: symmetric about zero (it has two representations of 0), so smallest \(=-(2^{n-1}-1)\), largest \(=2^{n-1}-1\).
  • (c) excess \(2^{m-1}\) (\(m\)-bit field, bias \(2^{m-1}\)): stored value ranges \(0\) to \(2^m-1\), actual value = stored \(-\) bias. Smallest (stored \(=0\)): \(-2^{m-1}\). Largest (stored \(=2^m-1\)): \(2^{m-1}-1\) — the same numeric range as \(m\)-bit two’s complement, just a different (biased) encoding of it.

Q9 — Logic gates: NOR and XOR

Draw the logic symbol, write the Boolean function, and write down the truth table for:

  1. a 4-input NOR gate
  2. a 3-input XOR gate (i.e. the odd function)

(a) 4-input NOR — symbol: an OR-gate body (curved input side, pointed output) with 4 input lines and a small bubble on the output denoting inversion. Boolean function (De Morgan’s): \(X = \overline{A+B+C+D} = \bar A \cdot \bar B \cdot \bar C \cdot \bar D\) — \(X=1\) only when every input is 0.

A B C D X
0 0 0 0 1
all other 15 combinations 0

(b) 3-input XOR (odd function) — symbol: an XOR-gate body (OR-gate shape with an extra curved line just behind the inputs), no bubble. Boolean function: \(X = A \oplus B \oplus C\) — \(X=1\) iff an odd number of inputs are 1.

A B C X
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

Reference material

Binary Number Representations

Bits, bytes, and words

  • Bit = binary digit (0 or 1).
  • Byte = 8 bits, e.g. 01010111.
  • Modern computers deal with words, usually a power-of-2 number of bytes: 1, 2, 4, or 8 bytes = 8, 16, 32, 64 bits.

Representing whole (unsigned) numbers

Each bit position has a value — a power of 2, increasing from right (least significant) to left (most significant):

Bit position 9 8 7 6 5 4 3 2 1 0
Value 512 256 128 64 32 16 8 4 2 1

Binary → decimal: add the values of each position where the bit is 1. E.g. 10010001 = \(128 + 16 + 1 = 145\).

  • Least significant bit (LSB) — the bit position worth the least (\(2^0 = 1\)).
  • Most significant bit (MSB) — the bit position worth the most. For an \(n\)-bit unsigned word, the MSB is worth \(2^{n-1}\).

Converting decimal to binary

Two equivalent methods (example: convert 53 to binary):

  • Method 1: rewrite \(n\) as a sum of powers of 2, by repeatedly subtracting the largest power of 2 not greater than \(n\). Assemble the binary number from 1’s in the bit positions corresponding to those powers of 2, 0’s elsewhere.
  • Method 2 (build up from the right/LSB): divide \(n\) by 2; the remainder (0 or 1) is the next bit; repeat with \(n\) = the quotient, until \(n = 0\).

Number range (unsigned)

  • Smallest representable value: all 0’s → 0.
  • Largest representable value: all 1’s → for an \(n\)-bit word, \(2^n - 1\) (e.g. 255 for 8 bits).

Other radices

Radix = number system base. A radix-\(k\) number system has \(k\) distinct symbols for digits \(0\) to \(k-1\), and the value of each digit (from the right) is \(k^0, k^1, k^2, \dots\)

  • Octal (radix-8): symbols 0–7. One octal digit corresponds to exactly 3 bits.
  • Hexadecimal (radix-16): symbols 0–9, A–F. One hex digit corresponds to exactly 4 bits — very convenient for grouping binary.
Dec 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Oct 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 21
Hex 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11

Radix notation conventions

Since a bare number like 101 or 747 is ambiguous, a radix indicator is needed. A subscript works generically (e.g. \(101_2\), \(101_{16}\)); in code/assembly, conventions vary:

Radix Convention Example Where used
Hex leading 0x 0x101 C, Atmel AVR
Hex trailing h 101h some assembly languages
Hex leading $ $747 Atmel AVR assembly
Octal leading 0 0101 C, Atmel AVR
Octal trailing q 101q some assembly languages
Octal leading @ @747 some assembly languages
Binary leading 0b 0b101 Atmel AVR assembly, some C
Binary trailing b 101b some assembly languages
Binary leading % %101 some assembly languages

Boolean Algebra

Logic functions can be expressed as expressions of variables (literals, e.g. \(A, B, X\)) and functions (e.g. \(+, \cdot, \oplus, \bar{\ }\)). Variables and functions can only take values 0 or 1.

Notation conventions

  • Inversion: overline, e.g. \(\text{NOT}(A) = \bar A\) (“A bar”).
  • AND: dot, or implied by adjacency, e.g. \(\text{AND}(A,B) = AB = A \cdot B\).
  • OR: plus sign, e.g. \(\text{OR}(A,B,C) = A+B+C\).
  • Other examples: \(\text{XOR}(A,B) = A \oplus B = \bar A B + A \bar B\); \(\text{NAND}(A,B,C) = \overline{ABC}\); \(\text{NOR}(A,B) = \overline{A+B}\).

Boolean identities

Name AND form OR form
Identity law \(1A = A\) \(0 + A = A\)
Null law \(0A = 0\) \(1 + A = 1\)
Idempotent law \(AA = A\) \(A + A = A\)
Inverse law \(A\bar A = 0\) \(A + \bar A = 1\)
Commutative law \(AB = BA\) \(A + B = B + A\)
Associative law \((AB)C = A(BC)\) \((A+B)+C = A+(B+C)\)
Distributive law \(A + BC = (A+B)(A+C)\) \(A(B+C) = AB + AC\)
Absorption law \(A(A+B) = A\) \(A + AB = A\)
De Morgan’s law \(\overline{AB} = \bar A + \bar B\) \(\overline{A+B} = \bar A \bar B\)

De Morgan’s law also means AND and OR gates can be interchanged if you invert all the inputs and the output — this is why NAND/NOR-only circuits (see logic-gates) can implement any function.

Sum of products

Any logic function can be implemented as the OR of AND combinations of its inputs (a sum of products):

  1. For each row where the truth table output is 1, write the AND term of the inputs (complementing wherever the input is 0) that produces that row.
  2. OR all of those terms together.

This always works, but doesn’t necessarily give the minimum number of gates — the resulting expression can often be simplified further using the identities above. E.g. \(Z = AB + AC = A(B+C)\) (distributive law) uses fewer gates than the raw sum-of-products form.

Logic Gates

Every logic gate has one or more inputs and exactly one output, and can be described four equivalent ways: logic symbol, truth table, Boolean expression, timing diagram (see timing-diagrams for the last of these, and for real-gate propagation delay / rise / fall times).

The 7 basic gate types

Gate Behaviour Truth table (\(A,B \to X\))
NOT (inverter) Inverts the input 0→1, 1→0
AND \(X=1\) iff all inputs are 1 00→0, 01→0, 10→0, 11→1
OR \(X=1\) iff at least one input is 1 00→0, 01→1, 10→1, 11→1
NAND \(X=1\) iff at least one input is 0 (NOT AND) 00→1, 01→1, 10→1, 11→0
NOR \(X=1\) iff all inputs are 0 (NOT OR) 00→1, 01→0, 10→0, 11→0
XOR \(X=1\) iff exactly one input is 1 (“odd function”) 00→0, 01→1, 10→1, 11→0
XNOR \(X=1\) iff inputs are the same (“even function”) 00→1, 01→0, 10→0, 11→1

Useful to remember: XOR is the odd function, XNOR is the even function — this generalises directly to more than 2 inputs (XOR = 1 iff an odd number of inputs are 1).

Universal (complete) gates

All circuits can be constructed from NAND-only or NOR-only gates — these are called complete (or universal) gates, because NOT, AND, and OR can each be built purely from one gate type:

  • NOT: a NAND (or NOR) gate with both inputs tied together.
  • AND: two NANDs in series (NAND followed by another NAND used as an inverter), or the NOR equivalent.
  • OR: built similarly from NAND-only or NOR-only combinations.

NAND and NOR are preferred in practice because they’re easier to build from transistors than AND/OR directly.

Gates on ICs

Example: the 74HCT00 integrated circuit packages four independent 2-input NAND gates into a single 14-pin DIP chip (Vcc = power e.g. 5V, GND = ground/0V; pin spacing 0.1”×0.3”, chip ~15mm long).