CSSE2010 — Week 1 Notes
Lecture 1 — Course Introduction; Bits, Bytes and Binary
See csse2010 for staff, assessment, and course logistics. The technical content of Lecture 1 is below.
Outline
- Course intro, organisation and admin
- Assessment details
- Technical content — binary numbers
What the course is about
Computers, in several different aspects — from a desktop PC down to the microcontrollers embedded in a car, a washing machine or an Arduino board. The semester climbs the stack in three blocks:
| Weeks | Block |
|---|---|
| W01–W05 | Hardware |
| W06–W08 | Low-level software |
| W09–W13 | High-level software |
Levels of abstraction
A computer can be described at six numbered levels, each built on the one below it. Level 0 is where this course starts.
Figure 1: The six levels of abstraction. Each level is implemented in terms of the one below it, so the same machine can be discussed as gates, as an instruction set, or as a C program. In blue: C sits at Level 5, and there is an unnamed level \(-1\) underneath the digital logic level, below the bottom of the numbered stack.
The course works up this stack across the semester, starting at the bottom: Lecture 2 is already at the digital logic level. The three course blocks are not tied to particular numbered levels, only ordered along the stack, but the named levels reappear later as topics in their own right (see instruction-set-architecture for Level 2, and assembly-process and compilation-and-linking for how Levels 4 and 5 are turned into machine code).
Computers and binary numbers
A computer — general purpose or embedded — takes inputs and instructions and produces outputs. All three are binary inside the machine.
Figure 2: The computer as a black box. Inputs, instructions and outputs are all just bit patterns; nothing inside the machine holds a decimal digit, a letter or a sign. Everything from here on is about what a given bit pattern is agreed to mean.
Bits, bytes, nibbles and words
- Bit = binary digit (0 or 1).
- Nibble = 4 bits, the unit that makes hexadecimal convenient.
- Byte = 8 bits, e.g.
01010111. - Word = the natural unit a machine works on, usually a power-of-2 number of bytes: 1, 2, 4 or 8 bytes = 8, 16, 32 or 64 bits. At the two ends of that list, the AVR used in this course has an 8-bit word and modern CPUs are 32- or 64-bit.
Larger amounts are counted in kilobytes, megabytes and gigabytes, which mean powers of 2 for memory but usually powers of 10 for disks (memory-technologies).
Binary numbers
Unsigned binary is covered in full (with diagrams and worked examples) in binary-number-representations. In outline:
- each bit position is worth a power of 2, and binary → decimal is just adding the positions where the bit is 1 — e.g.
10010001= 145; - MSB and LSB — the positions worth the most and least; for an \(n\)-bit unsigned word the MSB is worth \(2^{n-1}\);
- two methods for decimal → binary (sum of powers of 2; repeated division by 2), both worked on 53;
- the unsigned range: all 0’s = 0, all 1’s = \(2^n - 1\);
- other radices — octal (radix 8, 3 bits per digit) and hexadecimal (radix 16, 4 bits per digit);
- how a radix is indicated in code (
0x,$, leading0,0b, subscripts).
Signed numbers are Lab 1’s material; see week1-lab-number-representations.
Worked exercise — convert \(26_{10}\) to octal and hexadecimal
Divide repeatedly by the target radix, exactly as Method 2 does for binary, and read the remainders back.
Figure 3: Converting \(26_{10}\) by repeated division. Dividing 26 by 16 leaves quotient 1 and remainder 10, which is the hex digit A, so \(26_{10}=1\mathrm{A}_{16}\); dividing by 8 leaves quotient 3 and remainder 2, so \(26_{10}=32_{8}\). The check underneath expands each result back out as digit \(\times\) radix\(^{\text{position}}\).
The same answer falls out of the bit pattern directly: \(26_{10} = 00011010_2\), which groups into nibbles as 0001 1010 = 1 A, and into triples as 00 011 010 = 0 3 2 — see the bit-grouping figure in binary-number-representations.
Which radix notations this course uses
Of the ten ways of marking a radix in the full table, five are the ones this course mostly uses:
- a subscript, e.g. \(101_2\) or \(101_{16}\);
- leading
0xfor hex (C, Atmel AVR); - leading
$for hex (Atmel AVR assembly); - leading
0for octal (C, Atmel AVR) — so0101is not one hundred and one; - leading
0bfor binary (Atmel AVR assembly, some C).
The rest (h/q/b suffixes, @ and % prefixes) appear in various assembly languages but not here. Full table in binary-number-representations.
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.).
- 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.
Practice: binary-conversion-drill.
Lecture 2 — Intro to Logic Gates
See logic-gates and boolean-algebra for the reference definitions/tables.
Outline
- Introduction to Logic Gates
- Logic Diagrams
- Boolean Algebra and Logic Expressions
Digital logic
This is level 0, the Digital Logic level, of the abstraction stack from Lecture 1 (see 2026-07-27-course-intro-bits-bytes-binary) — the bottom of the stack, and where the course starts.
- Digital circuits only have two logical levels present (binary):
- logic ‘0’ — usually a small voltage (e.g. around 0 volts);
- logic ‘1’ — usually a larger voltage (e.g. 0.8 to 5 volts, depending on the logic family, i.e. the type/size of the transistors).
- Logic gates are the building blocks of computers. Each gate has one or more inputs and exactly one output, and performs a logic operation (or function). Inputs and outputs can only be in two states, 1 & 0 — also called “true” & “false”.
- 7 basic gate types: NOT, AND, OR, NAND, NOR, XOR, XNOR — see logic-gates for symbols and truth tables.
- Every gate (and every logic function) can be described four equivalent ways: logic symbol, truth table, Boolean expression, timing diagram.
Filling in truth tables
Two habits:
- A 2-input gate’s table has \(2 \times 2 = 4\) rows; \(n\) inputs give \(2^n\) rows.
- Don’t memorise NAND/NOR/XNOR. Write the AND / OR / XOR column first, then invert it row by row — that is all the “N” prefix means. (Both worked questions below are done this way.)
Worked: 3-input NAND truth table
Which truth table is the 3-input NAND?
Write the 3-input AND column first — 0 everywhere except the last row — then invert it. The NAND is the table where \(X = 1\) for every combination except \(A=B=C=1\):
| \(A\) | \(B\) | \(C\) | AND | NAND |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
The “output is HIGH when at least one input is LOW” wording carries over unchanged from two inputs to three.
Worked: 3-input XOR truth table
XOR is the odd function — the 2-input wording “exactly one input is HIGH” does not generalise; the correct statement is that the output is HIGH when an odd number of inputs are HIGH.
So the rows that are 1 are those with one or three 1s — \(001, 010, 100, 111\):
| \(A\) | \(B\) | \(C\) | XOR |
|---|---|---|---|
| 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 |
Correspondingly XNOR is the even function.
Boolean logic functions
A logic function is written as an expression of variables (literals, e.g. \(A\), \(B\), \(X\)) combined by functions — \(+\) (OR), \(\cdot\) (AND), \(\oplus\) (XOR), \(\bar{\ }\) (NOT) — with the output given as a function of the inputs, \(X = f(A,B)\). Variables and functions can only take on the values 0 or 1, and the rules for manipulating such expressions are Boolean algebra.
See boolean-algebra for the full notation conventions, the laws/identities table, De Morgan’s law and its gate equivalents, and the worked simplification example.
Four representations of a logic function
For a function of \(n\) inputs:
- Truth table — lists the output for all \(2^n\) combinations of the inputs. Best to list the input combinations in a systematic way (i.e. counting up in binary).
- Boolean function (or equation) — describes the conditions under which the function output is 1.
- Logic diagram — a combination of logic symbols joined by wires.
- Timing diagram — see timing-diagrams.
Logic diagram conventions
Figure 4: The drawing conventions for a logic diagram, on a two-input example. The two junction dots and the dot-free crossing next to them are the point: A branches down to the lower AND gate and crosses B’s wire on the way, and only the dots say which wires are actually joined.
- Inputs are conventionally drawn on the left, outputs on the right.
- Lines represent electrical wires. A wire can be at high or low potential — logic 1 or logic 0 respectively.
- A filled dot at a junction indicates an electrical connection; wires that cross without a dot are not connected.
Reading Figure 4 off the page as practice: the top AND gets \(\bar A\) and \(\bar B\), the bottom AND gets \(A\) and \(B\), so \(M = \bar A \bar B + AB\) — which is 1 exactly when \(A\) and \(B\) are equal, i.e. XNOR.
Gates on ICs
- Example: the 74HCT00 IC has four 2-input NAND gates in a single 14-pin DIP package — drawn out, with its pin numbers, in logic-gates.
- Vcc = power (e.g. 5V), GND = ground (0V). Pin spacing 0.1”×0.3”; chip ~15mm long.
- The internal drawing of the chip is a schematic; the black plastic part on the bench is the IC. See circuit-schematics for the difference and for how chips get labelled on a buildable drawing.
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. From the truth table:
- For each ‘1’ in the output column, write down the AND combination of inputs that gives that 1 (complementing each input that is 0 in that row).
- OR these 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 |
Four rows are 1, so there are four product terms:
\[M = \bar A BC + A\bar B C + AB\bar C + ABC\]
which simplifies to
\[M = AB + BC + AC\]
This is the majority function: \(M = 1\) whenever at least two of the three inputs are 1. (It comes back as the design task in week2-lab-majority-function-circuit-design.)
NoteThe simplification step
The route is to duplicate \(ABC\) using the idempotent law \(A + A = A\), then pair it with each of the other three terms and use the distributive and inverse laws (all in boolean-algebra):
\[\bar A BC + ABC = BC(\bar A + A) = BC\] \[A\bar B C + ABC = AC(\bar B + B) = AC\] \[AB\bar C + ABC = AB(\bar C + C) = AB\]
The equivalent logic diagram
Figure 5: The sum-of-products expression built directly as a circuit. Gates 1-3 generate the complements; the six vertical rails carry A, B, C and their complements past every gate; gates 4-7 form one product term per ‘1’ row of the truth table; gate 8 ORs them into M. Only the dots are connections - every other crossing is just two wires passing.
This is the unsimplified \(\bar A BC + A\bar B C + AB\bar C + ABC\) drawn literally — three inverters, four 3-input ANDs and a 4-input OR. It is what sum of products gives you before any algebra.
Equivalent functions (simplification)
Sum of products does not necessarily produce the circuit with the minimum number of gates. The Boolean function can be manipulated into an equivalent function using the rules of Boolean algebra (see boolean-algebra).
Example: \(Z = AB + AC = A(B+C)\) by the distributive law.
Figure 6: The same function drawn twice. The left circuit is the sum-of-products form AB + AC and needs three gates; factoring A out with the distributive law gives A(B+C), which needs two. Both have identical truth tables - the algebra is what buys the saving.
A second worked simplification, \(\text{CODE} = C + CD + \overline{(D + \bar D)}\), collapses all the way down to \(\text{CODE} = C\) — the steps are in boolean-algebra.
De Morgan’s law and equivalent circuits
AND and OR can be interchanged if you invert the inputs and the output — the four gate equivalences are drawn in boolean-algebra. Exercise: use truth tables to check that they are valid.
Universal (complete) gates
All circuits can be built from NAND-only or NOR-only gates (called complete gates), because NOT, AND, and OR can each be constructed purely from NAND gates, or purely from NOR gates — the six constructions are drawn in logic-gates. The reason this matters in practice: it is easier to build NAND and NOR gates 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. (Sign-on issues: email eait.mytimetable@uq.edu.au.)
- The slides used in a Learning Lab are released after the last session that week.
- If specific preparation is needed for a lab you will be told; by default, review the previous lectures.
- 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, and week1-lab-number-representations for the Learning Lab 1 session that works the same conversions and the same four signed formats.
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 →
NoteWorking
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 →
NoteWorking
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?
NoteWorking
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).
- Describe how a binary number can be converted into a radix-32 number.
- Describe how a decimal number can be converted into a radix-32 number.
- Convert the decimal numbers 1300 and 2300 to radix-32 representations.
1300 →
2300 →
NoteWorking
- (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\).
- \(1300 \div 32 = 40\) r\(20\); \(40 \div 32 = 1\) r\(8\); \(1 \div 32 = 0\) r\(1\) → digits \(1, 8, 20\)(=K) →
Q5 — Largest unsigned integer
What’s the largest unsigned integer that can be represented in:
- 10 bits
- 9 decimal digits
- 8 hexadecimal digits
(a) 10 bits →
(b) 9 decimal digits →
(c) 8 hexadecimal digits →
NoteWorking
The largest value in \(n\) digits of radix \(r\) is \(r^n - 1\) (all digits at their maximum):
- \(2^{10}-1 = 1023\)
- \(10^9-1 = 999{,}999{,}999\)
- \(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).
NoteWorking
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\)
- \(-16\)
- \(-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 →
NoteWorking
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:
- 16-bit two’s complement
- \(n\)-bit one’s complement
- excess \(2^{m-1}\)
NoteWorking
- (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.
All five ranges at a width small enough to see whole, which is where the asymmetry in (a) and (c) and the symmetry in (b) come from:
Figure 7: The five formats at 4 bits, each bar spanning the values it can represent. Every bar is drawn from the same 16 bit patterns, so a bar that is one value short has spent a pattern twice — and the two that do are exactly the two with a second zero, marked in red with the pair of patterns that share it. That is the whole of why ones’ complement and signed magnitude are symmetric about zero while two’s complement and excess-8 reach one further down than up.
Q9 — Logic gates: NOR and XOR
Draw the logic symbol, write the Boolean function, and write down the truth table for:
- a 4-input NOR gate
- a 3-input XOR gate (i.e. the odd function)
NoteWorking
Figure 8: The two symbols the question asks for. The shapes are distinctive-shape (not IEC rectangle), with inputs left and output right, an open bubble at the boundary for inversion, and XOR’s second concave arc set back from the input edge. Every gate symbol in the Device Pinouts sheet is two-input (or the hex inverter), and the kit contains no 3-or-more-input part, so nothing there shows how to draw a gate with more inputs. The extra input leads are stacked on the same gate body here, as a reasonable extension of the two-input symbols.
(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 |
Number Representations
Learning Lab 1. There is no hands-on prac this week; the prac activities start in week 2. See binary-number-representations for the reference version of everything below.
Worked: two unsigned conversions
Two plain unsigned conversions of the kind in 2026-07-27-course-intro-bits-bytes-binary. The format plays no part yet.
| Question | Answer | Working |
|---|---|---|
| Decimal 37 in 8-bit binary (unsigned) | 00100101 |
\(37 = 32 + 4 + 1 = 2^5 + 2^2 + 2^0\) |
Unsigned binary 01000110 in decimal |
70 | \(64 + 4 + 2 = 70\) |
Wrong answers to recognise: 00110101 is \(53\), which is what you get by mis-decomposing 37 as \(32+16+4+1\). 67, 71 and 72 are all one or two off 70, which is what a slipped bit position costs.
The bare metal
A computer stores everything with high and low voltages, or some other two-state signal: magnetic fields, switches, flash memory. That goes for all of these alike:
- unsigned numbers
- signed numbers
- decimal numbers, characters, images, sounds
You cannot know what data is just by looking at it.
This comes back at the end as “format matters”.
Radices
A radix-\(k\) number system has \(k\) symbols for the digits \(0\) to \(k-1\), and digit values (from the right) \(k^0, k^1, k^2, \dots\)
- Octal (radix-8): symbols 0–7; one octal digit = 3 bits.
- Hexadecimal (radix-16): symbols 0–9 A–F; one hex digit = 4 bits (useful).
Worked: the maximum value in \(n\) radix-\(k\) digits
Answer: \(k^n - 1\).
Two ways to see it:
- The smallest number you can’t represent is a one followed by \(n\) zeroes, whose value is \(k^n\). The largest you can is one less.
- The biggest number is \(n\) copies of the largest digit \(k-1\), i.e. \(\sum_{i=0}^{n-1} k^i (k-1) = k^n - 1\) by the geometric series.
Conversion facts
- A hex digit represents 16 values; so do 4 bits (\(2^4 = 16\)).
- An octal digit represents 8 values; so do 3 bits.
- A base-10 digit represents 10 values; so do \(3.321928\ldots\) bits [citation needed].
- Hex and octal convert to binary digit-by-digit; base-10 does not.
- Three hex digits represent 4096 values; so do four octal digits.
- \(123 = 0123\), but \(456 \neq 4560\) — pad zeroes on the left.
The conversion map
Binary is the hub of the conversions. Only two conversions are digit-by-digit, and both of them have binary at one end.
Figure 9: The conversions between decimal, binary, hexadecimal and octal, drawn as one map. Binary sits in the middle because hexadecimal and octal are both powers of two and so convert to it by regrouping bits, four at a time and three at a time respectively. Decimal is not a power of two, so its two arrows are arithmetic (repeated division, summation of powers) rather than regrouping. There is no direct hex-octal arrow: converting 0xC55E7201 to octal goes the long way, through 32 bits of binary. The box colours carry no meaning.
Worked conversions
Group binary into 4s for hex, 3s for octal, padding on the left:
| From | To | Working | Result |
|---|---|---|---|
001001101001 |
hex | 0010 0110 1001 |
0x269 |
01001101001 |
octal | 001 001 101 001 |
\(1151_8\) |
0xA1E |
binary | 1010 0001 1110 |
101000011110 |
| \(703_8\) | binary | 111 000 011 |
111000011 |
0xC55E7201 |
octal | regroup 32 bits into 3s (pad one zero): 011 000 101 010 111 100 111 001 000 000 001 |
\(30527471001_8\) |
Hex → octal has no shortcut: go via binary.
Negative numbers
Computers don’t store \(+\) and \(-\); four formats have been used. Two’s complement is what is practically used.
All four — and unsigned — use the same representation for positive numbers.
Signed magnitude
Leftmost bit is the sign (0 positive, 1 negative) and does not contribute to the magnitude. Negate by inverting the sign bit alone.
Ones’ complement
The sign bit now also contributes to the magnitude: its position value is \(-(2^{N-1}-1)\). Negate by inverting all the bits.
Two’s complement
The sign bit’s position value is \(-2^{N-1}\). Negate by inverting all the bits and adding 1.
Excess-\(2^{N-1}\)
For 8 bits, “excess 128”: the number is stored as its true value plus 128. So \(-3\) is stored as \(125\), and \(3\) as \(131\).
It is the same as two’s complement with the sign bit reversed — a 0 in the MSB means bit value \(-128\), a 1 means 0. Practical use: comparing two signed numbers becomes simple in hardware.
All of it in one picture
Write each format as a row of bit weights and stack the rows. They differ in one column only.
Figure 10: The four signed formats and unsigned, as stacked strips of bit weights. Every format gives bits 6 down to 0 exactly the same weights; the only thing any of them changes is what bit 7 is worth. Signed magnitude and excess-128 do not give bit 7 a weight at all — they give it a meaning, which is why those two boxes say what a 0 and a 1 mean rather than give a number. In signed magnitude the sign bit is not a magnitude position: only bits 6 to 0 carry magnitude.
The shaded column is the only one that differs. The reason two’s complement wins is not that it is cleverer at representing negatives; it is that \(-128\) is the only choice of bit-7 weight that leaves the whole row a plain sum of place values, with no special rule attached to the top bit. That is exactly what makes its addition ordinary binary addition, with no case analysis and no end-around carry. Limitations below says the same in words.
The ±47 example, 8-bit
\(+47 = \texttt{00101111}\) in all four formats.
| Format | \(-47\) |
|---|---|
| Signed magnitude | 10101111 |
| Ones’ complement | 11010000 |
| Two’s complement | 11010001 |
| Excess-128 | 01010001 |
And the 4-bit \(-3\) examples: ones’ complement 1100, two’s complement 1101.
Ranges
| Format | Range |
|---|---|
| 8-bit signed magnitude | \(-127\) to \(127\) |
| \(n\)-bit signed magnitude | \(-(2^{n-1}-1)\) to \(2^{n-1}-1\) |
| 8-bit ones’ complement | \(-127\) to \(127\) |
| 8-bit two’s complement | \(-128\) to \(127\) |
| \(n\)-bit two’s complement | \(-2^{n-1}\) to \(2^{n-1}-1\) |
| 8-bit excess-128 | \(-128\) to \(127\) |
Why “complement”
In the loose mathematical sense, a thing and its complement together make a whole. An angle and its complement make a right angle; a graph and its complement a complete graph; a set and its complement a universal set.
- In ones’ complement, a number plus its negative gives a string of ones (
11111111in 8 bits). - In two’s complement, a number plus its negative gives a power of two, with overflow (
1 00000000). It would more correctly be called power-of-two’s complement. - Base 10 has the equivalent nines’ and ten’s complements, used on some early mechanical adding machines to do subtraction.
Limitations
Two representations of zero — undesirable, because it wastes a bit pattern that could have extended the range:
- Signed magnitude:
00000000and10000000 - Ones’ complement:
00000000and11111111
Asymmetric range: two’s complement and excess-\(2^{m-1}\).
Arithmetic: signed-magnitude addition requires taking cases; ones’ complement addition requires an extra addition step; sign extension and comparisons are non-trivial in both.
Two’s complement has one zero, and its addition is just binary addition — which is why it wins.
Format matters
“What is 10010010 converted to decimal?” cannot be answered as asked. It depends on the format:
| Read as | Value |
|---|---|
| 8-bit unsigned | 146 |
| Two’s complement | \(-110\) |
| Ones’ complement | \(-109\) |
| Signed magnitude | \(-18\) |
| Excess-128 | 18 |
In the same way, 01010101 could be 85 (8-bit unsigned), \(-43\) (excess-128), 'U' (ASCII), or 10.625 (8-bit fixed point, 5 bits before the point and 3 after).
Binary data is meaningless unless you know the format. The format is not encoded in the data — it has to be known separately, by a human, a program, or the hardware.
Exercise — the five-format table
Write the decimal interpretation of every 4-bit pattern under each format:
| Pattern | Unsigned | Sign-mag | Ones’ comp | Two’s comp | Excess-8 |
|---|---|---|---|---|---|
0000 |
0 | 0 | 0 | 0 | \(-8\) |
0001 |
1 | 1 | 1 | 1 | \(-7\) |
0010 |
2 | 2 | 2 | 2 | \(-6\) |
0011 |
3 | 3 | 3 | 3 | \(-5\) |
0100 |
4 | 4 | 4 | 4 | \(-4\) |
0101 |
5 | 5 | 5 | 5 | \(-3\) |
0110 |
6 | 6 | 6 | 6 | \(-2\) |
0111 |
7 | 7 | 7 | 7 | \(-1\) |
1000 |
8 | \(-0\) | \(-7\) | \(-8\) | 0 |
1001 |
9 | \(-1\) | \(-6\) | \(-7\) | 1 |
1010 |
10 | \(-2\) | \(-5\) | \(-6\) | 2 |
1011 |
11 | \(-3\) | \(-4\) | \(-5\) | 3 |
1100 |
12 | \(-4\) | \(-3\) | \(-4\) | 4 |
1101 |
13 | \(-5\) | \(-2\) | \(-3\) | 5 |
1110 |
14 | \(-6\) | \(-1\) | \(-2\) | 6 |
1111 |
15 | \(-7\) | \(-0\) | \(-1\) | 7 |
The two \(-0\) entries are the wasted patterns. Excess-8 is the two’s complement column with the sign bit flipped.
Esoteric formats
Not examinable: binary coded decimal with sign pattern; negabinary (base \(-2\)); zig-zag encoding; LEB128; quarter-imaginary base (base \(2i\)) and the Davis–Knuth “twindragon” base (base \(i-1\)) for Gaussian integers; and “integers don’t exist” — JavaScript.
Admin
Lab kits are used during the lab from week 2 and loaned out later (see week3-lab-logisim-and-flip-flops). If you’re on your own laptop you’ll need two USB-A connections from week 11, and one from week 8 — get a dongle early if you need one. Prac activities start in week 2. Catch up on the lecture content before attending a lab.
There is a summary recording on Blackboard covering the signed binary formats, to be watched before week 2.
See also
- binary-number-representations — the reference version of every format here
- week-one-exercises — the week 1 problem set, which reuses this lab’s
1001101001conversion and asks for the same four formats at other widths - 2026-07-27-course-intro-bits-bytes-binary — Lecture 1, the unsigned conversions
- csse2010-sample-midsem-5 · csse2010-sample-midsem-6 — questions 1 to 4 of each paper are exactly this material
Reference material
The Assembly Process
How an assembly language program becomes machine code. It covers the four fields of a statement, the directives that tell the assembler what to do as opposed to the CPU, the three memory segments of the AVR and the location counter that walks through each, and the two-pass assembler with its symbol table, which is how a program can jump to a label it has not reached yet. The program skeleton these pieces fit into is avr-program-structure, and the memories the segments map onto are in memory-models and avr-architecture. First met in 2026-10-08-assembly-process.
What an assembler does
An assembler turns a text file of assembly language into the bits that go into the chip’s memories. Most of that is translation, one statement at a time: add r1, r2 has a fixed binary form, 0000 1100 0001 0010, and nothing else in the file can change it (avr-instructions). Each instruction becomes exactly one machine instruction (instruction-set-architecture).
Two things make it more than a lookup table:
- A program is more than instructions. It has to say where things go in memory, reserve space for variables, put constant tables in flash and give registers and addresses readable names. None of that is an instruction for the CPU. These lines are directives, commands to the assembler itself.
- Names stand for numbers that are not known yet.
jmp RESETneeds the address ofRESET, and ifRESET:is further down the file, a single read from top to bottom cannot supply it. The cure is to read the file twice.
C reaches machine code by a different road: the compiler turns one line of C into many instructions (2026-09-07-introduction-to-embedded-c-programming), and how that output is joined into a program is compilation-and-linking.
The format of a statement
An assembly program is a sequence of one-line statements. A statement has up to four fields, and any of them may be empty:
Figure 11: The four fields of one assembly statement. The label names the address this statement ends up at, so other statements can jump to it or refer to the data there. The operation field holds the mnemonic, which is either an instruction for the CPU or, if it starts with a dot, a directive for the assembler. The operands are what the operation works on: registers, constants or symbols, separated by commas. The comment runs from the semicolon to the end of the line and is thrown away by the assembler.
Label. A name for a position in memory. Labels exist so that statements can be jumped to and so that data can be referred to by name. Its value is the address the statement lands at: a word address in program memory for code, a byte address in data memory for a variable. By convention a label starts in column 1 and everything else is indented, so labels stand out down the left edge. In AVR assembly it ends with a colon.
Operation. A symbolic abbreviation for an instruction’s opcode, a mnemonic: LDS for Load Direct from data Space, ldi for load immediate. Or a directive, which starts with a dot.
Operands. The registers and addresses the instruction uses. Register names belong to the machine:
| Machine | Register names |
|---|---|
| Pentium | eax, ebx, esi, edi, … |
| SPARC | o0..o7, i0..i7, l0..l7, g0..g7 (out, in, local and global) |
| AVR | simply r0..r31 |
An address operand is usually written as a label, lds r16, count, and the assembler substitutes the number.
Comment. Space for explanation, only for people: the assembler discards it. In assembly comments are not optional politeness. ldi r20, 13 says nothing about why; the comment is the only place the intent is written down.
Ending a statement. Some assemblers want a semicolon at the end of every statement and others do not. AVR assembly does not: the end of the line ends the statement, and a semicolon starts a comment.
Directives
Besides instructions, the assembler needs other information, for example:
- where in memory the code and data should go;
- nicer names for registers and addresses, such as
tempforr16orSPHfor I/O address0x3E; - space for variables and tables of constants.
That information is given as a directive, also called a pseudo-instruction: a command to the assembler itself, written where an instruction would be and preceded by a dot, as in .byte or .def temp = r16. Most directives produce no machine code at all. They change what the assembler knows or where it is putting things.
The assembler in Microchip Studio, AVRASM2, has these, among others:
| Directive | What it does |
|---|---|
.byte |
reserve bytes for a variable |
.cseg |
switch to the code segment |
.csegsize |
set the program memory size |
.db |
define constant byte(s) |
.def |
give a register a symbolic name |
.device |
name the exact processor the program is for |
.dseg |
switch to the data segment |
.dw |
define constant word(s) |
.equ |
set a symbol equal to an expression, permanently |
.eseg |
switch to the EEPROM segment |
.exit |
stop processing this file |
.include |
read source from another file, here |
.list, .nolist |
turn generation of the list file on, off |
.listmac |
show macro expansions in the list file |
.macro, .endm (or .endmacro) |
begin, end a macro |
.org |
set the location counter: the address of what comes next |
.set |
set a symbol equal to an expression, changeably |
.if, .else, .elif, .endif |
conditional assembly: include lines only if a condition holds |
All of this is AVRASM2’s syntax. Other assemblers, even ones for the AVR, spell things differently. The GNU assembler used behind avr-gcc has a .byte directive too, and there it stores the bytes listed instead of reserving space.
Segments and location counters
The AVR has three memories (avr-architecture), and to the assembler each is a segment. Directives choose which segment the following lines go into:
| Segment | Directive | Memory | What can go there |
|---|---|---|---|
| code | .cseg |
flash, program memory | instructions, and constant data |
| data | .dseg |
SRAM, data memory | space only, reserved for variables |
| EEPROM | .eseg |
EEPROM | constants |
The data segment cannot be given values. The assembler’s output is programmed into flash and EEPROM, which keep their contents with the power off. SRAM is empty at power-up and holds nothing until the running program writes to it, so all the assembler can do there is decide which addresses each variable will use.
Each segment has its own location counter: the address the next thing in that segment will be placed at. A label takes the current value of its segment’s counter, and every statement that places something advances the counter by its size. Switching segment does not reset anything. It only changes which counter is in use, so a segment can be built up in pieces, and each piece carries on where the last piece of the same segment stopped.
Figure 12: One source file feeding three memories. The file switches segment four times, and each piece goes to the memory its directive names, carrying on from where the previous piece of the same segment stopped: the second code piece follows the first in flash, and total follows count in SRAM. Each segment has its own location counter. The code counter starts at 0 and counts 16-bit words. The data counter starts at 0x0100, the first address after the registers and I/O, and counts bytes. The EEPROM counter starts at 0 and counts bytes. Grey marks code, blue data and green EEPROM.
Where each counter starts:
- Code: at 0, the reset address, and the assembler starts in the code segment, so a file with no segment directives is all code. The counter counts 16-bit words, because each program-memory address names a word (memory-models).
- Data: at the first free SRAM address,
0x0100on the ATmega324A, since0x0000to0x00FFare the registers and I/O registers. The counter counts bytes. - EEPROM: at 0, counting bytes.
.org sets the counter of the current segment to a given value, so whatever follows is placed there. It works in any segment, in that segment’s units.
Reserving and defining data
Three directives put data in memory:
| Directive | Segment | Places | Size |
|---|---|---|---|
.byte n |
data | nothing: reserves n bytes |
n bytes |
.db a, b, … |
code or EEPROM | constant bytes, 8 bits each | one byte each |
.dw a, b, … |
code or EEPROM | constant words, 16 bits each | two bytes each |
.byte is allowed only in the data segment: it is how a variable gets an address. .db and .dw initialise constants, so they belong where constants can live: the code segment or the EEPROM segment.
.db in the code segment packs two bytes per word. Program memory is 16 bits wide, so consecutive bytes share a word, the first in the low byte and the second in the high byte. A .db line with an odd number of bytes leaves half a word over, and the assembler fills it with a zero pad byte so that the next line starts on a whole word. Each .db line is padded on its own, so two 5-byte lines take 3 words each, not 5 words between them. AVRASM2 warns when it pads. Writing the 0 yourself gives the same layout without the warning.
.dw takes one whole word per value, so it is the natural way to store numbers bigger than 255, or addresses.
Worked: a lookup table in flash
A lookup table (LUT) is a table of constants a program reads instead of computing. Lay out:
.cseg
table1: .db 11, 12, 30
table2: .dw 100, 133
.org 500
table3: .dw ...The code counter starts at 0.
table1= 0. Three bytes: 11 and 12 share word 0, 30 takes the low half of word 1, and a pad 0 fills its high half. The counter moves to 2.table2= 2. Two words, 100 at word 2 and 133 at word 3. The counter moves to 4..org 500sets the counter to 500. Words 4 to 499 are skipped, and nothing is placed there.table3= 500 (0x01F4).
Figure 13: The lookup table laid out in program memory, one 16-bit word per row, lowest address at the top. A .db puts two bytes in each word, the first in the low byte, and pads an odd count with a zero byte so that the next label starts on a whole word: here 30 shares word 1 with a pad. Each .dw value fills a whole word. The .org moves the location counter forward and leaves words 4 to 499 untouched, so table3 lands at word 500. The diagonal break means the gap is not drawn to scale. Grey marks the .db bytes, dark grey the pad and blue the .dw words.
On the data side, two .byte 2 lines in separate .dseg pieces end up next to each other, at 0x0100 and 0x0102, whatever code sits between them in the file. That is worked in 2026-10-08-assembly-process.
Naming things: .def, .equ and .set
Three directives give a name to something. None of them places anything or moves a location counter.
| Directive | Names | Can it be changed later? | Example |
|---|---|---|---|
.def |
a register, and only a register | yes, by another .def |
.def ZH = r31 |
.equ |
a value: a number, an I/O address, an expression | no | .equ sreg = 0x3f ; Status register |
.set |
a value | yes, by another .set |
.set io_offset = 0x23 ; For now |
.equ is the usual choice for a constant, because a second definition is an error and catches a clash of names. .set is for a value that a later part of the file deliberately redefines, which is what for now in the comment above says.
Check. The same program defines .equ SPH = $3E and .def ZH = r31. Why .equ for one and .def for the other? SPH is an I/O register, which instructions such as out reach by its I/O address, 0x3E. To the assembler that is just a number, so .equ. ZH is general-purpose register r31, the high byte of the Z pointer, which instructions name as a register operand, so .def.
Two more directives are about files and the processor rather than names:
.include "file"reads another file in at that point, as if its text were typed there..include "m324Adef.inc"is howPORTA,SPH,RAMENDand the rest get defined: the file is mostly.equand.deflines (avr-io-ports)..device ATmega324Anames the exact processor. The assembler then rejects any instruction that chip does not implement..exitstops reading the file at that line. Anything after it is ignored.
The forward reference problem
Read top to bottom, most statements can be translated on the spot. add r1, r2 names two registers and nothing else, so its machine word is known at once.
A label used before it is defined is different. A program usually starts with
jmp RESET
...
RESET: ldi temp, low(RAMEND)When the assembler reaches the jmp, it knows the opcode but not the operand: RESET has not been seen, so there is no address to put in the instruction. This is the forward reference problem. One forward reference anywhere in a file is enough to stop a single top-to-bottom pass from finishing the job.
The two-pass assembler
The fix is to process the file twice.
Pass one: define every symbol. Go through the file without generating anything. Keep a location counter for each segment, starting at 0 for code and EEPROM and at 0x0100 for data. For each line:
- if it has a label, enter the label in the symbol table with its segment and the current value of that segment’s counter;
- if it is
.equ,.setor.def, enter that name and its value; - if it is
.cseg,.dsegor.eseg, switch counters; if it is.org, set the current counter; - advance the current counter by the line’s size: 1 or 2 words for an instruction, the padded number of words for
.db, a word per value for.dw,nbytes for.byte n, and 0 for a line that only names something.
Pass one only needs each line’s size, and every instruction’s size is known without knowing its operands: jmp RESET takes 2 words whatever RESET turns out to be.
Pass two: assemble. Go through the file again with the counters reset. Now every symbol’s value is in the table, so each instruction can be assembled, turned into actual machine code, with its operands filled in, and each .db and .dw value can be written.
Figure 14: The two-pass assembler. Pass one reads the whole source and produces no code: it steps the location counters and records each symbol’s segment and value in the symbol table. Pass two reads the same source again from the top and, with every value now in the table, encodes each instruction and writes each constant. Its output is the contents of flash and of EEPROM. The data segment produces no output, only the addresses its labels were given.
Worked: a two-pass trace
The program:
.equ RAMEND = $08FF
.equ SPH = $3E
.equ SPL = $3D
.def ZH = r31
.def ZL = r30
jmp RESET
.dseg
var1: .byte 2
var2: .byte 2
.cseg
.def temp = r16
mesg: .db 72,101,108,108,111
table: .dw var1, var2
RESET: ldi temp, low(RAMEND)
out SPL, temp
ldi temp, high(RAMEND)
out SPH, temp
...
ldi ZH, high(mesg*2)
ldi ZL, low(mesg*2)
lpm ;R0 <= M[Z]Pass one. The code counter starts at 0 and the data counter at 0x0100 (256).
- The five
.equand.deflines enterRAMEND,SPH,SPL,ZHandZLin the table and place nothing. jmp RESETis a 2-word instruction, so it takes words 0 and 1 and the code counter goes to 2.RESETis not known yet, and pass one does not need it to be..dsegswitches to the data counter.var1= 256 (0x0100) and.byte 2moves the counter to 258.var2= 258 (0x0102) and the counter goes to 260..csegswitches back to the code counter, still at 2..def temp = r16enterstemp.mesg= 2. Five bytes need three words with a pad, words 2 to 4, and the counter goes to 5.table= 5. Two words, 5 and 6, and the counter goes to 7.RESET= 7. Each of the four instructions from here is one word:ldiat 7,outat 8,ldiat 9,outat 10.
The counters run code 0, 2, 5, 7, 8, 9, 10, 11 and data 256, 258, 260. The EEPROM counter is never used.
Figure 15: Pass one over the example, line by line. The two address columns show where each line is placed in its own segment, so a range means the line takes several words or bytes: the jmp two words, the 5-byte .db three words with its pad, the .dw two words, each .byte 2 two bytes. Lines that only name something or switch segment take no space and have no address. The code and data counters advance independently, which is why mesg comes straight after the jmp even though the data lines sit between them in the file. On the right is the symbol table pass one leaves behind: every name, the segment its value belongs to, and the value. The .equ and .def names have no segment.
So the instruction at RESET is at program address 7, mesg is at 2, table at 5, and the variables at 256 and 258.
Only one reference in the program is forward: jmp RESET. Every other symbol (RAMEND, var1, var2, mesg, SPL, SPH, ZH, ZL, temp) is defined above the line that uses it. One is enough to need the second pass.
Worked: what pass two writes
With the table complete, pass two replaces every symbol by its value and encodes:
| Address | Statement | With symbols replaced | Machine word(s) |
|---|---|---|---|
| 0–1 | jmp RESET |
jmp 7 |
0x940C 0x0007 |
| 2–4 | .db 72,101,108,108,111 |
bytes 72, 101, 108, 108, 111 and a pad 0 | 0x6548 0x6C6C 0x006F |
| 5–6 | .dw var1, var2 |
.dw 0x0100, 0x0102 |
0x0100 0x0102 |
| 7 | ldi temp, low(RAMEND) |
ldi r16, 0xFF |
0xEF0F |
| 8 | out SPL, temp |
out 0x3D, r16 |
0xBF0D |
| 9 | ldi temp, high(RAMEND) |
ldi r16, 0x08 |
0xE008 |
| 10 | out SPH, temp |
out 0x3E, r16 |
0xBF0E |
| later | ldi ZH, high(mesg*2) |
ldi r31, 0x00 |
0xE0F0 |
| later | ldi ZL, low(mesg*2) |
ldi r30, 0x04 |
0xE0E4 |
| later | lpm |
lpm |
0x95C8 |
Points worth checking by hand:
ldi r16, 0xFF. The form is1110 KKKK dddd KKKK, withddddthe register number minus 16.K=1111 1111anddddd=0000, so1110 1111 0000 1111=0xEF0F.- The
.dbwords. The first byte of each pair is the low byte: 72 and 101 make0x6548. The odd fifth byte, 111 =0x6F, shares its word with the pad. low()andhigh()split a 16-bit value into its bytes at assembly time.RAMEND=0x08FFgives0xFFand0x08: this is the stack pointer being set to the top of SRAM (procedures-and-the-stack).mesg*2.mesgis a word address, 2.lpmreads one byte of program memory from the byte address in Z, and word 2 starts at byte 4. So Z =0x0004, andlpmloadsr0with the byte there, 72, theHofHello. The two kinds of address are drawn in memory-models.tableholds the two variables’ addresses,0x0100and0x0102: a table of pointers, in flash, into the data segment.
Common mistakes
- Counting
jmpas one word. It is two, because it carries a full program address (avr-branches-and-jumps).rjmpis one. - Forgetting the pad. A
.dbline with an odd number of bytes takes a whole extra word, and each line is padded separately. - Counting
.dbbytes as words. Two bytes share a word in program memory. - Letting
.dseglines move the code counter, or the other way round. Each segment has its own counter, and switching segments only chooses which one is in use. - Giving size to lines that only name things.
.equ,.set,.def,.cseg,.dseg,.includeand comments place nothing. - Expecting
.byteto store a value..byte 2reserves two bytes. It does not put a 2 anywhere. Constants go in flash or EEPROM with.dbor.dw. .deffor a constant, or.equfor a register..defis for registers only.- Redefining an
.equ. It cannot be changed; that is what.setis for. - Handing a code label straight to
lpm. A code label is a word address.lpmwants the byte address, the label times 2. - Ending statements with a semicolon out of habit from another language. In AVR assembly it starts a comment.
- Assuming another assembler reads the same way. Directive names and meanings change between assemblers, even for the same chip.
See also
- avr-program-structure — the skeleton: vector table,
RESET, the main loop, and where segments and directives go in it - memory-models — word and byte addresses, cell sizes, and the AVR’s separate address spaces
- avr-architecture — flash, SRAM and EEPROM, the three memories behind the three segments · memory-technologies — what each of the three is as a technology
- avr-instructions · avr-branches-and-jumps — instruction sizes, which decide how far the code counter moves
- avr-interrupts —
.orgplacing eachjmpin the vector table - procedures-and-the-stack — the stack pointer set-up the worked example starts with
- instruction-set-architecture — assembly as a level, one line to one instruction
- compilation-and-linking — the road to machine code from C
- 2026-10-08-assembly-process — Lecture 20
Binary Conversion Drill
Convert between different number representations. All binary numbers are eight bits.
On the HTML site, fill in the blank with your answer (as a quoted string, e.g. "1A"), then click Run Code on the exercise to check. Reload the page for a new random question. In the PDF, the reference implementation is shown instead (interactive exercises need a browser).
The two short reference sections below are the minimum needed to attempt the drills without looking anything up; for the full treatment see binary-number-representations, and for the lab on these conversions, week1-lab-number-representations. Fractions, which these drills leave out, are in fixed-point-numbers and floating-point-numbers.
Doing a base conversion: one number, all four bases
The first drill picks two of decimal, hexadecimal, octal and unsigned binary at random and asks you to convert between them. Which pair comes up decides whether the job is regrouping or arithmetic:
- A hexadecimal digit stands for sixteen values, and so do 4 bits (\(2^4 = 16\)). An octal digit stands for eight values, and so do 3 bits. Both therefore convert to binary digit by digit, with no arithmetic at all.
- A base-10 digit stands for ten values, and so do \(3.321928\ldots\) bits — not a whole number. Decimal never lines up with a group of bits, so every decimal conversion costs real arithmetic: repeated division by 2 going in, a sum of powers of two coming out.
Figure 16: The same value, 205, written in all four bases the first drill uses, with the two groupings drawn on the one row of bits. The hexadecimal nibbles and the octal triples are cut from the same eight bits; the octal grouping needs a padding zero on the left, by the rule that 123 = 0123 but 456 is not 4560.
Two things to carry into the drill:
- Group from the right, and pad the leftmost group with zeroes. If the bit count is not a multiple of 3 or 4, the short group is the leading one. \(123 = 0123\), but \(456 \neq 4560\).
- Hex to octal has no shortcut. Three and four bits share no smaller common grouping, so expand the hex digits to bits and regroup them in threes. For example,
0xC55E7201becomes 32 bits, pads to 33, and regroups as \(30527471001_8\).
Doing a signed conversion: four recipes on the same number
The second drill converts between decimal and the four signed formats. Going from decimal to bits, each format has its own recipe, and only one of them is really a negation at all.
Figure 17: Plus and minus 47 carried through all four formats, arranged so the recipes can be compared on one number. Orange marks the bit a recipe actually changes; blue marks bits that are recomputed wholesale. The last row is the trap: excess-128 biases positive values too, so it is the one format that does not share the positive patterns with the others.
As a table, for looking up mid-drill:
| Format | Encode a negative by | Range, 8-bit |
|---|---|---|
| Signed magnitude | inverting the sign bit alone | \(-127\) to \(+127\) |
| Ones’ complement | inverting all the bits | \(-127\) to \(+127\) |
| Two’s complement | inverting all the bits and adding 1 | \(-128\) to \(+127\) |
| Excess-128 | storing value \(+128\) as plain unsigned | \(-128\) to \(+127\) |
Signed magnitude and ones’ complement each spend two of their 256 patterns on zero (00000000 and 10000000; 00000000 and 11111111), which is exactly the one value of range they give up compared with two’s complement.
Number base conversion
A random question is generated once per page load using an ojs cell, then passed into the Python exercise cells below via the input cell option – this keeps the question stable across repeated “Run Code” clicks (setup blocks re-run on every evaluation, so randomising there would change the question out from under the learner).
Signed number format conversion
Reading one pattern under one format
“What is 10010010 converted to decimal?” has no answer until someone names the format. This drill is that question, generated: it hands you eight bits and one format, and asks what value they hold. Answer with a plain integer (e.g. -110), not a string.
Binary Number Representations
Bits, bytes, and words
- Bit = binary digit (0 or 1).
- Nibble = 4 bits. It is the unit that makes hexadecimal convenient (one hex digit = one nibble).
- 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. The AVR used in this course is at the small end — an 8-bit (1-byte) word; modern CPUs sit at the other end, 32- or 64-bit.
Representing whole (unsigned) numbers
Each bit position has a value — a power of 2, increasing from right (least significant) to left (most significant). Binary → decimal: add the values of each position where the bit is 1.
Figure 18: Place values for an unsigned binary number, and a worked conversion. Position \(i\) is worth \(2^i\), so reading a binary number is just adding the place values of the positions holding a 1: \(10010001_2 = 128 + 16 + 1 = 145\).
Most and least significant bits
Figure 19: The two ends of a word get names, because almost every later convention (shifting, sign bits, bit numbering in AVR registers) is stated in terms of them. For an \(n\)-bit unsigned word the MSB is worth \(2^{n-1}\) — here \(2^7 = 128\) — and the LSB is always worth \(2^0 = 1\).
Converting decimal to binary
Two equivalent methods, both worked on the same number, 53.
Method 1 — sum of powers of 2. Rewrite \(n\) as a sum of powers of 2, by repeatedly subtracting the largest power of 2 not greater than \(n\) (\(53 - 32 = 21\), \(21 - 16 = 5\), \(5 - 4 = 1\), \(1 - 1 = 0\)). Then assemble the binary number from 1’s in the bit positions corresponding to those powers of 2, and 0’s everywhere else.
Figure 20: Method 1 on \(53\). Each power of two in the decomposition names one bit position — \(2^5\) is position 5, \(2^4\) is position 4, and so on — and every position with no term in the sum gets a 0. Reading the row off left to right gives \(00110101_2\).
Method 2 — repeated division. Build the bits up from the right (least significant): divide \(n\) by 2, the remainder (0 or 1) is the next bit, then repeat with \(n\) = the quotient. Stop when the quotient reaches 0, and read the remainders upwards.
Figure 21: Method 2 on \(53\). The remainders come out LSB-first, which is why the answer has to be read back up the column: \(110101_2\), or \(00110101_2\) padded to a byte. The same procedure with a divisor of 16 or 8 converts to hexadecimal or octal instead.
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).
The \(-1\) is the part worth understanding: an \(n\)-bit word has \(2^n\) distinct patterns, but one of them is spent on zero.
Figure 22: Why the largest unsigned value is \(2^n-1\) and not \(2^n\). Counting up from all-zeros steps through every pattern in turn — each extra bit doubles how many there are, so 8 bits give \(2^8 = 256\) patterns — and because the count starts at 0, the last one is 255.
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\) — so a radix-\(k\) number \(d_{m}\dots d_1 d_0\) is worth \(\sum_i d_i k^i\). E.g. \(1\mathrm{A}_{16} = 1 \cdot 16^1 + 10 \cdot 16^0 = 16 + 10 = 26\).
- 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 |
Converting binary ↔︎ hex/octal by grouping
Because \(16 = 2^4\) and \(8 = 2^3\), no arithmetic is needed: group the bits from the right — four at a time for hex, three at a time for octal — and translate each group with the table above. Pad the leftmost group with leading zeros.
Figure 23: One bit pattern read two ways. Grouping \(00011010_2\) into nibbles from the right gives \(1\) and \(\mathrm{A}\), i.e. \(1\mathrm{A}_{16}\); grouping the same bits in threes gives \(0\), \(3\) and \(2\), i.e. \(32_{8}\). The grouping must start at the right — starting at the left gives the wrong answer whenever the width is not a multiple of 3 or 4.
The same trick read backwards is why hex is used for bit patterns at all: a full byte of 1’s, 1111 1111, is F F = \(\mathtt{0xFF}\) = 255, and any byte can be written as two hex digits.
To convert decimal → any radix, use Method 2 with that radix as the divisor: \(26 \div 16\) gives quotient 1 remainder 10 (= A), so \(26_{10} = 1\mathrm{A}_{16}\); \(26 \div 8\) gives quotient 3 remainder 2, so \(26_{10} = 32_8\). See 2026-07-27-course-intro-bits-bytes-binary for that worked exercise.
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. Bolded rows are the ones this course mostly uses:
| Radix | Convention | Example | Where used |
|---|---|---|---|
| any | subscript | \(101_2\), \(101_{16}\) | generic/mathematical |
| 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 |
The octal convention is the trap: in C, a leading 0 silently changes the radix, so 0101 is \(65_{10}\), not \(101_{10}\).
Representing signed numbers
Computers don’t store \(+\) and \(-\) signs; the sign has to be encoded in the bits themselves. Four formats have been used, and all four — plus unsigned — represent positive numbers identically. Only the negatives differ.
Signed magnitude
The leftmost bit is a sign bit (0 positive, 1 negative) and contributes nothing to the magnitude. Negate by inverting the sign bit alone.
Ones’ complement
The sign bit now also carries weight: its position value is \(-(2^{N-1}-1)\). Negate by inverting all the bits.
Two’s complement
The sign bit’s position value is \(-2^{N-1}\). Negate by inverting all the bits and adding 1. This is the one actually used in practice.
Compare the position values, 8-bit:
| bit 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|
| Signed magnitude | sign | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Ones’ complement | \(-127\) | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Two’s complement | \(-128\) | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Excess-\(2^{N-1}\)
For 8 bits, “excess 128”: the value stored is the true value plus 128. So \(-3\) is stored as \(125\) and \(3\) as \(131\).
It is exactly two’s complement with the sign bit reversed — a 0 in the MSB means bit value \(-128\), a 1 means 0. Its practical use is that comparing two signed numbers becomes simple in hardware. The exponent of an IEEE floating-point number is stored in excess notation for exactly that reason, with a bias one smaller: excess-127 for 8 bits (floating-point-numbers).
Ranges
| Format | 8-bit | \(n\)-bit |
|---|---|---|
| Unsigned | \(0\) to \(255\) | \(0\) to \(2^n - 1\) |
| Signed magnitude | \(-127\) to \(127\) | \(-(2^{n-1}-1)\) to \(2^{n-1}-1\) |
| Ones’ complement | \(-127\) to \(127\) | \(-(2^{n-1}-1)\) to \(2^{n-1}-1\) |
| Two’s complement | \(-128\) to \(127\) | \(-2^{n-1}\) to \(2^{n-1}-1\) |
| Excess-\(2^{n-1}\) | \(-128\) to \(127\) | \(-2^{n-1}\) to \(2^{n-1}-1\) |
Worked example — \(\pm 47\) in 8 bits
\(+47 = \texttt{00101111}\) in every format.
| Format | \(-47\) | How |
|---|---|---|
| Signed magnitude | 10101111 |
flip the sign bit |
| Ones’ complement | 11010000 |
invert all bits |
| Two’s complement | 11010001 |
invert all bits, add 1 |
| Excess-128 | 01010001 |
\(-47 + 128 = 81\) |
And in 4 bits, \(-3\) is 1100 in ones’ complement and 1101 in two’s complement.
Why “complement”?
A thing and its complement together make a whole — an angle and its complement make a right angle, a set and its complement a universal set.
- Ones’ complement: a number plus its negative gives a string of ones (
11111111in 8 bits). - Two’s complement: a number plus its negative gives a power of two, with overflow (
1 00000000). It would more accurately be called power-of-two’s complement.
Base 10 has the same pair — nines’ and ten’s complement — used on early mechanical adding machines to do subtraction.
Why two’s complement wins
Two representations of zero, which wastes a bit pattern that could have extended the range:
- Signed magnitude:
00000000and10000000 - Ones’ complement:
00000000and11111111
Asymmetric range: two’s complement and excess-\(2^{n-1}\) (one more negative than positive).
Arithmetic: signed-magnitude addition requires taking cases; ones’ complement addition requires an extra addition step (the end-around carry); sign extension and comparison are non-trivial in both. Two’s complement has a single zero and its addition is just binary addition — no special cases.
Format matters
The same eight bits mean different things under different formats. 10010010 reads as:
| Read as | Value |
|---|---|
| Unsigned | 146 |
| Two’s complement | \(-110\) |
| Ones’ complement | \(-109\) |
| Signed magnitude | \(-18\) |
| Excess-128 | 18 |
Or 01010101: 85 unsigned, \(-43\) in excess-128, 'U' in ASCII, or 10.625 as fixed point with 5 bits before the binary point and 3 after.
The format is not encoded in the data. It has to be known separately — by a human, by a program, or by the hardware. See week1-lab-number-representations for the full 4-bit table across all five formats, and 2026-08-04-binary-arithmetic for what happens when you add these.
Fractions: fixed and floating point
Everything above is whole numbers. Place values carry on past a binary point as \(\tfrac12, \tfrac14, \tfrac18, \dots\), and there are two ways to use them.
- Fixed point: agree where the point sits, as in the 5.3 reading of
01010101above, and read the bits as before. Ordinary integer hardware does the arithmetic, but the format fixes the range and the precision once and for all. See fixed-point-numbers. - Floating point: store the digits and the position of the point separately, as binary scientific notation: a sign, a biased exponent and a mantissa. This is IEEE 754, the
floatanddoubleof C. See floating-point-numbers.
Boolean Algebra
Logic functions can be expressed as expressions of variables (literals, e.g. \(A, B, X\)) and functions (the operators \(+\), \(\cdot\), \(\oplus\), \(\bar{\ }\)) — i.e. an output written in terms of its inputs, \(X = f(A,B)\). Variables and functions can only take the values 0 or 1. Boolean algebra is the set of rules governing how such expressions can be manipulated.
Notation conventions
- Inversion: overline, e.g. \(\text{NOT}(A) = \bar A\) (pronounced “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}\).
\(+\) and \(\cdot\) are OR and AND, not arithmetic addition and multiplication — \(1 + 1 = 1\) here.
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\) |
Two rows in particular do the heavy lifting when simplifying: the inverse law (\(A\bar A = 0\), \(A + \bar A = 1\)) collapses whole terms to a constant, and the absorption law (\(A + AB = A\)) deletes a term outright.
The distributive law in its AND form is not the arithmetic one — \(A + BC = (A+B)(A+C)\) has no algebraic analogue and is easy to misremember.
De Morgan’s law and gate equivalents
De Morgan’s law says AND and OR can be interchanged if you invert both the inputs and the output. Drawn as gates, that gives four equivalences — every gate has a second symbol, and pushing an inversion through a gate always flips its shape:
Figure 24: De Morgan’s law drawn as gate symbols. (a) a NAND is an OR with inverted inputs; (b) a NOR is an AND with inverted inputs; (c) and (d) are the same two statements read the other way. Each pair is the same function, so either symbol may be used - pick whichever makes the surrounding bubbles cancel.
Exercise: verify each of the four with a truth table.
This is also why NAND-only and NOR-only circuits can implement any function (see logic-gates) — an AND feeding an OR can always be redrawn as a NAND feeding a NAND.
Simplifying an expression
Worked example:
\[\text{CODE} = C + CD + \overline{(D + \bar D)}\]
- Apply De Morgan’s law to the last term: \(\overline{D + \bar D} = \bar D \cdot \bar{\bar D} = \bar D \cdot D = 0\) (the double overline cancels, then the inverse law \(A\bar A = 0\) applies).
- The identity law \(0 + A = A\) drops that term: \(\text{CODE} = C + CD\).
- The absorption law \(A + AB = A\) finishes it: \(\text{CODE} = C\).
The whole expression is just \(C\) — neither \(D\) nor the \(CD\) term affects the output at all.
Sum of products
Any logic function can be implemented as the OR of AND combinations of its inputs (a sum of products):
- 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.
- OR all of those terms together.
Because every 1-row gets its own term, and each term is true for exactly that one row, the result is guaranteed to reproduce the table. Worked through in full, with the resulting circuit drawn out, in 2026-07-30-intro-to-logic-gates.
Sum of products always works, but does not necessarily give the minimum number of gates — the resulting expression can usually be simplified further with the identities above. E.g. \(Z = AB + AC = A(B+C)\) (distributive law) needs two gates rather than three.
Circuit Schematics
A logic diagram shows the idea of a circuit and is hardware-independent (see logic-gates). A circuit schematic goes further: it tells you how to actually build the circuit on real hardware — labelled ICs, pin numbers, power connections — so it’s hardware-specific. Schematics are drawn for practicals and assessment using 74-series logic chips and the CSSE2010/CSSE7201 IO Board (see device-pinouts for pin layouts). The rules are set out in the CSSE2010/CSSE7201 - Guide to Drawing Circuit Schematics (Blackboard, v2.3).
Required elements
Every circuit schematic must show:
- Labelled inputs and outputs — every input/output needs a sensible, unique name. Inputs and outputs use different symbols, and by convention inputs are drawn on the left, outputs on the right.
- Both symbols are the same right-pointing pentagon; what differs is which end the wire attaches to. An input has its wire leaving the point, so the signal flows out of the tip into the circuit. An output has its wire arriving at the flat back edge, with the point left free. Getting this backwards is one of the common errors below.
- Labelled devices — each physical device (chip or IO board) gets a unique identifier: one or more letters for the device type, then a sequential number starting from 1.
- Logic chips:
U1,U2,U3, … - IO board:
IO1(IO2for a second board, etc.) — when a group of inputs/outputs all belong to the same IO board, it only needs to be labelled once for the whole group, not per signal.
- Logic chips:
- Gate labels within a chip — where a chip contains multiple gates, each gate is labelled
A,B,C, … after the chip ID, separated by a colon (e.g.U1:A,U1:B). Labels can be assigned to gates in any order. A chip with only one gate/device doesn’t need a gate letter (justU3). - Device type — written on the line below the device ID (e.g.
74HCT00,74HCT04,IOBOARD). - Pin numbers — every pin used must be numbered per the actual device pinout (see device-pinouts).
- Power supply connections — shown once per device type, not per individual chip. Where two+ chip types share the same power pins, they can be grouped together. The IO board doesn’t need power connections shown.
Worked example
Figure 25: A correct schematic. Every rule above is visible here at once: five named inputs (A-E) and one named output (X0) on the IO board, four gates of one 74HCT00 labelled U1:A to U1:D, a fifth NAND that had to move to a second chip U2, an inverter on a third chip U3 because it is a different gate type, a pin number on every terminal, a junction dot where E splits to both inputs of U2:A, and one power-supply block covering both chip types.
Reading it against the rules:
- Naming: the inputs are
A,B,C,D,Eand the output isX0. The two IO-board groups are each labelledIO1/IOBOARDonce, not per signal. - Chip identifiers:
U1supplies four NAND gates (U1:A–U1:D). A fifth NAND is needed, so it comes from a second chip,U2:A. The inverter is a different gate type, so it needs a third chip,U3:A, of type 74HCT04. - Pin numbers: the 74HCT00’s four gates use inputs 1&2, 4&5, 9&10, 12&13 with outputs 3, 6, 8, 11 respectively — so those are the numbers written on
U1:A–U1:D.U3:Auses 1 → 2. - The junction dot:
E(pin 25) drives both inputs ofU2:A, which is what turns a NAND into an inverter. The dot at the split is what says the two wires are joined. - Power:
74HCT00and74HCT04have the same power pins, so they are braced together into one block: Vcc on pin 14, GND on pin 7. Nothing is shown per chip, and nothing at all for the IO board.
Common errors
Figure 26: The same circuit with seven deliberate mistakes ringed and numbered left to right, matching the list below. Compare each ring against the corresponding part of the correct schematic above.
- Duplicate names — two inputs given the same name (both called
A). Every input needs a unique name. - Missing junction dots — where wires join or split, a dot must mark the connection. Wires that merely cross on the page, with no dot, are not electrically connected. Here the split feeding both inputs of the NAND-as-inverter has no dot.
- Gate label exceeds chip capacity —
U1:Eon a 74HCT00, which only has four 2-input NAND gates (A–D). A fifth gate needs a new chip ID (U2:Aor similar). - Wrong device for the gate type —
U1:Fis a NOT gate, a different type from the rest ofU1, so it needs its own chip identifier (U3:A). (The figure also gives it as a74LS04while the rest of the schematic uses74HCTparts.) - Reusing pin numbers —
U1:Cis drawn with pins 1, 2 → 3, the same physical gate asU1:A. You can’t use one gate twice. - Inconsistent device type —
U1:Dis labelled74HCT47when the rest ofU1is a74HCT00. Every gate labelledU1:somethingmust show the same chip type. - Output errors — two distinct mistakes on
X0:- The input symbol is used (wire attached to the point) where the output symbol is needed (wire attached to the flat back) — see Figure 25.
- An input is wired to the output of a gate. An input should never be tied straight to a gate’s output; this may destroy the device. Gate outputs should only feed output devices (e.g. LEDs) or the inputs of other gates.
See also
- device-pinouts — the pin numbers and symbols every schematic has to match
- logic-gates — the gate symbols themselves, and the logic-diagram level above this one
- week3-lab-lab-4-pre-work — the preparation task that asks for schematics of a 2-to-1 mux, a 2-to-4 decoder and a 4-bit adder/subtractor
Compilation and Linking
How a C program turns into the machine code in the AVR’s flash. This note covers compiling against interpreting, where the compiler puts global, local and static variables, object files and their six sections, the linker’s two jobs (relocating and resolving), libraries, how header files differ from libraries, and static against dynamic linking. The assembler’s part, with its two passes and symbol table, is in assembly-process. First met in 2026-10-15-compilation-and-linking.
Compiled or interpreted
A processor runs machine code and nothing else. The fetch-decode-execute cycle (fetch-decode-execute-cycle) reads instruction words from memory, and nothing in it knows the program was once written in C. A program in a high-level language reaches the processor in one of two ways.
- Compilation translates the whole program into machine code before it runs, often by way of assembly language. The machine code then runs directly on the processor. C works this way.
- Interpretation never turns the program into machine code. Another program, the interpreter, reads the source and carries out each statement when it gets to it. The interpreter is itself machine code, and it is the interpreter that the processor runs. Python, Java and MATLAB work this way.
| Compiled | Interpreted | |
|---|---|---|
| What the processor runs | the program’s own machine code | the interpreter’s machine code |
| When translation happens | once, before the program runs | every time a statement is executed |
| Speed | fast | slow |
| Portability | the machine code suits one processor only | runs anywhere an interpreter exists |
Why interpreting is slow. Every time a statement is executed, the interpreter has to work out again what the statement means and then carry it out. That costs many of its own instructions per statement, and inside a loop it is repeated on every pass. A compiler does that work once, ahead of time.
Why it is portable. The program never becomes machine code, so nothing in it is tied to one instruction set. Moving it to a new processor only needs an interpreter built for that processor.
Bytecode and just-in-time compilation
Java and Python take a route in between. The source is first compiled, but not into machine code. It becomes bytecode, the instruction set of an imaginary machine. Bytecode is the same on every platform, so a compiled Java program is portable across all of them.
The bytecode is then run by a virtual machine, which is an interpreter for bytecode. The Java Virtual Machine is the one for Java. Running bytecode is faster than interpreting source text, because the parsing has already been done, but it is still interpretation.
To win back the speed, the virtual machine watches which parts of the program run most often and compiles them into real machine code while the program is running. This is just-in-time (JIT) compilation. Once a part has been JIT-compiled, it runs directly on the processor like compiled code. Standard Python interprets its bytecode, and a JIT compiler such as Numba can compile chosen Python functions to machine code in the same way.
The toolchain
Figure 27: How a three-file C program becomes a running program. Each source file goes through the first three steps by itself. The preprocessor pastes in headers and expands macros, the compiler turns C into assembly, and the assembler turns assembly into an object file, which is machine code plus the information needed to link it. Only the linker sees the whole program. It joins the object files to each other and to the library members they use, fixes up every address, and writes one executable. That executable is then loaded into memory, which on the AVR means programming it into flash. Changing one source file means repeating the first three steps for that file alone, then linking again.
| Step | Takes | Produces | Notes |
|---|---|---|---|
| Preprocess | a .c file |
C with every #include pasted in and every macro expanded |
c-preprocessor-and-avr-headers |
| Compile | that C | assembly language | maps variables to memory, and translates each statement into instructions |
| Assemble | the assembly | an object file, .o |
assembly-process |
| Link | all the object files, plus the library | one executable | relocates and resolves addresses |
| Load | the executable | the program in memory, ready to run | on the AVR, the executable is programmed into flash |
Some compilers write machine code directly and never produce assembly text. The object file that comes out is the same either way, so the three middle steps are often just called “compiling”. In the simplified view the compiler itself does two things, mapping variables to memory and translating C into assembler instructions. Turning those instructions into machine code is the assembler’s work.
With the AVR GCC toolchain the object files and the executable are ELF files. The .hex file that gets programmed into flash is extracted from the ELF executable.
How a compiler maps variables to memory
The compiler decides where each variable goes by how long it has to exist.
| Declared | Lives | Stored | Address |
|---|---|---|---|
| outside every function: a global | for the whole run | in the fixed data area, which starts at the bottom of SRAM | fixed before the program runs |
| inside a function: a local | only while that call is running | in the call’s stack frame | depends on how deep the stack is at the call |
inside a function, marked static |
for the whole run, and it keeps its value between calls | with the globals | fixed |
nowhere: obtained from malloc() |
until it is given back | on the heap | handed out while the program runs |
Globals. A global can be used at any moment from any function, so it needs one address that never changes. The compiler reserves as many bytes as the type needs (c-language-basics), one variable after another, from the start of SRAM. On the ATmega324A that is 0x0100 = 256, because addresses 0 to 255 are taken by the registers and the I/O registers (memory-models). It is the same thing an assembly programmer does with .dseg and .byte.
Locals. A local exists only while its function is running, and a recursive function can have several calls running at once, each needing its own copy. So the compiler cannot give it a fixed address. Instead, each call builds a stack frame, a block on the stack holding that call’s arguments, its return address and its local variables. The return takes the frame away again (procedures-and-the-stack). The same local therefore sits at different addresses on different calls.
static locals. static inside a function keeps the name private to the function but gives the variable a global’s lifetime. It is stored with the globals, at a fixed address, and is never part of a frame. That is why it still holds its value the next time the function is called.
static on a global means something else. The variable is stored exactly like any global, but its name is private to its own source file. It is left out of the object file’s entry point table (below), so no other file can link to it.
The heap and the stack grow toward each other. The heap starts above the globals and grows toward higher addresses. The stack starts at the top of SRAM (RAMEND) and grows down. The free memory between them shrinks from both ends, and if the two meet, that is a stack overflow. Nothing on the chip detects it. The first sign is usually a global or heap variable changing for no reason.
Figure 28: Where each kind of C variable ends up in the ATmega324A’s data memory, with the lowest address at the top. Globals and static variables are given fixed addresses from 0x0100, the first SRAM byte, so a static local such as c sits among the globals even though only its own function can name it. The heap, which malloc() hands out while the program runs, grows down the page toward the stack. The stack grows up the page from RAMEND. Each running call has a frame on it, and the frame of function() holds its locals a and b. When function() returns, that frame is gone. If the stack and the heap meet, the stack has overflowed.
Object files
A program of any size is split into several source files, and it pays to compile or assemble each one separately and then link them together. Change one file and only that file has to be compiled again. The others’ object files are reused as they are.
The price is that when a file is compiled, nobody knows where its code will end up. The file is translated as if it started at address 0. Every address inside it is relative to its own start, and any symbol defined in another file has no address at all yet. Once the linker has decided where everything goes, these addresses have to be fixed. A file that carries enough information for that fixing is a relocatable object module. “Object module” and “object file” mean the same thing.
So an object file is machine code plus information for the linker. There are many formats for it: a.out, COFF and ELF are object file formats, and DWARF is a format for debugging information, usually carried inside ELF files.
The six sections
Figure 29: The six sections of a relocatable object module, numbered from the bottom. Only section 4 is program: the machine instructions and constants, assembled as if the module began at address 0. The other five are information for the linker. They say what the module is called and where its parts are in the file (1), which of its symbols other modules may use (2), which symbols it uses but does not define (3), which addresses in section 4 have to be moved when the module is moved (5), and where execution starts (6). Linking reads 1, 2, 3, 5 and 6 to decide how to rewrite 4.
1. Identification. The name of the module, where each of the other sections is in the file, and the date it was assembled.
2. Entry point table. The symbols defined in this module that other modules may refer to, with their values. A value is an address: a procedure’s entry point, or a variable’s location. It is relative to the beginning of this object module. A file that defines a procedure abs_value at its address 10 has the entry abs_value 10. Anything not listed, such as a static global or a label used only inside the module, cannot be reached from another file.
3. External reference table. The symbols used in this module but not defined in it, both procedure names and variables, and for each one the list of instructions that use it. Those instructions are the places the linker will have to fill in once it knows the address.
One module’s entry point is another module’s external reference. If module A defines SUM and module B calls it, SUM appears in A’s entry point table and in B’s external reference table.
4. Machine instructions and constants. The assembled code and constants: the code segment, and the data segment holding the initialised and the uninitialised data. An initialised global such as int n = 5; needs its starting value stored in the file. An uninitialised one needs only its size. The addresses used in this code are not yet correct. They were worked out as if the module started at 0, so they need relocation.
5. Relocation dictionary. The list of addresses in section 4 that need to be relocated. When the module is placed, a relocation constant is added to the instruction or data at each of those addresses. There is one constant for code and a different one for data, because a module’s code goes in program memory and its data in data memory, and the two start in different places.
6. End of module. Possibly a checksum, to catch a corrupted file, and the address at which execution starts.
The linker
The linker combines object modules, the program’s own and any it needs from libraries, into a single executable binary program of machine code.
Its problem is the assembler’s problem again, one level up. That is the external reference problem: symbols are used before their values are known. Module A can call a procedure in module B before the linker has even read B. So the linker, like the assembler, works in two passes (assembly-process).
Pass 1: lay the program out.
- Read each module’s sizes and give it a place, in link order. Each module’s code starts where the previous module’s code ended, and the same goes for data. These starting addresses are the module’s two relocation constants.
- Read every entry point table. Add each symbol to one global symbol table, with its final address: its value relative to its module, plus that module’s starting address.
Pass 2: copy and patch.
- Copy each module’s section 4 to its place.
- Relocate. For each address in the module’s relocation dictionary, add the module’s constant, the code constant for a code address and the data constant for a data address.
- Resolve. For each external reference, look the symbol up in the global table and write its final address into every instruction listed against it. A symbol that no module defines cannot be resolved, so linking fails with an “undefined reference” error.
The two words to keep straight:
Relocating = adding a constant: fixing an address that points into the module’s own code or data, which moved when the module moved. Resolving = finding the value of an external address: filling in an address that points into another module.
Where a module starts follows from the order alone. A module’s code starts at the program start plus the code sizes of every module linked before it, and its data starts at the data start plus the data sizes of those same modules. Code and data are counted separately, in their own units: on the AVR, words of program memory and bytes of data memory (memory-models).
Worked: linking four modules
Four object modules, each assembled from address 0. Their lengths are A = 400, B = 600, C = 500, D = 300. Each holds a branch within itself, a data move, and (apart from D) a call to the next module.
| Module | At | Instruction |
|---|---|---|
| A | 0 | BRANCH TO 200 |
| A | 200 | MOVE P TO X |
| A | 300 | CALL B |
| B | 0 | BRANCH TO 300 |
| B | 300 | MOVE Q TO X |
| B | 500 | CALL C |
| C | 0 | BRANCH TO 200 |
| C | 200 | MOVE R TO X |
| C | 400 | CALL D |
| D | 0 | BRANCH TO 200 |
| D | 200 | MOVE S TO X |
They are linked in the order A, B, C, D. The first 100 addresses hold start-up code, the code that runs before main (on the AVR it sets the stack pointer and prepares the data), so A starts at 100.
Pass 1: place the modules. Each starts where the previous one ends.
| Module | Length | Starts at | Ends at | Relocation constant |
|---|---|---|---|---|
| A | 400 | 100 | 499 | +100 |
| B | 600 | 100 + 400 = 500 | 1099 | +500 |
| C | 500 | 500 + 600 = 1100 | 1599 | +1100 |
| D | 300 | 1100 + 500 = 1600 | 1899 | +1600 |
The global symbol table holds the module names as entry points: A = 100, B = 500, C = 1100, D = 1600. The program ends at 1899, and 1900 is the first free address.
Pass 2: patch each instruction. An instruction moves to its offset plus its module’s start. A branch inside a module is relocated: the target moves by the same constant as the instruction, so it still lands on the same MOVE. A call to another module is resolved from the symbol table.
| New address | Was | Becomes | Because |
|---|---|---|---|
| 100 | A: BRANCH TO 200 |
BRANCH TO 300 |
relocate: 200 + 100 |
| 300 | A: MOVE P TO X |
MOVE P TO X |
no code address in it |
| 400 | A: CALL B |
CALL 500 |
resolve: B starts at 500 |
| 500 | B: BRANCH TO 300 |
BRANCH TO 800 |
relocate: 300 + 500 |
| 800 | B: MOVE Q TO X |
MOVE Q TO X |
no code address in it |
| 1000 | B: CALL C |
CALL 1100 |
resolve: C starts at 1100 |
| 1100 | C: BRANCH TO 200 |
BRANCH TO 1300 |
relocate: 200 + 1100 |
| 1300 | C: MOVE R TO X |
MOVE R TO X |
no code address in it |
| 1500 | C: CALL D |
CALL 1600 |
resolve: D starts at 1600 |
| 1600 | D: BRANCH TO 200 |
BRANCH TO 1800 |
relocate: 200 + 1600 |
| 1800 | D: MOVE S TO X |
MOVE S TO X |
no code address in it |
B’s constant, 500, is the start-up code plus all of A: 100 + 400. Every branch ends up pointing at the instruction it pointed at before: A’s branch at 100 reaches A’s MOVE at 300, and B’s at 500 reaches B’s MOVE at 800. The MOVEs name data, P, Q, R, S and X. Those addresses are fixed in the same way with each module’s data constant, which this example leaves out so that only the code is followed.
Figure 30: Linking four object modules in the order A, B, C, D, with addresses increasing up the page and start-up code in 0 to 99. Left: after the first pass. Every module has its place, each starting where the one before it ends, but the instructions are still exactly as assembled. A’s branch at 100 still names 200, its target counted from A’s own 0, and 200 is now in the middle of A, not at its MOVE. Each call still names a module, not an address. Right: after the second pass. Each branch within a module has been relocated by its module’s starting address, so it lands on that module’s MOVE again, and each call to another module has been resolved to that module’s start. The bold operands are the ones the linker rewrote.
Worked: where each module starts
Three modules have these sizes. Code is measured in words, because AVR program memory holds 16-bit words, and data in bytes.
| Module | Code size (words) | Data size (bytes) |
|---|---|---|
| 1 | 45 | 17 |
| 2 | 67 | 5 |
| 3 | 100 | 25 |
They are linked in the order 2, 1, 3, starting at program address 62 and data address 256. Where does each module’s code and data start, and where do two sample references inside module 1 end up?
Lay them out in link order, keeping a running total for each memory:
| Module | Code | Data | Code constant | Data constant |
|---|---|---|---|---|
| 2 | 62 to 62 + 67 − 1 = 128 | 256 to 256 + 5 − 1 = 260 | +62 | +256 |
| 1 | 129 to 129 + 45 − 1 = 173 | 261 to 261 + 17 − 1 = 277 | +129 | +261 |
| 3 | 174 to 174 + 100 − 1 = 273 | 278 to 278 + 25 − 1 = 302 | +174 | +278 |
The next free code word is 274 and the next free data byte is 303. Both totals come out the same as for any other order, because the same three sizes are added up. Only where each module falls changes.
Relocate inside module 1. Suppose module 1 has, at its own word 20, a branch to its own word 40, and at its own word 30, a load from its own data byte 4.
- The branch moves to 20 + 129 = 149, and its target is relocated by the same code constant, 40 + 129 = 169.
- The load moves to 30 + 129 = 159, and its operand is a data address, relocated by the data constant: 4 + 261 = 265.
Adding the code constant to the data address would give 133, and the load would read the wrong byte. This is why the relocation dictionary has to say whether each entry is a code address or a data address.
Why 62 and 256? On the ATmega324A, program words 0 to 61 (0x0000 to 0x003D) are the interrupt vector table (avr-interrupts), so 0x003E = 62 is the first free word. Data addresses 0 to 255 are registers and I/O, so 0x0100 = 256 is the first byte of SRAM.
Libraries
A library is a collection of object files with an additional index. It provides useful functions and procedures that have already been written, tested and compiled. The rule is not to reinvent the wheel: use library code where it exists.
The index maps each symbol to the member object file that defines it. When an external reference is still unresolved, say a call to printf, the linker looks the name up in the index, takes that one member, and links it in like any other module. The rest of the library stays out of the program.
The standard C library is the one every C program can count on. It covers:
- standard input and output (
stdio.h:printf,getchar, …) - string handling (
string.h:strlen,strcpy, …) - date and time functions (
time.h) - general utilities (
stdlib.h:malloc,abs,atoi, …)
On the AVR it is provided by avr-libc, which also supplies the avr/io.h and avr/interrupt.h headers.
Header files are not the library
The two are easy to mix up, because #include <stdio.h> is what lets a program call printf.
A header file (.h)
- defines useful preprocessor macros,
- declares the functions that are in the library, as function prototypes, and
- declares variables that are available externally, with
extern.
The library is the collection of object files that implement those functions.
A declaration says what a name is and what type it has, so the compiler can check every use and generate the call. It contains no code, so the call still has nowhere to go. The header is therefore read by the compiler, and the library is read by the linker. Each kind of mistake shows up at its own step:
| Missing | When it shows | Typical message |
|---|---|---|
| the header | compiling | implicit declaration of function printf |
| the library, or the file that defines the function | linking | undefined reference to printf |
How a header gets pasted in is covered in c-preprocessor-and-avr-headers.
Static and dynamic linking
Everything so far is static linking. All the object code, the library’s and the main program’s, is joined into one binary before the program ever runs.
In dynamic linking, linking happens at run time instead: a library procedure is linked when it is first called. The executable holds only a reference to it, and the library stays in a separate file that is loaded when the program needs it. DLLs (dynamic-link libraries) on Windows work this way, and so do shared libraries (.so files) on Linux.
| Static | Dynamic | |
|---|---|---|
| Library code is joined in | when the program is linked | when the procedure is first called |
| Library code is stored | inside every executable that uses it | once, in its own file, shared |
| Executable size | larger | smaller |
| Updating the library | means relinking each program | takes effect in every program at once |
Its advantages:
- It saves space. Libraries are not linked into the executable, so ten programs that use the same library share one copy of it.
- The library can be updated independently of the programs that use it. A bug fixed in the DLL is fixed in all of them, without relinking anything.
The second advantage is also its weakness. A program tested with one version of a library can break when another installation replaces that library with a version that behaves differently. On earlier versions of Windows this was common enough to be called “DLL hell”.
Figure 31: The same two programs, both calling printf, linked statically and dynamically. Static linking copies printf’s object code into each executable when it is linked, so each program carries its own copy and is complete in itself. Dynamic linking leaves a reference in each executable and keeps a single copy of printf in a shared library file. The reference is linked to that copy at run time, when printf is first called. That saves space, and updating the shared file changes the printf both programs get, for better or worse.
The ATmega324A has no operating system to load a library at run time, so every AVR program is linked statically. Everything it will ever call is already in flash.
Common mistakes
- Treating the header as the library.
#include <math.h>makessqrtcompile. It does not supplysqrt. Without the library the link fails with an undefined reference. - Counting from the wrong module. A module’s start depends on the modules linked before it in link order, not on its number. In the order 3, 2, 1, module 2 starts after module 3.
- Mixing code and data sizes. The code start adds up code sizes only, and the data start adds up data sizes only. On the AVR they are not even in the same unit: words against bytes.
- Off by one at a boundary. A module of size \(n\) starting at \(s\) occupies \(s\) to \(s + n - 1\), and the next module starts at \(s + n\).
- Relocating an external reference. A call into another module is not fixed by adding this module’s constant. Its address comes from the symbol table, which holds the other module’s start plus the symbol’s offset in it.
- Relocating a data address with the code constant, or the other way round.
- Expecting a local variable to keep its value between calls. The frame is gone when the function returns. Use
staticif the value must persist. - Returning a pointer to a local. The address points into a frame that no longer exists, and the next call will overwrite it.
- Thinking “interpreted” means “never compiled”. Java is compiled, to bytecode, and a JIT compiles parts of it again to machine code. What makes it interpreted is that the virtual machine, and not the processor, runs the bytecode.
See also
- assembly-process — the assembler’s two passes and symbol table, the same problem one level down
- c-preprocessor-and-avr-headers —
#include, macros, and the header against the library - procedures-and-the-stack — stack frames,
callandret, and where locals live - c-language-basics — declarations and how much memory each type takes
- memory-models · avr-architecture — the AVR’s word-addressed program memory and byte-addressed data memory
- avr-interrupts — the vector table that the program code follows
- instruction-set-architecture · 2026-09-07-introduction-to-embedded-c-programming — compiling one-to-many against assembling one-to-one
- fetch-decode-execute-cycle — what “runs on the processor” means
- 2026-10-15-compilation-and-linking — Lecture 22
Sample Mid-semester Exam #1
This is the first of UQ’s sample mid-semester papers for csse2010 — CSSE2010/CSSE7201 Introduction to Computer Systems — printed for the Semester One Mid-semester Examinations, 2020, St Lucia campus. It runs for 60 minutes with 10 minutes of reading time beforehand, and it is an open book examination: no electronic aids (laptops, phones), but a Casio FX82-series or other UQ-approved calculator is allowed. Answers go on a supplied “True/False and Multiple Choice Answer Sheet”. There are 25 questions, each worth one mark, and the marking is blunt — a correct answer earns one mark, and an incorrect, missing or multiple answer earns zero, so there is no penalty for guessing.
WarningAnswers are derived, not official
The source paper ships without an answer key, so every answer below was worked out during transcription rather than taken from UQ. Each one shows its reasoning so it can be checked rather than trusted; anything uncertain is flagged. Treat a disagreement between your working and the answer here as a reason to check both.
How to use this
Two ways. For a timed run, set a clock for 60 minutes and work straight through all 25 questions — on the website the answers are collapsed, so they stay hidden until you click them, and the paper reads like the real thing. For targeted practice, use the question index below to pick out only the questions for one week or one concept, and follow the concept links when a step in the working is unfamiliar. Note that the PDF build prints every answer inline, so the site version is the one to practise from.
Question index
| Q | Topic | Week | Concept notes |
|---|---|---|---|
| 1 | One’s complement | 1 | binary-number-representations |
| 2 | Octal conversion | 1 | binary-number-representations |
| 3 | Range of a radix-r number | 1 | binary-number-representations |
| 4 | Properties across signed formats | 1 | binary-number-representations |
| 5 | Reading a gate-level circuit | 1 | logic-gates |
| 6 | Gate equivalence and De Morgan | 1 | logic-gates · boolean-algebra |
| 7 | Boolean simplification | 2 | boolean-algebra |
| 8 | Truth table to sum of products | 2 | boolean-algebra |
| 9 | Timing diagram to logic function | 2 | timing-diagrams |
| 10 | XOR identities | 2 | boolean-algebra |
| 11 | NOR-only implementation | 2 | boolean-algebra · logic-gates |
| 12 | NOR latch behaviour | 3 | flip-flops-and-latches |
| 13 | D flip-flop timing | 3 | flip-flops-and-latches · timing-diagrams |
| 14 | Two’s complement addition | 2 | binary-number-representations |
| 15 | Detecting overflow | 2 | binary-number-representations |
| 16 | Overflow on a positive sum | 2 | binary-number-representations |
| 17 | Programming a multiplexer | 2 | combinational-logic-blocks |
| 18 | Shift register with hold | 3 | shift-registers |
| 19 | Counter width | 4 | counters |
| 20 | Synchronous counter sequence | 4 | counters |
| 21 | State diagram to state table | 4 | state-machines |
| 22 | Tracing a state machine | 4 | state-machines |
| 23 | Tanenbaum ALU bit slice | 5 | arithmetic-logic-unit |
| 24 | ALU bit slice with an 8-way mux | 5 | arithmetic-logic-unit |
| 25 | What an ALU cannot compute | 5 | arithmetic-logic-unit |
Q1 — One’s complement of a negative
What is \(-21_{10}\) expressed in 8-bit one’s complement format?
10010101
11101010
11101011
11110010
None of the above
TipAnswer
(b)
One’s complement negates by inverting every bit of the magnitude, so start from \(+21\) in 8 bits:
\[21 = 16 + 4 + 1 = 0001\,0101_2\]
Inverting all eight bits gives
\[\overline{0001\,0101} = 1110\,1010_2\]
which is option (b). Option (c), 11101011, is the two’s complement of \(-21\) (one’s complement plus one) — the classic distractor here. See binary-number-representations.
Q2 — Octal conversion
\(111_8\) is equal to
\(1001001_2\)
\(71_{10}\)
0x73
\(7_{10}\)
None of the above
TipAnswer
(a)
Each octal digit is exactly three bits, so the conversion to binary is done digit by digit with no arithmetic at all:
\[1_8 \to 001, \quad 1_8 \to 001, \quad 1_8 \to 001 \;\Rightarrow\; 111_8 = 001\,001\,001_2 = 1001001_2\]
That is option (a). Checking the others against the decimal value \(1 \times 64 + 1 \times 8 + 1 = 73_{10}\): (b) is 71, not 73; (d) is 7; and (c) is the trap — 0x73 is hexadecimal 73, which is \(7 \times 16 + 3 = 115_{10}\), not the decimal 73 the value happens to equal. See binary-number-representations.
Q3 — Range of a radix-r number
An n-digit radix-r number can represent unsigned integer values from 0 up to
\(2^{(n-1)}\)
\(2^n\) - 1
\(r^{(n-1)}\) - 1
\(r^n\) - 1
None of the above
TipAnswer
(d)
With \(n\) digits and \(r\) choices per digit there are \(r^n\) distinct patterns. Counting from zero, the largest value is one less than the count:
\[0 \le \text{value} \le r^n - 1\]
Two other routes to the same answer:
- The smallest value you cannot represent is a one followed by \(n\) zeroes, which is worth \(r^n\). The largest you can represent is one below it.
- The largest value is \(n\) copies of the largest digit, \(r-1\) — 9999 in base 10, FF in hex — and summing that as a geometric series gives \(\sum_{i=0}^{n-1} r^i (r-1) = r^n - 1\).
Option (b) is the same formula specialised to \(r = 2\), which is only correct for binary, and the question asks for general radix \(r\). See binary-number-representations and week1-lab-number-representations.
Q4 — Properties across signed formats
Which of the following statements about the 8 bit binary number 01100101 is true?
The number is negative in signed magnitude, two’s complement, one’s complement and excess-128 formats.
The number is positive in signed magnitude, two’s complement, one’s complement and excess-128 formats.
The number is odd when considered to be in signed magnitude, two’s complement, one’s complement or excess-128 formats.
The number is even when considered to be in signed magnitude, two’s complement, one’s complement or excess-128 formats.
None of the above
TipAnswer
(c)
Read the pattern once in each format. \(0110\,0101_2 = 101_{10}\) as a plain unsigned number, and only the leading bit is read differently from one format to the next.
Figure 32: One bit pattern, four readings. Bits 6 down to 0 carry the same place values in every format, so the only question is what the leading bit is worth: nothing at all in signed magnitude, and a plain 0 in the two complement formats because it is clear. Excess-128 is the outlier - it reads the eight bits as plain unsigned and then takes the bias off the whole value, which is why the same pattern comes out negative there.
That immediately kills (a) and (b): the first three formats all read it as positive, but excess-128 reads it as \(-27\), so it is neither negative in all four nor positive in all four.
Parity is the property that does survive all four. In the three sign-magnitude-style formats the value is \(\pm 101\), which is odd; in excess-128 it is \(-27\), also odd. So (c) is true and (d) is false. See binary-number-representations.
Q5 — Reading a gate-level circuit
Which of the following logic circuits is an implementation of the function \(A \cdot (B \oplus C) \cdot D\)?
Figure 33: Question 5’s five candidate circuits. (a) is a three-input AND fed by A, an XNOR of B and C, and D; (b)–(e) each combine two two-input gates into a third.
- None of the above
TipAnswer
(d)
Read each circuit out as an expression:
| Option | Circuit | Function |
|---|---|---|
| (a) | 3-input AND of A, XNOR(B,C) and D | \(A \cdot \overline{(B \oplus C)} \cdot D\) |
| (b) | AND(A,D) and XOR(B,C) into an OR | \(A \cdot D + (B \oplus C)\) |
| (c) | AND(A,D) and OR(B,C) into an AND | \(A \cdot D \cdot (B + C)\) |
| (d) | AND(A,D) and XOR(B,C) into an AND | \(A \cdot D \cdot (B \oplus C)\) |
| (e) | AND(A,B) and AND(C,D) into an XOR | \((A \cdot B) \oplus (C \cdot D)\) |
AND is associative and commutative, so (d)’s \(A \cdot D \cdot (B \oplus C)\) is the same function as the target \(A \cdot (B \oplus C) \cdot D\).
The two near misses are worth naming. (a) has the right shape but the middle gate carries an output bubble, making it XNOR rather than XOR — the exact complement of what is wanted. (b) has both correct sub-gates but joins them with OR instead of AND. See logic-gates.
Q6 — Gate equivalence and De Morgan
Which of the following circuits is equivalent to:
Figure 34: Question 6’s given circuit (top) and its four candidate equivalents. The given circuit is an AND gate with its A input inverted; each candidate is a single two-input gate with bubbles on some of its terminals.
- None of the above
TipAnswer
(b)
The given circuit is an AND with a bubble on its A input, so it computes
\[F = \overline{A} \cdot B\]
Push that through De Morgan’s law to get an OR-shaped form:
\[\overline{A} \cdot B = \overline{\overline{\overline{A} \cdot B}} = \overline{A + \overline{B}}\]
That is a gate with a bubble on the B input and a bubble on the output — an OR body with both, which is exactly option (b).
Checking the rest: (a) is the same gate without the output bubble, so \(A + \overline{B}\); (d) is an OR with the A input inverted, \(\overline{A} + B\); and (c) is an XNOR with A inverted, \(\overline{\overline{A} \oplus B} = A \oplus B\). None of those equals \(\overline{A} \cdot B\). See boolean-algebra and logic-gates.
Q7 — Boolean simplification
Which of the following logic functions is identical to \(\overline{\overline{(\overline{A} + \overline{B})} \cdot \overline{C} + \overline{B}}\)?
0
\(AC + \overline{B}\)
\(AB + \overline{B}C\)
\(\overline{A}B + BC\)
None of the above
TipAnswer
(d)
Work outwards from the innermost bar. The inner complement is a straight De Morgan:
\[\overline{\overline{A} + \overline{B}} = A \cdot B\]
so the expression under the long outer bar is \(A B \overline{C} + \overline{B}\). That simplifies by the absorption identity \(X \cdot Y + \overline{X} = Y + \overline{X}\), taking \(X = B\) and \(Y = A\overline{C}\):
\[B \cdot (A\overline{C}) + \overline{B} = A\overline{C} + \overline{B}\]
Now apply the outer bar:
\[\overline{A\overline{C} + \overline{B}} = \overline{A\overline{C}} \cdot B = (\overline{A} + C) \cdot B = \overline{A}B + BC\]
which is option (d).
Checking a couple of rows against the original settles it. With \(A=0, B=1, C=0\) the inside is \(0 \cdot 1 \cdot 1 + 0 = 0\), so the whole expression is 1, and (d) gives \(\overline{A}B = 1\). With \(A=1, B=1, C=0\) the inside is \(1 \cdot 1 \cdot 1 + 0 = 1\), so the expression is 0, and (d) gives \(0 + 0 = 0\). See boolean-algebra.
Q8 — Truth table to sum of products
Consider the logic function represented by the following truth table:
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
Which of the following expressions is equivalent to the function represented in this table?
\(X = A + B + C\)
\(X = A\overline{B}.\overline{C} + \overline{A}.\overline{B}.C + \overline{A}.B.\overline{C}\)
\(X = \overline{A}.B.\overline{C} + \overline{A}.B.C + \overline{A}.\overline{B}.\overline{C}\)
\(X = \overline{A.B.C}\)
None of the above
TipAnswer
(e)
The table has \(X = 1\) on exactly three rows: \(ABC = 000\), \(100\) and \(101\). Writing one product term per row,
\[X = \overline{A}\,\overline{B}\,\overline{C} + A\,\overline{B}\,\overline{C} + A\,\overline{B}\,C = \overline{B}\,\overline{C} + A\overline{B} = \overline{B}(\overline{C} + A)\]
Now check each option against those three minterms:
| Option | Minterms it covers (\(ABC\)) | Matches? |
|---|---|---|
| (a) \(A+B+C\) | everything except 000 | no — it is 0 exactly where the table is 1 |
| (b) \(A\overline{B}\overline{C} + \overline{A}\overline{B}C + \overline{A}B\overline{C}\) | 100, 001, 010 | no — 001 and 010 are 0 in the table |
| (c) \(\overline{A}B\overline{C} + \overline{A}BC + \overline{A}\,\overline{B}\,\overline{C}\) | 010, 011, 000 | no |
| (d) \(\overline{A \cdot B \cdot C}\) | everything except 111 | no — it is 1 on 001, which the table makes 0 |
None reproduces \(\{000, 100, 101\}\), so the answer is (e).
Option (b) is the closest — it shares the minterm 100 with the correct function and has the right number of terms — which is presumably the intended trap. See boolean-algebra.
Confirmed on review. “None of the above” is an unusual answer for a routine sum-of-products question, and it would also follow from a single mis-set bar in the source’s option (b). A second independent pass measured the bar positions in option (b) against the glyph positions at 1800 dpi: the bars sit over the first term’s B and C, the second term’s A and B, and the third term’s A and C, exactly as transcribed. Option (b) shares only the minterm 100 with the function, so it is two terms out, not one bar out, and (e) stands.
Q9 — Timing diagram to logic function
What logic function is represented by the following timing diagram?
Figure 35: Question 9’s timing diagram. A, B and C step through all eight combinations — A toggling every interval, B every two, C every four — and X is the output to be identified.
\(X = \overline{C}.\overline{B}.A + \overline{C}.B.A + C.B.\overline{A}\)
\(X = \overline{C}.\overline{B}.\overline{A} + C.B.\overline{A} + \overline{C}.B.\overline{A}\)
\(X = C.\overline{B}.A + C.\overline{B} + C.\overline{A}\)
\(X = \overline{C}.\overline{B}.A + C.\overline{B}.\overline{A} + C.B.\overline{A}\)
None of the above
TipAnswer
(d)
A toggles every interval, B every two and C every four, so the eight intervals walk \(CBA\) through \(000, 001, 010, \ldots, 111\) in order. Read X off interval by interval:
| Interval | C | B | A | X |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 |
| 3 | 0 | 1 | 0 | 0 |
| 4 | 0 | 1 | 1 | 0 |
| 5 | 1 | 0 | 0 | 1 |
| 6 | 1 | 0 | 1 | 0 |
| 7 | 1 | 1 | 0 | 1 |
| 8 | 1 | 1 | 1 | 0 |
One product term per high interval:
\[X = \overline{C}\,\overline{B}\,A + C\,\overline{B}\,\overline{A} + C\,B\,\overline{A}\]
which is option (d) exactly, term for term. See timing-diagrams.
Q10 — XOR identities
Which of the following logic functions is identical to \(A \oplus \overline{B}\)?
\(A.\overline{B} + \overline{A}.B\)
\(\overline{A}.\overline{B} + \overline{A}.B + A.B\)
\(A + \overline{B}\)
\(\overline{A \oplus B}\)
None of the above
TipAnswer
(d)
Inverting one input of an XOR inverts its output — this is the standard identity \(A \oplus \overline{B} = \overline{A \oplus B}\), which is option (d) as written.
To see it rather than quote it, expand:
\[A \oplus \overline{B} = A\,\overline{\overline{B}} + \overline{A}\,\overline{B} = A B + \overline{A}\,\overline{B}\]
That is 1 exactly when A and B agree, which is the definition of XNOR, i.e. \(\overline{A \oplus B}\).
The others: (a) is plain \(A \oplus B\), the complement of what is wanted; (b) simplifies as \(\overline{A}(\overline{B} + B) + AB = \overline{A} + AB = \overline{A} + B\), which fails at \(A=0, B=1\) (it gives 1, the target gives 0); (c) \(A + \overline{B}\) fails at \(A=1, B=0\) (it gives 1, the target gives 0). See boolean-algebra.
Q11 — NOR-only implementation
Which of the following circuits is a NOR-gate only implementation of the following function:
Figure 36: Question 11’s given function A.B + C.D (top) and its four candidate implementations. In (c) and (d) the NOR gates with both inputs tied together are acting as inverters; (d) has one more of them than (c).
- None of the above
TipAnswer
(d)
The function to reproduce is \(F = A \cdot B + C \cdot D\).
A NOR gate with both inputs tied together is an inverter, since \(\overline{X + X} = \overline{X}\) — that is what the small gates on the left of (c) and (d) are. With inverters available, a NOR fed by two complemented inputs is an AND:
\[\overline{\overline{A} + \overline{B}} = A \cdot B\]
So in both (c) and (d) the two middle NORs produce \(A \cdot B\) and \(C \cdot D\), and the NOR that joins them produces
\[\overline{A B + C D} = \overline{F}\]
which is the complement of what is wanted. (c) stops there and is therefore wrong. (d) adds one more tied-input NOR on the output, inverting once more to give \(F\) itself — so (d) is the NOR-only implementation.
The other two: (a) is a correct implementation of \(A B + C D\), but built from NAND gates, not NOR; (b) is three NOR gates in the same shape as the given circuit, which computes \(\overline{\overline{A+B} + \overline{C+D}} = (A+B)(C+D)\), a different function. See boolean-algebra and logic-gates.
Q12 — NOR latch behaviour
Which truth table correctly captures the behaviour of the following latch circuit?
Figure 37: Question 12’s latch: two cross-coupled NOR gates. M is the external input to the gate that drives Q, N the input to the gate that drives Q-bar, and each gate’s output feeds back to the other gate’s second input.
| M | N | Q | \(\overline{Q}\) |
|---|---|---|---|
| 0 | 0 | Q | \(\overline{Q}\) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| M | N | Q | \(\overline{Q}\) |
|---|---|---|---|
| 0 | 0 | Q | \(\overline{Q}\) |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| M | N | Q | \(\overline{Q}\) |
|---|---|---|---|
| 0 | 0 | Q | \(\overline{Q}\) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 |
| M | N | Q | \(\overline{Q}\) |
|---|---|---|---|
| 0 | 0 | Q | \(\overline{Q}\) |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 |
- None of the above
TipAnswer
(d)
This is the standard cross-coupled NOR latch, so M behaves as the reset input and N as the set input — note which output each drives: M feeds the gate whose output is Q, so asserting M forces Q low.
Writing the two gate equations,
\[Q = \overline{M + \overline{Q}} \qquad \overline{Q} = \overline{N + Q}\]
and working through the four input combinations:
| M | N | Working | Q | \(\overline{Q}\) |
|---|---|---|---|---|
| 0 | 0 | both NORs just invert their feedback, so the state holds | Q | \(\overline{Q}\) |
| 0 | 1 | N = 1 forces the lower NOR’s output to 0, so \(\overline{Q} = 0\); the upper NOR then sees \(0 + 0\) and outputs 1 | 1 | 0 |
| 1 | 0 | M = 1 forces the upper NOR’s output to 0, so \(Q = 0\); the lower NOR sees \(0 + 0\) and outputs 1 | 0 | 1 |
| 1 | 1 | a 1 on either NOR forces its output low, so both outputs go to 0 | 0 | 0 |
That is option (d). The distinguishing rows are the middle two — (a) and (c) have them the wrong way round, treating M as set rather than reset — and the last row, where (b) and (c) claim both outputs go to 1 rather than 0. In a NOR latch the forbidden combination drives both outputs low; it is the NAND latch that drives them both high. See flip-flops-and-latches.
Q13 — D flip-flop timing
For the flip-flop circuit below and the given CLK and A values over time, which of the diagrams below best shows the Q output?
Figure 38: Question 13’s positive-edge-triggered D flip-flop, the CLK and A waveforms driving it, and the four candidate Q outputs (a) to (d).
- None of the above
TipAnswer
(b)
The clock input is drawn with a plain triangle and no bubble, so the flip-flop is positive-edge-triggered: Q takes the value of A at each rising edge of CLK and holds it until the next one.
There are four rising edges. Reading A at each:
| Rising edge | A at that instant | Q after |
|---|---|---|
| 1st | 0 — A does not go high until just after this edge | 0 |
| 2nd | 0 — A has already fallen | 0 |
| 3rd | 1 — A goes high just before this edge | 1 |
| 4th | 1 — A is still high | 1 |
So Q sits at 0 through the first two edges, rises at the third and stays high. That is exactly diagram (b), whose transition lands on the third rising edge.
The distractors are instructive. (c) is A itself, which is what a transparent latch would give rather than an edge-triggered flip-flop. (a) is what a negative-edge-triggered flip-flop would give: sampling on the falling edges catches A high at the first and third of them. (d) rises one clock too late, at the fourth edge. See flip-flops-and-latches and timing-diagrams.
Q14 — Two’s complement addition
What’s the result of adding the 5-bit two’s complement numbers 11101 and 01001?
00110
00111
01100
10110
10111
TipAnswer
(a)
Add the bit patterns as if they were unsigned and discard anything past bit 4 — that is the whole point of two’s complement:
\[\begin{array}{r} 11101 \\ +\;01001 \\ \hline 1\,00110 \end{array}\]
Dropping the carry out of the top bit leaves 00110, which is option (a).
The decimal check: 11101 has its sign bit set, so its magnitude is \(\overline{11101} + 1 = 00010 + 1 = 00011 = 3\), i.e. it is \(-3\). 01001 is \(+9\). And \(-3 + 9 = 6 = 00110_2\). The signs differ, so overflow is impossible here and the discarded carry is harmless. See binary-number-representations.
Q15 — Detecting overflow
Which of the following operations will result in an overflow in 5-bit two’s complement arithmetic?
10010+00010
10010–00010
01000+01010
01000–01010
None of the above
TipAnswer
(c)
A 5-bit two’s complement word covers \(-16\) to \(+15\). Overflow means the true result falls outside that range, which can only happen when two operands of the same sign are added (or operands of opposite sign are subtracted).
| Option | Decimal | Result | In range \([-16, 15]\)? |
|---|---|---|---|
| (a) | \(-14 + 2\) | \(-12\) | yes — and adding a positive to a negative can never overflow |
| (b) | \(-14 - 2\) | \(-16\) | yes — \(-16\) is exactly the most negative representable value |
| (c) | \(8 + 10\) | \(18\) | no — 18 > 15, so this overflows |
| (d) | \(8 - 10\) | \(-2\) | yes |
Option (b) is the near miss worth checking carefully: \(-16\) sits right on the boundary and is representable, as 10000. Only (c) leaves the range. See binary-number-representations.
Q16 — Overflow on a positive sum
Consider the binary addition operation 0111 + 0001. Which of the following statements is true if the numbers are interpreted as two’s complement?
The result is negative and no overflow occurs
The result should be negative but overflow occurs
The result is positive and no overflow occurs
The result should be positive but overflow occurs
The result is zero
TipAnswer
(d)
These are 4-bit two’s complement numbers, so the range is \(-8\) to \(+7\).
\[0111_2 = +7, \qquad 0001_2 = +1\]
The bit-level sum is
\[\begin{array}{r} 0111 \\ +\;0001 \\ \hline 1000 \end{array}\]
and 1000 read as 4-bit two’s complement is \(-8\). The true answer \(+8\) is one past the top of the range, so it cannot be represented: the addition of two positives has produced a negative pattern, which is the textbook overflow signature. The result should be positive but overflow has occurred — option (d).
Note that no carry leaves the top bit here, which is why “carry out” alone is not an overflow test in signed arithmetic; the test is the sign pattern of the operands versus the result. See binary-number-representations.
Q17 — Programming a multiplexer
Consider the following multiplexer. What must the inputs A,B,C,D be so that the multiplexer implements the function \(X = S_1 \oplus S_0\)?
Figure 39: Question 17’s 4-to-1 multiplexer. A, B, C and D are wired to data inputs 0 to 3; S1 and S0 are the select lines, and X is the output.
A=1, B=1, C=1, D=1
A=1, B=0, C=0, D=1
A=0, B=1, C=1, D=0
A=1, B=1, C=0, D=0
None of the above
TipAnswer
(c)
A multiplexer used this way is a lookup table: the select lines index a data input, and that input’s constant value becomes the output. So each data input holds one row of the truth table of the function being built, with \(S_1\) as the high-order select bit.
| \(S_1\) | \(S_0\) | Input selected | \(S_1 \oplus S_0\) | So that input must be |
|---|---|---|---|---|
| 0 | 0 | 0 (A) | 0 | A = 0 |
| 0 | 1 | 1 (B) | 1 | B = 1 |
| 1 | 0 | 2 (C) | 1 | C = 1 |
| 1 | 1 | 3 (D) | 0 | D = 0 |
That is \(A=0, B=1, C=1, D=0\) — option (c). Swapping which select line is the high bit changes nothing here, because XOR is symmetric in its two inputs, so (c) is the answer either way. The distractors are different functions: (d) is 1 on the two inputs reached when \(S_1 = 0\) and 0 on the other two, i.e. \(\overline{S_1}\) — what you get by reading only the high select bit — and (b) is the XNOR, the complement of the target. See combinational-logic-blocks.
Q18 — Shift register with hold
Which of the following statements about this shift register circuit is true?
Figure 40: Question 18’s two-stage shift register. Each stage is a 2-to-1 multiplexer feeding a D flip-flop: input 1 of each multiplexer takes the data from the left, input 0 takes that stage’s own Q back again, and FN drives both selects.
When A is 1, data will be shifted to the right on every rising clock edge
When A is 0, data will be shifted to the right on every rising clock edge
When FN is 1, data will be shifted to the left on every rising clock edge
When FN is 0, the flip-flops will maintain their values (even if the circuit is clocked)
None of the above
TipAnswer
(d)
Trace what each multiplexer feeds its flip-flop:
- Input 1 of the first multiplexer is A, and input 1 of the second is the first stage’s Q. So with the selects at 1, the chain is \(A \to \text{FF}_1 \to \text{FF}_2\) — data moves one stage to the right per clock.
- Input 0 of each multiplexer is that stage’s own Q, looped back over the top. So with the selects at 0, each flip-flop is reloaded with the value it already holds, and nothing changes even though the clock keeps running.
Both selects are driven by FN, so FN chooses shift (1) or hold (0), and A is data, not control. That makes (d) true: with FN = 0 the flip-flops maintain their values through any number of clock edges.
The others fail because A is a data input, not a mode control — (a) and (b) confuse the two — and because the connection order runs left to right, so FN = 1 shifts right, not left, killing (c).
This “recirculating” pattern is the standard way to add a hold or enable to a register without gating the clock, which would risk glitches. See shift-registers.
Q19 — Counter width
What’s the minimum number of flip-flops needed to build a synchronous binary counter capable of counting from 0 to 32 (inclusive)?
5
6
7
32
33
TipAnswer
(b)
“0 to 32 inclusive” is 33 distinct values, not 32 — that off-by-one is the whole question. Each flip-flop holds one bit, and \(n\) flip-flops give \(2^n\) states, so we need the smallest \(n\) with
\[2^n \ge 33\]
\(2^5 = 32\), which is one short; \(2^6 = 64\), which is enough. So six flip-flops — option (b).
Option (a) is the answer to “0 to 31”, which is the trap. See counters.
Q20 — Synchronous counter sequence
What sequence will the following synchronous counter count through?
Figure 41: Question 20’s two-bit synchronous counter. The left flip-flop’s D input comes from its own Q-bar, so Q1 toggles every clock; the right flip-flop’s D input is the XNOR of Q1 and Q0. Both flip-flops share the clock.
\(Q_1Q_0\): \(00 \to 01 \to 10 \to 11 \to 00 \to \ldots\)
\(Q_1Q_0\): \(00 \to 10 \to 11 \to 01 \to 00 \to \ldots\)
\(Q_1Q_0\): \(00 \to 11 \to 01 \to 10 \to 00 \to \ldots\)
\(Q_1Q_0\): \(00 \to 01 \to 11 \to 10 \to 00 \to \ldots\)
None of the above
TipAnswer
(c)
Read the two excitation equations off the schematic. The left flip-flop’s D input is wired straight back to its own \(\overline{Q}\), and the right flip-flop’s D input is the XNOR of the two Q outputs:
\[D_1 = \overline{Q_1} \qquad D_0 = \overline{Q_1 \oplus Q_0}\]
Both flip-flops share the clock, so both update together from the current state. Starting at 00:
| \(Q_1 Q_0\) | \(D_1 = \overline{Q_1}\) | \(D_0 = \overline{Q_1 \oplus Q_0}\) | Next |
|---|---|---|---|
| 0 0 | 1 | \(\overline{0 \oplus 0} = 1\) | 1 1 |
| 1 1 | 0 | \(\overline{1 \oplus 1} = 1\) | 0 1 |
| 0 1 | 1 | \(\overline{0 \oplus 1} = 0\) | 1 0 |
| 1 0 | 0 | \(\overline{1 \oplus 0} = 0\) | 0 0 |
So the sequence is \(00 \to 11 \to 01 \to 10 \to 00\), option (c). All four states appear, so the counter is a valid four-state cycle — just not in binary order.
The gate identity is what to watch here: the bubble on the gate’s output makes it an XNOR, and an XOR there would have produced a different sequence entirely. See counters.
Q21 — State diagram to state table
Consider the state diagram below.
Figure 42: Question 21’s state diagram. Each state shows its name above the rule and its XY output below; the labels on the arrows are the values of the single input A.
Which of the following is an equivalent state table?
| Current State | Input (A) | Next State | Outputs (X,Y) |
|---|---|---|---|
| S0 | 0 | S0 | 01 |
| S0 | 1 | S1 | 01 |
| S1 | 0 | S1 | 00 |
| S1 | 1 | S2 | 00 |
| S2 | 0 | S2 | 00 |
| S2 | 1 | S3 | 00 |
| S3 | 0 | S0 | 11 |
| S3 | 1 | S1 | 11 |
| Current State | Input (A) | Next State | Outputs (X,Y) |
|---|---|---|---|
| S0 | 0 | S0 | 01 |
| S0 | 1 | S1 | 01 |
| S1 | 0 | S2 | 00 |
| S1 | 1 | S1 | 00 |
| S2 | 0 | S2 | 00 |
| S2 | 1 | S3 | 00 |
| S3 | 0 | S0 | 11 |
| S3 | 1 | S2 | 11 |
| Current State | Next State (A=0) | Next State (A=1) | Outputs (X,Y) |
|---|---|---|---|
| S0 | S0 | S1 | 01 |
| S1 | S2 | S1 | 00 |
| S2 | S2 | S3 | 00 |
| S3 | S0 | S1 | 11 |
| Current State | Next State (A=0) | Next State (A=1) | Outputs (X,Y) |
|---|---|---|---|
| S0 | S0 | S1 | 00 |
| S1 | S2 | S1 | 01 |
| S2 | S2 | S3 | 10 |
| S3 | S0 | S1 | 11 |
- None of the above
TipAnswer
(c)
Read the eight arrows off the diagram — every state has exactly two, one per value of A, which is completeness for a one-input machine:
| State | Output XY | A = 0 | A = 1 |
|---|---|---|---|
| S0 | 01 | self-loop, stays S0 | goes to S1 |
| S1 | 00 | goes down to S2 | self-loop, stays S1 |
| S2 | 00 | self-loop, stays S2 | goes across to S3 |
| S3 | 11 | goes up to S0 | goes diagonally to S1 |
That is option (c), row for row.
Where each of the others goes wrong:
- (a) gets S1’s two arrows backwards — it makes S1 self-loop on 0 and go to S2 on 1, whereas the diagram has the self-loop labelled 1.
- (b) has the right S1 rows but sends S3 to S2 on A = 1; the diagonal arrow out of S3 goes to S1.
- (d) has the right next-state columns but the wrong outputs: it lists 00, 01, 10, 11 down the states, whereas the diagram gives 01, 00, 00, 11.
This is a Moore machine — the output is written inside each state bubble, so it depends only on the state and not on A, which is why (c) can fold the eight rows into four. See state-machines.
Q22 — Tracing a state machine
Consider the state machine represented by the state diagram in question 21 above (see Q21). What sequence of states is traversed if the machine starts in state S0 and A goes through the sequence 110011 (i.e. two 1’s followed by two 0’s followed by two 1’s)?
S0\(\to\)S1\(\to\)S2\(\to\)S2\(\to\)S3\(\to\)S1\(\to\)S1
S0\(\to\)S1\(\to\)S2\(\to\)S3\(\to\)S0\(\to\)S1\(\to\)S2
S0\(\to\)S1\(\to\)S1\(\to\)S2\(\to\)S2\(\to\)S3\(\to\)S3
S0\(\to\)S1\(\to\)S2\(\to\)S3\(\to\)S1\(\to\)S2\(\to\)S3
S0\(\to\)S1\(\to\)S1\(\to\)S2\(\to\)S2\(\to\)S3\(\to\)S1
TipAnswer
(e)
Feed the six input bits into the table derived in Q21, one transition per bit, starting from S0:
| Step | Input A | From | To |
|---|---|---|---|
| 1 | 1 | S0 | S1 |
| 2 | 1 | S1 | S1 (self-loop on 1) |
| 3 | 0 | S1 | S2 |
| 4 | 0 | S2 | S2 (self-loop on 0) |
| 5 | 1 | S2 | S3 |
| 6 | 1 | S3 | S1 |
Including the starting state, the traversal is
\[S0 \to S1 \to S1 \to S2 \to S2 \to S3 \to S1\]
which is option (e). The two self-loops are what separate it from the distractors: (a) and (b) skip them, and (c) has the right shape but ends with a self-loop on S3, which the diagram does not have — S3’s arrows both leave. See state-machines.
Q23 — Tanenbaum ALU bit slice
Consider the ALU bit slice below (from the Tanenbaum textbook, also shown in lectures)
Figure 43: Question 23’s ALU bit slice, the one from Tanenbaum. ENA, INVA and ENB condition A and B into the internal signals X and Y; the logical unit computes AB, A + B and B-bar from them and the full adder computes their sum; a two-to-four decoder driven by F0 and F1 raises exactly one enable line, so exactly one of the four results reaches the output OR.
For the ALU bit slice above, under what conditions will the ALU output be \(A\)?
ENA = 0, ENB = 0, INVA = 1, F\(_0\) = 1, F\(_1\) = 0, Carry in = 0
ENA = 1, ENB = 1, INVA = 1, F\(_0\) = 0, F\(_1\) = 0, Carry in = 0
ENA = 1, ENB = 0, INVA = 1, F\(_0\) = 0, F\(_1\) = 1, Carry in = 0
ENA = 1, ENB = 0, INVA = 0, F\(_0\) = 1, F\(_1\) = 1, Carry in = 0
None of the above
TipAnswer
(d)
Two things have to be worked out for every option: what the conditioning gates make of A and B, and which of the four function blocks the decoder enables.
The conditioning is read straight off the left of the figure:
\[X = (A \cdot \text{ENA}) \oplus \text{INVA} \qquad\qquad Y = B \cdot \text{ENB}\]
and the decoder’s four outputs pick the function in Tanenbaum’s order:
| \(F_0\) | \(F_1\) | Function selected |
|---|---|---|
| 0 | 0 | \(X\) AND \(Y\) |
| 0 | 1 | \(X\) OR \(Y\) |
| 1 | 0 | \(\overline{Y}\) |
| 1 | 1 | \(X + Y + \text{Carry in}\) (the adder) |
Now evaluate each option:
| Option | \(X\) | \(Y\) | Function | Output |
|---|---|---|---|---|
| (a) | ENA=0, INVA=1 \(\Rightarrow\) 1 | ENB=0 \(\Rightarrow\) 0 | \(\overline{Y}\) | \(\overline{0} = 1\) |
| (b) | ENA=1, INVA=1 \(\Rightarrow\) \(\overline{A}\) | ENB=1 \(\Rightarrow\) \(B\) | AND | \(\overline{A} \cdot B\) |
| (c) | ENA=1, INVA=1 \(\Rightarrow\) \(\overline{A}\) | ENB=0 \(\Rightarrow\) 0 | OR | \(\overline{A} + 0 = \overline{A}\) |
| (d) | ENA=1, INVA=0 \(\Rightarrow\) \(A\) | ENB=0 \(\Rightarrow\) 0 | adder | \(A + 0 + 0 = A\) |
Only (d) gives \(A\).
It is worth noticing why (d) works: the adder with one input forced to zero and no carry in is just a pass-through, so the arithmetic unit can move A to the output as easily as the logical unit can. The more familiar recipe from the combinations table — select OR, pass A, force the other side to zero — is not on offer here, since no option pairs \(F_0 = 0, F_1 = 1\) with INVA = 0. See arithmetic-logic-unit for the full table of useful control combinations.
Q24 — ALU bit slice with an 8-way mux
Consider the ALU bit slice below.
Figure 44: Question 24’s ALU bit slice. X = (A.ENA) xor INVA and Y = B.ENB feed eight candidate results; the multiplexer selects one under F2 F1 F0, giving in order X.Y, X + Y, X xor Y, NOT(X.Y), the carry in, the right shift in, Y-bar, and the full adder’s sum. The carry out is X.Y or the propagate term, which is gated so it only passes in add mode.
For an ALU made up of 8 of the bit slices above, which of the following control input settings will result in the ALU output being \(A - 1\)? (The “Right Shift In” control input refers to that for the most significant bit; the “Carry in” control input refers to that for the least significant bit.)
ENA = 1, ENB = 0, INVA = 0, F\(_2\) = 1, F\(_1\) = 1, F\(_0\) = 1, Right Shift In = 0, Carry in = 0
ENA = 1, ENB = 0, INVA = 1, F\(_2\) = 1, F\(_1\) = 1, F\(_0\) = 1, Right Shift In = 0, Carry in = 0
ENA = 1, ENB = 0, INVA = 0, F\(_2\) = 1, F\(_1\) = 1, F\(_0\) = 1, Right Shift In = 0, Carry in = 1
ENA = 1, ENB = 0, INVA = 1, F\(_2\) = 1, F\(_1\) = 1, F\(_0\) = 1, Right Shift In = 0, Carry in = 1
None of the above
TipAnswer
(e)
The conditioning is the same as in Q23:
\[X = (A \cdot \text{ENA}) \oplus \text{INVA} \qquad\qquad Y = B \cdot \text{ENB}\]
and the multiplexer’s eight inputs, in order, are
| \(F_2 F_1 F_0\) | Output |
|---|---|
| 000 | \(X \cdot Y\) |
| 001 | \(X + Y\) |
| 010 | \(X \oplus Y\) |
| 011 | \(\overline{X \cdot Y}\) |
| 100 | Carry in |
| 101 | Right Shift In |
| 110 | \(\overline{Y}\) |
| 111 | \(X + Y + \text{Carry in}\) (the full adder’s sum) |
Every option sets \(F_2 F_1 F_0 = 111\), so every option is doing arithmetic, and every option sets ENB = 0, so \(Y = 0\) across the whole word. That reduces the adder to \(X + 0 + C_{in}\), and there are only four things it can produce:
| Option | INVA | \(X\) | \(C_{in}\) | Result |
|---|---|---|---|---|
| (a) | 0 | \(A\) | 0 | \(A\) |
| (b) | 1 | \(\overline{A}\) | 0 | \(\overline{A}\), which is \(-A - 1\) |
| (c) | 0 | \(A\) | 1 | \(A + 1\) |
| (d) | 1 | \(\overline{A}\) | 1 | \(\overline{A} + 1\), which is \(-A\) |
None of them is \(A - 1\), so the answer is (e).
The reason is structural rather than a matter of picking the right row. \(A - 1\) means \(A + (-1)\), i.e. adding a word of all ones. The only way this slice can conjure a constant into the adder is through the B side, and B’s conditioning is just \(Y = B \cdot \text{ENB}\) — it can force Y to 0 or pass B through, but it can never force Y to 1. The A side can be forced to all ones (ENA = 0, INVA = 1), which is how \(B - 1\) is done, but there is no matching path to put A on the other adder input. Q25 is the same observation asked directly, and the two answers corroborate each other.
Q25 — What an ALU cannot compute
For the ALU in question 24 (see Q24), which of the following arithmetic operations can NOT be performed?
\(A + 1\)
\(B + 1\)
\(A - 1\)
\(B - 1\)
All of the above operations can be performed
TipAnswer
(c)
Work through the four operations using \(X = (A \cdot \text{ENA}) \oplus \text{INVA}\), \(Y = B \cdot \text{ENB}\) and the adder selected by \(F_2 F_1 F_0 = 111\):
| Operation | ENA | INVA | ENB | Carry in | \(X\) | \(Y\) | Sum |
|---|---|---|---|---|---|---|---|
| \(A + 1\) | 1 | 0 | 0 | 1 | \(A\) | 0 | \(A + 1\) ✓ |
| \(B + 1\) | 0 | 0 | 1 | 1 | 0 | \(B\) | \(B + 1\) ✓ |
| \(B - 1\) | 0 | 1 | 1 | 0 | all ones \(= -1\) | \(B\) | \(B - 1\) ✓ |
| \(A - 1\) | ? | ? | ? | ? | see below |
The three that work draw on two mechanisms, and both of them live on the A side or on the carry. A \(+1\) comes free as the carry into the least significant slice, which is how \(A + 1\) and \(B + 1\) are built. A \(-1\) has to be an operand of all ones, and the only place one can be conjured is the A path: setting ENA = 0 and INVA = 1 forces X to all ones, which is \(-1\) in two’s complement, and that is how \(B - 1\) is built.
\(A - 1\) needs the mirror image — A itself on one adder input and \(-1\) on the other — and the B side cannot produce a constant. \(Y = B \cdot \text{ENB}\) is either \(B\) or zero, never all ones, and there is no inverter on the B path to make it one. So \(A - 1\) cannot be done in a single pass, and the answer is (c).
Note the asymmetry is deliberate in this style of ALU: only one operand needs constant-generating hardware, because \(B - A\), \(B - 1\) and \(-1\) all fall out of putting it on the A side. See arithmetic-logic-unit, whose table of useful control combinations shows the same pattern.
Your score
Reload the page to clear your answers.
Sample Mid-semester Exam #5
This is UQ’s fifth sample mid-semester paper for CSSE2010/CSSE7201 Introduction to Computer Systems, printed for the Semester One mid-semester examinations, 2020, and set for St Lucia campus students. It runs for 60 minutes with 10 minutes of reading time, under open-book conditions — no electronic aids beyond a Casio FX82-series or UQ-approved calculator — and answers go on a supplied True/False and Multiple Choice answer sheet. There are 25 questions; each correct answer scores one mark, and an incorrect, missing or multiple answer scores zero, so there is no penalty for guessing. See csse2010 for the course note.
WarningAnswers are derived, not official
The source paper ships without an answer key, so every answer below was worked out during transcription rather than taken from UQ. Each one shows its reasoning so it can be checked rather than trusted; anything uncertain is flagged. Treat a disagreement between your working and the answer here as a reason to check both.
How to use this
Two ways. The first is a timed run: 25 questions in 60 minutes, working straight down the paper. On the site every answer is collapsed behind a disclosure triangle, so nothing is spoiled until you click it — that is the version to practise from. The second is targeted practice: use the question index below to pick out only the questions for one week or one concept, do those, and follow the concept link when the working does not make sense.
In the PDF build the collapsed callouts are always open, so the PDF is an answer key rather than a practice paper.
Question index
| Q | Topic | Week | Concept notes |
|---|---|---|---|
| 1 | Excess-128 representation | 1 | binary-number-representations · week1-lab-number-representations |
| 2 | Hexadecimal to octal | 1 | binary-number-representations · week1-lab-number-representations |
| 3 | Two’s complement range | 1 | binary-number-representations · week1-lab-number-representations |
| 4 | Converting between representations | 1 | binary-number-representations · week1-lab-number-representations |
| 5 | XNOR gate chain | 1 | logic-gates |
| 6 | Boolean simplification | 2 | boolean-algebra |
| 7 | Gate circuit for an expression | 1 | logic-gates |
| 8 | Expression to truth table | 2 | boolean-algebra |
| 9 | Timing diagram to expression | 2 | timing-diagrams |
| 10 | Sum-of-products form | 2 | boolean-algebra |
| 11 | 3-input NOR from 2-input NANDs | 1 | logic-gates |
| 12 | D flip-flop timing | 3 | flip-flops-and-latches |
| 13 | Two’s complement addition | 2 | binary-number-representations |
| 14 | Overflow detection | 2 | binary-number-representations |
| 15 | Overflow and result sign | 2 | binary-number-representations |
| 16 | Multiplexer as function generator | 2 | combinational-logic-blocks |
| 17 | Multiplexer output function | 2 | combinational-logic-blocks |
| 18 | Multiplexer-fed flip-flops | 3 | flip-flops-and-latches |
| 19 | Synchronous counter trace | 4 | counters |
| 20 | Flip-flops for a count sequence | 4 | state-machines |
| 21 | State diagram to state table | 4 | state-machines |
| 22 | State encoding width | 4 | state-machines |
| 23 | Tracing a state sequence | 4 | state-machines |
| 24 | ALU function select | 5 | arithmetic-logic-unit |
| 25 | ALU constant generation | 5 | arithmetic-logic-unit |
Q1 — Excess-128 representation
What is \(-75_{10}\) expressed in 8-bit excess-128 format?
00110101
01001011
10110100
10110101
11001011
TipAnswer
(a)
Excess-128 stores a value \(N\) as the plain unsigned binary of \(N + 128\). So
\[-75 + 128 = 53\]
and \(53 = 32 + 16 + 4 + 1\), which in 8 bits is \(00110101\).
Sanity check against the two’s complement form: \(-75\) in 8-bit two’s complement is \(10110101\) (option (d)), and excess-128 is exactly two’s complement with the sign bit flipped — flipping the leading 1 to 0 gives \(00110101\) again. See binary-number-representations.
Q2 — Hexadecimal to octal
What is the minimum number of octal digits needed to represent the number \(1ACED2010_{16}\)?
7
9
11
12
None of the above
TipAnswer
(c)
Go via binary, since both bases are powers of two. The number has nine hex digits, and each expands to four bits:
\[1\,A\,C\,E\,D\,2\,0\,1\,0 \;\to\; 0001\;1010\;1100\;1110\;1101\;0010\;0000\;0001\;0000\]
That is 36 bits with three leading zeros, so 33 significant bits. Octal digits take three bits each, and \(\lceil 33/3 \rceil = 11\).
Regrouping the 36 bits into twelve groups of three from the right confirms it — the first group is \(000\) and drops away:
\[000\;110\;101\;100\;111\;011\;010\;010\;000\;000\;010\;000 \;=\; 65473220020_8\]
which is 11 digits.
Q3 — Two’s complement range
A 5-bit number in two’s complement format can represent integers from
−32 to 31
−31 to 31
−16 to 15
−15 to 15
0 to 31
TipAnswer
(c)
An \(n\)-bit two’s complement number covers \(-2^{n-1}\) to \(2^{n-1}-1\). With \(n = 5\) that is \(-16\) to \(15\): \(10000\) is the most negative value and \(01111\) the most positive. The asymmetry is the giveaway — two’s complement has one more negative value than positive, which rules out (b) and (d) immediately, and (a) is the 6-bit range. See binary-number-representations.
Q4 — Converting between representations
Which of the following statements about binary number representations is FALSE?
Any 8-bit two’s complement number can be converted to excess-128 representation by inverting the sign-bit
Any negative n-bit two’s complement number can be converted to ones’ complement representation by subtracting 1
Any negative n-bit ones’ complement number can be converted to two’s complement representation by adding 1
Any negative n-bit ones’ complement number can be converted to signed-magnitude representation by inverting all bits except the sign-bit
None of the above
TipAnswer
(e) — all four statements are true, so none of them is the false one.
For a value \(v\) in \([-128, 127]\), two’s complement stores \(v \bmod 256\) and excess-128 stores \(v + 128\). For \(v \ge 0\) the stored patterns differ by exactly \(+128\), which sets a bit 7 that was 0; for \(v < 0\) they differ by exactly \(-128\), which clears a bit 7 that was 1. Either way, flip the sign bit. Q1 is a worked instance: \(-75\) is \(10110101\) in two’s complement and \(00110101\) in excess-128.
A negative \(v\) is stored as \(2^n + v\) in two’s complement and \(2^n - 1 + v\) in ones’ complement, a difference of exactly 1. Example with \(n=4\): \(-3\) is \(1101\) two’s complement, and \(1101 - 1 = 1100\), which is ones’ complement \(-3\). The one value this misses is \(-2^{n-1}\), which two’s complement can hold and ones’ complement cannot, so strictly nothing converts it; read as the standard conversion rule, which is how the paper means it, (b) is true.
The same identity read backwards, so it is true too: \(1100 + 1 = 1101\).
Ones’ complement represents \(-m\) as the bitwise complement of the pattern for \(+m\). Since \(+m\) has a 0 sign bit, the magnitude bits of \(-m\) are the complement of the magnitude of \(m\); inverting them back recovers \(m\) and leaves the 1 sign bit in place, which is exactly signed-magnitude. Example with \(n=4\): \(-3\) is \(1100\) in ones’ complement, and inverting the low three bits gives $1011 = $ signed-magnitude \(-3\).
Figure 45: The four statements as one map, worked on a single value. Options (d), (b)/(c) and (a) are the three links in the chain, read from left to right; each arrow is one of the paper’s four claims. The bit patterns are 4-bit representations of \(-3\), so you can check every arrow by eye: invert the magnitude bits, subtract or add one, flip the sign bit. The two left-hand links hold for negative values only, which is not a limitation in practice because all four formats already agree on the positives — the right-hand link is the one that works either way.
See binary-number-representations and week1-lab-number-representations for all four formats side by side.
Q5 — XNOR gate chain
What function is implemented by the following circuit?
Figure 46: Question 5’s circuit: A and B into an XNOR gate, whose output goes with C into a second XNOR gate.
\(\overline{A \oplus B} \oplus C\)
\(A \oplus B \oplus \overline{C}\)
\(\overline{A} \oplus \overline{B} \oplus \overline{C}\)
\(A \oplus B \oplus C\)
None of the above
TipAnswer
(d)
Both gates are XNORs — XOR bodies with an inversion bubble on the output. The first produces \(\overline{A \oplus B}\), and the second XNORs that with \(C\):
\[X = \overline{\;\overline{A \oplus B} \oplus C\;}\]
Now use the fact that complementing one input of an XOR complements its output, i.e. \(\overline{x} \oplus y = \overline{x \oplus y}\). Applying it to the inner term:
\[\overline{A \oplus B} \oplus C = \overline{(A \oplus B) \oplus C}\]
so the outer inversion cancels it and \(X = A \oplus B \oplus C\).
The other three options are all the same function as each other, and all equal \(\overline{A \oplus B \oplus C}\) — the complement of the answer. That is worth noticing: (a), (b) and (c) each apply an odd number of complements to an XOR chain, so they must agree with one another and disagree with (d). Two XNORs in series apply two complements, which cancel. See logic-gates.
Q6 — Boolean simplification
Which of the following logic functions is identical to \(\overline{\overline{A \cdot \overline{B}} \cdot C} \cdot (C + \overline{A} \cdot B)\)?
\(\overline{A} \cdot C + B \cdot C\)
\(A \cdot \overline{B} \cdot C + \overline{A} \cdot B \cdot \overline{C}\)
\(A \oplus B \oplus C\)
\(C\)
0 (False)
TipAnswer
(b)
Read the overbars carefully: in the source there are two bars over \(A\), three over \(B\) and one over \(C\) in the first factor, which parses as \(\overline{\overline{A \cdot \overline{B}} \cdot C}\).
Take the inner term first and push the complement in with De Morgan:
\[\overline{A \cdot \overline{B}} = \overline{A} + B\]
so the first factor is
\[\overline{(\overline{A} + B) \cdot C} = \overline{(\overline{A}+B)} + \overline{C} = A\overline{B} + \overline{C}\]
Now multiply out against the second factor:
\[(A\overline{B} + \overline{C})(C + \overline{A}B) = A\overline{B}C + A\overline{B}\,\overline{A}B + \overline{C}C + \overline{C}\,\overline{A}B\]
The middle two products each contain a variable and its complement, so they vanish, leaving
\[A \cdot \overline{B} \cdot C + \overline{A} \cdot B \cdot \overline{C}\]
which is option (b). See boolean-algebra.
Q7 — Gate circuit for an expression
Which of the following logic circuits is an implementation of the function \(A + \overline{B} \cdot \overline{C} + D\)?
Figure 47: Question 7’s five candidate circuits, (a) to (e), each taking A, B, C and D.
— the circuit labelled (a) above
— the circuit labelled (b) above
— the circuit labelled (c) above
— the circuit labelled (d) above
— the circuit labelled (e) above
TipAnswer
(b)
The target has one product term, \(\overline{B} \cdot \overline{C}\), ORed with the two bare literals \(A\) and \(D\). A NOR gate is that product term — \(\overline{B + C} = \overline{B} \cdot \overline{C}\) by De Morgan — so the circuit wanted is a 2-input NOR on B and C feeding a 3-input OR along with A and D. That is (b).
The others:
- uses a NAND instead of a NOR, giving \(A + \overline{B \cdot C} + D = A + \overline{B} + \overline{C} + D\). Same shape, wrong gate.
- gives \((A + \overline{B}) \cdot (\overline{C} + D)\) — a product of sums, not the right function (it is 0 when \(A=1, C=1, D=0\), where the target is 1).
- gives \((A \oplus \overline{B}\,\overline{C}) \oplus D\); XOR is not OR, so e.g. \(A = D = 1\) gives 0 rather than 1.
- gives \((A + \overline{B}) \cdot \overline{C} + D\), which is 0 when \(A = 1, C = 1, D = 0\).
See logic-gates.
Q8 — Expression to truth table
Which of the following truth tables is equivalent to the function \(X = A \cdot \left(B \cdot \overline{C} + \overline{A \cdot (B + \overline{C})}\right)\)?
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
- None of the above
TipAnswer
(d)
The whole expression is ANDed with \(A\), so \(X = 0\) whenever \(A = 0\) — that kills the top half of every table and is true of all four candidates, so it does not discriminate. Set \(A = 1\) and simplify:
\[A \cdot (B + \overline{C}) = B + \overline{C} \qquad\text{so}\qquad \overline{A \cdot (B + \overline{C})} = \overline{B + \overline{C}} = \overline{B} \cdot C\]
and therefore
\[X = B\overline{C} + \overline{B}C = B \oplus C\]
So the function is \(X = A \cdot (B \oplus C)\): 1 exactly when \(A = 1\) and \(B\) and \(C\) differ. That is rows \(101\) and \(110\), and nothing else:
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
which is table (d). Table (c) differs only in the \(101\) row and (b) only in the \(111\) row, so read those two rows carefully. See boolean-algebra.
Q9 — Timing diagram to expression
Which of the following expressions is NOT equivalent to the following timing diagram?
Figure 48: Question 9’s timing diagram: A, B and C step through all eight input combinations (A is the fastest-changing signal) and X is the resulting output.
\(\overline{B} \cdot (\overline{A} + \overline{C}) + A \cdot B \cdot C\)
\(\overline{B} \cdot \overline{C} + C \cdot (\overline{A} \oplus B)\)
\(\overline{A} \cdot \overline{B} + A \cdot (\overline{B} \oplus C)\)
\(\overline{A} \cdot \overline{B} + \overline{C} \cdot \overline{B} + A \cdot (B \oplus \overline{C})\)
None of the above
TipAnswer
(e) — every one of (a) to (d) is equivalent, so none of them is the odd one out.
First read the diagram off. A toggles every slot, B every two, C every four, so the nine intervals shown are the eight input combinations in binary counting order (with A as the least significant bit) plus a repeat of the first. X is high over slots 0, 1, 4 and 7:
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 |
So \(X = 1\) on exactly \(\{\overline{A}\,\overline{B}\,\overline{C},\; A\overline{B}\,\overline{C},\; \overline{A}\,\overline{B}C,\; ABC\}\) — writing the combinations as \(ABC\) bit strings, \(\{000, 100, 001, 111\}\).
Now test each option on that set:
- \(\overline{B}(\overline{A} + \overline{C})\) covers \(\overline{A}\,\overline{B}\) (that is 000 and 001) and \(\overline{B}\,\overline{C}\) (000 and 100); adding \(ABC\) (111) gives \(\{000, 001, 100, 111\}\). ✓
- \(\overline{B}\,\overline{C}\) covers \(\{000, 100\}\). \(\overline{A} \oplus B\) is 1 when \(A = B = 0\) or \(A = B = 1\), so \(C(\overline{A} \oplus B)\) covers \(\{001, 111\}\). Union is the same set. ✓
- \(\overline{A}\,\overline{B}\) covers \(\{000, 001\}\). \(\overline{B} \oplus C\) is 1 when \(B = 0, C = 0\) or \(B = 1, C = 1\), so \(A(\overline{B} \oplus C)\) covers \(\{100, 111\}\). ✓
- \(\overline{A}\,\overline{B}\) gives \(\{000, 001\}\), \(\overline{C}\,\overline{B}\) gives \(\{000, 100\}\), and \(B \oplus \overline{C}\) is 1 when \(B = 0, C = 0\) or \(B = 1, C = 1\), so \(A(B \oplus \overline{C})\) gives \(\{100, 111\}\). ✓
All four match, so the answer is (e). See timing-diagrams.
Q10 — Sum-of-products form
Which of the following is a sum-of-products expression equivalent to \((\overline{A} + B) \cdot \overline{(C + B \cdot D)}\)?
\(\overline{A} \cdot \overline{B} \cdot \overline{C} + \overline{A} \cdot \overline{C} \cdot \overline{D} + B \cdot \overline{C} \cdot \overline{D}\)
\(\overline{A} \cdot \overline{B} \cdot \overline{C} + \overline{A} \cdot \overline{C} \cdot \overline{D}\)
\(\overline{A} \cdot \overline{C} + B \cdot \overline{C} + \overline{A} \cdot \overline{B} \cdot \overline{D}\)
\(\overline{A} \cdot \overline{C} \cdot \overline{BD} + B \cdot \overline{C} \cdot \overline{BD}\)
None of the above
TipAnswer
(a)
Push the complement in with De Morgan, twice:
\[\overline{C + B \cdot D} = \overline{C} \cdot \overline{BD} = \overline{C} \cdot (\overline{B} + \overline{D})\]
so the whole expression is
\[(\overline{A} + B) \cdot \overline{C} \cdot (\overline{B} + \overline{D})\]
Multiply out the two sums:
\[(\overline{A} + B)(\overline{B} + \overline{D}) = \overline{A}\,\overline{B} + \overline{A}\,\overline{D} + B\overline{B} + B\overline{D} = \overline{A}\,\overline{B} + \overline{A}\,\overline{D} + B\overline{D}\]
since \(B\overline{B} = 0\). Distributing the \(\overline{C}\) gives
\[\overline{A}\,\overline{B}\,\overline{C} + \overline{A}\,\overline{C}\,\overline{D} + B\,\overline{C}\,\overline{D}\]
which is (a). Option (d) is also algebraically equal to the original, but it is not a sum of products — \(\overline{BD}\) is a complemented product, not a literal — and the question asks specifically for sum-of-products form. Option (b) is (a) with the last term missing, so it drops the case \(A = 1, B = 1, C = 0, D = 0\). See boolean-algebra.
Q11 — 3-input NOR from 2-input NANDs
Which of the following implements a 3-input NOR gate \((\overline{A + B + C})\) using only 2-input NAND gates?
Figure 49: Question 11’s five candidate NAND-only networks, (a) to (e). A NAND with its two inputs tied together — shown by the junction dot on its input lead — acts as an inverter.
— the circuit labelled (a) above
— the circuit labelled (b) above
— the circuit labelled (c) above
— the circuit labelled (d) above
— the circuit labelled (e) above
TipAnswer
(e)
Start from De Morgan: \(\overline{A + B + C} = \overline{A} \cdot \overline{B} \cdot \overline{C}\). So the network must invert all three inputs, AND them together, and a 2-input NAND only gives the AND complemented, so each AND needs a following inverter. A NAND with both inputs tied is an inverter, which is what the junction dots on the input leads mean.
Trace each option:
- (a) \(\text{NAND}(A,B)\), inverted, gives \(A \cdot B\); NANDed with \(C\) that is \(\overline{A \cdot B \cdot C}\) — a 3-input NAND, not a NOR.
- (b) Inverts A, B and C, then \(\text{NAND}(\overline{A}, \overline{B}) = A + B\), then NANDs that with \(\overline{C}\): \(\overline{(A+B) \cdot \overline{C}}\). Wrong.
- (c) Same as (b) but with an inverter after the first NAND, so the second NAND sees \(\overline{A}\,\overline{B}\) and \(\overline{C}\) and gives \(\overline{\overline{A}\,\overline{B}\,\overline{C}} = A + B + C\). That is a 3-input OR — one inversion short.
- (d) \(A \cdot B\) NANDed with \(\overline{C}\), i.e. \(\overline{A B \overline{C}}\). Wrong.
- (e) Exactly (c) with a seventh NAND wired as an inverter on the output, turning \(A + B + C\) into \(\overline{A + B + C}\). ✓
Counting gates is a quick filter: any correct answer needs at least three inverters (one per input), one NAND, one inverter to undo it, one more NAND and a final inverter — seven gates. Only (e) has seven. See logic-gates.
Q12 — D flip-flop timing
Consider the flip-flop circuit shown below and the associated CLK and output (Q) signals. Which timing diagram shows input (A) values over time which would have resulted in the given output (Q)?
Figure 50: Question 12’s given CLK and Q waveforms and the D flip-flop they belong to, with the five candidate A waveforms (a) to (e) below.
— the A waveform labelled (a) above
— the A waveform labelled (b) above
— the A waveform labelled (c) above
— the A waveform labelled (d) above
— the A waveform labelled (e) above
TipAnswer
(c)
The flip-flop is a plain D type with a triangle and no bubble on the clock input, so it samples D on each rising edge and holds in between. There are four rising edges in the CLK waveform. Reading Q against them:
| Rising edge | Q before | Q after | So A must have been |
|---|---|---|---|
| 1st | 0 | 1 | 1 |
| 2nd | 1 | 0 | 0 |
| 3rd | 0 | 0 | 0 |
| 4th | 0 | 1 | 1 |
So the required A is 1, 0, 0, 1 at the four rising edges, and completely unconstrained everywhere else — which is why several candidates look plausible until you check all four.
- is 1 at edge 1 but has risen again before edge 2, so Q would stay 1. ✗
- is right for the first three edges but has fallen again before edge 4, so Q would stay 0. ✗
- is 1, 0, 0, 1 at the four edges. ✓
- is 1, 0, then back to 1 before edge 3, which would set Q high a clock early. ✗
- is 1, 0, then 1 before edge 3 — same failure as (d). ✗
See flip-flops-and-latches and timing-diagrams.
Q13 — Two’s complement addition
What is the result of adding the 7-bit two’s complement numbers 1011001 and 0101111?
0000000
0001000
1110110
1110111
None of the above
TipAnswer
(b)
Add the bit patterns as unsigned binary and throw away the carry out of the top bit, which is what two’s complement addition always is:
1111111 <- carries
1011001
+ 0101111
---------
10001000
Discarding the ninth-column carry leaves \(0001000\).
Check in decimal: \(1011001\) has its sign bit set, so it is \(89 - 128 = -39\); \(0101111 = 47\). Then \(-39 + 47 = 8 = 0001000\). The signs of the operands differ, so overflow is impossible and the result is trustworthy. See binary-number-representations.
Q14 — Overflow detection
Which of the following operations will result in overflow in 5-bit two’s complement arithmetic?
01000 + 01000
11111 + 00001
11000 + 01111
11101 + 11010
None of the above
TipAnswer
(a)
5-bit two’s complement covers \(-16\) to \(+15\) (see Q3), and overflow means the true sum falls outside that. Adding operands of opposite sign can never overflow, so only (a) and (d) are even candidates.
- \(8 + 8 = 16\), which is one past the top of the range. The bit sum is \(01000 + 01000 = 10000\), which reads as \(-16\) — two positives producing a negative, the classic overflow signature. ✓
- \(-1 + 1 = 0\); signs differ, no overflow.
- \(-8 + 15 = 7\); signs differ, no overflow.
- \(-3 + (-6) = -9\), comfortably inside the range. The bit sum is \(11101 + 11010 = 110111\); dropping the carry gives \(10111 = -9\). Two negatives giving a negative, so no overflow.
Q15 — Overflow and result sign
Consider the binary addition operation 110111 + 101001. Which of the following statements is true if the numbers are interpreted as two’s complement?
The result is negative and no overflow occurs
The result should be negative but overflow occurs
The result is positive and no overflow occurs
The result is positive but overflow occurs
The result is zero
TipAnswer
(a)
These are 6-bit numbers, so the representable range is \(-32\) to \(+31\).
\[110111_2 = 55 \;\to\; 55 - 64 = -9 \qquad 101001_2 = 41 \;\to\; 41 - 64 = -23\]
and \(-9 + (-23) = -32\), which is exactly the most negative representable value — inside the range, so no overflow.
The bit-level addition agrees:
111111 <- carries
110111
+ 101001
--------
1100000
Dropping the carry out leaves \(100000 = -32\). Both operands are negative and the result is negative, so no overflow; equivalently, the carry into the sign column and the carry out of it are both 1, and overflow is their XOR, which is 0. See binary-number-representations.
Q16 — Multiplexer as function generator
Consider the following multiplexer. What must the inputs A,B,C,D be so that the multiplexer implements the function \(X = S_1 \oplus S_0 \oplus (G \cdot S_1)\)?
Figure 51: Question 16’s 4-to-1 multiplexer, with data inputs A, B, C and D on lines 0 to 3 and select inputs S1 and S0.
A= 1 B= 1 C= \(G\) D= \(\overline{G}\)
A= 0 B= 1 C= \(G\) D= \(\overline{G}\)
A= 1 B= 0 C= \(\overline{G}\) D= \(G\)
A= 0 B= 1 C= \(\overline{G}\) D= \(G\)
None of the above
TipAnswer
(d)
A multiplexer routes input \(i\) to the output when the select lines hold \(i\), so each data input is just the value the function takes for that one combination of \(S_1 S_0\). Evaluate \(X = S_1 \oplus S_0 \oplus (G \cdot S_1)\) four times:
| \(S_1 S_0\) | selected input | \(X\) |
|---|---|---|
| 00 | A | \(0 \oplus 0 \oplus (G \cdot 0) = 0\) |
| 01 | B | \(0 \oplus 1 \oplus (G \cdot 0) = 1\) |
| 10 | C | \(1 \oplus 0 \oplus (G \cdot 1) = 1 \oplus G = \overline{G}\) |
| 11 | D | \(1 \oplus 1 \oplus (G \cdot 1) = 0 \oplus G = G\) |
So A = 0, B = 1, C = \(\overline{G}\), D = \(G\), which is (d). The \(G \cdot S_1\) term is what makes only the bottom half depend on \(G\), and the \(S_1 \oplus S_0\) part is what flips \(\overline{G}\) into \(G\) between lines 2 and 3. See combinational-logic-blocks.
Q17 — Multiplexer output function
Consider the following multiplexer. Which of the following statements is TRUE? (+ indicates the logical OR operation)
Figure 52: Question 17’s 8-to-1 multiplexer, with the eight data lines hard-wired to constants and the select inputs S2, S1 and S0 driven by A, B and C.
If A is 0, \(X = \overline{B + C}\) If A is 1, \(X = B \cdot C\)
If A is 0, \(X = \overline{B \cdot C}\) If A is 1, \(X = \overline{B + C}\)
If A is 0, \(X = B + C\) If A is 1, \(X = \overline{B \cdot C}\)
If A is 0, \(X = \overline{B \cdot C}\) If A is 1, \(X = B + C\)
None of the above
TipAnswer
(d)
The select lines are \(S_2 S_1 S_0 = A\,B\,C\), so the selected line number is \(4A + 2B + C\) and A picks which half of the input list is in play.
With \(A = 0\) the mux can only reach lines 0–3, whose values are 1, 1, 1, 0:
| B | C | line | X |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 2 | 1 |
| 1 | 1 | 3 | 0 |
which is 0 only when both B and C are 1 — that is \(X = \overline{B \cdot C}\).
With \(A = 1\) it reaches lines 4–7, whose values are 0, 1, 1, 1:
| B | C | line | X |
|---|---|---|---|
| 0 | 0 | 4 | 0 |
| 0 | 1 | 5 | 1 |
| 1 | 0 | 6 | 1 |
| 1 | 1 | 7 | 1 |
which is 1 whenever either is 1 — that is \(X = B + C\).
So (d). This is the standard trick of using an \(n\)-select mux as a lookup table for an \(n\)-variable function. See combinational-logic-blocks.
Q18 — Multiplexer-fed flip-flops
Consider the circuit below. If A1 is 0 and A0 is 1, what are the values of Q1 and Q0 after five rising clock edges if FN is 0 for two rising clock edges then 1 for three rising clock edges?
Figure 53: Question 18’s circuit: two D flip-flops, each fed by a 2-to-1 multiplexer selected by FN — line 0 loads A1/A0, line 1 cross-couples the two Q outputs.
Q1 = 0 Q0 = 0
Q1 = 0 Q0 = 1
Q1 = 1 Q0 = 0
Q1 = 1 Q0 = 1
Insufficient information is provided to determine the values
TipAnswer
(c)
Read the multiplexers first. Each flip-flop’s D input comes from its own mux, and both muxes are selected by FN:
- FN = 0 selects line 0 on both, so \(D_1 = A_1\) and \(D_0 = A_0\) — a parallel load.
- FN = 1 selects line 1, and the wiring is crossed: \(D_1\) comes from \(Q_0\) and \(D_0\) comes from \(Q_1\) — a swap.
Now clock it. Note that the two load cycles wipe out whatever the flip-flops held beforehand, which is why (e) is not needed.
| Edge | FN | \(D_1 D_0\) | \(Q_1 Q_0\) after |
|---|---|---|---|
| start | — | — | unknown |
| 1 | 0 | \(A_1 A_0 = 01\) | 0 1 |
| 2 | 0 | \(A_1 A_0 = 01\) | 0 1 |
| 3 | 1 | \(Q_0 Q_1 = 10\) | 1 0 |
| 4 | 1 | \(Q_0 Q_1 = 01\) | 0 1 |
| 5 | 1 | \(Q_0 Q_1 = 10\) | 1 0 |
After five edges, \(Q_1 = 1\) and \(Q_0 = 0\). The swap has odd parity — three swaps is the same as one — which is the whole point of the question. See flip-flops-and-latches and combinational-logic-blocks.
Q19 — Synchronous counter trace
What sequence will the following synchronous counter count through, if it starts at Q1Q0 = 00?
Figure 54: Question 19’s synchronous counter. The OR gate is drawn mirrored, with its output pointing left back to D1; it takes Q0 and Q1-bar. The NAND takes Q0 and Q1 and drives D0.
Q1Q0: 00 → 01 → 11 → 10 → 11 → …
Q1Q0: 00 → 10 → 00 → …
Q1Q0: 00 → 11 → 01 → 11 → …
Q1Q0: 00 → 11 → 10 → 01 → 00 → …
Q1Q0: 00 → 11 → 10 → 01 → 11 → …
TipAnswer
(e)
Read the two next-state equations off the schematic. The OR gate is drawn mirrored — its output points left, back to the D input of the left flip-flop — and its two inputs are the \(Q_0\) rail running along the top and the \(\overline{Q}\) of the left flip-flop. The NAND takes the same \(Q_0\) rail and \(Q_1\), and drives the right flip-flop’s D. So
\[D_1 = Q_0 + \overline{Q_1} \qquad\qquad D_0 = \overline{Q_1 \cdot Q_0}\]
Both flip-flops share the clock, so evaluate both from the current state each cycle:
| \(Q_1 Q_0\) | \(D_1 = Q_0 + \overline{Q_1}\) | \(D_0 = \overline{Q_1 Q_0}\) | next |
|---|---|---|---|
| 00 | \(0 + 1 = 1\) | \(\overline{0} = 1\) | 11 |
| 11 | \(1 + 0 = 1\) | \(\overline{1} = 0\) | 10 |
| 10 | \(0 + 0 = 0\) | \(\overline{0} = 1\) | 01 |
| 01 | \(1 + 1 = 1\) | \(\overline{0} = 1\) | 11 |
So from 00 the machine runs 00 → 11 → 10 → 01 → 11 → 10 → 01 → …, settling into a three-state loop and never returning to 00. That is (e); (d) has the same first four states but wrongly loops back to 00. See counters.
Q20 — Flip-flops for a count sequence
What is the minimum number of flip-flops needed to implement a state machine which counts through the sequence 00000→00001→00011→11000→00001→… ?
2
3
4
5
32
TipAnswer
(a)
The five-bit patterns are the machine’s outputs, not necessarily its state encoding. Count the distinct patterns: 00000, 00001, 00011, 11000 — four of them, since the 00001 at the end of the sequence is the same state it was the first time round (the machine loops 00001 → 00011 → 11000 → 00001 forever after leaving 00000).
Four states need \(\lceil \log_2 4 \rceil = 2\) flip-flops, with combinational output logic decoding the two state bits into the five output bits. So (a).
Option (d) is the trap: five flip-flops is what you would need if you insisted on storing the output pattern directly in the register, which is the natural but not the minimal design. See state-machines.
Q21 — State diagram to state table
Consider the state diagram below.
Figure 55: Question 21’s Moore state diagram. Each bubble shows the state name above and its X,Y outputs below; the S4 to S8 transition carries no label, so it is taken for either value of A.
Which of the following is an equivalent state table?
| Current State | Input (A) | Next State | Outputs (X,Y) |
|---|---|---|---|
| S1 | 0 | S1 | 01 |
| S1 | 1 | S2 | 01 |
| S2 | 0 | S2 | 00 |
| S2 | 1 | S4 | 00 |
| S4 | 0 | S8 | 10 |
| S4 | 1 | S8 | 10 |
| S8 | 0 | S16 | 11 |
| S8 | 1 | S1 | 11 |
| S16 | 0 | S1 | 01 |
| S16 | 1 | S2 | 01 |
| Current State | Input (A) | Next State | Outputs (X,Y) |
|---|---|---|---|
| S1 | 0 | S1 | 01 |
| S1 | 1 | S2 | 01 |
| S2 | 0 | S2 | 00 |
| S2 | 1 | S4 | 00 |
| S4 | 0 | S8 | 10 |
| S4 | 1 | S8 | 10 |
| S8 | 0 | S1 | 11 |
| S8 | 1 | S16 | 11 |
| S16 | 0 | S1 | 01 |
| S16 | 1 | S2 | 01 |
| Current State | Next State (A=0) | Next State (A=1) | Outputs (X,Y) |
|---|---|---|---|
| S1 | S1 | S2 | 01 |
| S2 | S2 | S4 | 00 |
| S4 | S4 | S8 | 10 |
| S8 | S16 | S1 | 11 |
| S16 | S1 | S2 | 01 |
| Current State | Next State (A=0) | Next State (A=1) | Outputs (X,Y) |
|---|---|---|---|
| S1 | S1 | S2 | 01 |
| S2 | S2 | S4 | 00 |
| S4 | S8 | S8 | 01 |
| S8 | S16 | S1 | 11 |
| S16 | S1 | S2 | 01 |
- None of the above
TipAnswer
(a)
Read the ten transitions off the diagram. The outputs sit inside the bubbles, so this is a Moore machine and the output column depends only on the current state:
| From | On | To |
|---|---|---|
| S1 | \(\overline{A}\) | S1 (self-loop) |
| S1 | A | S2 |
| S2 | \(\overline{A}\) | S2 (self-loop) |
| S2 | A | S4 |
| S4 | (unlabelled) | S8 |
| S8 | \(\overline{A}\) | S16 |
| S8 | A | S1 |
| S16 | \(\overline{A}\) | S1 |
| S16 | A | S2 |
The S4 → S8 arrow carries no label, which means it is taken regardless of A — S4 has no other outgoing arrow, so it must be unconditional. Table (a) matches all of this line for line.
The other three each break in exactly one place:
- swaps S8’s two destinations: it sends S8 to S1 on A = 0 and to S16 on A = 1, the reverse of the diagram.
- gives S4 a self-loop on A = 0 instead of the unconditional move to S8.
- has the right transitions but prints S4’s outputs as 01 when the bubble says 10.
See state-machines.
Q22 — State encoding width
What is the minimum number of flip-flops needed to build the state machine shown in question 21?
1
2
3
4
5
TipAnswer
(c)
The diagram in Q21 has five states — S1, S2, S4, S8 and S16. A register of \(n\) flip-flops distinguishes \(2^n\) states, so \(n = \lceil \log_2 5 \rceil = 3\): two flip-flops would only cover four states, and three cover eight, leaving three encodings unused.
The state names are a distraction — they look like one-hot codes (1, 2, 4, 8, 16), and one-hot encoding really would need five flip-flops, which is option (e). But the question asks for the minimum, and nothing forces one-hot. See state-machines.
Q23 — Tracing a state sequence
Consider the state machine represented by the state diagram in question 21 above. What sequence of states is traversed if the machine starts in state S1 and A goes through the sequence 110011 (i.e. two 1’s followed by two 0’s followed by two 1’s)?
S1→S1→S2→S4→S8→S16→S2
S1→S2→S4→S8→S1→S2→S4
S1→S2→S2→S2→S4→S8→S16
S1→S2→S4→S8→S16→S2→S4
None of the above
TipAnswer
(d)
Six input values means six transitions, so the answer is a list of seven states starting at S1. Walk the table from Q21:
| Step | A | From | To |
|---|---|---|---|
| 1 | 1 | S1 | S2 |
| 2 | 1 | S2 | S4 |
| 3 | 0 | S4 | S8 (unconditional) |
| 4 | 0 | S8 | S16 |
| 5 | 1 | S16 | S2 |
| 6 | 1 | S2 | S4 |
giving S1→S2→S4→S8→S16→S2→S4, which is (d).
The step that separates the options is step 3: S4 moves on to S8 whatever A is, so the first 0 does not hold the machine still. Option (b) makes the mistake of sending S8 to S1 on A = 0, and (c) parks the machine in S2. See state-machines.
Q24 — ALU function select
Consider the ALU bit slice below.
Figure 56: Question 24’s ALU bit slice. ENA and ENB/INVB condition A and B into two internal rails; five logic blocks, the carry in, the right shift in and the full adder sum feed the eight inputs of a multiplexer selected by F2 F1 F0. The conditioned A rail is also the Right Shift Out.
For an ALU made up of 8 of the bit slices above, which of the following control input settings will result in the ALU output being \(A \oplus B\) ? (The “Right Shift In” control input refers to that for the most significant bit; the “Carry in” control input refers to that for the least significant bit.)
ENA = 1, ENB = 1, INVB = 0, F2 = 0, F1 = 0, F0 = 0, Right Shift In = 0, Carry in = 0
ENA = 1, ENB = 1, INVB = 1, F2 = 0, F1 = 0, F0 = 0, Right Shift In = 0, Carry in = 0
ENA = 1, ENB = 1, INVB = 1, F2 = 0, F1 = 1, F0 = 0, Right Shift In = 0, Carry in = 0
ENA = 1, ENB = 1, INVB = 0, F2 = 1, F1 = 1, F0 = 1, Right Shift In = 0, Carry in = 0
None of the above
TipAnswer
(e)
First read the slice. Two internal rails carry the conditioned inputs:
\[X = A \cdot \text{ENA} \qquad\qquad Y = (B \cdot \text{ENB}) \oplus \text{INVB}\]
and the \(X\) rail is also what leaves as Right Shift Out. Eight things feed the multiplexer, which is selected by \(F_2 F_1 F_0\) as a 3-bit number:
| \(F_2 F_1 F_0\) | mux line | Output |
|---|---|---|
| 000 | 0 | \(\overline{X + Y}\) |
| 001 | 1 | \(X \cdot Y\) |
| 010 | 2 | \(X + Y\) |
| 011 | 3 | \(\overline{X \cdot Y}\) |
| 100 | 4 | Carry In |
| 101 | 5 | \(\overline{X}\) |
| 110 | 6 | Right Shift In |
| 111 | 7 | \(X \oplus Y \oplus C_{in}\) (the adder sum) |
and the carry out is \(X \cdot Y + F_2 F_1 F_0 \cdot (X \oplus Y) \cdot C_{in}\) — an ordinary full-adder carry, with the propagate term switched off unless the adder is actually selected.
Now the options. All four set ENA = ENB = 1, so \(X = A\) throughout.
- INVB = 0 gives \(Y = B\), and \(F = 000\) selects NOR: \(\overline{A + B}\). ✗
- INVB = 1 gives \(Y = \overline{B}\), and \(F = 000\) selects NOR: \(\overline{A + \overline{B}} = \overline{A} \cdot B\). ✗
- \(Y = \overline{B}\) and \(F = 010\) selects OR: \(A + \overline{B}\). ✗
- \(Y = B\) and \(F = 111\) selects the adder. The per-bit output is \(A_i \oplus B_i \oplus C_i\), which looks like XOR, and for bit 0 (where Carry in = 0 is given) it is. But \(F = 111\) also switches the carry chain on, so bit 0 sends \(A_0 \cdot B_0\) into bit 1, bit 1 sends its carry into bit 2, and so on. What the 8-bit ALU computes is \(A + B\), not \(A \oplus B\); the two agree only when no pair of bits is 1 together. ✗
No mux line produces XOR without the carry chain, and there is no way to select the sum while stopping the carries, so the answer is (e).
Check this one. The intended answer may well be (d) if the examiner meant only the per-slice sum expression \(A \oplus B \oplus C_{in}\) — but in an 8-bit ALU the carries into slices 1–7 are not zero, so (d) really computes addition. The parenthetical note that Carry in refers only to the least significant bit is the hint that the ripple is meant to be taken seriously.
Q25 — ALU constant generation
For the ALU in Q24, which of the following control input settings will NOT result in the ALU output being the constant value –1 (negative one)?
ENA = 0, ENB = 0, INVB = 0, F2 = 0, F1 = 0, F0 = 0, Right Shift In = 1, Carry in = 0
ENA = 0, ENB = 0, INVB = 1, F2 = 0, F1 = 1, F0 = 0, Right Shift In = 0, Carry in = 1
ENA = 1, ENB = 0, INVB = 0, F2 = 0, F1 = 1, F0 = 1, Right Shift In = 0, Carry in = 1
ENA = 1, ENB = 1, INVB = 1, F2 = 0, F1 = 1, F0 = 1, Right Shift In = 0, Carry in = 0
ENA = 0, ENB = 1, INVB = 1, F2 = 1, F1 = 0, F0 = 1, Right Shift In = 0, Carry in = 1
TipAnswer
(d)
In two’s complement, \(-1\) is all ones, so the question is really: which setting fails to force every bit of the output to 1 regardless of the data in A and B? Use the rails and the mux table from Q24: \(X = A \cdot \text{ENA}\) and \(Y = (B \cdot \text{ENB}) \oplus \text{INVB}\).
- ENA = ENB = INVB = 0, so \(X = 0\) and \(Y = 0\). \(F = 000\) selects NOR: \(\overline{0 + 0} = 1\) on every bit. ✓ gives \(-1\).
- \(X = 0\); ENB = 0 with INVB = 1 gives \(Y = 0 \oplus 1 = 1\). \(F = 010\) selects OR: \(0 + 1 = 1\). ✓
- ENA = 1 so \(X = A\); ENB = 0, INVB = 0 so \(Y = 0\). \(F = 011\) selects NAND: \(\overline{A \cdot 0} = \overline{0} = 1\) whatever A is. ✓
- ENA = ENB = 1 and INVB = 1, so \(X = A\) and \(Y = \overline{B}\). \(F = 011\) selects NAND: \(\overline{A \cdot \overline{B}}\), which is 0 whenever \(A = 1\) and \(B = 0\). Data-dependent, so not the constant \(-1\). ✗
- ENA = 0 so \(X = 0\); \(F = 101\) selects \(\overline{X} = \overline{0} = 1\). ✓
Only (d) leaves the output depending on the data, so it is the one that will not give \(-1\).
The general lesson is the point of the question: ENA and ENB let the ALU force a rail to a constant 0, and INVB (or the NOT/NAND/NOR lines) turns that into a constant 1 across the whole word. That is how an ALU with no dedicated constant hardware still manages to produce \(-1\), and by extension \(B - 1\) and \(B - A\). See arithmetic-logic-unit.
Your score
Reload the page to clear your answers.
Sample Mid-semester Exam #6
This is UQ’s sixth sample mid-semester paper for csse2010 — CSSE2010/CSSE7201 Introduction to Computer Systems — printed for the Semester One mid-semester examinations of 2020, St Lucia campus. It runs for 60 minutes with 10 minutes of reading time, is an open book examination (calculators limited to the Casio FX82 series or a UQ-approved labelled model, no electronic aids), and is answered entirely on a supplied True/False and Multiple Choice answer sheet. There are 25 questions, each worth one mark; incorrect, missing or multiple answers score zero, so there is no penalty for guessing.
The paper covers the first five weeks of the course: number representations and binary arithmetic, logic gates and Boolean simplification, combinational blocks, flip-flops and counters, state machines, and the ALU bit slice.
WarningAnswers are derived, not official
The source paper ships without an answer key, so every answer below was worked out during transcription rather than taken from UQ. Each one shows its reasoning so it can be checked rather than trusted; anything uncertain is flagged. Treat a disagreement between your working and the answer here as a reason to check both.
How to use this
Two ways. Timed run — do all 25 questions in 60 minutes without looking at anything; on the website the answers are collapsed, so they stay hidden until you click them. Targeted practice — use the index table below to pick out only the questions for one week or one concept, and read the working straight away.
Note that in the PDF build every answer is expanded and visible, so the site version is the one to practise from.
Question index
| Q | Topic | Week | Concept notes |
|---|---|---|---|
| 1 | Two’s complement of a negative | 1 | binary-number-representations · week1-lab-number-representations |
| 2 | Octal to hexadecimal width | 1 | binary-number-representations · week1-lab-number-representations |
| 3 | Excess-32 range | 1 | binary-number-representations · week1-lab-number-representations |
| 4 | Ones’ to two’s complement | 1 | binary-number-representations · week1-lab-number-representations |
| 5 | Reading a two-gate circuit | 1 | logic-gates |
| 6 | Simplifying a product of sums | 2 | boolean-algebra |
| 7 | Circuit for an XOR expression | 1 | logic-gates |
| 8 | Truth table for an expression | 2 | boolean-algebra |
| 9 | Timing diagram to expression | 2 | timing-diagrams |
| 10 | Simplifying a complemented product | 2 | boolean-algebra |
| 11 | 3-input NOR from 2-input NORs | 2 | boolean-algebra |
| 12 | D flip-flop input from its output | 3 | flip-flops-and-latches |
| 13 | Two’s complement addition | 2 | binary-number-representations |
| 14 | Detecting overflow | 2 | binary-number-representations |
| 15 | Overflow on an addition | 2 | binary-number-representations |
| 16 | Multiplexer as function generator | 2 | combinational-logic-blocks |
| 17 | Reading an 8-input multiplexer | 2 | combinational-logic-blocks |
| 18 | Load/shift register trace | 3 | shift-registers |
| 19 | Synchronous counter sequence | 4 | counters |
| 20 | Flip-flops for an output sequence | 4 | state-machines |
| 21 | State diagram to state table | 4 | state-machines |
| 22 | Flip-flops for a state machine | 4 | state-machines |
| 23 | Tracing a state machine | 4 | state-machines |
| 24 | ALU control settings | 5 | arithmetic-logic-unit |
| 25 | ALU control settings | 5 | arithmetic-logic-unit |
Q1 — Two’s complement of a negative
What is \(-73_{10}\) expressed in 8-bit two’s complement format?
01001000
01001001
10110110
10110111
11001001
TipAnswer
(d)
Start from the magnitude. \(73 = 64 + 8 + 1\), so
\[73_{10} = 0100\,1001_2\]
which is option (b) — the positive value, offered as a distractor. Negate it the usual way (see binary-number-representations): invert every bit, then add one.
\[\overline{0100\,1001} = 1011\,0110 \qquad 1011\,0110 + 1 = 1011\,0111\]
So \(-73_{10} = 1011\,0111_2\). Option (c) is the one’s complement — the inversion without the \(+1\) — which is the usual slip here.
Checking: \(1011\,0111\) as two’s complement is \(-128 + 32 + 16 + 4 + 2 + 1 = -128 + 55 = -73\). ✓
Q2 — Octal to hexadecimal width
What is the minimum number of hexadecimal digits needed to represent the octal number 120105?
4
5
6
18
None of the above
TipAnswer
(a)
Go through binary, since one octal digit is exactly three bits and one hex digit is exactly four:
\[120105_8 = \underbrace{001}_{1}\ \underbrace{010}_{2}\ \underbrace{000}_{0}\ \underbrace{001}_{1}\ \underbrace{000}_{0}\ \underbrace{101}_{5}\]
That is 18 bits, but the leading two are zeros, so the value is really 16 significant bits. Regroup from the right in fours:
\[1010\ 0000\ 0100\ 0101_2 = \mathrm{A}045_{16}\]
Four hex digits. Option (d), 18, is the bit count rather than the digit count; option (c), 6, is the octal digit count.
Checking in decimal: \(120105_8 = 8^5 + 2\cdot 8^4 + 8^2 + 5 = 32768 + 8192 + 64 + 5 = 41029\), and \(\mathrm{A}045_{16} = 10 \cdot 4096 + 4 \cdot 16 + 5 = 41029\). ✓
Q3 — Excess-32 range
A 6-bit number in excess-32 format can represent integers from
–32 to 31
–31 to 32
–32 to 32
0 to 63
None of the above
TipAnswer
(a)
In excess-\(K\) (biased) notation the stored bit pattern is read as an ordinary unsigned number and then \(K\) is subtracted to get the value it represents:
\[\text{value} = \text{unsigned}(b) - K\]
Six bits give unsigned values \(0\) to \(2^6 - 1 = 63\), and here \(K = 32\), so the representable values run from \(0 - 32 = -32\) up to \(63 - 32 = 31\).
Option (d) is the unsigned range before the bias is applied; option (c) has 65 values, which six bits cannot hold.
Q4 — Ones’ to two’s complement
How can any n-bit ones’ complement number be converted to an (n+1)-bit two’s complement representation?
By prepending 0 and adding 1
By prepending the sign-bit, flipping all the bits and then adding 1
By prepending the sign-bit
By prepending the sign-bit and adding 1
By prepending the sign-bit and adding the value of the sign-bit
TipAnswer
(e)
The word any is what the question turns on: the recipe has to work for positive and negative values alike, and the four wrong options each work for only one sign.
Write the \(n\)-bit ones’ complement number as sign bit \(s\) over the remaining bits, whose unsigned value is \(M\). Its value is
\[V = -s\,(2^{n-1} - 1) + M\]
because a negative ones’ complement number is the bitwise inverse of its magnitude. Now prepend a copy of the sign bit, giving an \((n+1)\)-bit pattern \(s\,s\,b_{n-2}\ldots b_0\), and read it as two’s complement:
\[-s\,2^{n} + s\,2^{n-1} + M = -s\,2^{n-1} + M\]
That is short of \(V\) by exactly \(s\). Adding \(s\) — “the value of the sign-bit” — closes the gap:
\[-s\,2^{n-1} + M + s = -s\,(2^{n-1} - 1) + M = V\]
Concretely, with \(n = 4\):
| Ones’ complement | Value | Prepend sign | Add \(s\) | Two’s complement value |
|---|---|---|---|---|
| 0011 | \(+3\) | 00011 | \(+0\) = 00011 | \(+3\) ✓ |
| 1010 | \(-5\) | 11010 | \(+1\) = 11011 | \(-5\) ✓ |
| 1000 | \(-7\) | 11000 | \(+1\) = 11001 | \(-7\) ✓ |
| 1111 | \(-0\) | 11111 | \(+1\) = 00000 | \(0\) ✓ |
Figure 57: The first two rows of that table drawn out. Prepending the sign bit is the same move in both cases, but it lands in the right place only for the positive value: reading the widened negative pattern as two’s complement gives \(-6\), one too low, because ones’ complement’s top bit is worth \(-(2^{n-1}-1)\) while two’s complement’s is worth \(-2^{n-1}\). The correction is exactly that difference of 1, and it is needed precisely when the sign bit is 1 — which is what makes ‘add the value of the sign-bit’ the only option that works for both signs. The prepended bit is shaded.
Option (d) adds 1 unconditionally, which is right for negatives and one too many for positives (it would turn \(+3\) into \(+4\)); option (c) never adds, which is right for positives and one too few for negatives.
See week1-lab-number-representations for the two formats’ bit-position weights side by side, which is where the difference of 1 comes from.
Q5 — Reading a two-gate circuit
What function is implemented by the following circuit?
Figure 58: Question 5’s circuit: a two-input NOR on A and B, whose output is one input of a two-input NAND with C.
\(\overline{A . B . C}\)
\(\overline{\overline{A + B} . C}\)
\(\overline{\overline{A} + \overline{B} . C}\)
\(\overline{(\overline{A} + \overline{B}) . C}\)
\(\overline{\overline{A . B} + C}\)
TipAnswer
(b)
Read the circuit gate by gate. The first gate is an OR body with an output bubble — a NOR — so its output is
\[\overline{A + B}\]
That feeds one input of an AND body with an output bubble — a NAND — whose other input is \(C\). A NAND of \(P\) and \(C\) is \(\overline{P \cdot C}\), so the whole circuit is
\[\overline{\overline{A + B} \cdot C}\]
which is option (b) exactly as printed.
The distractors are all plausible readings of a two-gate circuit: option (d) is what you get if the first gate is misread as a NAND (\(\overline{A \cdot B} = \overline{A} + \overline{B}\) into a NAND with \(C\)), and option (e) swaps the two gate types over entirely. Options (a) and (c) do not have the right shape at all — (a) is a single three-input NAND, (c) has the outer bar covering an OR rather than the AND with \(C\).
Q6 — Simplifying a product of sums
Which of the following logic functions is identical to \(\overline{(A+B).(\overline{A}+B+C)}\)?
\(\overline{B}\)
\(\overline{A}.\overline{B}.\overline{C}\)
\(\overline{A}.\overline{B} + \overline{B}.\overline{C}\)
\(\overline{A}+\overline{B}+\overline{C}\)
None of the above
TipAnswer
(c)
Simplify what is inside the bar first, by multiplying the two sums out:
\[ \begin{aligned} (A+B)(\overline{A}+B+C) &= A\overline{A} + AB + AC + \overline{A}B + BB + BC \\ &= 0 + AB + AC + \overline{A}B + B + BC \\ &= B\,(A + \overline{A} + 1 + C) + AC \\ &= B + AC \end{aligned} \]
Everything with a \(B\) in it collapses into the bare \(B\) term, leaving \(AC\) beside it. Now complement, using De Morgan twice (see boolean-algebra):
\[ \begin{aligned} \overline{B + AC} &= \overline{B} \cdot \overline{AC} \\ &= \overline{B}\,(\overline{A} + \overline{C}) \\ &= \overline{A}\,\overline{B} + \overline{B}\,\overline{C} \end{aligned} \]
which is option (c).
Spot-check a row: \(A=1, B=0, C=0\) gives \((1+0)(0+0+0) = 1 \cdot 0 = 0\), so the complement is 1; and \(\overline{A}\overline{B} + \overline{B}\overline{C} = 0 \cdot 1 + 1 \cdot 1 = 1\). ✓
Q7 — Circuit for an XOR expression
Which of the following logic circuits is an implementation of the function \((\overline{A.B}) \oplus (\overline{C+D})\)?
Figure 59: Question 7’s five candidate circuits, laid out as one figure: (a), (b) and (c) on the top row, (d) and (e) on the bottom. Small circles on a gate’s inputs in (b) are inversion bubbles; a circle on the output is the usual NAND/NOR/XNOR bubble.
TipAnswer
(e)
The trap here is that the target expression complements both halves before the XOR, and XOR is blind to complementing both of its inputs:
\[\overline{P} \oplus \overline{Q} = \overline{P}\,Q + P\,\overline{Q} \dots\]
more directly, \(\overline{P} \oplus \overline{Q} = (\overline{P} \oplus Q) \oplus 1 \oplus 1 \cdots\) — easiest just to check the four rows:
| \(P\) | \(Q\) | \(P \oplus Q\) | \(\overline{P} \oplus \overline{Q}\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
They are the same column. So with \(P = A.B\) and \(Q = C+D\),
\[(\overline{A.B}) \oplus (\overline{C+D}) = (A.B) \oplus (C+D)\]
and the circuit that draws that literally is (e): a plain AND on \(A,B\), a plain OR on \(C,D\), and an XOR joining them.
Checking the others, in the same \(P \oplus Q\) terms:
- (a) has no XOR at all — it is \(C + \overline{A.B} + D\).
- (b) is \((\overline{A}.\overline{B}) \oplus (\overline{C}+\overline{D}) = \overline{A+B} \oplus \overline{C.D} = (A+B) \oplus (C.D)\) — the AND and OR the wrong way round.
- (c) is \(\overline{\overline{A.B} \oplus \overline{C \oplus D}}\) — an XNOR of an XNOR, nothing like it.
- (d) is \(\overline{A+B} \oplus \overline{C.D}\), the same function as (b), which is another reason neither can be the answer.
Q8 — Truth table for an expression
Which of the following truth tables is equivalent to the function
\[X = \left(\overline{\overline{A} . \overline{C}}\right) . \left(\overline{\overline{A} . B} + \overline{C} . B\right)\]
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
- None of the above
TipAnswer
(a)
Simplify before tabulating — it is much less error-prone than eight substitutions. De Morgan turns both complemented products into sums:
\[\overline{\overline{A}\,\overline{C}} = A + C \qquad\qquad \overline{\overline{A}\,B} = A + \overline{B}\]
so
\[X = (A + C)\,\bigl(A + \overline{B} + \overline{C}\,B\bigr)\]
The second bracket absorbs: \(\overline{B} + B\,\overline{C} = \overline{B} + \overline{C}\) (the classic \(P + \overline{P}Q = P + Q\) with \(P = \overline{B}\), \(Q = \overline{C}\)). That leaves
\[X = (A + C)\,(A + \overline{B} + \overline{C})\]
Multiply out. Every term containing \(A\) collapses into a single \(A\), and \(C \cdot \overline{C} = 0\):
\[X = A + C\,\overline{B} + C\,\overline{C} = A + \overline{B}\,C\]
Tabulating \(A + \overline{B}C\):
| A | B | C | \(\overline{B}C\) | X |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 |
That is 0, 1, 0, 0, 1, 1, 1, 1 — option (a). Option (d) is just \(X = A\), i.e. what you get if you drop the \(\overline{B}C\) term.
Q9 — Timing diagram to expression
Which of the following expressions is NOT equivalent to the following timing diagram?
Figure 60: Question 9’s timing diagram. A toggles every interval, B every two and C every four, so the eight intervals cover all eight combinations of A, B and C once each; X is the function being described. All four signals return to 0 in the tail at the right.
\(A.\overline{C} + B.\overline{C} + \overline{A}.B + \overline{A}.C\)
\((A \oplus C) + \overline{A}.B.\overline{C}\)
\(A.\overline{B}.\overline{C} + B.\overline{C} + \overline{A}.C\)
\(A.\overline{B}.\overline{C} + A.B.\overline{C} + \overline{A}.B + \overline{A}.\overline{B}.C\)
All of the above are equivalent to the timing diagram
TipAnswer
(e)
First read the diagram off as a truth table. \(A\) toggles every interval, \(B\) every second interval and \(C\) every fourth, so the eight intervals are the eight combinations of \(ABC\) — but note they arrive in the order \(C B A\) counting up, not \(ABC\). Reading the level of each track in each interval:
| Interval | A | B | C | X |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 0 | 1 | 0 | 1 |
| 4 | 1 | 1 | 0 | 1 |
| 5 | 0 | 0 | 1 | 1 |
| 6 | 1 | 0 | 1 | 0 |
| 7 | 0 | 1 | 1 | 1 |
| 8 | 1 | 1 | 1 | 0 |
Sorted into \(ABC\) order, \(X\) is 1 for \(ABC \in \{001, 010, 011, 100, 110\}\) and 0 for \(\{000, 101, 111\}\). Grouping the minterms:
\[X = \overline{A}\,\overline{B}\,C + \overline{A}B\overline{C} + \overline{A}BC + A\overline{B}\,\overline{C} + AB\overline{C} = \overline{A}B + A\overline{C} + \overline{A}\,\overline{B}C = \overline{A}B + \overline{A}C + A\overline{C}\]
Now evaluate all four options on those eight rows. Writing the \(X\) column as the string \(X_{000}X_{001}\ldots X_{111}\), the diagram gives 01111010, and:
| Option | \(X\) column | Matches? |
|---|---|---|
| (a) \(A\overline{C} + B\overline{C} + \overline{A}B + \overline{A}C\) | 01111010 | yes |
| (b) \((A \oplus C) + \overline{A}B\overline{C}\) | 01111010 | yes |
| (c) \(A\overline{B}\,\overline{C} + B\overline{C} + \overline{A}C\) | 01111010 | yes |
| (d) \(A\overline{B}\,\overline{C} + AB\overline{C} + \overline{A}B + \overline{A}\,\overline{B}C\) | 01111010 | yes |
All four are the same function, written four ways: (d) is the raw minterm list with two terms merged, (a) adds the redundant \(B\overline{C}\) cover, (c) splits \(A\overline{C}\) against \(B\), and (b) notices that everything except \(\overline{A}B\overline{C}\) is exactly \(A \ne C\). So nothing on the list fails, and the answer is (e).
Worth noticing as a sanity check: since (a)–(d) are all identical to each other, the answer could only ever be “all of them” or “none of them”, and there is no “none” option — so the diagram had to match.
Q10 — Simplifying a complemented product
Which of the following logic functions is identical to \(\overline{(A + \overline{C}).(\overline{A} + B.\overline{C})}\) ?
\(A.\overline{B} + C\)
\(\overline{A}.B + C\)
\(A.\overline{B} + A.C\)
\(\overline{A}.C + B.\overline{C}\)
None of the above
TipAnswer
(a)
Multiply out the inside first:
\[ \begin{aligned} (A + \overline{C})(\overline{A} + B\overline{C}) &= A\overline{A} + AB\overline{C} + \overline{A}\,\overline{C} + B\overline{C}\,\overline{C} \\ &= 0 + AB\overline{C} + \overline{A}\,\overline{C} + B\overline{C} \\ &= \overline{A}\,\overline{C} + B\overline{C} \end{aligned} \]
\(AB\overline{C}\) is absorbed by \(B\overline{C}\) (it is a subset of it), and \(\overline{C}\,\overline{C} = \overline{C}\). Factor:
\[= \overline{C}\,(\overline{A} + B)\]
Now complement with De Morgan (see boolean-algebra):
\[\overline{\overline{C}\,(\overline{A}+B)} = C + \overline{\overline{A}+B} = C + A\overline{B}\]
which is option (a).
Spot-check: \(A=1, B=0, C=0\) gives \((1+1)(0+0) = 0\) inside, so the answer should be 1; and \(A\overline{B} + C = 1 \cdot 1 + 0 = 1\). ✓ And \(A=0,B=1,C=0\) gives \((0+1)(1+1) = 1\) inside, so 0 out; \(A\overline{B}+C = 0 + 0 = 0\). ✓
Q11 — 3-input NOR from 2-input NORs
Which of the following circuits implements a 3 input NOR gate (\(\overline{A + B + C}\)) using only 2-input NOR gates?
Figure 61: Question 11’s five candidate NOR-only circuits. A gate whose two inputs are tied together (the bracket and dot on its left) is being used as an inverter.
TipAnswer
(b)
Writing \(\text{NOR}(P,Q) = \overline{P+Q}\), note that a NOR with both inputs tied together is an inverter: \(\text{NOR}(P,P) = \overline{P}\). That is the only extra trick needed.
The target is \(\overline{A+B+C}\). The obvious first move — NOR \(A\) with \(B\), then NOR that with \(C\) — does not work, because the first NOR has already complemented \(A+B\):
\[\text{NOR}(\text{NOR}(A,B),\,C) = \overline{\overline{A+B} + C} = (A+B)\,\overline{C}\]
which is option (a). The fix is to un-complement in between. Take \(\text{NOR}(A,B) = \overline{A+B}\), feed it into a tied-input NOR to get \(A+B\) back, then NOR that with \(C\):
\[\text{NOR}\bigl(\overline{\overline{A+B}},\,C\bigr) = \overline{(A+B) + C} = \overline{A+B+C}\]
Three gates, and that is exactly the arrangement drawn in (b).
The others:
- (c) inverts all three inputs first, then NORs \(\overline{A}\) with \(\overline{B}\) to get \(\overline{\overline{A}+\overline{B}} = A.B\), then NORs that with \(\overline{C}\): \(\overline{A.B + \overline{C}}\).
- (d) is (b) with \(C\) inverted on the way in, giving \(\overline{A + B + \overline{C}}\).
- (e) is (c) with an extra inverter after the \(A.B\) stage, giving \(\overline{\overline{A.B} + \overline{C}} = A.B.C\).
Only (b) leaves all three variables uncomplemented under one bar.
Q12 — D flip-flop input from its output
Consider the flip-flop circuit shown below and the associated CLK and output (Q) signals. Which timing diagram shows input (A) values over time which would have resulted in the given output (Q).
Figure 62: Question 12’s flip-flop and waveforms: the D flip-flop symbol, then the given CLK and Q traces, then the five candidate A traces (a)–(e) on the same time axis.
A
A
A
A
A
TipAnswer
(c)
The symbol has a triangle on the clock input and no bubble, so it is a positive-edge-triggered D flip-flop: \(Q\) takes the value \(D\) had immediately before each rising CLK edge, and does nothing at any other time (see flip-flops-and-latches).
There are four rising edges. Reading \(Q\) across them:
| Rising edge | \(Q\) before | \(Q\) after | So \(A\) must have been |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 2 | 0 | 1 | 1 |
| 3 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 |
The requirement is therefore \(A = 0, 1, 1, 0\) at the four edges, and what \(A\) does between edges is irrelevant. Checking each candidate at the four edge times:
| edge 1 | edge 2 | edge 3 | edge 4 | ||
|---|---|---|---|---|---|
| required | 0 | 1 | 1 | 0 | |
| (a) | 0 | 1 | 0 | 1 | fails at edge 3 |
| (b) | 0 | 1 | 0 | 0 | fails at edge 3 |
| (c) | 0 | 1 | 1 | 0 | matches |
| (d) | 0 | 1 | 0 | 0 | fails at edge 3 |
| (e) | 0 | 1 | 1 | 1 | fails at edge 4 |
So (c). It is the busy, rapidly toggling trace, which is the point of the question: a flip-flop ignores everything except the value present at the clock edge, so a wildly active input can produce a placid output.
Trace (e) is the near miss — it is right for the first three edges and only falls too late, just after the fourth rising edge, so \(Q\) would have stayed high.
Q13 — Two’s complement addition
What is the result of adding the 6-bit two’s complement numbers 101010 and 110011?
011100
011101
011110
111011
None of the above
TipAnswer
(b)
Add the bit patterns as if they were unsigned — two’s complement addition is ordinary binary addition — and throw away any carry out of the top bit:
\[ \begin{array}{r} \texttt{\ 101010} \\ + \texttt{110011} \\ \hline \texttt{1011101} \end{array} \]
Column by column from the right: \(0+1 = 1\); \(1+1 = 10\) so write 0 carry 1; \(0+0+1 = 1\); \(1+0 = 1\); \(0+1 = 1\); \(1+1 = 10\) so write 0 and carry 1 out of the word. Six bits of result: 011101.
As a decimal check, \(101010 = -32+8+2 = -22\) and \(110011 = -32+16+2+1 = -13\), so the true sum is \(-35\). That is outside the 6-bit two’s complement range \([-32, 31]\), so this addition overflows — two negatives producing a positive-looking \(011101 = +29\), and indeed \(-35 + 64 = 29\). The question only asks what the adder produces, though, and that is 011101.
Option (d) is what you get by ORing the two operands rather than adding them.
Q14 — Detecting overflow
Which of the following operations will result in an overflow in 5-bit two’s complement arithmetic?
01010 – 01110
10111 – 11100
11010 – 00111
01011 + 11111
None of the above
TipAnswer
(e)
Two’s complement overflow can only happen when the two values being added have the same sign and the result comes out with the other sign. A subtraction \(P - Q\) is really \(P + (-Q)\), so what matters is the sign of \(P\) and of \(-Q\). The 5-bit range is \([-16, +15]\).
Take each in turn, converting to decimal and also checking the sign rule.
(a) 01010 – 01110 \(= 10 - 14 = -4\). Adding a positive to a negative can never overflow, and \(-4\) is in range. In binary: \(01010 + 10010 = 11100 = -4\). ✓ No overflow.
(b) 10111 – 11100 \(= -9 - (-4) = -5\). Again opposite signs going into the adder (\(-9\) and \(+4\)). \(10111 + 00100 = 11011 = -5\). ✓ No overflow.
(c) 11010 – 00111 \(= -6 - 7 = -13\). Here both addends are negative (\(-6\) and \(-7\)), so overflow is possible — but \(-13\) still fits in \([-16,15]\). \(11010 + 11001 = 1\,10011\); discard the carry out and \(10011 = -13\), which is negative as expected. ✓ No overflow.
(d) 01011 + 11111 \(= 11 + (-1) = 10\). Opposite signs. \(01011 + 11111 = 1\,01010\); discard the carry and \(01010 = 10\). ✓ No overflow.
Note that (d) is a good reminder that a carry out is not overflow — the carry out of the top bit here is 1, yet the answer is perfectly correct. None of the four overflows, so the answer is (e).
Q15 — Overflow on an addition
Consider the binary addition operation 010111 + 001001. Which of the following statements is true if the numbers are interpreted as two’s complement?
The result is positive and no overflow occurs
The result should be positive but overflow occurs
The result is negative and no overflow occurs
The result should be negative but overflow occurs
The result is zero
TipAnswer
(b)
Both operands have a 0 in the sign position, so both are positive: \(010111 = 16+4+2+1 = 23\) and \(001001 = 8+1 = 9\). The true sum is \(32\), and the 6-bit two’s complement range is only \([-32, +31]\) — so \(32\) does not fit.
Doing the addition:
\[ \begin{array}{r} \texttt{010111} \\ + \texttt{001001} \\ \hline \texttt{100000} \end{array} \]
The result pattern \(100000\) has a 1 in the sign position, so the adder is reporting \(-32\). Two positives producing a negative is the definition of two’s complement overflow, which makes (b) the right description: the result should have been positive, but overflow occurred.
Note that no carry came out of the word here, which again shows carry-out and overflow are different things (compare Q14).
Q16 — Multiplexer as function generator
Consider the following multiplexer. What must the inputs A,B,C,D be so that the multiplexer implements the function \(X = S_1 \oplus S_0 \oplus \overline{G}\) ?
Figure 63: Question 16’s 4-to-1 multiplexer: data inputs A, B, C and D on lines 0 to 3, select inputs S1 and S0, output X.
A= 0 B= 1 C= 1 D= 0
A= \(G\) B= \(\overline{G}\) C= \(\overline{G}\) D= \(G\)
A= \(\overline{G}\) B= 1 C= 1 D= 1
A= \(\overline{G}\) B= \(G\) C= \(G\) D= \(\overline{G}\)
None of the above
TipAnswer
(d)
A multiplexer used this way is a lookup table: whatever is wired to input \(n\) appears at \(X\) whenever the select lines hold \(n\). So for each of the four values of \(S_1 S_0\), evaluate the required function and wire that expression to the matching input (see combinational-logic-blocks).
\[X = S_1 \oplus S_0 \oplus \overline{G}\]
| \(S_1 S_0\) | Input selected | \(S_1 \oplus S_0\) | Required \(X = (S_1 \oplus S_0) \oplus \overline{G}\) |
|---|---|---|---|
| 00 | A | 0 | \(0 \oplus \overline{G} = \overline{G}\) |
| 01 | B | 1 | \(1 \oplus \overline{G} = G\) |
| 10 | C | 1 | \(1 \oplus \overline{G} = G\) |
| 11 | D | 0 | \(0 \oplus \overline{G} = \overline{G}\) |
using \(0 \oplus P = P\) and \(1 \oplus P = \overline{P}\). So \(A = \overline{G}\), \(B = G\), \(C = G\), \(D = \overline{G}\) — option (d).
Option (b) is the same pattern inverted throughout, which is what you get by dropping the bar on \(G\) in the target function.
Q17 — Reading an 8-input multiplexer
Consider the following multiplexer. Which of the following statements is TRUE? (+ indicates the logical OR operation)
Figure 64: Question 17’s 8-to-1 multiplexer. The eight data inputs are hardwired to the constants 1, 0, 1, 0, 1, 1, 1, 0 on lines 0 to 7; the select inputs S2, S1 and S0 are driven by A, B and C respectively.
If A is 0, \(X = \overline{C}\) If A is 1, \(X = \overline{B + C}\)
If A is 0, \(X = \overline{B}\) If A is 1, \(X = \overline{B + C}\)
If A is 0, \(X = \overline{C}\) If A is 1, \(X = \overline{B.C}\)
If A is 0, \(X = C\) If A is 1, \(X = \overline{B.C}\)
None of the above
TipAnswer
(c)
\(A\) is the most significant select bit, so it splits the eight constants into two halves: \(A = 0\) selects among inputs 0–3, \(A = 1\) among inputs 4–7. Within each half, \(BC\) picks the row.
With \(A = 0\) the four constants are, for \(BC = 00, 01, 10, 11\):
| \(B\) | \(C\) | Input | Value |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 2 | 1 |
| 1 | 1 | 3 | 0 |
\(X\) is 1 exactly when \(C = 0\), whatever \(B\) does — so \(X = \overline{C}\).
With \(A = 1\) the constants are:
| \(B\) | \(C\) | Input | Value |
|---|---|---|---|
| 0 | 0 | 4 | 1 |
| 0 | 1 | 5 | 1 |
| 1 | 0 | 6 | 1 |
| 1 | 1 | 7 | 0 |
\(X\) is 0 only when \(B\) and \(C\) are both 1 — so \(X = \overline{B.C}\).
Both halves match option (c). Option (a) has the right first half but reads the second half as a NOR rather than a NAND, which would need the last three constants to be 0 rather than just the last one.
Q18 — Load/shift register trace
Consider the circuit below. If A1 is 1 and A0 is 0, what are the values of Q1 and Q0 after four rising clock edges if FN is 0 for one rising clock edge then 1 for three rising clock edges?
Figure 65: Question 18’s circuit: two D flip-flops, each fed by a 2-to-1 multiplexer under the shared select FN. On FN = 0 the flip-flops load A1 and A0; on FN = 1 the left one takes Q0-bar and the right one takes Q1, which makes the pair a twisted-ring counter.
\(Q_1 = 0\) \(Q_0 = 0\)
\(Q_1 = 0\) \(Q_0 = 1\)
\(Q_1 = 1\) \(Q_0 = 0\)
\(Q_1 = 1\) \(Q_0 = 1\)
Insufficient information is provided to determine the values
TipAnswer
(a)
First read the two multiplexers. Both have FN on their select input, so:
\[D_1 = \begin{cases} A_1 & \text{FN} = 0 \\ \overline{Q_0} & \text{FN} = 1\end{cases} \qquad\qquad D_0 = \begin{cases} A_0 & \text{FN} = 0 \\ Q_1 & \text{FN} = 1\end{cases}\]
The \(\overline{Q_0}\) feedback is the long run along the bottom, from the right flip-flop’s \(\overline{Q}\) pin all the way back to the left multiplexer’s input 1. With FN = 1 this is a twisted-ring (Johnson) counter: the pair shifts left-to-right and the complement of the last bit re-enters at the front.
Now trace the four edges. Both flip-flops are clocked together, so both take their new values from the old \(Q\) values at each edge.
| Edge | FN | \(D_1\) | \(D_0\) | New \(Q_1 Q_0\) |
|---|---|---|---|---|
| — | — | — | — | starting value unknown |
| 1 | 0 | \(A_1 = 1\) | \(A_0 = 0\) | 1 0 |
| 2 | 1 | \(\overline{Q_0} = \overline{0} = 1\) | \(Q_1 = 1\) | 1 1 |
| 3 | 1 | \(\overline{Q_0} = \overline{1} = 0\) | \(Q_1 = 1\) | 0 1 |
| 4 | 1 | \(\overline{Q_0} = \overline{1} = 0\) | \(Q_1 = 0\) | 0 0 |
After four edges \(Q_1 = 0\) and \(Q_0 = 0\) — option (a).
Option (e) is the trap: the starting contents of the flip-flops genuinely are unknown, but the first edge is a parallel load that overwrites both of them, so the answer is fully determined from edge 1 onwards.
Q19 — Synchronous counter sequence
What sequence will the following synchronous counter count through, if it starts at Q1Q0 = 00?
Figure 66: Question 19’s synchronous counter. Both gates see the same two feedback lines: Q0 comes back along the upper run and Q1 along the lower one, so D1 is the XOR of the two state bits and D0 their NAND. The source paper draws the XOR mirrored, with its output on the left; it is drawn the usual way round here, and the connections are unchanged.
Q1Q0: 00 → 10 → 01 → 11 → 00 → …
Q1Q0: 00 → 10 → 11 → 00 → …
Q1Q0: 00 → 01 → 10 → 11 → 00 → …
Q1Q0: 00 → 01 → 11 → 00 → …
None of the above
TipAnswer
(d)
Read the excitation equations off the circuit. Both gates take the same pair of inputs — the two state bits fed back — so:
\[D_1 = Q_1 \oplus Q_0 \qquad\qquad D_0 = \overline{Q_1 . Q_0}\]
Now build the state table (see counters):
| \(Q_1 Q_0\) | \(D_1 = Q_1 \oplus Q_0\) | \(D_0 = \overline{Q_1 Q_0}\) | Next state |
|---|---|---|---|
| 00 | 0 | 1 | 01 |
| 01 | 1 | 1 | 11 |
| 11 | 0 | 0 | 00 |
| 10 | 1 | 1 | 11 |
Starting from 00 the counter runs
\[00 \rightarrow 01 \rightarrow 11 \rightarrow 00 \rightarrow \dots\]
a three-state cycle, which is option (d). State 10 is outside the cycle; it drops into 11 on the next edge and joins the loop, so the counter is self-correcting.
The near miss is (b), \(00 \rightarrow 10 \rightarrow 11 \rightarrow 00\): the same three-state cycle with the two bits swapped over, which is what you get if \(Q_1\) and \(Q_0\) are mixed up when reading the circuit.
Q20 — Flip-flops for an output sequence
What is the minimum number of flip-flops needed to implement a state machine whose outputs always go through the sequence: 00001→00011→00111→11000→10000→00000→00001→… ?
3
4
5
6
None of the above
TipAnswer
(a)
The outputs are five bits wide, which is the distractor — it tempts option (c), one flip-flop per output bit. But the flip-flops hold the state, not the output; the output is whatever combinational logic decodes from the state (see state-machines).
So count the states. The sequence visits
\[00001,\ 00011,\ 00111,\ 11000,\ 10000,\ 00000\]
and then repeats. All six patterns are distinct, and because the machine “always” goes through this sequence, each output value identifies exactly one state — six states.
\(N\) flip-flops give \(2^N\) states, so we need the smallest \(N\) with \(2^N \ge 6\):
\[2^2 = 4 < 6 \qquad 2^3 = 8 \ge 6\]
Three flip-flops, option (a). The five output bits are then produced by output logic decoding those three, which is exactly the Moore-machine structure.
Q21 — State diagram to state table
Consider the state diagram below.
Figure 67: Question 21’s state diagram. Each state shows its name above the rule and its X,Y outputs below; the single input is A, and every state has one arrow for A and one for A-bar.
Which of the following is an equivalent state table?
| Current State | Input (A) | Next State | Outputs (X,Y) |
|---|---|---|---|
| S0 | 0 | S0 | 01 |
| S0 | 1 | S1 | 01 |
| S1 | 0 | S2 | 01 |
| S1 | 1 | S1 | 01 |
| S2 | 0 | S3 | 00 |
| S2 | 1 | S4 | 00 |
| S3 | 0 | S0 | 10 |
| S3 | 1 | S1 | 10 |
| S4 | 0 | S0 | 11 |
| S4 | 1 | S3 | 11 |
| Current State | Input (A) | Next State | Outputs (X,Y) |
|---|---|---|---|
| S0 | 0 | S0 | 01 |
| S0 | 1 | S1 | 01 |
| S1 | 0 | S2 | 01 |
| S1 | 1 | S2 | 01 |
| S2 | 0 | S3 | 00 |
| S2 | 1 | S4 | 00 |
| S3 | 0 | S0 | 10 |
| S3 | 1 | S1 | 10 |
| S4 | 0 | S3 | 11 |
| S4 | 1 | S0 | 11 |
| Current State | Next State (A=0) | Next State (A=1) | Outputs (X,Y) |
|---|---|---|---|
| S0 | S0 | S1 | 01 |
| S1 | S2 | S1 | 01 |
| S2 | S3 | S4 | 00 |
| S3 | S0 | S1 | 10 |
| S4 | S3 | S0 | 11 |
| Current State | Next State (A=0) | Next State (A=1) | Outputs (X,Y) |
|---|---|---|---|
| S0 | S0 | S1 | 01 |
| S1 | S2 | S1 | 10 |
| S2 | S3 | S4 | 00 |
| S3 | S0 | S1 | 10 |
| S4 | S3 | S0 | 11 |
- None of the above
TipAnswer
(c)
Read the ten arrows off the diagram, remembering that a label \(A\) means the transition is taken when \(A = 1\) and \(\overline{A}\) when \(A = 0\), and that this is a Moore machine so the outputs belong to the state, not the transition (see state-machines).
| Current state | \(A = 0\) | \(A = 1\) | Outputs \(X,Y\) |
|---|---|---|---|
| \(S_0\) | \(S_0\) (self loop, \(\overline{A}\)) | \(S_1\) (top arc, \(A\)) | 01 |
| \(S_1\) | \(S_2\) (down the right, \(\overline{A}\)) | \(S_1\) (self loop, \(A\)) | 01 |
| \(S_2\) | \(S_3\) (\(\overline{A}\)) | \(S_4\) (bottom arc, \(A\)) | 00 |
| \(S_3\) | \(S_0\) (\(\overline{A}\)) | \(S_1\) (\(A\)) | 10 |
| \(S_4\) | \(S_3\) (\(\overline{A}\)) | \(S_0\) (\(A\)) | 11 |
Each state has exactly two arrows leaving it, one per value of \(A\), so the diagram is complete. This table is option (c) exactly.
The other three each differ in one place:
- (a) swaps \(S_4\)’s two destinations — it has \(S_4 \to S_0\) on \(A=0\) and \(S_4 \to S_3\) on \(A=1\), the wrong way round.
- (b) sends \(S_1\) to \(S_2\) on both input values, losing \(S_1\)’s self loop.
- (d) is (c) with \(S_1\)’s output changed from 01 to 10.
Q22 — Flip-flops for a state machine
What is the minimum number of flip-flops needed to build the state machine shown in question 21?
1
2
3
4
5
TipAnswer
(c)
The diagram in Q21 has five states: \(S_0\), \(S_1\), \(S_2\), \(S_3\) and \(S_4\). With \(N\) flip-flops there are \(2^N\) possible codes, so we need the smallest \(N\) with \(2^N \ge 5\):
\[2^2 = 4 < 5 \qquad 2^3 = 8 \ge 5\]
so three flip-flops, with three of the eight codes left unused.
Option (e), five, is the one-hot encoding — legal and often convenient, but not the minimum. Option (b), two, would only stretch to four states.
Q23 — Tracing a state machine
Consider the state machine represented by the state diagram in question 21 above. What sequence of states is traversed if the machine starts in state S3 and A goes through the sequence 10001 (i.e. 1 followed by three 0s followed by a 1)?
S3→S0→S0→S0→S0→S1
S3→S1→S2→S3→S0→S1
S3→S1→S2→S4→S3→S1
S3→S0→S1→S2→S3→S1
None of the above
TipAnswer
(b)
Walk the table from Q21 one input bit at a time, starting in \(S_3\):
| Step | Current state | \(A\) | Next state |
|---|---|---|---|
| 1 | \(S_3\) | 1 | \(S_1\) |
| 2 | \(S_1\) | 0 | \(S_2\) |
| 3 | \(S_2\) | 0 | \(S_3\) |
| 4 | \(S_3\) | 0 | \(S_0\) |
| 5 | \(S_0\) | 1 | \(S_1\) |
so the machine visits
\[S_3 \rightarrow S_1 \rightarrow S_2 \rightarrow S_3 \rightarrow S_0 \rightarrow S_1\]
which is option (b).
Option (c) goes wrong at step 3 by taking \(S_2\)’s \(A = 1\) arrow instead of its \(A = 0\) one; option (a) takes \(S_3\)’s \(\overline{A}\) arrow on the first bit, which is 1.
Q24 — ALU control settings
Consider the ALU bit slice below.
Figure 68: Question 24’s ALU bit slice. The ENA/INVA and ENB/INVB gates on the left condition A and B into the two internal rails X and Y; the five logic blocks and the full adder all work from those rails, and the 8-input multiplexer under F2 F1 F0 picks which result reaches the output. Right Shift Out is the X rail itself. The carry logic at the bottom points downwards as in the source: an AND on the two rails for the generate term, and a five-input AND for the propagate term, whose extra three inputs are F2, F1 and F0 — so a carry only travels when the adder is the selected function.
For an ALU made up of 8 of the bit slices above, which of the following control input settings will NOT result in the ALU output being \(\overline{B}\) ? (The “Right Shift In” control input refers to that for the most significant bit; the “Carry in” control input refers to that for the least significant bit.)
ENA=0 INVA=0 ENB=1 INVB=0 F2=0 F1=1 F0=1 Right Shift In=0 Carry in=0
ENA=0 INVA=0 ENB=1 INVB=1 F2=0 F1=0 F0=1 Right Shift In=0 Carry in=0
ENA=0 INVA=1 ENB=1 INVB=0 F2=0 F1=1 F0=0 Right Shift In=0 Carry in=0
ENA=0 INVA=1 ENB=1 INVB=1 F2=0 F1=0 F0=0 Right Shift In=0 Carry in=0
All of the above result in the ALU output being \(\overline{B}\)
TipAnswer
(e)
Start by writing down what the slice actually computes. The conditioning gates give the two internal rails
\[X = (A \cdot \text{ENA}) \oplus \text{INVA} \qquad\qquad Y = (B \cdot \text{ENB}) \oplus \text{INVB}\]
and the multiplexer, selected by \(F_2 F_1 F_0\) read as a binary number, chooses between:
| \(F_2 F_1 F_0\) | Input | Output |
|---|---|---|
| 000 | 0 | \(X . Y\) |
| 001 | 1 | \(X + Y\) |
| 010 | 2 | \(\overline{X . Y}\) |
| 011 | 3 | \(\overline{X + Y}\) |
| 100 | 4 | Carry In |
| 101 | 5 | \(\overline{X}\) |
| 110 | 6 | Right Shift In |
| 111 | 7 | \(X \oplus Y \oplus C_{in}\) (the adder’s sum) |
Every option here has \(\text{ENB} = 1\), so \(Y\) is \(B\) or \(\overline{B}\); and every option has \(\text{ENA} = 0\), so \(X\) is a constant — 0 when \(\text{INVA} = 0\) and 1 when \(\text{INVA} = 1\). Feeding a constant into one side of a two-input gate is exactly how this ALU turns a logic block into a pass-through or an inverter.
(a) \(X = 0\), \(Y = B\), select 011 = NOR: \(\overline{0 + B} = \overline{B}\). ✓
(b) \(X = 0\), \(Y = \overline{B}\), select 001 = OR: \(0 + \overline{B} = \overline{B}\). ✓
(c) \(X = 1\), \(Y = B\), select 010 = NAND: \(\overline{1 \cdot B} = \overline{B}\). ✓
(d) \(X = 1\), \(Y = \overline{B}\), select 000 = AND: \(1 \cdot \overline{B} = \overline{B}\). ✓
All four produce \(\overline{B}\), so the answer is (e). Note that none of them selects input 4, 6 or 7, which is why the Right Shift In and Carry In settings never matter — they are there to make the options look longer than they are.
The paper does not label which select pin of the multiplexer carries which weight, but two things settle it. First, the figure routes \(F_2\) to the leftmost of the three select pins and \(F_0\) to the rightmost, and everywhere else in this paper — the multiplexers in Q16 and Q17 — the leftmost select pin is the most significant (\(S_1\) then \(S_0\); \(S_2\) then \(S_1\) then \(S_0\)). Second, reading \(F_2\) as the most significant bit is what makes all four settings land on \(\overline{B}\); any other assignment sends at least one of them to the Carry In or Right Shift In input instead, which would give a question with three wrong answers rather than none.
The four settings are the four ways of getting \(\overline{B}\) out of the four two-input logic blocks: complement the function (NOR/NAND) or complement the operand (\(\text{INVB}\)), and choose the constant that makes the other input transparent.
Q25 — ALU control settings
For the ALU in question 24, which of the following control input settings will result in the ALU output being \(A.B\)?
ENA=1 INVA=0 ENB=1 INVB=0 F2=0 F1=0 F0=1 Right Shift In=0 Carry in=0
ENA=1 INVA=0 ENB=1 INVB=0 F2=0 F1=1 F0=0 Right Shift In=0 Carry in=0
ENA=1 INVA=0 ENB=1 INVB=0 F2=0 F1=1 F0=1 Right Shift In=0 Carry in=0
ENA=1 INVA=1 ENB=1 INVB=1 F2=0 F1=1 F0=1 Right Shift In=0 Carry in=0
None of the above
TipAnswer
(d)
Same slice as Q24, same two steps: work out \(X\) and \(Y\), then look up what \(F_2 F_1 F_0\) selects.
(a) \(\text{ENA} = \text{ENB} = 1\) with both INV inputs 0, so \(X = A\) and \(Y = B\). Select \(001 = 1\) is the OR block: \(A + B\). ✗
(b) Same \(X\) and \(Y\); select \(010 = 2\) is the NAND block: \(\overline{A.B}\). ✗ — the complement of what is wanted, which is the tempting wrong answer.
(c) Same \(X\) and \(Y\); select \(011 = 3\) is the NOR block: \(\overline{A + B}\). ✗
(d) \(\text{INVA} = \text{INVB} = 1\), so \(X = \overline{A}\) and \(Y = \overline{B}\); select \(011 = 3\) is the NOR block:
\[\overline{\overline{A} + \overline{B}} = \overline{\overline{A}} \cdot \overline{\overline{B}} = A . B\]
by De Morgan. ✓
So (d) — the slice has no AND-with-uncomplemented-inputs route selected here, and instead reaches \(A.B\) the De Morgan way, by inverting both operands into a NOR. Selecting the AND block (000) with \(\text{INVA} = \text{INVB} = 0\) would have done it directly, but that combination is not on the list.
Your score
Reload the page to clear your answers.
Instruction Set Architecture
The layer where software meets hardware: what a machine instruction is, what an ISA specifies, and why assembly language exists. See cpu-organisation for the hardware below this line and avr-instructions for a real instruction set.
Machine instructions
A machine instruction is a pattern of bits. 0000 1101 0111 0111 is a valid Atmel AVR instruction. Instructions typically consist of two things:
- Opcode (operation code) — defines the operation, e.g. addition.
- Operands — what is being operated on, e.g. particular registers or a memory address.
So one word of machine code says what to do and what to do it to, packed into fixed bit fields. Which bits mean which is entirely a matter of convention — and that convention is the ISA.
The ISA
An Instruction Set Architecture is a specification — i.e. a document. It specifies the interface between hardware and software.
Figure 69: The ISA as an interface. Software above the line is written and compiled without knowing how the hardware works; hardware below the line is designed without knowing what program will run. The only thing both sides must agree on is which bit patterns mean what — and that agreement is a document, not a circuit.
The point of drawing it as a line is that the ISA is the only thing the two sides have to agree on. A compiler writer needs the ISA and nothing else about the chip; a chip designer needs the ISA and nothing else about the programs that will run.
Microarchitecture
Microarchitecture = the architecture of the control unit — i.e. the state machine (gates and flip-flops etc.) that implements the control unit.
This is the same state-machines material from earlier in the course, applied at the scale of a whole processor: the control unit is a state machine whose job is to emit the right control signals, in the right order, for whatever the instruction register holds.
ISA vs microarchitecture
One ISA can be implemented by many different microarchitectures. The specification says what the bit patterns mean; it does not say how a chip must go about honouring them.
| ISA | Implemented by |
|---|---|
| 8086 | many processors, in different ways |
| Pentium | Pentium … Pentium IV … Core2Duo … i7 (each in different ways), various AMD devices, and other manufacturers |
This is why a program compiled decades ago still runs: the ISA held still while the microarchitecture beneath it was rebuilt many times over.
What makes an ISA?
Four things:
- Memory models
- Registers
- Instructions
- Data types
If you know all these details, you can write machine code that runs on the CPU and build the CPU.
This is the completeness test for a specification: both sides of the line in Figure 69 have to be constructible from the document alone, and nothing else about the chip may be needed by either.
1. Memory models
How does memory look to the CPU? Four issues decide it — addressable cell size, alignment, address spaces and endianness — treated in full in memory-models.
2. Registers
Two types of register:
- General purpose — used for temporary results etc. On AVR, r0–r31.
- Special purpose, e.g.
- Program Counter (PC)
- Stack pointer (SP)
- Input/Output registers — 224 of them on the ATmega324A, see avr-io-ports
- Status register — N, Z, C, V among others. Tanenbaum calls this the Program Status Word.
Some other registers are part of the microarchitecture, NOT the ISA — e.g. the Instruction Register (IR). The programmer doesn’t need to know about these, and can’t directly change or use them.
That distinction is the cleanest illustration of what an ISA actually is. The IR unquestionably exists and holds the instruction being executed (fetch-decode-execute-cycle) — but no instruction names it, so it is invisible to software and a chip designer is free to change or remove it. The PC is the opposite case: jmp writes it, so it has to be in the specification. Existing in the hardware is not the criterion; being reachable from an instruction is.
Figure 70: The same interface line as in the previous figure, with the machine’s registers sorted across it. The five above the line are part of the ISA; four of them carry an example of an instruction that names the register, and the SP box carries none. The single box below, the IR, is part of the microarchitecture only. Nothing about a register’s size or importance decides which side it lands on — only whether some instruction can refer to it.
The AVR’s own answer to this pillar — the regularity of r0–r31, the r16–r31 exception, and the X/Y/Z pointer pairs — is in avr-architecture.
3. Instructions
This is the main feature of an ISA. Instruction types include:
| Type | Does |
|---|---|
| Input/Output | communicate with I/O devices/ports |
| Load/Store | move data from/to memory |
| Move | copy data between registers |
| Arithmetic | addition, subtraction, … |
| Logical | Boolean operations |
| Branching | for deciding which instruction to perform next |
The Input/Output row is the one where the AVR’s answer is least obvious. The ATmega324A’s 224 I/O registers are all reachable by ld/st at their data-memory addresses 32 to 255 ($20 to $FF), but only the first 64 also get the short in rd, P / out P, rr form that names an I/O register by its own number P — because P is a six-bit field and \(2^6 = 64\). The other 160, the “extended” I/O registers, can only be reached the long way. The mechanics, the numbering offset and the register list are in avr-io-ports.
With arithmetic and logical merged, the same set can be cut the other way instead — by how many operands an instruction takes:
- Dyadic — two operands, one result
- Monadic — one operand, one result
And instructions use various addressing modes: how an operand says where its value is, covered in addressing-modes.
The AVR instructions met so far, sorted into these boxes, are in avr-instructions.
4. Data types
Numeric
- Integers of different lengths (8, 16, 32, 64 bits), possibly signed or unsigned
- Floating point numbers, e.g. 32 bits (single precision) or 64 bits (double precision)
- Many others not listed
Non-numeric
- Boolean (0 means false, 1 means true) — stored in a whole byte or word
- Bit-map (collection of Booleans, e.g. 8 in a byte)
- Characters
- Pointers (memory addresses)
Different machines provide hardware support for different data types. Two ends of the range:
Intel-64 Architecture
| Data type | 8 bits | 16 bits | 32 bits | 64 bits | 128 bits |
|---|---|---|---|---|---|
| Signed integer | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | |
| Unsigned integer | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | |
| BCD integer | \(\checkmark\) | ||||
| Floating point | \(\checkmark\) | \(\checkmark\) |
Atmel AVR
| Data type | 8 bits | 16 bits | 32 bits | 64 bits | 128 bits |
|---|---|---|---|---|---|
| Signed integer | \(\checkmark\) | ||||
| Unsigned integer | \(\checkmark\) | ||||
| BCD integer | |||||
| Floating point |
The only data type an AVR supports in hardware is an 8-bit integer, signed or unsigned. There is no 16-bit integer type, no floating point, no BCD.
Other data types can be supported through software! e.g. 16-bit integer operations can be built out of 8-bit operations, using a sequence of instructions — which is exactly what the two-instruction 16-bit addition in avr-instructions does. So the hardware/software line here is about cost, not possibility: anything missing from the table can still be computed, it just takes more instructions and more cycles. Floating point is the costly case: one float multiply is hundreds of instructions (floating-point-numbers), which is why fractions on the AVR are usually kept as fixed-point-numbers.
Assembly language
Machine code is too hard to program in. Assembly language is used instead:
- Human readable (just!).
- Converted into machine code by software called an assembler.
Two Atmel AVR examples:
| Assembly | Meaning |
|---|---|
add r3,r4 |
r3 ← r3 + r4 |
inc r22 |
r22 ← r22 + 1 |
The important structural detail is in the arrows of Figure 69: a high-level language compiles one-to-many — one line of C becomes however many instructions it takes — whereas assembly assembles one-to-one. Each assembly instruction is one machine instruction, written in a form a person can read. That is the whole of what an assembler buys you, and it is why assembly is still “programming the machine” in a way C is not.
The toolchain
For CSSE2010 the assembler is Microchip Studio, and two supplied tutorials walk through it end to end: Intro to Microchip Studio (create an assembler project, pick the device, edit, build, and step through the simulator) and Microchip Studio C Tutorial (the same for a GCC C project). Both are click-through guides to follow at the machine rather than material to learn — they are on Blackboard, and the labs are where they get used.
See also
- memory-models · addressing-modes — pillars 1 and 3, in full
- cpu-organisation · fetch-decode-execute-cycle · state-machines
- avr-architecture · avr-instructions · avr-io-ports · avr-program-structure
- assembly-process — what the assembler does besides translating: directives, segments and two passes · compilation-and-linking — the compiler’s one-to-many road, through object files and the linker
- 2026-08-27-avr-introduction — Lecture 10
- 2026-08-31-instruction-set-architecture-part-1 — Lecture 11
- 2026-09-03-instruction-set-architecture-part-2 — Lecture 12
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).
Gates sit at the bottom of the abstraction stack — the digital logic level, level 0 (see 2026-07-27-course-intro-bits-bytes-binary). A digital circuit only ever carries two logic levels: logic ‘0’ is usually a small voltage (around 0 V) and logic ‘1’ a larger one (e.g. 0.8 V to 5 V, depending on the logic family — the type and size of the transistors the gate is built from). Because inputs and outputs have only these two states, they can equivalently be called true and false.
The 7 basic gate types
Figure 71: The seven basic gates, with the distinguishing symbol and Boolean expression for each. NOT, AND and OR are the three base shapes; NAND, NOR and XNOR are those same bodies with an inversion bubble on the output, and XOR/XNOR add a second arc across the back of the OR body.
| Gate | Behaviour | Truth table (\(A,B \to X\)) |
|---|---|---|
| NOT (inverter) | Inverts the input | 0→1, 1→0 |
| AND | Output is HIGH when all inputs are HIGH | 00→0, 01→0, 10→0, 11→1 |
| OR | Output is HIGH when at least one input is HIGH | 00→0, 01→1, 10→1, 11→1 |
| NAND | Output is HIGH when at least one input is LOW | 00→1, 01→1, 10→1, 11→0 |
| NOR | Output is HIGH when all inputs are LOW | 00→1, 01→0, 10→0, 11→0 |
| XOR | Output is HIGH when exactly one input is HIGH | 00→0, 01→1, 10→1, 11→0 |
| XNOR | Output is HIGH when the inputs are the same | 00→1, 01→0, 10→0, 11→1 |
Useful to remember: XOR is the odd function, XNOR is the even function.
Deriving the inverting gates from the base gates
The quickest way to fill in a NAND/NOR/XNOR truth table is not to memorise it, but to write the underlying AND/OR/XOR column first and then invert it row by row — the “N” prefix is exactly one inversion on the output:
| \(A\) | \(B\) | AND | NAND | OR | NOR | XOR | XNOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
More than two inputs
A gate of \(n\) inputs has a truth table of \(2^n\) rows — two inputs give \(2 \times 2 = 4\) rows, three inputs give 8. The “at least one / all” wordings above carry over unchanged to more inputs; the XOR/XNOR wordings do not, and must be restated in terms of parity:
- XOR output is HIGH when an odd number of inputs are HIGH (the odd function). For two inputs this collapses to “exactly one”, which is why the 2-input wording works.
- XNOR output is HIGH when an even number of inputs are HIGH (the even function).
| \(A\) | \(B\) | \(C\) | 3-input AND | 3-input NAND | 3-input XOR |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 |
Note that the kit of parts used for practicals has no 3-or-more-input gate chips (see device-pinouts) — a 3-input function has to be built from 2-input gates.
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:
Figure 72: Why NAND and NOR are complete gates: NOT, AND and OR built from each one alone. Tying both inputs of a NAND or NOR together turns it into an inverter, and everything else follows — AND is NAND then invert, OR is invert-both-inputs then NAND (and the NOR row is the mirror image of that).
- NOT: a NAND (or NOR) gate with both inputs tied together — \(\overline{A \cdot A} = \bar A\), and \(\overline{A + A} = \bar A\).
- AND from NAND: a NAND followed by a second NAND wired as an inverter. AND from NOR: invert both inputs first, then NOR them (\(\overline{\bar A + \bar B} = AB\), by De Morgan — see boolean-algebra).
- OR from NOR: a NOR followed by a NOR-as-inverter. OR from NAND: invert both inputs first, then NAND them (\(\overline{\bar A \cdot \bar B} = A+B\)).
The two rows are De Morgan’s law drawn twice: whenever you push an inversion through a gate, AND and OR swap. NAND and NOR are preferred in practice because they are easier to build from transistors than AND/OR directly.
Gates on ICs
Gates are sold packaged several to an integrated circuit (IC). The 74HCT00 is four independent 2-input NAND gates in one 14-pin DIP package.
Figure 73: Inside the 74HCT00: four independent 2-input NAND gates in a 14-pin package, with the pin each gate terminal is wired to. Pin 14 is Vcc (power, e.g. 5 V) and pin 7 is GND (0 V) — shared by all four gates, so nothing works if either is left unconnected. Gate letters A-D are the labels a schematic uses as U1:A … U1:D.
- Vcc = power (e.g. 5 V), GND = ground (0 V). One Vcc/GND pair supplies all four gates.
- Physically: pin spacing is 0.1” along the package and 0.3” across it; the chip is about 15 mm long.
- The drawing above is the chip’s internal schematic, not a picture of the part — see circuit-schematics for how a chip like this is drawn (and labelled
U1:A…U1:D) on a schematic you can actually build from, and device-pinouts for the pinouts of every chip in the course kit.
Memory Technologies
The kinds of memory a computer is built from, and how big they are. This note covers why a computer needs memory at all, the five ways memory is classified and where SRAM, DRAM, ROM, flash, SSDs and hard disks fall on each, how a static cell differs from a dynamic one, what “RAM” means now, the ROM family from ROM to flash, the ATmega324A’s three memories, the generations of DRAM, and the units capacity is quoted in, where “1 MB” can mean three different numbers. How these memories are arranged by speed is in memory-hierarchy-and-cache, and disks and files are in magnetic-disks and file-systems. First met in 2026-10-22-memory-disks-and-files.
Why a computer needs memory
A processor on its own holds a few dozen registers. Everything else has to live somewhere, and there are three distinct jobs:
- Temporary results. Intermediate values, variables, the stack: things a running program needs for a while and then discards.
- Programs. The instructions themselves have to be stored somewhere the processor can fetch them from (fetch-decode-execute-cycle).
- Settings that survive power-off. A calibration constant, a high score, the last channel a TV was on. These must still be there when the power comes back.
The first job wants memory that is fast and can be rewritten endlessly. The third wants memory that keeps its contents with no power. No single technology is best at all three, which is why there are many types.
Five ways to classify memory
Each axis asks one question about a memory.
| Axis | The question | The two answers |
|---|---|---|
| Access | Can any cell be reached directly, in the same time? | random access: the address selects the cell directly. Sequential access: the data has to be passed over in order to reach a cell, like a tape |
| Static or dynamic | Does a stored bit stay put by itself while powered? | static: held by a flip-flop or latch. Dynamic: held as charge that leaks away and must be refreshed |
| Volatility | Does it keep its contents when the power is off? | volatile: forgets. Non-volatile: remembers |
| Read-only | Can the processor write it in normal use? | read/write, or read-only (written once, or only by a special process) |
| Primary or secondary | Does the processor address it directly? | primary: on the processor’s address bus, holding the running program and its data. Secondary: reached through I/O, holding files |
Random access is what an address decoder gives you. In the gate-level memory of memory-models, the address bits drive a decoder that selects exactly one row, and it takes the same time whichever row it is. A tape has to wind past everything in front of the data first.
Where the common technologies fall:
Figure 74: Six memory technologies against the five ways of classifying memory. Each row is one technology and each column one axis; a filled dot means the left-hand answer in the column heading, an open circle the right-hand one. SRAM and DRAM are both random-access, volatile, read/write primary memory, and differ only in being static or dynamic. ROM and flash are non-volatile; ROM is read-only, while flash is rewritten electrically, in blocks. SSDs (built from flash) and hard disks are secondary storage, reached through I/O rather than the address bus. All six are random access, in that any location can be reached directly by its address; the sequential case is tape. A hard disk’s access time does still depend on where the data is, because it must wait for the head to move and the disk to turn. The static/dynamic distinction only applies to the semiconductor RAMs, so it is left blank for the rest.
Two entries need a word. Flash is used both as primary memory (the program memory of a microcontroller like the AVR, which the processor fetches instructions from directly) and, packaged as an SSD, as secondary storage. And a hard disk counts as random access (sometimes called direct access) because the head can go straight to any track without reading what lies in between, unlike a tape. Reaching a sector still means moving the head and waiting for the sector to rotate underneath, though, so unlike a memory chip its access time depends on where the data is (magnetic-disks).
Static and dynamic memory
Static memory (SRAM) stores each bit in a flip-flop or latch: a loop of gates that holds its state for as long as the power is on (flip-flops-and-latches). Nothing needs doing to keep the bit. A typical cell is two cross-coupled inverters plus two switches to connect it to the bit lines, about six transistors per bit, so SRAM is fast but expensive per bit.
Dynamic memory (DRAM) stores each bit as charge on a capacitor, with a transistor as a switch that connects the capacitor to its bit line when the row is selected. One transistor and one capacitor per bit is far smaller than a flip-flop, so many more bits fit on a chip and each costs less. The price is that the charge leaks away. A DRAM cell forgets its contents within milliseconds unless it is refreshed, meaning read and written back, which the memory does to every row every few tens of milliseconds (of the order of 20 ms). Reading is slower too, because the small charge has to be sensed and amplified.
Figure 75: One bit of static and one bit of dynamic memory. Left: the static cell is two inverters in a loop. Whatever value sits at one side, the other inverter feeds its complement back, so the pair holds the bit for as long as there is power. Raising the word line closes both switches and connects the two sides to the bit line and its complement, for reading or writing. Right: the dynamic cell is a single switch (a transistor) and a capacitor. Raising the word line connects the capacitor to the bit line; a charged capacitor is a 1 and an empty one a 0. The charge leaks away through the switch, so the cell has to be read and rewritten, refreshed, every few tens of milliseconds.
| SRAM | DRAM | |
|---|---|---|
| Bit stored in | a flip-flop or latch | charge on a capacitor, behind a transistor switch |
| Keeps its bit while powered? | yes | only if refreshed every few tens of ms |
| Cell size | large (about six transistors) | small (one transistor, one capacitor) |
| Bits per chip | fewer | many more |
| Speed | faster | slower |
| Cost per bit | high | low |
| Volatile? | yes | yes |
| Typical use | registers, cache, small microcontroller RAM (the ATmega324A’s 2 kB) | a computer’s main memory |
What “RAM” means
RAM stands for random access memory. Originally that meant exactly the first axis above: any cell can be accessed directly, as opposed to sequential access. By that definition ROM and flash are random access too.
In current use “RAM” means volatile read/write memory, and SRAM and DRAM are the two kinds. So “RAM” and “ROM” are treated as opposites even though the original meaning of RAM covers both.
Volatile and non-volatile memory
Volatile memory forgets its contents when the power goes off. Both SRAM and DRAM are volatile. DRAM is volatile even with the power on, in the sense that it forgets within milliseconds if it is not refreshed.
Non-volatile memory remembers its contents with the power off. There are several kinds, and they differ in how, and how easily, they can be rewritten. Hard disks and optical disks are non-volatile too, but they are secondary storage; the next section is about non-volatile chips.
From ROM to flash
- ROM, read-only memory. The contents are hardwired into the silicon by the chip’s manufacturer. They can never be changed.
- EPROM, erasable programmable ROM. Programmed electrically by the user, and erased by ultraviolet light. An EPROM package has a small quartz window over the die. Shining a UV lamp through it for some minutes erases the whole chip, which can then be programmed again.
- EEPROM, electrically erasable PROM. Erased by applying a certain voltage, so it can be erased and rewritten in the circuit, with no lamp, one cell (byte) at a time.
- Flash. A newer form of EEPROM. The two used to be different technologies and have been converging. The main difference that remains is that flash is written and erased in blocks, where EEPROM is written and erased one cell at a time. Erasing a large block at once is what makes flash dense and cheap, and it is why flash holds programs and files while EEPROM holds a few bytes of settings that change one at a time.
Figure 76: The family of non-volatile memory chips, from least to most easily rewritten. Each step keeps the contents with the power off and changes how they are erased. ROM cannot be erased at all: the bits are fixed when the chip is made. An EPROM is erased whole, by ultraviolet light shining through a window in the package. An EEPROM is erased electrically, in the circuit, a single cell at a time. Flash is erased electrically too, but a block of many cells at a time, which is what lets it be so dense.
The ATmega324A’s three memories
The ATmega324A has one of each of the three common kinds on the chip, and each is a separate address space with its own assembler segment (memory-models, assembly-process).
| Memory | Technology | Size | Holds | Volatile? | Assembler segment |
|---|---|---|---|---|---|
| Flash | flash (block-erased EEPROM) | 32 kB, as 16-bit words | the program and constant tables | no | .cseg |
| SRAM | static RAM | 2 kB | variables, the stack, the heap | yes | .dseg |
| EEPROM | EEPROM (cell-erased) | 1 kB | settings that must survive power-off | no | .eseg |
The flash is divided into two blocks: an application section, where the program normally lives, and a boot loader section at the top of program memory. A boot loader is a small program that can receive a new program, over a serial link for instance, and write it into the application section. Because flash is erased a block at a time, having the program in a separate block from the boot loader means the application can be erased and rewritten while the boot loader that is doing the rewriting stays intact. Other AVR devices have one flash block, and some have more.
Figure 77: The ATmega324A’s three memories as technologies: what each holds, the unit it is erased or written in (dark), and whether it survives power-off. Flash holds the program and keeps it with the power off, but it can only be erased a block at a time, so it is split into two blocks: a boot loader in the small block can erase and rewrite the program in the large one without erasing itself. SRAM holds the variables and the stack; any byte can be written at any time, at full speed, but all of it is lost at power-off. EEPROM keeps its bytes with the power off and, unlike flash, erases and rewrites them one at a time, which suits a few settings that change one by one.
The table is the answer to a common question: which memory should this value go in? Code goes in flash. A variable the program changes goes in SRAM. A value the program changes and that must still be there after a reset goes in EEPROM.
Generations of DRAM
Every DRAM stores bits as charge on a capacitor, not in flip-flops. Its cells are smaller than a static cell, so a chip packs in more bits, and it is slower than static memory. What has changed over the generations is the interface, the way rows and columns are addressed and data is moved out:
| Generation | What it changed |
|---|---|
| FPM DRAM, fast page mode | once a row is open, further columns in that row can be read without re-sending the row |
| EDO DRAM, extended data out | keeps the output valid while the next column address is sent, so successive reads overlap; a refinement of FPM |
| SDRAM, synchronous DRAM | runs from a clock shared with the memory controller, so transfers happen on clock edges and can be pipelined |
| RDRAM, Rambus DRAM | a narrow, very fast proprietary bus |
| DDR SDRAM, double data rate, generations 1 to 5 | transfers data on both the rising and falling clock edges; each generation raises the rate |
| GDDR, graphics DDR, up to GDDR7 | a DDR variant tuned for the bandwidth of graphics cards |
FPM and EDO belong together as the asynchronous generations. SDRAM is the break: from there on, DRAM is clocked, and DDR4 and DDR5 are what current machines use.
Capacity units: powers of 2 or of 10
In SI units, kilo, mega and giga mean powers of 10: \(10^3\), \(10^6\), \(10^9\). In computing they have conventionally, or at least historically, meant the nearest powers of 2: \(2^{10} = 1024\), \(2^{20}\), \(2^{30}\). The two agree to within a few per cent, and the gap grows with every prefix.
| Prefix | Power of 10 | Power of 2 | Power of 2 is larger by |
|---|---|---|---|
| kilo (k) | \(10^3\) = 1,000 | \(2^{10}\) = 1,024 | 2.4 % |
| mega (M) | \(10^6\) = 1,000,000 | \(2^{20}\) = 1,048,576 | 4.86 % |
| giga (G) | \(10^9\) = 1,000,000,000 | \(2^{30}\) = 1,073,741,824 | 7.37 % |
| tera (T) | \(10^{12}\) | \(2^{40}\) = 1,099,511,627,776 | 9.95 % |
The percentages are measured against the power of 10: \((2^{30} - 10^9)/10^9 = 0.0737\).
Figure 78: The decimal and binary meanings of each prefix side by side, on a log scale. Each step up the decimal ladder multiplies by 1000 and each step up the binary ladder by 1024, so the binary value pulls a little further ahead at every step: 2.4 per cent at kilo, 4.86 at mega, 7.37 at giga and almost 10 at tera. That is why the ambiguity is a rounding error for a kilobyte but a real difference for a terabyte disk.
Why main memory comes in powers of 2
A memory chip is addressed by address lines, and \(n\) lines can name exactly \(2^n\) cells: one line selects between 2 cells, two lines between 4, three between 8. A memory that used only 1,000,000 of the 1,048,576 addresses its 20 lines can name would waste the rest, so main memory is built in powers of 2 and its size is quoted that way: a “4 GB” module holds \(4 \times 2^{30}\) bytes.
Figure 79: Why memory sizes are powers of 2. With one address line a decoder can select one of 2 cells, with two lines one of 4, and with three lines one of 8: every extra line doubles the number of cells that can be named. So n address lines give exactly 2 to the n cells, and a memory is built to fill that number.
Which convention is used where
| Context | Convention | Example |
|---|---|---|
| Main memory capacity | always powers of 2 | 1 GB \(= 1024 \times 1024 \times 1024\) B \(= 2^{30}\) B |
| Hard disk capacity, as sold | powers of 10 | 1 GB \(= 1000 \times 1000 \times 1000\) B \(= 10^9\) B |
| Operating systems (e.g. Windows) reporting sizes | powers of 2 | a “500 GB” disk shows as about 465.66 GB |
| Data speeds, transfer rates | usually powers of 10 | 1 Gbps (gigabit per second) \(= 10^9\) bits per second |
| Occasionally, a mixture | one of each | the 1.44 MB floppy disk: \(1.44 \times 1000 \times 1024\) bytes |
Disk makers’ powers of 10 make a disk seem bigger. A disk sold as 500 GB holds \(500 \times 10^9\) bytes, and an operating system that divides by \(2^{30}\) reports \(500 \times 10^9 / 2^{30} = 465.66\) “GB”. Nothing is missing; the two numbers use different gigabytes.
Note the case of the b: B is a byte and b is a bit. 1 Gbps is a rate in bits, so it moves \(10^9 / 8 = 125 \times 10^6\) bytes per second at most.
Binary prefixes: KiB, MiB, GiB
To avoid the confusion, standard names were created for the binary meanings:
| Name | Symbol | Value |
|---|---|---|
| kibibyte | KiB | 1024 bytes |
| mebibyte | MiB | 1024 KiB \(= 2^{20}\) bytes |
| gibibyte | GiB | 1024 MiB \(= 2^{30}\) bytes |
With these, kB, MB and GB can keep their SI meanings. Few people use them, though, and these notes use kilo, mega and giga as everyone does, with the meaning depending on the context. When the difference matters, say which one is meant.
Worked: what is a megabyte, and a gigabyte?
How many bytes is 1 MB? How many is 1 GB? How different are the meanings, and how many bytes does a “1.44 MB” floppy disk hold?
1 MB, three ways.
- Conventionally: \(1\text{ MB} = 2^{10}\text{ kB} = 1024\text{ kB} = 2^{20}\text{ B} = \mathbf{1{,}048{,}576}\) B.
- Sometimes, the SI meaning: \(1\text{ MB} = 10^6\text{ B} = \mathbf{1{,}000{,}000}\) B.
- Or in between, with a decimal mega of binary kilobytes: \(1000\text{ kB} = 1000 \times 1024 = \mathbf{1{,}024{,}000}\) B.
1 GB, three ways.
- Conventionally: \(1\text{ GB} = 2^{10}\text{ MB} = 2^{20}\text{ kB} = 2^{30}\text{ B} = \mathbf{1{,}073{,}741{,}824}\) B.
- Sometimes: \(1\text{ GB} = 10^9\text{ B} = \mathbf{1{,}000{,}000{,}000}\) B.
- Or in between: \(1000 \times 2^{20} = \mathbf{1{,}048{,}576{,}000}\) B, a thousand binary megabytes.
How different. The binary gigabyte exceeds the decimal one by \(1{,}073{,}741{,}824 - 1{,}000{,}000{,}000 = 73{,}741{,}824\) bytes, and
\[\frac{73{,}741{,}824}{1{,}000{,}000{,}000} = 0.0737 \approx 7.4\,\%.\]
That 7.4 % is measured against the decimal gigabyte. Measured against the binary one it is \(73{,}741{,}824 / 1{,}073{,}741{,}824 = 6.87\,\%\): the decimal gigabyte is 6.87 % smaller. For the megabyte the gap is \(48{,}576 / 1{,}000{,}000 = 4.86\,\%\). The in-between gigabyte, 1,048,576,000 B, is 4.86 % above \(10^9\) and 2.34 % below \(2^{30}\) (equivalently, \(2^{30}\) is 2.4 % above it).
The floppy disk. Its “1.44 MB” is 1.44 thousand binary kilobytes:
\[1.44 \times 1000 \times 1024 = \mathbf{1{,}474{,}560}\ \textbf{bytes} = 1440\text{ KiB}.\]
That is 1.40625 MiB in binary megabytes and 1.47456 MB in decimal ones. The label is right in neither, which is the point: it mixes a decimal thousand with a binary kilobyte.
Common mistakes
- Calling SRAM “dynamic” because it can be rewritten. Static and dynamic are about how a bit is held, a flip-flop against a leaking capacitor, not about whether it can change. Both are read/write.
- Thinking non-volatile means read-only. Flash and EEPROM are non-volatile and rewritable. ROM is the only one here that can never be rewritten.
- Thinking SRAM keeps its contents at power-off because it does not need refreshing. Static means no refresh while powered. Both SRAM and DRAM are volatile.
- Mixing up flash and EEPROM. Both are electrically erasable; flash erases a block at a time, EEPROM one cell at a time. On the AVR the program goes in flash and individual settings in EEPROM.
- Assuming “MB” has one meaning. Memory sizes are powers of 2, disk sizes and data rates are powers of 10, and some figures mix the two. Say which, or use KiB, MiB, GiB.
- Getting the 7.4 % backwards. \(2^{30}\) is 7.37 % more than \(10^9\), but \(10^9\) is 6.87 % less than \(2^{30}\). The base of a percentage matters.
- Confusing B and b. A 1 Gbps link is about 125 MB/s, not 1 GB/s.
See also
- memory-hierarchy-and-cache — how registers, cache, DRAM and disk are arranged by speed and cost
- magnetic-disks · file-systems — secondary storage and how files are kept on it
- memory-models — the ATmega324A’s address spaces and the three assembler segments
- avr-architecture — flash, SRAM and EEPROM on the chip
- flip-flops-and-latches — the storage element of a static memory cell
- assembly-process —
.cseg,.dsegand.eseg - 2026-10-22-memory-disks-and-files — Lecture 24
Timing Diagrams
A timing diagram is the fourth of the four equivalent ways to describe a logic function, alongside the logic diagram, the truth table, and the Boolean expression (see logic-gates).
Timing diagram as a logic representation
It is like a truth table, but in graphical format: time runs left to right along the horizontal axis, and each signal gets its own horizontal track that steps between the logic 0 and logic 1 levels (drawn as two dashed reference lines).
Worked example — an inverter. The input waveform starts at logic 0, rises to logic 1 for a period, then falls back to logic 0. The output waveform is the mirror image: it starts at logic 1, falls to logic 0 for exactly that period, then returns to logic 1. Each change in the input causes the output to change.
Figure 80: An inverter drawn as a timing diagram. Reading the four intervals off the input gives 0, 1, 1, 0 and off the output gives 1, 0, 0, 1 — which is the inverter’s truth table, just laid out along a time axis instead of down a page. The two dashed lines per track are the logic 0 and logic 1 reference levels.
At this idealised level the output changes at exactly the same instant as the input; the transitions are drawn as vertical lines. That is a convenient fiction, corrected at the bottom of this note.
Convention for drawing the input waveforms
The input waveforms must be drawn so that all possible input combinations are covered — that is what makes the diagram equivalent to the full truth table.
The standard construction for a 2-input gate divides the time axis into four equal intervals and drives the inputs like a binary count:
- \(A\) is low for the first half of the diagram, then high for the second half.
- \(B\) toggles at twice that rate: low, high, low, high.
Reading the four intervals left to right therefore gives \(AB = 00, 01, 10, 11\) — every combination, once each, in truth-table order. For \(n\) inputs the same scheme generalises: input \(i\) toggles at half the rate of input \(i+1\), and the diagram is \(2^n\) intervals wide.
To read a gate’s output off the diagram, work interval by interval: identify the \(AB\) combination in that interval, look up the gate’s truth table row, and draw the output at that level for the width of the interval.
Figure 81: The convention on a 2-input example, with the AND output filled in. The vertical rules divide the four intervals; the digits under each track are the truth-table row for that interval. Because the inputs count 00, 01, 10, 11, the output track is literally the output column of the truth table, drawn left to right.
Going the other way — being given the output track and asked which gate it is — is the standard exam form of this. Read the output value in each interval, write it beside the corresponding \(AB\) row, and compare the resulting column with the gates you know. A worked instance is in 2026-08-06-combinational-logic.
Real gates aren’t perfect: the reality of timing
The idealised diagrams above show instantaneous, perfectly square transitions. Real gates do not behave that way — real waveforms have sloped edges, and the output changes some time after the input does. Three quantities describe this:
| Term | Definition |
|---|---|
| Propagation delay | Time for a change in the input to affect the output. |
| Fall time | Time taken for the output to fall from 1 to 0. |
| Rise time | Time for the output to rise from 0 to 1. |
Figure 82: The same inverter drawn honestly. The input’s edges slope instead of jumping; the output does not begin to move until the propagation delay has elapsed; and once moving, its downward edge takes the fall time and its later upward edge takes the rise time. Rise and fall times are properties of one edge of one signal — the propagation delay is the gap between two signals.
Measured on an inverter: the input ramps up, and only after the propagation delay does the output begin to move; the output’s downward edge then takes the fall time to complete, and its later upward edge takes the rise time.
The three quantities are measured differently, and it is worth keeping them apart. Rise time and fall time are properties of a single edge of a single waveform — how long that edge takes to get from one level to the other. Propagation delay is the gap between two waveforms — how long the output takes to react at all. All three are marked on the same pair of inverter waveforms above.