高校情報I 圧縮と誤り検出—元に戻せる条件とパリティの検出範囲を確かめる｜武蔵野個別指導塾

連続する記号を個数との組に直して復元し、偶数パリティが2ビットの反転を検出しない理由も確かめられます。

よくあるのは、受け取ったビット列のパリティが合ったので、送信中の誤りはなかったと断定する場面です。検査を通ることと、元の列と完全に一致することは同じではありません。圧縮でも、短くなったことと元に戻せることは別の条件です。範囲表や授業ノートで扱う規則を確認し、何を数え、何を確かめられるのかを答案に残しましょう。

問題文から拾う3つの条件

定期テストでは、まず可逆圧縮と非可逆圧縮を、復元した結果が元と一致するかで選ぶ型があります。文章や数値の記録のように各部分を正確に取り戻したい場面と、細部の変化を許して容量を小さくしたい場面では、求める条件が違います。名前だけで選ばず、失ってよい情報があるかを理由に添えます。

次に、連続する同じ記号を記号と個数の組で表すランレングスの型があります。符号の順序、個数の書き方、区切りを読み、元の並びを左から追います。元に戻す問題と、圧縮後の長さを数える問題では、答える対象が違います。

もう1つは偶数パリティです。送信側で検査用のビットを付ける問題と、受信側で検査する問題があります。後者では、検査に通ったとしても誤りがないと断定できるかが問われます。何個のビットが反転したかという条件まで読むことが、結論を正しく限定する鍵です。

元に戻す操作と検査の役割

圧縮は、情報を表すデータの量を減らす方法です。可逆圧縮は、定めた復元方法によって元のデータを完全に再現できます。非可逆圧縮は、復元時に失われた細部を元どおりには再現できない方法です。見た目や聞こえ方が似ていても、元のデータと各部分が一致するとは限りません。

図1のように、復元の一致を問う圧縮の分類と、届いた列の異常を調べるパリティは役割が異なります。圧縮できたこと自体は、送受信の途中で変化していない証明にはなりません。逆にパリティ検査を通過しても、非可逆圧縮で捨てた情報は戻りません。

ランレングスでは、同じ記号が切れ目なく続く部分を1組として表します。例えば符号を「記号、個数」の順に書き、組を区切る規則なら、Aが3個続く部分は A3 と表せます。復元するときは個数だけ記号を並べます。規則と記号の種類が両者で共有され、個数や組の区切りを読み取れることが必要です。記号が頻繁に切り替わる列では、個数を記す分だけ長くなる場合もあります。

偶数パリティでは、データのビットに検査用の1ビットを加え、全体の1の個数を偶数にします。元の1の個数が偶数なら検査用は0、奇数なら1です。0も偶数として扱います。受信側はデータ部分と検査用ビットを合わせて1を数え、奇数なら異常を検出します。偶数ならこの検査では異常を検出しませんが、元どおりとは限りません。

1ビットの反転とは、0が1に、または1が0に変わることです。1か所の反転で1の個数の偶数と奇数は入れ替わります。2か所なら2回入れ替わって元の偶奇に戻ります。データ部分だけでなく検査用ビットの反転も数に含める点に注意します。

基本例題を左から処理する

例題1。記号AとBからなる列 AAABBBAA を圧縮します。連続する同じ記号を、記号の直後に個数を1桁で付けた組で表し、組を空白で区切ります。各連続部分は9個以下とします。圧縮後の組と、空白を数えない記号数を答えてください。元の1文字と、圧縮後の文字または数字はそれぞれ1記号として数えます。

左端からAが3個続きます。最初の組は A3 です。

次にBが3個続くので、2番目は B3 です。

最後のAは2個なので、3番目は A2 です。

答えは A3 B3 A2、空白を除いて6記号です。図2のように3組それぞれを展開すると、AAA、BBB、AAとなり、つなげて元の AAABBBAA に戻ります。元は8記号なので、この数え方では2記号少なくなりました。実際のファイルの大きさを求めるには、記号の表現に必要なビット数や付加情報など別の条件が必要です。

