KR100308723B1

KR100308723B1 - 올림수-보존 가산기회로 및 복수의 이진 데이터 비트 합산 방법

Info

Publication number: KR100308723B1
Application number: KR1019960700549A
Authority: KR
Inventors: 레오나르드 데니스 래릭
Original assignee: 박세광; 현대 일렉트로닉스 아메리카 인코포레이티드
Priority date: 1993-08-05
Filing date: 1994-08-01
Publication date: 2001-11-30
Also published as: KR960704266A; US5504915A; JPH09501526A; CN1128069A; WO1995004964A1; CN1101017C

Abstract

본 발명은 이진 승산기에서 사용하기 위한 감소된 수의 전가산기 스테이지를 갖는 올림수-보존 가산기에 관한 것으로, 본 발명의 올림수-보존 가산기는 이진 데이터 컬럼을 합산하고, 복수 1-비트(30) 및 2-비트(60) 전가산기들에 의해 구현된다. 1-비트(30) 및 2-비트(60) 전가산기들은 하나 이상의 컬럼으로부터의 이진 데이터를 합산하여 부분합(74) 및 부분올림수(76)를 산출하는 복수의 상호연결된 개량된 월리스-트리 가산기로 배열된다. 각각의 개량된 월리스-트리 가산기는 다수의 이진 데이터 비트의 수를 감소시키는 1-비트(30) 및 2-비트(60) 전가산기들을 포함하는 복수의 스테이지(70, 110, 130, 150)를 갖는데, 여기서 최종 스테이지(36, 122, 142, 162)는 부분합(74) 및 부분올림수(76)를 산출하는 하나의 1-비트 전가산기(36, 122, 142, 162)를 포함한다. 복수의 도체들이 각각의 개량된 월리스-트리 가산기의 스테이지들을 동일한 월리스-트리 가산기내의 스테이지들 및 다른 개량된 월리스-트리 가산기내의 스테이지들과 상호연결시킨다.

Description

[발명의 명칭]

올림수-보존 가산기회로 및 복수의 이진 데이터 비트 합산 방법{Carry-save adder circuit and a method of summing a plurality of binary data bits}

[기술분야]

본 발명은 디지털 승산방법 및 그 장치에 관한 것으로, 더욱 상세하게는 이진 승산기에서 올림수-보존 가산기(carry-save adder)를 구현하는 방법 및 그 장치에 관한 것이다.

이진 승산기는 컴퓨터적으로 집중적인 계산에 이용되는 디지털 컴퓨터에 있어서 주요 요소이다. 승산 함수는 신속한 구현을 위해 복잡한 회로설계를 필요로 하므로 속도에 대한 병목이 될 수 있다. 따라서, 이진 승산기의 성능 향상은 컴퓨터를 전용하는 적용에 있어 컴퓨터의 성능에 직접적으로 영향을 미친다. 전형적인 이진 승산기는 기본적인 빌딩블럭으로서 올림수-보존 가산기를 구비한다. 월리스-트리 이진 가산기(Wallace-Tree binarry adder; 이하, 'WTA'라 한다)를 이용함은 올림수-보존 가산기를 구현하는 하나의 모습이고, 고속-이진 승산기의 효과적인 구현에 있어 필수불가결한 요소이다. 월리스-트리 가산기는 중간 컬럼 가산(intermediate column addition calculation)을 수행하고, 승산기 예비 곱 결과(multiplier preliminary product result)를 취하며, 컬럼(column) 데이터와 관련된 부분합 및 부분 올림수를 발생시킨다. WTA는 한 쌍의 부분합 및 올림수를 산출한다; 입력 데이터 컬럼마다 하나의 WTA가 요구된다. 더욱이, M-비트×N-비트 승산기에 있어서는, 하나의 WTA 마다 N 비트까지의 입력을 갖는 N+M-1개의 이러한 WTA가 요구된다. 월리스-트리 가산기는 기본적인 빌딩블럭으로 1-비트 전가산기(full adder: FA)를 이용한다. 1-비트 전가산기의 경우에, 3개의 입력 데이터 비트는 두 개의 출력 데이터 비트, 합 및 올림수를 산출한다.

WTA는 일련의 스테이지로 배열된 전가산기의 어레이를 포함한다. 그것은 컬럼 데이터를 초기 크기(N 비트)로부터 요구되는 쌍의 비트, 부분합 및 부분올림수로 감소시킨다. 전가산기(FA) 비트 감소 특성은(즉, 3 입력-2 출력: three-to-two) WTA에서 요구되는 FA 스테이지의 수를 결정한다. 그리고 일정한 계산에 요구되는 스테이지의 수는 전체적인 속도에 직접적으로 영향을 미치기 때문에, WTA의 구현은 처리율 속도에 있어 중요하다.

FA 구현의 3 입력-2 출력 비트 감소 특성은 WTA에 있는 FA 스테이지의 수가 입력 비트수의 로그값에 비례한다는 것이다. 구체적인 예를 들면; 6비트는 3 스테이지를 필요로 하고, 32 비트는 8 스테이지를 필요로 하며, 64비트는 10 스테이지를 필요로 한다. FA 마다의 게이트 지연의 수는 구현에 의존한다. 그럼에도 불구하고, 비트의 수가 커지기 때문에, FA 스테이지의 수 및 그에 따라 승산기를 통한 순수 지연(net delay)이 커진다.

따라서, 입력 비트의 수는 WTA 속도에 실질적으로 영향을 주고, 그 결과로 프로세서 속도에 실질적으로 영향을 미친다. 그러므로, WTA 구현을 위해 요구되는 FA 스테이지의 수에 있어서의 임의의 감소는 일정한 이진 승산기의 처리율 속도를 실질적으로 향상시킬 것이다.

[배경기술]

본 발명에 따라, 스테이지 수가 감소된 전가산기를 갖는 올림수-보존 가산기가 기술된다. 올림수-보존 가산기는 이진 데이터의 세트 또는 컬럼들을 합산하여, 각 컬럼에 대한 부분합 및 부분올림수를 발생시키는 것이다. 특정 컬럼의 이진 데이터 비트들은 동일 차수의 크기를 갖는다. 상이한 컬럼의 이진 데이터 비트들은 차수 크기가 서로 상이하고, 인접한 컬럼은 증가하는 차수로 차수 크기가 하나 만큼 차이가 난다. 올림수-보존 가산기는 복수의 1-비트 및 2-비트 전가산기들을 포함한다. 1-비트 및 2-비트 전가산기들은 복수의 상호연결된 개량된 월리스-트리 가산기(세트 가산기)내에 구성되고, 각각의 개량된 월리스-트리 가산기는 하나 이상의 컬럼으로부터 이진 데이터 비트를 합산하여, 부분합 및 부분올림수를 발생시킨다. 개량된 월리스-트리 가산기들의 수는 이진 데이터의 컬럼의 수와 일치한다. 각각의 개량된 월리스-트리 가산기는 이진 데이터 비트의 수를 감소시키는 1-비트 및 2-비트 전가산기들의 조합을 포함하는 복수의 스테이지를 갖고, 부분합 및 부분 올림수결과를 발생시키기 위한 하나의 1-비트 전가산기를 포함하는 마지막 스테이지를 갖는다. 다수의 도체들은 각각의 개량된 월리스-트리 가산기내의 스테이지들을 동일한 개량된 월리스-트리 가산기내의 스테이지들 및 다른 개량된 월리스-트리 가산기내의 스테이지들과 상호연결하는데, 도체들은 일반적으로 동일한 차수 크기의 이진데이터 비트들을 수신 및 송신하는 입력 및 출력 터미널들을 연결하도록 제한된다.

본 발명은 다수의 이진 데이터 비트들을 합산하는 방법의 견지에서도 기술될 수 있다. 우선, 이진 데이터 비트들은 세트들로 편성되며, 각 세트는 동일한 차수의 크기를 갖는 모든 이진 데이터 비트들을 포함한다. 이어서 이진 데이터 비트들의 각각의 세트는 적어도 하나의 개량된 월리스-트리 가산기 내에 입력되며, 각각의 개량된 월리스-트리 가산기는 다수의 상호연결된 1-비트 및 2-비트 전가산기들을 포함한다. 그 다음으로 이진 데이터 비트의 수는 1-비트 및 2-비트 전가산기들의 연속적인 스테이지에 의해 감소되어, 각 세트의 이진 데이터 비트들에 대한 부분합 결과 및 부분올림수 결과를 발생시킨다.

이하의 본 명세서의 나머지 부분 및 도면을 참고함으로써 본 발명의 특성 및 이점에 대하여 보다 깊이 이해할 수 있을 것이다.

[발명의 상세한 설명]

