書記が数学やるだけ#755 誤り検出と訂正

通信路における誤り検出と訂正について。

問題

パリティの問題は基本情報技術者試験や応用情報技術者試験などで頻出。

説明

誤り検出と訂正の簡素な例はパリティチェックで，元の情報に1ビット付加することでもし誤りがあった場合に検出あるいは訂正ができるといったものである。

誤り検出と訂正の能力は最小ハミング距離により決まる。

解答

単一パリティは元の情報に検査記号を1ビット付加するもので，誤りが奇数のとき1ビット検出可能である。

一方で，水平垂直パリティは，1個の誤りなら訂正可能で，2個の誤りなら検出可能である。

例としてハミング符号について，以下の式は線形符号の回で扱う。

最小ハミング距離について，具体例を示しておく。

最小ハミング距離と誤り訂正・符号の関係について，誤りの個数tを半径とした円について最小ハミング距離を考えることで示すことができる。

本記事のもくじはこちら：