Fast Dynamically Reconfigurable Architectures For 1-D And 2-D Recursive Digital Filters
Architectures Rapides Dynamiquement Reconfigurables des Filtres Numériques Récursifs 1-D et 2-D
OPEN ACCESS
In this paper, we consider the array processors implementation of the infinite impulse response (11R)1-D and 2-D digital filters that require recursive computations. We use the state space representation to obtain, in a straight forward manner, efficient implementation via dynamically switchable systolic arrays (cylindrical type) of 1 -D direct realisation . This direct description leads to reduce the computation speed and the throughput rate. In order to improve, in a general way, the throughput rate performance of recursive filtering arrays, the solution proposed, in this paper, is based on the CTP decomposition technique of Porter which transforms the matrix-column product on a triple matrix product. It is shown in this work that this technique allows a realisation of IIR filters via dynamically reconfigurable cylindrical architectures that are much faster. However, this throughput improvement is obtained in the cost of a hardware complexity. The use of a sparse matrix of the tridiagonal type with the CTP decomposition permits a significant improvement of the hardware complexity of recursive filter arrays .
Résumé
L'objectif de ce travail consiste à développer des architectures systoliques, aussi performantes que possible, pour des filtres numériques RII 1-Det 2-D nécessitant des calculs récursifs. La mise enoeuvredirecte des filtres RII sur les réseaux systoliques (type cylindrique) dynamiquement commutables est obtenue en les décrivant par des opérations matricielles dans l'espace d'état . Cependant, cette réalisation systolique engendre une latence proportionnelle à l'ordre du filtre . Pour améliorer d'une manière générale les performances en débit de données des réseaux de filtrage récursif, la solution proposée dans cet article repose sur la décomposition CTP de Porter qui transforme le produit d'une matrice par une colonne en un produit de trois matrices. Nous montrons que cette décomposition permet de réaliser des filtres RII par des structures cylindriques dynamiquement reconfigurables plus rapides. Néanmoins, le gain en débit de données est obtenu au détriment de la complexité de mise en oeuvre. La version améliorée de la technique de décomposition CTP est appliquée aux filtres RII 1-D représentés par des matrices creuses du type tridiagonale dans l'espace d'état. Ce dernier algorithme permet une amélioration significative de la complexité matérielle.
Recursive digital filters, array processors, systolic, cylindrical, state space, sparse matrix, throughput, latency.
Mots clés
Filtres numériques récursifs, processeurs, systolique, cylindrique, espace d'etat, matrices creuses, débit en données, latence.
[1] H. T. Kung, «Why systolic architectures?», Computer, Vol. 15, 1982, pp. 3746.
[2] L. Guo-Jie, B. Wash, «The design of optimal systolic arrays», IEEETrans. Comput.,Vol. C-34, N° 1, Jan. 1985, pp. 66-77.
[3] P. R. cappello, K. steiglitz,«Unifying VLSI array designs with geometric transformations», in Proc. Int. Conf. Parallel Processing, 1983, pp. 448-457.
[4] S. Y. Kung, H. J. Whitehouse, T. Kailath, «VLSI and modern signal processing», Englewood Cliffs, N. J., Prentice-Hall, Inc. 1985.
[5] J.H. Cheng, O. H. Ibarra, T. C. Pong, S. M. Sohn, «Two- dimensional convolution on a pyramid computer», in Proc. Int. Conf. Parallel Processing, 1987, pp. 780-782.
[6] J. V. Mc Canny, J. G. Mc Whirter, «Some systolic array developments in the UK», IEEE Comp.,Vol. 20, N° 7, 1987, pp. 53-65.
[7] G. I. Kechriotics, M. Au, M. Bletsas, R. Tolimieri, E. S. Manolakos, «A new approach for computing multidimensional DFT's on parallel machines and its implementation on the iPSC/860 hypercube», IEEETrans. on Signal Processing, Vol.43, N° 1, Jan. 1995.
[8] I Gertner, M. Shamash, «VLSI architectures for multidimensional Fourier transform processing», IEEETrans. on Computers, Vol. C-36, N° 11, Nov. 1987.
[9] R. K. Montoye, D. H. Lawrie, «A practical algorithm for the solution of triangular systems in a parallel processing systems», IEEE Trans. Comput., Vol.C-31, N'1, Nov. 1982.
[10] J. G. Chung, K. K. Parhi, « Pipelining of lattice IIR digital filters«, IEEE Trans. on Signal Processing, Vol. 42, N°4, April 1994, pp. 751-761.
[11] L. E. Lucke, K. K. Parhi, «Parallel processing architecture for rank order and stack filters», IEEE Trans. on Signal Processing, Vol. 42, N°5, May 1994, pp. 1178- 1188.
[12] P. Comon, Y. Robert, «A systolic array for computing BA-I>>, IEEETrans. on Acoustics, Speech, and Signal Processing, Vol. ASSP 35, N'6, June. 1987.
[13] W. A. Porter, J. L. Aravena, «Cylindrical arrays for matrix multiplications», in Proc. 24thAllerton Conf., Oct. 1986.
[14] W. A. Porter, and J. L. Aravena,«Orbital architectures with dynamic reconfiguration», Proc.IEE, part E, Vol. 134, N°6, Nov. 1987, pp. 281-287.
[15] W. A. Porter, J. L. Aravena, «Array based design of digital filters», IEEE Trans.on Acoustics, Speech, and Signal Processing, Vol. 38, N°9, Sep. 1990, pp. 1628-1632.
[16] W. A. Porter, «Concurrent forms of signal processing algorithms», IEEE Trans. on Circuits and Systems, Vol. 36,N°4, Apr. 1989, pp. 553-560.
[17] W. A. Porter, «Fast forms of banded maps», IEEE Trans. on Acoustics, Speech,and Signal Processing,Vol. 38, N°7, July. 1990, pp. 1192-1197.
[18] P. R. Cappello, «Towards an FIR filter tissue», Proc. IEEE Int Conf. on Acoustics, Speech, and Signal Processing, Tampa, Florida, USA, Mar.1985, pp. 276-279.
[19] M. M. Fahmy, Y. Wan, «New array processor architectures for twodimensional FIR digital filters», IEE Proc. ,Vol. 136, part E, N°4, July 1989, pp. 234-238.
[20] K K. Parhi, D G. Messerschmitt, «Block digital filtering via incremental block-state structure», Proc. IEEE Int. Symp. on Circuits and Systems, Philadelphia, PA, USA, May 1987, pp. 645-648.
[21] R. F. Woods, J. V. McCanny,<<Design of a high-performance IIR digital filter chip»,IEE Proc., part E,Vol . 139, N°3, May 1992, pp. 195-202.
[22] D. Chikouche, R. E. Bekka, A. Khellaf, A. Boucenna, «Orbital architectures for recursive digital filters», Proc. Maghrebean Conff on Soft. Eng. and Art. Intel.,Algiers, Apr. 1996, pp. 273-277.
[23] W. A. Porter, «Fast forms of banded maps», IEEE Trans. on Acoustics, Speech, and Signal Processing, Vol. 38, N°7, Jul.1990.
[24] K. Ogata, « », Englewood Cliffs, N. J., Prentice-Hall, Inc. 1987.
[25] D. F. Delchamps, «State-space and imput-ouput linear systems», SpringerVerlag, N. Y. 1988.
[26] F. J. Taylor, «Digital filter design handbook», Marcel dekker, Inc., N. Y. 1983.
[27] T. Lin, M. Kawamata, T. Higuchi, «Design of 2-D digital filters with an arbitrary response and no overflow oscillations based on a new stabilitycondition», IEEE Trans. on Circuits and Systems, Vol. CAS-34, N°2, Feb. 1987, pp. 113-126.
[28] S. A. H. Aly, M. Fahmy, «Spatial-domain design of two-dimensional recursive digital filters», IEEE Trans. on Circuits and Systems, Vol. CAS-27, Oct. 1980, pp. 892- 900.
[29] J. W. Woods, J. H. Lee, I. Paul, «Two-dimensional IIR filter design with magnitude and phase error criteria», IEEETrans. on Acoustics,Speech, and Signal Processing, Vol. ASSP-31,Aug. 1983, pp. 886-894.
[30] R. P. Roesser, «A discrete state space model for linear image processing», IEEE Trans. Automat. Contr., Vol. AC-20, Feb. 1975, pp. 1-10.
[31] S. J. Varoufakis, P. N. Paraskevopoulos, G. E. Antoniou, «On the minimal state-space realizations of all- pole and all-zero 2-D systems », IEEETrans. on Circuits and Systems, Vol.CAS-34, N° 3, Mar. 1987, pp. 289- 292.
[32] M. B. Srivastava, M. Potkonjak, «Optimum and heuristic transformation techniques for simultaneous optimisation of latency and throughput», IEEE Trans. VLSI Systems, Vol. 3, N° 1, March 1995, pp. 2-19.
[33] P. R. Gelabert, T. P. Barnwell, «Optimal periodicmultiprocessor scheduler for fully specified flow», IEEE Trans. Signal Process., Vol. 41, 1993, pp. 858-888.
[34] K K. Parhi, M. Hatamian, «A high sample rate recursive digital filter chip», in «VLSI Signal Processing III«,IEEEPress, N. Y., USA, 1988, pp. 3-14.