反復符号を使うと、そのまま送信するよりも誤り率を下げられるが、送るデータの量が増え、効率が悪くなってしまう。
反復符号ほどはデータ量を増やさずに誤り率を下げる方法の一つに、パリティ検査符号がある。
パリティ検査符号では、符号を規定のビット数ごとに区切り、その内容に応じて別の符号を付け加えることでも誤り検出を行う。

まず、情報源 (送信側) で という処理を行う。こうすることで、追加後の \(k+1\) ビットのブロックの1の数は常に偶数個になるはずなので、通信路で変化が起こらない限りこの条件は満たされる。そこで受信者は のような処理を行う。

例 ( \(k=4\) の場合)
変化がなければ のように復元できる。

通信路で変化がおきていた場合は、受信者側で1が奇数個含まれるブロックがみつかる。みつけたら再送信を要求する。
「チェック用に追加した符号」(この例ではそれぞれのブロックの5ビット目) のことを検査符号、もとの符号のことを情報源符号という。
この呼び名は反復符号でも同様で、「0」を「000」にするケースでは最初の0が情報源符号、後ろの00が検査符号にあたる。

符号「011011101111」にパリティ検査符号を追加したものを記述せよ。ただし \(k=4\) とする。

パリティ検査符号追加済みの以下の符号を受け取ったとき、通信路で変化があったかどうかを判定し、以下のものを解答せよ。ただし \(k=3\) とする。

• 変化があった場合 → 「変化あり」と解答
• 変化がなかった場合 → 情報源符号を記述

1. 011010101111
2. 011101101100

\(k=2\) のパリティ検査符号を使い、2元対称通信路を通した場合に誤り検出を行うケースを考える。
1ブロック中に変化が1回起こったときは、受信者がブロック中の1の数をカウントすると奇数個になるので、「変化があった」と判定することになる。
ところが、1ブロック中で2回変化が起きてしまうと、ブロック中の1の数が偶数個になってしまうので「変化なし」と判定され、誤ったものが復元されてしまう。
情報源符号(元の符号)は2つとも変化することもあるし、片方だけが変化することもある。
1ブロック中で3回変化が起きると、ふたたびブロック中の1の数は奇数個になるので「変化あり」と判定される。
反復符号で誤り検出を行った場合と同様に、変化の検出に応じて再送信を要求すると図のような流れで結果が決まる。


情報源符号「00」にパリティ検査符号を加え、入力が0, 1のどちらでも確率 \(p\) で変化し、消失が起こらない通信路を通すと、1回の送信で起こることは下の表のようになる。

変化の回数	受け取るもの	確率	判定	やること
0	000	\((1-p)^3\)	変化なし	00を復元 (正しい)
1か3	001, 010, 100, 111		変化あり	再送信を要求
2	110, 101, 011	\(p^2(1-p)\)	変化なし	11, 10, 01を復元

「ブロック単位で考えて」正しい結果を復元する確率を \(p_a\), 再送信になる確率を \(p_b\), 誤った結果を復元する確率を \(p_c\) とすると、


となる ( \(p_b\) は誤り率の計算には不要なので表には書いていない)。最終的に「ブロックとして誤った値を復元してしまう確率」\(p_{e0}\) (誤り率とは異なる) は、反復符号の場合とまったく同様に

となる。

誤り率は「1ビットの符号が誤ったものに復元される確率」で、この値そのものではない。
ブロックとして誤った値が復元されるケースは11, 10, 01の3通りで、先頭の1ビットだけに注目すると、誤ったものになるのは11, 10になったときの2通りだけである。つまり、誤り率は \(p_{e0}\) の2/3になるので、
となる。これに(1), (2)式の右辺の形を入れると、誤り率は以下のようになる。

\(k=2\) のパリティ検査符号を追加し、\(p=0.01\) の2元対称通信路を通して誤り検出を行った場合の誤り率を求めよ。ただし、四捨五入して小数第4位までにすること。

普通のパリティ検査符号では、ブロック中で変化がおきたかどうかを調べることができるが、ピンポイントでどこが変化したかを知ることはできない。しかし、以下のようにすれば変化が起きた場所を特定し、誤り訂正を行うことができる。
送信側でやること( \(k=3\) の場合)

1. 情報源符号を3桁×3の形に並べる
「001101111...」なら

0	0	1
1	0	1
1	1	1



2. それぞれの行の右と列の下にパリティ検査符号を追加する (右下端の符号は「その上の3つ」「その左の3つ」のどちらで作っても同じ値になる)

0	0	1	1
1	0	1	0
1	1	1	1
0	1	1	0



3. 上から1行ずつ順に送信する
この場合なら送るのは「0011 1010 1111 0110」

受信側では、受け取ったものを2と同様の形に並べ、縦と横について1の数をカウントし、すべて偶数になっているかどうかをチェックする。
もし通信路で図のような変化が起こったとすると、左の列と上から2番目の行で1の数が奇数個になる。
すると、変化した場所が「左から1番目、上から2番目」であることを特定でき、それが本当は1だったことがわかる。
そのため、再送信を要求しなくても情報源符号を復元できる。

\(k=4\) の水平垂直パリティ検査符号追加済みの符号「01100 11011 10011 11110 11000」を受け取った場合の情報源符号を記述せよ。ただし、変化は最大1回しか起こっていないものとする。