高校情報I ビット数と種類数—必要な識別数から足りる桁数の境界を決める｜武蔵野個別指導塾

端末の状態を固定長の符号に割り当て、未使用の列と桁を増やす境界からビット数と種類数を考えます。

よくあるのは、端末に付けた番号の最大値を、そのまま表せる状態の種類数だと考える場面です。0から番号を付ければ、0も1種類として数えます。また、状態名に付けた符号を数として読むことと、符号の並びを識別の目印として使うことは別です。どちらを尋ねられているかを確かめ、必要な状態が収まる最小のビット数を選びましょう。

問題で求められるものを分ける

1つ目の型は、ビット数から作れる符号の種類数を求める問題です。各桁に0か1を置き、各桁の選び方を組み合わせます。続けて、符号を0以上の整数として読む場合の最大値を聞かれることもあります。この2つは同じ答えではありません。

2つ目の型は、必要な状態数から最小のビット数を選ぶ問題です。足りる候補を1つ挙げるだけでは最小とは言えません。その候補で足りることと、1桁少ない候補では足りないことを両方示します。ちょうど収まる数の次に状態が増えたとき、境界を越えます。

3つ目の型は、符号表に状態を割り当てた後の点検です。使わない並びを数えたり、受け取った並びが表にない場合の扱いを考えたりします。符号の種類数には、表で実際に使ったものも、まだ使っていないものも含まれます。以下の数や対応は学習用に設定した条件であり、実在する端末の規格を表していません。

桁の選択肢と状態の対応

ビットは0または1を表す単位です。固定長符号では、どの状態にも同じ桁数のビット列を割り当てます。1桁なら0と1の2通りです。2桁なら、最初の桁のそれぞれに対して次の桁を0か1にできるため4通りです。1桁増やすたびに各列の末尾に0を付けた列と1を付けた列ができ、種類数は2倍になります。

図1のように、3ビットでは8通りの列ができます。桁数をnとすると、種類数は2をn個掛けた数、すなわち2のn乗です。たとえば4ビットは2の4乗で16通りです。桁数と種類数を同じ数として扱わないようにしましょう。

図1の右端は作れる列の数であって、必ず割り当てる状態の数ではありません。異なる状態を区別するには、異なる列をそれぞれに割り当てます。反対に、同じ列を2つの状態に割り当てると、その列を受け取った側はどちらかを一意に決められません。

符号を0以上の2進整数と見なす場合、3ビットの最小は000、最大は111です。10進数では0から7までなので、最大値は7です。0を含めて数えると8個あります。最大値が7であることと、種類数が8であることは矛盾しません。先頭の0も固定長の列の一部として残します。たとえば001と1は数値として同じですが、3桁で書く指定には001が必要です。

必要な状態数をN、桁数をnとすると、足りる条件はN ≤ 2のn乗です。Nが正の整数で、nを正の整数として選ぶ問題なら、最小のnについては、1桁少ない場合も比べます。nが2以上なら、2の(n-1)乗 < N ≤ 2のn乗が境界を表します。1ビットで足りる場合も、問題が0ビットを候補に含めるか確認します。ここでは問題ごとに候補の下限を定めます。

必要数が作れる数より少なければ、その差は未使用の符号の数です。未使用の列に勝手な状態を読み取ることはできません。受信時には表にないことを示し、原因を確認するなど、扱いを別に決める必要があります。未使用の列があるからといって、現在の表に状態が追加済みであるとは限りません。

基本例題：端末の状態を5種類に分ける

ある端末の状態を「待機」「準備」「動作」「停止」「点検」の5種類に分けます。各状態に異なる固定長の2進符号を1つずつ割り当てます。符号は少なくとも1ビットとし、最小のビット数と未使用の符号数を整数で求めてください。さらに、1つの割当例を先頭の0を省かずに示してください。

まず2ビットでは、00、01、10、11の4通りです。5種類には1通り不足します。3ビットでは2の3乗で8通りですから、5種類に異なる列を配れます。2ビットが不足し3ビットが足りるので、最小は3ビットです。8から5を引くと、未使用は3通りです。

