https://runjp.com/docs/tokyo-university/IST/denshi/2016/denshi_201508_senmon_4

Description

(1) For a 4-bit code consisting of information bits $x_1, x_2, x_3, x_4$, a 1-bit check bit $x_5$ is added. Describe a method for generating $x_5$ such that it is possible to detect a single-bit error.

(2) Find the minimum Hamming distance between the codeword $(0, 0, 0, 0, 0)$ and other codewords of the code in (1). Also, provide one codeword whose Hamming distance from $(0, 0, 0, 0, 0)$ is equal to the minimum Hamming distance.

(3) In a $(7, 4)$ Hamming code, check bits $x_5, x_6, x_7$ are generated for information bits $x_1, x_2, x_3, x_4$ using:

$x_5 = x_1 + x_2 + x_4$

$x_6 = x_2 + x_3 + x_4$

$x_7 = x_1 + x_2 + x_3$

and encoded into a codeword $(x_1, x_2, x_3, x_4, x_5, x_6, x_7)$. Here, "$+$" represents the Exclusive OR (XOR) operation. Create a table showing all codewords.

(4) Using the table from (3), find the minimum Hamming distance between the codeword $(0, 0, 0, 0, 0, 0, 0)$ and other codewords.

(5) Using the minimum Hamming distance, indicate the maximum number of bit errors that can be corrected for the code designed in (1) and the $(7, 4)$ Hamming code, respectively.

(6) In general, even with the same bit error rate, the performance of Hamming codes degrades more in the case of burst errors than in the case of random errors. Discuss a technique to handle burst errors and its advantages and disadvantages.

---

答案

1

To detect a single-bit error in a code block, the most common and efficient method is to use a Single Parity Check. This involves adding a check bit ($x_5$) such that the total number of “1”s in the 5-bit sequence follows a specific parity rule (either even or odd).

1. Parity Check Methods

There are two primary ways to generate the check bit $x_5$:

• Even Parity: The check bit $x_5$ is chosen so that the total number of 1s in the sequence $\{x_1, x_2, x_3, x_4, x_5\}$ is even.

  Mathematically, this is calculated using modulo-2 addition (XOR):

  $x_5 = x_1 \oplus x_2 \oplus x_3 \oplus x_4$

• Odd Parity: The check bit $x_5$ is chosen so that the total number of 1s in the sequence is odd.

  Mathematically, this is the inverse of the even parity bit:

  $x_5 = \neg(x_1 \oplus x_2 \oplus x_3 \oplus x_4)$

---

2. How it Detects Errors

When the receiver gets the 5-bit code, they perform a Parity Check (re-calculating the sum of the bits).

1. Transmission: Suppose you use Even Parity. You send a 4-bit message 1010. Since there are two 1s (already even), $x_5 = 0$. The sent code is 10100.
2. Error Occurs: If a single bit flips during transmission (e.g., the second bit becomes 1), the receiver sees 11100.
3. Detection: The receiver counts the 1s and finds there are three (an odd number). Since the protocol requires an even number of 1s, the receiver knows a single-bit error has occurred.

---

Summary Table

Data (x1x2x3x4)	Even Parity (x5)	Resulting Code
0000	0	00000
1000	1	10001
1100	0	11000
1110	1	11101

Note: While this method is excellent for detecting single-bit errors, it cannot detect “even” errors (e.g., if two bits flip simultaneously, the parity remains the same) and it cannot identify which bit is wrong—it only signals that the data is corrupted.

2

To determine the minimum Hamming distance, we look at the properties of the parity check code generated in the previous step.

1. Minimum Hamming Distance ($d_{min}$)

The Hamming distance between two codewords is the number of positions at which the corresponding bits are different. The Hamming distance between any codeword and the all-zero codeword $(0, 0, 0, 0, 0)$ is simply the Hamming weight (the number of 1s) of that codeword.

In a Single Parity Check code (using even parity):

• Every valid codeword must have an even number of 1s.
• The possible weights for non-zero codewords are 2 or 4.
• The smallest number of 1s a non-zero valid codeword can have is 2.

Therefore, the minimum Hamming distance $d_{min}$ between $(0, 0, 0, 0, 0)$ and all other valid codewords is 2.

---

2. Example Codeword

To find a codeword with a Hamming distance of 2 from $(0, 0, 0, 0, 0)$, we need a sequence where exactly two bits are “1” and the parity remains even.

