Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
1. Для любых элементов а, Ь, принадлежащих множеству, а • b также принадлежит множеству.
2. Выполняется ассоциативный закон, т. е. для любых а, Ь, с, принадлежащих множеству,
а » ф • с) = (а • Ь) • с. (6.3.1)
3. В множестве имеется нейтральный элемент е, такой, что
а • е = е • а — а для всех а, принадлежащих множеству. (6.3.2)
*> Эта совокупность аксиом не является минимальной среди тех, которые могли бы быть использованы (см., например, книгу Биркгофа и Маклейна (1941)), но она наиболее полезна для нас.
8 Зак. 210
225
4. Для любого элемента а из множества существует принадлежащий множеству обратный элемент а~1, удовлетворяющий соотношениям
а • аг1 = а-1 • а = е. (6.3.3)
Абелева (или коммутативная) группа определяется как группа, для которой также выполняется коммутативный закон:
а • 6=6 • а для всех а, Ь, принадлежащих множеству. (6.3.4)
Ниже наибольший интерес будут представлять абелевы группы.
Введенная выше операция • во многом подобна обычному умножению, и нетрудно убедиться, что множество обычных ненулевых действительных чисел с операцией обычного умножения удовлетворяет всем аксиомам группы. С равным успехом, однако, операцией в группе может быть сложение или любая другая произвольным образом введенная операция. Например, целые числа с операцией сложения образуют группу. В этом случае 0 является нейтральным элементом, а обратным элементом для а служит —а. Аналогично, элементы
О и 1 образуют группу, в которой операцией является сложение по модулю 2. Во всех случаях, когда операция в группе обозначается знаком + или 0, условимся обозначать нейтральный элемент знаком
О, а элемент, обратный для элемента а, через —а.
Следующие свойства полезно знать при работе с группами. Пусть е — нейтральный элемент, определяемый соотношением (6.3.2), а — произвольный элемент группы и аг1 — обратный элемент для элемента а [см. (6.3.3)]. Первые два приведенных ниже свойства утверждают единственность элементов ей а-1.
1. Единственным элементом х, для которого а • х = а, является е. (6.3.5)
2. Единственным х, для которого а • х = е, является аг1. (6.3.6)
3. Если а ¦ b — а ¦ с, то b — с. (6.3.7)
4. Уравнение а • х = b имеет единственное решение
х = аг1 • Ь. (6.3.8)
Чтобы проверить свойство 1, умножим обе части равенства а • х = ¦=а на аг1, получим аг1 • а • х = а-1 ¦ а, или е • х = е, или х = е. Свойства 2, 3 и 4 доказываются аналогично.
Подгруппы
Подмножество S элементов группы G, удовлетворяющее аксиомам группы при том же определении операции, что и в группе G, называется подгруппой группы G. В качестве примера рассмотрим множество всех двоичных последовательностей длины N. Это множество с операцией сложения последовательностей по модулю 2 образует группу. Последовательность 0 является нейтральным элементом и каждая последовательность является обратным элементом для самой себя-226
Кодовые слова любого кода с проверкой на четность, имеющего длину блока N, образуют подгруппу этой группы. Чтобы показать это, заметим, что 0 всегда является кодовым словом, обратным элементом для кодового слова служит само это слово, а сумма по модулю 2 любых двух кодовых слов также является кодовым словом.
Порядком группы или подгруппы называется число элементов в группе или подгруппе. Следующая теорема Лагранжа содержит важный результат.
Теорема 6.3.1. (Лагранж.) Порядок группы, если он конечен, кратен порядку каждой подгруппы.
Нам потребуется несколько вспомогательных результатов. Правым смежным классом (левым смежным классом) группы G по подгруппе S называется подмножество sx - a, s2 • а, ..., (а. • slt а • s2, ...) элементов G, где а — произвольный заданный элемент группы G, a slt s2 ... — все элементы S. Непосредственно можно убедиться, что для подгруппы конечного порядка число элементов в смежном классе равно числу элементов в подгруппе, так как если st Ф Sj, то st • а Ф Sj ¦ а. Кроме того, если два правых смежных класса (левых смежных класса) одной и той же подгруппы имеют какой-либо общий элемент, то эти два подмножества совпадают. Чтобы доказать это, предположим, что одно подмножество порождается элементом а, а другое—элементом Ь. Если Si-a — Sj-b, то sj1-si-a=b и b принадлежит смежному классу, порождаемому а. Поэтому для любого sn, принадлежащего S, sn • b = sn ¦ sj1 ¦ st ¦ а и любой элемент смежного класса, порождаемого Ь, принадлежит смежному классу, порождаемому а.
В коде с проверкой на четность, как было показано, для любой фиксированной последовательности у сумма xQy имеет тот же самый синдром, что и кодовое слово х. Поэтому множество последовательностей с данным синдромом является смежным классом по подгруппе, образуемой кодовыми словами. Тогда правило декодирования по максимуму правдоподобия в двоичном симметричном канале может быть переформулировано следующим образом: по заданному у найти шумовую последовательность z, полагая, что она является последовательностью минимального веса в смежном классе, которому принадлежит у.
