２進数の足し算回路 ~半加算器と全加算器~

サイエンス記事
2022.09.06

２進数の加算回路を全員が学ぶ時代

高校の情報Iの教科書を見ると、どの教科書にも２進数の加算回路について説明しています。情報Iは必修科目で１年次に学ぶので、これからは全員が学ぶことになります。共通テストに出題されることもあるでしょう。

実際にProcessingとPythonのそれぞれで加算回路を作ってみましょう。

基本回路の説明

■基本回路

CPU内部では複数の論理回路を組み合わせることで複雑な演算を行っています。論理値の真（true）を1、偽（false）を0として扱います。

論理回路の基本としてはAND回路、OR回路、NOT回路があり、この3つの組み合わせで様々な論理回路を構成できます。

AND回路は2つの入力と1つの出力を持ちます。2つの入力がともに１の時だけ、出力が1になります。

OR回路は2つの入力と1つの出力を持ちます。入力のいずれか一方が１であれば、出力が1になります。

NOT回路は1つの入力と1つの出力を持ちます。入力した信号を反転した値を出力します。

■半加算回路

以下の図のようなAND回路、OR回路、NOT回路を組み合わせた回路を半加算回路と呼びます。

入力はA、Bで出力は桁上がりC（Carry）と和S（Sum）です。

すなわち、２進数の１桁の加算ができる論理回路です。

例えば、A=1, B=1のとき、C=1, S=0となります。

■全加算回路

半加算回路では１桁の計算しかできませんでしたが、下図のように半加算回路を組み合わせることで、下からの桁上がりを考慮した加算器ができます。これを全加算回路と呼びます。

この全加算回路をさらに組み合わせれば、任意の桁数の加算回路が実現できます。

プログラムで加算回路を作ってみる

■Processingの場合

以下のようなプログラムで半加算回路と全加算回路を作ることができます。入力と出力を図と照らし合わせながら確認すると良いでしょう。２進数３桁の計算を行なっています。

入力　x 0 0 1（2進数）
入力　y 1 1 1（2進数）
の場合
桁上がり　c 1 1 1
和　s 0 0 0
が確認できます。

桁が上がって1000になりますが、３桁の計算にしているのでsは000です。

 

boolean carry, sum;

void setup() {
  boolean[] x = new boolean[3];
  boolean[] y = new boolean[3];
  boolean[] c = new boolean[3];
  boolean[] s = new boolean[3];

  x[0] = true;  // 1桁目は1
  x[1] = false;  // 2桁目は0
  x[2] = false;  // 3桁目は0 すなわち2進数の001
  y[0] = true;  // 1桁目は1
  y[1] = true;  // 2桁目は1
  y[2] = true;  // 3桁目は1 すなわち2進数の111

  halfAdder(x[0], y[0]);  // 1桁目の計算
  c[0] = carry;  // 桁上がりc
  s[0] = sum;  // 和s

  fullAdder(x[1], y[1], c[0]);  // 2桁目の計算 1桁目の桁上がりc[0]を入力
  c[1] = carry;  // 桁上がりc
  s[1] = sum;  // 和s

  fullAdder(x[2], y[2], c[1]);  // 3桁目の計算 2桁目の桁上がりc[1]を入力
  c[2] = carry;  // 桁上がりc
  s[2] = sum;  // 和s

  println("x", int(x[2]), int(x[1]), int(x[0]));  // 逆順に出力
  println("y", int(y[2]), int(y[1]), int(y[0]));
  println("c", int(c[2]), int(c[1]), int(c[0]));
  println("s", int(s[2]), int(s[1]), int(s[0]));
}

boolean AND(boolean a, boolean b) {  // AND回路
  return a && b;
}

boolean OR(boolean a, boolean b) {  // OR回路
  return a || b;
}

boolean NOT(boolean a) {  // NOT回路
  a = (a == false)? (a = true):(a = false);
  return a;
}

void halfAdder(boolean a, boolean b) {  // 半加算回路
  boolean or1, and1, not1, and2;
  or1 = OR(a, b);
  and1 = AND(a, b);
  not1 = NOT(and1);
  and2 = AND(or1, not1);

  carry = and1;
  sum = and2;
}

