В процессе кодирования-декодирования сигналов с использованием конечных полей приходится неоднократно вычислять произведение двух векторов (полиномов), которое принято называть свёрткой.

Свёртка — это базовая операция в ЦОС. Различают линейную, циклическую или в общем случае полевую свёртку .

Линейная (или апериодическая, или ациклическая ) свёртка   y[t]   двух векторов   x[t] и h[t]   определяется в следующей   ∑∏-форме:

Циклическая (или   периодическая, или   круговая, или нелинейная ) свёртка y[t]   двух векторов   x[t] и h[t]   определяется в следующей   ∑∏-форме:

Если векторы   y[t], x[t] и h[t]   рассматривать как полиномы (или многочлены)   Y(z), X(z) и H(z) , а их элементы ("точки") — как коэффициенты при степенях неизвестного z, то в общем случае свёртка в виде произведения полиномов запишется так

Для циклической свёртки полином-модуль

Полином   Q(z)   является делителем   P(z), если можно найти такой полином D(z), что   D(z)·Q(z)=P(z) . Полином P(z) степени T-1 называется неприводимым, если его единственные делители — это полиномы степени 0 или степени T-1. Неприводимые полиномы в полях полиномов являются аналогами простых (неделимых) чисел в кольце обычных целых чисел Z.

Полевая (или по модулю неприводимого полинома, например P(z)=z3+z+1, который порождает поле   GF(23), т.е. с учётом тождеств   z3 ≡ z+1 ,   z4 ≡ z2+z , z5 ≡ z3+z2 ≡ z+1+z2 ) свёртка   y[t]   двух векторов   x[t] и h[t]   определяется в следующей   ∑∏-форме:

Например, для трёхточечных (или трёхкомпонентных Tx=Th=T=3 ) векторов x[t] и h[t]   полиномы степени 3-1=2 запишутся так

Заметим, что при определении линейной и циклической свёрток, в отличие от операций над индексами, на операции умножения и сложения элементов векторов не налагается никаких ограничений; в частности, они могут выполняться по модулю M, где M — простое число. В этом случае компоненты вектора y[k] могут вычисляться над простым полем Галуа GF(M).

Если циклическая свёртка y[t] двух векторов x[t] и h[t] , заданых на абелевой группе H, определена в числовом поле или в кольце (с единицей), то она изоморфна соответствующим дискретным χ-преобразованиям, так что, например, ДП Фурье можно вычислять через циклическую свёртку, а свёртку — через прямое и обратное ДП Фурье:

Линейная свёртка широко применяется при ЦОС над полями комплексных и вещественных чисел. При кодировании сообщений X(z) циклическими кодами каждое закодированное сообщение (или кодовое слово) Y(z) находится как произведение полиномов (свёртка векторов)

NB. Главная задача — научиться правильно вычислять свёртку целочисленных сигналов по быстрым алгоритмам именно в целых числах, не переходя в поле комплексных чисел, но так, чтобы результаты были сравнимы с вычислениями в поле комплексных чисел.

Историю быстрых алгоритмов (БА) обработки сигналов принято отсчитывать с момента, когда в 1965 г. Кули и Тьюки опубликовали свой БА вычисления дискретного преобразования Фурье (БА ДПФ или БПФ) по смешанному основанию (при разложении длины вектора N=N1N2... на любые множители, но на примере основания 2, т.е. для длины N=2v, когда N1=N2=...=2 ), хотя на самом деле эта история началась намного раньше. Просто эта статья появилась в нужный момент и была написана авторитетными специалистами, поэтому она послужила катализатором применения методов ЦОС. Вскоре было замечено, что БПФ-алгоритмы могут служить удобным способом для вычисления свёрток и цифровой фильтрации, так что для них имеется множество приложений, и поэтому работа Кули и Тьюки стала широко известной. Лишь по прошествии несколько лет было осознано, что другой БПФ-алгоритм, сильно отличающийся от алгоритма Кули-Тьюки, был разработан ещё раньше Гудом (1958) и Томасом (1963) для случая разложения длины N=N1N2... на взаимно-простые множители. В своё время публикация БПФ-алгоритма Гуда-Томаса прошла почти незамеченной.

Неблагоприятным следствием популярности БПФ-алгоритма Кули-Тьюки явилось широкое распространение мнения о том, что практично применять ДПФ лишь при длине вектора, равной степени двух, т.е. N=2v . Это привело к тому, что БПФ-алгоритмы стали диктовать параметры применяемых устройств вместо того, чтобы приложения диктовали выбор подходящего алгоритма БПФ. На самом деле хорошие БПФ-алгоритмы существуют практически для любой длины вектора N.

