Математическое введение к линейным кодам

4.6 Математическое введение к линейным кодам

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

Множества, для которых определены некоторые алгебраические операции, называют алгебраическими системами. Под алгебраической операцией понимают однозначные сопоставление двум элементам некоторого третьего элемента по определенным правилам. Обычно основную операцию называют сложением (обозначают a+b=c) или умножением (обозначают a*b=c), а обратную ей – вычитанием или делением, даже, если эти операции проводятся не над числами и не идентичны соответствующим арифметическим операциям.

Рассмотрим кратко основные алгебраические системы, которые широко используют в теории корректирующих кодов.

Группой множество элементов, в котором определена одна основная операция и выполняются следующие аксиомы:

1.    В результате применения операции к любым двум элементам группы образуется элемент этой же группы (требование замкнутости).

2.    Для любых трех элементов группы a,b,c удовлетворяется равенство (a+b)+c=a+(b+c), если основная операция – сложение, и равенство a(bc)=(ab)c, если основная операция – умножение.

3.    В любой группе G_n существует однозначно определенный элемент, удовлетворяющий при всех значениях a из G_n условию а+0=0+а, если основная операция – сложение, или условию а*1=1*а=а, если основная операция – умножение. В первом случае этот элемент называют нулем и обозначают символом 0, а во втором – единицей и обозначают символом 1.

4.    Всякий элемент а группы обладает элементом, однозначно определенным уравнением а+(-а)=-а+а=0, если основная операция – сложение, или уравнением а*а^-1= а^-1*а=1, если основная операция – умножение.

В первом случае этот элемент называют противоположным и обозначают (-а), а во втором – обратным и обозначают а^-1.

Если операция, определенная в группе, коммутативна, то есть справедливо равенство a+b=b+a (для группы по сложению) или равенство a*b=b*a (для группы по умножению), то группу называют коммутативной или абелевой.

Группу, состоящую из конечного числа элементов, называют порядком группы.

Чтобы рассматриваемое нами множество n-разрядных кодовых комбинаций было конечной группой, при выполнении основной операции число разрядов в результирующей кодовой комбинации не должно увеличиваться. Этому условию удовлетворяет операция символического поразрядного сложения по заданному модулю q (q – простое число), при которой цифры одинаковых разрядов элементов группы складываются обычным порядком, а результатом сложения считается остаток от деления полученного числа по модулю q.

При рассмотрении двоичных кодов используется операция сложения по модулю 2. Результатом сложения цифр данного разряда является0, если сумма единиц в нем четная, и 1, если сумма единиц в нем нечетная, например,

Å

Выбранная нами операция коммутативна, поэтому рассматриваемые группы будут абелевыми.

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

Пример24. Определить, являются ли группами следующие множества кодовых комбинаций:

1)   0001, 0110, 0111, 0011;

2)   0000, 1101, 1110, 0111;

3)   000, 001, 010, 011, 100, 101, 110, 111.

Решение: Первое множество не является группой, так как не содержит нулевого элемента.

Второе множество не является группой, так как не выполняется условие замкнутости, например, сумма по модулю 2 комбинаций 1101 и 1110 дает комбинацию 0011, не принадлежащую исходному множеству.

Третье множество удовлетворяет всем перечисленным условиям и является группой.

Подмножества группы, являющиеся сами по себе группами относительно операции, определенной в группе, называют подгруппами. Например, подмножество трехразрядных кодовых комбинаций: 000, 001, 010, 011 образуют подгруппу указанной в примере группы трехразрядных кодовых комбинаций.

Пусть в абелевой группе G_n задана определенная подгруппа А. Если В – любой, не входящий в А элемент из G_n, то суммы (по модулю 2) элементов В с каждым из элементов подгруппы А образуют определенный класс группы G_n по подгруппе А, порождаемый элементом В.

Элемент В, естественно, содержится в этом смежном классе, так как любая подгруппа содержит нулевой элемент. Взяв последовательно некоторые элементы B_j группы, не вошедшие в уже образованные смежные классы, можно разложить всю группу на смежные классы по подгруппе А.

