Chapter 4의 흐름
- 이진 덧셈의 기본 구조
- Half Adder, Full Adder
- 여러 비트 덧셈기 구성
- 보수를 이용한 뺄셈
- signed number 표현과 overflow
- 곱셈 및 특수 산술 블록
- design by contraction과 데이터 확장
즉, 다음과 같은 흐름으로 진행한다.
1비트 가산기 -> 다비트 가산기 -> 보수 기반 뺄셈 -> signed 연산 -> overflow -> 곱셈기 / 특수 회로
Arithmetic Function의 의미
Arithmetic funtions는 숫자 데이터에 대해 수행되는 연산이다.
대표적으로 덧셈, 뺄셈, 증가, 감소, 곱셈, 비교가 있다.
이번 챕터에서는 덧셈과 뺄셈 회로가 중심이다. 실제 디지털 시스템에서 산술 회로의 기본이 결국 adder이기 때문이다.
Half Adder(HA)
Half Adder는 2개의 1비트 입력을 더해서 합(Sum), 자리올림(Carry)을 출력하는 가장 기본적인 가산기다.
입력 : X, Y 출력 : S, C
진리표
카르노 맵
논리식
즉 Half Adder는 합은 XOR, 자리올림은 AND로 구현된다.
Half Adder는 이전 자리에서 넘어오는 carry-in을 처리하지 못한다.
그래서 다비트 덧셈에는 Half-Adder만으로는 부족하고, Full Adder가 필요하다.
Full Adder(FA)
Full Adder는 3개의 1비트 입력을 더하는 회로다.
입력 : X, Y, Z 또는 C_in 출력 : S, C_out
이전 자리에서 올라온 carry 까지 포함해 계산할 수 있다.
진리표
카르노 맵
논리식
다음과 같이도 표현 가능하다.
즉 세 입력 중 적어도 두 개 이상이 1이면 carry 발생이다. 즉 ,carry는 majority function
구현
Half Adder 2개로 Full Adder 구현이 가능하다.
Full Adder는 보통 Half Adder 2개와 OR 게이트 1개로 만들 수 있다.
구성 :
첫 번째 HA : X,Y 입력
두 번째 HA : 첫 번째 Sum과 C_in 입력
Carry는 두 HA의 carry 를 OR
AI 활용 설정
사진 설명을 입력하세요.
Ripple Carry Adder
Ripple Carry Adder는 여러 개의 Full Adder를 직렬로 연결해 만든 다비트 가산기다.
예 : 4비트 가산기 -> Full Adder 4개 연결
각 자리의 carry-out이 다음 자리의 carry-in으로 전달된다.
구조
장점 : 구조가 단순, 설계가 쉬움, 확장 가능
단점 : Carry Propagation Delay
가장 큰 문제는 carry가 한 자리씩 전달되므로 시간이 오래 걸린다는 점이다.
즉, 최상위 비트 결과는 모든 이전 자리의 carry가 계산된 뒤에야 확정된다. 이걸 ripple carry delay라 한다.
Carry Propagation Delay의 의미
왜 느린지 이해를 해야 한다. 예를 들어 4비트 가산기에 MSB 결과를 구하려면 LSB의 carry가 먼저 계산되고 그 carry가 다음 자리로 전달되고 다시 다음 자리로 전달되어야 한다. 즉, carry가 파도처럼 ripple되어 전파된다.
Binary Substraction
뺄셈은 직접 구현할 수도 있지만, 실제 회로에서는 보통 보수(complement)를 이용해서 덧셈으로 바꿔 처리한다.
왜냐하면 adder 하나로 addition, subtraction 모두 처리할 수 있기 때문이다.
1's Complement
1의 보수는 각 비트를 반전시킨 값이다.
예 : 1010 -> 0101 즉, 0 -> 1 , 1 -> 0
2's Complement
2의 보수는 먼저 1의 보수를 구하고 거기에 1을 더한 값이다.
예 : 0101(원래 수) -> 1010(1의 보수) -> 1011(2의 보수)
왜 중요한가?
2의 보수는 현대 컴퓨터에서 signed integer 표현의 표준이다.
이유로는 덧셈 회로 하나로 뺄셈 가능, 0표현이 하나만 있음, 회로 구현이 단순함이 있다.
음수 표현
n비트 2의 보수에서 양수는 일반 이진수와 같음, 음수는 해당 양수의 2의 보수로 표현
4비트에서 +5 = 0101, -5 = 1011
2's Complement의 범위
n비트 signed 2의 보수 정수의 범위는 다음과 같다.
예 :
4비트 -> -8 ~ +7, 8비트 -> -128 ~ +127
왜 2의 보수를 쓰면 뺄셈이 덧셈이 되나?
예를 들어 A-B를 계산하고 싶으면 A + (-B)로 생각하면 된다.
그리고 -B를 2의 보수로 표현하면, 결국 가산기로 그냥 더하면 된다.
즉, subtraction = addition of 2's complement
이게 adder-subtractor회로의 핵심이다.
Adder-Subtractor Circuit
기본 아이디어
한 개의 가산기로
A+B, A-B를 둘다 하도록 만든 회로다.
제어 신호를 보통 S라 하자. S = 0 -> 덧셈, S = 1 -> 뺄셈
구현 원리
뺄셈할 때는 B를 2ㅡ이 보수로 만들어야 하므로
각 B_i를 XOR 게이트에 통과시켜 제어신호 S와 XOR
또한 첫 carry-in에 S를 넣는다.
따라서 전체적으로
핵심 식
Adder-subtractor는 실제로 다음 연산을 수행한다.
Adder-subtractor에서 XOR는 조건부 반전 역할을 한다.
Signed Number Representation
이번 챕터에서 signed integer를 표현하는 3가지 방식이 비교된다.
- Signed-Magnitude
- Signed 1's Complement
- Signed 2's Complement
Signed-Magnitude
가장 왼쪽 비트가 부호 비트다.
0 -> 양수, 1 -> 음수
나머지 비트는 크기(magnitude)를 나타낸다.
예 : 4비트
- +5 = 0101
- -5 = 1101
단점 : +0, -0 두 개 존재, 연산 회로가 복잡
Signed 1's Complement
음수는 양수 비트의 1의 보수로 표현
예 :
- +5 = 0101
- -5 = 1010
단점 : +0, -0 두 개 존재, end-around carry 등 불편
Signed 2's Complement
음수는 양수의 2의 보수로 표현
예 :
- +5 = 0101
- -5 = 1011
장점 : 0이 하나뿐, 덧셈기 구조 단순 현대 시스템 표준 즉, 2의 보수 방식이 가장 중요하다.
Overflow
overflow란?
결과가 주어진 비트수로 표현 가능한 범위를 벗얼날 때 발생한다.
특히 signed 2's complement 연산에서 중요하다.
signed overlflow가 발생하는 경우
2의 보수 signed 덧셈에서 overflow는
양수 + 양수 = 음수
음수 + 음수 = 양수처럼 나올 때 발생한다.
예 :
4비트에서 7 + 3 = 10 표현 불가
결과 비트는 음수처럼 보일 수 있음 -> over flow
carry와 overflow는 다르다
- Unsigned addition에서는 carry-out이 중요하다.
- signed 2's complement addtion에서는 overflow가 중요하다
carry-out이 있다고 overflow인 것도 아니고, carry-out이 없다고 overflow가 없는 것도 아니다.
overflow 검출 공식
signed 2's complement addition에서 overflow는
즉 부호 비트로들어가는 carry, 부호 비트에서 나오는 carry가 다르면 overflow다.
여기서 C_n-1 = sign bit로 들어가는 carry, C_n = sign bit에서 나오는 carry다.
왜 XOR인가? 같으면 정상 다르면 overflow 부호 비트 계산이 비정상적으로 뒤틀렸다는 뜻
Overflow를 부호로 판단하는 방법
signed addition에서 좀 더 직관적으로 보면
- 양수 + 양수 -> 결과가 음수면 overflow
- 음수 + 음수 -> 결과가 양수면 overflow
- 양수 + 음수 -> overflow 없음
Unsigned와 Signed의 차이
같은 비트 패턴도 해석 방식이 다르면 값이 달라진다.
예 : 4비트 1111
- unsigned로는 15
- signed 2의 보수로는 -1
즉 회로 계산 문제에서 항상 먼저 이 수가 unsigned인지 signed 2의 보수인지 확인해야한다.
Incrementer / Decrementer
가산기름 조금 변형하면 1 증가, 1감소 회로도 만들 수 있다.
incrementer = 어떤 수에서 1 더하기
decrementer = 어떤 수에서 1 빼기
이번 챕터에서 중요한 것은 이러한 회로들이 결국 adder 구조를 바탕으로 만들어진다는 것이다.
Design by Contraction
기존의 일반적인 회로 블록에서 특정 입력을 0이나 1로 고정하고 불필요한 부분을 제거해서 더 단순한 특수 목적 회로를 만드는 방법이다.
예시
일반 adder에서 어떤 입력을 0으로 고정하면 단순화 가능
carry를 특정 값으로 고정하면 incrementer처럼 동작
즉 범용회로에서 특수 기능 회로를 뽑아내는 방식이다.
Multiplication
이진 곱셈은 10진 곱셈과 원리가 같다.
각 비트에 대해 partial product 생성, partial products를 더함
partial product
곱셈에서 한 자리씩 생기는 중간 곱은 partial product라 한다.
이진에서는 각 비트가 0 또는 1이므로 매우 단순하다.
multiplier 비트가 0 -> partial product = 0
multiplier 비트가 1 -> partial product - muliplicand
즉 partial product는 보통 AND 게이트 배열로 생성할 수 있다.
예시
101 X 11
부분 곱
하위 비트 1-> 101
상위 비트 1 -> 1010
더하면 : 1111
즉 5 X 3 = 15
회로 관점
곱셈기는 보통 AND array로 partial product 생성, adder array로 partial products 합산 구조를 가진다.
Arithmaetic Building Blocks의 핵심 관계
중간 정리를 하자
Hald Adder : 1비트 두 입력 덧셈
Full Adder : carry-in 포함 1비트 덧셈
Ripple Carry Adder : 다비트 덧셈
Adder-Subtractor : 덧셈/뺄셈 통합
Multiplier : 부분곱 + 덧셈
즉, 대부분의 산술 회로는 결국 adder를 중심으로 확장된다.
Zero Fill과 Extension
데이터 조작 개념이다
Zero Fill
비트 폭을 늘릴 때 새로 추가되는 사위 비트를 0으로 채우는 것이다.
예 :
1011 -> 001011
이는 보통 unsigned 수에 사용한다.
Sign Extension
signed 2's complement 수의 비트 폭을 늘릴 때는 부호 비트(sign bit)를 복사해야 한다.
예 :
4비트 0101 (+5) -> 8비트 00000101
4비트 1011 (-5) -> 8비트 11111011
이렇게 해야 값이 유지된다.
왜 sign extension이 필요한가?
signed number는 최상위 비트가 부호의 의미를 가지므로 단순히 0을 채우면 음수 값이 바뀌어 버릴 수 있다.
예 :
1011은 4비트에서 -5 만약 00001011로 만들면 +11이 되어버린다.
따라서 signed number 폭 확장에서는 반드시 sign extension을 해야한다.
Chapter 4 총정리
- Half Adder의 출력은 S=X⊕Y, C=XY이다.
- Full Adder의 출력은 S=X⊕Y⊕Z, C=XY+XZ+YZ이다.
- Ripple Carry Adder는 여러 Full Adder를 직렬 연결한 다비트 가산기이다.
- Ripple Carry Adder의 주요 단점은 carry propagation delay이다.
- 1의 보수는 각 비트를 반전한 값이다.
- 2의 보수는 1의 보수에 1을 더한 값이다.
- 2의 보수 표현은 signed integer의 표준 방식이다.
- Adder-subtractor는 XOR와 초기 carry-in을 이용해 덧셈과 뺄셈을 모두 수행한다.
- signed 2’s complement addition에서 overflow는 Cn⊕Cn−1로 검출할 수 있다.
- 양수 + 양수 = 음수이면 overflow, 음수 + 음수 = 양수이면 overflow이다.
- 곱셈은 partial product 생성과 덧셈으로 이루어진다.
- zero fill은 unsigned 확장, sign extension은 signed 확장에 사용한다.