이진수 승수

Binary multiplier
시리즈의 일부
산술 논리 회로
빠른 네비게이션
이론.
구성 요소들
분류
「 」를 참조해 주세요.

이진 곱셈기는 컴퓨터와 같은 디지털 전자제품에서 두 개의 이진수를 곱하기 위해 사용되는 전자 회로입니다.

디지털 승수를 구현하기 위해 다양한 컴퓨터 연산 기술을 사용할 수 있습니다.대부분의 기술은 부분적 집합의 계산을 수반하며, 이 부분적 집합은 이진수 가산기를 사용하여 합산됩니다.이 과정은 2진법(이진법)의 숫자 체계를 사용한다는 점을 제외하고는 긴 곱셈과 유사합니다.

역사

1947년에서 1949년 사이에 Arthur Alex Robinson은 English Electric Ltd.에서 학생 견습생으로 일했고 그 후 개발 엔지니어로 일했다.이 기간 동안 그는 맨체스터 대학에서 박사 학위를 취득하기 위해 공부했고, 초기 Mark 1 컴퓨터의 하드웨어 멀티플라이어 설계에 종사했습니다.[3] 그러나 1970년대 후반까지 대부분의 미니컴퓨터는 곱셈 명령어를 가지고 있지 않았기 때문에 프로그래머들은 종종 루프 와인딩을 사용하여 작성되는 부분적인 결과를 반복하고 축적하는 "멀티플라이 루틴"[1][2]을 사용했다.메인프레임 컴퓨터에는 다중 명령이 있었지만 "다중 루틴"과 같은 종류의 이동 및 추가 작업을 수행했습니다.

초기 마이크로프로세서에는 다중 명령도 없었다.16비트 [3]세대에서는 멀티 명령어가 보편화되었지만, 적어도 2개의 8비트 프로세서가 멀티 명령어를 가지고 있습니다:[4][5] 1978년에 도입된 Motorola 6809와 1980년에 개발된 Intel MCS-51 패밀리, 그리고 나중에 ATMega, ATTiny 및 ATXMe 마이크로 컨트롤러에 존재하는 현대의 AVR 8비트 마이크로프로세서가 그것입니다.

대규모 집적화로 칩당 트랜지스터가 늘어나면서 한 번에 한 개씩 제품을 처리하는 데 한 개의 가산기를 재사용하지 않고 한 개의 칩에 충분한 양의 가산기를 넣어 모든 부분 제품을 한꺼번에 합칠 수 있게 됐다.

일부 일반적인 디지털 신호 처리 알고리즘은 대부분의 시간을 곱셈에 소비하기 때문에 디지털 신호 프로세서 설계자는 곱셈을 가능한 한 빠르게 하기 위해 상당한 칩 영역을 희생합니다.단일 사이클 곱셈 누적 유닛은 초기 DSP의 칩 영역을 대부분 사용합니다.

이진수 긴 곱셈

학교에서 10진수를 곱하는 방법은 부분곱을 계산하여 왼쪽으로 이동한 후 합산하는 것이다.가장 어려운 부분은 부분적 곱입니다. 긴 숫자에 한 자리(0~9)를 곱하는 것입니다.

123 x 456 ===== 738 (이것은 123 x 6) 615 (이것은 123 x 5, 왼쪽으로 한 위치 이동) + 492 (이것은 123 x 4, 왼쪽으로 두 위치 이동) ===== 56088

이진수 컴퓨터는 십진수와 정확히 같은 곱셈을 하지만 이진수를 사용합니다.바이너리 인코딩에서는 각 긴 숫자는 1자리(0 또는 1)로 곱됩니다.이것은, 0 또는 1의 곱이 단지 0이거나 같은 숫자이기 때문에, 10진수보다 훨씬 간단합니다.따라서 두 이진수의 곱은 부분곱(0 또는 첫 번째 숫자)을 계산하고 왼쪽으로 이동한 다음 이들을 합산하는 것으로 귀결됩니다(물론 이진수 덧셈). 