図2のように、待機を000、準備を001、動作を010、停止を011、点検を100にできます。残る101、110、111は未使用です。割当はこの順序に限りませんが、異なる状態に同じ列を使わない条件は必要です。

図2の表を逆にたどると、010は動作、100は点検に戻ります。一方、101は表にないため、どの状態かは決められません。5つの使用列と3つの未使用列を合わせて8通りとなり、3ビットで作れる列の数とも一致します。列の総数を元の条件と照合すると、数え漏れを見つけやすくなります。

標準例題：境界を越える追加

別の端末では12種類の状態を区別します。各状態に異なる固定長の2進符号を付け、桁数は少なくとも1とします。最小のビット数と未使用数を整数で答え、状態が重複なく16種類、さらに17種類へ増えた場合もそれぞれ答えてください。

3ビットは8通りなので12種類に足りません。4ビットは16通りなので収まります。最小は4ビット、未使用は16から12を引いて4通りです。状態が16種類なら、4ビットの全16通りを使ってちょうど収まり、未使用は0通りです。15種類目から16種類目への追加は、空いている最後の列で対応できます。

17種類になると4ビットでは1種類足りません。5ビットなら32通りなので、最小は5ビット、未使用は32から17を引いた15通りです。境界の前後で未使用数が大きく変わるのは、1桁増えた結果、利用可能な列が16通りから32通りへ倍増するためです。

検算では、それぞれ使用数と未使用数を足します。12と4で16、16と0で16、17と15で32となり、それぞれの桁数の総数に戻ります。5ビットにした後、元の4ビットの列をそのまま混ぜるのではなく、例えば先頭に0を付けて5桁にそろえる必要があります。実際の移行では、送り手と受け手が同じ新しい表を使うように決めます。

発展例題：最大値から必要数へ戻る

表示する番号を0から23までの整数とし、各番号を同じ桁数の2進数で表します。桁数は少なくとも1とします。最小のビット数、使わない列の数、最大番号23をその桁数の2進数で答えてください。表示範囲の外の整数には符号を割り当てません。

0から23までは、23に0の分を加えて24種類です。4ビットでは0から15までの16種類しか表せません。5ビットでは0から31までの32種類を表せるので、最小は5ビットです。未使用は32から24を引き8通りです。使わない列は数値で読むと24から31に対応します。

23は16、4、2、1の和なので、5桁では10111です。逆に10111を10進数に戻すと16と4と2と1の和で23になります。0から23まで24個を使い、24から31まで8個を使わないと数えれば、合計は32個です。最大番号23を種類数と誤認すると、未使用数も1つ多くなるため、範囲の両端を先に書き出します。

状態の追加を見込んで最初から余裕のある桁数を選ぶ設計も考えられます。ただし、必要最小の桁数を問う問題では、将来の追加を条件に含めず、今の状態数で判断します。逆に追加後も同じ桁数を使うよう条件があるなら、追加後の合計を基準にします。何を数えるかは、現在の数と将来の数を分けて問題文から読み取ります。

符号の並びに名前を付ける順番は自由ですが、表を変更すれば同じ列が別の状態を指すことがあります。新旧の表が混在したまま列だけを渡すと、同じ列でも読み取り結果が変わります。そのため、表を使う双方で対応をそろえるという条件も、識別を考える際に欠かせません。

誤答の手前で立ち止まる

基本例題で「3ビットの最大値は7だから、状態は7種類まで」と答えたとします。図3のように、0を最初の番号として使うと、0から7までの番号は8個です。最大値は最後の番号、種類数は並びの個数として別々に記録しましょう。

図3の対応を戻して確認すると、000から111までの8列に0から7までの8個の数が対応します。最大値7に1を足した8が種類数です。ただし、この関係を使うのは0から連続して番号を付ける場合です。途中を飛ばす状態番号なら、実際に使う番号を数えます。

