22-Elec-A4 Digital Systems and Computers · May 2013

Question 5 of 6: Big-Endian Storage and the Stack

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Paper format. National Exams, May 2013 — 07-Elec-A4 Digital Systems & Computers. Three hours, closed book (one approved Casio or Sharp calculator). Six questions are printed; any five constitute a complete exam and all questions are worth 12 marks. An excitation table for the RS/JK/T/D flip-flops and a table of basic Boolean identities are supplied on the last page of the paper. All six questions are solved below, because this set is a study resource rather than a timed sitting.

Reference texts.

M. M. Mano and M. D. Ciletti, Digital Design: With an Introduction to the Verilog HDL, VHDL, and SystemVerilog, 6th ed. — Boolean algebra (Ch. 2), combinational design (Ch. 4), synchronous sequential logic (Ch. 5), registers and counters (Ch. 6), memory and address decoding (Ch. 7).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — canonical forms and minimisation (Ch. 3–4), counters and shift registers (Ch. 8).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — bus structure and addressing (Ch. 2), stacks (§2.6), memory system organisation and chip-select decoding (Ch. 8).

Convention used throughout. In the address/data expressions a prime denotes complement ($\overline{A}$ is written A′ in the figures, where SVG text cannot carry an overbar). Hexadecimal constants keep the Motorola dollar-sign notation of the exam paper, written here as $7A01 in prose so that it cannot be mistaken for a mathematics delimiter.

Question 5: Big-Endian Storage and the Stack (12 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given.

Item	Value
Datum	16-bit word $7A01, i.e. most-significant byte $7A, least-significant byte $01
Store address	$C239 (memory drawn with low addresses at the top)
Stack pointer before PUSH	SP = $DC51
Byte order	Big-endian (Motorola convention)
Stack growth	Toward low memory, SP addressing the next free byte
Marks	(a) 4, (b) 4, (c) 4

Find. The byte written into each drawn location by the STORE and by the PUSH, and the post-PUSH contents of SP.

Approach. Apply the two independent conventions in turn: big-endianness fixes which byte goes at which address, while the stack discipline fixes which addresses are used and how SP moves. Both must be applied to part (b); part (a) needs only the first.

Split the datum. A 16-bit word occupies two 1-byte locations. Splitting $7A01, $$\text{MS byte} = \text{7A}_{16}, \qquad \text{LS byte} = \text{01}_{16}$$ Big-endian order means the big end of the number — its most significant byte — is stored at the lowest address of the pair, and the address quoted in the instruction is that lowest address.
(a) Perform the STORE. The instruction names $C239, so that location takes the most significant byte and the next location up takes the least significant byte: $$(\text{C239}_{16}) \leftarrow \text{7A}_{16}, \qquad (\text{C23A}_{16}) \leftarrow \text{01}_{16}$$ Location $C238 lies below the named address and is not touched by this instruction.
Question 5(a) - memory contents after storing $7A01 to address $C239 in big-endian order.
Reading the two bytes back in increasing-address order reproduces 7A 01, which is the printed form of the number — the practical reason big-endian ordering is convenient for hexadecimal memory dumps.

(b) Perform the PUSH. A Motorola-style stack grows downward in memory and SP points at the next free byte. Pushing a 16-bit quantity is therefore two byte-pushes, least significant byte first:

Micro-step	Action	Result
1	$(\text{SP}) \leftarrow$ LS byte	($DC51) = $01
2	$\text{SP} \leftarrow \text{SP} - 1$	SP = $DC50
3	$(\text{SP}) \leftarrow$ MS byte	($DC50) = $7A
4	$\text{SP} \leftarrow \text{SP} - 1$	SP = $DC4F

Pushing the low byte first is what makes the pair land big-endian: because each push moves to a lower address, the byte pushed last — the most significant one — ends up at the lower address, exactly as in part (a). Location $DC52 is below the stack top and is untouched.

Question 5(b) - stack contents after pushing $7A01 with SP = $DC51 before the push.

Cross-check the stored word. Reading the two occupied bytes in increasing-address order gives $$(\text{DC50}_{16})\,(\text{DC51}_{16}) = \text{7A}_{16}\;\text{01}_{16} = \text{7A01}_{16}$$ identical to the result of the STORE in part (a), confirming that the PUSH preserved big-endian order. A subsequent PULL would reverse the four micro-steps, incrementing SP first, and recover the same word.
(c) Final stack pointer. Two bytes were pushed and SP decrements once per byte: $$\text{SP}_{\text{after}} = \text{DC51}_{16} - 2 = \boxed{\text{DC4F}_{16}}$$ SP again addresses the next free byte, one below the word just pushed.

Check: stack-pointer convention. The answer above uses the Motorola 6800/68HC11 convention stated by the figure, in which SP addresses the next free byte and therefore ends at $DC4F. Some processors (including the 68000 family with its predecrement addressing) define SP as pointing at the last item pushed; with that convention the first byte would go to $DC50, the second to $DC4F and SP would finish at $DC4F as well — the same final SP, but the two data bytes shifted one location down. The figure's arrow marks SP at $DC51 before the push, i.e. at a location shown as empty, which identifies the next-free-byte convention used here.

Part	Location	Contents after the instruction
(a)	$C238	unchanged
(a)	$C239	$7A (most significant byte)
(a)	$C23A	$01 (least significant byte)
(b)	$DC50	$7A (pushed second)
(b)	$DC51	$01 (pushed first)
(b)	$DC52	unchanged
(c)	SP after PUSH	$DC4F

Topic. Byte ordering of multi-byte operands and hardware stack operation.

Key relations. Big-endian: MS byte at the lowest address, $(\text{addr}) = $ MS, $(\text{addr}+1) = $ LS. Little-endian is the reverse. Downward-growing stack with SP at the next free byte: PUSH is $(\text{SP}) \leftarrow \text{datum};\ \text{SP} \leftarrow \text{SP} - 1$ per byte; PULL is $\text{SP} \leftarrow \text{SP} + 1;\ \text{datum} \leftarrow (\text{SP})$. After an $n$-byte push, $\text{SP}_{\text{after}} = \text{SP}_{\text{before}} - n$.

Why this works. Endianness and stack direction are independent design choices that happen to interact neatly in the Motorola architecture. Endianness answers only one question — in which order the bytes of a word are laid out in ascending addresses — and neither ordering is technically superior; big-endian matches the way humans write numbers and so makes memory dumps directly readable, while little-endian simplifies casting a long to a short. The stack discipline answers a different question: where the next item goes. Growing the stack downward from the top of RAM lets the stack and the program's static data expand toward each other from opposite ends of memory, maximising the space available to whichever needs it. Pushing the low byte first is not arbitrary — it is the choice that keeps the in-memory image of a pushed word identical to the image produced by an ordinary store, so that a subroutine can treat a stacked parameter exactly like any other variable.

Common pitfall. Writing $01 at $C239 and $7A at $C23A, which is the little-endian (Intel) answer to a question that explicitly names Motorola. On the stack the corresponding error is pushing the most significant byte first, which stores the word byte-reversed relative to the STORE in part (a) — an inconsistency that should immediately signal the mistake. Also remember that SP moves by two, not one, for a 16-bit push.

Source. Hamacher et al., Computer Organization and Embedded Systems, 6th ed., §2.3 (memory locations and byte addressability, big- and little-endian) and §2.6 (stacks); Mano & Ciletti, Digital Design, 6th ed., Ch. 8.

← Question 4 Next: Question 6 →