Propozycja metody mnożenia liczb ze znakiem

• Autorzy: Gryś S.
• Języki publikacji: PL

Abstrakty

PL

Niniejszy artykuł poświęcono programowym rozwiązaniom operacji mnożenia, przeznaczonym do implementacji w relatywnie prostych systemach wbudowanych wyposażonych w 8/16 bitowe mikroprocesory, które nie posiadają w liście rozkazów mnożenia liczb ze znakiem. Reprezentantami tej grupy mikroprocesorów są m.in.: 8051, Freescale 68HC08 i HCS12, Atmel ATtiny, Zilog eZ8core!, STMicroelectronics ST7, Microchip PIC16/18, Texas Instruments MSP430, NEC 78K0S/0R i in.

EN

An efficient technique of signed binary multiplication using unsigned multiply instruction was presented in this paper. A performance of the proposed technique was compared to the software emulated versions of classical techniques such as: radix-2 Booth method, reversal of sign method (negative to positive conversion) and sign extension method. Numerous examples were provided to show the efficiency of the technique in the context of practical software implementation. The proposed algorithm is suitable for embedded systems based on the widespread microprocessors/microcontrollers which have an unsigned multiplication in their instruction set but they lack signed multiply instruction. The sampies of code presenting the solutton of signed multiplication problem using various techniques were prepared in an assembly language for MCS 8051 compatible microcontroller. The comparison of the performance of algorithms was carried out als for 8051 core treated as reference microcontroller architecture but the obtained conclusions are potentially general and not only limited to this microcontroller.

Słowa kluczowe

PL

algorytmy arytmetyczne; systemy wbudowane; mnożenie; języki asemblerowe

EN

arithmetic algorithms; signed multiplication; embedded system; assembly language

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2009
• Tom: nr 1 (18)
• Strony: 15--27
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Gryś S.

• Politechnika Częstochowska Wydział Elektryczny

Bibliografia

• [1] Wallace C. S. A suggestion for a fast multiplier. IEEE Trans. Comput. No 13 (2)/1964, 1964, s. 14-17.
• [2] Dadda L. Some schemes for parallel multiplier. Alta Frequenza, Vol. 34, 1992, s. 349-356.
• [3] Millar B., Madrid P., Swartzlander E. A fast hybrid multiplier combining booth and Wallace/ DADDA algorithms. The 35th Midwest Symposium on Circuits and Systems, 1992, s. 158-165.
• [4] Ercegovac M. D., et al. Fast multiplication without carry-propagate addition. IEEE Trans. Comput. Vol. 39, No 11/1990, 1990, s. 1385-1390.
• [5] Dae Won Kim, Jun Rim Choi. Variable radix-2 multibit coding for 400 Mpixel/s DCT/IDCT of HDTV video decoder. Integration, the VLSI journal, Vol. 35, 2003, s. 47-67.
• [6] Li C. W., Wah B. W. Optimal bit-level processor arrays for matrix multiplication. Proc. of the 11th International Conference on Systems Engineering, 1996, s. 596-601.
• [7] Smith S. C., et al. NULL convention multiply and accumulate unit with conditional rounding, scaling, and saturation. Journal of Systems Architecture, Vol. 47, 2002,s. 977-998.
• [8] da Costa E., Monteiro J., Bampi S. A new array architecture for signed multiplication using Gray encoded radix-2m operands. Integration the VLSI journal, Vol. 40, 2007,s. 118-132.
• [9] Yu Z., Wasserman L., Willson A. A painless way to reduce power by over 18% in booth-encoded carry-save array multipliers for DSP. Workshop on Signal Processing Systems, 2000, s. 571–580.
• [10] Baugh C. R., Wooley B. A. A two’s complement parallel array multiplication algorithm. IEEE Transactions on Computers. C-22, December 1973, p. 1045-1047.
• [11] Omondi A. R. Computer Arithmetic Systems, Algorithms, Architecture and implementations. Series in Computer Science Prentice-Hall International, Englewood Cliffs, New York, 1994.
• [12] Parhami B. Computer Arithmetic. Algorithms and Hardware Designs. Oxford University Press, New York, 2000.
• [13] Koren I. Computer Arithmetic Algorithms. A. K. Peters, Natick, MA, 2002.
• [14] Gryś S. Arytmetyka komputerów – w praktyce. Wyd. Naukowe PWN, Warszawa, 2007.
• [15] Biernat J. Metody i układy arytmetyki komputerowej. Wyd. Politechniki Wrocławskiej, Wrocław, 2001.
• [16] Booth A. D. A signed binary multiplication technique. Journal of Applied Mathematics, Vol. 4, No 2/1951, 1951, s. 236–240.
• [17] McSorley O.L. High speed arithmetic in binary computers. Proceedings of IRE, January 1961, s. 67-91.
• [18] Sam H., Gupta A. A generalized multibit coding of two’s complement binary numbers and its proof with application in multiplier implementation. IEEE Trans. Comput.,Vol. 39, No 8/1990, 1990, s. 1006-1015.
• [19] Efstathiou C., Vergos H. Modified booth 1’s complement and modulo 2n-1 multipliers. The 7th IEEE International Conference on Electronics Circuits and Systems, 2000, s. 637-640.
• [20] Gallagher W., Swartzlander E. High radix booth multipliers using reduced area adder trees. The 28th Asilomar Conference on Signals, Systems and Computers, 1994, s. 545-549.
• [21] Goldovsky A., et al. Design and implementation of a 16 by 16 lowpower two’s complement multiplier. IEEE Int. Symp. Circuits Syst., 2000, s. 345-348.
• [22] Seidel P., McFearin L., Matula D. Binary multiplication radix-32 and radix-256. 15th Symposium on Computer Arithmetic, 2001, s. 23-32.
• [23] Cherkauer B., Friedman E. A hybrid radix-4/radix-8 low power, high speed multiplier architecture for wide bit widths. IEEE Int. Symp. Circuits Syst., 1996, s. 53-56.
• [24] Wang Y., Jiang Y., Sha E. On area-efficient low power array multipliers. The 8th IEEE International Conference on Electronics, Circuits and Systems, 2001, s. 1429-1432.