伝送技術

このページでは、パリティ・CRC・ハミング符号による誤りの検出と訂正、キャラクタ同期・フラグ同期・調歩同期、HDLCの手順がわかります。

• 一言で言うと：
  • データを正しく送り届けるための、昔からの基本技術の話
  • 送られてきたデータの誤りを見つけて直す（誤り制御）、送る側と受ける側のタイミングを合わせる（同期制御）、相手の様子を見ながら送る手順を決める（伝送制御、HDLC）の3つ

誤りを見つける・直す（パリティ、CRC、ハミング符号、水平垂直パリティ）→ タイミングを合わせる（キャラクタ同期、フラグ同期、調歩同期）→ 送る手順（HDLC）

覚え方の軸

• 誤り制御は「見つけて再送か、その場で直すか」
  • 見つけるだけ（再送してもらう）のが、パリティチェックとCRC
  • その場で直せるのが、ハミング符号と水平垂直パリティチェック（1ビットの誤りを訂正）
• 見つける力は「パリティ＜CRC」
  • パリティは1ビットの誤りしか見つけられない。バースト誤り（連続した誤り）は苦手
  • CRCはバースト誤りも見つけられる（HDLCが使う）
• ハミング符号は「2ビットまで見つけて、1ビットは直す」
  • 誤りのあるビットは、値が1になった検査式に共通に含まれるビット
• 同期方式は「何を目印にするか」
  • キャラクタ同期はSYNコード、フラグ同期はフラグ（01111110）、調歩同期はスタートビット（0）とストップビット（1）
• HDLCは「フラグで挟み、CRC（FCS）で確かめ、返事を待たずに続けて送る」
  • フラグと同じ並びがデータに出ないよう、1が5つ続いたら0を入れる（ゼロインサーション）

誤り制御：誤りを見つける、直す（★）

• 誤り制御：
  • ネットワークで送ったデータの誤りを検出したり、誤ったデータをその場で回復したりすること
• 誤り制御の方法：
  • ①誤り検出で再送する方法 → パリティチェック、CRC
  • ②誤り訂正で自己修復する方法 → ハミング符号

① パリティチェック

• パリティチェック：
  • 最もシンプルな検査方法
  • 例えば、7ビットのデータを送るとき、8ビット目に誤り検出用のパリティビットを付けて、データの整合性を調べる
• 偶数パリティ：
  • 8ビット全体で「1」の数が偶数になるように、パリティビットを入れる
• 奇数パリティ：
  • 全体で「1」の数が奇数になるように調節する
• パリティチェックの長所と短所：
  • 構造がシンプルで、機器を対応させやすく、オーバヘッドも少ない
  • でも、1ビットの誤りしか検出できない
  • だから、バースト誤り（データが連続して誤りを起こすこと）には対応できない
• パリティチェックの例え：
  • 「クラスの出席者は偶数人のはず」と決めておく。1人増えたり減ったりすれば気付くが、2人同時に入れ替わると気付かない

例題（パリティビット）

• 問題：
  • 7ビットのデータ「1011001」に、偶数パリティと奇数パリティのパリティビットを付けると、それぞれ何になるか
• 答え：
  • 「1」の数は、1・0・1・1・0・0・1 で4個（偶数）
  • 偶数パリティなら、全体を偶数のままにするので、パリティビットは0
  • 奇数パリティなら、全体を奇数にするので、パリティビットは1
• 検算：
  • 偶数パリティ：1の数は4 ＋ 0 ＝ 4（偶数）。奇数パリティ：4 ＋ 1 ＝ 5（奇数）
• 2ビット誤りに弱い理由：
  • 例えば、偶数パリティの「10110010」の2ビットが反転して「01110010」になっても、1の数は4のままで偶数なので、誤りに気付けない

② CRC

• CRC（Cyclic Redundancy Check：巡回冗長検査）：
  • 送るデータに生成多項式を適用して、誤り検出用の冗長データを作り、それを付けて送る
  • 受信側は、送信側と同じ生成多項式で受信データを割り算し、同じ結果ならデータ誤りがないと判断する
• CRCの特徴：
  • パリティビットも冗長データだが、CRCはさらに複雑な演算をするので、バースト誤りも検出できる
  • HDLC手順が採用している（HDLCは後述）
• CRCの例え：
  • 長い数字の列を、決まった数（生成多項式）で割った「余り」を一緒に送る。受け取った側も同じ数で割り、余りが合わなければ、どこかが書き換わったとわかる

③ ハミング符号

• ハミング符号：
  • 情報ビットに検査ビットを付けることで、2ビットまでの誤り検出と、1ビットの誤り自動訂正ができる誤り制御方式
