сз = 2 Ь1 + Д1 2 ; 4=22,

где учтено, что=0 при к<Оц при к>п- I = 2. Представим циклическую свертку в 2П-форме:

/ = л - 1

где скобки означают операции, выполняемые по модулю п над индексами компонент вектора а; кроме того, учтено, что / - и + 1 = / + + 1 (mod п). Например, для рис. 4.7, б имеем и = 3 и

со =0 Ьо + j bi -Ь я( 2 2 = до Ьо + 2 bi + ffi Ьг = со + сз; 1 =я1 Ьо + aobi -Ь 2 = flfibo + aobi + 22 = ci + с4;

с2 =20 + ibi + 02 = 2,

где отрицательные индексы у компоненты вектора а приведены по модулю 3,T.e.a f=a f,k=lj2.

Заметим, что в определениях и линейной (4.10), и циклической (4.11) сверток, в отличие от операций над индексами, на операции умножения и сложения элементов не налагается никаких ограничений; в частности, они могут выполняться по модулю р, где р - простое число, в этом случае компоненты вектора с могут вычисляться над простым полем GF(p).

Линейная свертка широко применяется при цифровой обработке сигналов над полями комплексных и вещественных чисел. При кодировании сообщений d(x) циклическими кодами каждое кодовое слово с(х) находится как произведение с(х) = g(x)d(x), которому соответствует циклическая свертка(4.И), где g{x) - порождающий полином кода; циклическую свертку можно вычислить и как линейную, а затем привести по модулюх"-1 [37].

Полевую свертку также можно представить в 2П-форме; для примера свертки трехкомпонентных векторов (рис. 4.7, в) имеем

со = со + сз; cl = cl + сз -Ь с4; с = сг + с4.

На основе полевой свертки синтезируются быстрые схемы для вычисления произведений векторов над полем GF(2), не требующие логарифмирования - антилогарифмирования (ни обычного, ни модифицированного по Зеху) - см. § 3.3. Примеры вычисления сверток даны на рис. 4.8.

Вычислить свертку можно не только прямым, столбиковым "школьным", способом (разумеется, с учетом необходимых переносов), но и с помощью дискретных преобразований. В свою очередь, быстрый

Риа 4.8. Примеры вычисления сверток, приведенных на рис. 4.7, для векторов

(ПО) и (101)

алгоритм ДПФ длины р (р

простое число) основан на переходе к цик-

- 1. Эти приемы вычисления цикли-

1, т. е. со = \/Т

лическои свертке векторов длины р-ческих сверток и преобразований над конечными полями будут рассмотрены в § 4.3.

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

в полях вещественных и рациональных чисел (-1) = -1, п - 2, следовательно, в этих полях существует ДПФ лишь для векторов длины п - 2. Такое короткое ДПФ не имеет особого практического значения; вот, кстати, почему вычисление сверток для последовательностей вещественных чисел приходится переносить в комплексную область. Для поля Галуа ДПФ над векторами длины п существует тогда и только тогда, когда п является делителем числа зв -q-\, включая само это число, где q - порядок данного поля [10, 37]. (Указанное ограничение для полей Галуа вытекает из теоремы Ферма.) Однако всегда можно перейти к полю большего порядка i, такого, что и I (1 - 1).

в литературе по помехоустойчивому кодированию, например в монографии [36], дискретное преобразование Фурье над полем Галуа называется преобразованием (многочленом) Мэттсона - Соломона. В дальнейшем это преобразование будем называть преобразованием Фурье -Мэттсона- Соломона, или ФМС-преобразованием.

Преобразование ФМС определяется аналогично ДПФ - с помощью матрицы Ф = [со ], т. е.

(4.12)

где для наглядности строки и столбцы пронумерованы переменными / и /, т. е. / и / - целые неотрицательные числа с обычной операцией их

- ядро ДПФ; со - первообразный корень уравнения

1, т. е. о? = \/l и п - наименьшее число, обладающее таким свой-

1. Итак, в то время как ДПФ в комплексной области

умножения; сЛ

ством, что со

существует для произвольной длины п (в этой области \П~имеет смысл

при любых п), ДПФ над конечным полем GF{q = р/* ), т. е. ФМС-преобра-зование может быть определено лишь для таких длин п, которые делят

число 9 - 1, так как s/YE GF(q) только при п \ (q - 1), где ( ~ 1) - порядок мультипликативной группы поля GF(cf). Например, над полем GF(2*) возможны ФМС-преобразования лишь длины 3, 5 и 15. Далее рассматриваются преобразования над полями характеристики 2.

Как уже отмечалось, в конечном поле циклическая свертка может быть вычислена с помощью ФМС-преобразования, Необходимость вычисления таких сверток появляется, например, при кодировании сообщений с помощью циклических кодов. Подробнее ФМС-преобразование и его свойства рассмотрены в § 4.3, а кодирование - декодирование на основе этого преобразования - в § 6.3.

Возникает естественный вопрос: существует ли дискретное преобразование для вычисления полевой свертки? Ответ положителен.

Введем еще один тип дискретного преобразования для чего по-

строим матрицы [а ] размера w X п с разным расположением (пуме рацией) столбцов:

6 - 1610