半加算器と全加算器を使って手で計算

応用情報技術の本で勉強を進めていて、本では理解ができず、理解しようとして時間を結構使いました。最終的に、理解しようとした翌日には理解できたので忘れないうちにメモを書きます。

ググったり動画とか見てもさっぱり分からなかったのが、理解できるきっかけになったのがこちらの記事です。

基本情報でわかる 論理演算 「真理値表を書けば、半加算器と全加算器の仕組みがわかる」

全加算器で重要なのは、実際に全加算器を机上で使って手で計算してちゃんと結果が出せるということだと思い、手で試しました。

大切なのは、1回の全加算器で出力される値は1桁どうしの和と次の桁に持ち越す値だということ。初めてということもあってか、ここが最初はなぜか理解できなかった。最終的なｃとsとc'の値をどのように扱うのかも分からなかった。いろんなサイトなどで調べたけど、この部分の説明がなぜか抜け落ちていたので、どれも初心者目線を忘れたひとが作ってたのかも。

上記から、複数桁がある足し算だと、最低でも桁数分は全加算器での計算を繰り返さないといけないということが自然と分かります。

例
二進数で101+101= 1 0 1 0 となる計算を全加算器を使って計算すると下記のような手順になります。

1桁目の和 = 0 →2桁目に桁上がりする
2桁目の和 = 1
3桁目の和 = 0 →4桁目に桁上がりする。
4桁目の和 = 1 →4桁目は存在しないが3桁目の桁上がり分が4桁目として来る。

x、ｙ：桁毎の、足し算する対象の数値
c ：次の桁へ持ち越しする数値（Carryの略）
s：その桁の和（Sumの略）
c'：一つ前の桁から持ち越してきた数値

ｃは論理積（AND）で計算された値：ｘもｙも1のときだけ1を出力する。
ｓは排他的論理和（XOR）で計算された値：ｘかｙのどちらかが1のときだけ1を出力する。

ｃが2回計算されるけど、どちらかが1であれば、1を出力するように論理和を使う。2回計算されるｃのどっちかが1であれば、1桁上がりすることになるため。これは普通に2進数の1 + 1の足し算を考えてみたら理解できる。

1桁目の計算：1 + 1
(1)1つめの半加算器
x=1
y=1
c=1
s=0

(2)2つめの加算器
s=0
c’=0 (1桁目なので前の桁からの持ち越しなし)
c=0
s=0

1桁目の最終的な値(c=次の桁への持ち越しの値、s=その桁の解（和）)
c=1
s=0

2桁目の計算：0 + 0
(1)1つめの半加算器
x=0
y=0
c=0
s=0

(2)2つめの半加算器
s=0
c’=1
c=0
s=1

2桁目の最終的な値(c=次の桁への持ち越しの値、s=その桁の解（和）)
c=0
s=1

3桁目の計算：1 + 1
(1)1つめの半加算器
x=1
y=1
c=1
s=0

(2)2つめの半加算器
s=0
c’=0
c=0
s=0

3桁目の最終的な値(c=次の桁への持ち越しの値、s=その桁の解（和）)
c=1
s=0

4桁目
(1)
x=0
y=0
c=0
s=0

(2)
s=0
c’=1
c=0
s=1

最終的
c=0 (c=0なので桁上がりしないのでこの桁で計算は終了)
s=1

以上で、1桁目から4桁目までの計算が完了
3桁目で桁上がりしているので4桁目をx=0、y=0として計算している。
(101+101→0101+0101)
1桁目から4桁目の値となる、最終的なsの値を並べると、1010となり正しく足し算の結果が出ました。