当サイトの一部ページには、アフィリエイト・アドセンス・アソシエイト・プロモーション広告を掲載しています。

Amazonのアソシエイトとして、Security Akademeiaは適格販売により収入を得ています。

広告配信等の詳細については、プライバシーポリシーページに掲載しています。

消費者庁が、2023年10月1日から施行する景品表示法の規制対象(通称:ステマ規制)にならないよう、配慮して記事を作成しています。もし問題の表現がありましたら、問い合わせページよりご連絡ください。

参考:令和5年10月1日からステルスマーケティングは景品表示法違反となります。 | 消費者庁

Unsigned Less【Turing Complete編】

大小比較器

大小比較器(マグニチュードコンパレーター)とは、2つ入力を比較して、どちらが大きいか、あるいは等しいかを判定する回路です。

1ビット大小比較器

1ビットの入力が2つあり、その大小を識別する回路です。

1ビット大小比較器

真理値表

ABA=BA<BA>B
00100
01010
10001
11100
1ビット大小比較器の真理値表

デジタル回路

※AとBに関係するラインを色分けしました。

若干複雑に見えます。これはA=Bのときに1を出力する回路が「2つのANDゲート+ORゲート+2つのNOTゲート」と多数の拭くゲートを組み合わせているためです。この回路は一致回路であり、不一致回路と等価であるXORゲートとNOTゲートを組み合わせた回路に置き換えられます。

XOR回路にNOTゲートを追加してもよいのですが、XOR回路の内部構成によってはすでに出力直前にNOTゲートを使って折り、その際はこれを取り除けばよいのです。

以上を踏まえて回路を書き換えると次のようになります。回路の意味が明確になり、ワイヤリングもすっきりしています。

※Component previewにピンがすべて表示されるように、入力端子を離して配置しました。またわかりやすいようにラベル名も設定しています。

2ビット大小比較器

2ビットの入力が2つあり、その大小を識別する回路です。

A=A2A1、B=B2B1とします。

論理式

それぞれの出力の論理式がわかれば、基本論理素子で回路を組めます。

LTの論理式

A<Bの場合は、次の2通りに分けられる。

(a) A2<B2のとき

A2=0かつB2=1

$LT1 = \overline{A2} \cdot B2$

(b)「A2=B2」かつ「A1<B2」

$LT2 = \overline{A2 \oplus B2} \cdot ( \overline{A1} \cdot B1)$

※$\oplus$はXORを意味します。XORしてからNOTを取っているというXNORです。XORは不一致回路であることを思い出してください。不一致回路を反転させると一致回路ということです。

したがって、

$LT=LT1 + LT2$

EQの論理式

A=Bの場合は、「A2=B2」かつ「A1=B1」のときになります。

$EQ= \overline{A2 \oplus B2} \cdot \overline{A1 \oplus B1} $

GTの論理式

A>の場合は、次の2通りに分けられます。

(a)A2>B2のとき

$GT1 = A2 \cdot \overline{B2}$

(b)「A2=B2」かつ「A1>B2」のとき

$GT2= \overline{A2 \oplus B2} \cdot (A1 \cdot \overline{B1})$

したがって、

$GT=GT1 + GT2$

デジタル回路

自然と拡張版1ビット大小比較器が得られた

2ビット大小比較器は1ビット大小比較器を2つ組み合わせることで構築できました。

次のように破線で囲んだ回路を考えます。すると、対称とする桁の入力と下位の桁からの判定結果に対して、全体の判定結果を出力する回路になっています。この回路を拡張版1ビット大小比較器と名づけます。

拡張版1ビット大小比較器を標準として作っておくといろいろと便利です。右上の部分の回路を考える必要がなくなるのです。

2つ並べてつなげれば2ビット大小比較器になりますし、3つ並べてつなげれば3ビット大小比較器になります。ただし、最下位に対応する拡張版1ビット大小比較器の接続用ピンについては、初期入力として「A>B」ピンを0、「A=B」ピンを1、「A<B」ピンを0とします。

変形版2ビット大小比較器

通常の大小比較器は3つのケースそれぞれの出力がありました。

状況によっては、それぞれのケースを識別するのではなく、特定のケースのみに1を出力させたいことがあります。

※例えば、Unsigned Lessステージで組む回路もそうです。

「A=B」のときに1を出力するのであれば、一致回路なので、XNORそのものです。

