はじめに

簡単なCPUをVHDLやVerilogなどのハードウェア記述言語を使って実装するというのは，大学の情報系学部ではありふれた講義のようです．
そのような講義に触発された僕は，自由研究としてICチップを使ってCPUを自作することを思い付きました．これが最近流行りの自作PCというやつなのですね，多分．
この記事は，自由研究で使おうとしている74181という汎用ロジックICの実装について調査したことをまとめたものになります．

公開されているデータシート[1]の回路図を見ると，ゲート数を削減するために，あまり直感的でないような方法で実装されていることがわかります．
この工夫された実装方法について解明することがこの記事の目的になります．
実は，74181ICの実装について先に書かれている方がおり，その記事[2]を読んで興味を持ったことも，この記事を書くに至った理由の一つです．
この記事では，データシートで決められている32種類の演算に主に着目して，74181ICについて説明することにします．

74181ICについて

よくご存知の方はこの項(またはこの記事全体)を読み飛ばしていただいて構いません．
74181ICとは端的に言えば，ALUを実現する際に有用な様々な論理・算術演算を1つのICに実装したものです．
ここでは，被演算子と演算結果の数値を表すビット列は，アクティブハイの場合のみを考えますが，アクティブローの場合の正当性に関しても最後に考察しています．
データシートによれば，74181ICの入出力信号は主に以下のように決められています．

信号名	入力 or 出力	用途
$A[0..3]$	入力	1つ目の被演算子
$B[0..3]$	入力	2つ目の被演算子
$C_{n}$	入力	キャリー入力
$M$	入力	1ならば論理演算，0ならば算術演算
$S[0..3]$	入力	演算を特定する
$F[0..3]$	出力	演算結果
$C_{n + 4}$	出力	キャリー出力

実現されている演算と，それぞれの演算を行うための入力信号の値は以下のように決められています．
ここで算術演算の和差は$+$ ，$-$ で，論理和は$\lor$ ，論理積の演算子は省略して表します．また，2進数で$"0000", "1111"$と表されるビット列はそれぞれ$0, -1$と表します．

論理演算($M = 1$)，アクティブハイ

$S$	$F$	$S$	$F$	$S$	$F$	$S$	$F$
$0000$	$\overline{A}$	$0100$	$\overline{AB}$	$1000$	$\overline{A} \lor B$	$1100$	$-1$
$0001$	$\overline{A \lor B}$	$0101$	$\overline{B}$	$1001$	$\overline{A \oplus B}$	$1101$	$A \lor \overline{B}$
$0010$	$\overline{A}B$	$0110$	$A \oplus B$	$1010$	$B$	$1110$	$A \lor B$
$0011$	$0$	$0100$	$A\overline{B}$	$1011$	$AB$	$1111$	$A$

算術演算($M = 0$)，アクティブハイ

$S$	$F(C_{n} = 0)$	$F(C_{n} = 1)$	$S$	$F(C_{n} = 0)$	$F(C_{n} = 1)$
$0000$	$A$	$A + 1$	$1000$	$A + AB$	$A + AB + 1$
$0001$	$A \lor B$	$(A \lor B) + 1$	$1001$	$A + B$	$A + B + 1$
$0010$	$A \lor \overline{B}$	$(A \lor \overline{B}) + 1$	$1010$	$(A \lor \overline{B}) + AB$	$(A \lor \overline{B}) + AB + 1$
$0011$	$-1$	$0$	$1011$	$AB - 1$	$AB$
$0100$	$A + A\overline{B}$	$A + A\overline{B} + 1$	$1100$	$A + A$	$ A + A + 1$
$0101$	$(A \lor B) + A\overline{B}$	$(A \lor B) + A\overline{B} + 1$	$1101$	$(A \lor B) + A$	$(A \lor B) + A + 1$
$0110$	$A - B - 1$	$A - B$	$1110$	$(A \lor \overline{B}) + A$	$(A \lor \overline{B}) + A + 1$
$0111$	$A\overline{B} - 1$	$A\overline{B}$	$1111$	$A - 1$	$A$

実装について

先に掲載した演算表は，キャリー入力について同一視すると32種類の演算を定めていますが，明らかに利用しなさそうな演算を含んでいて，恣意的に決められているような印象を受けます．

演算表をこのように決定した意図を探るために，以下のように関数 $f_{S_1 S_0}(A, B)$ を定義します．

\begin{align}
f_{00}(A, B) & = A \\
f_{01}(A, B) & = A \lor B \\
f_{10}(A, B) & = A \lor \overline{B} \\
f_{11}(A, B) & = -1
\end{align}

論理演算

関数 $f_{S_1 S_0}(A, B)$ を用いると，論理演算($M = 1$)の演算表は以下のように変形できます．

$S_3S_2$	$F$
$00$	$\overline{f_{S_1S_0}(A, B)} \lor 0$
$01$	$\overline{f_{S_1S_0}(A, B)} \lor A\overline{B}$
$10$	$\overline{f_{S_1S_0}(A, B)} \lor AB$
$11$	$\overline{f_{S_1S_0}(A, B)} \lor A$