Спустя 10 лет, развивая подход Гуда-Томаса, Виноград (1976) опубликовал свой более эффективный, но и на много более сложный БПФ-алгоритм (БА Винограда для ДПФ или АВПФ), сводящий вычисление ДПФ к вычислению коротких свёрток (с числом умножений в 5 раз меньшим, чем в алгоритме Кули-Тьюки).

Впервые БА для коротких свёрток были построены Агарвалом и Кули (1977) на основе остроумных догадок, а не общего метода. Общий метод построения БА для свёртки описал Виноград (1978), доказав при этом важные теоремы неулучшаемости оценок для числа умножений (т.е оценок мультипликативной сложности БА) для данных из полей комплексных и вещественных чисел. Однако, Агарвал и Кули указали в (1977), основанный на КТО (китайской теореме об остатках), метод разделения задачи вычисления длинных свёрток на подзадачи вычисления коротких свёрток. Их метод в сочетании с алгоритмами Винограда для коротких свёрток, даёт хорошие результаты (в смысле эффективности по числу умножений).

Самая ранняя идея того, что мы называем БА, появилась намного раньше, чем БПФ-алгоритмы. Алгоритм Левинсона для решения систем линейных уравнений с тёплицевыми матрицами был опубликован в 1947 году (т.е. до эры распространения компьютеров). Несмотря на чрезвычайную важность этого алгоритма в обработке сейсмических данных, литература по алгоритму Левинсона многие годы не пересекалась с публикациями по алгоритмам БПФ. В то время исследователи не делали попыток отделить собственно вычислительную процедуру (алгоритм Левинсона) от задачи фильтрации, к решению которой он применялся, или алгоритм Витерби от задачи поиска пути на дереве, или вычислительную процедуру БПФ от задачи вычисления ДПФ.

В статье Гуд пишет: «Одномерные ДПФ могут быть преобразованы в многомерные либо с помощью китайско-руританского метода (Гуд-Томас), либо с помощью "реакционного" метода (Кули-Тьюки), применяемого значительно чаще... Ссылки Кули и Тьюки (1965) на мою статью (1958) были несколько преувеличены, так как создали впечатление, что оба метода почти идентичны. Их метод больше напоминает методы Рунге (1905) и Даниельсона-Ланцоша (1942), работы которых в целом ускользнули от внимания океанографов, специалистов по рентгеновской кристаллографии и многих других исследователей, часто использующих гармонический и спектральный анализ. Указанные авторы писали свои работы до эры ЭВМ и в этом смысле опередили своё время, хотя БПФ был бы полезен уже в течение последних 100 лет.»

Различные вариации БПФ-алгоритма Кули-Тьюки появлялись и ранее во многих обличьях. По существу та же самая идея используется для построения многолучевой плоско-фазированной радиолокационной антенны и известна под названием матрицы Батлера (Butler, 1961).

Гуд пишет: «Иейтс (F.Yates, 1937) придумал простой алгоритм, использующий только сложения и вычитания, для вычисления взаимодействий в 2n-факторном эксперименте. То, что алгоритм Иейтса можно рассматривать как многомерное ДПФ по mod 2 (т.е. как ДП Адамара) было отмечено Гудом (1953). В статье 1958 Гуд показал, что этот алгоритм может быть обобщён применительно к любому многомерному ДПФ и даже к более общим преобразованиям.»

Конечно, хочется упомянуть и о других значительных событиях в истории БА ЦОС, таких как, появление в 1969 БПФ Рейдера для простых N через ЦС, в 1979 появились ПП Нуссбаумера, в 1980 БПФ Капорина и его развитие в 1984 Уэнгом, в 1984 опубликован БПФ Split-Radix, в 1984 и в 1986 — ТА БПФ2 Григоряна и многое чего ещё. После пионерской и не очень понятой в своё время публикации Рейдера (1969), воспринимавшейся современниками скорее как курьёз, не сразу но всё же теоретики в 70-х обратили свои взоры на конечные числовые поля и их место в ЦОС. Поэтому в конце 70-х и в 80-е годы уже было много статей о ТЧП в конечных модулярных полях и кольцах.

Наличие тесной связи между циклической свёрткой (ЦС) и ДПФ, т.е. их изоморфизм, постепенно привели к пониманию того, что ДПФ — это лишь представитель широкого класса дискретных преобразований (ДП), обладающих свойством циклической свёртки (СвЦС). Чтобы ДП вектора длины N обладало СвЦС (или было изоморфно ЦС), необходимо существование корня из 1 степени N и элемента N−1 в поле значений входного вектора и его спектра (т.е. разложения входного вектора по базису ортогональных функций). В самом деле, у ДПФ корнем из 1 порядка N является комплексная экспонета W при входных и выходных данных над полем комплексных чисел (причём N — любое целое).