One such codeword is:

$(1, 1, 0, 0, 0)$

Verification:

• Information bits: $x_1=1, x_2=1, x_3=0, x_4=0$
• Check bit calculation (Even Parity): $x_5 = 1 \oplus 1 \oplus 0 \oplus 0 = 0$
• Full Codeword: $(1, 1, 0, 0, 0)$
• Distance from $(0, 0, 0, 0, 0)$: 2 bits differ (the first and second positions).

3

To create the codeword table for this $(7, 4)$ Hamming code, we iterate through all $2^4 = 16$ possible combinations of the information bits $(x_1, x_2, x_3, x_4)$ and calculate the check bits using the provided generator equations:

• $x_5 = x_1 \oplus x_2 \oplus x_4$
• $x_6 = x_2 \oplus x_3 \oplus x_4$
• $x_7 = x_1 \oplus x_2 \oplus x_3$

(7, 4) Hamming Codeword Table

x1	x2	x3	x4	x5	x6	x7	Full Codeword
0	0	0	0	0	0	0	0000000
0	0	0	1	1	1	0	0001110
0	0	1	0	0	1	1	0010011
0	0	1	1	1	0	1	0011101
0	1	0	0	1	1	1	0100111
0	1	0	1	0	0	1	0101001
0	1	1	0	1	0	0	0110100
0	1	1	1	0	1	0	0111010
1	0	0	0	1	0	1	1000101
1	0	0	1	0	1	1	1001011
1	0	1	0	1	1	0	1010110
1	0	1	1	0	0	0	1011000
1	1	0	0	0	1	0	1100010
1	1	0	1	1	0	0	1101100
1	1	1	0	0	0	1	1110001
1	1	1	1	1	1	1	1111111

---

Observations

• Minimum Hamming Distance ($d_{min}$): For this specific Hamming code, the minimum distance is 3. This means it can detect up to 2-bit errors and correct any single-bit error.
• Zero Codeword: As with all linear codes, the all-zero input results in an all-zero codeword.
• Weight: Excluding the all-zero codeword, the minimum number of “1”s in any codeword (Hamming weight) is 3.

4 and 5

(4) Minimum Hamming Distance for (7, 4) Hamming Code

The Hamming distance between any codeword and the all-zero codeword $(0, 0, 0, 0, 0, 0, 0)$ is equal to the Hamming weight (the number of 1s) of that codeword.

By inspecting the table generated in part (3), we look for the non-zero codeword with the fewest number of 1s:

• Example: The codeword for 0001 is 0001110, which has a weight of 3.
• Example: The codeword for 0110 is 0110100, which has a weight of 3.
• There are no valid non-zero codewords in this table with only 1 or 2 ones.

Therefore, the minimum Hamming distance $d_{min}$ between $(0, 0, 0, 0, 0, 0, 0)$ and other codewords is 3.

---

(5) Maximum Correctable Bit Errors

The error-correcting capability of a code is determined by its minimum Hamming distance ($d_{min}$). The maximum number of bit errors $t$ that a code can guarantee to correct is calculated using the formula:

$t = \left\lfloor \frac{d_{min} - 1}{2} \right\rfloor$

1. The Code from (1) (Single Parity Check)

• Minimum Distance ($d_{min}$): 2
• Calculation: $t = \lfloor (2 - 1) / 2 \rfloor = \lfloor 0.5 \rfloor = 0$
• Correction Capability: 0 bits.
  • Note: A parity check can detect a single-bit error, but it cannot correct any errors because it doesn’t have enough information to locate which bit flipped.

2. The (7, 4) Hamming Code

• Minimum Distance ($d_{min}$): 3
• Calculation: $t = \lfloor (3 - 1) / 2 \rfloor = \lfloor 1 \rfloor = 1$
• Correction Capability: 1 bit.
  • Note: This code is specifically designed to identify the exact position of a single-bit flip and flip it back to the correct value.

---

Summary Table

Code Type	dmin	Max Errors Detectable	Max Errors Correctable
Single Parity Check (1)	2	1	0
(7, 4) Hamming Code	3	2	1

6

To address the vulnerability of Hamming codes to burst errors—where multiple adjacent bits are corrupted simultaneously—the most common and effective technique is Interleaving.

1. The Technique: Interleaving

Interleaving is a process where the order of bits from multiple codewords is rearranged before transmission. Instead of sending codewords one by one, they are “shuffled” together.

