Shift【Turing Complete編】

2023年9月12日

1 はじめに
2 ビットシフト操作
3 Shiftステージ
4 Shiftステージを解く
5 8 Bit Splitterと8 Bit Maker間のワイヤーをずらして倍々を実現する【別解】

はじめに

いつもブログをご覧いただきありがとうございます。

コーストFIRE中のIPUSIRONです😀

IPUSIRONのプロフィールを見る

ビットシフト操作

後日追加予定。

Shiftステージ

Shiftステージのゴールは、8ビット用のシフト回路を組むことです。

最初に入力したビット列に対して、2番目の入力で指定した値だけ左シフトします。

・8ビットの枠から外れた分は切り捨て。

・シフト後に空く桁はOFF（0）で埋める。

入力	・左上のInput端子（VALUE端子）：シフト対象のビット列。8ビット。・右上のInput端子（SHIFT BY端子）：シフトする回数。8ビット。ただし、最大値は7とする。
出力	・Output端子：左シフトした結果。8ビット。

シフト演算には論理シフトと算術シフトがありますが、今回は論理シフトになります。

Shiftステージを解く

1回左シフトすると算術的には2倍になるという事実を使ってみます。

1：ナンバーフォーマットを16進数に切り替える

ステージのクリアには直接影響しませんが、テスト時に流れるデータがわかりやすいようにナンバーフォーマットを切り替えます。「FF」となっていれば、流れるデータが2桁の16進数になります。

2：回路の設計方針を検討する

乗算回路はまだないので、加算回路で2倍を実現します。

「計算対象を2倍すること」と「計算対象の数同士を足し合わせること」では同じ結果が得られます。

・0回左シフト（何もしない）⇒「Valueのまま」

・1回左シフト（1ビット分左シフト）⇒「Valueの2倍（＝Value’）」⇒「Value＋Value」

・2回左シフト（2ビット分左シフト）⇒「Valueの2倍の2倍」⇒「Valueの2²倍」⇒「Value’の2倍（＝Value"）」⇒「Value’＋Value’」

・3回左シフト（3ビット分左シフト）⇒「Valueの2倍の2倍の2倍」⇒「Valueの2³倍」⇒「Value"の2倍（＝Value"’）」⇒「Value"＋Value"」

･･･

・7回左シフト（7ビット分左シフト）⇒「Valueの2⁷倍」

以上でビット操作する処理は大丈夫そうです。

次にそれをどうやって取り出すのかという点について考えます。

これまでたくさんの回路を組んできた中で自然と採用していたテクニックがあります。「全パターンを計算して、どの計算結果を流すのかをスイッチで制御する」というテクニックです。パターン数が10未満といった少数の場合に有効といえます。全パターンを計算するのは効率が悪いですが、回路がすっきりします。

スイッチの制御については、「8 Bit Splitter＋3 Bit decoder」のペアで得られたワイヤー群を活用します。このワイヤー群のうち1本だけにON信号が流れます。つまり、ワイヤーにスイッチをつなげておけば、全パターンのスイッチの1つだけがONになり、1つの計算結果だけを取り出せるというわけです。

3：回路を実装する

8ビット用のAddコンポーネントを使います。このステージ以降、コンポーネントの右上に数字が振ってある赤丸があります。これは対象データのビット数を意味します。

桁上げなどを気にする必要がないので、Input 1ピン、Input 2ピン、Resultピンだけを使います。

4：テストする

テストにパスすると、ステージクリアになります。

次の4つのコンポーネントがアンロックします。

コンポーネント名	コンポーネントの刻印	動作
8 Bit Shift left	SHL	左シフト演算
8 Bit Shift right	SHR	右シフト演算
8 Bit Rotate left	ROL	左ローテート演算
8 Bit Rotate right	ROR	右ローテート演算