Элементы B_j называют образующими элементами смежных классов по подгруппам.

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

Пример25: Разложить группу трехразрядных двоичных кодовых комбинаций по подгруппе двухразрядных кодовых комбинаций.

Решение: Разложение выполняют в соответствии с таблицей:

Таблица 4.4.

Пример26: Разложить группу четырехразрядных двоичных кодовых комбинаций по подгруппе двухразрядных кодовых комбинаций.

Решение: Существует много вариантов разложения в зависимости от того, какие элементы выбраны в качестве образующих смежных классов.

Один из вариантов:

Таблица 4.5.

Кольцом называют множество элементов R, на котором определены две операции (сложение и умножение), такие, что

1)   множество R является коммутативной группой по отношению;

2)   произведение элементов аÎR и bÎR есть элемент R (замкнутость по отношению и умножению);

3)   для любых трех элементов a,b,c из R справедливо равенство a(bc)=(ab)c (ассоциативный закон для умножения);

4)   для любых трех элементов a,b,c из R выполняются соотношения a(b+c)=ab+ac и (b+c)a=ba+ca (дистрибутивные законы);

Если для любых двух элементов кольца справедливо соотношение ab=ba, то кольцо называют коммутативным.

Кольцо может не иметь единичного элемента по умножению и обратных элементов.

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

Полем F называют множество, по крайней мере, двух элементов, в котором определены две операции – сложение и умножение, и выполняются следующие аксиомы:

1)   множество элементов образуют коммутативную группу по сложению;

2)   множество ненулевых элементов образуют коммутативную группу по умножению;

3)   для любых трех элементов множества a,b,c выполняется соотношение (дистрибутивный закон) a(b+c)=ab+ac.

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

Поле GF(P), состоящее из конечного числа элементов Р, называют конечным полем или полем Галуа. Для любого числа Р, являющегося степенью простого числа q, существует поле, насчитывающее р элементов. Например, совокупность чисел по модулю q, если q - простое число, является полем.

Поле не может содержать менее двух элементов, поскольку в нем должны быть по крайней мере единичный элемент относительно операции сложения (0) и единичный элемент относительно операции умножения (1). Поле, включающее только 0 и 1, обозначим GF(2). Правила сложения и умножения в поле с двумя элементами следующие:

Рис. 4.5 Правила сложения и умножения в поле с двумя элементами

Двоичные кодовые комбинации, являющиеся упорядоченными последовательностями из n Элементов поля GF(2), рассматриваются в теории кодирования как частный случай последовательностей из n элементов поля GF(P). Такой подход позволяет строить и анализировать коды с основанием, равным степени простого числа. В общем случае суммой кодовых комбинаций A_j и A_i называют комбинацию A_f = A_i + A_j, в которой любой символ A_k (k=1,2,…,n) представляет собой сумму k-х символов комбинаций, причем суммирование производится по правилам поля GF(P). При этом вся совокупность n-разрядных кодовых комбинаций оказывается абелевой группой.

В частном случае, когда основанием кода является простое число q, правило сложения в поле GF(q) совпадает с правилом сложения по заданному модулю q.

Похожие работы

Энтропия. Теория информации

Скачать

63729

48

3

... порядок чередования букв формируется согласно правилам, заданным верхними иерархическими уровнями текста, то есть не «снизу вверх», а «сверху вниз». Что же касается исполь­зуемой теорией информации вероятностной функции энтропии, то она может быть использована в качестве точного математического инструмента только на нижних уровнях иерархии текста, поскольку только на этих уровнях удается найти ...

Классическая теория информации и еe ограничения

Скачать

12754

0

0

... , 1968. - 340 с.]. В связи с этим логично было бы далее предположить, что она не предполагает строго количественного эквивалента, подобно энергии или материи. Но парадокс классической теории информации именно в том и состоит, что в её основе лежит предположение Р.Хартли, согласно которому информация допускает количественную оценку [Hartley R.V.L. Transmission of Information // BSTJ.- 1928. - V.7 - ...

Прикладная теория информации

Скачать

88587

0

39

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

Концепции общей теории информации

Скачать

96932

1

1

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