본 발명의 하나의 양상은 다수의 세트의 이진 데이터 비트들을 합산하여 각 세트에 대한 부분합 결과 및 부분올림수 결과를 발생시키는 올림수-보존 가산기로서, 특정한 세트의 이진 데이터 비트들은 동일한 차수 크기를 갖고, 상이한 세트의 이진 데이터 비트들은 차수 크기가 서로 상이하며, 상기 올림수-보존 가산기는, 다수의 1-비트 전가산기; 다수의 2-비트 전가산기 - 상기 1-비트 및 2-비트 전가산기들은 다수의 상호연결된 세트 가산기로 배열되고, 각각의 세트 가산기는 적어도 하나의 세트로부터의 이진 데이터 비트들을 합산하여 부분합 결과 및 부분올림수 결과를 산출하고, 각 스테이지가 1-비트 및 2-비트 전가산기들의 조합을 포함하는 다수의 스테이지를 구비함 - ; 다수의 올림수-보존 가산기내에서 각 세트 가산기의 스테이지들을 동일한 세트 가산기내의 스테이지 및 다른 세트 가산기내의 스테이지와 연결하는 도체를 포함한다.

본 발명의 올림수-보존 가산기의 상기 1-비트 저가산기는 가수 입력 터미널 A 및 B; 첫 번째 입력-올림수 입력 터미널 C_i; 첫 번째 출력-올림수 출력 터미널 C_o; 및 합계 출력 터미널 S를 포함한다.

본 발명의 올림수-보존 가산기에서, 상기 2-비트 전가산기는 첫 번째 가수 입력 터미털 AO 및 BO; 두 번째 가수 입력 터미널 A1 및 B1; 두 번째 입력-올림수 입력 터미널 C_i; 두 번째 출력-올림수 출력 터미널 C_o; 첫 번째 합계 출력 터미널 SO; 및 두 번째 합계 출력 터미널 S1을 포함하여 구성된다.

본 발명의 올림수-보존 가산기에서, 상기 세트 가산기는 적어도 하나의 세트로부터의 것인 이진 데이터 비트들의 수를 감소시키는 첫 번째 스테이지; 이진 데이터 비트의 수를 더욱 더 감소시키는 다수의 중간 스테이지; 및 부분합 및 부분올림수 결과를 산출하는 하나의 1-비트 전가산기를 포함하는 최종 스테이지를 포함한다. 또한, 상기 각 세트 가산기의 첫 번째 스테이지가 첫 번째 차수의 크기를 갖는 첫 번째 이진 데이터 비트를 받아들이는 더 높은 차수의 입력 터미널과 두 번째 차수 크기를 갖는 두 번째 이진 데이터 비트를 받아들이는 더 낮은 차수의 입력 터미널을 갖는 적어도 하나의 2-비트 전가산기를 포함하며, 여기서 첫 번째 차수 크기가 두 번째 차수 크기 보다 1차수 크기만큼 크다. 본 발명의 올림수-보존 가산기에서, 상기 도체는 동일한 차수 크기의 이진 데이터 비트들을 수신 및 송신하는 입력 및 출력 터미널들을 연결한다.

본 발명의 다른 양상은 다수의 세트의 이진 데이터 비트들을 합산하여 각 세트에 대한 부분합 결과 및 부분올림수 결과를 발생시키는 올림수-보존 가산기로서, 특정한 세트의 이진 데이터 비트들은 동일한 차수 크기를 갖고, 상이한 세트의 이진 데이터 비트들은 차수 크기가 서로 상이하며, 상기 올림수-보존 가산기는 복수의 1-비트 전가산기, -상기 각각의 1-비트 전가산기는 가수 입력 터미널 A 및 B, 첫 번째 입력-올림수 입력 터미널 C_i, 첫 번째 출력-올림수 출력 터미널 C_o, 및 합계 출력 터미널 S를 포함함 - ; 복수의 2-비트 전가산기, - 상기 각각의 2-비트 전가산기는 첫 번째 가수 입력 터미널 A0 및 B0, 두 번째 가수 입력 터미널 A1 및 B1, 두 번째 입력-올림수 입력 터미널 C_i, 두 번째 출력-올림수 출력 터미널 C_o, 첫 번째 합계 출력 터미널 SO 및 두 번째 합계 출력 터미널 S1을 포함하며, 상기 1-비트 및 2-비트 전가산기들은 다수의 상호연결된 세트 가산기로 배열되고, 각 세트 가산기가 적어도 하나의 세트로부터 이진 데이터 비트를 합산하여 부분합 결과 및 부분올림수 결과를 산출하고, 각 스테이지가 1-비트 및 2-비트 전가산기들의 조합을 포함하는 다수의 스테이지들을 구비함 - ; 및 올림수-보존 가산기내에서 각 세트 가산기의 스테이지들을 동일한 세트 가산기내의 스테이지 및 다른 세트 가산기내의 스테이지와 상호연결하고, 동일한 차수 크기의 이진 데이터 비트들을 받아들이고 전송하는 입력 및 출력 터미널들을 연결하는 다수의 도체를 포함하는 올림수-보존 가산기이다.

상기 올림수-보존 가산기에서, 각 세트 가산기의 첫 번째 스테이지는 적어도 하나의 2-비트 전가산기를 포함하고, 첫 번째 스테이지에 있는 각각의 2-비트 전가산기의 A1 및 B1은 첫 번째 세트로부터 첫 번째 차수 크기를 갖는 첫 번째 이진 데이터 비트를 받아들이고, 각각의 2-비트 전가산기의 AO, BO 및 C_i는 두 번째 세트로부터 두 번째 차수 크기를 갖는 두 번째 이진 데이터 비트를 받아들이며, 첫 번째 차수 크기가 두 번째 차수 크기 보다 1 차수 크기만큼 크다.

또한, 상기 올림수-보존 가산기에서, 각각의 두 번째 C_o는 그 다음 높은 차수의 이진 데이터, 비트들을 합산하는 세트 가산기의 스테이지에 있는 A1 및 B1, 및 두 번째 높은 차수의 이진 데이터 비트들을 합산하는 세트 가산기의 스테이지에 있는 A, B, AO, BO, 첫 번째 C_i및 두 번째 C_i로 필수적으로 구성되는 군에 속하는 입력 터미널에만 연결되고; 각각의 첫 번째 C_o및 S1은 동일한 세트 가산기에 있는 A1 및 B1, 및 그 다음 높은 차수의 이진 데이터 비트를 합산하는 세트 가산기의 스테이지에 있는 A, B, AO, BO, 첫 번째 C_i및 두 번째 C_i로 필수적으로 구성되는 군에 속하는 입력 터미널에만 연결되며; 및 각각의 S 및 SO는 동일한 세트 가산기에 있는 A, B, AO, BO, 첫 번째 C_i및 두 번째 C_i와 그 다음 낮은 차수의 이진 데이터 비트를 합산하는 세트 가산기에 있는 A1 및 B1로 필수적으로 구성되는 군에 속하는 입력 터미널에만 연결된다. 또한, 각 세트에 있어서의 상기 이진 데이터 비트의 최대수는 18 또는 55이다.

본 발명의 또 다른 양상은 복수의 이진 데이터 비트들의 합산 방법으로서, 이진 데이터들을 컬럼들로 - 각 컬럼은 동일한 크기의 차수를 갖는 모든 이진 데이터 비트들을 포함함 - 편성하는 단계; 각 컬럼의 이진 데이터 비트들을 적어도 복수의 컬럼 가산기 회로중의 하나 - 각 컬럼 가산기 회로는 복수의 상호연결된 1-비트 및 2-비트 전가산기 회로를 포함하고, 각 컬럼 가산기 회로는 또한 복수의 스테이지를 포함하며, 각 스테이지는 상기 1-비트 및 2-비트 전가산기 회로의 조합을 포함함 - 에 입력하는 단계; 각각의 컬럼 가산기회로에 있는 1-비트 및 2-비트 전가산기회로들의 연속적인 스테이지에 의해 이진 데이터 비트의 수를 감소시키는 단계; 및 복수의 부분합 결과 및 복수의 부분올림수 결과를 발생시키는 단계를 포함한다.

[도면의 간단한 설명]

제1도는 이진 승산 함수 및 전형적인 컬럼 가산 함수의 예시도로서, 상기 도면은 3가지의 함수 서브섹션인 1-비트 승산, 올림수-보존 가산 및 올림수 예견 가산을 예시한 것이다.

제2a도는 입력신호 레벨에 대한 출력 신호 특성을 보여주는 1-비트 전가산기의 함수테이블이다.

제2b도는 2- 및 3- 입력 NOR 로직 및 와이어드 OR 로직에 의해 구현된 1-비트 전가산기의 개략도이다.

제3도는 올림수-보존 가산 함수를 수행하는 1-비트 전가산기들로 구성된 월리스-트리 가산기의 개략도이다.

