論理ゲートから加算器へ

コンピュータは「計算」ができるわけではない——論理ゲートを積み木のように重ねているだけだ。この講義では、XOR・AND・OR ゲートを使って足し算ができる回路を実際に組み立て、半加算器から全加算器、そして4ビット加算器へと段階的に構築していく。


日常の足し算——筆算の示唆

紙の上で足し算をする過程を思い出してみよう。計算:37 + 58:

まず一の位を計算する:7 + 8 = 15、書く5,繰り上がり 1。

次に十の位を計算する:3 + 5 + 繰り上がり 1 = 9、書く9、結果は95。

この過程は3つの重要なポイントを明らかにしている:

1. 桁ごとの計算:各桁は自分の2つの加数と下位からの繰り上がりのみを考慮する。

2. 桁上げの伝搬:下位の計算で桁上げが発生することがあり、その桁上げは上位へ伝えなければならない。

3. 最下位は特殊:最下位にはそれより下位からの桁上げがないため、2つの加数だけを処理すればよい。

コンピュータの足し算も同じ考え方だ。大きな問題(複数桁の加算)を多くの小さな問題(1ビット加算)に分割し、1つずつ解決していく。

半加算器——最下位の 1 ビット加算

最下位には桁上げ入力がないため、2つの1ビットの2進数を加算するだけでよい。このような場合を処理できる回路を半加算器(Half Adder)。

半加算器には2つの入力 A と B、そして2つの出力がある:和ビット Sumと桁上げ Carry。

半加算器の真理値表:

ABSum(和)Carry(桁上げ)
0000
0110
1010
1101

真理値表を眺めると、驚くべき偶然が浮かび上がる:

Sum = A XOR B。A と B が異なるとき Sum=1、同じとき Sum=0——これはまさに XOR ゲートの真理値表である。

Carry = A AND B。2つの入力がともに 1 のときだけ桁上げが発生する——これはまさに AND ゲートの真理値表である。

半加算器は1 つの XOR ゲート + 1 つの AND ゲートだけで実現できる。ジョージ・ブールでさえ、自分が発明した代数システムがいつか加算器の数学的基盤になるとは思ってもみなかっただろう。

全加算器——桁上げを処理する完全な加算

半加算器には致命的な欠陥がある:下位からの桁上げを受け取れないことだ。。最下位を除き、各桁は A、B、下位からの桁上げ Cin の3つの数を処理しなければならない。

2つの加数と1つの桁上げ入力を同時に処理できる回路を全加算器(Full Adder)。

全加算器の真理値表:

ABCinSumCout
00000
00110
01010
01101
10010
10101
11001
11111

巧妙な設計がある:2つの半加算器を使えば全加算器を組み立てられる。。

ステップ1:半加算器1が A と B を処理し、中間和 S1 と桁上げ C1 を得る。

ステップ2:半加算器2が S1 と Cin を処理し、最終和 Sum と桁上げ C2 を得る。

ステップ3:最終的な桁上げCout = C1 OR C2(どちらかの半加算器が桁上げを生成すれば、最終的に桁上げを出力する)。

全加算器の回路構成:2つの半加算器 + 1つの OR ゲート。層を重ねるように、各半加算器の内部もまた XOR + AND でできている。この階層的に構築する考え方は、コンピュータのアーキテクチャ全体に貫かれている。

カスケード接続の全加算器——4ビット・リップルキャリー加算器

全加算器があれば、複数ビットの加算は簡単だ:複数の全加算器を直列につなぎ、下位の桁上げ出力を上位の桁上げ入力に接続する。。

4ビット加算器のカスケード構造:

第0ビット(最下位):全加算器が A0、B0 を処理し、桁上げ入力 = 0、和 S0 と桁上げ C0 を生成する。

第1ビット:全加算器が A1、B1 を処理し、桁上げ入力 = C0、和 S1 と桁上げ C1 を生成する。

第2ビット:全加算器が A2、B2 を処理し、桁上げ入力 = C1、和 S2 と桁上げ C2 を生成する。

