5つの状態をもつ順序回路を、状態を2進数で符号化して D フリップフロップで実現するとき、必要なフリップフロップの最小個数はいくつか。

解説

正解は「3」です。k 個のフリップフロップで表せる状態は $2^k$ 通りなので、5つの状態を区別するには、$2^k$ が5以上になる最小の k を求めます。$2^2=4$ では足りず、$2^3=8$ で足りるので、3個必要です。使われない3通りの符号は、フリップフロップの入力関数を簡単化するときにドントケアとして利用できます。「2」では4通りしか表せず、5つ目の状態を区別できません。「4」は必要以上の個数です。「5」は状態ごとにフリップフロップを1個ずつ割り当てるワンホット符号化の個数で、回路が単純になる利点はありますが、最小ではありません。