제4도는 종래의 컬럼-대-컬럼 명명법에 대한 변형을 예시한 1-비트 전가산기들로 구성된 월리스-트리 가산기의 개략도이다.

제5도는 입력 데이터 비트의 수의 함수로서 월리스-트리 가산기내에서 요구되는 1-비트 전가산기 스테이지의 수를 나타낸 다이어그램이다.

제6a도는 입력신호 레벨에 대한 출력 신호 특성을 보여주는 2-비트 전가산기의 함수테이블이다.

제6b도는 2- 및 3-입력 NOR 로직 및 와이어드 OR 로직에 의해 구현된 2-비트 전가산기의 개략도이다.

제6c도는 1-비트 전가산기 및 2-비트 전가산기의 특정한 구현의 실행의 샘플 계산 결과를 나타낸 표이다.

제7도는 2-비트 전가산기를 구비하는 개량된 월리스-트리 가산기의 다이어그램이다.

제8도는 실시예의 첫 번째 두 스테이지에 대하 2-비트 전가산기를 개량된 월리스-트리 가산기내에 구현하는 상호연결 스킴을 도시한 다이어그램이다.

제9도는 입력 데이터 비트수의 함수로서 개량된 월리스-트리 가산기에서 요구되는 스테이지의 수를 나타낸 다이어그램이다.

제10도는 입력 데이터의 비트수에 대한 월리스-트리 가산기에서 요구되는 1-비트 전가산기 스테이지의 수를 개량된 월리스-트리 가산기에서 요구되는 가산기 스테이지의 수와 비교하여 나타낸 표이다.

제11도는 월리스-트리 가산기내에서 한 쌍의 1-비트/2-비트 전가산기 스테이지와 하나의 1-비트 전가산기 스테이지 사이의 상호연결의 가능한 조합들을 나타낸 표이다.

제12도는 첫 번째 및 두 번째 스테이지 사이의 최대의 수의 두 번째로 높은 WTA 상호연결을 이용하고, 2-비트 전가산기 스테이지들의 최적의 적용을 나타낸 35비트 월리스-트리 가산기의 구성도이다.

제13도는 첫 번째 및 두 번째 스테이지 사이의 교차 WTA 상호연결의 혼합을 이용하고, 상호연결 스킴에 있어서의 두 번째 변형예를 예시한 35 비트 월리스-트리 가산기의 구성도이다.

제14도는 전체에 걸쳐 최대의 수의 인접한 교차 WTA 상호연결을 이용하고, 상호연결 스킴에 있어서의 세 번째 변형예를 예시한 35 비트 월리스-트리 가산기의 구성도이다.

[실시예]

[이진 승산 함수]

도 1은 컬럼 가산을 이용하는 이진 승산 함수를 예시한 것이다. 설명된 바와 같이, 이러한 연산은 보통 승수(4) 일 비트를 피승수(6)에 곱한 승산에서 생기는 중간 로우(row, 2)에 의해 우측에서 좌측으로 종이 및 연필 방법으로 이루어진다. 즉, 승수 비트가 1인 경우에, 그 결과로서 생기는 로우(2)는 승수 비트의 차수 만큼 오른쪽으로 쉬프트된, 피승수(6)의 복사판(duplicate)이다. 승수 비트가 0인 경우에, 그 결과로서 생기는 로우(2)는 모두 0이다. 로우(2)는 특정 비트의 파우어(또는 차수)와 관련되어 컬럼(8)에 정렬된다. 이러한 과정의 결과로, N+M-1개 컬럼(N은 피승수(6)에서의 비트수), M개 로우(2)(M은 승수(4)에서의 비트수)가 존재하게 된다. 그 다음으로 실시예에는; 5-비트 승수(4) 및 5-비트 피승수 (6); 비트식 승산 결과를 나타내는 중간 데이터의 5로우(2) 및 9컬럼(8)이 도시되어 있다. 또한 이후에 더 자세히 설명될, 각각 9 비트인 2 로우의 부분합(10) 및 부분올림수(12)가 있다. 그리고 컬럼(8)들에 대하여 합산을 수행한 최종 결과인 최종 합계(14)(10 비트 길이)가 있다. 디지털 계산기에서, 이진 승산은 3개의 함수 섹션으로 분할될 수 있다. 이들은: 1-비트 승산 어레이(16), 올림수-보존 가산기(18) 및 올림수-예견 가산기(20)이다. 이들도 도 1에 도시되어 있다. 1-비트 승산기(16)는 두 개의 입력 워드, 승수(4; M 비트) 및 피승수(6: N 비트)를 취하고, 비트식 승산(bitwise multiply)을 행하여, 편릉형 어레이로 N*M 값을 산출한다. 이것은 데이터의 N+M-1 컬럼(8)을 구성하고, 이것은 이어서 올림수-보존 가산기(18)에 대한 입력 데이터가 된다. 올림수-보존 가산기(18)는 데이터에 대한 기본적인 합산을 실행하여, 중간 결과로서, 컬럼(8)마다 하나의 부분합 비트와 하나의 부분올림수 비트를 산출한다. 이것은 올림수-예견 가산기(20)에 대한 입력 데이터를 구성한다. 올림수-예견 가산가(20)는 최종 합산을 행하여 최종 결과(14), N+M 비트 수를 산출한다. 이진 컬럼 가산 함수는 이진 승산 함수에 있어서 중추적인 계산이다. 본원에서 취급되는 본 발명은 특히 이진 승산 함수와 관련된 컬럼 가산기로서의 올림수-보존 가산기(18)의 구조 개선에 관계한다.

[월리스-트리 가산기(Wallace-Tree Adder: 이하 'WTA'라 한다.)]

월리스-트리 이진 가산기는 이진 승산기내 올림수-보존 가산기(18)의 구현시의 통상의 빌딩 블록이고, 고속 이진 승산기의 효과적인 구현에 필수불가결한 요소이다. WTA는 상술한 바와 같이, 중간 계산을 위한 컬럼 가산기로 기능하고, 중간 컬럼 합산을 수행하여 컬럼(8) 마다 1 비트 부분합 및 1 비트 부분올림수를 산출한다. 컬럼(8)마다 이러한 WTA가 하나 존재한다. WTA 마다 N 비트까지의 입력을 갖는 N×M 비트 승산기(16)에 대해 요구되는 N+M-1개의 이러한 가산기들이 존재한다. 이러한 적용예에서는 부스 코드화(Booth encoding)를 이용하거나 또는 이용하지 않을 수 있는 WTA의 몇 가지 공통적인 구현 형태들이 존재한다. 나무-유사 구조로 된 한벌의 1-비트 가산기들(FAs)을 이용하는 WTA의 구현은 본원에서 고려된 특정한 종래의 접근방식이다. 확인될 바와 같이, 이러한 구현은 다수의 FA 스테이지를 만드는데, 이들의 수는 입력 데이터 비트수의 로그값에 비례한다.

[1-비트 전가산기(One-Bit Full Adder : 이하 'FA'라 한다.)]

1-비트 전가산기는 WTA의 구현을 위한 종래의 기본적인 빌딩블럭이다. 1-비트 전가산기의 기초적인 연산 특성은 도 2a에 도시된 함수테이블(22)에 예시하였다. 1-비트 전가산기는 다음과 같은 특성을 갖는다: 세 개의 입력 데이터 비트는 두 개의 출력 데이터 비트를 산출한다. 입력 데이터 포트(24)들은 통상 문자 A, B, C_i(carry in)로 표시되고; 출력포트(26)들은 S(Sum) 및 C_o(carry out)로 기술된다. 함수테이블(22)은 3가지의 입력 이진 데이터의 모든 가능한 조합(8)의 함수로서, 결과된 출력 데이터를 나타낸 것이다. 함수테이블(22)은 또한 FA가 이진 계수기로 기술되어 아래와 같이 될 수 있음을 보여준다.

입력이 모두 0일 때, 출력은 0 (즉, S=C-0);

입력중 임의의 하나가 1일 때, 출력은 1 (즉, S=1, C_o=0);

입력중 임의의 한 쌍이 1일 때, 출력은 2 (즉, S=0, C_o=1); 및

입력이 모두 1일 때, 출력은 3 (즉, S=C_o=1).