第3ビット(最上位):全加算器が A3、B3 を処理し、桁上げ入力 = C2、和 S3 と桁上げ C3(最終桁上げ)を生成する。

桁上げは水の波のように下位から上位へと段階的に「伝わっていく」。このため、この構造をリップルキャリー加算器(Ripple Carry Adder)。

リップルキャリー加算器はシンプルで分かりやすいが、性能上のボトルネックがある。最悪の場合、桁上げは第0ビットから最上位まで伝播し、N段の全加算器の遅延を経る。現代の CPU は桁上げ先読み(Carry Lookahead)などの技術で最適化しているが、リップルキャリーを理解することは、あらゆる加算器の最適化を理解するための前提である。

Python コードのデモ

実例

# ============================================
# 第8回:論理ゲートから加算器へ - Python デモ
# サンプル チュートリアルシリーズ
# ============================================

def half_adder(a, b):
    """
半加算器:2つの1ビット2進数を加算し、桁上げ入力を考慮しない。

引数:
a, b: それぞれ 0 または 1

戻り値:
(sum_bit, carry_out): 和ビットと桁上げ

回路の実装:
sum_bit = a XOR b (XORゲート)
carry_out = a AND b (ANDゲート)
    """

    sum_bit = a ^ b      # XOR:同じなら 0、異なれば 1
    carry_out = a & b    # AND:両方が 1 のときだけ桁上げ
    return sum_bit, carry_out


def full_adder(a, b, carry_in):
    """
全加算器:2つの1ビット2進数を加算し、桁上げ入力を考慮する。

引数:
a, b, carry_in: それぞれ 0 または 1

戻り値:
(sum_bit, carry_out): 和ビットと桁上げ

実装のコツ——2つの半加算器をカスケード接続する:
ステップ1:half_adder(a, b) → (s1, c1)
ステップ2:half_adder(s1, carry_in) → (sum_bit, c2)
最終桁上げ:carry_out = c1 OR c2
    """

    s1, c1 = half_adder(a, b)
    sum_bit, c2 = half_adder(s1, carry_in)
    carry_out = c1 | c2   # ORゲート:どちらかが桁上げなら、最終的に桁上げ
    return sum_bit, carry_out


def adder_4bit(a_bits, b_bits):
    """
4ビット・リップルキャリー加算器:4つの全加算器をカスケード接続。

引数:
a_bits: 4ビットの2進数リスト。a_bits
b_bits: 4ビットの2進数リスト。b_bits

戻り値:
(sum_bits, final_carry): 4ビットの和(下位を先頭)と最終桁上げ

桁上げ伝搬の全過程を出力し、リップルキャリーの動作を示す。
    """

    carry_in = 0
    sum_bits = []

    print("=" * 55)
    print(" 4ビット・リップルキャリー加算器 —— 桁上げ伝搬過程")
    print("=" * 55)
    # 上位を先頭に表示(人間が読みやすいように)
    print(f" 加数 A: {list(reversed(a_bits))} (上位を先頭)")
    print(f" 加数 B: {list(reversed(b_bits))} (上位を先頭)")
    print()

    for i in range(4):
        s, carry_out = full_adder(a_bits[i], b_bits[i], carry_in)
        sum_bits.append(s)

        print(f" [第 {i} ビット] (最下位は第 0 ビット)")
        print(f" 入力: A[{i}]={a_bits[i]}, B[{i}]={b_bits[i]}, 桁上げ入力={carry_in}")
        print(f" 出力: 和ビット={s}, 桁上げ出力={carry_out}")

        if carry_out:
            print(f" >> 桁上げ発生!Carry={carry_out} は第 {i+1} ビットへ渡される")

        carry_in = carry_out  # 現在の桁上げが次のビットの桁上げ入力になる
        print()

    print(f" 計算結果: {list(reversed(sum_bits))} (上位を先頭)")
    print(f" 最終桁上げ: {carry_in}")
    print("=" * 55)

    return sum_bits, carry_in


