冬期講習 2026-2027、募集中。総復習は売りません。90分×完全1対1で、穴だけを塞ぎます 詳しく →
電話 0422-27-7828チャットで質問無料相談を予約

武蔵野個別指導塾の特徴

共通テスト情報I 符号表の切替え—同じビット列の読みが変わる位置を見つける|武蔵野個別指導塾

学習のイメージ写真 武蔵野個別指導塾
X LINE Facebook

固定長の自作符号表で2項目を交換し、誤読する位置と変わらない位置を追って符号表を読み解きましょう。

よくあるのは、高校生が送信側と受信側の符号表が違うと知り、文字が全て誤読されると決める場面です。表が違っても、変更されていない対応があります。その符号が現れた位置は正しく読める一方、交換された対応に当たる位置は別の文字に見えます。

同じビット列から何が読めるかは、列そのものと、読む側が使う表の両方で決まります。ここでは自作の固定長の符号表を使い、送信時の文字列を復号結果と位置ごとに照合します。実在の文字コードの割当てを表したものではありません。

どこを固定して比べるか

判定の型は大きく3つあります。1つ目は、送信側の表と入力文字列からビット列を作り、受信側の表で読み直して一致する位置を探す型です。2つ目は、同じビット列を2種類の表でそれぞれ読み、結果が分かれる位置を比べる型です。3つ目は、入力列の中で交換された文字が現れる場所だけを調べ、影響の範囲を判定する型です。

いずれも、比較する間に入力列や区切り方を勝手に変えません。送信側の表で文字をビット列に変えた後、受信側の表でビット列を文字に戻します。表の列を読む向きが逆になるため、最初にどちらが文字、どちらが符号かを確認します。

たとえば表の一部分が更新されても、使った符号の対応がその部分に含まれなければ結果は変わりません。逆に、交換された2文字のどちらかを含むと、その位置は別の文字になります。文字の種類が変更されたかという問いと、入力の何番目が影響するかという問いは別です。同じ文字が繰り返されれば、影響する位置も繰り返されます。

符号と文字を往復する

図1のように、送信側の表Aと受信側の表Bを用意します。どちらも1文字を2ビットで表し、表にある4文字を扱います。表Bは表Aの「ア」と「イ」の符号を交換し、「ウ」と「エ」は変更していません。各表では4種類の符号が重ならず、各符号から文字を1つに決められます。

図1 送信側と受信側の符号表で交換された対応

図1の対応は次の表でも確認できます。左から右へたどると符号化、右側の符号から左へ戻ると復号です。送信側でアに付けた00を受信側で読むと、表Bではイに対応します。00というビット列が途中で変化したわけではありません。

文字 表Aの符号 表Bの符号
ア 00 01
イ 01 00
ウ 10 10
エ 11 11

固定長とは、ここではどの文字も同じ2ビットで表すという条件です。先頭から2ビットずつ区切れば、符号の境界が定まります。区切った各組は数値として計算せず、表にある記号の並びとして照合します。先頭の0も符号の一部なので省きません。

表Aと表Bを比べると、00と01では読みが入れ替わり、10と11では読みが一致します。この比較は表の全行について行っています。入力に現れない符号の対応が違っていても、その入力に対する読みには影響しません。一方、表の違いが1組の交換でも、交換された文字が複数回現れれば複数箇所で読みが変わります。

基本例題:並びを1文字ずつ照合する

表Aで「アウイエア」を符号化し、そのビット列を変更せず表Bで復号します。表は上の4行とし、各文字は2ビット、区切りは先頭から取ります。復号した5文字と、元の文字と一致する位置を左から1番目として番号で答えてください。

図2のように、まず文字ごとに表Aの符号を置きます。区切りを示す空白は説明のためであり、符号のビットには含めません。送信した列は00 10 01 11 00です。

図2 基本例題の送信列と受信側で読んだ文字
位置 元の文字 表Aで送る符号 表Bで読む文字 一致
1 ア 00 イ しない
2 ウ 10 ウ する
3 イ 01 ア しない
4 エ 11 エ する
5 ア 00 イ しない