• 検査ビットの数：
  • 誤りビットを訂正できるように、4ビットの情報に3ビットの検査ビットを持たせる
  • 8ビットの情報には4ビット、16ビットの情報には5ビットの検査ビットが必要

ハミング符号の例

• 検査ビットの決め方：
  • 4ビットの情報 X1X2X3X4 に、3ビットの検査ビット（冗長ビット）P1、P2、P3 を付ける
  • 次の3つの式の値が0になるように、P1、P2、P3を決める（⊕は排他的論理和）
• 3つの検査式：
  • X1 ⊕ X3 ⊕ X4 ⊕ P1 ＝ 0
  • X1 ⊕ X2 ⊕ X4 ⊕ P2 ＝ 0
  • X1 ⊕ X2 ⊕ X3 ⊕ P3 ＝ 0
• 送りたいデータが「1001」のとき：
  • P1 ＝ X1 ⊕ X3 ⊕ X4 ＝ 1 ⊕ 0 ⊕ 1 ＝ 0、P2 ＝ X1 ⊕ X2 ⊕ X4 ＝ 1 ⊕ 0 ⊕ 1 ＝ 0、P3 ＝ X1 ⊕ X2 ⊕ X3 ＝ 1 ⊕ 0 ⊕ 0 ＝ 1
  • 送信するハミング符号は、X1X2X3P3X4P2P1 の順で「1001100」
• 誤りの見つけ方：
  • 受け取ったデータを3つの式に当てはめる
  • すべての式の値が0なら、誤りビットなし
  • 1ビットの誤りがあれば、そのビットを含む式の値が1になる
• 受信例：
  • 「1101100」が届いた（X2が1になっている）
  • 1つ目の式は 1 ⊕ 0 ⊕ 1 ⊕ 0 ＝ 0、2つ目の式は 1 ⊕ 1 ⊕ 1 ⊕ 0 ＝ 1、3つ目の式は 1 ⊕ 1 ⊕ 0 ⊕ 1 ＝ 1
  • 1になった2つ目と3つ目の式に共通に含まれ、1つ目の式には含まれないビットはX2なので、X2が誤り
  • X2の「1」を「0」にすれば訂正できる
• mod関数を使う方法：
  • 排他的論理和の代わりに、関数mod（ ）を使って検査ビットの値を決める方法もある（2で割った余りを使う）
• ハミング符号の例え：
  • 3人の見張り（検査式）が、それぞれ決まった数人を見張っている。誰か1人がおかしくなると、その人を見張っている見張りだけが手を挙げる。手を挙げた見張りの組合せから、犯人が1人に決まる

例題（ハミング符号で誤りを直す）

• 問題：
  • 上と同じ検査式を使う。データ「1011」（X1＝1、X2＝0、X3＝1、X4＝1）を送るときの検査ビットを求めよ。また、X3が反転して届いたとき、どう見つけるか
• 検査ビット：
  • P1 ＝ X1 ⊕ X3 ⊕ X4 ＝ 1 ⊕ 1 ⊕ 1 ＝ 1
  • P2 ＝ X1 ⊕ X2 ⊕ X4 ＝ 1 ⊕ 0 ⊕ 1 ＝ 0
  • P3 ＝ X1 ⊕ X2 ⊕ X3 ＝ 1 ⊕ 0 ⊕ 1 ＝ 0
• X3が0になって届いたとき：
  • 1つ目の式：1 ⊕ 0 ⊕ 1 ⊕ 1 ＝ 1
  • 2つ目の式：1 ⊕ 0 ⊕ 1 ⊕ 0 ＝ 0
  • 3つ目の式：1 ⊕ 0 ⊕ 0 ⊕ 0 ＝ 1
• 答え：
  • 1になったのは1つ目と3つ目の式。この2つに共通に含まれ、2つ目の式には含まれないビットはX3
  • だから、X3を0から1に戻せば訂正できる
• 検算：
  • X3を1に戻すと、1つ目は 1 ⊕ 1 ⊕ 1 ⊕ 1 ＝ 0、3つ目は 1 ⊕ 0 ⊕ 1 ⊕ 0 ＝ 0 で、すべて0になる

④ 水平垂直パリティチェック

• 水平垂直パリティチェック：
  • ハミング符号と似ているが、パリティチェックを水平方向と垂直方向で同時に行うことで、1ビットの誤りを訂正できる
• 例：
  • 2行のデータを送るとき、水平方向パリティ（行ごと）と垂直方向パリティ（列ごと）を作る
  • 受信側でも同じ計算をすると、A列のパリティと2行目のパリティが合わない
  • だから、A列2行目のデータが誤りで、本当は0だとわかる
• 水平垂直パリティの例え：
  • 表の縦の合計と横の合計を両方メモしておく。縦も横も合わない行と列が交わるマスが、書き間違えたマス