def decimal_to_4bit(n):
    """0〜15 の10進数を、4ビットの2進数リスト(下位を先頭)に変換する"""
    return [(n >> i) & 1 for i in range(4)]


def bits_to_decimal(bits):
    """2進数ビットリスト(下位を先頭)を10進数の整数に変換する"""
    return sum(bit * (2 ** i) for i, bit in enumerate(bits))


# ============================================
# テストケース
# ============================================

print(">>> サンプル 半加算器テスト <<<")
for a in (0, 1):
    for b in (0, 1):
        s, c = half_adder(a, b)
        print(f"  half_adder({a}, {b}) => sum={s}, carry={c}")
print()

print(">>> サンプル 全加算器テスト <<<")
test_cases = [
    (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
    (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)
]
for a, b, cin in test_cases:
    s, c = full_adder(a, b, cin)
    print(f"  full_adder({a}, {b}, carry_in={cin}) => sum={s}, carry={c}")
print()

print(">>> サンプル 4ビット加算器テスト: 7 + 5 <<<")
a_dec, b_dec = 7, 5
a_bits = decimal_to_4bit(a_dec)
b_bits = decimal_to_4bit(b_dec)
result_bits, final_carry = adder_4bit(a_bits, b_bits)
result_dec = bits_to_decimal(result_bits)
print(f" 期待値: {a_dec} + {b_dec} = {a_dec + b_dec}")
print(f"結果: {result_dec} (桁上げ={final_carry})")
print(f" サンプル 検証: {'通過!' if result_dec == a_dec + b_dec else '失敗!'}")
print()

print(">>> サンプル 追加テスト: 10 + 6 (オーバーフロー可能性)")
a_bits2 = decimal_to_4bit(10)
b_bits2 = decimal_to_4bit(6)
result_bits2, carry2 = adder_4bit(a_bits2, b_bits2)
result_dec2 = bits_to_decimal(result_bits2)
full_result = result_dec2 + (carry2 * 16)
print(f" 期待: 10 + 6 = 16")
print(f" 4 ビット結果: {result_dec2}, 桁上げ: {carry2}, 完全な 5 ビット値: {full_result}")
print(f" サンプル 検証: {'通過!' if full_result == 16 else '失敗!'}")

コードを実行して、桁上げが各ビット間でどのように伝播するかを観察してください。最下位ビットが最初に計算され、桁上げが発生すると次のビットへ渡され、次のビットが計算され、桁上げが発生するとさらに後方へ伝わります。これが「リプルキャリー」という名称の由来です。


インタラクティブデモ:4ビット加算器カスケードアニメーション(サンプル 桁上げ伝搬デモ)

下部では純粋な div+SVG で 4 ビットリプルキャリー加算器をシミュレートしています。ボタンをクリックして、桁上げが第 0 ビット(最下位)から第 3 ビット(最上位)にどのように伝わるかを段階的にデモします。、また「自動デモ」で全体の流れを見ることもできます。

4ビット・リップルキャリー加算器——桁上げ伝搬アニメーション

入力 A(上位ビットが先)
加数 A(上位ビットが先)
加数 B(上位ビットが先)
4 つの全加算器のカスケード(上位から下位へ:FA3 ← FA2 ← FA1 ← FA0)
全加算器 #3(最上位ビット)
A=0 B=0
桁上げ入力 Cin=0
和 Sum=?
桁上げ出力 Cout=?
←
全加算器 #2
A=0 B=0
桁上げ入力 Cin=0
和 Sum=?
桁上げ出力 Cout=?
←
全加算器 #1
A=0 B=0
桁上げ入力 Cin=0
和 Sum=?
桁上げ出力 Cout=?
←
全加算器 #0(最下位ビット)
A=0 B=0
桁上げ入力 Cin=0
和 Sum=?
桁上げ出力 Cout=?
操作ボタン
計算結果: -
「次へ」をクリックして桁上げ伝播のデモを開始します
その他の拡張