함수테이블(22)은 FA 응답이 입력 1(또는 0) 들의 개수에만 의존하고, 어느 포트가 여기되었는지에는 의존하지 않는다는 사실을 보여준다. 즉, FA는 모든 입력 포트를 동등하게 처리하기 때문에 상호교환 가능하다(interchangeable). 이러한 사실은 S 및 C_o포트의 특성이 서로 상이하고 동등한 것으로 처리될 수 없는 출력 포트에 대해서는 적용되지 않는다. FA(30)의 특정한 구현을 도 2b에 게르트 레벨로 개략적으로 도시하였다. 여기서, FA 함수는 각각 최상단 및 최하단에 표기된 입력(C_i, A 및 B)들 및 출력(C_o및 S)들을 갖는 NOR 논리 소자(32)를 이용함으로써 발생되고, 상기 회로들은 FA(30)에 대해서 함수테이블(22)의 특성을 정확하게 실현시킨다. 와이어드 OR(Wired OR) 소자들은 물론 2- 및 3- 입력 NOR 논리 소자(32)들이 이용된다. NOR 논리 소자(32)의 특성은 일정한 소자의 출력이 모든 입력이 0으로 설정되는 경우에만 1로 된다는 것이다. 이러한 특수한 구현은 이하에서 추가로 논의될 2- 컬럼 가산기와의 처리율 속도 비교를 위해 이용된다.

[종래의 월리스-트리 이진 가산기의 구현]

FA(30)은 일반적으로 WTA의 구현에 있어 기본적인 빌딩블럭으로 이용된다. 이러한 구현은 본원에서 논의되고, WTA(34)의 구현의 일례를 도 3에 개략적으로 도시하였다. 이것은 5 스테이지(36)로 되어있는 11개의 FA 소자(30)들을 이용한 13-비트 입력-2-비트 출력 월리스-트리 가산기로서, 이러한 적용을 위한 종래의 배열을 나타내는 것이다. 일정한 컬럼(8)과 관련된 13개의 입력 비트에 대한 입력 터미널(38)들은 도면의 최상단을 가로질러 표시되었다. 이러한 회로는 컬럼 가산기이기 때문에, 입력 비트의 체계는 없다. 즉, 이러한 로우에 대한 1-비트 승산 함수로부터의 임의의 소자는 임의의 편리한 입력 터미널(38)에 연결될 수 있다. 사실상, 컬럼에 있는 임의의 특정 비트는 임의의 이용가능한 입력 터미널(38)에 입력될 수 있다. 이러한 예에서, 12 비트의 입력 데이터는 4개의 FA(30)의 첫 번째 스테이지(36)를 통해서 처리된다. 1비트는 직접 두 번째 스테이지(36)로 루트가 정해진다. 첫 번째 스테이지(36)의 출력은 도면에서 40으로 표기된, 그 다음 높은 차수의 비트 컬럼으로 루트가 정해지는 각각의 출력-올림수(C_o; carry-out) 포트로부터의 출력에 의해 12 입력 비트에서 8 비트로 감소된다. 두 번째 스테이지(36)에 대한 부가적인 입력은 도면에서 42로 표기된 그 다음 낮은 차수의 비트 컬럼의 C_o포트로부터 유래된다. 유사한 방식으로, 두 번째 스테이지(36)는 입력 테이터를 처리하여, 비트수를 9에서 6으로 감소시키고, 계속하여 하나의 부분합 비트(44) 및 하나의 부분올림수 비트(46)를 산출하는 하나의 FA(30)까지 감소시킨다. 더욱이, 각각의 FA(30)로부터의 각각의 출력-올림수 비트는 그 다음 높은 차수의 비트 컬럼에 연결된다. 그리고, 유사한 방식으로, 그 다음 낮은 차수의 스테이지로부터의 각 출력-올림수 결과는 이러한 컬럼에 연결된다.

논의중인 WTA(34)를 설명하는 도면들의 복잡성을 줄이기 위한 수단으로, 그 다음 높은 차수의 비트 컬럼으로의 및 그 다음 낮은 차수의 컬럼으로부터의 출력-올림수 데이터의 상호연결을 설명하는 변형된 스킴을 도 4에 도시하였다. 그 안에 숫자(이 경우에는 1)가 기재되어 있는 원으로 도시된 표시는 40 및 42를 대신하는 것이다. 더욱이, 이후의 논의에서 숫자 2가 기재된 원도 나타날 것이다. 이것은 출력-올림수 데이터의 상호연결이 두 번째 높은 차수의 비트 컬럼에 연결되고, 입력이 두 번째 낮은 차수의 비트 컬럼으로부터 유래된다는 것을 의미한다. 부가적인 확장이 추가로 이용될 것이다. 즉, 원의 내부에 음수를 이용하는 바, 이것은 상호 연결 스킴에 대한 역의 의미이다. 예를 들어, -1이 포함된다면, 출력 데이터 흐름이 "이전의 컬럼으로"연결되고, 입력 데이터가 "다음 컬럼으로부터" 유래된다.

도 5는 FA의 스테이지들을 포함하는 WTA의 특성을 더 설명하기 위한 것으로, 요구되는 1-비트 전가산기의 수(하단을 가로질러 1-9) 대 입력 컬럼 데이터 비트의 수(3부터 63비트까지)를 도시한 다이어그램이다. 이 도면은 비트의 범위에 대한 샘플 레이아웃에 의해 유도되고, 원 앤드 투(one and two) 방식으로 교차되는 가지들로 구성되는 대로 4번째 비트로부터 일반화 될 수 있다. 이 도면은 또한 주어진 수의 스테이지에 대한 최대 입력 비트수를 나타낸다. 이와 관련하여 중요한 것은 13 비트(우리의 실시예)가 FA 스테이지를 이용하는 5-스테이지 WTA에 종래의 방법으로 부가될 수 있는 입력 비트의 최대수라는 것이다. FA의 3입력-2출력 데이터 비트 감소 특성은 그 수가 입력 데이터 비트수의 로그값에 비례하고, 그의 스테이지 당 비트 감소율이 1.5의 최대값을 갖는 한 벌의 스테이지를 만들어낸다.

[2-비트 전가산기(Two-Bit Full Adder: TFA)]

본 발명에 의하면, 1-비트 전가산기 외에, 2-비트 전가산기도 개량된 WTA의 구현을 위한 기본적인 빌링 블럭의 하나이다. 2-비트 전가산기(Two-Bit Full Adder: TFA)의 기초적인 연산 특성이 도 6a에 도시된 함수테이블(50)에서 설명된다. 상기 TFA는 다음과 같은 특성을 갖는다: 5 입력 데이터가 3 출력 데이터를 산출한다. 입력 데이터 포트(52)는 통상적으로 문자 AO, BO, C_i(carry-in), A1 및 B1로 표현하고; 출력 데이터 포트(54)는 SO(sum zero), S1(sum 1) 및 C_o(carry- out)으로 나타내었다. 함수테이블(50)은 결과되는 출력 데이터를 5 입력의 모든 가능한 32 가지의 조합의 함수로서 나타낸 것이다. TFA는 하나의 FA의 출력-올림수가 내부적으로 두 번째 FA의 입력-올림수에 연결된 병렬의 한 쌍의 FA로 생각할 수 있다. 이것은 5 입력 및 3 출력을 설명해주고 입력 및 출력 사이의 함수 관계를 설명해준다. 더욱이, TFA의 함수 특성은 또한 A1 및 B1 입력 그리고 AO, BO, 및 C_i입력 사이에 차이가 만들어져야 한다는 것을 설명해준다. 즉, TFA는 모든 입력 포트들을 동등하게 취급하지 않는다. A1, B1 입력은 그 다음 높은 차수의 비트와 관련되는 것으로 간주되어야 한다. 출력과 관련하여서는, S1이 그 다음 높은 차수의 비트와 관련되는 것으로 간주되어야 하고, C_o는 두 번째 높은 차수의 비트와 관련되는 것으로 간주되어야 한다. 위에서 지적한 바와 같이, TFA는 병렬의 두 개의 FA로 간주될 수 있다. 이러한 배합은 유리하게 이용될 것이고, 이하에서 추가로 기수 될 것이다.

TFA(60)의 특정한 구현을 게이트 레벨에서 개략적으로 도 6b에 도시하였다. FA와 마찬가지로, TFA 함수는 각각 최상단 및 최하단에 표기되어 있는 입력 및 출력을 갖는 NOR 논리소자(32) 및 와이어드 OR(Wired OR) 소자를 이용함으로써 발생되는데, 상기 회로는 TFA(60)에 대해서 함수테이블(50)의 특성을 정확하게 실현시킨다. TFA(60)가 병렬의 한 쌍의 FA라는 것을 명확하게 실현하기 위해 상기 특정한 개략적 배열을 도시하였다. 또한, 이러한 특정한 구현은 요구되는 게이트 레벨의 수와 관련하여 FA의 구현과 비교될 수 있다. 즉, 두 가지 구현에 있어서, 동일한 수의 게이트 레벨, 즉, 4개가 요구됨을 알 수 있다. 따라서, 두 종류의 회로의 일정한 구현에서, 두 장치들이 거의 같은 지연 시간을 제공할 것이라는 주장이 제기될 수 있다. 이러한 주장은 특수한 CMOS 구현을 위한 컴퓨터 시뮬레이션에 의해 입증되었다. 이러한 시뮬레이션의 결과들은 FA(30) 및 TFA(60) 양자에 대해 도 6c의 표(64)에 나타내었다. 표(64)는 장치 입력으로부터 특정 출력까지의 최악의 경우의 지연시간을 나타낸 것이다. 상기 결과는 TFA에서 S1 출력에 대한 1.6 nsec 지연에 비해, FA의 경우 합 출력에 대한 지연시간이 1.4 nsec임을 보여준다. 이러한 결과들은 양자 모두 기술 의존적이고 구현 의존적일지라도, 그럼에도 불구하고 이들은 양자의 회로가 본질적으로 동일한 속도로 작동할 것이라고 하는 본래의 주장을 입증해준다.