• 冗長化の注意：
  • ハミング符号も水平垂直パリティチェックも、誤り検出や訂正の精度を上げようとすると、それだけチェック情報が冗長になる（送るデータが増える）

同期制御：送る側と受ける側のタイミングを合わせる（★）

• 同期制御：
  • 通信するとき、送信側と受信側でタイミングを合わせるために行うこと
• 同期：
  • 互いのタイミングを合わせる作業
  • 同期の取り方には、3種類の方法がある

同期方式

方式	やり方	長所・短所
キャラクタ同期方式	送信側が、送信データの最初に、SYNコードという同期をとるための特別なコードを2個以上続けて送る	8ビットのテキストデータの送信に便利でよく使われた。でも、SYNコードと同じパターンのデータは送れない、8ビット長のデータにしか対応していない
フラグ同期方式（フレーム同期方式）	送りたいデータの前後に、フラグという特別なビット列を入れて同期をとる。フラグはふつう「01111110」	フラグと同じパターンが出なければよいので、データは何ビット単位でもよい。柔軟に運用でき、使いやすい。HDLC手順が採用
調歩同期方式（非同期方式）	7ビットか8ビットの固定長ブロックの前後に、スタートビット「0」とストップビット「1」を付けて送る	1文字ごとに2ビットを付ける必要があるので、大きなデータを送るとオーバヘッドが大きい。今はあまり使われていない

• キャラクタ同期方式の制約：
  • 16ビットでできている日本語や、可変長のマルチメディアデータは送れない
• ゼロインサーション：
  • フラグ同期方式で、フラグ「01111110」と同じ並びがデータの中に出ないようにする処理
  • 送信側は、データ中に1が5つ続いたら、強制的に0を挿入する
  • 受信側は、データ中で1が5つ続いたら、次に続く0を強制的に取り除く
  • こうして、フラグの固有性（フラグにしか「1が6つ連続」が現れないこと）を保つ
• 調歩同期方式の待機中：
  • データを送っていないときは、常にストップビット「1」を送り続けている
  • だから、「1」から「0」（スタートビット）に変わった瞬間に、データの始まりがわかる
• 3つの方式の例え：
  • キャラクタ同期は、「せーの、せーの」（SYNコード）と声をかけてから話し始める
  • フラグ同期は、話の前後を決まったチャイム（フラグ）で挟む
  • 調歩同期は、1文字ごとに「よーい（スタート）」「おわり（ストップ）」と言う。丁寧だが時間がかかる

例題（ゼロインサーション）

• 問題：
  • データ「0111111011」を送るとき、ゼロインサーション後のビット列はどうなるか
• 答え：
  • 先頭の0の後、1が5つ続いたところ（011111）で0を入れる
  • 「01111101011」になる
• 確かめ：
  • 元のデータには「1が6つ連続」（0111111）があり、そのままだとフラグ（01111110）と区別できない
  • 0を入れた後は、どこにも1が6つ続かない
  • 受信側は、「11111」の次の0を取り除いて、元の「0111111011」に戻す

伝送制御：相手の様子を見ながら送る

• 伝送制御：
  • データを送るときに、伝送する相手の状態を確かめながら行うこと
  • 代表的な方式にHDLCがある

① HDLC

• HDLC（High-level Data Link Control）：
  • 高い効率と信頼性を追求した、フラグ同期方式を採用した伝送制御手順
• HDLCのメリット：
  • 任意のビットパターンを伝送できる
  • データを連続して転送できる
• 任意のビットパターンを送れる理由：
  • HDLCでは、伝送するデータがキャラクタ（文字）にしばられないので、任意のビット列を送れる
• 連続して転送できる理由：
  • HDLCでは、データをフレーム単位で送るが、受信確認を待たずにフレームを送れる
  • だから、伝送能力が大幅に上がる
• ベーシック手順：
  • 伝送制御手順の1つ
  • データがキャラクタとして伝送されるのが特徴
  • そのため、テキスト以外のデータを大量に送る用途には向かない
  • SYNキャラクタを使って同期をとる
• HDLCとベーシック手順の例え：
  • ベーシック手順は、1通送るたびに「届いた？」と確認してから次を送る。しかも文字しか送れない
  • HDLCは、確認を待たずにどんどん送り、何でも（画像でも）送れる

HDLCフレーム構成（★）

記号	名前	中身
F	フラグシーケンス（01111110）	フレームの開始と終了の区切りの記号（前後に付く）
A	アドレス部	送信または受信先のアドレス
C	制御部	コマンドまたはレスポンスの種類
DATA	情報部	転送するデータ
FCS	フレームチェックシーケンス	誤り検出用のCRC符号

