Отправлено Vadim Kudryavtsev 07 апреля 2005 г. 03:30 В ответ на: ... FFT не сходится ... Вроде по букварю, а часть не сходится .... отправлено Чего-то не вьеду 06 апреля 2005 г. 22:09

Voob4e-to v Matlabe udobnee v matri4nom vide vse delat' - krasivee nagljadnee i dostupnee polu4aetsja.
Tak, FFT mozhno interpretirovat' kak razlozhenie matrizy DFT na slabozapolnennye matrizy (4to sobstvenno i privodit k bystromu algorithmu)

X = [1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0];

%perfom 16 point radix-2 fft (decimation in frequency)

%глобальные переменные
N = 16;

%константы
w0 = exp (-j*2*pi*0/N);
w1 = exp (-j*2*pi*1/N);
w2 = exp (-j*2*pi*2/N);
w3 = exp (-j*2*pi*3/N);
w4 = exp (-j*2*pi*4/N);
w5 = exp (-j*2*pi*5/N);
w6 = exp (-j*2*pi*6/N);
w7 = exp (-j*2*pi*7/N);

%заполняем локальные переменные
x0 = X(1);
x1 = X(2);
x2 = X(3);
x3 = X(4);
x4 = X(5);
x5 = X(6);
x6 = X(7);
x7 = X(8);
x8 = X(9);
x9 = X(10);
x10 = X(11);
x11 = X(12);
x12 = X(13);
x13 = X(14);
x14 = X(15);
x15 = X(16);

%первая стадия FFT (начальные батерфляи)
%суммы
xy0 = x0 + x8;
xy1 = x1 + x9;
xy2 = x2 + x10;
xy3 = x3 + x11;
xy4 = x4 + x12;
xy5 = x5 + x13;
xy6 = x6 + x14;
xy7 = x7 + x15;
%разности
xy8 = - x8 + x0;
xy9 = - x9 + x1;
xy10 = - x10 + x2;
xy11 = - x11 + x3;
xy12 = - x12 + x4;
xy13 = - x13 + x5;
xy14 = - x14 + x6;
xy15 = - x15 + x7;
%уможаем
xy9 = xy9 * w1;
xy10 = xy10 * w2;
xy11 = xy11 * w3;
xy12 = xy12 * w4;
xy13 = xy13 * w5;
xy14 = xy14 * w6;
xy15 = xy15 * w7;

%вторя стадия fft
%суммы
xx0 = xy0 + xy4;
xx1 = xy1 + xy5;
xx2 = xy2 + xy6;
xx3 = xy3 + xy7;
%разности
xx4 = - xy4 + xy0;
xx5 = - xy5 + xy1;
xx6 = - xy6 + xy2;
xx7 = - xy7 + xy3;
%и снова суммы
xx8 = xy8 + xy12;
xx9 = xy9 + xy13;
xx10 = xy10 + xy14;
xx11 = xy11 + xy15;
%и опять разности :))))
xx12 = - xy12 + xy8;
xx13 = - xy13 + xy9;
xx14 = - xy14 + xy10;
xx15 = - xy15 + xy11;
%умножаемся
xx5 = xx5 * w2;
xx6 = xx6 * w4;
xx7 = xx7 * w6;
xx13 = xx13 * w2;
xx14 = xx14 * w4;
xx15 = xx15 * w6;

%третяя стадия вычисления
xxx0 = xx0 + xx2;
xxx1 = xx1 + xx3;
xxx4 = xx4 + xx6;
xxx5 = xx5 + xx7;
xxx8 = xx8 + xx10;
xxx9 = xx9 + xx11;
xxx12 = xx12 + xx14;
xxx13 = xx13 + xx15;

xxx2 = - xx2 + xx0;
xxx3 = - xx3 + xx1;
xxx6 = - xx6 + xx4;
xxx7 = - xx7 + xx5;
xxx10 = - xx10 + xx8;
xxx11 = - xx11 + xx9;
xxx14 = - xx14 + xx12;
xxx15 = - xx15 + xx13;

%умножаемся
xxx3 = xxx3 * w4;
xxx7 = xxx7 * w4;
xxx11 = xxx11 * w4;
xxx15 = xxx15 *w4;

%четвертая стадия вычислений
xxxx0 = xxx0 + xxx1;
xxxx1 = - xxx1 + xxx0;
xxxx2 = xxx2 + xxx3;
xxxx3 = - xxx3 + xxx2;
xxxx4 = xxx4 + xxx5;
xxxx5 = - xxx5 + xxx4;
xxxx6 = xxx6 + xxx7;
xxxx7 = - xxx7 + xxx6;
xxxx8 = xxx8 + xxx9;
xxxx9 = - xxx9 + xxx8;
xxxx10 = xxx10 + xxx11;
xxxx11 = - xxx11 + xxx10;
xxxx12 = xxx12 + xxx13;
xxxx13 = - xxx13 + xxx12;
xxxx14 = xxx14 + xxx15;
xxxx15 = - xxx15 + xxx14;

%ну типа все :)))
%теперь только соберем все в порядок :)
mm(1) = xxxx0;
mm(2) = xxxx8;
mm(3) = xxxx4;
mm(4) = xxxx12;
mm(5) = xxxx2;
mm(6) = xxxx10;
mm(7) = xxxx6;
mm(8) = xxxx14;
mm(9) = xxxx1;
mm(10) = xxxx9;
mm(11) = xxxx5;
mm(12) = xxxx13;
mm(13)= xxxx3;
mm(14) = xxxx11;
mm(15) = xxxx7;
mm(16) = xxxx15;

%сравниваем результаты с fft матлаба
yy = fft (X);

yy
mm

• Ответ: Спасибо, да подзабыл. — Чего-то не вьеду   (07.04.2005 10:51, пустое)