[개량된 월리스-트리 가산기]

올림수-보존 가산기의 개량된 버젼은 개량된 월리스-트리 가산기에 의해 구현될 수 있다. 이러한 개량은 동일한 포트-대-포트 함수를 실행하면서도 더 적은 수의 스테이지를 이용하도록 적당하게 FA 및 TFA가 혼합된 회로 구조의 구현 및 TFA 입력/출력 신호 요구에 기인하는 변화를 책임질 수 있도록 하는 상호연결 회로 구조에 대한 적절한 개량으로 구성된다. 이러한 개량은 WTA에서의 스테이지의 수를 감소시킴으로써, 결과적으로 올림수-보존 가산기의 성능을 향상시킨다. 상기 개량을 본원에서는 도 7에 도시된 13 비트 올림수-보존 가산기의 일부분에 의해 설명한다. 이 특별한 WTA 회로(70)는 앞부분의 설명(도 4)과 기능적으로 동등하지만, 앞에 나왔던 종래의 WTA(34)보다 하나 적은 스테이지를 갖는다. 이러한 개량된 WTA(70)를 설명하기 위해, 우리는 출력에서 시작하여 역방향으로 설명해나갈 것이다. 네 번째인 마지막 스테이지(72)는 2개의 출력 비트인, 부분합(74)과 부분올림수(76)를 제공하므로, FA(30)에 매우 적합하게 된다. 이 스테이지에 대한 입력은 3개의 입력을 필요로 하므로, 하나의 TFA(60)는 세 번째 스테이지(78)에 매우 적합하게 된다. 최초의 WTA(34)와 이러한 개량된 WTA(70)에서 상호연결 사이의 가장 중요한 차이점은 데이터가 인접한 컬럼 가산기로 및 그 가산기로부터 연결되는 방식이다. TFA(60)의 경우에는, 인접한 그 다음 WTA_S내외로 입출력되는 S1 출력 외에, 출력-올림수(C_o)가 떨어져 있는 두 번째 WTA_S내외로 입출력된다. 더욱이, 일반적으로 양자의 입력 A1 및 B1도 다음의 더 높은 차수의 WTA로부터 유래된다. 이러한 고찰은 세 번째 스테이지(78)로부터의 출력이 상술한 바와 같이 연결되는 세 번째 및 네 번째 스테이지(78 및 72) 사이의 상호연결 스킴을 예시하였다. 더 나아가, 이러한 네 번째 스테이지에 대한 입력은 다음과 같다.

B에 대한 입력은 세 번째 스테이지의 SO로부터 유래되고;

A에 대한 입력은 이전의 낮은 차수의 WTA의 A1으로부터 유래되고; 및

C_i에 대한 입력은 이전의 두 번째 WTA의 C_o으로부터 유래된다.

이것은 이전의 낮은 차수의 WTA의 S1으로부터의 출력이 현재의 WTA의 차수와기능상 동등하고, 그 다음 이전의 WTA의 C_o로부터의 출력이 기능상 현재의 WTA와 동등하기 때문이다. 이러한 동등성은 또한 도 7에서 두 번째 스테이지(80) 및 세 번째 스테이지(78)의 TFA(60) 사이의 상호연결에 대해서도 설명된다. 여기서, 그 다음 높은 차수의 비트 레벨에 있는 S1 출력은 세 번째 스테이지(78)의 B1 입력에 연결된 것으로 나타난다. 이것은 B1 입력이 그 다음 높은 차수의 비트 레벨로부터의 입력을 필요로 하기 때문이다.

출력에서 시작하여 역으로 입력으로 설명을 진행하자면, 세 번째 스테이지(78)에 대해 요구되는 5 입력은 당연히 한 쌍의 FA(30) 및 TFA(60)를 필요로 한다. 상호연결은 상술한 설명대로 이루어진다. 최종적으로, 두 번째 스테이지에 대해 요구되는 8 개의 입력은 당연히 두 개의 TFA(60) 및 하나의 FA(30)의 설정을 초래한다. 첫 번째 스테이지의 하나의 FA/TFA 쌍은 두 번째 스테이지의 TFA(60)을 구동하고, 다른 TFA(60)는 두 번째 스테이지(80)의 FA(30)를 구동한다. 첫 번째 스테이지(82)에 대한 입력, A1 및 B1 포트에서 그 안에 -1이 적힌 원은 다음 단락에서 논의하겠다. 이렇게, 개량된 WTA(70)의 설정 및 상호연결이 설명된다.

올림수-보존 가산기 배열의 구조에 대한 나머지 개량은 입력 컬럼 데이터가 분포되는 방식의 재구성이다. 즉, TFA(60)들의 A1 및 B1 입력이 그 다음 높은 차수의 비트 레벨과 결합되기 때문에, 이것은 입력 컬럼 데이터가 이것을 고려할 것을 요한다. 그리고 이러한 요구는 위에서 설명되고 도 7에 도시된 바와 같이 WTA(70)에 대한 입력에서 -1이 적힌 원이 필요하게 만든다.

이러한 상호연결 스킴을 도 8에 예시하였다. 도 8에는 세 개의 연속적인 개량된 WTA(70)에 대한 컬럼 입력 데이터 연결을 도시하였고, 연결은 X로 표기하였다. 이것은 또한 13 비트예로서, 각각의 개량된 WTA(70)의 첫 번째 및 두 번째 스테이지(82 및 80) 양자에 대한 입력의 연결 스킴을 나타내 준다. 세 세트의 선(점선(84), 굵은 실선(86) 및 가는 실선(88))은 세 개의 개개의 13-비트 WTA(70)(즉, 두 개의 TFA(60) 및 하나의 FA(30)를 포함하는 첫 번째 스테이지)에 대한 입력 양상을 나타낸다. 첫 번째 스테이지에서 굵은 실선(86)을 맨 밑에서 맨 위까지 검토해보면 입력 컬럼 n으로부터 TFA들 중 하나로의 세 개의 입력(비트 1,2 및 3)들이 존재한다. 또한 위에서 언급한 바와 같이, 입력 컬럼 n+1로부터 두 개의 부가적 입력(비트 4 및 5)들이 동일한 TFA 내 A1 및 B1로 추가로 입력된다. 마찬가지로, 상술한 상호연결 스킴에서 요구되는 바와 같이, 입력 컬럼 n의 입력 비트 4 및 5는 인접하는 개량된 WTA의 A1 및 B1 입력으로 연결된다(점선으로 표시된). 굵은 실선으로 표시된 WTA에 대한 그 다음의 3개의 입력(비트 6,7, 및 8)은 FA의 3 입력이고, 따라서, 모두 입력 컬럼 n으로부터 유래된다. 나머지 연결(비트 9 내지 13) 들은 처음 5개 비트 연결과 동일한 것이다.

첫 번째 스테이지로부터의 출력은 도시된 입력에 대한 연결 스킴에 의해 8 비트의 데이터 비트를 산출한다. 두 번째 스테이지(80)의 입력 연결 스킴은 첫 번째 스테이지의 처음 8 비트를 정확하게 복제한 것이고, 8 비트에 대한 전형적인 연결 스킴이다.

TFA(70)들 및 FA(30)들의 조합으로 구성된 스테이지를 포함하는 WTA(70)의 특성을 도 9에서 추가로 설명하였다. 도 9는 요구되는 가산기 스테이지의 수 대비 입력 3부터 58 비트까지의 컬럼 데이터 비트수를 도시한 것이다. 이 도면은 도 5와 유사하다. 도 9는 일정한 수의 스테이지에 대한 최대 입력 비트수를 나타낸다. 이와 관련하여 중요한 것은 13 비트(우리의 이전의 실시예에서)가 4-스테이지 WTA의 경우에 입력 비트의 최대수라는 것이다. 이것은 FA만을 갖는 WTA 구현보다 1 스테이지 적은 것이다. 이것은 스테이지당 5입력-3출력 데이터 비트 감소율이 단지 1.5인 것과 대조적으로 1.667의 최대값을 갖기 때문이다.

