# 誤り検出符号 ## 定義 誤り検出符号(error-detecting code)は、フレームに冗長ビットを付加し、伝送中に生じたビット誤りを受信側が検知できるようにする仕組みである。送信側・受信側が同じアルゴリズムをメッセージに適用し、結果が一致すれば誤りなしと判断する。冗長ビットの生成が加算に基づくものは特に**チェックサム(checksum)**と呼ばれる。目標は「少ない冗長ビット数($k$)で高い誤り検出能力」を両立させることであり、$n$ ビットのメッセージ全体を2重に送る素朴な方式(冗長ビットが $n$)と比べ、CRC は $n$ に対してごく小さい $k$(Ethernet では 32 ビット)で強い検出能力を達成する。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 2 Direct Links]] §2.4) 本書はこの節を、同じ「誤りを検知する」という目的に対して複数の解(単純な繰り返し送信・インターネットチェックサム・CRC・FEC)を並べ、それぞれの冗長ビット数・検出能力・計算コストのトレードオフを示す構成を取っており、システムズアプローチの典型例として位置づけられる。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 2 Direct Links]] §2.4) ### インターネットチェックサム データを 16 ビット単位の整数列とみなし、1 の補数算術で総和を取り、その 1 の補数をチェックサムとする。16 冗長ビットのみで済み実装が容易(ソフトウェアで軽量)だが、検出能力は弱い。例えば、一方の語をある値だけ増やし、別の語を同じ値だけ減らすような一対の単一ビット誤りは相殺されて検出できない。それでも実用上妥当とされるのは、これがエンドツーエンドプロトコルにおける「最後の防衛線」であり、大半の誤りはより強力なリンク層の CRC によって既に捕捉されているためである。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 2 Direct Links]] §2.4.1) ### CRC (Cyclic Redundancy Check) $(n+1)$ ビットのメッセージを $n$ 次多項式 $M(x)$ とみなし、送受信双方が事前に合意した除数多項式 $C(x)$(次数 $k$)で割り切れるように、$k$ ビットの冗長ビットを付加した $P(x)$ を送る。受信側が $P(x)$ を $C(x)$ で割った余りが 0 でなければ誤りありと判定する。多項式演算は係数を mod 2(XOR)で扱う特殊な体で行われる。$C(x)$ の選び方次第で、以下が理論的に保証される。 - $x^k$ と $x^0$ の係数が非ゼロなら、すべての単一ビット誤りを検出できる - $x^0$ の係数が非ゼロで $C(x)$ が $x^j + 1$ を割り切らなければ、$j$ ビット離れたすべての2ビット誤りを検出できる - $C(x)$ が因子 $(x+1)$ を持てば、奇数個の誤りをすべて検出できる - バースト長が $k$ ビット未満のバースト誤りをすべて検出できる(多くの場合 $k$ ビット以上のバーストも検出できる) Ethernet は CRC-32(次数 32 の多項式)を用いる。CRC は $k$ ビットのシフトレジスタと XOR ゲートで容易にハードウェア実装できる。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 2 Direct Links]] §2.4.2) ### 検出と訂正のトレードオフ(FEC) 誤り訂正符号(ECC)を使えば、受信側は再送を要求せずにその場で誤りを訂正できる。しかし検出のみの符号と同等の誤り範囲をカバーする訂正符号は、一般により多くの冗長ビットを必要とする。したがって検出方式は「誤りが起きたときだけ」多くのビットを送ればよいのに対し、訂正方式は「常に」多くのビットを送り続ける必要がある。誤り訂正が有利になるのは (1) 誤り率が高い環境(無線)、(2) 再送コストが高い環境(衛星リンクなど遅延の大きい経路)である。ネットワーキングにおける誤り訂正符号の利用は**前方誤り訂正(FEC, Forward Error Correction)**と呼ばれ、802.11 のような無線ネットワークで一般的である。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 2 Direct Links]] §2.4.2) ## 横断的知見 - (現時点では [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 2 Direct Links]] 単独からの立ち上げであり、複数ソースの突き合わせによる知見はまだない。他の source が誤り検出・訂正符号に触れた際にここへ積み増す。) ## 未解決の問い - インターネットチェックサムの「最後の防衛線」という位置づけは、QUIC など UDP 上に構築された近年のトランスポートプロトコルでも維持されているか。QUIC のパケット保護(暗号化+認証)は誤り検出の役割をどう再定義しているか。 - CRC-32 の多項式選択(Ethernet の生成多項式)がどのような実証的根拠(誤りパターンの統計)に基づいて決まったか、本章は「本を調べて分かる」としか説明していない。 - FEC と ARQ(自動再送要求)を同一リンク上で組み合わせる設計(例: 誤りが少ないうちは FEC のみ、閾値を超えたら ARQ も併用)は本章では扱われていない。 ## 関連 - source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 2 Direct Links]](§2.4) - 概念: [[ネットワーク符号化]](誤り検出とは異なる「ネットワーク内符号化」の概念。混同注意) ## 出典 - [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 2 Direct Links]](§2.4, §2.4.1, §2.4.2) </content>