KR0141870B1 - High speed pipeline multiplication circuit - Google Patents
High speed pipeline multiplication circuitInfo
- Publication number
- KR0141870B1 KR0141870B1 KR1019930015194A KR930015194A KR0141870B1 KR 0141870 B1 KR0141870 B1 KR 0141870B1 KR 1019930015194 A KR1019930015194 A KR 1019930015194A KR 930015194 A KR930015194 A KR 930015194A KR 0141870 B1 KR0141870 B1 KR 0141870B1
- Authority
- KR
- South Korea
- Prior art keywords
- quasi
- carry
- bits
- multiplication circuit
- high speed
- Prior art date
Links
- 230000036961 partial effect Effects 0.000 claims abstract description 24
- 230000000295 complement effect Effects 0.000 abstract description 4
- 238000010586 diagram Methods 0.000 description 6
- 238000004088 simulation Methods 0.000 description 5
- 238000000034 method Methods 0.000 description 4
Landscapes
- Complex Calculations (AREA)
Abstract
본 발명은 언사인드와 2의 보수 형태의 고속 승산을 수행하는 고속 파이프라인 승산회로에 관한 것으로, 승수 Y를 2비트 단위씩 레코딩한 후 피승수 X와 결합하여 부분적을 생성하는 부스 레코딩부와, 이 부스 레코딩부에서 출력되는 부분적과 준캐리 부분적 및 준가산 부분적을 가산 및 2비트씩 쉬프트하여 다음단에서 사용될 준캐리 2비트를 생성하는 가산 및 쉬프트부와, 가산 및 쉬프트부의 출력을 첫 번째 클럭에서 래치하는 파이프라인 레지스터와, 이 파이프 라인 레지스터의 출력을 가산하는 캐리 룩어헤드 가산기로 구성됨으로써, 구조가 규칙적이고 간단하면서 속도가 빠른 승산을 수행할 수 있는 것이다.The present invention relates to a high-speed pipeline multiplication circuit that performs fast multiplication of unsigned and two's complement form. The present invention relates to a booth recording unit which generates a partial by combining a multiplier X after recording a multiplier Y by two bits. An add and shift unit for generating a sub carry 2 bit to be used in the next stage by adding and shifting the bit and the quasi-carry part and the quasi-added part output from the booth recording part by 2 bits, and the output of the add and shift part from the first clock. The structure consists of a pipeline register for latching and a carry lookahead adder for adding the output of the pipeline register, so that the structure can be multiplied regularly, simply and at a high speed.
Description
제1도는 종래의 승산회로를 간략하게 나타낸 블럭구성도1 is a block diagram schematically showing a conventional multiplication circuit.
제2도는 상기 제1동의 월리스 트리부의 상세 블럭구성도2 is a detailed block diagram of the wallless tree portion of the first block.
제3도는 본 발명에 따른 고속 파이프라인 승산회로의 블럭구성도3 is a block diagram of a high speed pipeline multiplication circuit according to the present invention.
제4도는 본 발명에 따른 고속 파이프라인 승산회로의 각 부의 시뮬레이션 결과를 보여주는 도면4 is a diagram showing a simulation result of each part of the high speed pipeline multiplication circuit according to the present invention.
*도면의 주요부분에 대한 부호의 설명* Explanation of symbols for main parts of the drawings
31:부스 레코딩부32:가산 및 쉬프트부31: Booth recording section 32: Addition and shift section
33:캐리 룩어헤드 가산부331:파이프라인 레지스터33: carry lookahead adder 331: pipeline register
332:캐리 룩어헤드 가산기332: Carry look-ahead adder
본 발명은 고속 파이프라인 승산회로에 관한 것으로서, 더욱 상세하게는 순수한 조합 논리회로와 래치로만 구성시켜 회로가 규칙적이고 간단하면서 언사인드(Unsigned)와 2의 보수 형태의 승산이 고속으로 수행되도록 하는 고속 파이프라인 승산회로에 관한 것이다.The present invention relates to a high speed pipeline multiplication circuit. More particularly, the present invention relates to a high speed pipeline multiplication circuit. More particularly, the present invention relates to a high speed pipeline multiplication circuit. It relates to a pipeline multiplication circuit.
제1도는 종래의 승산회로에 대한 블럭구성도로서, 부스(Booth)엔코더(11), 부분적 생성부(12), 윌리스 트리(Wellace tree)부(13), 캐리 룩어헤드(carry Lookahead)가산부(14)로 구성된다.1 is a block diagram of a conventional multiplication circuit, which includes a booth encoder 11, a partial generation unit 12, a Willis tree unit 13, and a carry lookahead adding unit. It consists of 14.
이와같이 구성된 종래의 승산회로는 부스 엔코더(11)에서 승수(Y) n 비트의 레코딩 값이 생성되어 부분적 생성부(12)로 입력되면, 부분적 생성부(12)에서는 부스 엔코더(11)의 레코딩 값과 외부에서 입력되는 n 비트의 피승수(X)를 결합하여 부분적을 생성한다. 그런다음, 이 부분적 생성부(12)에서 생성된 부분적들은 제2도에 도시된 바와 같이 전가산기(Full Adder)의 배열로 이루어진 윌리스 트리부(13)에 입력되어 두 개의 행으로 감축되고, 다시 두 개의 행은 캐리 룩어헤드 가산부(14)에 입력되므로서 최종의 승산 결과를 얻는다.In the conventional multiplication circuit configured as described above, when the recording value of the multiplier (Y) n bits is generated by the bus encoder 11 and input to the partial generator 12, the partial generator 12 records the recording value of the bus encoder 11 in the partial generator 12. And a n-bit multiplicand (X) input from outside to generate a partial. Then, the partials generated by this partial generating unit 12 are input to the Willis tree unit 13 formed of an array of full adders as shown in FIG. 2, and reduced into two rows, and again. Two rows are input to the carry lookahead adder 14 to obtain a final multiplication result.
그러나, 상술한 바와같은 종래의 승산회로는 부분적을 생성하는 부스 엔코더와 부분적 생성부 및 병렬 가산을 행하는 윌리스 트리부의 구조가 복잡할 뿐만 아니라, 게이트에 의한 시간 지연이 발생되는 문제점이 있으며, 또한, 이로 인해 속도에 제한이 따르게 되는 문제점을 갖는다.However, the conventional multiplication circuit as described above has a problem in that the structure of the booth encoder that generates the part and the willis tree part that performs the partial generation part and the parallel addition is not only complicated, but also causes a time delay caused by the gate. This causes a problem that speed is followed.
본 발명은 이러한 종래기술의 문제점을 해결하기 위해 안출한 것으로서, 언사인드와 2의 보수 형태의 고속 승산을 순수한 조합 논리회로와 래치로만 구성시켜 수행함으로써 회로가 규칙적이고 간단하면서 속도가 빠른 고속 파이프라인 승산회로를 제공하는데 그 목적이 있다.SUMMARY OF THE INVENTION The present invention has been made to solve the problems of the prior art, and the circuit is a regular, simple and fast high-speed pipeline by performing the unsigned and two-complement high-speed multiplication by using only a pure combination logic circuit and a latch. The purpose is to provide a multiplication circuit.
상기 목적을 달성하기 위하여 본 발명은 승수 Y를 2비트 단위씩 레코딩한 후 피승수 X와 결합하여 부분적을 생성하는 부스 레코딩 수단과, 이 부스 레코딩 수단에서 출력되는 부분적과 준캐리 부분적 및 준가산 부분적을 가산 및 쉬프트하여 다음단에서 사용될 준캐리 부분적 및 준가산 부분적과 쉬프트된 가산 2비트 및 쉬프트된 캐리 2비트를 생성하는 가산 및 쉬프트 수단과, 이 가산 및 쉬프트 수단의 출력을 첫 번째 클럭에서 래치하는 파이프라인 레지스터와, 이 파이프라인 레지스터의 출력을 가산하는 캐리 룩어헤드 가산기로 이루어진 고속 파이프라인 승산회로를 제공한다.In order to achieve the above object, the present invention provides a booth recording means for generating a partial by combining a multiplier X after recording the multiplier Y by 2 bits, and the partial and quasi-carry part and quasi-added part output from the booth recording means. Adding and shifting means for adding and shifting to generate a quasi-carrier partial and quasi-additional part and shifted addition 2 bits and shifted carry 2 bits, and latching the output of the addition and shift means at the first clock. A high speed pipeline multiplication circuit comprising a pipeline register and a carry lookahead adder for adding the output of the pipeline register is provided.
본 발명의 기타 목적과 여러 가지 장점은 이 기술분야에 숙련된 사람들에 의해 첨부된 도면을 참조하여 하기에 기술되는 본 발명의 바람직한 실시예로부터 더욱 명백하게 될 것이다.Other objects and various advantages of the present invention will become more apparent from the preferred embodiments of the present invention described below with reference to the accompanying drawings by those skilled in the art.
이하, 본 발명에 따른 고속 파이프라인 승산회로의 바람직한 실시예에 대하여 첨부도면을 참조하여 상세히 설명한다.Hereinafter, a preferred embodiment of the high speed pipeline multiplication circuit according to the present invention will be described in detail with reference to the accompanying drawings.
제3도는 본 발명에 따른 고속 파이프라인 승산회로의 블록구성도를 나타낸다. 동도면에 도시된 바와같이, 본 발명의 고속 파이프라인 승산회로는 승산의 초기 단계에서 수정형 부스 알고리즘을 사용하여 n/2 개의 부분적을 생성하는 부스 레코딩부(31)와, 이 부스 레코딩부(31)에서 입력되는 부분적과 준캐리 부분적 및 준가산 부분적을 가산하여 쉬프트된 가산 2비트 및 쉬프트된 캐리 2비트와 다음단에 입력되는 쉬프트된 준가산 부분적 및 준캐리 부분적을 생성하는 가산 및 쉬프트부(32)와, 이 가산 및 쉬프트부(32)의 출력에 대해 병렬 가산하는 캐리 룩어헤드 가산부(33)로 구성된다.3 shows a block diagram of a high speed pipeline multiplication circuit according to the present invention. As shown in the figure, the high speed pipeline multiplication circuit of the present invention comprises a booth recording section 31 which generates n / 2 portions using a modified booth algorithm in the initial stage of multiplication, and the booth recording section ( 31. An addition and shift unit for generating a shifted addition 2-bit and a shifted carry 2-bit and a shifted quasi-additional part and a quasi-carry part input by adding a partial input and a quasi-carrier partial and a quasi-addition partial input in 31). And a carry look-ahead adding portion 33 that adds in parallel to the output of the adding and shifting portions 32.
여기서, 상술한 캐리 룩어헤드 가산부(33)는, 상기 가산 및 쉬프트부(3)의 출력을 래치하여 파이프라인 기능을 하는 파이프라인 래치스터(331)와, 이 파이프라인 레지스터(331)에 래치된 값을 가산하는 룩어헤드 가산기(332)로 구성된다.Here, the carry look-ahead adding section 33 latches the output of the adding and shifting section 3 to perform a pipeline function and a latch to the pipeline register 331. It consists of a look-ahead adder 332 to add the added value.
이와같이 구성된 본 발명은, 부스 레코딩부(31)에서 승수 Y가 n 비트일 경우 n/2 스텝으로 줄어 n/2 개의 부분적을 생성한다.According to the present invention configured as described above, when the multiplier Y is n bits in the booth recording section 31, the present invention is reduced to n / 2 steps to generate n / 2 parts.
즉, 승산의 초기 단계에서 수정형 부스 알고리즘을 사용하여 n/2 개의 부분적을 생성한다. 여기서, n 은 승수의 비트수이다. 다시 말해, 수정형 부스 알고리즘은 승수를 두비트 단위씩 레코딩함으로써 생성되는 부분적 행위 수를 반으로 줄이게 된다.That is, in the initial stages of multiplication, the modified booth algorithm is used to generate n / 2 partials. Where n is the number of bits of the multiplier. In other words, the modified booth algorithm cuts the number of partial actions generated by recording the multiplier by two bits in half.
이때, 하기의 〈표 1〉에서와 같이 승수 Y의 레코딩을 정의하는데 Zi가 '2'와 '-2'일 경우 피승수 X에서 최하위 비트(LSB)에 '0'을 붙여 '2'를 곱하는 의미를 나타낸다. 그리고 '-1'과 '-2'는 2의 보수를 취한다. 그리고, 부호 확장은 피연산자의 최상위 비트(MSB)값으로 하고 이때 Zi가 '1'일 경우 '0' 대신에 '1'로 확장하여 처리한다. 그 결과, XZn/2, XZn/2-1, . . . XZ2, XZ1, XZ0의 부분적이 생성된다.In this case, as shown in Table 1, the recording of the multiplier Y is defined, and when Zi is '2' and '-2', it means to multiply '2' by adding '0' to the least significant bit (LSB) in the multiplicand X. Indicates. And '-1' and '-2' take two's complement. The code extension is the most significant bit (MSB) of the operand. When Zi is '1', the code extension is extended to '1' instead of '0'. As a result, XZ n / 2 , XZ n / 2-1 ,. . . Partials of XZ 2 , XZ 1 and XZ 0 are generated.
*표1생략Table 1 Omitted
그런 다음, 가산 및 쉬프트부(32)의 제1가산 및 쉬프트기(321)에서 첫 번째 부분적과 접지된 준가산 부분적과 준캐리 부분적을 가산하여 이로부터 쉬프트된 가산 2비트와 쉬프트된 캐리 2비트, 그리고 다음단에 입력될 쉬프트된 준가산 부분적과 준캐리 부분적을 생성한다.Then, in the first addition and shifter 321 of the addition and shift unit 32, the first partial and the grounded semi-additional part and the quasi-carrying part are added to shift the added 2 bits and the shifted carry 2 bits. Then, we generate the shifted quasi-additional part and the quasi-carrier part to be input in the next step.
다음에, 가산 및 쉬프트부(32)에 제2가산 및 쉬프트기(322)에서 상기 부스 레코딩부(31)의 두 번째 부분적과 상기 제1가산 및 쉬프트기(321)에서 출력되는 준가산 부분적과 준캐리 부분적을 가산하여 다음의 쉬프트된 가산 2비트 및 쉬프트된 캐리 2비트와 쉬프트된 준가산 부분적 및 준캐리 부분적을 생성한다.Next, the second addition of the second addition and shifter 322 to the addition and shift unit 32 and the semi-additional partial output from the first addition and shifter 321 and the second addition of the booth recording unit 31; The quasi-carry portion is added to produce the next shifted addition 2 bits and the shifted carry 2 bits and the shifted quasi-add portion and quasi-carry portion.
이러한 과정을 가산 및 쉬프트부(32)를 통해서 n/2번 계속하여 n/2개의 쉬프트된 가산 2비트 및 쉬프트된 캐리 2비트와 준가산 부분적(n+2비트) 및 준캐리 부분적을 생성한다.This process is continued n / 2 times through the add and shift unit 32 to generate n / 2 shifted add 2 bits and shifted carry 2 bits and semiaddition partial (n + 2 bits) and quasi-carry partial. .
이때, 상기 가산 및 쉬프트부(32)에서는 세 개의 피연산자를 캐리 세이브 가산부 형태로 처리한 후 승수 Y를 2비트씩 레코딩하였기 때문에 2비트씩 오른쪽으로 쉬프트하여 출력한다. 이때, 준캐리 부분적과 준가산 부분적은 각각 최상위 비트(MSB)값으로 2비트 쉬프트된다.In this case, the adder and the shifter 32 processes the three operands in the form of a carry save adder, and since the multiplier Y is recorded by 2 bits, the shifter 32 shifts the bits by 2 bits to the right. At this time, the quasi-carrier portion and the quasi-addition portion are shifted by two bits to the most significant bit (MSB) value, respectively.
따라서, 캐리 룩어헤드 가산부(33)의 파이프라인 레지스터(331)의 첫 번째 클럭에서 상기 가산 및 쉬프트부(32)의 출력을 래치한 후 캐리 룩어헤드 가산기(332)에서 병렬 가산을 하여 승산의 최종결과를 얻는다.Therefore, after latching the output of the add and shift unit 32 at the first clock of the pipeline register 331 of the carry lookahead adder 33, the carry lookahead adder 332 performs parallel addition to multiply the multipliers. Get the final result.
즉, 병렬 가산을 할 때 캐리 전파시간이 속도 향상에 문제가 된다. 따라서, 상기 캐리 룩어헤드 가산부(33)는 이를 개선한 방법으로 다음단에 대한 캐리를 미리 찾는 방법을 이용한다.That is, the carry propagation time becomes a problem for speed improvement when performing parallel addition. Therefore, the carry look-ahead adder 33 uses a method of finding the carry for the next stage in advance as a method of improving this.
이때, 실제 LSI 로직사의 10K 라이브러리로 시뮬레이션한 결과 22ns의 시간지연과 파이프라인을 이용하지 않을시 39ns의 시간지연을 나타내므로 구조와 속도면에서 상당한 향상을 가져왔다.At this time, the simulation result of LSI Logic's 10K library shows a significant delay in structure and speed because it shows a time delay of 22ns and a time delay of 39ns without using a pipeline.
예를들어, 9비트의 피승수 X 와 승수 Y에서 최상위 비트(MSB)값이 '1'일 경우 2의 보수 형태이고, '0'일 경우는 언사인드 형태이며, 이에 대한 각 부의 시뮬레이션 결과는 제4도에 도시된 바와같다.For example, if the most significant bit (MSB) value of 9-bit multiplier X and multiplier Y is '1', it is a two's complement form, and if it is '0', it is an unsigned form. As shown in 4 degrees.
즉, 제4도(가)는 부스 레코딩부(31)의 시뮬레이션 결과를 나타내고, 제4도(나)는 가산 및 쉬프트부(32)의 시뮬레이션 결과를 나타내며, 제4도(다)는 캐리 룩어헤드 가산부(33)의 시뮬레이션 결과를 나타낸다.That is, FIG. 4A shows the simulation result of the booth recording unit 31, FIG. 4B shows the simulation result of the addition and shift unit 32, and FIG. 4C shows the carry look. The simulation result of the head adder 33 is shown.
이상에서와 같이 본 발명에 따른 고속 파이프라인 승상 회로에 의하면, 디지털 신호처리(Digital Signal Process:DSP), 고선명 텔레비젼(HDTV)등에 응용시, 언사인드와 2의 보수 형태의 고속 승산이 순수한 조합 논리회로와 래치로만 구성되어 수행됨으로써, 구조가 규칙적이고 간단해지며, 속도가 빨라지는 효과가 있다.As described above, according to the high-speed pipeline lift circuit according to the present invention, when applied to digital signal processing (DSP), high-definition television (HDTV), and the like, unsigned and high-speed multiplication in the form of two's complement is purely combined logic. By being composed of only circuits and latches, the structure is regular and simple, and the speed is increased.
Claims (4)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1019930015194A KR0141870B1 (en) | 1993-08-05 | 1993-08-05 | High speed pipeline multiplication circuit |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1019930015194A KR0141870B1 (en) | 1993-08-05 | 1993-08-05 | High speed pipeline multiplication circuit |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| KR950007294A KR950007294A (en) | 1995-03-21 |
| KR0141870B1 true KR0141870B1 (en) | 1998-07-01 |
Family
ID=66817523
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1019930015194A KR0141870B1 (en) | 1993-08-05 | 1993-08-05 | High speed pipeline multiplication circuit |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR0141870B1 (en) |
-
1993
- 1993-08-05 KR KR1019930015194A patent/KR0141870B1/en not_active IP Right Cessation
Also Published As
| Publication number | Publication date |
|---|---|
| KR950007294A (en) | 1995-03-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5375079A (en) | Arithmetical unit including accumulating operation | |
| US4953115A (en) | Absolute value calculating circuit having a single adder | |
| US20010009010A1 (en) | Data split parallel shifter and parallel adder/subtractor | |
| US5177703A (en) | Division circuit using higher radices | |
| JP3556950B2 (en) | Structure and method for reducing the number of carry look-ahead adder stages in high speed arithmetic devices | |
| KR100218825B1 (en) | Multiplication device and sum of products calculation device | |
| JPH04270415A (en) | High-performance adder | |
| KR0141870B1 (en) | High speed pipeline multiplication circuit | |
| US5870322A (en) | Multiplier to selectively perform unsigned magnitude multiplication or signed magnitude multiplication | |
| US5268858A (en) | Method and apparatus for negating an operand | |
| KR0147942B1 (en) | Booth recording circuit in multiplier | |
| US7620677B2 (en) | 4:2 Carry save adder and 4:2 carry save adding method | |
| US4890127A (en) | Signed digit adder circuit | |
| US5781465A (en) | Method and apparatus for fast carry generation detection and comparison | |
| US5978826A (en) | Adder with even/odd 1-bit adder cells | |
| Deshpande et al. | Squaring units and a comparison with multipliers | |
| KR0153759B1 (en) | High speed multiplication-accumulation circuit | |
| US4979140A (en) | Signed digit adder circuit | |
| US6631393B1 (en) | Method and apparatus for speculative addition using a limited carry | |
| JP3315042B2 (en) | Multiplier | |
| JP2991788B2 (en) | Decoder | |
| US7240085B2 (en) | Faster shift value calculation using modified carry-lookahead adder | |
| Kumar et al. | Design and implementation of 64-bit parallel prefix adder | |
| JP2864598B2 (en) | Digital arithmetic circuit | |
| Cappuccino et al. | High speed self-timed pipelined datapath for square rooting |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 19930805 |
|
| A201 | Request for examination | ||
| PA0201 | Request for examination |
Patent event code: PA02012R01D Patent event date: 19940304 Comment text: Request for Examination of Application Patent event code: PA02011R01I Patent event date: 19930805 Comment text: Patent Application |
|
| PG1501 | Laying open of application | ||
| E701 | Decision to grant or registration of patent right | ||
| PE0701 | Decision of registration |
Patent event code: PE07011S01D Comment text: Decision to Grant Registration Patent event date: 19971231 |
|
| GRNT | Written decision to grant | ||
| PR0701 | Registration of establishment |
Comment text: Registration of Establishment Patent event date: 19980325 Patent event code: PR07011E01D |
|
| PR1002 | Payment of registration fee |
Payment date: 19980325 End annual number: 3 Start annual number: 1 |
|
| PG1601 | Publication of registration | ||
| PR1001 | Payment of annual fee |
Payment date: 20010227 Start annual number: 4 End annual number: 4 |
|
| PR1001 | Payment of annual fee |
Payment date: 20020228 Start annual number: 5 End annual number: 5 |
|
| PR1001 | Payment of annual fee |
Payment date: 20030303 Start annual number: 6 End annual number: 6 |
|
| PR1001 | Payment of annual fee |
Payment date: 20040226 Start annual number: 7 End annual number: 7 |
|
| PR1001 | Payment of annual fee |
Payment date: 20050225 Start annual number: 8 End annual number: 8 |
|
| PR1001 | Payment of annual fee |
Payment date: 20060224 Start annual number: 9 End annual number: 9 |
|
| PR1001 | Payment of annual fee |
Payment date: 20070305 Start annual number: 10 End annual number: 10 |
|
| PR1001 | Payment of annual fee |
Payment date: 20080303 Start annual number: 11 End annual number: 11 |
|
| PR1001 | Payment of annual fee |
Payment date: 20090302 Start annual number: 12 End annual number: 12 |
|
| PR1001 | Payment of annual fee |
Payment date: 20100302 Start annual number: 13 End annual number: 13 |
|
| FPAY | Annual fee payment |
Payment date: 20110302 Year of fee payment: 14 |
|
| PR1001 | Payment of annual fee |
Payment date: 20110302 Start annual number: 14 End annual number: 14 |
|
| LAPS | Lapse due to unpaid annual fee | ||
| PC1903 | Unpaid annual fee |
Termination category: Default of registration fee Termination date: 20130209 |