Carry Save Adder

소개

booth algorithm 은 요즘 구현 되고 있는 대부분의 multiplier에 반드시 필요한 곱셈기이다.
이 곱셈기를 구현하기 위해서는 빠른 속도를 가진 Adder가 필요한다. 그 대표적인 Adder가
CSA 이다.
본 레포트 에서는 어떻게 CSA를 구현하지를 설명하고자 한다.

목차

1. booth algorithm
2. Carry Save Adder
- algorithm
- architecture

본문내용

ooth Algorithm

그림 4진 booth 기록을 이용한 곱셈생성부분
그림1 은 4진 Booth 기록을 이용한 곱셈기를 구현한 것이다. 4-radix booth`s recoding에서 Recoding logic은 기본적으로 3 bit의 출력을 받아. 3 bit의 출력을 보낸다. 그리고 이 출력의 3bit는 0, ±1, ±2 이렇게 5가지를 의미하게 된다. neg는 값이 +(0), -(1)을 의미하고, two는 2(1), 1(0)을 의미한다. 그리고 non0는 값이 있음(1), 값이 없음(0)을 의미하게 된다. 따라서 Multiplexer의 출력 값은 0, a, 2a 중 하나로 결정나게 된다.
이렇게 출력된 Add/Substract control과 Zi/2 a값이 Adder의 입력으로 누적해서 들어가게 된다. 이 누적된 Partial product의 합이 전체 C두 값의 합이 되게 된다. 그런데 여기서 이 partial product를 얼마나 빨리 더하느냐가 가장 중요하다. 따라서 CSA(Carry save adder)를 사용한다.


그림 캐리가 전파되는것이 아니라 보존된다면, Ripple-carry adder는 Carry-save adder로 변한다.
Carry Save Adder
Binary
full
adder
(stage i)
Digit in [0, 2]
Digit in [0, 2]
Binary digit
To Stage
i + 1
From
Stage i - 1
Cout
Cin
그림 Carry-save adder를 위한 독립 이진 FA의 사용
두 수의 합으로 크기를 줄이는 방법 보다는 세 수를 두 수로 줄이는 어떤 메커니즘을 사용하는 방법으로 이진 FA의 한 행을 볼 수 있다. 그림2 는 Ripple-carry adder과 Carry- save-adder의 관계를 보여준다.
그림 점표기에서의 CPA와 CSA
그림 점표기에서의 HA와 FA
그림4 은 점 표기로 그림2 의 관계를 나타낸다. 좀 더 정확하게 다양한 점들에서 이 관계가 성립하는지 보기 위해, 박스안에 FA에 입력을 형성하는 어떤 세 점을 포함하고, 그 대각선의 FA의 합과 케리출력을 연결한다(그림5). 때로는 단 두 점이 합과 케리를 형성하기 위해 조합될 수 있다. 이때 두 점은 박스 안에 포함되고, 출력을 연결하는 대각선의 교차되는 선에 의해 HA의 사용이 표시된다. 점 표시는 Carry-save adder의 기능을 또다른 면으로 설명될 수 있다.

참고자료

· 없음