誤り訂正

Study

• ちょっとメモ

誤り訂正符号 †

• 誤り検出と誤り訂正とで分けられる場合もある
  • 検出して訂正するかしないかの違い

パリティビット †

• 最も単純な誤り検出符号
  • 与えられた2進数の奇偶性をチェックする
    • 1が奇数個あるか偶数個あるかをチェック
• 送信するデータの左端にパリティビットを追加する
  • 0:even（1が偶数個ある）
  • 1:odd （1が奇数個ある）
• ただし、偶数個のビットが違っても奇偶性は変わらないので検出できない

ハミング符号 †

• 最も古い誤り訂正符号の1つ
  • やはり由来は開発者名から
  • 訂正率は高くないが、処理が早い
    • 誤り率が高くなくて処理速度が求められる機器に使われる

• 2つの行列
  • 検査行列H
  • 生成行列G

• 符号化
  • 生成符号Gと送信したいデータとの乗算を行う
  • 生成されたデータを送信する

• 復号化
  • 受信した信号と検査行列Hの乗算を行う
    • 誤りがあるとその部分の位置が分かるので、その部分を反転させればよい

• 拡張ハミング符号
  • パリティチェックを追加する
    • 元の1bitの誤り訂正
    • さらに、2bitの符号誤り検出まで出来るようになる

リード・ソロモン符号 †

• 誤り訂正符号の1つで、訂正能力が高く様々なディジタル機器等で応用されている
  • 名前の由来は開発者二人の名前
  • ただ、若干複雑なので処理速度が求められる部分では使われない
• 1シンボル単位で誤りを検出する
  • 複数ビットを1単位とする
    • たいていは8bit(1Byte)単位で1シンボルとする
  • 連続したビットが間違ってても1まとまりの間違いにするのでラク
  • 1シンボルのパターンは決まっている
    • それを利用してビット列を原始多項式I(x)（情報多項式）で表すことが出来る

• 符号化
  • ビット列の情報多項式I(x)から生成演算によって別の多項式を生成する
  • 出来たC(x)を送信する

• 復号化
  • 復号化の方法はいくつかある
    • ピーターソン法
    • ユークリッド法
  • 結局は誤りに対して次の手順で復号する
    • 受信信号からシンドロームSi(x)の算出（検出しやすくする数式）
    • 誤シンボルの数の検出
    • 誤シンボルの位置を検出
    • 誤シンボルの値を検出
    • 誤シンボルの訂正

用語 †

S/N*1 †

• 信号に対する雑音の比率
  • SNR*2、SN比とも呼ばれる
• 常用対数で示してS/Nのlogをとった値で単位は[dB]

ビット誤り率BER*3 †

• データのうちの誤ったビットの割合
  • BER＝10^(−9)の場合，10^9個のデータを送ると1個間違いがあることを意味する