한국어
메뉴

리플 캐리·캐리 룩어헤드·캐리 세이브 가산기의 차이: 지연·회로 규모·용도 비교

모두 전가산기를 조합한 덧셈 회로이지만, 자리올림을 다루는 방식이 다릅니다. 리플 캐리 가산기는 전가산기를 직렬로 연결해 자리올림이 하위에서 상위로 차례로 전달되므로, 지연은 비트 수 n에 비례합니다(O(n)). 캐리 룩어헤드 가산기는 각 자리의 생성 신호와 전파 신호로부터 모든 자리올림을 병렬로 구하며, 룩어헤드 회로를 계층화하면 지연은 O(log n)으로 끝납니다. 캐리 세이브 가산기는 세 수를 자리올림을 전달하지 않고 합과 자리올림의 두 수로 정리하는 회로로, 지연은 비트 수와 관계없이 전가산기 1단 분량입니다. 곱셈기에서는 캐리 세이브 가산기의 트리(월리스 트리 등)로 부분곱을 줄이고, 마지막에 남은 두 수를 고속 가산기로 더합니다.

비교 항목리플 캐리 가산기캐리 룩어헤드 가산기캐리 세이브 가산기
입력과 출력두 수(와 자리올림 입력)를 더해 하나의 합과 자리올림 출력을 낸다두 수(와 자리올림 입력)를 더해 하나의 합과 자리올림 출력을 낸다세 수를 합 S와 자리올림 Cy의 두 수로 정리한다(A + B + C = S + Cy)
자리올림의 처리각 전가산기가 하위로부터의 자리올림을 기다려 차례로 상위로 전달한다생성 신호 g = a·b와 전파 신호 p = a ⊕ b를 써서 c(i+1) = g(i) + p(i)·c(i)를 전개해 자리올림을 병렬로 구한다옆 자리로는 전달하지 않고, 1자리 왼쪽으로 민 수로서 다음 단에 넘긴다
지연이 늘어나는 방식O(n). 최악의 경우 자리올림이 최하위에서 최상위까지 전달된다O(log n)(룩어헤드 회로를 계층화한 경우)O(1). 비트 수와 관계없이 전가산기 1단 분량
64비트에서의 기준자리올림이 전가산기 64단을 지난다4비트 블록을 3계층으로 구성한다. 병렬 프리픽스 가산기라면 Kogge-Stone형에서 자리올림 계산은 log₂64 = 6단1단은 전가산기 1개 분량의 지연. 64개의 부분곱을 두 개로 정리하는 월리스 트리는 10단
회로 규모최소. n비트에서 전가산기 n개룩어헤드 회로만큼 크다. 빠른 구성일수록 게이트와 배선이 많다(Kogge-Stone형에서는 대략 n log n)1단은 전가산기 n개이며 자리올림을 전달하는 회로는 없다. 곱셈기의 트리 전체로는 부분곱의 비트 수(n² 정도)에 비례한다
결과의 형태일반적인 2진수일반적인 2진수합과 자리올림의 두 수로 나뉜 중복 표현. 하나의 값으로 만들려면 마지막에 일반 가산기로 더해야 한다
주요 용도속도가 중요하지 않은 작은 회로나 저전력 회로. FPGA에서는 전용 자리올림 회로(캐리 체인)를 써서 만드는 경우가 많다CPU의 ALU, 주소 계산, 부동소수점 유닛, 곱셈기 마지막 단의 덧셈곱셈기의 부분곱 덧셈(월리스 트리, 다다 트리), 곱셈 누산의 누적, 많은 수의 덧셈
관련 방식캐리 스킵 가산기, 캐리 셀렉트 가산기(속도와 면적이 중간)병렬 프리픽스 가산기(Kogge-Stone형, Brent-Kung형 등)4:2 컴프레서, 부분곱을 줄이는 부스 알고리즘과의 조합

수치는 대략적인 자릿수 기준이며, 공정 세대와 제품에 따라 달라져요.

상황별 선택 기준

