Главная Помехоустойчивое кодирование
Рис. 3.9* Следы базисных элементов полей GF(2), г = 2 .. . 7 Тг(а2) = Тг(3) = 1(63 = о, б2 = Ь bi = 0. г>о = 0) = 63 = о, что совпадает с результатами соответственно (3.41) и (3.42), (3.43) и (3.44), (3.45) и (3.46). Пусть снова {-ь 2» • • •. г} произвольный базис попя GF(2), тогда хотя бы для одной компоненты Тг(Л.у) = 1. С другой стороны, слеДы TY всех элементов из одного и того же циклокласса, а следовательно, и нормального базиса, принимают одинаковые значения, поэтому для простоты будем говорить: "след циклокласса", "спед нормального базиса". Отсюда вытекает одно из важнейших свойств ~ свойство следа нормального базиса: его след, т. е. след всех компонент нормального базиса, равен 1. Вот почему след особенно просто находится тогда, когда элемент 6 представлен в нормальном базисе. ЛрЙствительно, подставляя в формулу (3.47) Тг(Л.,-) = 1, получаем / = г - 1 Тг(6) = Z = wt(6 j,6 2,...,6o) , / = О (3.49)
Рис. 3.10. Логические выражения для функщй след Тг(6) где 6 - координаты заданного вектора 6 в иормалыом базисе. Ясно, что число единиц в представлении всякого элемента 0 поля GF(2) по любому нормалыюму базису всегда неизменно; причем, если оно четно, то след Тг 0 равен нулю, а если нечетно - то единице. Обращаясь к табл. 3.4 и 3.16 и суммируя по модулю 2 координаты элементов 6 е GF(2), 11 е GF(2), 3 е GF(2), представленных в нормальных базисах, читатель без труда убедится в верности значений следов, ранее найденных для этих элементов другими способами. Два базиса Л.2, ... , -/- и- £ i, £ 2. • • - , поля GF(2*) называются двойственными, если выполняется соотнощение при! =; ; при / Ф}. 10 = 12 = а", 16 = Вьзысканне нормальных базисов. Свойство следов нормальных базисов позволяет в процессе поиска таких базисов отбраковать циклоклассы длины i -г, т. е. наборы вида {jv, N, 7v, . . ., л"} , = 2" если Тг (N) = о, и отнести к множеству нормальных базисов только те из них, для которых Tr(7v) = 1. На рис. 3.11 дан пример испытаний нескольких циклоклассов на нормальный базис для поля GF(2®), я(лс) = + + + + i. Следы циклоклассов с ведущими элементами 6 = а, = а, 22 = равны 1. Поэтому нормальными базисами данного поля являются наборы с этими элементами. Конечно, не обязательно, чтобы элементы поля были представлены в векторной (или полиномиальной) форме. Используя логарифмы Зеха, можно произвести расчеты, оперируя только с модифицированными логарифмами - десятичными О числами из табл. ПЛ. Подобный пример для поля GF(2 ) дан на рис. 3.12, где произведено испытание иа нормальный базис трех циклоклассов. След элемента 6 = о: равен 1, следовательно, соответствующий ему набор является нормальным базисом для рассматриваемого поля. (Как будет показано далее, всего у поля GF(2 ) 16 нормальных базисов.) В табл. 3.14 в последней колонке указаны следы циклоклассов, рассчитанные при задании полей GF(2) примитивными полиномами я(х), перечисленными в табл. 3.1- Из табл. 3-14, в частности, следует, что циклокласс -[б, 11, 21, 41, 81, 161, 66, 131 ] с ведущим элементом 6 = 0: является нормальным базисом для поля GF(2®), я(х) ~ х + х + х + х + 1 (см. также рис. 3.11). Изображения всех элементов данного поля по указанному базису сведены в табл. П. 2 (переход 01 у). Там же эти изображения упорядочены по нарастанию (имеются в виду десятичное и двоичное представления изображений). Переход 7 -»-а используется в § 5.1 при рещеиии квадратных уравнений над полем GF (2®). Число нормальных базисов. Рассмотрим теперь задачу подсчета числа нормальных базисов для поля GF(2) при фиксированном значении его размерности г. Прежде всего напомним, что два конечных поля, даже порожденных с по-моцд>ю разных непроводимых полиномов пу {х) и я2 (х), но имеющих один и тот же порядок (количество элементов), изоморфны, т. е. совпадают с точностью до обозначения элементов. Однако свойство циклокласса *быть нормальным базисом" ие всегда наследуется при изоморфном отображении. Другими словами, если набор [ А i, Л.2, • • » \г} является нормальным базисом при задании поля Галуа с помощью полинома
Рис ЗЛ1. Испытание ряда циклоклассов, состоящих из элементов в векторной :орме, на нормальный базис для поля GF(2®), п(х) - х° + х* + х + х + 1 7Г1(х), то при выборе полинома Я2 (х) этот набор нормальным базисом может и не быть. Поясним сказанное простым примером. Существуют два неприводимых (минимальных) над полем GF (2) полинома степени 3 - см. рис. 3.7: тту (х) = х + + X + 1 н nj{x) = X + X + 1. На рис. 3.13 показаны два способа представления поля GF(2 ) с помощью этих полиномов и найдены следы двух циклоклассов: {l, 3, 5} и (4, 7, б}. В первом случае Тг (2) = О, Тг(4) = 1* поэтому набор 4, 7, 6} длины / = 3 является нормальным базисом поля GF(2 ), пу {х) = + + х + 1, а набор {2, 3, 5} таким базисом не является. Во втором случае, при выборе полинома 1Т2 (х) в качестве порождающего, распределение ролей у этих циклоклассов обратное, так как Тг(2) = 1, а Тг (4) = О- Подчеркнем еще раз, что оба использованных способа задания поля GF(2 ) эквивалентны: соответствие о: устанавливает их изоморфизм. 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.0122 |