월리스 트리

4 레이어 월리스가 8x8 부분 제품 매트릭스를 줄여서 14개의 하프 애더(점 2개)와 38개의 풀 애더(점 3개)를 사용한다.각 열의 점들은 같은 무게의 비트들이다.

월리스 승수는 두 정수를 곱하는 디지털 회로인 이진 승수를 하드웨어로 구현하는 것이다.풀 애더(Wallace tree 또는 Wallace 축소)와 하프 애더(Wallace tree 또는 Wallace 축소)를 선택하여 두 숫자가 남을 때까지 단계별로 부분 제품을 합산한다.월리스 승수는 각 층마다 최대한 줄인 반면, 다다 승수는 상위 층으로 줄인 것을 미루어 필요한 관문 수를 최소화하려고 한다.^[1]

월리스 승수는 1964년 호주의 컴퓨터 과학자 크리스 월리스에 의해 고안되었다.^[2]

월리스 트리는 세 가지 단계가 있다.

각 변수의 각 비트에 다른 것을 곱하라.
전체 애더더와 절반 애더더의 레이어별로 부분 제품 수를 2개로 줄인다.
와이어를 두 숫자로 묶은 후 기존 애드더로 추가하십시오.^[3]

일반 애더더로 순진하게 부분 제품을 추가하는 것에 비해 월리스 트리의 이점은 속도가 더 빠르다는 것이다. $O(\log n)$ ) ${\displaystyle$ O $(\log$ n $)}$ 개의 $O(\log n)$ 축소 레이어를 가지고 있지만, 각 레이어는 $O(1)$ ( $O(1)$ ) ${\displaystyle O(1)$ 전파 $O(1)$ 지연만 가지고 있다.부분 제품의 순진한 추가는 O $O(\log ^{2}n)$ $O(\log ^{2}n)$ ⁡ $O(\log ^{2}n)$ ) $O(\log ^{2}n)$ 시간이 필요할 $O(\log ^{2}n)$ 것이다.부분 제품을 만드는 것은 $O(1)$ ( 1 ) $O(1)$ 이고 $O(1)$ 최종 $O(\log n)$ 는 O $O(\log n)$ ( $O(\log n)$ n $O(\log n)$ ) ${\displaystyle O(\log$ n $O(\log n)$ 이므로, 총 곱셈은 O $O(\log n)$ ( $O(\log n)$ $O(\log n)$ $O(\log n)$ ) ${\displaystysty$ O $(\log n)}$ 이며 $O(\log n)$ 덧셈보다 그리 느리지 않다.복잡한 이론적 관점에서 월리스 트리 알고리즘은 NC 등급에¹ 곱셈을 넣는다.월리스 트리의 단점은 부분적인 상품의 순진한 추가에 비해 훨씬 높은 게이트 카운트라는 점이다.

이러한 계산은 게이트 지연만을 고려하고 와이어 지연은 다루지 않으며, 이는 또한 매우 중대한 것일 수 있다.

월리스 트리는 3/2 또는 4/2의 추가자 나무로도 표현될 수 있다.

그것은 때때로 부스 인코딩과 결합된다.^[4]^[5]

상세설명

월리스 나무는 긴 곱셈의 변종이다.첫 번째 단계는 한 요인의 각 자릿수(각 비트)에 다른 요인의 각 자릿수를 곱하는 것이다.이 부분적인 제품들은 각각 그 요소들의 제품과 동일한 무게를 가지고 있다.최종 산출물은 이 모든 부분 생산물의 가중 합계로 계산된다.

위에서 말한 바와 같이 첫 번째 단계는 한 숫자의 각 비트에 다른 숫자의 각 비트를 곱하는 것으로 단순한 $n^{2}$ 게이트로서 n $n^{2}$ ${\$ n $^{2}}$ 비트를 $n^{2}$ 생성하며, $b_{n}$ ${\$ 에 $a_{m}$ $a_{m}$ m $a_{m}$ {\ $displaystystyle a_{$ m} 비트의 부분 곱은 $2^{(m+n)}$ 2 $2^{(m+n)}$ ( $2^{(m+n)}$ + n $){$ ){\ $displaystyledisplaystyled$ )이다. $2^{(m+n)}}}$

두 번째 단계에서는 결과 비트가 두 개 숫자로 감소한다. 이는 다음과 같이 이루어진다.동일한 중량을 가진 3개 이상의 와이어가 있는 한 다음과 같은 레이어를 추가한다.

동일한 중량의 3개의 와이어를 취하여 완전한 추가기에 입력한다.결과는 동일한 중량의 출력 와이어와 각 3개의 입력 와이어에 대해 더 높은 중량을 갖는 출력 와이어가 될 것이다.
같은 무게의 와이어가 2개 남아 있을 경우 절반의 추가기에 입력한다.
와이어가 한 개만 남아 있으면 다음 층에 연결한다.

세 번째와 마지막 단계에서, 두 개의 결과 숫자는 최종 제품을 얻으면서 추가자에게 공급된다.

예

$n=4$ = 4 ${\displaystyle n=4$ $a_{3}a_{2}a_{1}a_{0}$ a $a_{3}a_{2}a_{1}a_{0}$ $a_{3}a_{2}a_{1}a_{0}$ $a_{3}a_{2}a_{1}a_{0}$ $a_{3}a_{2}a_{1}a_{0}$ 0 ${\$ 에 $a_{3}a_{2}a_{1}a_{0}$ b $b_{3}b_{2}b_{1}b_{0}$ $b_{3}b_{2}b_{1}b_{0}$ 2 $b_{3}b_{2}b_{1}b_{0}$ $b_{3}b_{2}b_{1}b_{0}$ b $b_{3}b_{2}b_{1}b_{0}$ 을 곱한 값: ${\$ }b_{ $1}b_{0}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}:{$ 0 $b_{3}b_{2}b_{1}b_{0}$ :

첫째로 우리는 모든 조각에 모든 조각을 곱한다.
- 중량 1 – $a_{0}b_{0}$ $a_{0}b_{0}$ $a_{0}b_{0}$ ${\$
- 무게 2 – $a_{0}b_{1}$ $a_{0}b_{1}$ $a_{0}b_{1}$ ${\$ 1}b_{ $0},$ $a_{1}b_{0}$ $a_{1}b_{0}$ $a_{1}b_{0}$ ${\$
- 무게 4 – $a_{0}b_{2}$ $a_{0}b_{2}$ $a_{0}b_{2}$ ${\$ $a_{1}b_{1}$ $a_{1}b_{1}$ $a_{1}b_{1}$ ${\$ }2 $}},$ $a_{2}b_{0}$ $a_{2}b_{0}$ 0 ${\$
- 무게 8 – $a_{0}b_{3}$ $a_{0}b_{3}$ $a_{0}b_{3}$ ${\$ 1 $a_{1}b_{2}$ $a_{1}b_{2}$ ${\$ 1} $b_$ {2 $}},$ 2 $a_{2}b_{1}$ $a_{2}b_{1}$ ${\$ {2 $}b_{1},$ 3 $a_{3}b_{0}$ $a_{3}b_{0}$ ${\$ v_{0}}}}}}}}}}}}}}}}}}}}}}}}}}.
- 무게 16 – $a_{1}b_{3}$ $a_{1}b_{3}$ 3 ${\$ $a_{2}b_{2}$ $a_{2}b_{2}$ 2 ${\$ }}, $a_{2}b_{2}$ $a_{3}b_{1}$ $a_{3}b_{1}$ 1 ${\$ }:{1}:{1 $}}}}}}$
- $a_{2}b_{3}$ 32 – $a_{2}b_{3}$ $a_{2}b_{3}$ $a_{2}b_{3}$ ${\$ b_{2}}, $a_{2}b_{3}$ $a_{3}b_{2}$ $a_{3}b_{2}$ $a_{3}b_{2}$ ${\$ }}
- 무게 64 – $a_{3}b_{3}$ $a_{3}b_{3}$ $a_{3}b_{3}$ ${\$
감소층 1:
- 유일한 중량-1 와이어를 통과, 출력: 중량-1 와이어 1개
- 중량 2, 출력: 중량 2 와이어 1개, 중량 4 와이어 1개 추가
- 중량 4, 출력: 중량 4 와이어 1개, 중량 8 와이어 1개 추가
- 중량 8에 대한 전체 애더더를 추가하고 남은 와이어를 출력: 중량 8 와이어 2개, 중량 16 와이어 1개
- 중량 16에 대한 전체 애더더 추가, 출력: 중량 16 와이어 1개, 중량 32 와이어 1개
- 중량 32에 대해 절반의 추가 기능 추가, 출력: 중량 32 와이어 1개, 중량 64 와이어 1개
- 유일한 중량-64 와이어를 통과, 출력: 중량-64 와이어 1개
감속층 1의 출력에 있는 와이어:
- 무게 1 – 1
- 무게 2 – 1
- 무게 4 – 2
- 무게 8 – 3
- 무게 16 – 2
- 무게 32 – 2
- 무게 64 – 2
감소층 2:
- 무게 8에 대한 전체 애더더와 무게 4, 16, 32, 64에 대한 반 애더더 추가
출력:
- 무게 1 – 1
- 무게 2 – 1
- 무게 4 – 1
- 무게 8 – 2
- 무게 16 – 2
- 무게 32 – 2
- 무게 64 – 2
- 중량 128 – 1
전선을 한 쌍의 정수와 더하기 위해 더하기 위해 전선을 그룹화한다.

참고 항목

다다나무

참조

^ Townsend, Whitney J.; Swartzlander, Earl E.; Abraham, Jacob A. (2003). "A comparison of Dadda and Wallace multiplier delays". Advanced Signal Processing Algorithms, Architectures, and Implementations XIII. 5205: 552–560. doi:10.1117/12.507012. ISSN 0277-786X.
^ Wallace, Christopher Stewart (February 1964). "A suggestion for a fast multiplier". IEEE Transactions on Electronic Computers. EC-13 (1): 14–17.
^ Bohsali, Mounir; Doan, Michael (2010). "Rectangular Styled Wallace Tree Multipliers" (PDF). Archived from the original (PDF) on 2010-02-15.
^ "Introduction". 8x8 Booth Encoded Wallace-tree multiplier. Tufts university. 2007. Archived from the original on 2010-06-17.
^ Weems Jr., Charles C. (2001) [1995]. "CmpSci 535 Discussion 7: Number Representations". Amherst: University of Massachusetts. Archived from the original on 2011-02-06.

추가 읽기

Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.

외부 링크

Wallace Tree Multiers의 일반 VHDL 구현.

[1] Townsend, Whitney J.; Swartzlander, Earl E.; Abraham, Jacob A. (2003). "A comparison of Dadda and Wallace multiplier delays". Advanced Signal Processing Algorithms, Architectures, and Implementations XIII. 5205: 552–560. doi:10.1117/12.507012. ISSN 0277-786X.

[Wallace_1964-2] Wallace, Christopher Stewart (February 1964). "A suggestion for a fast multiplier". IEEE Transactions on Electronic Computers. EC-13 (1): 14–17.

[Bohsali_2010-3] Bohsali, Mounir; Doan, Michael (2010). "Rectangular Styled Wallace Tree Multipliers" (PDF). Archived from the original (PDF) on 2010-02-15.

[tufts_2007-4] "Introduction". 8x8 Booth Encoded Wallace-tree multiplier. Tufts university. 2007. Archived from the original on 2010-06-17.

[Weems_2001-5] Weems Jr., Charles C. (2001) [1995]. "CmpSci 535 Discussion 7: Number Representations". Amherst: University of Massachusetts. Archived from the original on 2011-02-06.

[1]

[2]

[3]

[4]

[5]

Search

월리스 트리

네임스페이스

더

목차

상세설명

예

참고 항목

참조

추가 읽기

외부 링크