Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
т <1(х) /44 (х) - 1 ¦ |- х4 -4 х6 -4 х7 -4 х
s
Этот код является линейным (15,7)-кодом с проверочным много'
членом
h (х) -¦ ( х
ЧЛБ
I) /4 4)
1
х
л
х8 + ХЕ
В качестве базиса этого (15,7)-БЧХ-гсода возьмем векторы, ответствуют не
многочленам
со
4
'\w'
44 Щ 44 x2g 4Е xng (х), tfg (х), xbg (х), хе g (х)
аким образом, получаем порождающую матрицу
I 0 0 0 1 0 1 1 1 0 0 0 0
0 0
0 1 0 0 0 1 0 1 1 I 0 0 0
0 0
0 0 I 0 0 0 1 0 1 1 I 0 0
0 0
0 0 0 1 0 0 0 1 0 i 1 1 0
0 0
0 0 0 0 I 0 0 0 I 0 1 1 1
0 0
0 0 0 0 0 1 0 0 0 1 0 1 I
I 0
0 0 0 0 0 0 1 0 0 0 1 0 I
1 1
?едположим теперь, что полученное слово v имеет
10 0 10 0 1 1 0 0 0 0 10 0;
тогда соответствующий многочлен v (х) имеет вид
I? (х)
1
i... \*** ,-X-
X
.J-.. у А* з А
№
*
Л 2
• 4 -.2 г l
¦¦^ответствии с шагом 1 декодирующего алгоритма найдем его
лии соотношениями (9.6):
воспользовавшись при этом для упрощения вычисле-
Si - е (а) ~ v (а) • 1
616
Гл. 9. Приложения конечных полей
а'
S:i - е (а3) : v (а3)
5, ^:;т с (а4) :: v (aJ) ~ 1
Максимальная невырожденная система линейных уравнений носительио
неизвестных т( (шаг 2} нмеет в этом случае вид
о:
S2x,
-ГН
5." т.
Ч
>
Л- ;др
ИЛИ
4
0С4Т
т, -г т* " а",
.1 (Ц *
1 V, 1
Очевидно, что матрица этой системы невырожденна. Следов:; тельно, число
встретившихся ошибок должно равняться 2, т. г 2. Решая эту систему
уравнений, получаем т* - 1, и ~
Подставляя эти значения в s (х) и считая, что г0 что
1, получав!
S (х)
1.
-г X
ах
Так как корнн этого многочлена лежат в IFte, то iff1 а6, цГ1 т а8 и,
следовательно, цv а\ г\2 -¦ а4 Отсюда мы делаем вт вод, что ошибки
появились в 8-й и 10-й компонентах переданной слова. Исправив эти ошибки
в полученном многочлене, пол уча-..;.
Ш(х) - Л (х) - е (Х) (1 -{" ¦*
'"А
.fl
X7 ¦ j X12) {X1 4" х*!)
1 ! - х3 4- хв
X
,9
X
12
Ч
s^s!:
Соответствующее кодовое олово --
10 0 1 0 0 10 0 10 0 10 0.
Исходную информацию (до кодирования) можно получить с п мощью деления
исправленного многочлена (т. е. переданной кодового многочлена w (х)) на
многочлену (х). В результате пол? чаем
ю [X) П1
ч."
л
I
X
Л
X
я
что соответствует передаваемому сообщению 100 3 10 0.
3. Конечные геометрии
¦М
г параграф посвящен применению теории конечных П лен в геометрии. В
известном смысле теорию кодирования моЩ также рассматривать и как раздел
геометрии, и как раздел к бинпторнки, так как в иен изучаются вопросы
упаковки шар| в метрическом пространстве конечной мощности, как правилу в
конечномерном векторном пространстве над полем. р5.
Проективная плоскость состоит ид множества точек и множест|
rt
§ 3, Конечные геометрии 6.17
прямых, которые связаны между собой отношением инцидентности, Эго
отношение позволяет для каждой точки и каждой прямой установить, лежит
данная точка на данной прямой или нет. Для 'того чтобы дать строгое
определение, необходимо сформулировать несколько аксиом.
9.53. Определение- Проективная, плоскость определяется как множество
элементов, называемых точками, вместе с выделенными подмтожествами этого
множества, называемыми прямыми, и от 1 > о ш е 1 (и е м /, н а з ываемьш
отношен нем ин ц идея т н ост и между точками и прямыми и удовлетворяющим
следующим условиям: (!) каждая пара различных прямых инцидентна
единственной точке (т. е. для каждой пары различных прямых существует
единственная точка, лежащая на обеих прямых и называемая их
пересечением);
(и) каждая пара различных точек инцидентна единственной прямой (т. с.
для каждой пары различных точек существует единственная прямая,
содержащая обе эти точки, иначе - прямая, проходящая через эти точки);
ли) существуют четыре точки, такие, что никакие три из них не инцидентны
одной и той же прямой (т. е, существуют четыре точки, такие, что никакие
три из них не лежат и а одной прямой).
Отсюда следует, что каждая прямая содержит по меньшей мере 3 точки и что
через каждую точку проходят по меньшей мерс 3 прямые. Если множество
точек проективной плоскости конечно, то мы будем говорить о конечной
проективной плоскости. Из трех приведенных выше аксиом нетрудно вывести,
что условие (Hi) выполняется и в случае, если в нем поменять местами
попятим "точках и "прямая". Тем самым устанавливается принцип
двойственности между точками и прямыми, из которого в свою очередь молено
получить следующий результат:
X.
i
454. Теорема. Пусть II конечная проективная плоскость.
'I хорд
П) существует целое число т Зд- 2, такое, что каждая точка [прямая]
плоскости П инцидентна в точности т -j- 1 прямым Чяичкам) плоскости П;
(И) II содержит ровно тг - т I точек {прямых).
55. Пример. Простейшая конечная проективная плоскость Случается при т 2,
в иен через каждую точку проходят ровно 3 прямые и каждая прямая содержит
ровно 3 точки. Всего же плоекость содержит 7 точек и 7 прямых. Такая
проективная Плоскость называется плоскостью Фана; [[а рис. 9.2 приводится
^ схематическое изображение. Плоскость содержит точки А, О, Е, F и а и
