Teoria sobre DSP

Introducción

Hay mucha información gratuita en Internet sobre DSP. Se apuntará en la sección de links

Algoritmos implementados en el DSP C67x

Para hacer la convolución FFT.

FFT

  • DSPF_sp_bitrev_cplx
  • DSPF_sp_cfftr4_dif:

(14*n/4 + 23)*log4(n) + 20
e.g., if n = 256, cycles = 3696.

  • DSPF_sp_cfftr2_dit:

(14*n/4 + 23)*log4(n) + 20
e.g., if n = 256, cycles = 3696.

  • DSPF_sp_fftSPxSP:

cycles = 3 * ceil(log4(N)-1) * N + 21 * ceil(log4(N)-1) + 2*N + 44
e.g., N = 1024, cycles = 14464
e.g., N = 512, cycles = 7296
e.g., N = 256, cycles = 2923
e.g., N = 128, cycles = 1515
e.g., N = 64, cycles = 598

  • DSPF_sp_ifftSPxSP:

cycles = 3 * ceil(log4(N)-1) * N + 21*ceil(log4(N)-1) + 2*N + 44
e.g., N = 1024, cycles = 14464
e.g., N = 512, cycles = 7296
e.g., N = 256, cycles = 2923
e.g., N = 128, cycles = 1515
e.g., N = 64, cycles = 598

  • DSPF_sp_icfft2_dif:

2*n*log2(n) + 37
e.g., IF n = 64, cycles = 805
e.g., IF n = 128, cycles = 1829

El coste para una señal de 256 taps es de 3600 ciclos. 48000 taps por segundo son 188 fragmentos de 256.

El paso al dominio de la frecuencia cuesta: 3600*188 = 677000 ciclos por segundo.

Multiplicaciones

Hay que hacer la multiplicación compleja entre el filtro en el dominio de la frecuencia y la señal, una vez pasada al ominio de la frecuencia.

  • DSPF_sp_vecmul: se puede hacer el producto en el dominio complejo mediante esta técnica.

2*floor((n-1)/2) + 18
e.g., for n = 200, cycles = 216

El producto será aproximadamente el doble de la longitud: 48000 * 2 = 100000 ciclos

Coste de la recombinación de los trozos

NPI

Total

700000 ciclos por filtro siendo optimista.

Partitioned convolution

The central idea found in many of these improvements, is that the impulse response, that is the filter, is partitioned into several smaller parts. When each part is filtered with the input, the results delayed suitably and finally added together, one gets the same result as when processing the whole filter at once. As far as I know, the earliest user of this simple but powerful concept is T.G. Stockham [16], who published his results only one year after the famous Cooley and Tukey FFT paper [5]. The concept can be used to solve several problems. Stockham used it for saving memory, but in later work made in the eighties and early nineties, at the time when realtime DSP became feasible for the first time, it was stated that it can also be used to reduce quantisation erros, reduce I/O-delay, and adapt to optimal FFT lengths of a specific implementation. All these improvements are described by J.S. Soo and K.K. Pang [14], [15]. Other realtime partitioned convolution pioneers are B.D. Kulp [17], P.C.W. Sommen [12], [13] and J.M.P. Borrallo and M. G. Otero [4]. Their work is a good place to start reading for the one interested in getting a more detailed description of partitioned convolution. The convolution algorithm in BruteFIR is conceptually exactly the same as the one found in these papers.

Preguntas a contestar

Salvo que se diga otra cosa, el contenido de esta obra está bajo la licencia: Creative Commons Reconocimiento NoComercial CompartirIgual 2.5 España.