【論理回路】比較器の設計

比較器とは
比較器の演算内容
最後に
参考文献

比較器とは

ある2つの数値A,Bを比較し、どちらが大きいか判定する演算器です。

判定方法はシンプルです。人間の目で10進数の数値を大小比較するときに考えることを2進数に落とし込むだけです。

もし、A=33,B=4ならば、どちらが大きいかは明白です。A=33です。

どのように判断されましたでしょうか？Bは1桁で、Aは2桁と、そもそもAの方が桁数が多いと答える方が多そうです。

この考え方を論理回路でも用います。

A=33を2進数にすると、[100001]です。B=4を2進数にすると、[100]です。

2進数も、桁数の多いAが大きいことが一目で分かりました。

もし同じ桁数の場合は、1桁目から数字を比較していきます。この動作内容を次章で示します。

比較器の演算内容

Nbitの数値 $A = [a_{N} a_{N - 1} \dots a_{1}], B = [b_{N} b_{N - 1} \dots b_{1}]$ の比較を考えます。

前章で示した指針通り、 $a_{1}, b_{1}$ の比較をまず行います。変数(i=1,2,\ldots,N\)を用いて一般化し、\とし、A,Bを構成するビットのうち、 $i$ ビット目の比較結果を下記のフラグで表します。

比較結果とフラグ

$a_{i} > b_{i}$ のとき、 $f_{1} = 1$ 、 $f_{1} = a_{i} \overset{―}{b_{i}}$
$a_{i} = b_{i}$ のとき、 $f_{2} = 1$ 、 $f_{2} = \overset{―}{f_{1}} ･ \overset{―}{f_{3}}$
$a_{i} < b_{i}$ のとき、 $f_{3} = 1$ 、 $f_{3} = a_{i} \overset{―}{b_{i}}$

$i$ ビット目までのAとBの大小関係の比較結果を、A>B、A=B、A<Bの順に $f_{1, i}, f_{2, i}, f_{3, i}$ とします。

それぞれの成立条件は、下記のように考えることができます。

i

ビット目までのAとBの大小関係の比較方法

$f_{1, i} = 1$ ：
i bit目のAとBの数値がAの方が大きいまたは
i bit目の数値はAとB等しいが、i-1bit目までのAとBの数値がAの方が大きい
$f_{1, i} = f_{1} + f_{2} ･ f_{1, i - 1}$
$f_{2, i} = 1$ ：
i bit目のAとBの数値が等しいかつ i-1 bit目までのAとBの数値も等しい
$f_{2, i} = f_{2} + f_{2} ･ f_{2, i - 1}$
$f_{3, i} = 1$ ：
i bit目のAとBの数値がBの方が大きいまたは
i bit目の数値はAとB等しいが、i-1bit目までのAとBの数値がBの方が大きい
$f_{3, i} = f_{3} + f_{2} ･ f_{3, i - 1}$

上記が全てです。これが分かれば後は論理式の通り回路を組むだけです。

比較器の回路設計

$\begin{matrix} (1) & \begin{aligned} f_{0} & = a_{i} \overset{―}{b_{i}} = a_{i} (\overset{―}{a_{i}} + \overset{―}{b_{i}}) = a_{i} \overset{―}{a_{i} b_{i}} \\ f_{2} & = f_{2} = \overset{―}{f_{1}} ･ \overset{―}{f_{3}} = \overset{―}{f_{1} + f_{3}} \\ f_{3} & = \overset{―}{a_{i}} b_{i} = b_{i} (\overset{―}{a_{i}} + \overset{―}{b_{i}}) = b_{i} \overset{―}{a_{i} b_{i}} \end{aligned} \end{matrix}$