Ответ: Вот, пожалуйста. («Телесистемы»: Конференция «Микроконтроллеры и их применение»)

---

Отправлено ВН 04 июля 2002 г. 15:13 В ответ на: Кидай исходник или алгоритм. Ради смеха можно попробовать. отправлено Сергей Борщ 04 июля 2002 г. 13:35

16 точечное fft с прореживанием по времени, по основанию 2.
Алгоритм с замещением и с прямым порядком данных на входе.
Т.е. результат кладется туда же, где были исходные данные, но данные результата расположены в двоично-инверсном порядке.
Исходные данные в общем случае комплексные. Лежат в массиве DAT.
Четные элементы массива- реальная часть, нечетные-мнимая.
У результата так же.
Косинусы, синусы насчитаны заранее и лежат в массивах COSARR и SINARR, соответственно. В каждом по 16-точечному периоду. Вообще-то достаточно было бы и одного массива, 2 для упрощения.
Попытался написать как можно более понятно.
int DAT[32];
int COSARR[16];
int SINARR[16];
int NSUBSTAG=1;
int NBATTER=8;
union lonint
{
long l;
int i[2];
};
int bitrev8(int i)
{
int j=((i&1)<<2) | (i&2) | ((i&4)>>2);
return j;
}
void fft(void)
{
int RA,IA,RB,IB,RW,IW;
int n,m,l,k,j,i;
long RE,IM;
union lonint LI;
for(n=0;n<4;n++)
{
for(m=0;m {
k=bitrev8(m);
RW=COSARR[k];
IW=SINARR[k];
for(l=0;l {
k=2*m*NBATTER+l;
RA=DAT[2*k];
IA=DAT[2*k+1];
RB=DAT[2*k+2*NB];
IB=DAT[2*k+2*NB+1];
RE=(long)RB*(long)RW+(long)IB*(long)IW;
IM=(long)IB*(long)RW-(long)RB*(long)IW;
LI.l=(long)RA+RE;
DAT[2*k]=LI.i[1];
LI.l=(long)IA+IM;
DAT[2*k+1]=LI.i[1];
LI.l=(long)RA-RE;
DAT[2*k+2*NB]=LI.i[1];
LI.l=(long)IA-IM;
DAT[2*k+2*NB+1]=LI.i[1];
}
}
NBATTER>>=1;
NSUBSTAG<<=1;
}
}
В вычислениях RE и IM я, возможно, не совсем корректно использовал приведение типов. Но написал так для того, чтобы показать, что результат операции a*c+b*d, например, должен быть 32-х разрядным при 16-ти разрядных a,b,c,d.
union введен только для того, чтобы показать, что сохраняются только старшие 16 разрядов 32-х разрядного результата. На C для 430 никогда не писал, не знаю как там long хранится, так что не судите строго.
Вместо функции bitrev8 можете использовать таблицу. Ввел ее для компактности.
Теперь про синусы, косинусы - для исключения переполнений и простоты можно их отнормировать к 16384. Обычно и с переполнениями и с "недополнениями" в fft борьба по другому, используется блочная плавающая запятая, например. Но это усложняет немного реализацию, потому и не ввел ее.
При любом n и m=0 RW=1(т.е. 16384), IW=0. Можно это использовать.

• Ответ: Куда -то m++ во 2-м for'е делся. И l++ в 3-м. — ВН   (04.07.2002 15:37, пустое)