例題2。データ 10110 の末尾に偶数パリティの検査用ビットを1個付けます。送信する6ビットを答え、受信した列が 101100 の場合の検査結果を述べてください。

データの1は3個で奇数です。全体を偶数にするため、検査用は1です。

送信列は 101101 です。1は4個で偶数になっています。

受信列 101100 の1は3個なので奇数です。したがって異常を検出します。送信列と比べると末尾が1から0に変わっていますが、受信側が検査結果だけからその位置を特定できるわけではありません。異常を検出することと、どこを直すかを知ることも区別します。

条件が変わると結果も変わる

例題3。データ 11001 の末尾に偶数パリティを付けて送ります。送信列を答えた後、次の2つの受信列をそれぞれ検査し、異常を検出するか答えてください。左からの位置は1から数えます。アは送信列の2番目だけが反転し、イは1番目と2番目が反転したものです。

データの1は3個なので、末尾に1を付けます。送信列は 110011 で、1は4個です。アでは2番目の1が0になり、受信列は 100011 です。1が3個なので奇数となり、異常を検出します。変化した位置を送信列に戻すと確かに元の6ビットになります。

イでは最初の2個の1がそれぞれ0になり、受信列は 000011 です。1は2個で偶数なので、異常を検出しません。しかし送信列との比較では2か所が異なります。検査を通ったという結果を「誤りがない」と言い換えると、この場合を落とします。正しくは「偶数パリティによる異常は検出されない」です。

この規則では反転が奇数個なら偶奇が変わり、偶数個なら偶奇が変わりません。反転数が0個なら一致しますが、受信列だけを数えた結果は2個の反転の場合と区別できません。検査に通る場合には、正常に届いた場合と、検査が見逃す場合の両方が含まれます。

圧縮でも成功と失敗を分けて考えます。例題1の規則で A3 B3 A2 と正しく読めれば元に戻せます。一方、途中の個数が失われたり、規則が共有されていなかったりすれば、その表記だけから元の連続個数を決められません。復元方法があることと、壊れた圧縮データまで修復できることは別です。

誤答の原因を見つけて直す

例題3のイに対し「1の個数が偶数なので、送信時と同じ列である」と答えたとします。偶数と数えた部分は正しいものの、そこから導いた結論が広すぎます。2か所の反転で偶奇が元に戻る場合を考えていないからです。

図3のように送信列 110011 と受信列 000011 を見比べると、先頭の2か所が異なる一方、どちらの1の個数も偶数です。答案は「検査では異常を検出しないが、2ビットが反転している」と修正します。実際の受信側が送信列を知らない場合には、異なる位置や個数まで断定できません。問題文が送信列を与えているときの比較と、検査結果だけの判断を分けましょう。

もう1つの誤りは、非可逆圧縮で復元した画像が元と同じに見えることから、元の各データも完全に一致すると決めることです。見た目の近さは完全一致の証明ではありません。問題が正確な再現を要求しているなら、元のデータを完全に再現できる可逆圧縮を選び、その条件を書くと筋が通ります。

自分で解く4問

次の記号列とビット列は練習用に作ったものです。答えは問題の後にまとめています。先に紙に途中の組や1の個数を書き、元の条件へ戻して確かめてください。

1. 列 CCCDDCCCC を、連続する同じ記号について「記号の直後に1桁の個数」を書き、組を空白で区切って表します。空白を除く圧縮後の記号数と、展開した元の列を答えてください。1文字と数字は各1記号です。
2. 列 XYXYX を、同じ規則で組にします。空白を除く圧縮後の記号数と元の記号数を答え、この数え方で短くなったか述べてください。
3. データ 01001 の末尾に偶数パリティを1ビット付けます。6ビットの送信列と、送信列の左から3番目だけが反転した受信列を書き、検査結果を答えてください。
4. 送信列 101011 は、末尾を含め1の個数が偶数です。左から1番目と4番目が反転した受信列を書き、検査結果と、誤りがないと断定できるかを答えてください。

