[A] 2ビットのデータ入力 A,B と2ビットの制御入力 P,Q ，及び，2ビットのデータ出力 X,Y を持つ「1ビット シフタ(shifter; 移動器)」を4入力2出力の組み合わせ回路 L として設計してみよう．このシフタでは，表1の機能表に示すように，2ビットデータ入力 A B を，制御入力 PQ に従って，PQ = 00のとき無操作(シフト無し)，PQ = 01のとき左1ビットシフト，PQ = 10のとき右1ビットシフト，PQ = 11のとき交換(循環シフト)，の各操作をして2ビットデータ出力 X,Y とする．ただし，表1の機能表において，α(シフトした後の空いたビットを埋める論理値)は "0", "1", "−"(ドントケア) のいずれかであり，α＝0 とするシフタを L₀ ，α＝1 とするシフタを L₁ ，α＝−(ドントケア) とするシフタを L' とする．この3種類の1ビットシフタ L₀,L₁,L' を設計する．また，L₀ における2ビット出力を X₀ Y₀ ，L₁ における2ビット出力を X₁ Y₁ ，L' における2ビット出力を X' Y' ，とする．次の問すべてに答えなさい．

表1
P	Q	X	Y	操作
0	0	A	B	無操作
0	1	B	α	左シフト
1	0	α	A	右シフト
1	1	B	A	交換

(1) 表1のシフタ機能表を展開(論理変数を論理定数に変換)してできる下記の真理値表の空白部分(出力値)を埋めて完成しなさい．

(2) (1)を下記のカルノー図に写し，それぞれ2段論理最小化して，各回路出力 X₀ Y₀ ，X₁ Y₁ ，X' Y' それぞれの最小(最簡)積和形論理式を求めなさい．

(3) (2)で設計した L₀,L₁,L' のうち，空間サイズが最小のものはどれか，理由を添えて示しなさい． なお，論理回路の空間サイズは「2入力ANDゲートと2入力ORゲートの総数」によって計るものとする．

(4) (2)で設計した X₀ Y₀,X₁ Y₁,X' Y' のうち，ファクタリング(多段論理最小化)できるものがあれば，ファクタリングした後の論理式を示しなさい．

(5) (2)で設計した L₀,L₁,L' を2入力ANDゲートと2入力ORゲート(とNOTゲート)だけで構成(テクノロジマッピング)し，それぞれAND-OR回路とする．このとき，2本の出力 X,Y が共有論理ゲートを持ち，論理回路 L 全体のさらなる空間最適化が図れるもの(L₀,L₁,L' のいずれか)が１つある．その共有論理ゲートによる空間最適化を行ったAND-OR回路図を示しなさい．L₀,L₁,L' のいずれであるか，入力 A,B,P,Q と出力 X,Y を明示すること．

(6) (5)のAND-OR回路をすべての論理ゲートが2入力NANDゲートから成るNAND回路に変換し，その論理回路図を示しなさい．

[B] [A]で設計した「1ビットシフタ」を，今度は，2個のTフリップフロップ（FF_A, FF_Bとし，その状態(＝出力)をそれぞれ A, B とする）を用いる同期式順序回路 C として設計してみよう．このシフタの機能は[A]と同様であり，表2の状態遷移表に従う．ただし，[A]でシフト対象となったデータ入力の代わりに，この順序回路では，2ビットの状態 A, B をシフト対象とする． すなわち，このシフタでは，表2の機能表に示すように，2ビット(T-FF)の現状態 A B を，順序回路への制御入力 PQ に従って，PQ = 00のとき無操作(シフト無し)，PQ = 01のとき左1ビットシフト，PQ = 10のとき右1ビットシフト，PQ = 11のとき交換(循環シフト)，の各操作をして2ビット(T-FF)の次状態 A⁺ B⁺ とする．ただし，表2の状態遷移表において，α(シフトした後の空いたビットを埋める論理値)は "0", "1", "−"(ドントケア) のいずれかであり，α＝0 とするシフタを C₀ ，α＝1 とするシフタを C₁ ，α＝−(ドントケア) とするシフタを C' とする．この3種類の1ビットシフタ C₀,C₁,C' を設計する．また，FF_A と FF_B の各T入力については，C₀ のそれを T_A0 T_B0，C₁ のそれを T_A1 T_B1，C' のそれを T_A' T_B'，とする．さらに，入力と状態遷移はクロックによって同期することを前提とするが，解答(論理式や論理回路図など)では，クロックは無視/省略しなさい．次の問すべてに答えなさい．

表2
P	Q	A+	B+	操作
0	0	A	B	無操作
0	1	B	α	左シフト
1	0	α	A	右シフト
1	1	B	A	交換

(1) 表2の状態遷移表を展開(論理変数を論理定数に変換)してできる下記の展開状態遷移表(真理値表)の空白部分(次状態値)を埋めて完成しなさい．

(2) (1)で作成した展開状態遷移表と右記のT-FFの入力要求表によって，(1)の展開状態遷移表の右側に各T入力要求欄(6列)を連結し，拡大入力要求表を完成しなさい．

(3) (2)を下記のカルノー図に写し，それぞれ2段論理最小化して，T_A0 , T_B0 , T_A1 , T_B1 , T'_A, T'_B それぞれの最小(最簡)積和形論理式を求めなさい．

(4) (2)で設計した C₀,C₁,C' のうち，空間サイズが最小のものはどれか，理由を添えて示しなさい． なお，論理回路の空間サイズは「2入力ANDゲートと2入力ORゲートの総数」によって計り，T-FF(を構成する基本論理ゲート数)分は勘定に入れないものとする．

(5) C₀,C₁,C' のうち，(4)で空間サイズが最小としたもののT入力(T_A, T_B)がさらにファクタリング(多段論理最小化)できれば，ファクタリングした後の論理式を示しなさい． T_A0 , T_B0 , T_A1 , T_B1 , T'_A, T'_B のいずれであるか明記すること．

(6) (5)で最適化設計した順序回路 C (C₀,C₁,C' のいずれか)を2入力ANDゲートと2入力ORゲート(とNOTゲート)だけで構成(テクノロジマッピング)し，AND/OR回路とする．このとき，2本のT入力 T_A, T_B が共有論理ゲートを持てば論理回路 C 全体のさらなる空間最適化が図れることに注意して，その共有論理ゲートによる空間最適化を行ったAND/OR回路図を示しなさい．C₀,C₁,C' のいずれであるか，制御入力 P,Q を明示すること．また，回路図では，FFの内部をAND-OR回路で示す必要はなく，T-FFは解答欄の記号を用いなさい．