跳到主要内容

大阪大学 電子情報学専攻 2015年8月実施 専門 第4問 誤り検出・訂正符号

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

(1) 情報ビット x1,x2,x3,x4x_1,x_2,x_3,x_4 に検査ビット x5x_5 を1個付け、単一誤りを検出する方法を述べよ。

(2) この符号の零符号語と他の符号語の最小Hamming距離、およびその距離を達成する符号語を示せ。

(3) (7,4)(7,4) Hamming符号を

x5=x1+x2+x4,x6=x2+x3+x4,x7=x1+x2+x3x_5=x_1+x_2+x_4,\quad x_6=x_2+x_3+x_4,\quad x_7=x_1+x_2+x_3

で生成する（加算は排他的論理和）。全符号語 (x1,…,x7)(x_1,\ldots,x_7) を表で示せ。

(4) 上の表から零符号語 (0,0,0,0,0,0,0)(0,0,0,0,0,0,0) と他の符号語の間の最小Hamming距離を求めよ。(5) (1)と(3)の符号の訂正可能な最大ビット数を求めよ。(6) 同一のビット誤り率でも、ハミング符号はランダム誤りよりバースト誤りに対して性能が劣化する。バースト誤りに対応する方法と利害得失を述べよ。

Kai​

(1) 偶数パリティとして x5=x1⊕x2⊕x3⊕x4\boxed{x_5=x_1\oplus x_2\oplus x_3\oplus x_4} とする。受信した5 bitのXORが1なら誤りを検出する。

(2) 非零符号語の重みは正の偶数なので dmin⁡=2\boxed{d_{\min}=2}。例は 10001\boxed{10001}。

(3)

情報語符号語情報語符号語
0000000000010001000101
0001000111010011001011
0010001001110101010110
0011001110110111011000
0100010011111001100010
0101010100111011101100
0110011010011101110001
0111011101011111111111

(4) 非零符号語の最小重みは3である。線形符号なので dmin⁡=3\boxed{d_{\min}=3}。

(5) t=⌊(dmin⁡−1)/2⌋t=\lfloor(d_{\min}-1)/2\rfloor より、(1)は 0 bit\boxed{0\text{ bit}}、Hamming符号は 1 bit\boxed{1\text{ bit}} まで訂正可能。

(6) 複数の符号語をインタリーブして送信し、受信後に元の順へ戻す。連続した誤りを異なる符号語へ分散でき、各語の誤り数を訂正能力以下に抑えられる。利点は元の誤り訂正符号を利用できること、欠点は並べ替え用メモリと遅延が増えることである。インタリーブ深さを超える長いバーストには訂正不能となる場合がある。

本页目录