1011(이것은 소수점 11의 이진수) x 1110(이것은 소수점 14의 이진수) ====== 0000(이것은 1011 x 1, 왼쪽으로 한 위치 이동) 1011(이것은 1011 x 1, 왼쪽으로 두 위치 이동) + 1011(이것은 1011 x 1, 이것은 왼쪽으로 세 위치 이동) ========= 10011010(10진수 154의 경우 이진수)

이것은 10진법보다 훨씬 간단하다. 왜냐하면 곱셈표는 기억하기 어렵기 때문이다.그냥 시프트와 덧셈일 뿐이다.

이 방법은 수학적으로 정확하며 작은 CPU가 전용 회로 대신 시프트 및 산술 논리 유닛의 기능을 사용하여 곱셈을 수행할 수 있다는 장점이 있습니다.그러나 이 방법은 많은 중간 추가가 수반되기 때문에 느립니다.이러한 추가에는 시간이 걸립니다.더 적은 수의 추가를 수행하기 위해 더 빠른 승수를 설계할 수 있습니다. 최신 프로세서는 64비트 숫자 2개와 6개의 추가(64가 아닌)를 곱할 수 있으며 [citation needed]여러 단계를 동시에 수행할 수 있습니다.

두 번째 문제는 기본 학교 방식이 별도의 규칙(+++++++++++++++++++++++++++++++++++++++++++++++++++++++최신 컴퓨터는 숫자 자체에 숫자 기호를 포함하며, 보통 두 개의 보형 표현에 포함됩니다.그러면 곱셈 과정이 2의 보수를 처리하도록 조정되고, 그 과정이 조금 더 복잡해집니다.마찬가지로, 하나의 보완, 부호 및 크기, IEEE-754 또는 다른 이진 표현을 사용하는 프로세서는 곱셈 프로세스에 대한 특정 조정이 필요합니다.

부호 없는 정수

예를 들어 부호 없는 8비트 정수 a[7:0]와 b[7:0]를 곱한다고 가정합니다.8개의 1비트 곱셈을 수행하여 8개의 부분 제품을 만들 수 있습니다(승수 a의 각 비트당 1개).

  p7[7:0])a[7]b[7:0])×{8{a[7]}} 및 b[7:0]

여기서 {8{a[0]}}은 a[0](a의 0번째 비트)를 8회 반복하는 것을 의미합니다(Verilog 표기).

제품을 입수하기 위해서는 아래 그림과 같이 8개의 부분 제품을 모두 합산해야 합니다.

p0[7] p0[6] p0[4] p0[3] p0[2] p0[2] p0[0] + p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0 + p2[7] p2] p2[5] p2]p3[0] 0 0 + p4 [ 7 ]p4 [ 6 ]p4 [ 4 ]p4 [ 3 ]p4 [ 2 ]p4 [ 1 ]p4 [ 0 ] 0 0 + p5 [ 6 ]p5 [ 4 ]p5 [ 3 ]p5 [ 0 ]p5 [ 0 ]] 0 0 0 0 0 ----------------------------------------------------------------------------------------------------------------------------------------------------- P[15] P[14] P[13] P[12] P[11] P[10] P[8]

즉, P[15:0]는 p0, p1 < < 1, p2 < < 2 등을 가산하여 최종 서명되지 않은16비트 제품을 만듭니다.

부호 있는 정수

b가 부호 없는 정수 대신 부호 있는 정수일 경우 부분 곱은 합계를 하기 전에 곱의 너비까지 부호 확장을 해야 합니다.a가 부호 있는 정수일 경우 부분곱 p7은 덧셈이 아니라 최종합에서 빼야 합니다.

위의 배열 승수는 여러 개의 곱셈 항을 반전시키고 첫 번째 부분 곱셈 항 왼쪽에 1을 삽입함으로써 두 개의 보완 표기 부호 숫자를 지원하도록 수정할 수 있습니다.

