БПФ на конечном поле

[Naked]

Народ, помогите, плиз с реализацией алгоритма быстрого преобразования Фурье (БПФ) на конечном поле. Может кто-нибудь ссылку даст на хорошее описание алгоритма или его реализацию (на любом языке) и просто на Преобразование Фурье, вообще эти два алгоритма сравнить нужно... Заранее спасибо всем за помощь.

[Trotil]

http://sherbetsoft.da.ru/cgi-bin/nph...ml/fourier.pdf

Совсем не уверен, что это вам подойдет, но на всякий случай посмотрите. Это электронный вариант наших лекций по алгоритму БПФ (дискретного) от многих переменных... Правда без соответствующей подготовки понять написанное сложно (потому что фактически без пояснений).

Если это то самле, у меня в лекции записано в два раза больше, начиная от определения и простого примерчика... Могу выслать.

[Naked]

Спасибо, но думаю не совсем это. Дело в том, что преобразование Фурье я вообще не проходил, поэтому разобраться с конспектом довольно сложно, я имел ввиду описание именно этого конкретного алгоритма...

[Trotil]

Ну так в сети очень много материала на тему...
http://alglib.sources.ru/fft/
http://forum.sources.ru/index.php?sh...0&#entry299706
http://forum.vingrad.ru/index.php?showtopic=51486
http://dsp-book.narod.ru/ - раздел "книги"
но вот чтобы так все и сразу, чтобы все было разложено по полочкам, я такого не встретил по ссылкам...

[Naked]

Trotil:
чтобы все было разложено по полочкам

да, а так бы было неплохо, просто свершенно не понимаю, как мне писать это преобразование, ну да ладно, как нибудь сделаю спасибо. А преобразование на конечном поле это не просто взятие по модулю?

[Trotil]

Сообщение от The_naked

А преобразование на конечном поле это не просто взятие по модулю?

Ой, да, когда я давал ссылки, как-то совершенно опустил из виду, что сказано про конечные поля. Знаете, сразу сложно сообразить, какое это накладывает ограничения на алгоритм и как он может модифицироваться при таком условии.

Сообщение от The_naked

А преобразование на конечном поле это не просто взятие по модулю?

Взятие по модулю, то бишь вычеты - это в общем случае кольца, а не поля. В случае p - простого, тогда да, это поле, в противном случае в кольце вычетов существуют делители нуля, и обратного элемента по умножению для делителей нуля там нет...

По поводу БПФ: попробуйте задать вопрос тут: http://narod.yandex.ru/userforum/?owner=dsp-book или на мат.форумах: (например, тут: http://www.mmonline.ru/forum/list.php?f=1). Может быть там что нибудь дельное посоветуют...

[Naked]

Trotil:
Может быть там что нибудь дельное посоветуют...

было бы время осталось 3 дня до сдачи курсовика....

[Trotil]

Тебе, кстати ответили на dsp-book. Можешь выложить сюда тот материал, который тебе обещали выслать?

[Naked]

Да, ответили, спасибо за форум. Хотя вроде это не совсем то, что мне нужно... Оказалось, что нужно использовать алгоритм Кули-Тьюкки немного переделав его под конечные поля... Файл приложил.

[Naked]

Народ, может кому не сложно будет, напишите плиз реализацию алгоритма БПФ на конечном поле (два в кубе 2^3) по алгоритму Кули-Тьюки. В общих чертах знаю, что там разбиваем на две части и получаем две суммы, а выигрыш в скорости получаем, потому что вторая сумма считается один раз... Помогите, если не влом

[Naked]

фух, написал, наконец-то, если кому интересна эта тема, то пишите в ПМ - кину сам алгоритм и программку (в ней, правда баг есть, но он легко исправляется).
P.S. Модераторам: тему можно закрывать