練習の答えと戻し方

1. C3 D2 C4 で、空白を除き6記号です。Cを3個、Dを2個、Cを4個に展開すると CCCDDCCCC になります。元の9記号を順に再現しているので、途中で分かれたCの組を誤ってまとめていないことも確認できます。先頭と末尾が同じ記号でも、間にDがあるため1組にはしません。

2. X1 Y1 X1 Y1 X1 で、圧縮後は10記号、元は5記号です。1個ずつ交互に現れるため5組になり、各組に個数を付けると長くなります。展開すれば XYXYX に戻るので、長くなったことと復元できないことは別です。記号数の比較には空白を含めないという条件を使います。

3. データの1は2個で偶数なので、検査用は0です。送信列は 010010、3番目の0を1にした受信列は 011010 です。受信列の1は3個で奇数なので異常を検出します。受信列の3番目を再び0にすると送信列に戻り、指定された反転を確認できます。検査用が0であっても、検査時には末尾を含めて数えます。

4. 1番目の1と4番目の0を反転すると 001111 です。1は4個で偶数なので異常を検出しません。しかし指定された2か所は変わっており、誤りがないとは断定できません。受信列の同じ2か所を再び反転すると 101011 に戻ります。1が0になる変化と0が1になる変化が同時に起こり、1の個数自体が変わらない例です。

規則の読み落としを防ぐ

ランレングスの答案では、組の表記が合っていても、記号数の比較まで自動的に決まるわけではありません。例えば、個数を数字1文字で表す練習の規則は、連続が9個以下という条件に支えられています。10個以上が続く列に出会ったら、そのまま1桁に押し込めず、問題文に別の規則があるかを確かめます。規則が与えられていなければ、この表記だけでどう扱うかは決められません。

また、受信した列の1の個数が奇数の場合、検査の対象内で奇数個の反転があったことはわかりますが、その数が必ず1個とは限りません。1か所を推測して反転させれば偶数にはできますが、元の列に戻った保証はありません。奇数という検査結果から導ける範囲と、問題文が別に指定する反転の位置や個数を分けて記します。

送信前と受信後の処理を混ぜず、それぞれの列を別の行に書くと数え直しやすくなります。

問題文に検査用ビットをどこへ付けるかが書かれているときは、その位置も答案の一部です。末尾に付ける条件で先頭に置けば、全体の1の個数が正しくても指定した送信列とは異なります。受信後に数える対象がデータ部分だけなのか検査用を含む全体なのかも、数え始める前に確かめます。偶数パリティの検査では全体を使います。

答案に残す要点

可逆圧縮は元のデータを完全に復元でき、非可逆圧縮は失った情報を完全には戻せません。
ランレングスは連続部分ごとの記号と個数を、指定された規則で対応させます。
偶数パリティは検査用ビットを含む1の個数が偶数になるように付けます。
奇数個の反転は検出できますが、偶数個の反転は見逃します。

途中の記録からつまずきを探す

組の境目を間違える場合は、元の列に記号が切り替わる位置を記してから各個数を数えます。展開後の列が元の順序と長さに戻るかを見ると、組の抜けや隣接しない部分の結合に気づけます。圧縮後の長さでは、空白や区切りを数えるかという問題固有の条件にも印を付けます。

パリティで迷う場合は、データ部分と検査用を分けて書き、最後に合わせた1の個数を数えます。個別指導では、検査を通った列について、反転がない例と2か所が反転した例を本人に並べてもらい、同じ偶奇から何を言えるかを説明してもらえます。検査結果の範囲を言葉で区切ることが、誤りの見逃しを答案に反映させます。