우리는 N-입력 데이터를 2-출력 비트로 감소시키는 일정한 월리스-트리 가산기의 경우에 N 부분합을 단지 두 개의 부분합만으로 감소시키는데 요구되는 스테이지의 수를 다음 식에 의해 어림할 수 있다:

(M/P)＾(스테이지의 수)=N/2 (1)

여기서, M은 개개의 가산기 당 입력 비트의 수이고, P는 가산기에 대한 출력 비트의 수이다.

상기 식은 스테이지의 수의 파우어로 상승된 스테이지당 감소(즉, M/P)가 입력 대 출력 비율과 같다는 것을 나타낸다. 스테이지 수는 다음과 같이 산출한다.

스테이지의 수=(logN-log2)/(logM-logP) (2)

상기 식은 보다 활용가치가 적은데, 왜냐하면 M/P에 의한 각각의 승산 이후 에 결과는 다음 정수까지 반올림되어야 하기 때문이다.

M=3, 및 P=2인 1-비트 전가산기만을 이용하는 경우, 상기 식 (2)는 다음을 산출한다:

스테이지의 수=(logN-.30103)/.17609 (3)

각 스테이지에서 소거된 부분합의 수가 이전 스테이지의 그 수의 1/3이하이기 때문에, 우리는 스테이지 당 감소가 0.33333임을 알 수 있다. 이와 반대로 M=5, 및 P=3인 2-비트 전가산기를 이용함으로써, 상기 식 (2)는 다음을 산출한다:

스테이지의 수=(logN-.30101)/.22185 (4)

각 스테이지에서 소거된 부분합의 수가 이전 스테이지의 그 수의 3/5이하이므로, 우리는 스테이지 당 감소가 0.4임을 알 수 있다. 따라서, 우리는 감소율(M/P)이 2-비트 전가산기의 경우 1-비트 전가산기에 비해 최대 20% 정도 더 높다는 것을 확인할 수 있다.

위에서 나타낸 바와 같이, TFA의 5입력-3출력 데이터 비트 감소 특성은 FA만으로 구현된 WTA 보다 높은 감소 요소를 같는 WTA 가산기 스테이지를 만들어낸다. 도 10은 종래의 월리스-트리 가산기에서 요구되는 1-비트 전가산기 스테이지(92)의 수와 개량된 월리스-트리 가산기에서 요구되는 가산기 스테이지(94)의 수(1-비트 전가산기 및 2-비트 전가산기의 조합으로서)를 입력 데이터(96)의 비트수에 대하여 비교한 표(90)이다. 이 표(90)는 도 5 및 도 9에 도시된 것과 동일한 데이터를 제공하지만, 본 발명의 특징을 종래의 배열의 특징과 비교하는 수단을 제공할 수 있도록 다소 상이한 형태로 나타낸 것이다. 표(90)은 또한 마지막 컬럼(98)에서, 종래의 배열 대 개량된 배열 각각에 대해 요구되는 스테이지의 수 사이의 차이로 개량을 입증해준다. 개량된 WTA가 요구되는 스테이지의 수를 감소시키지 않는 경우는 단지 네 가지 경우뿐이다: 즉, n의 경우, 비트의 수가 3,4,6, 및 9와 동일한 경우.

[개량된 월리스-트리 가산기 회로 구현의 다양성]

가산되는 각각의 컬럼 비트의 수와 관련하여 다수의 가능한 회로 구현이 존재한다. 우리는 13 비트의 예를 이용하였는데, 이는 그것이 편리한 크기이고 본 발명의 모든 현저한 특징들을 설명할 수 있기 때문이다. 그러나, 다른 많은 가능한 구현이 존재하기 때문에, 우리는 이러한 가능한 변형의 정도를 알리는 수단으로 몇 가지 보다 구체적인 예를 더 설명한다.

이하에서 하나의 FA/TFA 쌍 및 하나의 TAF 사이의 상호연결에 대해 이루어질 수 있는 가능한 회로 조합을 고찰한다. 이러한 상호연결은 전형적인 WTA 구현을 통해서 수득될 수 있고, 이러한 두 세트의 회로 감소 특성의 결과로 당연히 수득할 수도 있다. 한편, 동등한 기능을 발휘하는 스테이지-간 연결 스킴(inter-stage connection scheme)도 매우 다양하다.

하나의 TFA에 연결된 하나의 FA/TFA 쌍의 상대적으로 단순한 조합에 있어서, 10 가지의 서로 상이한 상호연결 조합이 존재한다. 수득할 수 있는 가능한 회로 조합을 도 11에 도시하였다. 즉, 표(100)의 각 컬럼(102)은 특수하고 유일한 회로 배열에 해당한다. TFA의 세 가지의 입력 AO,BO,또는 C_i중 임의의 것에 대한 입력이 모두 동등한 이상은, 상이한 회로 배열로 간주되지 않는다. 이와 같은 사실은 TFA에 대한 한 쌍의 입력, A1 및 B1에 대해서도 똑같이 적용된다. 이와같이 동등한 것도 서로 다른 것으로 간주된다면, 가능한 조합의 총수는 12배정도 배가될 것이다(즉,3!*2!). 표의 컬럼(table columns)들은 비트 레벨 상호연결을 나타낼 뿐이다. 즉, 하나의 TFA내에는 두 개의 가능한 서로 다른 비트 레벨들이 존재한다. 즉, 동일한 컬럼 및 그 다음 인접한 컬럼(들). 이들은 각각 (1) 및 (2)로 호칭되고, 동일한 컬럼이 국부적으로: 1 위치, (1); 2 위치, (2)에 있는 것으로 간주될 수 있다고 하는 고찰과 관련된다. 더욱이, 그 회로의 출력-올림수에 해당하는 TFA의 출력으로부터 4 위치, (4)가 존재한다. FA/TFA 쌍으로부터 3개의 서로 상이한 출력 레벨이 존재한다: 즉, 각각 FA 및 TFA로부터 유래된 동일한 컬럼으로부터의 출력([1]); 각각 FA 및 TFA로부터 유래된 그 다음 인접한 컬럼으로부터의 출력([2]); 및 TFA로부터 유래된 떨어져 있는 두 번째 컬럼으로부터의 출력([4]).이 표(100)에서, FA/TFA 쌍의 출력으로부터 다음 하나의 TFA에 대한 상호 연결을 상술한 명명법을 이용하여 도시하였다. FA/TFA쌍을 하나의 TFA 비트로 감소시키는(즉, 8 입력- 3 출력)적용에 있어서는 10 가지의 서로 다른 상호연결 조합이 존재한다. 예를 들면, 13비트 실시예(도 7)는 도면의 첫 번째 컬럼에 표현된 조합으로 연결된다: 즉, [1], [1], [1], [2] 및 [2]. 이러한 배열은 첫 번째 및 두 번째 스테이지 사이에 이용됨은 물론 두 번째 및 세 번째 스테이지 사이에도 이용된다.

논의중인 WTA를 나타내는 도면의 복잡성을 더욱 더 줄이기 위한 수단으로, 도 12 내지 도 14에서는 FA(30) 및 TFA(60) 부속회로(subcircuits)를 나타내는 변형스킴을 이용하였다. 즉, 관련된 터미널 표시(즉 A, AO등)는 생략하였다. 이것은 연결의 순서를 동일하게 유지하는 규칙에 의해 설명된다. 즉, 예를 들어, TFA에서, 입력 터미널들은 상단을 가로질러, 좌측에서부터 우측으로: C_i, B1, BO, A1, 및 AO이다. 그리고, 출력 터미널들은 하단을 가로질러 좌측에서부터 우측으로: C_o, S1, 및 SO이다.

이러한 설명은 가능한 상호연결 스킴의 다양성의 다른 예를 보여주는 도 12 에 예시된다. 이러한 예는 35-비트 월리스-트리 가산기(110)이다. 이들은 6 스테이지의 가산기(30 및 60)들이고, 이들은 첫 번째 스테이지를 가로지르는 모든 TFA(60)들을 이용하며, 그렇게 함으로써 6 스테이지 가산기(110)에 의해 처리될 수 있는 비트수를 최대화한다. 본 실시예에서, 최소수의 상호연결은 첫 번째 스테이지(112)의 7 TFA(60)의 출력(및 두 번째 스테이지(114)로의 입력)으로부터 다른 WTA(110)으로 연결된다. 이것은 두 번째로 높은 차수의 WTA 상호연결(2가 기재된원)의 최대화에 의해 달성된다. 도 11의 하나의 FA/TFA 쌍 및 하나의 TFA로부터의 가능한 상호연결의 4가지 예들은 도 12에서 설명된다. 이들 예들은 스테이지 4 및 5(118 및 120)사이의 배열 #3, 스테이지 3 및 4(116 및 118) 사이의 #6, 스테이지 2 및 3(114 및 116) 사이의 각각 중앙 및 우측면의 #2 및 #5이다.

