Home 반가산기와 전가산기
Post
Cancel

반가산기와 전가산기

Seongwook Jang on Jan 102022-01-10T22:18:48+09:00
Updated Jan 182022-01-18T21:39:34+09:00 7 min read

디지털논리회로

1) 논리게이트 - AND: 두 개의 입력이 모두 참(true)일 때만 참(true)이 된다. - OR: 두 개의 입력 중 하나라도 참(true)일 경우에만 참(true)이 된다. - INVERTER (NOT): 입력값이 반전된 값이 출력된다. - NAND (NOT AND): AND의 반대로, 입력값이 모두 거짓(false)일 때만 참(true)이 된다. - NOR (NOT OR): OR의 반대로, 입력값이 하나라도 거짓(false)인 경우 참(true)이 된다. - XOR: 입력값이 서로 반대일 경우에만 참(true)이 된다.

2) 비트의 순서 - 1byte (8bit)

1
2
3

    |     7     | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
    |-----------|---|---|---|---|---|---|---|
    |MSB(부호비트)|2^6|2^5|2^4|2^3|2^2|2^1|2^0|

3) 반가산기 (half-adder) - 1비트 2진수 1과 0을 더했을 때의 결과는 01이 된다.
따라서 결괏값01에서 두번째 비트인 0은 자리올림(carry)이 되고 첫번째 비트인 1은 합(sum)이 된다.

4) 전가산기 (full-adder) - 2비트 2진수 01과 01을 더했을 때의 결과는 10이 된다.
두 2진수의 첫번째 비트인 1과 1을 더하게 되면 10이 되고 결괏값의 첫번째 비트 1은 자리올림(carry)이 되며 두번째 비트 0은 합(sum)이 된다.
자리올림(carry)이 1이기 때문에 입력값의 두번째 비트인 0과 0을 더할 때 자리올림(carry)값을 더해주면 최종 결과는 10이 된다. - 따라서 전가산기는 반가산기 2개와 OR연산 1개가 필요하다.

반가산기 구현하기

  • 반가산기를 구현하기 위해서는 논리게이트를 이용해야 한다.
  • 두 비트를 더했을 때의 합(sum)과 자리올림(carry)을 구해야 한다.
    • 합(sum)은 두 비트 중 하나만 1인 경우에만 1이 되므로 XOR 연산을 이용한다.
    • 자리올림(carry)는 두 비트 모두 1인 경우에만 1이 되므로 AND 연산을 이용한다.
  • 합(sum)구현
    • 두 개의 입력값이 다를 경우에만 true가 되어야 한다.
      • 두 개의 입력값이 다르다는 것은 1, 0, 0, 1인 경우인데 서로 더했을 때 결과값은 1이 되기 때문에 자리올림 수는 0이 되고 합은 1이 된다.
    • 두 개의 입력값이 같다면 자리올림 수가 1이 되거나 합이 0이 되는 경우만 존재하므로 이 경우에는 false가 되어야 한다.
    1
2
3

      fun sum(bitA: Boolean, bitB: Boolean): Boolean {
      return bitA xor bitB
  }
  • 합(sum)구현 테스트
    1
2
3
4
5
6
7
8

      fun sumTest() {
      // SUM 함수 테스트
      println("SUM 함수 테스트")
      println(sum(true, true))
      println(sum(true, false))
      println(sum(false, true))
      println(sum(false, false))
  }
  • 결과
    1
2
3
4

      false
  true
  true
  false
  • 자리올림(carry)구현
    • 자리올림(carry)는 두 개의 입력값을 더했을 때 자리올림이 되는 경우 true를 반환해야 한다.
      • 즉, 1, 1인 경우에만 결괏값이 10이 되므로 자리올림비트를 설정해주어야 한다.
    1
2
3

      fun carry(bitA: Boolean, bitB: Boolean): Boolean {
      return bitA and bitB
  }

  • 테스트

    1
2
3
4
5
6
7
8

      fun carryTest() {
      // CARRY 함수 테스트
      println("CARRY 함수 테스트")
      println(carry(true, true))
      println(carry(true, false))
      println(carry(false, true))
      println(carry(false, false))
  }
  • 결과
    1
2
3
4

      true
  false
  false
  false

halfAdder 함수 구현 및 테스트

  • 두 개의 비트를 입력받아 합(sum)과 자리올림(carry)을 배열로 리턴하도록 구현하였다.

    1
2
3
4
5
6
7

      fun halfadder(bitA: Boolean, bitB: Boolean): BooleanArray {
      val answer = BooleanArray(2)
      answer[0] = carry(bitA, bitB)
      answer[1] = sum(bitA, bitB)

      return answer
  }
  • 테스트
    1
2
3
4
5
6
7
8

      fun halfadderTest(bitA: Boolean, bitB: Boolean) {
      println("halfadder 함수 테스트")
      println("bitA = $bitA")
      println("bitB = $bitB")

      var result = halfadder(bitA, bitB)
      println("결과 = [${result[0]}, ${result[1]}]")
  }

  • 결과

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

      bitA = true
  bitB = true
  결과 = [true, false]

  bitA = true
  bitB = false
  결과 = [false, true]

  bitA = false
  bitB = true
  결과 = [false, true]

  bitA = false
  bitB = false
  결과 = [false, false]

전가산기 구현하기

  • 두 개의 비트와 한 개의 자리올림 비트를 입력받아 합(sum)과 자리올림(carry)을 배열로 리턴하도록 구현하였다.
  • 전가산기는 2진수 한 자리를 계산하고, 자리올림 수를 포함해 출력한다. 다음 자리를 계산할 때 이전에 출력한 자리올림 수를 이용해 다시 계산한다.

    • 예를들어, 11과 01을 더한다고 가정했을 때 아래와 같이 계산된다.

      1
2
3
4
5

           1 1          1 1                             1 1
  +  0 1   =>  +  0 1                    =>       0 1             => ...
 -------      -------                          +  1 (자리올림 수) 
                    0 (자리올림 수 1)          --------- 
                                                    0

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

      fun fulladder(bitA: Boolean, bitB: Boolean, carry: Boolean): BooleanArray {
      val curHalfAdder = halfadder(bitA, bitB)
      val curCarry = curHalfAdder[0]
      val curSum = curHalfAdder[1]

      val nextHalfAdder = halfadder(carry, curSum)
      val nextCarry = nextHalfAdder[0]
      val nextSum = nextHalfAdder[1]

      val answer = BooleanArray(2)
      answer[0] = curCarry or nextCarry
      answer[1] = nextSum

      return answer
  }

  • 테스트

    1
2
3
4
5
6
7
8
9

      fun fulladderTest(bitA: Boolean, bitB: Boolean, carry: Boolean) {
      println("fulladder 함수 테스트")
      println("bitA = $bitA")
      println("bitB = $bitB")
      println("carry = $carry")

      var result = fulladder(bitA, bitB, carry)
      println("결과 = [${result[0]}, ${result[1]}]")
  }

  • 결과

    1
2
3
4
5
6
7
8
9

          bitA = true
      bitB = true
      carry = true
      결과 = [true, true]

      bitA = true
      bitB = false
      carry = true
      결과 = [true, false]
CS
CS 반가산기 전가산기
This post is licensed under CC BY 4.0 by the author.
Recent Update
Contents

시간복잡도와 공간복잡도

[BOJ 1475] 방 번호

Comments powered by Disqus.