How it works (Block Interleaving):

1. Arrange in a Matrix: Write $M$ codewords (each of length $N$) row by row into a 2D memory buffer (an $M \times N$ matrix).
2. Transmit by Columns: Read the bits out column by column for transmission.
3. De-interleave at Receiver: The receiver performs the inverse operation, writing the received bits into columns and reading them out as rows to restore the original codewords.

---

2. Why it Works

If a burst error occurs during transmission and affects, for example, 4 consecutive bits, those errors will be spread across 4 different codewords after de-interleaving.

• Because a $(7, 4)$ Hamming code can correct 1 bit error per codeword, a burst of length 4 that is spread across 4 codewords results in only 1 error per codeword, which the Hamming code can now successfully fix.

---

3. Advantages and Disadvantages

Feature	Description
Advantage: Error Dispersion	Converts a single long burst error into multiple, isolated single-bit errors that the Hamming code is actually designed to handle.
Advantage: Efficiency	Does not require adding more overhead or check bits beyond what the Hamming code already uses.
Disadvantage: Latency	The system must wait to receive the entire block ($M \times N$ bits) before it can begin de-interleaving and decoding. This is problematic for real-time applications.
Disadvantage: Memory	Both the transmitter and receiver require extra memory (buffers) to store the matrix during the shuffling and unshuffling process.

---

Summary

Interleaving essentially “dilutes” the impact of a burst error. By spreading the damage, it allows a simple code like the $(7, 4)$ Hamming code—which is otherwise helpless against bursts—to provide robust protection in environments with temporal noise, such as wireless communications or deep-space signals.

🔀 交织技术：把“大灾难”化解为“小麻烦”

汉明码（Hamming Code）虽然厉害，但它有一个致命弱点：它通常只能修好 1 位错误。如果遇到“突发错误”（连续好几位都坏了），汉明码就束手无策了。

交织技术（Interleaving） 就是为了解决这个问题而生的。

1. 核心思想：把鸡蛋放在不同的篮子里

【比喻】： 想象你有 4 盒鸡蛋（4 个码字），每盒有 7 个。

• 如果不交织：路上有个大石头砸中了第一盒，把里面的 4 个鸡蛋全砸碎了。汉明码一看：“一盒碎了 4 个？救不回来，扔了吧。”
• 如果使用交织：你在出发前，把 4 盒鸡蛋混合在一起。第一盒拿 1 个，第二盒拿 1 个… 这样排队。当大石头砸中连续的 4 个鸡蛋时，其实是每盒各碎了 1 个。汉明码一看：“每盒只碎了 1 个？小意思，我能修好！”

2. 操作流程：先“横写纵读”，再“纵写横读”

交织的过程就像填字游戏：

1. 发送端（交织）：
   • 准备一个矩阵（比如 4 行 7 列）。
   • 横着写：把 4 个汉明码字一行一行地填进去。
   • 纵着读：发信号时，按第一列、第二列… 这样竖着把数字发出去。
2. 传输中（突发错误发生）：
   • 假设由于干扰，连续 4 位数据变乱了。因为你是“竖着发”的，这 4 位错误其实分布在不同的列。
3. 接收端（解交织）：
   • 接收方把收到的数据再竖着填进去，然后横着读出来。
   • 奇迹发生了：原本连续的 4 位错误，被分散到了 4 个不同的行里。现在每一行（每一个码字）只包含 1 个错误。

3. 优缺点分析

特性	描述
优点：分散风险	把一个无法修复的“连环车祸”变成了多个可以修复的“轻微刮擦”。
优点：无额外开销	不需要增加额外的校验位，只是改变了发送顺序，非常高效。
缺点：延迟（Latency）	你必须等整块数据（比如全部 28 位）都收齐了，才能开始“拆解”和纠错。这对实时通话或游戏会有延迟。
缺点：费内存	发送方和接收方都需要开辟一块“小仓库”（内存缓冲区）来摆放这个矩阵。

4. 总结：为什么要用它？

在无线通信（如 Wi-Fi、4G/5G）或深空通信中，干扰往往是持续一小段时间的（像一阵风吹过）。交织技术本质上是在“稀释”干扰的浓度，让原本只能纠正单点错误的简单算法（如汉明码），也能具备对抗长时间干扰的能力。

一句话总结：交织就是把“集中的痛苦”平摊给每一个码字，让大家都能扛得住。