Глава 9. ПОЛНЫЙ ПРОИЗВОЛЬНЫЙ КОД

9.1. Алгебраические свойства полного кода

Как было определено в класс или полный код состоит из всех последовательностей, отличающихся хотя бы одним элементом. Объем класса согласно (8.2) равен где основание манипуляции, число элементов. В частном случае, когда класс вырождается в алфавит объема

Исследование корреляционных свойств класса полного кода имеет большое значение для изучения свойств систем сигналов, являющихся подклассами данного класса. Оно существенно упрощается, если учитывать алгебраические свойства полного кода, который является группой. Перейдем к рассмотрению этого вопроса.

Группа и ее свойство. Допустим, что имеем некоторое множество объектов или элементов. Обозначим объекты через Определим на множестве бинарную операцию — однозначную функцию

двух переменных. Обычно операцию обозначают или как умножение или как сложение а

Группой называется (см., например, [92, 121]) множество, на котором определена бинарная операция и выполняются следующие аксиомы.

1. Замкнутость. Операция может быть применена к любым двум элементам группы, в результате чего получается элемент группы.

2. Ассоциативность. Для любых трех элементов группы и с имеет место ассоциативный закон, т. е. с или а Ассоциативный закон означает, что порядок выполнения операции несуществен и скобки не обязательны.

3. Нейтральный элемент. Существует нейтральный элемент который не изменяет результата операции, т. е. или а для любого а.

Если операция называется умножением, то нейтральный элемент называется единицей, обозначается 1 и определяется из уравнения Если операция называется сложением, то нейтральный элемент называется нулем, обозначается 0 и определяется из уравнения

4. Обратный элемент. Существует обратный элемент а такой, что При умножении обратный элемент обозначается и определяется из уравнения При сложении обратный элемент обозначается —та и определяется из уравнения а

Кроме перечисленных аксиом, элементы группы могут удовлетворять коммутативному закону, т. е. или а . В этом случае группа называется коммутативной или абелевой. Все рассматриваемые в дальнейшем группы коммутативны.

В теории групп большое значение имеет теорема о нейтральном и обратном элементах [121].

Теорема. Группа обладает единственным нейтральным элементом и каждому элементу группы соответствует единственный обратный элемент.

Доказательство. а) Допустим, что в группе два нейтральных элемента Тогда имеем тождество т. е. нейтральные элементы совпадают. Следовательно, в группе один нейтральный элемент, б) Допустим, что у элемента а имеется два обратных элемента а и а. Имеем равенства т. е. обратные элементы совпадают.

Примеры групп.

1. Аддитивная двоичная группа. Состоит из элементов 0 и 1. Операция сложения определена по модулю т. е. а где знак сравнения. Числа сравним по т. е. если

где любые целые числа; остаток, Операция сложения в группе определена табл. 9.1.

Нейтральным элементом является 0, обратным элементом к О является 0, а обратный к 1 является 1, так как

2. Мультипликативная двоичная группа. Состоит из элементов 1 и —1. Операция умножения в группе определена табл. 9.2. Нейтральным элементом является 1, обратным элементом к 1 является 1, а обратным к — 1 является — 1. Из сравнения табл. 9.1, 9.2 видно, что они имеют много общего. Если заменить элемент 0 на 1, элемент 1 на операцию сложения по на умножение, то табл. 9.1 переходит в табл. 9.2. Это свойство сохраняется и при -ичных группах.

Таблица 9.1 (см. скан)

Таблица 9.2 (см. скан)

3. Аддитивная -ичная группа. Она состоит из элементов Операция сложения определяется по и для приведена в табл. 9.3.

Нейтральным элементом является 0, а обратными являются: для 0 элемент 0, для для 2—3, для 3—2, для 4—1. Обратными элементами являются те, которые дополняют элемент до 5 или 0, так как

4. Мультипликативная -ичная группа. Она состоит из элементов вида

Таблица 9.3 (см. скан)

Таблица 9.4 (см. скан)

Операция умножения определяется следующим равенством

Следовательно, умножение элементов изоморфно сложению индексов пит, входящих в показатели экспонент. Табл. 9.4 определяет операцию умножения.

Из сравнения табл. 9.3 и 9.4 следует, что индексы у элементов табл. 9.4 образуют табл. 9.3. Нейтральным элементом является а обратными элементами те, которые дополняют показатель степени до величины, кратной . Обратным к является Для для для

5. Мультипликативная комплексно-сопряженная -ичная группа. Она состоит из элементов но операция умножения определяется следующим образом:

где — знак комплексной сопряженности. Из (9.4) следует, что комплексно-сопряженное умножение соответствует вычитанию индексов. Но разность

где т. е. разности можно привести к значениям элементы

В табл. 9.5 даны разности для приведенные к значениям 0,4. Например — Согласно табл. 9.5 в табл. 9.6 приведены правила комплексно-сопряженного умножения согласно (9.4).