1~p0[7] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0] ~p1[7] +p1[6] +p1[5] +p1[4] +p1[3] +p1[3] +p1[2] +p1[2] +p1[2]~p3[7] +p3[6] +p3[4] +p3[3] +p3[2] +p3[1] +p3[0] 0 0 ~p4[7] +p4[6] +p4[5] +p4[4] +p4[3] +p4] +p4 [1] +p4]p6[2] +p6[1] +p6[0] 0 0 0 0 0 0 1 +p7[7] ~p7[6] ~p7[5] ~p7[4] ~p7[3] ~p7[2] ~p7[1] ~p7[0] 0 0 0 0 0 ----------------------------------------------------------------------------------------------------------------------------------------------5] P[4] P[3] P[2] P[1] P[0]

여기서 ~p는 p의 보(반대값)를 나타냅니다.

위의 비트 배열에는 표시되지 않고 명확하지 않은 많은 단순화가 있습니다.1개의 보완 비트 뒤에 비보완 비트가 이어지는 시퀀스는 부호 확장을 피하기 위해 2개의 보완 트릭을 구현하고 있습니다.p7(비보완 비트 뒤에 모든 보완 비트)의 시퀀스는 이 용어를 빼기 때문에 처음부터 모두 부정되었습니다(그리고 최하위 위치에 1이 추가됨).두 가지 시퀀스 유형 모두 마지막 비트가 플립되고 MSB 바로 아래에 암시적 -1을 추가해야 합니다.비트 위치 0(LSB)의 p7에 대한 두 개의 보완 부정의 +1과 비트 열 7~14(각 MSB가 위치한 위치)의 모든 -1을 합하면 "마술적으로" 왼쪽으로 떠 있는 단일 1로 단순화할 수 있습니다.MSB를 뒤집으면 기호 확장자가 저장되는 이유에 대한 설명과 증거는 컴퓨터 [6]산술서를 참조하십시오.

부동 소수점 수

이진 부동 숫자에는 부호 비트, 유효 비트(significant) 및 지수 비트가 포함됩니다(간단히 하기 위해 기본 및 조합 필드는 고려하지 않습니다).각 오퍼랜드의 부호 비트는 정답의 부호를 얻기 위해 XORd입니다.그런 다음 두 개의 지수를 더하여 결과의 지수를 구합니다.마지막으로 각 피연산자의 유의와 값을 곱하면 결과의 유의와 값이 반환됩니다.단, 2진수 곱셈의 결과가 특정 정밀도(예를 들어 32, 64, 128)의 합계 비트수보다 클 경우에는 반올림이 필요하며, 지수를 적절히 변경한다.

하드웨어 구현

곱셈 프로세스는 3단계로 [7][8]나눌 수 있습니다.

  • 부분적 생성
  • 부분적 환원
  • 컴퓨팅 최종 제품

이전의 승수 아키텍처에서는 각 부분적(종종 사이클당 하나의 부분적)을 합산하기 위해 시프터와 축전지(accumulator)를 사용하여 다이 영역과 속도를 교환했습니다.현대의 승수 아키텍처는 (수정된) Baugh-Wooly 알고리즘,[9][10][11][12] Wallace 트리 또는 Dadda 승수를 사용하여 단일 사이클에서 부분 곱을 합산합니다.Wallace 트리 구현의 성능은 두 개의 승수 중 하나를 수정함으로써 개선될 수 있으며, 이를 통해 합산해야 하는 부분적 곱의 수를 줄일 수 있습니다.

속도를 위해 시프트 앤 애드 승수는 고속 가산기(리플 [13]캐리보다 빠른 것)가 필요합니다.

"단일 사이클" 승수(또는 "고속 승수")는 순수한 조합 논리입니다.