答えは「イウアエイ」、一致する位置は2番目と4番目です。1番目の00は表Aではアですが、表Bではイです。3番目の01は逆にアになります。2番目と4番目の符号は両表で同じ文字に対応するため、表が異なっていても正しく読めます。

答えを送り返す向きに確認しましょう。表Bで「イウアエイ」を符号化すると00 10 01 11 00となり、送った列と一致します。ただし、この往復だけでは元の文字列が読めたことにはなりません。送信側の元の文字列との比較が必要です。受信側の表の中で矛盾なく往復することと、送信者の意図が再現されることは別の条件です。

同じ表の違いでも結果は変わる

標準例題:変更した文字が現れない場合

上の表A、表Bを使います。表Aで「エウウエ」を符号化し、列を変えずに表Bで復号します。各文字は2ビットで、先頭から2ビットずつ区切ります。復号した4文字と一致する位置を全て番号で答えてください。

表Aによる列は11 10 10 11です。表Bで順に読むと「エウウエ」となり、一致する位置は1、2、3、4番目です。使った11と10はそれぞれ両表で同じ文字を表します。表が違うという事実だけから全位置の不一致を結論することはできません。

復号結果を表Bで符号化すると11 10 10 11に戻り、元の列と一致します。また4文字を表Aの入力と照合すると、各位置が一致します。この2つの確認で、列の読み間違いと元の文字との不一致を別々に点検できます。

発展例題:同じ符号列を二通りに読む

表Aと表Bを使い、先頭から2ビットずつ区切った列01 11 00 10 01をそれぞれの表で復号します。5文字ずつ答え、両方の読みが一致する位置を番号で示してください。送信側の文字列を先に仮定せず、与えられた同じ列を両表に通します。

表Aでは「イエアウイ」、表Bでは「アエイウア」です。両方の読みが一致するのは2番目と4番目です。01と00に対応する文字は交換されていますが、11と10の対応は同じです。表Aで得た文字を表Aで再び符号化し、表Bで得た文字を表Bで符号化すると、どちらも指定の列に戻ります。

ここで「表Aで符号化した元の文字列」を知っている場合は、表Aで読んだ結果がその文字列です。しかし符号列だけが与えられ、どの表で作られたか不明なら、どちらの読みが送信者の意図かは決められません。候補を2つ作れることと、正しい表を特定できることは違います。

誤答の始まりを探す

基本例題で「表が違うのでイエアウイと読む」と答えたとします。最初の1文字イは合っていますが、2番目は誤りです。送られた2組目は10で、表Bでもウに対応します。図3はこの最初の食い違いを示します。

図3 基本例題の誤答で最初に違う2番目の対応

図3のように、誤答の2番目エを表Bで符号化すると11です。実際の2組目10に戻りません。誤りの原因は、表の相違を全ての対応の相違とみなし、変更されていない行を確認しなかったことです。10を表Bで引き直してウに直し、残りの組も個別に表と照合します。

別の失敗は、送信時に表Bを使ってしまうことです。表Bで作った列を表Bで読めば元に戻るため、表の食い違いを見落とします。表の上に送る側と読む側を書き、符号化と復号の向きを分ければ、どの段階で表を取り違えたか特定できます。

入力が途中で切れて最後に1ビットだけ残った場合は、2ビットの符号として表を引けません。残ったビットを勝手に補わず、条件不足として止めます。また表外の文字は、その表では符号化できません。符号の重複がある表では、同じ符号から複数の文字が候補になるので、一意な復号を約束できません。これらは表が違うための誤読とは区別する失敗です。

表の異常と読みの成否

2つの表が同じでも、その表自体に同じ符号を2文字へ割り当てた行があれば、受信側はその符号から元の1文字を選べません。逆に各表がそれぞれ一意に読める形でも、表同士の対応が違えば、基本例題のような誤読が生じます。表の内部で区別できるかと、両側で対応が一致するかは別の点検です。

