Z. J. Mou and . Duhamel, Fast FIR filienng [31 R.E. Blahut. Fait Algorithms for Digital Signal Processing, 1985.

C. S. Burrus, Digital filter structures described by distributed arithmetic, IEEE Traits. Circuits £ Systems, pp.674-680, 1977.

R. Crochiere and L. R. Rabiner, Multirate Digital Signal Processing, 1983.

K. K. Hayashi, . K. Dhan, K. Sugahara, and . Hirano, Design of high-speed digital filters suitable for multi-DSP implementation, CAS-33. Ftbruary, pp.202-216, 1986.

H. J. Nussbaumer, Fast Fourier Trallsf-and Coniohttion Algorithms. Spnnger, 1981.

P. C. Palla, S. D. Antoniou, and . Morgera, Higher radix aperiodic convolution algorithms, IEEE Trans. Aeoust., Speech, Signal Process, pp.60-68, 1986.

A. Peled and B. Liu, A new hardware realization of digital filters, IEEE Trans. Aeoust., Speech, Signal ProCfts, vol.22, pp.456-462, 1974.

S. Winograd, Arithmetic complexity of computations, CBMS-MSF Régional Conf. Séries in Applied Mathematics, 1980.

S. Winograd, Arithmetic complexity of computations, CBMS-NSF Reginal Conf. Séries in Applied Mathematics, 1980.

Z. J. Mou and P. Duhamel, Fast FIR filtering: algorithms and implementations, Signal Processing, pp.377-384, 1987.

M. Vetterli, Running FIR and HR filtering using multirate filter banks, IEEE Trans. Acoust. Speech, Signal Processing, vol.36, pp.730-738, 1988.

H. K. Kwan and M. T. Tsim, High speed 1-D FIR digital filtering architecture using polynomial convolution, Proc. IEEE Int. Conf. Acoust. Speech, Signal Processing, pp.1863-1866, 1987.

P. P. Vaidyanathan and S. K. Mitra, Polyphasé networks, block digital filtering, LPTV Systems and alias-free QMF banks: A unified approach based on pseudocirculants, IEEE Trans. Acoust. Speech, Signal Processing, vol.36, pp.381-391, 1988.

P. Duhamel and M. Vetterli, Improved Fourier and Hartley transform algorithms: application to cyclic convolution of real data, IEEE Trans. Acoust. Speech, Signal Processing, vol.35, pp.818-824, 1988.

S. Winograd, Some bilinear forms whose multiplicative complexity dépends on the field of constants, Number Theory in Digital Signal Processing, vol.10, pp.169-180, 1977.

R. C. Agarwal and J. W. Cooley, New algorithms for digital convolution, IEEE Trans. Acoust. Speech, Signal Processing, vol.25, pp.392-410, 1977.

H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, Real-valued fast Fourier transform algorithms, IEEE Trans. Acoust. Speech, Signal Processing, vol.35, pp.849-863, 1988.

Z. J. Mou and P. Duhamel, A unified approach to the fast FIR filering algorithms, Proc. IEEE Int. Conf. Acoust. Speech, Signal Processing, pp.1914-1917, 1988.

R. E. Blahut, Fast Algorithms for Digital Signal Processing, 1985.

P. C. Balla, A. Antoniou, and S. D. Morgera, Higher radix aperiodic convolution algorithms, IEEE Trans. Acoust. Speech, Signal Processing, vol.34, pp.60-68, 1986.

R. E. Crochiere and L. R. Rabiner, Multirate Digital Signal Processing, 1983.

R. C. Agarwal and C. S. Burrus, Fast one-dimensional digital convolution by multi-dimentional techniques, IEEE Trans. on

, ASSP, vol.22, issue.l, pp.1-10, 1974.

R. C. Agarwal and J. W. Cooley, New algorithms for digital convolution, IEEE Trans. on ASSP, issue.5, pp.392-410, 1977.

P. C. Balla, A. Antoniou, and S. D. Morgera, Higher radix aperiodic convolution algorithms, IEEE Trans. Acoust. Speech, Signal

. Processing, ASSP-34, N°l, pp.60-68, 1986.

M. G. Bellanger and J. L. Daquet, TDM-FDM Transmutiplexer: Digital Polyphasé and FFT, vol.22, pp.1199-1204, 1974.

J. Benesty,

R. E. Blahut, Fast Algorithms for Signal Processing, 1985.

D. S. Chan and L. R. Rabiner, Analysis of quantization errors in the direct form for finite impulse response digital filters, IEEE Trans. Audio Electroacoust, issue.4, pp.354-366, 1973.

G. A. Clark, S. K. Mitra, and S. R. Parker, Block implementation of adaptive digital filters, IEEE Trans. Acoust. Speech, Signal Processing, vol.29, pp.744-752, 1981.

J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier séries, Math. of Comput, vol.19, pp.297-301, 1965.

R. E. Crochiere and L. R. Rabiner, Multirate Digital Signal Processing, 1983.

P. Duhamel and M. Vetterli, Improved Fourier and Hartley Transform Algorithms: Application to Cyclic Convolution of Real Data, IEEE Trans. on ASSP, issue.6, pp.818-824, 1987.

P. Duhamel, Z. J. Mou, and J. Benesty, Une présentation unifiée du filtrage rapide fournissant tous les intermédiaires entre traitements temporels et fréquentiels, Proc. of 12th GRETSI Syposium, 1989.

K. Hayashi, K. K. Dhar, K. Ksugahara, and . Hirano, Disign of high speed digital filters suitable for multi-DSP implementation, IEEE Trans. Circuits Syst, vol.33, pp.202-216, 1986.

H. K. Kwan and M. T. Tsim, High Speed 1-D FIR Digital Filtering Architecture using Polynomial Convolution, Proc.ICASSP, vol.87, pp.1863-1866

E. A. Lee, Programmable DSP Architectures: Part I, IEEE ASSP Magazine, pp.4-19, 1988.

T. G. Marshall and J. , Transform methods for developing parallel algorithms for cyclic block signal processing, Proc. Int. Conf. Commun, pp.288-294, 1986.

R. Meyer, Error analysis and comparison of FFT implementation structures, Proceedings of ICASSP89, pp.888-891, 1989.

Z. J. Mou and P. Duhamel, Fast FIR Filtering: Algorithms and Implementations, Signal Processing, pp.377-384, 1987.

Z. J. Mou and P. Duhamel, A unified approach to the fast FIR filtering algorithms, Proc. IEEE ICASSP, pp.1914-1917, 1988.

Z. J. Mou and P. Duhamel, Short length FIR filters and their use in fast non recursive filterings, 1989.

H. J. Nussbaumer, Fast Fourier Transform and Convolution Algorithms, 1981.

M. R. Portnoff, Time-Frequency Représentation of Digital Signais and Systems Based on Short-Time Fourier Analysis, IEEE Trans. on ASSP, vol.28, pp.55-69, 1980.

M. A. Soderstrand, W. K. Jenkins, and G. A. Jullien, Residue Number System Arithmetic: Modem applications in digital signal processing, pp.1-2, 1986.

H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, Realvalued fast Fourier transform algorithms, IEEE Trans. Acoust. Speech, Signal Processing, vol.35, pp.849-863, 1988.

T. G. Stockham, High Speed Convolution and Corrélation, Proc, 1966.

, Spring Joint Comput. Conf., AFIPS, vol.28, pp.229-233, 1966.

P. P. Vaidyanathan and S. K. Mitra, Polyphasé networks, block digital filtering, LPTV Systems and alias-free QMF banks: A unified approach based on pseudocirculants, IEEE Trans. Acoust. Speech, Signal Processing, vol.36, pp.381-391, 1988.

M. Vetterli, Runing FIR and IIR Filtering Using Multirate Filter Banks, IEEE Trans. on ASSP, vol.36, issue.5, pp.730-738, 1988.

B. Widrow, M. E. Hoff, and J. , Adaptive switching circuits, 1960 IRE WESCON Conv. Rec., part, vol.4, pp.96-104

B. Widrow, J. Mccool, and M. Ball, The complex LMS algorithm, Proceedings of IEEE, pp.719-720, 1975.

S. Winograd, Some bilinear forms whose multiplicative complexity dépends on the field of constants, Math. Syst. Theory, vol.10, issue.2, pp.169-180, 1977.

S. Winograd, Arithmetic Complexity of Computation, CBMS-NSF Régional Conf. Séries in Applied Mathematics, SIAM publications, 1980.

S. Anderson, J. Earle, R. Goldschmidt, and D. Powers, The IBM 360 model 91: Floating point exécution unit, IBM J. Res. Develop, vol.ll, 1967.

A. D. Booth, A signed binary multiplication technique, Qt. J. Mech. Appl. Math, vol.4, 1951.

C. S. Burrus, Digital filter structures described by distributed arithmetic, IEEE Trans. Circuits Syst, vol.24, pp.674-680

M. Buttner and H. W. Shusseler, On structures for the implementation of the distributed arithmetic, Nachrichtentech. Z, vol.29, pp.472-477, 1976.

C. F. Chen, Implementing FIR filters with distributed arithmetic, IEEE Trans. ASSP, vol.33, pp.1318-1321, 1985.

A. Croisier, D. J. Esteban, M. E. Levilion, and V. Riso, Digital fil ter for PCM encoded signais, vol.777, p.130, 1973.

P. Duhamel, Z. Mou, and M. Cand, Multiplieur généralisé mettant en oeuvre un filtre numérique, 1988.

M. Hatamian and G. L. Cash, Parallel bit-level pipelined VLSI designs for high speed signal processing, Proceedings of the IEEE, vol.75, pp.1192-1202, 1987.

W. Li and J. Burr, Parallel multiplier accumulator using 4-2 adders

W. Li, J. Burr, and A. Peterson, A fully parallel VLSI implementation of distributed arithmetic, Proceedings of Int. Symp. Circuits and Systems, 1988.

O. L. Macsorley, High speed arithmetic in binary computers, Proc. IRE, vol.49, pp.67-91, 1961.

L. Montperrus, Etude d'une famille d'additionneurs et de multiplieurs, 1988.

W. Li and J. Burr, Parallel multiplier accumulator using 4-2 adders

W. Li, J. Burr, and A. Peterson, A fully parallel VLSI implementation of distributed arithmetic, Proceedings of Int. Symp. Circuits and Systems, 1988.

O. L. Macsorley, High speed arithmetie in binary computers, Proc. IRE, vol.49, pp.67-91, 1961.

L. Montperrus, Etude d'une famille d'additionneurs et de multiplieurs, 1988.

Z. J. Mou and W. Li, Fast arithmetic for computing ±(W±X±Y±Z)A, 1989.

A. Peled and B. Liu, A new hardware realization of digital filters, IEEE Trans. ASSP, vol.22, pp.456-462, 1974.

A. Peled and B. Liu, Digital Signal Processing Theory, Design, and Implementation, 1976.

L. P. Rubinfield, A proof of the modified Booth's algorithm for multiplication, IEEE Trans. on Computers, pp.1014-1015, 1975.

M. Santoro and M. Horowitz, A pipelined 64x64b itérative array multiplier, Also in IEEE J. Solid-State Circuits, vol.24, issue.2, pp.487-493, 1988.

J. Vuillemin, A very fast multiplication algorithm for VLSI implementation, the VLSI Journal INTEGRATION, vol.l, pp.39-52, 1983.
URL : https://hal.archives-ouvertes.fr/inria-00076375

C. S. Wallace, A suggestion for a fast multiplier, IEEE Trans. Electronic Computers, vol.13, pp.14-17, 1964.

W. Waser and M. J. Flynn, Introduction to Arithmetic for Digital Systems Designers, 1982.

D. Zuras and W. H. Mcallister, Balanced delay trees and combinatorial division in VLSI, IEEE J. Solid-State Circuits, vol.21, issue.5, pp.814-819

, Algorithmes de petite longueur On choisit N=2 sans tenir compte de l'ordre du filtre, Nous obtenons: Y0(Z2)+Yi(Z2)z =

=. Ri,

, Et on interpole Q(z) aux points suivants: (ai) = {0,1,°°}. Donc: Rl(0)=H0(z2) R2(0) = Xo(z2)

. Rl, HO(z2) + Hi(z2) R2(l) = Xo(z2) + Xi(Z2)

. Rl, Hi(Z2) R2(-) = X1(z2)

, Calculons ensuite les "restes": Q(0) =Ri(0), p.2

, Q(l) =Ri(l)R2(l)

, R1(oo), p.2

, On obtient les sorties: Y0(Z2)= Q(0) + Z2Q(oo)

, Cet algorithme calcule 2 sorties d'un filtre de l'ordre L à la fois par trois filtres de l'ordre L/2. Le nombre d'opérations est le suivant: 3L/4 multiplication-accumulations (MACs) par sortie 25% de réduction est ainsi obtenu

, Réduction de la complexité

, Par exemple, pour N=L/2, Rl(k) sont des filtres de longueur 2. En variant le rapport entre N et L, nous pouvons dériver tous les intermédiaires entre traitements temporel et fréquentiel, qui représentent différent compromis entre complexité de calcul et structure régulière, Dans le cas où N?L, les multiplications dans le domaine fréquentiel sont devenu des filtrages complexes de longueur L/N

, N = L/2, les algorithmes par FFT courte nécessitent moins d'opérations que ceux par FFT "longue" qui sont utilisés habituellement

A. , Une approche unifiée =? tous les intermédiaires entre traitements temporel et fréquentiel

B. , Revue des algorithmes classiques=? Leurs dérivations, leurs avantages et défauts

C. ;. De-la and . Partie, Nouvelles classes d'algorithmes permettant : -de maintenir l'architecture "MAC", -de réduire le nombre d'opérations, -d'éviter les grands blocs, ARCHITECTURE

A. , Etude de l'arithmétique de base dans le cadre du multiplieur-accumulateur

B. , Nouvelles architectures de filtre par arithmétique distribuée ayant les caractéristiques suivantes: sans ROM; additionneur 'carry-save' comme

C. , Codage pour calculer (X+Y)H dans le filtre RIF symétrique