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



(п-1)

1 2

п +1

. of

. of

. of

п + 1

. of

2 (« - 1)

(и-1) •

. . 2

- <

• • * *

а"

.а"

1 о

of of

а of

of of

n - 1

Из построения ясно, что Г и Т - соответственно ганкелева и теплицева матрицы. Поэтому дискретное преобразование с помощью подобных матриц назовем преобразованием Ганкеля-Теплица, или ГТ-п рео бразов анием.

Вспомним, что ФМС-преобразование заданного порядка п существует не во всяком поле Галуа, т. е. что ядро со этого преобразования должно иметь порядок п в поле GF{q), где п кратно 9 - 1. Так вот ГТ-преобразование существует в любом поле Галуа, а ядро а этого преобразования суть примитивный элемент поля. Нас в первую очередь интересуют поля характертстики 2, для которых о: = 2 - всегда п(м-митивный элемент. В этом случае

(/2 + 1) (/2+2)

4 «

(2/2- 1)

(/2+1)

(2/2-1)

(/2 + 2) (/2+1)

(4.13)

где элементы поля GF(2) представлены своими модифицированными логарифмами - десятичными номерами TV.

Как будет показано далее, для вычисления циклических сверток матрицы (4.13) заменяются следующими:



4 «

(«с 1)

* 4

{п~Л) (/2-1).

(/2-1)

. 2 1 . 3 2

(/2- 1) (/2- 2) ... 1 /2.

(4.14)

Преобразование на основе циркулянтных матриц (4.14) будем называть циркулянтным ГТ-преобразованием, или (ГТ)ц-преобразова-нием.

Если необходимо подчеркнуть, какая именно используется матрица - Г или Т в (4.13), Гц или Тц в (4.14), то уточним: Г (Гц)-преоб-разование или Т (Тц)-преобразование. Подробнее свойства ГТ-преобра-зования и его разновидностей рассмотрены в § 4.4-

4.3. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ - МЭТТСОНА - СОЛОМОНА

Прямое и обратное ФМС-преобразование. Согласно § 4.2, /2-точечное ФМС-преобразование над конечным полем для вектора v = (р 2- • • v\vq) длины/2 задается выражением

I = п - I

2 Л-, gfiq=p), /2(-1) / = о

(4.15)

или в развернутом виде

{n-l)k

(4.16)

где = 0, 1, ...,/2- 1; co - ядро преобразования - элемент порядкап в поле GF(p), т. е. порождающий элемент мультипликативной цикли-

1 и /2 - минимальное положитель-

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

Обратное ФМС-преобразование над конечным полем GF() для вектора Vj = (J, i Цг-2 • • • о) определяется соотношением

к = п - 1

- 2 cJ~vk, g¥{q=p), n\(q-l) к = о

(4.17)

или в развернутом виде

(4.18)

где г

О, 1, . . . , /2-1

то же ядро, что и в формулах (4.15)

ц (4.16), а /2 в знаменателе дроби ifn берется по модулю р, т. е. рассматривается как элемент поля GF (р).



можно

вить так:

гдеФ~* = [со"" ]: /2 матрица, обратная матрице Ф (4.12).

Порядки Wj элементов конечного поля с характеристикой 2 являются нечетными числами (см., например, табл. 3.14). Поэтому над полями GF(2), которые нас интересуют больше всего, выполняется сравнение 1 2= 1 (mod 2).

Отметим интересное свойство ФМС-преобразования: для любого поля справедливо равенство

откуда для поля GF (2 ) следует

(Уо 11 . ;-1)Ф" = (Уо Vn-i-- ОФ- (4.19)

можно

находить

с помощью матрицы Ф, но для вектора (входного либо выходного).

видоизмененного согласно перестановке

р , Xq Xi Х2 ... Х 2 Х 1

Xq j Х 2 * * * •2 .l

(4.2G)

Преобразование ФМС может рассматриваться как важный частный

,

случай интерполяции Лагранжа [37] над циклической группой порядка п. Один из основных этапов декодирования помехоустойчивого крра

над конечньхм полем состоит в решении степенного уравнения (урав-нения локаторов). Оказывается, для этой Дели также может быть использовано ФМС-преобразование. Действительно, пусть векторы

= (vo,vi,...,v ) и У{Уо.Ух.-.Уп-1У

связаны ФМС-преобразованием (прямым и обратным). Тогда эти векторы можно сопоставить с полиномами

«- 1 . п- \ ,

v{x)= 2 v.x и V{x)= 2 V.x\

i = о i = о

Для того чтобы элемент поля ot был корнем полинома v(jc), необходимо и достаточно, чтобы коэффициент Vj полинома был равен нулю; наоборот, элемент будет корнем полинома У{х), если и только если

Например, зададимся полиномом v{x) = (х + 1) (jc + 2) {х + 5) (д: + + 6) = jc* + 2х + 1х + 7д: + 4надполемСР(9 = 2),я(д:) =д: 1, табл. 3.4. Умножив вектор v = {vq, pj, 13. Js, б) = (4, 7, 7, 2, 1, 164



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.0134