水平垂直パリティ符号とは？原理・実装・利点欠点と実用例
エバープレイ編集部概要 — 水平垂直パリティ符号とは
水平垂直パリティ符号（2次元パリティ、two‑dimensional parity）は、データを行（水平）と列（垂直）に分割してそれぞれにパリティ（偶性）ビットを付加することで、単一ビット誤りの検出と訂正を可能にする単純で実用的な誤り検出・訂正（EDC/ECC）方式です。各行に1ビット、各列に1ビットのパリティを持つことで、誤りが生じた行と列の交差点を特定して誤ったビットを訂正できます。組み込み機器や簡易なストレージ保護、通信の簡易チェックなどで利用されます。
基本原理
パリティとはビット列の1の数が偶数か奇数かを示す情報で、通常はXOR演算で計算します。水平垂直パリティ符号では、次のように構成します。
- データをm行×n列のビットブロックに配置する。
- 各行について、その行のビットをXORして行パリティビット（水平パリティ）を付加する。
- 各列について、その列のビットをXORして列パリティビット（垂直パリティ）を付加する。
- オプションで全体のパリティ（行パリティと列パリティを含めた総和のパリティ）を付ける場合もある。これにより、誤りの種別の判定精度が向上することがある。
実装上はXOR（排他的論理和）を用いるため、ハードウェア/ソフトウェアのいずれでも簡単に計算できます。
具体例 — 4×4ブロックの計算例
4行×4列のデータを例に説明します。データビットを以下のように配置します（A〜Pは1ビットずつ）。
A B C D | r1 E F G H | r2 I J K L | r3 M N O P | r4 --------+--- c1 c2 c3 c4
ここで各行のパリティ r1..r4 はそれぞれ行内ビットのXOR、各列のパリティ c1..c4 は列内ビットのXORです。例えば行1のパリティ r1 = A ⊕ B ⊕ C ⊕ D、列1のパリティ c1 = A ⊕ E ⊕ I ⊕ M となります。
送信側はデータと行パリティ・列パリティを付加して送ります。受信側で再度各行・各列のパリティを計算し、送られてきたパリティと比較します。ある行とある列でパリティ不一致が起きれば、その交差点のビットが誤っていると判断して反転させる（訂正する）ことができます。
誤り検出・訂正能力
- 単一ビット誤り：必ず検出および訂正可能。行と列の不一致から誤り位置を一意に特定できる。
- 複数ビット誤り：すべてを検出・訂正できるわけではない。例えば同じ行内で偶数個のビットが反転すると行パリティは変わらないため、その行単独では検出できないケースがある。2つの誤りが異なる行・列にあると、2行2列でパリティ不一致となり、誤り位置の特定が困難（誤補正のリスク）となる。
- 検出可能性：多くの多ビット誤りを検出するが、特定の組み合わせ（例えば対称的な反転）が発生すると検出できない場合がある。
まとめると、2次元パリティは単一エラーの訂正に有効で、複数エラーに対しては検出能力はある程度あるが完全ではなく、誤り訂正能力は限定的です。
シンドローム（検査結果）の解釈
受信側で各行・各列のパリティを計算して送信されたパリティと比較すると、パリティ不一致の行・列の集合（シンドローム）が得られます。典型的な処理は次の通りです。
- 不一致行数 = 0 かつ 不一致列数 = 0：誤りなし。
- 不一致行数 = 1 かつ 不一致列数 = 1：その行と列の交差点が誤り。訂正して終わり。
- 不一致行数 > 1 または 不一致列数 > 1：複数ビット誤りの可能性。単純な2次元パリティでは正確な訂正ができないため再送要求（ARQ）や上位の強力なECCへ委ねる。
オプションで全体パリティを追加すると、偶数個の誤りの検出能が向上するケースがあり、誤りの種類（偶数個か奇数個か）判別に役立つことがありますが、万能ではありません。
実装のポイントと効率
- 計算コスト：XORのみを使うため非常に軽量。ハードウェアではゲート数が少なく、ソフトウェアでもビット演算のみで高速。
- オーバーヘッド：データの行数＋列数分のパリティビットが必要。例えばm×nブロックではm+nビット（＋オプションの全体パリティ1ビット）のオーバーヘッドがある。
- パラメータ設計：行長や列長は誤りモデル（単一ビット誤りが多いか、バースト誤りが多いか）に合わせて選ぶ。バースト誤りには弱いので、連続ビット誤りが多い環境では不利になる。
- 同期と配置：ブロック境界の取り扱いやパリティビットの配置（フレーム化）を設計する必要がある。ストレージやメモリでは物理的な配置（行＝バイト、列＝ワード等）を工夫すると効率的。
実用例・適用分野
- 組み込み機器の簡易メモリ保護：単純で低コストなエラー訂正が求められる場合。
- 通信プロトコルの低レイヤでの簡易チェック：高い耐障害性を要求しない管理情報や制御チャネルなど。
- 一部のストレージ実装やRAIDの派生手法：RAIDの基本的なパリティとは異なるが、複数方向のパリティを持つ考え方は高度な二重パリティ方式（例：P+Qなど）に発展している。
ただし、高信頼性が求められる大規模ストレージや通信では、ハミング符号、リードソロモン符号、CRC＋ARQなど、より強力な方式が用いられることが多いです。
他の符号との比較
- ハミング符号：ハミングは単一ビット誤りの訂正と二重誤りの検出が理論的に保証される（特定の距離を持つ）一方、2次元パリティは構造が単純でブロック単位の配置による自由度が高いが理論的な最良性は持たない。
- CRC（巡回冗長検査）：CRCは多くの誤りパターン（特にバースト誤り）を高確率で検出できる完検ではない検査方式で、誤り訂正能力はない。2次元パリティは訂正（単一ビット）が可能だが、バースト誤りへの耐性は低い。
- リードソロモンやLDPC：これらは大きな符号長で高い誤り訂正能力を提供するが、計算コストが高く実装が複雑。2次元パリティはリソース制約のある環境で有用。
拡張と発展
2次元パリティを基礎に、誤り検出・訂正性能を高めるための拡張が存在します。
- 追加の総パリティ（パリティのパリティ）：総体の偶奇を取ることで、ある種の二重誤りの検出能力を増す。
- 対角パリティや斜め方向のパリティを加える：位置特定の冗長性を増やすことで複数誤りの訂正能力を高める工夫。
- 2次元パリティをP+Qのような多重パリティ（線形独立なパリティ）に発展させ、RAID‑6のような二重パリティ構成に近い仕組みで故障耐性を強化するアプローチ。
実用上の注意点と設計指針
- 誤りモデルの理解：単一ビット誤りが主なら2次元パリティは有効だが、連続バースト誤りが多い環境ではCRCやRS符号の方が適する。
- オーバーヘッドとパフォーマンスのバランス：パリティビット追加による容量・帯域のコストと、計算コスト（低いながらも存在）を評価する。
- 上位プロトコルとの組合せ：誤りが訂正できないケースは再送（ARQ）や上位の強力なECCに委ねる設計が現実的。
まとめ
水平垂直パリティ符号は、設計が簡単で実装コストが低い一方、誤り訂正能力は単一ビットに限定的であり、多ビット誤りやバースト誤りに弱いという特性を持ちます。軽量な誤り訂正を必要とする組み込み用途や簡易なデータ保護の場面では有用ですが、高信頼性が要求される用途ではハミング符号、リードソロモン符号、LDPC、CRC＋ARQなどとの組み合わせや置き換えを検討すべきです。実際の採用では誤り発生の傾向（単一ビット中心かバースト中心か）、許容オーバーヘッド、計算リソースを総合的に勘案して選択してください。
参考文献
- パリティビット - Wikipedia（日本語）
- 誤り検出訂正符号 - Wikipedia（日本語）
- Two-dimensional parity check - Wikipedia（英語）
- Hamming code - Wikipedia（英語）
- Reed–Solomon error correction - Wikipedia（英語）
投稿者プロフィール
