The increase of DFT and DCT computation rate and accuracy with the use of parallel operations

• Autorzy: Pogribny W. , Drechny M.
• Języki publikacji: EN

Abstrakty

EN

The increase of DFT and DCT DFT (Discrete Fourier Transform) and its derivative DCT (Discrete Cosine Transform) are the transforms most often used in DSP (Digital Signal Processing), especially in data communications for signal compression [1, 2, 3, 4]. DFT and DCT algorithms have been modified and their rate and accuracy optimized for many years [3, 4]. Most of them are calculated in multibit PCM (Pulse Code Modulation) format. The differential DPCM (Differential Pulse Code Modulation) format, used in this work can be an alternative for PCM format applied in DFT and DCT. It ensures higher accuracy of computation with code word length shorter than PCM code word. When we modify DPCM format (Section 3) in such a way that the quantization steps are set of the numbers with a base 2 and exponent belonging to a natural numbers set, the multiplication operation rate, as one of the most often used operation in DSP, increases. It is possible because multiplication operations can be replaced with fast shift bit logical operations. The parallel combination of some MDPCM (Modified Differential Pulse Code Modulations) codes creates SDPCM (Synthesized Differential Pulse Code Modulation) code (Section 3), which has high computational accuracy, equal to the DPCM accuracy, however it does not require multiplications. In most cases, parallel computations lead to their rate increase in comparison to computation rate of sequentially operations. These calculations, apart from using appropriate and accurate algorithms require applying the systems which enable the effective work of the parallel methods. Thus, for this purpose the programmable FPGA devices (Fields Programmable Gates Array) have been the most commonly used recently. Their main advantages are high speed of operations, the possibility of programming every computational structure and their low price. In this work, apart from fast parallel DFT and DCT algorithms, we presented the structures of processing DFT and DCT systems (specialized processors) working in parallel way. The processing systems presented in Section 5 allow fast and accurate calculations without time-consuming multiplications. With reference to the article [5] presenting fast differential DCT algorithms, in this work the authors proposed another way of increasing the rate and accuracy of DCT computations, which consists in the modifications of a partV

Słowa kluczowe

EN

DFT; discrete Fourier transform; DCT; discrete cosine transform; DPCM; differential pulse code modulation; paralell computations

PL

DFT; dyskretna transformata Fouriera; DCT; dyskretna transformata cosinusowa; DPCM; obliczenia równoległe

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2007
• Tom: Vol. 53, No 2
• Strony: 155--176
• Opis fizyczny: Bibliogr. 13 poz., tab., wykr.

Twórcy

autor

Pogribny W.

autor

Drechny M.

• University of Technology and Life Sciences, Faculty of Telecommunications and Electrical Engineering, Al. Prof. S. Kaliskiego 7, 85-796 Bydgoszcz, Poland,

Bibliografia

• 1. D. Hankerson, G.A. Harris, P.D. Johnson: Introduction to Information Theory and Data Compression, CRC Press, Boca Raton, 2nd edition, 2003.
• 2. D. Salomon: Data Compression. The Complete Reference, Springer-Verlag, New York, 3rd edition, 2004.
• 3. K.R. Rao, P. Yip: Discrete Cosine Transform - algorithms, advantages, applications. San Diego, Academic Press, 1990.
• 4. R.N. Bracewell: The Fourier Transforms and its Applications, McGraw Hill, Singapore 2000.
• 5. W. Pogribny, M. Drechny: Różnicowa DCT w zagadnieniach przetwarzania sygnałów, Kwartalnik Elektroniki i Telekomunikacji, t. 52 z. 4, ss. 797-813.
• 6. P.J. Grewen, W.F.G. Mecklenbrauker, N.A.M. Verhoeckx, F.A.M. Snijders, H.A. van Essen: A New Type of Digital Filter for Data Transmission. IEEE Transaction on Communications, vol. 23, issue 2, February 1975, pp. 222-234.
• 7. T.P. Zieliński: Cyfrowe przetwarzanie sygnałów, od teorii do zastosowań, WKiŁ, 2005.
• 8. U. Meyer-Bayese: Digital Signal Processing with Field Programmable Gate Arrays, Springer- Verlag, 2001.
• 9. N. Ahmed, T. Natarajan, K.R. Rao: Discrete Cosine Transform. IEEE Transaction on Computers, vol. 23, January 1974, pp. 90-93.
• 10. W.B. Pennebaker, J.L. Mitchell: JPEG Still Image Data Compression Standard, Van Nostrand Reinhold, New York, 1993.
• 11. W. Pogribny, I. Zelinski: Differential coding and processing of images, Proceedings of SPIE: Diagnostic Imaging, Technologies and Applications, vol. 3827, Bellingham, Washington, 1999, pp. 155-163.
• 12. http://www.xilinx.com/bvdocs/userguides/ug070.pdf - 27.11.2006.
• 13. http://www.xilinx.com/products/silicon_solutions/fpgas/virtex/virtex4/overview/index.htm - 27.11.2006.