Главная Помехоустойчивое кодирование



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

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

GF(2 - 1

= 3), GF(2 -

GF(2

5 1 =

31).

GF(2

- 1= 127),

1 1

1 1

1 1

1 1

1 1

1 1

1 1

1 2

1 2

1 2

4 8

2 4

8 16

32 64

1 4

1 4

16 2

4 16

64 2

8 32

1 8

2 16

8 64

4 32

2 16

1 16

8 4

16 2

32 4

64 8

32 8

2 64

16 4

64 32

16 8

4 2

1 = 2047),

= 11

1 1

1 2

1024

1 4

1024

1 8

1024

1 16

1024

1 32

1024

1 64

1024

1 128

8 1024

1 256

1024

1 512

1024

1 1024 512

Риа 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и



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 [51] 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.0202