리플 캐리 가산기
비트 수가 적을 때, 또는 속도보다 면적이나 소비 전력을 우선할 때 씁니다. 회로가 단순하고 규칙적이므로, FPGA처럼 전용 고속 자리올림 경로를 가진 디바이스에서는 이 형태로 효율적으로 구현할 수 있습니다.
캐리 룩어헤드 가산기
두 수의 덧셈을 한 번에 빨리 끝내야 할 때 씁니다. CPU의 ALU나 크리티컬 패스에 들어가는 가산기가 대표적입니다. 계층화 방법이나 병렬 프리픽스 가산기의 종류에 따라 단수와 면적·배선량 사이의 균형을 고릅니다.
캐리 세이브 가산기
세 개 이상의 수를 더할 때 씁니다. 도중에는 자리올림의 전달을 기다리지 않고 수를 줄이고, 마지막에 한 번만 캐리 룩어헤드 가산기 등으로 더하므로, 많은 부분곱을 더하는 곱셈기나 곱셈 누산을 반복하는 MAC에서 효과가 커집니다.

자주 묻는 질문

O(n)과 O(log n)의 차이는 실제로 어느 정도인가요?

64비트에서 리플 캐리 가산기의 자리올림은 전가산기 64단을 지나지만, Kogge-Stone형 병렬 프리픽스 가산기에서는 자리올림 계산이 log₂64 = 6단입니다. 1단당 지연은 회로에 따라 다르므로 단순한 비율은 되지 않지만, 비트 수가 늘수록 차이는 커지며, GHz급 프로세서의 64비트 덧셈에는 리플 캐리 가산기로는 시간이 모자랍니다.

캐리 세이브 가산기의 동작을 수로 확인하려면?

4비트의 5(0101), 6(0110), 7(0111)을 넣으면, 각 자리의 합 비트를 모은 수 S는 0100(4), 자리올림 비트를 모아 1자리 왼쪽으로 민 수 Cy는 1110(14)이 됩니다. 4 + 14 = 18로 5 + 6 + 7과 일치합니다. 각 자리는 독립된 전가산기이므로 자리올림을 기다릴 필요가 없습니다.

월리스 트리의 단수는 어떻게 정해지나요?

각 단에서 캐리 세이브 가산기가 세 수를 두 수로 정리하므로, 수는 대략 3분의 2씩 줄어듭니다. 부분곱이 h개일 때 1단에서 2⌊h/3⌋ + (h mod 3)개가 되며, 8개면 4단, 16개면 6단, 32개면 8단, 64개면 10단으로 두 개가 됩니다. 단수는 비트 수의 로그에 비례하는 정도이며, 마지막에 남은 두 수를 고속 가산기로 더하면 곱이 완성됩니다.

캐리 룩어헤드의 식을 큰 비트 수에서 그대로 쓰지 않는 이유는 무엇인가요?

자리올림 식을 완전히 전개하면 상위 자리일수록 항이 늘어나, 입력 수가 매우 많은 게이트가 필요해지기 때문입니다. 그래서 4비트 정도의 블록마다 그룹 생성 신호 G와 그룹 전파 신호 P를 구하고, 위 계층에서 같은 형태의 룩어헤드 회로를 씁니다. 병렬 프리픽스 가산기는 이 생각을 일반화한 것입니다.

이해도 확인

전가산기를 직렬로 연결한 리플 캐리 가산기의 단점으로 올바른 것은?

  1. A음수를 다룰 수 없다
  2. B올림수가 하위에서부터 차례로 전달되므로 비트 수에 비례해 지연이 커진다
  3. C비트 수가 늘어나도 회로 규모가 변하지 않는다
정답과 해설 보기

정답: B. 올림수가 하위에서부터 차례로 전달되므로 비트 수에 비례해 지연이 커진다

리플 캐리 가산기에서는 각 전가산기가 하위에서의 올림수를 기다린 후 계산하므로, 올림수가 최하위에서 최상위까지 차례로 전달되어 지연이 비트 수에 비례해 늘어납니다. 64비트에서는 전가산기 64단분의 지연이 되어 GHz로 동작하는 CPU에는 너무 느립니다. 회로가 작고 단순하므로 속도가 중요하지 않은 용도에 사용됩니다. 고속화에는 캐리 룩어헤드, 캐리 셀렉트, 병렬 프리픽스(Kogge-Stone 등) 가산기가 사용됩니다.

캐리 룩어헤드 가산기가 빠른 이유로 올바른 것은?

  1. A덧셈의 비트 수를 줄이기 위해
  2. B클록 주파수를 2배로 하기 위해
  3. C각 비트의 올림수를 하위에서의 전파를 기다리지 않고 입력으로부터 병렬로 계산하기 때문에