Так как нейтральный элемент, то Из табл. 9.6 видно, что элемент расположен среди элементов

Таблица 9.5 (см. скан)

Таблица 9.6 (см. скан)

Таблица 9.7 (см. скан)

6. Полный -ичный код. Он является группой, так как если в нем определить бинарную операцию, то он будет удовлетворять всем четырем групповым аксиомам. Определение бинарной операции зависит от представления элементов (сигналов) полного кода. Покажем это на примере.

Положим Объем полного кода т. е. он содержит 9 сигналов (элементов). Каждому сигналу может быть поставлена в однозначное соответствие кодовая последовательность, представляющая запись ее номера в -ичной системе счисления. При алфавит состоит из элементов 0, 1, 2. В табл. 9.7 приведены номера кодовых последовательностей и их запись.

Представление кодовых последовательностей в виде, представленном в табл. 9.7, обусловливает выбор в качестве бинарной операции посимвольное сложение по Например, сумма элементов так как

в связи с тем, что Таблица 9.8 представляет полную таблицу сложения при для кодовых последовательностей табл. 9.7.

По табл. 9.8 проверим все групповые свойства полного кода. Замкнутость имеет место, так как все элементы табл. 9.8 принадлежат полному коду. Ассоциативность проверяется непосредственно. Например, С другой стороны, Нейтральным элементом является 0, и для каждого элемента имеется единственный обратный элемент, который в сумме дает 0. Следовательно, полный код является группой.

Если символы кодовых последовательностей представить в виде (9.2), то в качестве бинарной операции над элементами полного кода следует взять посимвольное умножение согласно соответствующей таблице умножения элементов При этом индексы у получаемых элементов будут соответствовать таблице сложения, аналогичной табл. 9.8.

Разложение группы по подгруппам. Если часть группы обладает свойствами подгруппы, т. е. у нее выполняются все четыре групповые аксиомы, то она называется подгруппой. Очевидно, нейтральный элемент подгруппы должен совпадать с нейтральным элементом группы, иначе группа должна была бы содержать два нейтральных элемента, что невозможно. В общем случае, все подгруппыимеют

Таблица 9.8 (см. скан)

один и тот же нейтральный элемент. Согласно четвертой аксиоме подгруппа должна содержать все свои обратные элементы.

В качестве примера рассмотрим табл. 9.8. Из этой таблицы сразу же можно выделить подгруппу, состоящую из элементов 0, 1,2. Можно также выделить подгруппы из элементов 0, 3, 6; 0, 4, 8; О, 5, 7.

Подгруппы имеют большое значение в теории групп, так как они позволяют разлагать группы на более простые структуры. Например, если использовать подгруппу 0, 1,2, то разложение группы (полного кода) с имеет вид

Перейдем к разложению группы по подгруппе в общем случае. Обозначим элементы группы через где объем группы. (В теории групп объем называется порядком группы.) Элементы подгруппы обозначим через где объем или порядок подгруппы. Положим Составим упорядоченную таблицу элементов группы следующим образом. В первую строку поместим элементы подгруппы, причем она начинается с нейтрального элемента. Каждый элемент подгруппы появляется в строке один раз. Первым элементом второй строки может быть любой элемент группы, не входящий в

первую строку. Остальные элементы получаются в результате выполнения принятой операции; например, при умножении (сложении) всех элементов подгруппы на первый элемент строки. Аналогично образуются и все остальные строки, до тех пор, пока в таблицу не войдут все элементы группы. Такое представление группы дается следующей таблицей, причем в качестве групповой операции взято умножение:

Из (9.6) следует, что число строк равно а число столбцов равно Число элементов в (9.6) равно С другой стороны, число элементов в группе равно Поэтому

В общем случае порядок подгруппы делит порядок группы (теорема Лагранжа).

Совокупность элементов в строке называется смежным классом, а элемент, стоящий в первом столбце строки — образующим смежного класса. Для разбиения (9.6) известен ряд теорем; основными являются ниже следующие [121].

Теорема 1. Два элемента группы принадлежат одному и тому же смежному классу по подгруппе тогда и только тогда, когда произведение принадлежит

Теорема 2. Каждый элемент группы принадлежат одному и только одному смежному классу по подгруппе

Число различных разбиений группы по подгруппам весьма велико [138]. Среди различных разбиений отметим только одно, которое назовем натуральным. Заменим последовательности их номерами в -ичной системе счисления и положим, что объем подгруппы

причем

Если то делит и число смежных классов (включая саму подгруппу) согласно (9.7) равно

Расположим все элементы группы в порядке их номеров:

Пример такого разбиения был дан в форме (9.5). Оно позволяет представить все сигналы через сигналы с номерами Всего необходимо знать сигналов вместо Наименьшее число будет при Из (9.10) следует, что при любом совокупность элементов является подгруппой.