Effective residue-to-binary converter with the Chinese Remainder Theorem

• Autorzy: Ulman Z. , Czyżak M.

Warianty tytułu

PL

Efektywna konwersja liczb z systemu resztowego do systemu wagowego z uzyciem chińskiego twierdzenia o resztach

• Języki publikacji: EN

Abstrakty

EN

The residue-to-binary conversion is the key operation in all digital signal processing applications that use the Residue Number System (RNS). In this work a new conversion technique based on the Chinese Remainder Theorem (CRT) for 5- and 6-bit moduli is proposed. It is especially suited for the realization with the use of binary arithmetic. the specific property of the realization with the use of binary arithmetic. The specific property of the technique is a way of calculation of the excess factor r in the CRT formula that makes possible, under certain conditions, the reduction of processed numbers from the range [0,nM) to [0,2M) where "M" is the product of moduli. This is done by replacing the calculation of "r" by the computation of the result of division of the sum of projections by a power of 2 close to M. Such approach allows for very effective hardware realization of the converter. Only small ROM`s and standard binary adders are required. Moreover, the pipelining on the Full-Adder (FA) level possible.

PL

Konwersja liczb z systemu resztowego do systemu binarnego jest podstawową operacją we wszystkich układach cyfrowego przetwarzania sygnałów, które wykorzystują system resztowy. W niniejszej pracy zaproponowano nowa metodę konwersji opartą o chinskie twierdzenie o resztach dla modułów 5- i 6-bitowych. Specyficzną cechą nowej metody jest sposób obliczania tzw. współczynnika pomiaru "r" w formule chińskiego twierdzenia o resztach, co umożliwia pod pewnymi warunkami, redukcję przetwarzanych liczb z zakresu [0,nM) do [0,2M). Jest to realizowane poprzez zastąpienie obliczania "r" obliczaniem rB, gdzie M jest potęgą liczby 2 bliska M. Takie podejście pozwala na bardzo efektywną sprzętową realizację konwertora. Konieczne są tylko małe pamięci typu ROM i standardowe sumatory binarne. ponadto możliwa jest realizacja potokowa z częstotliwością ograniczoną opóźnieniem sumatora 1-bitowego.

Słowa kluczowe

EN

digital signal processing; fast computer arithmetic; residue number system; residue-to-binary converter

PL

cyfrowe przetwarzanie sygnałów; szybka arytmetyka komputerowa; resztowy system liczbowy

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2003
• Tom: R. 49, nr 12
• Strony: 34--38
• Opis fizyczny: Bibliogr. 25 poz., tab., wzory

Twórcy

autor

Ulman Z.

• Gdańsk University of Technology, Faculty of Electrical and Control Engineering, Department of Control Engineering

autor

Czyżak M.

• Gdańsk University of Technology, Faculty of Electrical and Control Engineering, Department of Theoretical Electrotechnics and Informations

Bibliografia

• [1] S. Szabo and R. J. Tanaka: Residue Arithmetic and its Applications to Computer Technology, New York, McGraw-Hill, 1967.
• [2] N. B. Chacraborti, J. S. Soundaranajan and A. L. N. Reddy: An implementation of mixed-radix conversion for residue number systems, applications, IEEE Trans. on Comput. vol. C-35, August 1986.
• [3] F. Barsi, M. C. Pinotti: Time-optimal mixed radix conversion for residue number applications, Computer J., vol. 37, no. 10, 1994, pp. 907-916.
• [4] H. Henkelmann, A. Drolshagen, H. Bagherinia, H. Ahrens, W. Anheier: Automated implementation of RNS-to-binary converters, IEEE ISCAS Conference, Naval Postgraduate School, Monterrey, CA, June 3, 1998.
• [5] C. H. Huang: A fully parallel mixed-radix conversion algorithm for the residue number system, IEEE Trans, on Comput. vol. C-32, April 1983, pp. 398-402.
• [6] D. F. Fraser, N. J. Bryg: An adaptive digital signal processor based on the residue number system. Proc. AIAA 2nd Comput. Aereospace Conf., Los Angeles, CA, Oct. 22-24, 1979.
• [7] V. S. Cheng, C. H. Huang.: On the decoding of residue numer, Proc. Int. Symp. Mini- Microcomput. Contr. Measurement, San Francisco, CA, May 20-22, 1981.
• [8] F. J. Taylor and A. S. Ramnarayanan: An efficient rcsiduc-to-dccimal converter, IEEE Trans. Circuits Syst. vol. CAS-28, Dec. 1981, pp. 1164-1169.
• [9] W. K. Jenkins: A technique for the efficient generation of projections for error correcting residue codes. IEEE Trans. Circuits Syst. vol. CAS-30, pp. 223-226, Feb. 1984.
• [10] C. N. Zhang, B. Shirazi, D. Y. Y. Yun: Parallel designs for chínese remainder conversion," Proc. Int. Conf. on Parallel Processing. August 17-21, 1987, pp. 557-559.
• [11] K. M. Elleithy, M. A. Bayoumi: Fast and flexible architectures for RNS arithmetic decoding, IEEE Trans. on Cicuits and Systems-II: Analog and digital signal processing, vol. 39, No. 4. April 1992, pp. 226-235.
• [12] S. J. Pestrak: Design of high-speed residue-to-btnary number system converter based on the Chinese Remainder Theorem. Proc. lCCD'94, Int. Conf. on Computer Design: VLSI in Computers and Processors.,Cambridge, MA, Oct. 10-12,1994, pp. 508-511.
• [12] S. J. Piestrak: 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.
• [13] Y. Wang: Residue-to-binary converters based on the new Chinese Remainder Theorems, IEEE Trans. Circuits Syst.. - II Analig and Digital Signal Processing, vol. 47, march 200, pp. 197-205.
• [14] Z. Wang, G. A. Julien, W. C. Miller: An improved residue-to-binary converter, IEEE Trans. Circuits Syst. - I: Fundamental Theory and Applications, vol. 47, March 2000, pp. 1437-1440.
• [15] G. C. Cardarilli, M. Re, R. Lojacono: RNS-to binary conversion for efficient VLSI implementation, IEEE Trans. Circuits Syst. - I: Fundamental Theory and Applications, vol. 45, June 1998, pp. 667-669.
• [16] M. A. Soderstrand, C. Vernia and J.-H. Chang: An improved residue number system digital-to-analog converter: IEEE Trans. Circuits Syst. vol. CAS-30, 1983, pp. 903-907.
• [17] S. J. Meehan, S. D. O1Neil, J. J. Vaccaro: An universal input and output RNS converter, IEEE Trans. Circuits Syst. vol. CAS-37, June 1990, pp. 1158-1162.
• [18] J. Y. Kim, K. H. Park, H. S. Lee: Efficient residue-to-binary conversion technique with rounding error compensation, IEEE Trans. Circuits Syst. vol. CAS-38, march 1991, pp. 315-317.
• [19] I. Lee, W. K. Jenkins: The design of residue number system arithmetic units for VLSI adaptive equalizer, Proc. of the Great Lakes Symposium on VLSI, Feb. 1998, pp. 179-184.
• [20] T. V. Vu: Efficient implementations of the Chinese Remainder Theorem for sign detection and residue decoding, IEEE Trans. Comput, vol. C-34, pp. July 1985, pp. 646-651.
• [21] Z. D. Ulman and M. Czyżak: Highly parallel, fast scaling of numbers in nonredundant residue arithmetic, IEEE Trans. Signal Processing, vol. 46, pp. 487-496, Feb. 1998.
• [22] G. C. Cardarilli, M. Re, R. Lojacono: A systolic architecture for jigh-performance scaled residue to binary conversion, IEEE Trans. Circuits Syst. - I: Fundamental Theory and Applications, vol. 47, October 2000, pp. 667-669.
• [23] N. Burgess: Scaled and unscaled residue number system to binary conversion techniques using the core function, 1997 IEEE Symposium on Computer Arithmetic, pp. 250-257.
• [24] Xilinx Inc.: Virtex II Pro FPGA, 2003.
• [25] Samsung Electronics: 0.18 Standard Cell Logic Library STDL 150, 2001.