Система остаточных классов, для проебразования фурье Опции

[mvm54]

Кто может объяснить на пальцах в чём заключается суть применение вычислений проебразования фурье (для примера) в системе остаточных классов.
В чём минусу и плюсы такого подхода и каковы особенности аппаратной реализации.

Всё что нашёл в интернете по данному вопросу изобилует математическими формулами и написано учёными для учёных...

Поищите эту обзорную статью (там страниц 20). Написана для инженеров. Полной версии у меня сейчас нет.

Прикрепленные файлы

 Blahut.PDF ( 210.65 килобайт ) Кол-во скачиваний: 73

 

[анатолий]

Это уже чтото! Спасибо.

Где здесь распаралеливание применяется (что так актуально для FPGA)?
А вот какие приемущества? Понимаю что прирост производительности.

И есть ли недостатки у такого подхода?

Про СОК много говорили в году, так 1970-м, когда операции экономили.
Главное преимущестов то, что если число представлялось, скажем, 4 остатками, то сумматоры становятся в 4 раза короче
и в 4 раза быстрее.
Все выглядело красиво за исключением преобразования в СОК и обратно, а также проблемы переполнения.
Про СОК резко забыли в 80-е годы, как появились аппаратные умножители и всякая такая экономия стала неактуальной.
Сейчас СОК может поконкурировать в ПЛИС, если надо обрабатывать, скажем, 1000-разрядные целые числа.
Или алгоритмы с тесными обратными связями, кот. не конвейеризуются и требуют точных результатов.
Так что это ну никак не преобразование Фурье.

[Zelepuk]

Про СОК много говорили в году, так 1970-м, когда операции экономили.
Главное преимущестов то, что если число представлялось, скажем, 4 остатками, то сумматоры становятся в 4 раза короче
и в 4 раза быстрее.
Все выглядело красиво за исключением преобразования в СОК и обратно, а также проблемы переполнения.
Про СОК резко забыли в 80-е годы, как появились аппаратные умножители и всякая такая экономия стала неактуальной.
Сейчас СОК может поконкурировать в ПЛИС, если надо обрабатывать, скажем, 1000-разрядные целые числа.
Или алгоритмы с тесными обратными связями, кот. не конвейеризуются и требуют точных результатов.
Так что это ну никак не преобразование Фурье.

вы по моему путаете. СОК и Фурье сами по себе в разных плоскостях понятия...

Я говорил о реализации Фурье методами СОК.
Якобы применяя СОК можно избавиться от проблем переполнения и округления...

[анатолий]

вы по моему путаете. СОК и Фурье сами по себе в разных плоскостях понятия...

Я говорил о реализации Фурье методами СОК.
Якобы применяя СОК можно избавиться от проблем переполнения и округления...

Действительно, в СОК все результаты точные.
Но тогда нужно зарезервировать те самые эквивалентные 1000 разрядов, чтоб не вышло переполнение.

Касательно реализации Фурье и прочей свертки, то имелось в виду, наверное, ТЧП - теоретико-числовые преобразования, примерами коих есть поля Галуа, Мерсенна и т.п. ТОгда все точно - и результат оказывается
без переполнения.

А собственно, чему мешает округление в БПФ?
Если сигнал случайный, то и результаты случайные, как бы точно их не вычислять,
- все упирается в динамический диапазон, и округление тут - в помощь - выбрасывать неверные разряды.
А если точное БПФ - для ускорения умножения 10000- разрядных чисел, то это совсем другой форум.

[ReAl]

Поищите эту обзорную статью (там страниц 20). Написана для инженеров. Полной версии у меня сейчас нет.

В конце 80-ых его книга "Быстрые алгоритмы ЦОС" в из-ве "МИР" выходила. Только там фамилию в виде "Блейхут" транскрибировали.
Наверняка где-то отсканированная есть.