정답과 해설 보기

정답: C. 각 비트의 올림수를 하위에서의 전파를 기다리지 않고 입력으로부터 병렬로 계산하기 때문에

캐리 룩어헤드 가산기는 각 비트의 생성 G = A・B(반드시 올림수를 냄)와 전파 P = A⊕B(하위 올림수를 통과시킴)를 사용하여, C1 = G0 + P0・C0, C2 = G1 + P1・G0 + P1・P0・C0 … 처럼 각 자리의 올림수를 입력으로부터 병렬로 계산합니다. 지연은 비트 수의 로그에 비례해 늘어날 뿐입니다. 다만 식이 길어지므로 4비트 정도의 블록을 계층적으로 조합하여 사용합니다.

캐리 룩어헤드 가산기에서 사용하는 각 자리의 생성 신호 g와 전파 신호 p의 정의(a, b는 그 자리의 입력)와, 윗자리로의 올림 c(i+1)의 식의 조합으로 올바른 것은 무엇입니까?

  1. Ag = a + b, p = a・b, c(i+1) = p + g・c(i)
  2. Bg = a・b, p = a ⊕ b, c(i+1) = g + p・c(i)
  3. Cg = a ⊕ b, p = a・b, c(i+1) = g・p・c(i)
정답과 해설 보기

정답: B. g = a・b, p = a ⊕ b, c(i+1) = g + p・c(i)

그 자리에서 a와 b가 모두 1이면 아래에서의 올림과 관계없이 반드시 올림이 발생하므로 생성 신호는 g = a・b입니다. a와 b 중 한쪽만 1이면 아래에서의 올림을 그대로 위로 전달하므로 전파 신호는 p = a ⊕ b(OR로 하기도 함)입니다. 따라서 c(i+1) = g(i) + p(i)・c(i)가 되며, 이를 전개하면 각 자리의 올림을 입력의 g・p와 최하위 올림만으로 2단의 논리로 병렬 계산할 수 있습니다. 생성과 전파를 바꾼 식으로는 올바르게 계산할 수 없습니다.

  1. 승산기에서 다수의 부분곱을 더하는 데 캐리 세이브 가산기가 사용되는 주된 이유는 무엇입니까?
  2. 고속 승산기에서 사용되는 월리스 트리의 특징으로 올바른 것은 무엇입니까?
  3. 전가산기의 입력으로 올바른 조합은?

컴퓨터 산술 문제 풀기

주요 용어 설명

전가산기(full adder)
두 비트와 아래 자리에서 올라온 캐리의 3입력을 더해 합과 윗자리로의 캐리를 출력하는 회로. 캐리 입력이 없는 것은 반가산기. 직렬로 연결하면 다비트 가산기가 된다.
캐리 룩어헤드 가산기(Carry-Lookahead Adder)
각 자리의 생성 신호 g = a·b와 전파 신호 p = a ⊕ b로부터 자리올림을 하위로부터의 전파를 기다리지 않고 병렬로 구하는 가산기. 비트 수가 많아도 지연이 작다.
캐리 세이브 가산기(Carry-Save Adder)
세 수를 자리올림을 전파하지 않고 '합'과 '자리올림'의 두 수로 정리하는 가산기. 전가산기를 자릿수별로 나열한 것뿐이라 지연이 일정하므로, 승산기에서 다수의 부분곱을 더하는 데 쓰인다.
월리스 트리(Wallace Tree)
곱셈기에서 다수의 부분곱을 캐리 세이브 가산기 트리로 병렬로 줄여 나가는 구성. 단수가 비트 수의 로그 정도로 끝나 고속 곱셈기에 사용된다. 마지막에 두 수를 일반 가산기로 더한다.
부스 알고리즘(Booth's algorithm)
승수의 비트열을 2비트씩 등으로 나누어 부호 있는 자리로 바꿔 부분곱의 수를 줄이는 곱셈 방법. 기수 4 부스 방식에서는 부분곱이 거의 절반이 된다.
크리티컬 패스(Critical Path)
회로 안에서 지연이 가장 크고, 동작할 수 있는 최대 클록 주파수를 결정하는 경로. STA에서는 슬랙이 최소인 경로에 해당하며, 고속화는 이 경로의 지연을 줄이는 것부터 시작한다.

관련 비교