An improved high-speed residue-to-binary converter based on the Chinese Remainder Theorem

• Autorzy: Czyżak M.

Warianty tytułu

PL

Ulepszony szybki konwerter z systemu resztowego do systemu binarnego oparty na chińskim twierdzeniu o resztach

• Języki publikacji: EN

Abstrakty

EN

A new high-speed residue-to-binary converter for five bit moduli based on the Chinese Remainder Theorem is presented. The orthogonal projections are computed by mapping using five-variable logic functions. The sum of projections is calculated using the Wallace tree. The output carry-save representation is partitioned into four segments in such a way that the sum of the numbers represented by the low-order segments does not exceed the Residue Number System (RNS) range M. The bits of the high-order segments are compressed by the small carry-propagate adder that in effect diminishes the size of the modulo M generator used to reduce the number represented by the high-order segments. The obtained sum is smaller than 2M, thus the effective two-operand final modulo M adder can be used. The proposed converter can be pipelined on the full-adder level.

PL

Zaprezentowano nową architekturę konwertera z systemu resztowego do systemu binarnego dla modułów 5-bitowych opartą na chińskim twierdzeniu o resztach. Projekcje ortogonalne określane są poprzez odczyt z pamięci ich obliczonych wartości. Pamięć symulowana jest poprzez użycie funkcji logicznych o liczbie zmiennych równej bitowej długości modułu. Suma projekcji obliczana jest przy użyciu sumatora wielooperandowego opartego na drzewie Wallace'a. Wyjściowe wektory sumy i przeniesienia są dzielone na cztery segmenty w taki sposób, że suma liczb reprezentowanych przez bity o młodszych wagach nie przekracza zakresu liczbowego systemu resztowego, M. Bity należące do segmentów o starszych wagach są dodawane w niewielkim sumatorze, co w efekcie umożliwia znaczne zmniejszenie rozmiaru generatora stosowanego do redukcji modulo M liczby reprezentowanej przez te bity. Suma otrzymana po zsumowaniu liczby reprezentowanej przez segmenty o młodszych wagach i zredukowanej liczby reprezentowanej przez segmenty starszych wagach nie przekracza 2M, co umożliwia zastosowanie efektywnego sumatora końcowego modulo M. Konwerter w proponowanej konfiguracji może pracować potokowo na poziomie pełnego sumatora.

Słowa kluczowe

EN

residue number system; residue-to-binary conversion

PL

system resztowy; konwersja z systemu resztowego do systemu binarnego

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2007
• Tom: R. 53, nr 4
• Strony: 72--73
• Opis fizyczny: Bibliogr. 19 poz., tab., wzory

Twórcy

autor

Czyżak M.

• Wydział Elektrotechniki, Politechnika Gdańska,

Bibliografia

• [1] Szabo N. S., Tanaka R. J.: Residue Arithmetic and its Applications to Computer Technology, New York, McGraw-Hill, 1967.
• [2] Soderstrand M. A. et al. : Residue Number System Arithmetic: Modem Applications in Digital Signal Processing, IEEE Press, NY, 1986.
• [3] Chacraborti, N. B. Soundaranajan J. S. and Reddy A. L. N.: An implementation of mixed-radix conversion for residue number systems applications, IEEE Trans. on Comput., Vol. C-35, August 1986.
• [4] Barsi F., Pinotti M. C.: Time-optimal mixed radix conversion for residue number applications, Computer J., Vol. 37, no. 10, 1994, pp. 907-916.
• [5] Henkelmann H., Drolshagen A., Bagherinia H., Ahrens H., Anheier W.: Automated implement0ation of RNS-to-binary converters IEEE ISCAS Conference, Naval Postgraduate School, Monterrey, CA, June 3, 1998.
• [6] Zhang C. N., Shirazi B., Yun D. Y. Y.: Parallel designs for chinese remainder conversion, Proc. Int. Conf. on Parallel Processing, August 17-21, 1987, pp. 557-559.
• [7] Elleithy K. M., Bayoumi M. A.: Fast and flexible architectures for RNS arithmetic decoding, IEEE Trans. on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 39, No. 4, April 1992, pp. 226-235.
• [8] Piestrak S. J.: Design of high-speed residue-to-binary number system converter based on the Chinese Remainder Theorem, Proc. ICCD'94, Int. Conf. on Computer Design: VLSI in Computers and Processors, Cambridge, MA, Oct. 10-12, 1994, pp. 508-511.
• [9] Wang Y.: Residue-to-binary converters based on the new Chinese Remainder Theorems, IEEE Trans. Circuits Syst. -II Analog and Digital Signal Processing, Vol. 47, March 2000, pp. 197-205.
• [10] Wang Z., Jullien G. A., Miller W. C.: An improved residue-to-binary converter, IEEE Trans. Circuits Syst. -I :Fundamental Theory and Applications,Vol. 47, Sept. 2000, pp. 1437-1440.
• [11] Meehan S. J, O'Neil S. D., Vaccaro J. J.: An universal input and output RNS converter, IEEE Trans. Circuits Syst. Vol. CAS-37, June 1990, pp. 1158-1162.
• [12] Cardarilli G. C., Re M., Lojacono R. : A systolic architecture for highperformance scaled residue to binary conversion, IEEE Trans. Circuits Syst. -I :Fundamental Theory and Applications, vol. 47, October 2000, pp. 667-669.
• [13] Huang C. H.: A fully parallel mixed-radix conversion algorithm for the residue number system IEEE Trans. on Comput. vol. C-32, April 1983, pp. 398-402.
• [14] Burgess N.: Scaled and unsealed residue number system to binary conversion techniques using the core function, 1997 IEEE Symposium on Computer Arithmetic, pp. 250-257.
• [15] Czyżak M.: High-speed binary-to-residue converter with the improved architecture, SPETO 2004, May, Niedzica, Poland.
• [16] Hwang K.: Computer Arithmetic, Wiley, 1979.
• [17] Samsung Electronics: Standard Cell Logic Library STDL 130, 2001.
• [18] Czyżak, M.: High-speed residue-to-binary converter based on the Chinese Remainder Theorem, Proc. of the Sixth IM. Scientific Conf. Electronic Computers and Informatics ECI 2004, Sept. 22-24, 2004, Kosice-Herl`any, Slovakia, pp. 212-207.
• [19] Xilinx: Virtex-II Pro Platform FPGA Handbook, 2002.