数式を使わずによくわかるエラー訂正符号！ということで「RFワールド-No.32-らくらく！エラー訂正符号入門」の個人的メモなどです。
ハミング符号については本書でよくわかります。ここまで丁寧にわかりやすく解説してくれる本もなかなかないでしょう。
リードソロモン符号や畳み込み符号についても説明がありますが、こちらは紙面の都合上、ハミング符号ほど丁寧に説明といかなかったようで、若干の消化不良でした。それでも定性的な雰囲気くらいは掴めます。
【雑誌：RFワールド-No.32-らくらく！エラー訂正符号入門】元データを完全に保存するXORすごい。ループ付きシフトレジスタの破壊力も衝撃。このレジスタが1クロックで1シフトして、規則性を持った巡回符号を世界のあちこちの基板の中で叩き出しているかと思うと、神の所業か？と思いたくなる。しゅごい
— Keiya | 強くなりたい (@2R8R9) July 1, 2023
XORは元データを完全に保存する
エラー訂正符号を理解するには、XORの性質を理解することがとても大事。
その性質とは、「ある値を2回XORすればその値の影響は完全に消える」ということ。
ということで、通信の世界では送信側で1回XORして、受信側で2回目のXORをすることで、チェックを行っている。
ループ付きシフトレジスタの魔力
シフトレジスタは、それ単体だとだたのバッファでしかない。
しかし、そこにループ構造を持ち込むと、規則性を持って巡回する符号を生成する装置に変貌を遂げる。
「規則性を持って巡回する符号」とは、具体例をあげるなら、「11001010」「11001010」「11001010」…みたいなことだ。
1循環のビットを長く取れば、まるでランダムなビット列が生成されているように見える。
これが疑似ランダム信号（PN信号）と呼ばれるやつ。
あくまでビット列が長くてランダムに「みえる」というだけで、1循環すればもとのパターンに戻るので本当の意味でランダムではないので注意。
ハミング符号
ペイロードと検査ビットで構成される。検査ピットには各ビットの紋章のXORが設定する。受信側で紋章を再びXORして結果が0になれば、XORの影響が完全に消えたということでエラーなしと判断。1ビット誤りありの場合は、当該ビットの紋章が浮かび上がるので、当該ビットを反転させてエラー訂正完了。すなわちハミング符号は1ビットエラー訂正が可能な符号。
拡張ハミング符号
ハミング符号とパリティ検査を組み合わせたもの。2ビットのエラー検出が可能（パリティOKでハミングNGだと2ビットエラーで訂正不可と判断）。
BCH符号
紋章の数を増やして、2ビットとか3ビット誤ってもその結果の紋章が、各ビットの紋章と被らないようにしたもの。
ゴレイ符号
紋章の決め方を巧妙にしたハミング符号。3ビットまでのエラー訂正が可能。紋章をもれなくダブりなく使用。神様からの贈り物。数学的に完全で美しい。
リードソロモン符号
ビット単位であるハミング符号をバイト単位に拡張したもの。バイト単位なので連続したエラーに強い。
畳み込み符号
この符号だけブロック符号ではないので雰囲気が違う。畳み込み符号はデータをそのまま送信しない。送信すべきビット値をもとにして、ステートマシンに刺激を与えて状態を変化させ、その状態を送信する。
畳み込み符号によるエラー訂正の本質は、前後の何ビットかの関係性をもとに生成される状態の並びによって、エラー情報を推理すること。拘束長が長いステートマシン（宇宙などでは7が使われる）にすればより強力なエラー訂正が可能だが、計算量は指数的に増える。ビタビ復号に失敗すると前後のデータが広く巻き添えを食い、狭い範囲に固まったバーストエラーが発生する。この点はバーストエラーに強いRS符号と相性がよい。
コメント