Тогда теоретико-числовые преобразования (ТЧП) можно рассматривать как аналоги ДПФ, определённые в поле или в кольце целых чисел по модулю некоторого целого числа. Тоже самое и N-точечные полиномиальные преобразования   (ПП), т.е. произведения двух полиномов (многочленов) степени   N-1   по модулю третьего полинома P(z), где z — КОРЕНЬ из 1 в поле коэффициентов при степенях полиномов, — это аналоги ДПФ в кольце полиномов.

Фактически   ТЧП   являются даже частными случаями   ПП , в которых   (b+1)-битовые слова (т.е. элементы поля или кольца) рассматриваются как полиномы. Это особенно очевидно для T=2b=2n+1-точечных ПП, определённых по модулю полинома

Такие ПП вычисляют   T=2b=2n+1-точечную   ЦС, компонентами которой являются слова-полиномы степени   b=2n, т.е. с   (2n+1) коэффициентами. Если 2n+1   входных полиномов — T точек ЦС — определены как   (b+1)=(2n+1)-битовые слова, то ПП (и ЦС) сводится к вычислению   2n+1-точечных   ЧП Ферма по модулю

Например, пусть

P.S. На самом деле при вычислениях по модулю чисел Ферма используются не  (b+1)-битовые  слова (хотя это так по определению), а — b-битовые слова (что реально соответствует размеру арифметического регистра компьютера — 8, 16, 32, 64), в то время как последний   (b+1)-й   бит хранится в отдельном байте. Смотри об этом в разделе "(A-1)-арифметика".

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

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

По-видимому, наиболее интересны те ПП, размерность которых равна степени 2, т.е. N=2v . Эти преобразования имеют структуру, подобную БПФ, и поэтому могут программироваться аналогичным образом. Комбинируя эти ПП с традиционными алгоритмами БПФ для вычисления одномерных свёрток, произведений полиномов и ДПФ, можно получать двумерные алгоритмы, которые основаны на простоте метода БПФ и обеспечивают существенное уменьшение числа операций.

Для вычисления свёрток существует достаточно большой выбор ТЧП. С точки зрения числа арифметических операций наиболее привлекательны ТЧП, которые вычисляются без умножений посредством алгоритма типа БПФ и при заданной длине машинного слова b=2n-бит допускают максимально возможные длины преобразований. В практических задачах этим требованиям полностью удовлетворяют ЧП Ферма и комплексные преобразования по модулю псевдочисел Мерсена.

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

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

Сравнение БПФ и ЧП Ферма обсуждалось в . Было показано, что свёртка длиной от 32 до 2048 отсчётов с помощью ЧП Ферма при длине слова 32 бита вычисляется примерно в 2-4 раза быстрее (на универсальной ЭВМ), чем посредством эффективных программ БПФ. При этом свёртки длиной более 128 вычислялись с помощью 2мЧПФ.

Рассмотрим комплексную свёртку yre + jyim , определённую по модулю Fn

Обычно эту комплексную свёртку вычисляют посредством 4-х вещественных свёрток:

Покажем, что вычисление yre[k] + jyim[k] можно выполнить с помощью только двух вещественных свёрток, воспользовавшись специальным свойством для j=√-1 в некоторых кольцах целых чисел. В кольце целых по модулю числа Ферма   Fn = 2b+1 ,   b — чётное ,   2b ≡ -1 mod Fn , так что   2b/2 ≡ √-1 mod Fn . Тогда комплексную целочисленную свёртку можно вычислить с помощью двух вспомогательных вещественных свёрток   a[k] и b[k]:

NB. Следовательно, этот метод обеспечивает вычисление ЦС при помощи ЧП Ферма с двумя умножениями на один комплексный отсчёт вместо четырёх в обычном случае.

NB. Таким образом, ПП и ТЧП являются как бы ДПФ, которые определены в конечных полях и кольцах, элементы которых соответственно — полиномы или целые. Основное их преимущество по сравнению с ДПФ для комплексных данных состоит в том, что в конечных полях или кольцах можно определить корни из 1, которые имеют простое представление, что позволяет исключить из вычислений операции умножения, а комплексную арифметику заменить на вещественную (для ПП) или на арифметику по модулю целого (для ТЧП).