Scala で半加算器と全加算器を実装する

Scala で半加算器・全加算器を作ってみました。

ふと、論理回路とオブジェクト指向型って機能分割されている面で相性良さそうだなぁと感じたので、ノリと勢いで作ってみました。

前提知識
実装
検証
まとめ

前提知識

半加算器

半加算器 (half adder, HA) とは、下の桁からの桁上がり (キャリー, carry) を考慮せず、2つの1ビットの値を入力し、加算結果と桁上がりを出力するものです。入力 A、B に対して、加算結果 S (sum) と桁上がり C は次の論理式で与えられます。

\begin{align} S = A \oplus B \\ C = A \cdot B \end{align}

すなわち、真理値表は以下のようになります。

A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

全加算器

全加算器 (full adder, FA) とは、下の桁からの桁上がりを考慮して、2つの1ビットの値を入力し、加算結果と桁上がりを出力するものです。入力 A、B、C_r (下位桁からの桁上がり) に対して、加算結果 S、桁上がり C は次の論理式で与えられます。

\begin{align} S = A \oplus B \oplus C_r \\ C = A \cdot B + C_r \cdot (A \oplus B) \end{align}

すなわち、真理値表は以下のようになります。論理式より、全加算器は半加算器を組み合わせて構成できることがわかります。

A	B	C_r	S	C
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

n ビット加算器

全加算器と半加算器を組み合わせると、nビットの加算器を構成することができます。

全加算器と半加算器は、1ビットの入力に対して加算結果と桁上がりを出力するというものでした。そのため、全加算器を n-1 個、半加算器を 1 個用いることによって、n ビットの加算結果を出力する回路を構成できます。

f:id:tomoki0606:20200825231008j:plain

実装

では、実際に半加算器、全加算器、n ビット加算器を Scala で実装していきましょう。

半加算器

半加算器は、入力の XOR を返す sum メソッドと、入力の AND を返す carry メソッドを定義したオブジェクトとして実装しました。

/**
 * Binary half adder
 */
object HalfAdderBinary {

  /**
   * Calculate sum
   */
  def sum(num1: Int, num2: Int): Int =
    num1 ^ num2

  /**
   * Calculate carry
   */
  def carry(num1: Int, num2: Int): Int =
    num1 & num2
}

Scala において、 ^ は XOR を表し、 & は AND を表します。単にビット演算の結果を返しているだけなので、実装は簡単です。

全加算器

全加算器は、半加算器を組み合わせて sum と carry を計算するメソッドを定義したオブジェクトとして定義しました。

/**
 * Binary full adder
 */
object FullAdderBinary {

  /**
   * Calculate sum
   */
  def sum(num1: Int, num2: Int, carry: Int): Int =
    HalfAdderBinary.sum(
      HalfAdderBinary.sum(num1, num2),
      carry
    )

  /**
   * Calculate carry
   */
  def carry(num1: Int, num2: Int, carry: Int): Int =
    HalfAdderBinary.carry(num1, num2) |
      HalfAdderBinary.sum(num1, num2) & carry
}

sum の論理式は $S = A \oplus B \oplus C_r$ で表されるので (num1 ^ num2) ^ carry としても良いです。今回は、半加算器を組み合わせて構成するというところに注目して実装しました。

carry の論理式は $C = A \cdot B + C_r \cdot (A \oplus B)$ で表されるので (num1 & num2) | carry & (num1 ^ num2) としても良いです。

n ビット加算器

n ビット加算器は、全加算器と半加算器の組み合わせによって構成できます。今回は、実装の簡略化のため全加算器のみで構成してみました。

addBinary メソッドを、引数として2つの2進数 bin1、 bin2 をとり、その加算結果を返すメソッドとして実装しました。

/**
 * Calculate sum of two binary numbers
 */
def addBinary(bin1: String, bin2: String): String = {
  println(s"binary addition: ${bin1} + ${bin2} = ???")
  val length  = bin1.length.max(bin2.length)
  val revBin1 = bin1.reverse
  val revBin2 = bin2.reverse
  (0 to length).foldLeft(("", 0)) {
    (acc, index) => {
      val bit1     = scala.util.Try(revBin1(index).toInt - '0').getOrElse(0)
      val bit2     = scala.util.Try(revBin2(index).toInt - '0').getOrElse(0)
      val bitSum   = FullAdderBinary.sum    (bit1, bit2, acc._2)
      val bitCarry = FullAdderBinary.carry(bit1, bit2, acc._2)
      println(s"bit: $index) input: num1: $bit1, num2: $bit2, carry: ${acc._2} | output: sum: $bitSum, carry: $bitCarry")
      (bitSum.toString + acc._1, bitCarry)
    }
  }._1
}