問題は「A<B」か「A>B」のときになります。今回は「A<B」のときについて解説しますが、「A>B」についても一般性を失いません。

変形版2ビット大小比較器

4ビット大小比較器

4ビットの入力が2つあり、その大小を識別する回路です。

A=A4A3A2A1、B=B4B3B2B1とします。

2ビット大小比較器から4ビット大小比較器を構築する

作りたい回路は上記の4ビット大小比較器です。

[1]最上位2桁A4A3とB4B3の比較

2ビット大小比較器を使って、入力としてA4A3とB4B3を与えます。

3つの出力を次のように定義します。

[2]最上位2桁A2A1とB2B1の比較

[1]と同様に次のように定義します。

[3]最終的な出力を決定する

・LTが1になるには、LTupper or 「EQupperかつLTlower

・EQが1になるには、EQupperかつEQlower

・GTが1になるには、GTupper or「EQupperかつGTlower

4ビット大小比較器の内部構成は次のようになります。

同様なやり方で、4ビット大小比較器から8ビット大小比較器を構築できます。これは一般化できます。

2nビット大小比較器から、2n+1ビット大小比較器を構築できるのです。

今までの構築例について、nに注目してみます。

・1ビット(=20)大小比較器から2(=20+1)大小比較器

・2ビット(=21)大小比較器から4(=21+1)大小比較器

・4ビット(=22)大小比較器から8(=22+1)大小比較器

8ビット大小比較器

拡張版4ビット大小比較器から8ビット大小比較器を構築する

接続用の入力を備えた、拡張版4ビット大小比較器を考えます。

これを2つ使って、8ビット大小比較器を構築するには、次のように接続するだけです。

半減算器から大小比較器を作る

半減算器の入出力については、以下のWebページを参照ください。

Unsigned Lessステージ

Unsigned Lessステージのゴールは、1番目の入力が2番目の入力より小さければONを出力する回路を組むことです。

ただし、入力バイトデータは符号なし(Unsigned)として解釈するものとします。

Unsigned Lessステージを解く

1:回路の設計を検討する

Equalityステージの別解で紹介した、前段の回路を見てください。

本ステージでは一致ではなく、大小を識別することになります。

大小を識別する基本戦略は、減算してゼロより大きいか小さいかを調べることになります。

8ビット用の減算コンポーネントはありません。

※ALUコンポーネントは減算をサポートしていますが、本ステージでは使えません。

AとBについて3つのパターンが考えられます。具体的なビット列で、Addの出力結果がどう変わるのかを確認してみます。Carry Outピンに注目するのがポイントです。

ケースA(上のInput端子)B(下のInput端子) ̄B(Bのビット反転)Add(A,  ̄B)のCarry OutピンAdd(A,  ̄B)のResultピン
A=B0110 0110b0110 0110b1001 1001b01111 1111b
A>B0110 0110b0001 1101b1110 0010b10100 1000b
A<B0010 0001b1001 1100b0110 0011b01000 0100b
前段の回路

本ステージは「A<B」を確定的に知りたいわけですが、残念ながらCarry Outピンに注目しても「A<B」のケースを確定できません。

なぜなら0になるのは「A<B」だけでなく「A=B」のケースも含まれるためです。

※逆に「A>B」を識別する回路は、前段の回路をそのまま流用して、出力端子に接続すれば実現できます。

しかし、この考察は無駄ではありません。前段の回路を少し変更を加えれば、うまくいきそうであることがわかります。それは、下のInput端子側の8 Bit NOTコンポーネントを外して、代わりに上のInput端子側に配置するのです。

以上の考察を踏まえて、回路を組むと次のようになります。

実際にテストする前に、表を使って手計算で確認してみます。

ケースA(上のInput端子)B(下のInput端子) ̄A(Aのビット反転)Add( ̄A, B)のCarry OutピンAdd( ̄A, B)のResultピン
A=B0110 0110b0110 0110b1001 1001b01111 1111b
A>B0110 0110b0001 1101b1001 1001b01011 0110b
A<B0010 0001b1001 1100b1101 1110b10111 1010b
修正版の回路

Carry Outピンが1になるのは、「A<B」のケースのみです。つまり、Carry Outピンに注目することで、「A<B」を識別できるわけです。

2:回路を実装する

シミュレーター上に、上記に示した修正版回路(上に8 Bit NOTコンポーネントがある回路)を組んでください。

3:テストする

クリアすると、Unsigned Lessコンポーネントがアンロックします。