東京大学 情報理工学系研究科 電子情報学専攻 2015年8月実施 専門 第4問

标签：

• Tokyo-University
• Parity-Bit-Single-Error-Detection
• Hamming-74-Code-and-Minimum-Distance
• Interleaving-for-Burst-Error

Author

diohabara, 祭音Myyura

Description

(1) 情報ビット $x_1,x_2,x_3,x_4$ の $4$ ビットの符号に対して $1$ ビットの検査ビット $x_5$ を付加する。単一誤りを検出することが可能であるような $x_5$ の生成方法を述べよ。

(2) (1) の符号の符号語 $(0,0,0,0,0)$ と他の符号語の間の最小ハミング距離を求めよ。また, $(0,0,0,0,0)$ とのハミング距離が最小ハミング距離となる符号語を一つ示せ。

(3) $(7,4)$ ハミング符号においては, 情報ビット $x_1,x_2,x_3,x_4$ に対して検査ビット $x_5,x_6,x_7$ を

$$\begin{aligned} x_5 &= x_1 + x_2 + x_4 \\ x_6 &= x_2 + x_3 + x_4 \\ x_7 &= x_1 + x_2 + x_3 \\ \end{aligned}$$

 を用いて生成し, $(x_1,x_2,x_3,x_4,x_5,x_6,x_7)$ という符号語に符号化する。ここで, "+"は排他的論理和の演算である。全ての符号語を表にして記せ。

(4) (3)の表を用いて, 符号語 $(0,0,0,0,0,0,0)$ と他の符号語の間の最小ハミング距離を求めよ。

(5) 最小ハミング距離を利用して,(1) で設計した符号と $(7,4)$ ハミング符号が, それぞれ最大何ビットの誤りまで訂正可能であるかを示せ。

(6) 一般にハミング符号は, 同一のビット誤り率であっても, バースト誤りの場合にはランダム誤りの場合よりも性能が劣化する。バースト誤りに対応する手法とその利害得失を論ぜよ。

题目描述

(1) 对由信息位 $x_1,x_2,x_3,x_4$ 构成的 $4$ 位字附加一个校验位 $x_5$。说明如何生成 $x_5$，使所得编码能够检测单比特错误。

(2) 求 (1) 的码字 $(0,0,0,0,0)$ 与其他码字之间的最小汉明距离，并举出一个与 $(0,0,0,0,0)$ 的距离恰为该最小距离的码字。

(3) 在 $(7,4)$ 汉明码中，对信息位 $x_1,x_2,x_3,x_4$ 按

$$\begin{aligned} x_5&=x_1+x_2+x_4,\\ x_6&=x_2+x_3+x_4,\\ x_7&=x_1+x_2+x_3 \end{aligned}$$

生成校验位 $x_5,x_6,x_7$，并编码为 $(x_1,x_2,x_3,x_4,x_5,x_6,x_7)$；其中“$+$”表示异或。用表格列出全部码字。

(4) 利用 (3) 的表，求码字 $(0,0,0,0,0,0,0)$ 与其他码字之间的最小汉明距离。

(5) 利用最小汉明距离，分别说明 (1) 所设计的编码与 $(7,4)$ 汉明码最多能纠正多少比特错误。

(6) 在比特错误率相同的情况下，汉明码对突发错误的性能通常比对随机错误差。讨论一种应对突发错误的方法及其利弊。

Kai

(1)

$x_5 = x_1 \oplus x_2 \oplus x_3 \oplus x_4$ とすればよい。受信した $5$ ビットの排他的論理和は、いずれか $1$ ビットが反転したとき $1$ となるので誤りを検出できる。

(2)

偶数パリティなので、非零符号語の重みは少なくとも $2$ である。$(1,1,0,0,0)$ の重みが $2$ なので、最小ハミング距離は $\boxed{2}$。

(3)

すべての符号語を表にすると以下の通り。

$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$
0	0	0	0	0	0	0
0	0	0	1	1	1	0
0	0	1	0	0	1	1
0	0	1	1	1	0	1
0	1	0	0	1	1	1
0	1	0	1	0	0	1
0	1	1	0	1	0	0
0	1	1	1	0	1	0
1	0	0	0	1	0	1
1	0	0	1	0	1	1
1	0	1	0	1	1	0
1	0	1	1	0	0	0
1	1	0	0	0	1	0
1	1	0	1	1	0	0
1	1	1	0	0	0	1
1	1	1	1	1	1	1

(4)

零符号語を除き、表中の $1$ の個数の最小値は $\boxed{3}$。例えば $(0,0,0,1,1,1,0)$ がこれを達成する。

(5)

最小ハミング距離 $d_H$ に対して $2d + 1 \le d_H$ となる最大の整数 $d$ を考える。このとき、$d$ ビットの誤り訂正が可能。

• (1) の場合、最小ハミング距離は $2$ なので $d = 0$ となる。すなわち誤り訂正はできない

• (3) の場合、最小ハミング距離は $3$ なので $d = 1$ となる。したがって、$1$ ビットの誤りまでなら誤り訂正が可能。

(6)

インタリーブを用いる。複数の符号語を行方向に並べて列方向に送信し、受信側で元の順序に戻す。これにより、連続した誤りを複数の符号語へ分散し、各符号語内の誤り数を訂正能力以下に抑える。

深さ $L$ のインタリーブなら、長さ $L$ 以下のバーストを各符号語の高々 $1$ ビットの誤りに分散できる。一方、並べ替え用のメモリと符号語を蓄積する遅延が必要になる。