35-비트 개량된 월리스-트리 가산기의 두 번째 예(130)를 도 13에 도시하였다. 이러한 상호연결의 변형은 상술한 회로(도 12)와 동등한 기능을 실현하지만, 이 경우에 첫 번째 스테이지(132)의 7 TFA(60)로부터의 출력에 대한 교차(cross) WTA 상호연결의 혼합(mix)을 이용한다(1 및 2가 기재된 5 개의 원). 도 13은 도 11의 하나의 FA/TFA 쌍 및 하나의 TFA 사이의 4가지가 추가된 상호연결 스킴을 보여준다. 구체적으로, 배열 #9, #8, #10, 및 #7이 스테이지 4 및 5(138 및 140) 사이, 스테이지 3 및 4(136 및 138), 그리고 스테이지 2 및 3(134 및 136)사이의 중간 및 우측에 각각 설명되어 있다.

35-비트 개량된 월리스-트리 가산기의 세 번째 예(150)를 도 14에 도시하였다. 이러한 상호연결의 변형은 상술한 회로(도 12 및 도 13)와 동등한 기능을 구현하지만, 이 경우에 상기 구현은 전체에 걸쳐 최대의 수의 인접한, 그 다음 높은 차수의 교차 WTA 상호연결(1이 기재된 가산기 원)을 이용한다. 도 14의 회로는 또한 도 11의 하나의 FA/TFA 쌍 및 하나의 TFA 사이의 하나의 추가 가능한 상호연결 스킴을 이용한다. 구체적으로, 배열 #4는 스테이지 4 및 5(158 및 160) 사이에 설명 도시되었다. 가능한 상호연결 스킴의 다양성의 광범위한 실시예로서, 도 12 및 도 13에 예시된 35-비트 가산기(110 및 130)의 두 번째 스테이지(114 및 134)를 고려할 수 있다. 21비트를 13비트로 감소시키는 세 개의 TFA(60)와 두 개의 FA(30)가 있다. 도 14의 실시예에 다른 동등한 변형을 예시하였다. 이 실시예에서 두 번째 스테이지 배열은 20비트를 12비트로 감소시키고, 21번째 비트가 두 번째 스테이지(154)를 우회하여 세 번째 스테이지(156)의 입력으로 직접적으로 연결되도록 하는 네 개의 TFA(60)를 이용한다. 이러한 스킴은 이전의 조합과 기능상 동등하여, 요청되는 대로 첫 번째 스테이지(152)의 21-비트로부터 세 번째 스테이지(156)의 13비트 입력으로의 감소를 제공한다. 그러나, 이러한 특수한 상호연결은 모두 두 번째 및 세 번째 스테이지 양자에 대해, 대다수의 이전의 실시예에서 이용된 하나의 TFA감소 스킴에 FA/TFA 쌍 이용을 피한다. 하나의 FA/TFA 쌍이 세 번째 스테이지(156)에 나타나지만, 출력 상호연결은 우측 회로, 다른 FA(30)로 넘어간다. 더욱이, 후속되는 하나의 TFA에 대한 입력은 세 번째 스테이지의 모든 소자(즉, TFA_S및 FA)로 부터 유래된다. 이것은 요구되는 기능상의 동등성 및 최소수의 스테이지를 유지하면서, 일정한 월리스-트리 가산기에서 FA(30)와 TFA(60)를 연결하는 다수의 상이한 방식이 존재한다는 것을 입증하기 위해 행해진다. 이것은 또한 동등 상호연결 스킴들이 어떠한 종류의 균일성, 주기성, 반복성, 또는 고유의 부속회로 구조에도 의존하지 않는다는 것을 입증해준다. 실제로, 일정한 세트의 회로 타입(FA/TFA 쌍 및 하나의 TFA의 조합과 유사한)에 대해서 뿐만 아니라, 다수의 적합한 TFA 및 FA의 조합의 설정에 의한 가능한 높은 차수의 조합 혼합(combinatorial mixes)이 있는데에서 다수의 가능한 상호연결 스킴이 존재한다. 따라서, 식 [2]에 의해 어림되고도 9에 정확하게 도시된 결과들은 가능한 회로 조합의 다양성에 의해 수득된다.

본 발명이 본 발명의 구체적인 실시양태를 참고하여 구체적으로 시현되고 기술되었다고 하더라도, 본 발명의 정신 및 범주를 벗어나지 않고도 본 발명의 형태 및 세부사항에 대한 전술한 및 기타의 변형들이 당업자들에 의해 이해될 수 있을 것이다.

Claims

