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

Вернемся к табл. 4.1. Преобразование Лапласа-Галуа, предложенное Цыпкиными Фараджевым [48], используется при исследовании цифровых автоматов, состояния которых описьгоаются сигналами, заданными в областях целых чисел (в дискретные моменты времени)

Риа 4.6. Примеры ядер теоретико-числовых преобразований: а - над полями Галуа;

б - над модулярным кольцом (2047 - не простое число)

и принимающими значения в конечном поле. Дискретное преобразование Фурье над полями Галуа и кольцами (с единицами) принято называть теоретико-числовыми (ТЧП). Преобразование Фурье-Мэттсона-Соломона играет особую роль в теории помехоустойчивого кодирования и будет рассмотрено далее.

Теоретико-числовые преобразования МерсеннаиФерма выполняются в конечных полях и кольцах, порядок которых является соответственно числом Meрсенна 2-1, где р- простое число, или числом Ферма 2 + 1, где q = 2, п - целое число. В полях и кольцах, основанных на числах Мерсенна и Ферма, сравнительно просто выполняется операция приведения по модулю. Так, приведение по модулю чисел Мерсенна эквивалентно циклическому сдвигу (по сути - это арифметика в обратном двоичном коде) [16, 37]. Еще одно достоинство использования подобных ТЧП - возможность формирования матрицы преобразования только из чисел, являющихся степенью двойки. Ряд подобных матриц пред-

ставлен на рис. 4.6. (Правда при реализации быстрых алгоритмов, основанных на факторизации матриц, картина меняется: в матрицах преобразования появляются числа, не представимые степенью двойки.) В практике кодирования телеинформации с контролем ошибок ТЧП Мерсенна, Ферма, так же как и Уолша-Галуа и т.п., широкого распространения не получили.

4.2. ВВЕДЕНИЕ В ДИСКРЕТНЫЕ ПРЕОБРАЗОВАНИЯ

НАД полями ГАЛУА

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

На рис. 4.7 представлены три вида сверток - умножений трехразрядных Векторов, соответствующих полиномам третьей степени я() = = агХ + ffj д: + До и Ъ{х) =: ЪгХ + bi х + Ьо с различными методами учета разрядов переполнения. На рис. 4.7, а эти разряды остаются без изменения; подобная свертка называется линейной. Ш рис. 4.1,6 разряды переполнения добавляются к младшим разрядам: первый разряд переполнения - к младшему, крайнему справа разряду, второй разряд переполнения - ко второму справа разряду и т. д. Таким образом, осуществляется циклический сдвиг разрядов переполнения и последующее их суммирование с основными разрядами; данная свертка называется циклической.

На рис. 4.7, в разряды переполнения также добавляются к основным, но не по циклическому, а по какому-нибудь более сложному правилу, в рассматриваемом примере - по модулю неприводимого полинома 7г(х) = х + л: + 1, порождающему соответствующее поле

ab (line)

(fl2 oi qq) - a

(2 1 bo) - b

гЬц Oibo floo

fl21 ll OQbi

агЬг ах2 оЬг

= ( c4 сз c2 ci

c4 =fl2*2;

c3 = fl2*l +«12;

C2 =fl2*0 +«1*1 +flo*2;

ci = flio + flo*i;

co = floo-

Co )

6) c4 c3 c2 ci co

c4 c3

(cycle)

= (2 1 co)

cJ = Ci +c4; co = co + c3.

) c4 c2 ci co

с3 c3

c4 c4 i *

ab (gf)

. " " ft

= (c2 cj co)

c2 = c2 +c4;

= ci +c3 +c4; co = co + c3.

рис. 4.7. три типа сверток: а - линейная; б - циклическая; в - полевая для поля

gf(2) с порождающим полиномом 7г(д:) = д: +д: + 1

тождеств

= + д: + 1. Этот последний тип умножения назовем полевой сверткой векторов (полиномов).

Представление сверток в БП-форме Назовем для краткости сумму произведений компонент пары свертываемых векторов ЕП-формой. Линейная свертка, определяемая как произведение векторов а -

- (л-х • • • ао)у Ъ - (b„ j Ь„ 2 • • • 1о) длины и или как произведение соответствующих им полиномов, может быть представлена

в следующей ЕП-форме:

/ = я - 1

а. bn + а.

I -I

bi + .

(4.10)

где z = О, 1, ..., и- 1, а операции над индексами - обычные операции сложения и вычитания целых чисел.

Например, для трехкомпонентных векторов (рис. 4.7, а) имеем

и=3и