符号理論

符号理論は、シンボルを表現、伝送、復元する方法を扱います。ソフトウェアシステムにおける「符号化」は、圧縮、誤り符号、通信路レベルの信号、またはフレーミング規約を意味する場合があります。これらの機構は相互作用しますが、解決する問題は異なります。

情報源符号化と通信路符号化 #

情報源符号化は、情報量が許す限り少ないビットで情報源を表現します。可逆圧縮は統計的な冗長性を除去し、元のバイト列を正確に再現する必要があります。非可逆コーデックは、アプリケーション固有の歪みモデルに従って情報を破棄します。

通信路符号化は、伝送または保存の前に構造化された冗長性を追加します。受信側はその冗長性を使用して破損を検出または訂正します。パリティビットが検出できるのは一部の誤りパターンだけです。反復符号は多数決によって誤りを訂正できますが、多くの帯域幅を消費します。ハミング符号や現代のブロック符号または畳み込み符号は、同じオーバーヘッドでより有用な距離を提供します。

したがって、圧縮と通信路符号化のビット予算は逆になります。

圧縮は、通信路が信頼できると仮定するため、冗長性を減らします。
通信路符号化は、通信路にノイズがあると仮定するため、冗長性を加えます。

誤り訂正符号の後に圧縮器を適用しても、一般に冗長性はほとんど見つかりません。圧縮後に誤り訂正を適用する方法は、圧縮済みストリームにも保護が必要なため有効です。

ハミング距離、冗長性、および符号化率 #

同じ長さの 2 つのビット列間のハミング距離は、値が異なる位置の数です。ブロック符号の最小距離 d は、任意の 2 つの有効な符号語間の最小距離です。復号器は最大 d - 1 個のビット誤りを常に検出でき、限界距離復号器は最大 floor((d - 1) / 2) 個の誤りを訂正できます。

符号が k 情報ビットを n 伝送ビットへ写像する場合、その符号化率は R = k/n です。残りの n - k ビットが冗長性です。最小距離を増やすと通常は R が低下するため、実装では通信路の誤りモデルに合う符号化率と復号器を選択します。チェックサムや CRC も冗長性を追加しますが、訂正ではなく検出を目的として設計されています。検査の失敗は、元のビットを特定することなく、受信メッセージが無効であることを示します。

ライン符号と遷移特性 #

ライン符号化は、ビットを物理的な信号レベルまたは遷移へ写像します。クロック復元、スペクトル、およびベースラインの挙動に影響しますが、メッセージ境界を識別したりビット誤りを修復したりはしません。

Nonreturn-to-Zero（NRZ） #

NRZ レベル規約では、一方のビット値が 1 つの信号レベルを選び、もう一方の値がビット区間全体にわたって別のレベルを選びます。したがって、同じビットが長く続くと遷移がありません。受信側は、別のクロック、遷移の多い符号化、またはビットスタッフィングなどの規則からタイミングを復元する必要があります。

「NRZ」は、単一の普遍的なマッピングではなく遷移規約を表す場合もあるため、プロトコル仕様には極性とタイミングの規則を記載する必要があります。実装は名前だけからマッピングを推測してはなりません。

Nonreturn-to-Zero Inverted（NRZI） #

NRZI は、一方のビット値を遷移として、もう一方を遷移なしとして符号化します。USB で使用される一般的な規約は次のとおりです。

入力ビット	信号の挙動
`0`	レベルを反転する
`1`	直前のレベルを維持する

ビットの意味を逆にするプロトコルもあります。初期レベルが確立された後の NRZI は極性に依存しませんが、遷移のない長い連続を排除するものではありません。「維持」ビットが連続する場合は、依然としてクロック規則が必要です。そのため、USB はビットスタッフィングを使用します。また、NRZI はフレーミング、誤り検出、誤り訂正を提供しません。

レイヤーを分離する #

堅牢なリンクには、次のすべてのレイヤーを含められます。

物理信号化は、ビットを電圧、光学シンボル、または遷移に変換します。
フレーミングは、境界、アドレス、および場合によっては長さフィールドを示します。
情報源符号化は、ペイロードを圧縮します。
CRC などの完全性検査は、偶発的な変更を検出します。
通信路符号化は、検出または訂正を可能にする冗長性を追加します。

レイヤーごとに障害モードは異なります。遷移規則からフレームの終端は判別できず、フレーム区切りでは反転したペイロードビットを訂正できず、圧縮器ではバイト列が伝送に耐えたかを検証できません。レイヤーを明示的に名付けることで、NRZI、CRC、およびハフマン符号を交換可能な「符号化」として扱うことを防げます。

参考資料 #

C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, 1948.
R. W. Hamming, “Error Detecting and Error Correcting Codes,” Bell System Technical Journal, 1950.
Universal Serial Bus Specification, Revision 2.0、NRZI およびビットスタッフィングに関する節。