Introduction

2022 SA am1

01-02: https://blog.yexca.net/archives/184
03-05: https://blog.yexca.net/archives/185
06-10: https://blog.yexca.net/archives/186
11-15: https://blog.yexca.net/archives/189
16-30: https://blog.yexca.net/archives/190

So, regarding this article: I’ve decided to challenge myself by taking the System Architect exam—the advanced level of the Computer Technology and Software Professional Qualification. To be honest, I’m not sure if I’ll pass. A lot of the knowledge required for this cert might not seem useful in day-to-day coding (actually, it is, we just don’t realize it), but having it is better than not. I’ll try my best to finish this past paper. Hopefully, this process helps snap me back into reality.

Ramblings

I’ve been in a bit of a slump for the past two years, and it’s definitely affected how I handle things. I can’t keep going like this. Since I can’t change the past, I’ll just do my best with what’s ahead. I want to at least give it a shot; the scariest thing is losing the courage to try, which already cost me an opportunity recently. I need some change to feel like I’m actually “living” again. Sometimes it feels like I’m living in a dream—not a good one, just an unrealistic one. Words are limited; actual experience is more convincing, even if it’s a fabricated reality. I’m starting to believe some pretty far-fetched things.

Emm, this feels like a diary entry. Oh well, it is what it is.

The mention of feeling like I’m in a dream reminds me of a cultivation novel where a member of a demonic sect believes they are an immortal, that the current world is just an illusion, and they are only there for a trial. Sometimes I feel like that setting has influenced me too. Anyway, enough nonsense.

Question 1

A Hamming code is created by adding redundancy bits to data to allow for 1-bit error correction. Consider a Hamming code $X_1X_2X_3P_3X_4P_2P_1$ consisting of 4 bits of data $X_1, X_2, X_3, X_4$ and 3 redundancy bits $P_3, P_2, P_1$. The added bits $P_1, P_2, P_3$ are determined as follows:

Where $\oplus$ represents the XOR (exclusive OR) operation.

The Hamming code 1110011 contains a 1-bit error. Which of the following is the corrected Hamming code?

A. 0110011

B. 1010011

C. 1100011

D. 1110111

This is a Hamming code problem. The question provides the formulas. Substituting the values into the XOR equations:

The result of the check is $(111)_2$, which indicates the error is at the 7th bit. Therefore, the correct data is 0110011, which corresponds to option A (ア).

When I saw “Hamming code,” it felt familiar, but I couldn’t remember the details. Man, what was I even studying before?

Hamming codes are used to detect and correct single-bit errors. For example, to convert the original data 1100 into a Hamming code:

First, calculate the number of parity bits using $2^k \ge k + m + 1$, where $m$ is the number of data bits and $k$ is the number of parity bits. In this case, $k$ should be 3. Parity bits are placed at positions $2^n$ (1, 2, 4, 8…). So here, parity bits are at positions 1, 2, and 4. Position numbering usually goes from right to left.

With 3 parity bits and 4 data bits, there are 7 positions total. Let’s list their binary representations (3 bits):

The parity bit positions (1, 2, 4) correspond to 001, 010, and 100. This means position 1 tracks bits with a ‘1’ in the first binary digit, position 2 tracks the second, and position 4 tracks the third.

Now, determine the value of the parity bits based on the original data so that each group has an even number of 1s (even parity):

(Leaving parity bits blank for now)

Group 1 (bits 1, 3, 5, 7): Contains one “1”. Add 1 to make it even. Group 2 (bits 2, 3, 6, 7): Contains two “1"s. Add 0. Group 3 (bits 4, 5, 6, 7): Contains two “1"s. Add 0.

The resulting Hamming code is:

So 1100 becomes 1100001. The verification process is the same as the question.

To check for errors: Perform the XOR check for each group. If the results are all 0, there’s no error. If not, the resulting binary number (Group 3, Group 2, Group 1) points to the position of the flipped bit.

References:

Understanding Hamming Codes

Hamming Code Encoding and Verification

Exclusive OR (XOR)

Question 2

Lists can be implemented using either arrays or pointers. Which of the following is a characteristic of a list implemented using an array? Here, an array-based list stores elements contiguously, while a pointer-based list uses elements and pointers to the next element.

A. Regardless of the actual number of elements, space for the maximum possible number of elements must be allocated, which may result in unused memory.

B. To reference a middle element, you must traverse the list from the beginning, requiring time proportional to the number of elements.

C. In addition to the space for storing elements, extra space is required to store pointers to the next element.

D. If the insertion point is known, elements can be inserted in constant time regardless of the actual number of elements in the list.

This question asks about the characteristics of an array-based list implementation. Options B, C, and D are characteristics of linked lists (pointer-based). The correct answer is A.

The logic is straightforward; if I got it wrong, it’s only because I couldn’t read the Japanese :cry:. Here is the translation breakdown:

A: Max size must be pre-allocated regardless of actual usage, leading to potential waste. (Array trait)

B: Accessing an element requires O(n) traversal. (Linked list trait; arrays have O(1) random access)

C: Requires extra space for pointers. (Linked list trait)

D: Constant time insertion if the position is known. (Linked list trait; arrays require shifting elements, making it O(n))