更に，$F$の2項目について$f_{S_1 S_0}(A, B)$ の双対関数 $f^d_{S_1 S_0}(A, B) = \overline{f_{S_1 S_0}(\overline{A}, \overline{B})}$ を用いて変形すると，以下のように表せます．

F = L_{S_3S_2S_1S_0}(A, B) = \overline{f_{S_1S_0}(A, B)} \lor f^d_{\overline{S_3} \overline{S_2}}(A, B)

算術演算

$A + B = (A \lor B) + AB$に注意すると¹，算術演算($M = 0$)についても以下のように変形できます．

$S_3S_2$	$F(c_n = 0)$	$F(c_n = 1)$
$00$	$f_{S_1S_0}(A, B) + 0$	$f_{S_1S_0}(A, B) + 1$
$01$	$f_{S_1S_0}(A, B) + A\overline{B}$	$f_{S_1S_0}(A, B) + A\overline{B} + 1$
$10$	$f_{S_1S_0}(A, B) + AB$	$f_{S_1S_0}(A, B) + AB + 1$
$11$	$f_{S_1S_0}(A, B) + A$	$f_{S_1S_0}(A, B) + A + 1$

論理演算と同様に，双対関数を用いることで更に以下のように変形できます．

F = A_{S_3S_2S_1S_0}(A, B) = f_{S_1S_0}(A, B) + f^d_{\overline{S_3} \overline{S_2}}(A, B) + C_n

論理設計

以上のことを踏まえて，74181ICの実装をふんわりと考えてみると，以下のようになります．

回路の左半分で$f_{S_1S_0}(A, B)$と$f^d_{\overline{S_3} \overline{S_2}}(A, B)$を計算し，回路の右半分でこれらの信号から$F$と$C_n$を計算しています．
データシートにある実際の回路と比較してみると，左半分の回路は一致していて，また右側に加算器のような回路も見当たるため，大きくは異なっていないように思われます．

アクティブローの場合について

アクティブハイの演算表を回路で実現することで，アクティブハイの演算表も実現されることを見てみます．

論理演算

\begin{align}
L_{S_3S_2S_1S_0}(\overline{A}, \overline{B}) & = \overline{f_{S_1S_0}(\overline{A}, \overline{B})} \lor f^d_{\overline{S_3} \overline{S_2}}(\overline{A}, \overline{B}) \\
& = f^d_{S_1S_0}(A, B) \lor \overline{f_{\overline{S_3} \overline{S_2}}(A, B)} \\
& = L_{\overline{S_1} \overline{S_0} \overline{S_3} \overline{S_2}}(A, B) \\
& = \overline{L_{S_1S_0S_3S_2}(A, B)}
\end{align}

最後の行は，$f_{S_1S_0}(A, B)$が$S_1, S_0$の関数として見ると²自己双対関数であることを利用しています．

算術演算

\begin{align}
A_{S_3S_2S_1S_0}(\overline{A}, \overline{B}) & = f_{S_1S_0}(\overline{A}, \overline{B}) + f^d_{\overline{S_3} \overline{S_2}}(\overline{A}, \overline{B}) \\
& = \overline{f^d_{S_1S_0}(A, B)} + \overline{f_{\overline{S_3} \overline{S_2}}(A, B)} \\
& = -(f^d_{S_1S_0}(A, B) + f_{\overline{S_3} \overline{S_2}}(A, B) + 1) - 1 \\
& = \overline{f^d_{S_1S_0}(A, B) + f_{\overline{S_3} \overline{S_2}}(A, B) + 1} \\
& = \overline{A_{\overline{S_1} \overline{S_0} \overline{S_3} \overline{S_2}}(A, B) + 1}
\end{align}

アクティブローにすることで$C_n$が反転することを考えれば，たしかに正しい演算が行われることがわかります．

まとめ

この記事では，演算表に着目して74181ICの回路図の意味を考察し，32種類の演算がとても効率的に，しかもアクティブハイ・ローの両方の場合に適用できるように決められていることを見ました．

課題として残るのは，74181ICの設計者が，どのようにしてこの効率的な演算の組み合わせを発見したのかという点です．何かご存知の方がいらっしゃいましたら是非教えてください．

参考文献

[1] テキサス・インスツルメンツ社『Arithmetic Logic Units/Function Generators datasheet』(https://www.ti.com/lit/ds/symlink/sn54ls181.pdf)
[2] 『74181のお話』(http://diode.matrix.jp/ESSAY/181.htm)

$x \oplus y \oplus c = (x \lor y) \oplus xy \oplus c$，$xy \lor yc \lor cx = (x \lor y)xy \lor xyc \lor c(x \lor y)$より示せる ↩
$f_{A, B}(S_1, S_0)$ということ ↩

74181ICの実装に関する話

はじめに

74181ICについて

実装について

論理演算

算術演算

論理設計

アクティブローの場合について

論理演算

算術演算

まとめ

参考文献