また、完全な長さの組であっても表に登録されていない符号なら、対応する文字を決められません。不完全な組は区切りの条件が満たされず、未登録の組は区切れていても対応がありません。どちらも前後の文字から推測して埋めるのではなく、そこで判定を止めます。問題が補充や訂正の規則を別に与えたときは、その規則を確認してから処理します。

練習:別の表で位置を追う

次の5問では共通して、1文字を3ビットで表します。表Cと表Dはそれぞれ次の4文字と4符号だけを扱い、表Dは表Cの「カ」と「キ」の対応を交換しています。符号100など表にない列は未登録です。区切りは先頭から3ビットずつ、列は途中で変更されないものとします。問題の符号表と入力は自作の条件です。

文字 表C 表D
カ 000 001
キ 001 000
ク 010 010
ケ 011 011
  1. 表Cで「カクケキ」を符号化し、表Dで復号します。送信列を3ビットごとに区切って示し、復号した4文字と一致する位置を答えてください。
  2. 表Cで「ケクケクク」を符号化し、表Dで復号します。送信列と復号した5文字、一致する位置を答えてください。
  3. 列001 010 000 011 000を、表Cと表Dで別々に復号します。それぞれの5文字と、読みが一致しない位置を答えてください。
  4. 表Cで「キカキケカ」を符号化し、表Dで復号します。送信列と復号した5文字、一致しない位置を答えてください。
  5. 表Cで作ったとされる列010 001 10を表Dで復号します。完全な組から読める文字と、最後の部分を一意に読めるかを答えてください。補充の規則はありません。

練習の答えと照合

  1. 送信列は000 010 011 001、復号結果は「キクケカ」です。一致するのは2、3番目です。000と001の読みは交換され、010と011は変わりません。結果を表Dで符号化すると送信列に戻ります。
  2. 送信列は011 010 011 010 010、復号結果は「ケクケクク」です。一致するのは1、2、3、4、5番目です。使われた2種類の符号は両表で同じ対応なので、全位置が一致します。表Dで符号化し直すと同じ5組に戻ります。
  3. 表Cでは「キクカケカ」、表Dでは「カクキケキ」です。一致しないのは1、3、5番目です。それぞれを読んだ表で符号化し直すと001 010 000 011 000になります。同じ符号列でも表によって文字が変わる位置があります。
  4. 送信列は001 000 001 011 000、復号結果は「カキカケキ」です。一致しないのは1、2、3、5番目です。交換対象の文字が繰り返されるので、影響位置も繰り返されます。復号結果を表Dで符号化すると元の5組に戻ります。
  5. 完全な組010と001から、表Dでは「クカ」と読めます。最後の10は2ビットしかないため、一意に読めません。0を足して100にしても、1を足して101にしても表Dには登録がなく、そもそも補充する規則もありません。読めた2文字を表Dで符号化すると010 001に戻り、残りの10は未処理として残ります。

覚えておくこと

つまずきの場所を見分ける

個別に確かめるときは、最初に送信側の文字から符号への矢印を説明できるかを見ます。次に同じ組を受信側の表で逆向きにたどり、元の文字と読んだ文字を位置ごとに比べます。表の差を見つけても、入力にその符号が現れたかを確認していなければ、影響位置を正しく決められません。

答えが違う場合は、最初に食い違う位置の符号を取り出します。そこまでの区切りが正しいか、送る表と読む表を取り違えていないか、受信側の符号から文字を選んだかの順に調べます。不完全な組を完成済みとして扱った場合は、どの条件が足りないかを言葉にします。表の違いは、実際に使われた符号との照合によって初めて位置ごとの違いになります。

もう「日東駒専」を目標にしないでください。

武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。

まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。

本気になった日が、入塾の日。

お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。

電話は年中無休。365日、24時間、お電話可能。

チャットで質問チャット
無料相談を予約する 電話 0422-27-7828電話 LINE チャット
で質問