Faltungsalgorithmen

Die Einzel-Addition der jeweils verschobenen (und mit dem Gewichtswert multiplizierten) Kernfunktion wird im File 'convloop.m' demonstriert.

% Beispieldaten zu Faltung in Einzelschritten
va = [ 1 2 3 4  ]
vb = [ 1 2 3 2 1]
% Eigentliche Berechnung zirkulaere Faltung
lconv = length(va) + length(vb) -1;
vbl = [ vb , zeros(1,lconv-length(vb)) ];
vres = va(1) * vbl;
for k=2:length(va)
  vres = vres + va(k)*shrg(vbl,k-1)
end

Dazu wird die Funktion 'shrg.m' benötigt.

% vback = shrg(vin,nsh) - Rechts-Verschiebung zirkulaer
function vback = shrg(vin,nsh)
  ntot = length(vin);
  nlast = ntot -nsh;
  vback = [ vin(nlast+1:ntot) , vin(1:nlast) ];

Die schrittweise Addition, welche eine Faltung in ihrer Entstehung demonstriert, wird im File 'convoldemo.m' benötigt.

function c = convoldemo(a,b)
%  a,b Eingangs-Zahlenfolgen zur Faltung  convoldemo(a,b)
%    mit graphischer Demonstration
n1 = length(a);  n2 = length(b); % Laengen
nr = n1 + n2 - 1;
% plot arrays haben zuaetzliche Randwerte 0
cpl = zeros(1,nr+2);  cpl0 = cpl;
cplp = cpl;  cplo = cpl;  xpl = 0:(nr+1);
% Ordinaten-maximum
cmx = max(conv(a,b));
% Schleife
for k = 1:n1
cplp = cpl0-0.1;
  for l = 1:n2
    cpl(k+l-1+1) = cpl(k+l-1+1) + a(k)*b(l);
    cplp(k+l-1+1) = cplp(k+l-1+1) + a(k)*b(l);
  end
   c=  cpl(2:nr+1)
% plot Teilschritt
   plot(xpl,cpl0,'k');    hold on;  axis([0 nr+1 -0.5 cmx+0.5])
   plot(xpl, cplp,'r' );  plot(xpl, cplo,'g' )
   plot(xpl, cpl,'b' );  hold off; cplo = cpl;
  pause
end
%    c = cpl(2:nr+1);

Die beiden M-Files 'fftfaltgew.m' und 'fftfaltzyk.m' benutzen beide den Faltungssatz, also den für große Vektorlängen lohnenden ,,Umweg`` über die schnelle Fouriertransformation.

function c = fftfaltgew(a,b)
% c = fftfaltgew(a,b) gewoehnliche Faltung nach Faltungssatz
%  mit geeignetem Anhaengen von Nullen (zero padding)
n1 = length(a) ; n2 = length(b);  al = a; bl = b; nr = n1+n2-1;
% Nullen auffuellen bis zu Reaultatlaenge der gewoehnlichen Faltung
  al = [al zeros(1,nr-n1)];  
  bl = [bl zeros(1,nr-n2)];
c = real(ifft(fft(al).*fft(bl)));

function c = fftfaltzirk(a,b)
% c = fftfaltzirk(a,b) zirkulaere Faltung nach Faltungssatz
n1 = length(a) ; n2 = length(b);  al = a; bl = b;
if n1 < n2  % Laengen-Test mit Nullen nachfuellen
  al = [al zeros(1,n2-n1)];   n1 = n2;
elseif n1 > n2
  bl = [bl zeros(1,n1-n2)];
end
c = real(ifft(fft(al).*fft(bl)));