다수 컬럼의 이진 데이터 비트들을 합산하여 복수의 부분합 결과 및 복수의 부분올림수 결과를 발생시키되, 특정 컬럼의 이진 데이터 비트가 동일한 차수 크기를 갖고, 상이한 컬럼의 이진 데이터 비트는 차수 크기가 서로 상이하게 되어 있는 올림수 보존 가산기회로에 있어서, 복수의 1-비트 전가산기회로; 복수의 2-비트 전가산기회로, - 상기 1-비트 및 2-비트 전가산기회로는 복수의 상호 연결된 컬럼 가산기회로로 배열되고, 각각의 컬럼 가산기회로는 적어도 하나의 컬럼으로부터 이진 데이터 비트들을 합산하여 부분합 결과 및 부분올림수 결과를 산출하며, 각각의 컬럼 가산기회로는 복수의 스테이지를 구비하고, 각각의 스테이지는 1-비트 및 2-비트 전가산기회로의 조합을 포함함 - ; 및 각 컬럼 가산기회로의 스테이지들을 동일한 컬럼 가산기회로내의 다른 스테이지 및 올림수-보존 가산기회로내의 다른 컬럼 가산기회로내의 스테이지와 상호 연결하는 복수의 도체를 포함하는 것을 특징으로 하는 올림수-보존 가산기회로.
다수 컬럼의 이진 데이터 비트들을 합산하여 복수의 부분합 결과 및 복수의 부분올림수 결과를 발생시키되, 특정 컬럼의 이진 데이터 비트가 동일한 차수 크기를 갖고, 상이한 컬럼의 이진 데이터 비트는 차수 크기가 서로 상이하게 되어 있는 올림수 보존 가산기회로에 있어서: 복수의 1-비트 전가산기회로, - 각각의 상기 1-비트 전가산기회로는 가수 입력 터미널 A 및 B, 첫 번째 입력-올림수 입력 터미널 C_i, 첫 번째 출력-올림수 출력터미널 C_o, 및 합계 출력 터미널 S를 포함함 - ; 복수의 2-비트 전가산기회로, - 각각의 상기 2-비트 전가산기회로는 첫 번째 가수 입력 터미널 A0 및 B0, 두 번째 가수 입력 터미널 A1 및 B1, 두 번째 입력-올림수 입력 터미널 C_i, 두 번째 출력-올림수 출력 터미널 C_o, 첫 번째 합계 출력 터미널 S0, 및 두 번째 합계 출력 터미널 S1을 포함하고, 상기 1-비트 및 2-비트 전가산기회로는 복수의 상호연결된 컬럼 가산기회로로 배열되며, 각 컬럼 가산기회로는 적어도 하나의 컬럼으로부터의 이진 데이터 비트를 합산하여 부분합 결과 및 부분 올림수 결과를 산출하고, 각각의 컬럼 가산기회로는 복수의 스테이지를 구비하며, 각각의 상기 스테이지는 1-비트 및 2-비트 전가산기회로의 조합을 포함함 - ; 및 각 컬럼 가산기회로의 스테이지들을 동일한 컬럼 가산기회로내의 다른 스테이지 및 올림수-보존 가산기회로내의 다른 컬럼 가산기회로내의 스테이지와 연결하는 복수의 도체를 포함하는 것을 특징으로 하는 올림수-보존 가산기회로.
이진 데이터들을 컬럼들로 - 각 컬럼은 동일한 크기의 차수를 갖는 모든 이진 데이터 비트들을 포함함 - 편성하는 단계; 각 컬럼의 이진 데이터 비트들을 적어도 복수의 컬럼 가산기 회로중의 하나 - 각 컬럼 가산기 회로는 복수의 상호연결된 1-비트 및 2-비트 전가산기 회로를 포함하고, 각 컬럼 가산기 회로는 또한 복수의 스테이지를 포함하며, 각 스테이지는 상기 1-비트 및 2-비트 전가산기 회로의 조합을 포함함 - 에 입력하는 단계; 각각의 컬럼 가산기회로에 있는 1-비트 및 2-비트 전가산기회로들의 연속적인 스테이지에 의해 이진 데이터 비트의 수를 감소시키는 단계; 및 복수의 부분합 결과 및 복수의 부분올림수 결과를 발생시키는 단계를 포함하는 것을 특징으로 하는 복수의 이진 데이터 비트 합산 방법.
청구항 1에 있어서, 각각의 1-비트 전가산기회로는 가수 입력 터미널 A 및 B; 첫 번째 입력-올림수 입력 터미널 C_i; 첫 번째 출력-올림수 출력 터미널 C_o; 및 합계 출력 터미널 S를 포함하는 것을 특징으로 하는 올림수-보존 가산기회로.
청구항 1에 있어서, 각각의 2-비트 전가산기회로는 첫 번째 가수 입력 터미널 A0 및 B0; 두 번째 가수 입력 터미널 A1 및 B1; 두 번째 입력-올림수 입력 터미널 C_i; 두 번째 출력-올림수 출력 터미널 C_o; 첫 번째 합계 출력 터미널 SO; 및 두 번째 합계 출력 터미널 S1을 포함하는 것을 특징으로 하는 올림수-보존 가산기회로.
청구항 1에 있어서, 각각의 컬럼 가산기 회로는 적어도 하나의 컬럼으로부터의 이진 데이터 비트들의 수를 감소시키는 첫 번째 스테이지; 이진 데이터 비트의 수를 더욱 감소시키기 위한 복수의 중간 스테이지; 및 부분합 및 부분올림수 결과를 산출하는 하나의 1-비트 전가산기회로를 포함하는 최종 스테이지를 포함하는 것을 특징으로 하는 올림수-보존 가산기 회로.
청구항 6에 있어서, 각각의 컬럼 가산기회로의 제1스테이지는 더 높은 차수의 입력터미널과 더 낮은 차수의 입력터미널을 갖는 적어도 하나의 2-비트 전가산기 회로를 포함하고, 상기 더 높은 차수의 입력터미널은 첫 번째 차수의 크기를 갖는 첫 번째 이진 데이터 비트를 받아들이며, 상기 더 낮은 차수의 입력터미널은 두 번째 차수의 크기를 갖는 두 번째 데이터 비트를 받아들이고, 상기 첫 번째 차수 크기가 두 번째 차수 크기 보다 1 차수 크기만큼 큰 것을 특징으로 하는 올림수-보존 가산기회로.
청구항 1에 있어서, 상기 복수의 도체는 입력 및 출력 터미널을 접속하며, 상기 입력 및 출력 터미널은 각기 동일한 차수 크기의 이진 데이터 비트를 수신 및 송신하는 것을 특징으로 하는 올림수-보존 가산기회로.
청구항 2에 있어서, 각각의 컬럼 가산기회로의 첫 번째 스테이지는 적어도 하나의 2-비트 전가산기회로를 포함하고, 첫 번째 스테이지에 있는 각각의 2-비트 전가산기회로의 A1 및 B1은 첫 번째 컬럼으로부터 첫 번째 차수 크기를 갖는 첫 번째 이진 데이터 비트를 수신하며, 각각의 2-비트 전가산기회로의 A0, B0, 및 C_i는 두번째 컬럼으로부터 두번째 차수 크기를 갖는 두 번째 이진 데이터 비트를 수신하고, 상기 첫 번째 차수 크기가 두 번째 차수 크기 보다 1 차수 크기만큼 큰 것을 특징으로 하는 올림수-보존 가산기회로.
청구항 2에 있어서, 각각의 두 번째 C_o는 그 다음 높은 차수의 이진 데이터 비트들을 합산하여 컬럼 가산기회로의 스테이지에 있는 A1 및 B1, 그리고 두 번째 더 높은 차수의 이진 데이터 비트들을 합산하는 컬럼 가산기회로의 스테이지에 있는, A, B, A0, B0, 첫 번째 C_i및 두 번째 C_i로 구성되는 군에 속하는 입력 터미널에만 연결되고; 각각의 첫 번째 C_o및 S1은 동일한 컬럼 가산기회로에 있는 A1 및 B1, 그리고 그 다음 높은 차수의 이진 데이터 비트를 합산하는 컬럼 가산기회로의 스테이지에 있는 A, B, A0, B0, 첫 번째 C_i및 두 번째 C_i로 구성되는 군에 속하는 입력 터미널에만 연결되며; 그리고 각각의 S 및 S0는 동일한 컬럼 가산기회로에 있는 A, B, A0, B0, 첫 번째 C_i및 두 번째 C_i와, 그 다음 낮은 차수의 이진 데이터 비트를 합산하는 컬럼 가산기회로에 있는 A1 및 B1로 구성되는 군에 속하는 입력 터미널에만 연결되는 것을 특징으로 하는 올림수-보존 가산기회로.
청구항 2에 있어서, 각 컬럼에 있어서의 상기 이진 데이터 비트의 최대수가 18인 것을 특징으로 하는 올림수-보존 가산기회로.
청구항 2에 있어서, 각 컬럼에 있어서의 상기 이진 데이터 비트의 최대수가 55인 것을 특징으로 하는 올림수-보존 가산기회로.
복수 컬럼의 이진 데이터 비트들을 합산하여 복수의 부분합 결과 및 복수의 부분올림수 결과를 발생시키되, 특정 컬럼의 이진 데이터 비트가 동일한 차수 크기를 갖고, 상이한 컬럼의 이진 데이터 비트는 차수 크기가 서로 상이하게 되어 있는 올림수 보존 가산기회로에 있어서, 복수의 1-비트 전가산기회로, - 각각의 1-비트 전가산기 회로는 가수 입력터미널 A 및 B, 첫 번째 입력-올림수 입력 터미널 C_i, 첫 번째 출력-올림수 출력 터미널 C_o, 및 합계 출력 터미널 S를 포함함 - ; 복수의 2-비트 전가산기 회로, - 각각의 2-비트 전가산기 회로는 첫 번째 가수 입력 터미널 AO 및 BO, 두 번째 가수 입력 터미널 A1 및 B1, 두 번째 입력-올림수 입력 터미널 C_i, 두 번째 출력-올림수 출력 터미널 C_o, 첫 번째 합계 출력 터미널 S0 및 두 번째 합계 출력 터미널 S1을 포함하며, 상기 1-비트 및 2-비트 전가산기 회로는 복수의 상호연결된 컬럼 가산기회로로 배열되고, 각 컬럼 가산기회로는 적어도 하나의 컬럼으로부터의 이진 데이터 비트를 합산하여 부분합 결과 및 부분 올림수 결과를 산출하고, 각각의 컬럼 가산기회로는 복수의 스테이지를 구비하며, 각각의 스테이지는 1-비트 및 2-비트 전가산기회로의 조합을 포함함 - ; 각 컬럼 가산기회로의 스테이지들을 동일한 컬럼 가산기회로내의 다른 스테이지 및 올림수-보존 가산기회로내의 다른 컬럼 가산기회로내의 스테이지와 상호 연결하는 복수의 도체, - 상기 복수의 도체는 동일한 차수의 크기를 갖는 이진 데이터 비트들을 수신 및 송신하는 입력 및 출력 터미널을 연결함 - ; - 여기서, 각각의 두 번째 C_o는 그 다음 더 높은 차수의 이진 데이터 비트들을 합산하는 컬럼 가산기회로의 스테이지에 있는 A1 및 B1, 그리고 두 번째 더 높은 차수의 이진 데이터 비트들을 합산하는 컬럼 가산기회로의 스테이지에 있는 A, B, A0, B0, 첫 번째 C_i및 두 번째 C_i로 구성되는 군에 속하는 입력 터미널에만 연결됨; 각각의 첫 번째 C_o및 S1은 동일한 컬럼 가산기회로에 있는 A1 및 B1, 그리고 그 다음 더 높은 차수의 이진 데이터 비트를 합산하는 컬럼 가산기회로의 스테이지에 있는 A, B, A0, B0, 첫 번째 C_i및 두 번째 C_i로 구성되는 군에 속하는 입력 터미널에만 연결됨; 및 각각의 S 및 SO는 동일한 컬럼 가산기회로에 있는 A, B, A0, B0, 첫 번째 C_i및 두 번째 C_i와 그 다음 더 낮은 차수의 이진 데이터 비트를 합산하는 컬럼가산기 회로에 있는 A1 및 B1로 구성되는 군에 속하는 입력 터미널에만 연결됨 - 을 포함하는 것을 특징으로 하는 올림수-보존 가산기회로.
청구항 13에 있어서, 각 컬럼에 있어서의 상기 이진 데이터 비트의 최대수가 18인 것을 특징으로 하는 올림수-보존 가산기회로.
청구항 13에 있어서, 각 컬럼에 있어서의 상기 이진 데이터 비트의 최대수가 55인 것을 특징으로 하는 올림수-보존 가산기회로.