別の誤りは「5種類には2ビットでよい」として、5番目の状態にも既存の列を再利用することです。その表では受信した列から状態を1つに戻せません。必要数と総数の大小を先に比較し、不足するときは桁数を増やしてから表を作ります。

また、未使用の列を受け取った場合に、似た列の状態へ自動的に置き換えると、停止を動作と読み違えるおそれがあります。問題の条件に訂正規則がなければ、表にない列として扱います。列の欠落や桁数の不一致も、状態として復号できない入力です。たとえば3桁の表に01が届いたときは、先頭に0を勝手に補う前に、固定長の条件を満たしていないことを確かめます。

練習：条件を読み、境界を示す

各問で符号は固定長の2進符号とし、ビット数は1以上の整数とします。異なる対象には異なる列を割り当てます。答えの数は整数で示し、符号は指定された桁数で先頭の0を残してください。

1. 6ビットで作れる符号は何種類ですか。また、それらを0以上の整数として読むと最大値はいくつですか。いずれも10進数で答えてください。
2. 貸出札の区分が9種類あります。最小ビット数と未使用の符号数を求めてください。さらに、区分が重複なく1種類増えたときの最小ビット数と未使用数も答えてください。
3. 棚の番号を0から18まで付けます。各番号を2進数で表す最小ビット数と未使用の列の数を求め、18をその桁数の2進数で書いてください。
4. ある係は7種類を3ビットで区別し、後に2種類を追加したいと考えました。3ビットのままで足りるか、足りない場合は最小何ビットか、理由とともに答えてください。変更後の未使用数も求めてください。
5. 2ビットの表で、00を空き、01を使用中、10を点検中とします。11を受け取った場合と、1桁の1を受け取った場合をそれぞれどう扱うべきですか。判断の根拠と、状態を決めるために不足する条件を述べてください。

練習の答えと確かめ方

1. 6ビットでは2の6乗で64種類です。0から連続した整数として読むと最大値は63です。0から63までを数え直すと64個なので、最大値と種類数は区別できます。

2. 3ビットでは8通りで不足し、4ビットでは16通りなので最小は4ビットです。未使用は16から9を引いた7通りです。10種類になっても4ビットで足り、未使用は6通りです。9と7、10と6のいずれも合計16となり、4ビットの全列に戻ります。

3. 0から18までは19種類です。4ビットの16通りでは不足し、5ビットの32通りなら足りるので、最小は5ビットです。未使用は13通りです。18は16と2の和なので10010です。10010を10進数に戻すと18であり、使用する19通りと未使用の13通りを合わせると32通りです。

4. 追加後は9種類なので、8通りの3ビットでは1種類足りません。4ビットなら16通りですから最小は4ビットで、未使用は7通りです。9種類に7通りを加えると16通りに戻ります。追加前に空いていた1列だけでは、2種類の追加を区別できません。

5. 11は2桁ですが、提示された表には対応する状態がありません。未使用の列として扱い、状態を決めずに表や入力を確認します。1は表の2桁という条件を満たさないので、桁数の不一致として扱います。いずれも、対応の追加や欠落時の扱いについての取り決めが不足しています。勝手に状態を決めると元の表から復元できません。

覚えておくこと

• nビットの固定長符号は2のn乗通りです。
• 0から連続する整数として読む場合、最大値は種類数より1小さくなります。
• 最小桁数は、その桁で足りて1桁少ないと足りないことを示します。
• 未使用数は作れる列の総数から割当済みの列数を引いて求めます。
• 表にない列や桁数の違う入力は、条件なしに状態へ決めつけません。

自分の答案を点検する

桁数を選べないときは、必要数、1桁少ない総数、選んだ桁の総数を横に並べてください。最大値を間違えるときは、0を含む番号を小さい例で実際に数えると原因が見えます。個別指導では、本人が作った対応表の重複や未使用列を確認し、列から元の状態に戻せるかを説明してもらいます。式だけでなく、足りない場合に何が区別できなくなるかまで言葉にすると、境界の意味が残ります。