• 並び順：
  • F → A → C → DATA → FCS → F
• FCSの検査対象の範囲：
  • A（アドレス部）、C（制御部）、DATA（情報部）
  • フラグ（F）は対象外
• ゼロインサーションとHDLC：
  • 情報部（DATA）などに、フラグシーケンス「01111110」と同じビット列が出たときは、ゼロインサーションを行う

② フレームチェックシーケンス（FCS）

• FCSの作り方：
  • アドレス部（A）、制御部（C）、情報部（DATA）に対して、CRC方式で誤りチェック情報を計算し、FCSとしてフレームに付ける
• 計算の例：
  • ビット列が「1001010」なら、これを多項式「X⁶＋X³＋X¹」と見なす
  • あらかじめ決めた生成多項式（X¹⁶＋X¹²＋X⁵＋1）で割り算し、その余りをFCSに入れる
• ビット列を多項式にする読み方：
  • 右端を X⁰ として、左へ X¹、X²…と番号を付け、「1」が立っている位置だけを足す
  • 「1001010」は、右から X⁰（0）、X¹（1）、X²（0）、X³（1）、X⁴（0）、X⁵（0）、X⁶（1）なので、X⁶＋X³＋X¹
• CRCの強さ：
  • CRCは強力な誤り検出方式で、パリティチェックではできない複数ビットの誤りを見つけられる
  • 生成多項式がn次なら、長さn以下のバースト誤りをすべて検出できる
  • だから、HDLC手順の信頼性はとても高い

混同しやすいペア

• 誤り検出 ／ 誤り訂正
  • 誤り検出は、誤りを見つけて再送してもらう（パリティチェック、CRC）
  • 誤り訂正は、その場で自分で直す（ハミング符号、水平垂直パリティチェック）
• 偶数パリティ ／ 奇数パリティ
  • 偶数パリティは、全体の「1」の数を偶数にする
  • 奇数パリティは、全体の「1」の数を奇数にする
• パリティチェック ／ CRC
  • パリティチェックは、シンプルでオーバヘッドが少ないが、1ビットの誤りしか見つけられない
  • CRCは、生成多項式で割り算をし、バースト誤りも見つけられる（HDLCが採用）
• ハミング符号 ／ 水平垂直パリティチェック
  • ハミング符号は、検査式（排他的論理和）で、2ビットまで検出し、1ビットを訂正する
  • 水平垂直パリティチェックは、縦と横のパリティで、1ビットの誤りを訂正する
• 情報ビット ／ 検査ビット（冗長ビット）
  • 情報ビットは、本来送りたいデータ
  • 検査ビットは、誤りを見つけたり直したりするために付け足すビット
• バースト誤り ／ 1ビットの誤り
  • バースト誤りは、データが連続して誤ること（CRCで検出できる）
  • 1ビットの誤りは、1か所だけの誤り（パリティで検出、ハミング符号で訂正できる）
• キャラクタ同期方式 ／ フラグ同期方式
  • キャラクタ同期方式は、SYNコードを2個以上送る。8ビットのデータしか送れない
  • フラグ同期方式は、データの前後にフラグ（01111110）を入れる。何ビット単位でもよい（HDLC）
• フラグ同期方式 ／ 調歩同期方式
  • フラグ同期方式は、データのかたまりの前後をフラグで挟む
  • 調歩同期方式は、1文字（7か8ビット）ごとにスタートビット0とストップビット1を付ける（非同期方式）
• スタートビット ／ ストップビット
  • スタートビットは、「0」。データの始まり
  • ストップビットは、「1」。データの終わり。送るものがないときも送り続ける
• ゼロインサーション（送信側） ／ ゼロの除去（受信側）
  • 送信側は、1が5つ続いたら0を入れる
  • 受信側は、1が5つ続いたら、次の0を取り除く
• SYNコード（同期） ／ SYNパケット（TCP）
  • 同期のSYNコードは、キャラクタ同期で、タイミングを合わせるための特別なコード
  • TCPのSYNは、3ウェイハンドシェイクのコネクション確立要求
• HDLC ／ ベーシック手順
  • HDLCは、フラグ同期。任意のビットパターンを、受信確認を待たずに連続して送れる
  • ベーシック手順は、キャラクタ単位でSYNキャラクタを使う。テキスト以外の大量データには向かない
• アドレス部 ／ 制御部
  • アドレス部は、送信または受信先のアドレス
  • 制御部は、コマンドまたはレスポンスの種類
• FCS ／ フラグシーケンス
  • FCSは、誤り検出用のCRC符号（A、C、DATAが対象）
  • フラグシーケンスは、フレームの開始と終了の区切り（01111110）

---

← 07 ネットワークの目次に戻る