void fullAdder(boolean a, boolean b, boolean c0) {  // 全加算回路
  boolean halfAdder_c1, halfAdder_s1, halfAdder_c2, halfAdder_s2, or;
  halfAdder(a, b);
  halfAdder_c1 = carry;
  halfAdder_s1 = sum;

  halfAdder(halfAdder_s1, c0);
  halfAdder_c2 = carry;
  halfAdder_s2 = sum;

  or = OR(halfAdder_c1, halfAdder_c2);

  carry = or;
  sum = halfAdder_s2;
}

 

■Pythonの場合

この場合も以下のようなプログラムで半加算回路と全加算回路を作ることができます。入力と出力を図と照らし合わせながら確認すると良いでしょう。２進数３桁の計算を行なっています。

入力の x = [True, False, False] は1桁目が1, 2桁目が0, 3桁目が0なので2進数の001となります。

関数AND(a, b)はAND回路
関数OR(a, b)はOR回路
関数NOT(a, b)はNOT回路
half_adder(a, b)は半加算回路
full_adder(a, b, c0)は全加算回路
です。

half_adder(x[0], y[0])で1桁目の計算を行なっています。
full_adder(x[1], y[1], c[0])で1桁目の桁上がりc[0]を考慮した2桁目の計算を行なっています。
full_adder(x[2], y[2], c[1])で2桁目の桁上がりc[1]を考慮した3桁目の計算を行なっています。

最後に逆順で出力しています。

 

import numpy as np

x = [True, False, False]  # 1桁目が1, 2桁目が0, 3桁目が0 すなわち2進数の001
y = [True, True, True]  # 1桁目が1, 2桁目が1, 3桁目が1 すなわち2進数の111
c = []
s = []

def AND(a, b):  # AND回路
    return a and b

def OR(a, b):  # OR回路
    return a or b

def NOT(a):  # NOT回路
    return not a

def half_adder(a, b):  # 半加算回路
    or1 = OR(a, b)
    and1 = AND(a, b)
    not1 = NOT(and1)
    and2 = AND(or1, not1)
    return and1, and2

def full_adder(a, b, c0):  # 全加算回路
    c_and_s = half_adder(a, b)
    halfAdder_c1 = c_and_s[0]
    halfAdder_s1 = c_and_s[1];
    
    c_and_s = half_adder(halfAdder_s1, c0)
    halfAdder_c2 = c_and_s[0]
    halfAdder_s2 = c_and_s[1];

    or_ = OR(halfAdder_c1, halfAdder_c2)
    
    return or_, halfAdder_s2

c_and_s = half_adder(x[0], y[0])  # 1桁目の計算
c.append(c_and_s[0])  # 桁上がりc
s.append (c_and_s[1])  # 和s

c_and_s = full_adder(x[1], y[1], c[0])  # 2桁目の計算 1桁目の桁上がりc[0]を入力
c.append(c_and_s[0])  # 桁上がりc
s.append (c_and_s[1])  # 和s

c_and_s = full_adder(x[2], y[2], c[1])  # 3桁目の計算 2桁目の桁上がりc[1]を入力
c.append(c_and_s[0])  # 桁上がりc
s.append (c_and_s[1])  # 和s

print("x", [int(i) for i in list(reversed(x))])  # 逆順で出力
print("y", [int(i) for i in list(reversed(y))])
print("c", [int(i) for i in list(reversed(c))])
print("s", [int(i) for i in list(reversed(s))])

 

以下の出力が得られます。

x [0, 0, 1]
y [1, 1, 1]
c [1, 1, 1]
s [0, 0, 0]

入力　x 0 0 1（2進数）
入力　y 1 1 1（2進数）
の場合
桁上がり　c 1 1 1
和　s 0 0 0
が確認できます。

桁が上がって1000になりますが、３桁の計算にしているのでsは000です。

まとめ

半加算回路と全加算回路を実際にプログラムで作成し、2進数の加算を行なってみました。
教科書に書いてあることも、プログラムを使って実際にやってみることでより理解が深まります。