Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(ei 0 е2)Я2 Ф 0. Согласно пункту (а), это справедливо тогда и только тогда когда (ej 0 ti)H1 ф 0, что, в свою очередь, выполняется тогда и только тогда, когда ej#! ф Множество шумовых последовательностей {е^ е2......} в таб-
лице декодирования, составленной по Н2, обладает тем свойством, что е; Н2Ф ф ejH2 при i ф j. Как показано выше, эти шумовые последовательности также входят в таблицу декодирования, составленную по Нх,
(в) В линейной алгебре известен результат, утверждающий, что если мощность максимального множества линейно независимых столбцов Н равен г', то подпространство векторов х, для которых хН= О, имеет размерность N— г'. Выберем г’ независимых столбцов матрицы Н и приведем эту матрицу к систематическому виду путем элементарных операций над столбцами. Получится провероч* ная матрица, соответствующая коду c2N~r кодовыми словами и таблицей декодирования (2Г' строками. Из пунктов (а) и (б) следует, что код, соответствующий Нъ состоит из тех же кодовых слов, а его таблица декодирования включает те же шумовые последовательности.
6.12. Последовательность, целиком состоящая из нулей, входит в оба кода. Более того, если Xj и х2 входят в оба кода, то и хх © х2 входит в оба кода. Наконец, х является обратным по сложению элементом для самого себя. Таким образом, пересечение кодовых слов этих двух кодов образует подгруппу каждого кода. Если Нг и Н2 — проверочные матрицы для первоначальных кодов, то х является кодовым словом кода—«пересечения» тогда и только тогда, когда одновременно х#! = О и х#2 — 0- Это выполняется тогда и только тогда, когда
Обычно удобно исключить из Н зависимые столбцы и привести Н к систематическому виду.
6.13. Пусть а и b — произвольные элементы группы, а г — нейтральный элемент. Так как обратным элементом для ab является элемент ab, то имеем ab-a-b = е. Умножение слева на а и справа на b дает а-b = Ь-а; таким образом, группа является абелевой. Теперь заметим, что для любого элемента группы афе пара элементов ей а образует подгруппу, т. е. а-а—е, а-е=а, е-а— а, е-е—е. Теперь возьмем любой элемент (отличный от а и е) и заметим, что b и Ь-а образуют смежный класс по подгруппе {в, а}. Аналогично {в, a, b, b-а} образует новую подгруппу. Продолжим образование новых подгрупп и смежных классов указанным способом. Произведение любых двух элементов смежного класса принадлежит подгруппе, а произведение любого элемента подгруппы на элемент смежного класса является элементом смежного класса. Наконец, так как каждый элемент является обратным для самого себя, то совокупность подгруппы и смежного класса замкнута по групповой операции и по операции образования обратного элемента; поэтому она образует подгруппу с удовоенным числом элементов. Отсюда^следует, что число элементов в каждой новой подгруппе является сте-
хп^п i' ПУСТЬ К .... K-L — столбцы матрицы Нг. Как известно,
xh? = ^ аг, / (х-Ьг)=0;
г= 1
1 < i < N — L.
хН = 0, где
Я = [Я1|Я2].
21 Зак. 210
641
пеныо 2 и в момент,когда вновь образованная под-руппа совпадает с полной группой, число элементов в ней будет равно 2N, где N—некоторое целое число. Теперь предположим, что элемент е соответствует последовательности из N нулей, элемент а соответствует {1, 0, 0, ..., 0}, элемент b соответствует {0,1,0, ..., 0} и пусть каждый последующий новый элемент выбирается таким образом, чтобы создавать новый смежный класс, соответствующий другой двоичной последовательности веса 1. Если в качестве групповой операции ввести сложение последовательностей по модулю 2, то станет ясно, что мы придем к изоморфизму. Этот изоморфизм не единствен и так как в качестве а может быть выбран любой из 2N —- 1 элементов, а в качестве b — любой из 2N — 2 элементов и т. д., то получим
N—1
П (2ы—2‘) i = 0
различных способов установления этого изоморфизма.
6.14.
Элемент 1 а а2 а3 а4 а5
Порядок 1 6 3 2 3 6
Подгруппами являются
(1, а2, а4}, {1, а3}, {1}, {1, а, а2, а3, а4, а5}.
6.15. (а)
+ 0 1 2 3 4 0 1 2 3 4
0 0 1 2 3 4 0 0 0 0 0 0
1 1 '2 3 4 0 1 0 1 2 3 4
2 2 3 4 0 1 2 0 2 4 1 3
3 3 4 0 1 2 3 0 3 1 4 2
4 4 0 1 2 3 4 0 4 3 2 1
(б) Пусть а — элемент GF(p). Число р — 1 делится на мультипликативный порядок а и, следовательно, аР~1 == 1. Теперь заметим, что при любых целых а и Ъ имеем Rp(ab) = RP(RP (a) Rp (b)). Если воспользоваться символом* для обозначения умножения в GF(p), то последнее эквивалентно соотношению
Rp (ab)=Rp (а) * Rp(b). По индукции отсюда следует, что Rp {ap~^l) = Rp (а) * Rp (а) * ... * Rp (а)
р— 1 раз
Поскольку это (р — 1)-я степень некоторого элемента GF(p), то произведение равно 1.
6.16. Простейший путь разложения многочлена над GF(2) состоит в переборе всех возможных делителей, имеющих степень вплоть до половины степени многочлена. Производя сначала деление на D + 1, получаем
