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



Циклокласс {2. 3, 5, 9, 17, 33, 65, 129} Тг(2) = 2 + 3 + 5 + 9+ 17 + 33 + 65 + 129 =

= 2- (1 + 2) + 5* (1 + 5) + 17 J (1 + 17) +65 • (1 + 65) =

= 2 26 + 5 - 101 + 17 - 146 + 65 - 71 =

= (27 + 105) + (162 + 135) = 27 (1 + 79) + 135 (I + 28) = = 27 - 213 + 135.- 105 = 239 + 239 = О

Циклокласс {4, 7, 13, 25, 49, 97, 193, 130} Тг(4) = 4 + 7 + 13 + 25 + 49 + 97 + 193 + 130 =

= 4- (1 +4) + 13- (1 + 13) +49 (1 +49) + 193 • (1 + 193) =

= 4 224 + 13-128 + 49 254 + 193 - 248 =

= (227 + 140) + (47 + 185) = 140- (1 +88) +47- (1 + 139) =

= 140- 168 + 47 6 = 52 + 52 = О

Циклокласс {б, 11, 21, 41, 81, 161, 66, 13l} Тг(6) 6 + U + 21+41 + 81 + 161 + 66 + 131 =

= 6* (1+6) +21- (If 21) + 8i- (1 + 81) + 66- (1 +66) =

= 6 • 139 + 21 - 43 + 81 • 169 + 66 - 163 =

= (144 + 63) + (249 + 228) = 63 - (1 + 82) + 228 • (1 + 22) = = 63 • 161 + 228- 11 = 223 + 238 = 223 - (1 + 16) = = 223 34 = 1

Рис 3.12. Испытание ряда циклоклассов с помощью функций Зеха на нормальней

базис для поля GF(2), я (х) = + + + + 1

Поле GF(2), 7Г (х) = х + X + 1

О 1 1

о О 1 -Тг(4) = 1

Поле GF(2),

я (х) = х + х + 1

*• 1

>--Ik ч:--

0 Тг(2) = 0

1 1 О

О 1 1

Тг(2) = 1

О О О Тг(4) = О

Рис. 3.1 3. Выявление нормальных базисов по следу циклокласса при двух способах

задания поля GF(2 )



Дополнительно обратим внимание читателя на следующее важное обстоятельство. В то время как разбиение элементов (из множества заданной мощности) на циклоклассы осуществляется однозначно, свойства самих циклоклассов (их следы) зависят от выбора неприводимого полинома я (х). Однако вне зависимости от я(х) оказывается важный показатель - количество Jy нормальных базисов. Это объясняется тем, что при любом задании поля GF(2) количества элементов, имеющих след О и 1, одинаковы. (Назовем это явление принципом баланса следов.) Причем если прн изоморфном отображении след какого-либо циклокласса длины / изменится, например, так: О 1, то у другого циклокласса точно такой же длины / изменение следа обратное: 1 -+0. Это наглядно иллюстрирует и рнс. 3.13.

Следовательно, наряду с константой 1. - числом циклоклассов (неприводимых и минимальных полиномов степени г) число нормальных базисов у поля GF(2) - векторного пространства размерности г также является важной константой.

В табл. 3.15 в знаменателях указаны числа для размерностей г = 1 ... 20, а в скобках - следы циклоклассов- Рассмотрим, например, строку /• = 12. Из табл. 3.15 следует, что все элементы попя GF(2) распределяются по циклоклас-сам следующим образом: в двух циклоклассах содержится по о;цному элементу -см. столбец / = 1 (мы знаем, что это элементы О н 1); в ozihom циклоклассе содержится 2 элемента (столбец / = 2), в двух - по 3 (/ = 3) в трех - по 4 (/ = 4), девяти - по 6 (/ = 6) ив 335 - по 12 (столбец I - г). Причем цифры в скобках означают, что след О имеют все циклоклассы длины /, равной 1, 2, 3 и 6, а также один циклокласс длины / = 4 (два других циклокласса этой.длины имеют след 1) • Число 170 в знаменателе - это количество нормальных базисов, т. е. циклоклассов длины / = г = 12 со следом 1. Остальные 335 - 170 = 165 циклоклассов имеют спед 0. Таким образом, имеем баланс:

число следов О

2-1 + 1- 2 + 2- 3 + 1.4 + 9- 6 + 165-12= 2048;

число следов 1 2-4 + 170 - 12 = 2048,

тде, конечно, использована обычная арифметика.

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

Из приведенного расчета ясен один из методов определения величины \ количество циклоклассов длины I = г разбивается на две части так, чтобы обеспечить равенство числа следов О и 1. Предварительно устанавливаются значения следов циклоклассов в очеви;цных случаях. Например, след элемента О (один из циклоклассов длины / = 1) всегаа равен 0. След элемента 1, образующего другой циклокласс длины / = 1, равен 1 при нечетных г и О - при четных г. Вообще след циклокласса всегда равен О, если число l/r четное. Если же l/r - нечетное число, то след соответствующего циклокласса может быть как О, так и 1.

Приведем формулы для расчета количества У/- нормальных базисов при различных значениях г. Предположим, что г - простое нечетное число, тогда количество нормальных базисов определяется соотношением



а для размерностей г, являющихся степенью двойки,

В общем случае Jf, [ 2 : i2r)] = int ] ,

где int - • • - малая Антье-функция.

ГЛАВА ЧЕТВЕРТАЯ

ДИСКРЕТНЫЕ ПРЕОБРАЗОВАНИЯ НАД ПОЛЯМИ ГАЛУА

4.1. ВВЕДЕНИЕ В ТЕ0Й1Ю ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ

Классификация Фурье-подобных преобразований. Прежде чем рассматривать дискретные преобразования над конечными полями, напомним основные положения Фурье-подобных преобразований в поле комплексных чисел С [16, 37, 45].

В основу классификации преобразований целесообразно положить принцип, восходяищй к работе Л. С. Понтрягина [41] по инвариантному преобразованию функций. Суть этого принципа состоит в следующем. На множестве А значений аргументов (в области определения функции) задается бинарная операция, причем такая, что А по этой операции является абелевой группой. На множестве Ф значений функций задается пара таких бинарных операций, что Ф образует поле или в более общем случае - кольцо с единицей. Классификация основных Фурье-подобных преобразований представлена в табл. 4.1.

Пусть непрерывный сигнал v (t) задан на абелевой (аддитивной) группе G вещественных чисел. Тогда, как известно, его можно подвергнуть интегральному преобразованию:

(4.1)

v(0 =JF(co)H*(co,f)c/co,

где V(cjj) - изображение (спектр) сигнала v(t)\ W{cj,t) и Н*(а), ) - ядра прямого и обратного преобразований. При этом предполагается, что интегралы в формулах (4.1) сходятся.

Базисные функции, определяющие ядро преобразования, могут быть выбраны различными способами. В основе Фурье-подобных преоб-



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