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

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

Быстрые точные целочисленные свертки реализовывать, например.



Математика - она вообще такая, пишется учеными для ученых и инженеров. Если вам это не нравится - смените профессию.

Да, было бы интересно услышать о методах СОК.

если не хотите рассказать, то зачем время своё тратить на указывание, что кому делать.

Я говорю о том что можно написать формулы с кучей мат. знаков и прочим. Описать всё это терминами сложнейшими, которые по сути имеют легкочитаемые синонимы, и гордиться что ты книжный червь и для таких же и пишешь.

А можно писать просто и лаконично с ориентацией на практику. Я всё же склонен различать литературу для инженеров и литературу для учёных. Хотя и граница несколько размыта.

Вот напрмиер, если взять ЦОС. Есть очень хорошие авторы (например Кестер и Стивен В. Смит), которые так и утверждают в предисловии, что книга написаня для практиков и лишена глубоких математических выкладок.
___________________________________________________________________________

Всё же кто нибудь может написать по пунктам какие операции производим над выборкой отсчётов сигнала, когда делаем Фурье с применением остаточных классов?

Не читал.
Скажите, а применения обычного комплексного ДПФ вы именно по этим книгам изучали, значит?

ну и поним в том числе...
а в чём дело?

Да просто Фурье он и есть Фурье. Для тех, кто его понимает. От кольца алгоритмы зависят слабо - соотношения там алгебраические.

Тогда и я за компанию спрошу. Возможно ли использовать для получения свертки вместо преобразования Фурье какое-нибудь другое преобразование типа ... э... меандроподобных , т.е. таких, где базис образован не гармониками, а функциями, могущими принимать не более трех дискретных значений: 0, +1, -1? Если да, то как такое преобразование называется?

Только не отвечайте ТЧП, а конкретно. Например, я знаю преобразование Уолша-Адамара, но оно для получения свертки, кажется, не годится.

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

В Z/3 существет желаемое вами ПФ длиной 2, базисные функции которого принимают значения толлько +1 и -1. С помощью него тривиально вычисляется циклическая свертка длиной 2.

Фурье-то я понимаю. Не совсем понятна идея остаточных классов.
Вот получили выборку например с АЦП, что далбше с ней происходит?

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

Только сейчас эффективнее воспользоваться умножителем в FPGA IMHO.

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

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

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

Вообще говоря, сложность реализации однотактного умножителя пропорциональна квадрату длины перемножаемых слов. Поэтому, вообще говоря, разбив слова длиной N*M бит на N модулей по M бит, можно упростить умножения при вычислении свертки, жрущие основные ресурсы, в N раз. Конечно, в реальности не всё будет так идеально. Да и если в FPGA используются аппаратные умножители, выполняющие любое умножение за такт, то работа в вычетах может наоборот усложнить реализацию, так как потребует только больше умножителей. Не всё коту масленница.

Если мы разбиваем отсчёты на множество мелкоразрядных отсчётов и перемножаем их. Выигрыш может быть от отсутствия переполнений.
Я вижу ускорение только за счёт паралелизма умножений в FPGA. Непонятно как это может усложнить реализацию...((

Для класических мкропроцессоров (и DSP) я вообще не вижу смысла втоаком подходе.

Количество умножений возрастает в N раз, но при этом каждый умножитель оказывается порядка в N^2 раз проще при реализации логикой. Плюс умножения становятся умножениями по модулю. Дальше всё зависит от того, используются ли для реализации умножителей в FPGA DSP блоки?

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

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

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

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

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

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

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

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