4-1강 - Combinational System Design 1 (Full Adder, Ripple Carry Adder, Carry Look-Ahead Adder)

half adder는 XOR 하나와 AND 하나가 합쳐진 구조

0. Half Adder

1) 정의 

1bit 2진수 2개를 더할 때, 덧셈한 기존의 합(S)과 동시에 자리올림수(C)를 구하는 조합논리회로입니다.

(예를 들어 1과 1을 더하면 결과는 0(S)이지만 자리올림수는 1(C)이 됩니다.)

 

2) Truth Table

3) 논리회로도

1> C(자리 올림수) - AND

A와 B 모두 1이어야 자리 올림이 있으므로 AND gate를 통해 C를 구하고

2> S(합) - XOR

A와 B의 실제 합은 XOR 연산자의 결과와 같으므로 이를 통해 S를 구합니다.

 

 

 

1. Full Adder 

1) 정의

1> 이전 자리올림수

기존 반가산기 개념에서 더 나아가 뒷자리에서 올라온 자리올림수(C_i, C_in)를 포함하여 1bit 2진수 3자리의 합을 계산한다.

2> 자리올림수 (C_i+1 & 합(S_i)

이 때, 반가산기처럼 합(S_i)과 자리올림수(C_i+1, C_out)을 구하는 회로이다.

 

(예를 들어, 기존의 input에 1과 1이 들어와 있는데 뒷자리에서 올라온 자리올림수가 1(C_i)이라면 합은 1(S_i)이며 자리올림수도 1(C_i+1)입니다.)

 

2) Truth Table

1> C_i+1 (자리올림수)

2> S_i (합)

3) 논리회로도

 

1> C_i+1 (자리 올림수)

- [1] x와 y 모두 1이거나

- [2] C_i와 (x와 y) 중 하나가 1이거나

 

2> S_i (합) - XOR

x, y, C_i 중 홀수개의 1을 가지면 S_i가 1이다.

4) Gate Delay

파형이 어떻게 그려지는지 이해하기 

 

cf>4개의 NAND를 연결하면 XOR을 만들 수 있다.

 

5) Delay through 1-bit adder (full adder)

NAND가 4개의 transistor로 구현할 수 있어서

구현할 때, 면적 측면에서나 delay 측면에서나 유리합니다.

1> 자리올림수 (C_i+1 )

실제 회로 상에서는 NAND로 구현한다. 실제 회로상의 gate로 식을 쓰면 아래와 같다.

C_i+1 = ~(((~(C&X^Y)) & (~(X&Y)))

 

2> 합 (S_i)

실제 회로 상에서는 NAND로 구현한다. 

NAND gate 8개로 XOR을 2개 구현해서 S_i를 구한다.

※ 보다시피 XOR이 아닌 NAND로도 구현이 가능하다. 이 얘기는 다른 회로도 다양한 방법으로 구현이 가능합니다. 그 구현마다 성능, 면적, 속도, power가 다릅니다. 그래서 경우에 따라 다르게 design을 할 필요가 있다.

 

3> gate delay

사진에 있는 것처럼

S_i는 6△

C_i+1은 5△

만큼 gate delay가 일어납니다. 

 

4> 만약에 여러 Full Adder를 붙이면 (2n+4)△의 gate delay가 일어납니다.

 

2. Ripple Carry Adder

1) Full Adder의 연결

Full Adder를 추가할 때 생기는 gate delay

 

1> sum (S_i) 

C_i (2n+4-3△)에서

NAND 3층을 거치면 (XOR은 NAND 4개로 만든다.)

2n+4△의 gate delay가 발생한다. (gate delay 3△증가)

 

2> carry (C_i+1)

C_i (2n+4-3△)에서

NAND 2층을 거치면 (4개의 input<a, b, c, a^b>에 대해 NAND를 2층으로 3번 하면 곱들의 합이 된다.) (ab+c(a^b))

2n+3△의 gate delay가 발생한다. (gate delay 2△증가)

 

2) N-bit ripple carry adder의 gate delay

0> gate delay

이를 통해 매번 FA를 연결할 때마다 2△의 gate delay가 발생하므로

Ripple Carry Adder는 (2n+4)△의 gate delay가 발생한다고 할 수 있다.

 

1> 4-bit ripple carry adder

2> 8-bit ripple carry adder

 

 

3. Carry look-ahead adders

0) 도입 배경

문제 : gate delay

원인 : 위의 ripple carry adders는 carry(C_i)때문에 gate delay가 생긴다.

해결 : 그래서 carry를 미리 계산해서 문제를 해결한다. (그래서 이름이 carry look-ahead adder)

 

1) Carry look-ahead technique

결과적으로 carry로 인한 gate delay를 줄여준다.

1> carry에 대한 분석

[1] x와 y 모두 1이거나 [2] 전단계에서 carry가 있어야(C_i=1) → carry(C_i+1이 생긴다.)

그러므로 2가지 경우가 어떻게 조합되는지 치환해서 간단하게 표현해본다.

 

2> adder 내부의 AND, XOR을 치환한다.

- [1] carry-generate function → g_i = x_i*y_i

- [2] carry-propagate function → p_i = x_i^y_i

 

3> index별 carry

4> 장점

carry를 바로 얻을 수 있어서 gate delay를 줄일 수 있다.

5> 단점

bit가 늘어날수록 carry 식이 복잡해져서 회로가 커진다.

 

2) 4-bit carry look ahead adder

1> 4-bit ripple carry adder (기존 방식)

순차적으로 연산해야 해서 S_i를 구해야 S_i+1을 구할 수 있다.

2> 4-bit carry look ahead adder

carry를 계산하는 Carry Look Ahead generator가 존재해서 S_i, S_i+1, S_i+2, S_i+3을 동시에 구할 수 있다.

3> Single-level 16 bit carry look ahead adder using 4 bit CLA blocks

16bit를 한 번에 carry 형성하기에는 너무 복잡하므로 4 bit씩 carry를 계산한다.

- 4bit 내부는 병렬적으로 연산하지만

- 4bit끼리는 순차적으로 연산한다.

 

3) 다른 4-bit carry look ahead adder

sum과 carry를 연산하는 방법은 여러가지이기 때문에 구조는 약간씩 바뀔 수 있습니다.

 

0> adder 1개

Karnaugh Map 간소화로 아래와 같이 정리할 수 있습니다.

1> C_i의 gate delay

• AND gate 3개 1층, OR gate 1개 1층 → 2△의 gate delay

 

2> S_i의 gate delay

• NOT gate들 1층, AND gate 4개 1층, OR gate 1개 1층 → 3△의 gate delay

 

3> Carry look-ahead - g_i, p_i의 gate delay

 

치환이 적용된 C_i+1의 식 자체는 이전과 동일한 것을 관찰할 수 있다.

• g_i, p_i 각각 AND, OR gate 1개씩 가진다. → 1△의 gate delay

4> Carry look-ahead adder 1개의 gate delay

5>16-bit Carry Look ahead Adder using 4 bit CLA  1개의 gate delay

4-bit CLA를 4개 사용

4) 16-bit super CLA block

16-bit를 한 번에 계산하면 carry 계산할 때 빠르지만 회로가 복잡해질 수 있다. (그래도 한 번 해본다.)

다만 이전과 다른 점은 carry look-head를 2 level로 쓴다는 것이다. (CLA를 2층으로 만든다.)

1> 2nd level CLA에서의 치환

2> carry

 

3> gate delay