고속 승수에서는 일반적으로 부분적 감소 프로세스가 [7]승수의 지연, 전력 및 영역에 가장 많이 기여합니다.속도의 경우, 일반적으로 "부분적 제품 감소" 단계는 압축기로 구성된 캐리어-세이브 가산기로 구현되며, "최종 제품 계산" 단계는 고속 가산기(리플 캐리보다 빠른 것)로 구현됩니다.

로 압축기 정적 CMOS에서 구현된("3대 2압축기") 많은 빠른 multipliers. 같은 영역에서 더 나은 공연이나 작은 면적에서 같은 성능을 극대화하려면, 곱셈기 디자인,[8][7]더 빠른 논리에 압축기를 구현할 경우 압축기 같은 고차 압축기 등 전달 게이트 논리, 파를 사용해도 좋다 완전한 가산기를 사용한다.stran시스터 로직, 도미노 로직),[13] 다른 패턴으로 컴프레서를 연결하거나 일부 조합으로 연결합니다.

회선의 예

IEEE 규격 91/91a-1991 US 기호를 사용한2비트 바이너리 승수

「 」를 참조해 주세요.

레퍼런스

  1. ^ 엘리자베스 D의 '포스의 진화'오히려 등.[1] [2]
  2. ^ "하드웨어 멀티플라이어와 범용 마이크로프로세서 인터페이스"
  3. ^ M. Rafiquzzaman (2005). Fundamentals of Digital Logic and Microcomputer Design. John Wiley & Sons. p. 251. ISBN 978-0-47173349-2.
  4. ^ Krishna Kant (2007). Microprocessors and Microcontrollers: Architecture, Programming and System Design 8085, 8086, 8051, 8096. PHI Learning Pvt. Ltd. p. 57. ISBN 9788120331914.
  5. ^ Krishna Kant (2010). Microprocessor-Based Agri Instrumentation. PHI Learning Pvt. Ltd. p. 139. ISBN 9788120340862.
  6. ^ Parhami, Behrooz, 컴퓨터 연산:알고리즘과 하드웨어 설계, 옥스포드 대학 출판부, 뉴욕 (ISBN 0-19-512583-5, 490 + xx 페이지)
  7. ^ a b c 마흐누시 루홀라미니, 오미드 카베히, 아미르-파샤 미르바하, 소마예 자파랄리 자스비, 케이반 나비."7:2 컴프레서의 새로운 설계"
  8. ^ a b Yuhao Leong, HaiHiung Lo, Michael Drieberg, Abu Bakar Sayuti, Patrick Sebastian."FPGA의 8-3 압축기 성능 비교 검토"
  9. ^ Baugh, Charles Richmond; Wooley, Bruce A. (December 1973). "A Two's Complement Parallel Array Multiplication Algorithm". IEEE Transactions on Computers. C-22 (12): 1045–1047. doi:10.1109/T-C.1973.223648. S2CID 7473784.
  10. ^ Hatamian, Mehdi; Cash, Glenn (1986). "A 70-MHz 8-bit×8-bit parallel pipelined multiplier in 2.5-μm CMOS". IEEE Journal of Solid-State Circuits. 21 (4): 505–513. doi:10.1109/jssc.1986.1052564.
  11. ^ Gebali, Fayez (2003). "Baugh–Wooley Multiplier" (PDF). University of Victoria, CENG 465 Lab 2. Archived (PDF) from the original on 2018-04-14. Retrieved 2018-04-14.
  12. ^ Reynders, Nele; Dehaene, Wim (2015). Ultra-Low-Voltage Design of Energy-Efficient Digital Circuits. Analog Circuits and Signal Processing Series. Analog Circuits And Signal Processing (ACSP) (1 ed.). Cham, Switzerland: Springer International Publishing AG Switzerland. doi:10.1007/978-3-319-16136-5. ISBN 978-3-319-16135-8. ISSN 1872-082X. LCCN 2015935431.
  13. ^ a b 펑창입니다."재구성 가능한 디지털 멀티플라이어와 4:2 압축기 셀 설계"2008.

외부 링크