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

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

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



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

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

Сообщение отредактировал TigerSHARC - Jan 12 2011, 06:00

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

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

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

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

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

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

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

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

Тогда и я за компанию спрошу. Возможно ли использовать для получения свертки вместо преобразования Фурье какое-нибудь другое преобразование типа ... э... меандроподобных , т.е. таких, где базис образован не гармониками, а функциями, могущими принимать не более трех дискретных значений: 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 блоки?