Дискретная математика (стр. 4 )

Аналогично определяются и правые смежные классы, содержащие элементы вида h*g. Первым левым и первым правым смежными классами является сама подгруппа H. Среди смежных классов первый – единственная подгруппа, остальные классы – просто подмножества группы G.

Для получения второго левого смежного класса надо взять любой элемент g из группы G, не попавший в первый класс, и последовательно умножить его на все элементы подгруппы H (g*h). Результаты этого умножения образуют второй левый класс. Для получения третьего левого смежного класса надо взять любой элемент g из группы G, не попавший в первый и во второй классы, и последовательно умножить его на все элементы подгруппы H. Результаты этого умножения в свою очередь образуют третий левый класс. И так далее. В качестве последнего левого смежного класса берутся все оставшиеся (не попавшие в предыдущие классы) элементы G (умножать уже не надо).

Аналогично определяются и правые смежные классы. Множество левых классов образуют разбиение группы G, так же как и множество правых. У не коммутативной группы множество левых и правых классов могут и не совпасть. Если эти разбиения (правое и левое) совпадают, то подгруппа называется нормальным делителем. Например, рассмотрим разбиение симметрической группы степени три по подгруппе H ={e, (1 2)} порядка два:

Здесь слева от элемента (с буквой l) показана его принадлежность к левому разбиению, а справа (с буквой r) – к правому. Для получения второго левого класса взят элемент g =, не попавший в первый класс, и умножен на элемент (1 2), так как на групповую единицу его можно не умножать. Результат умножения элементвместе с элементомобразуют второй левый класс.

Третий левый составили два элемента, не попавшие в первые два класса. Для получения второго правого класса взят тот же элемент g =, не попавший в первый класс, и элементумножен на него. Результат умножения элементвместе с элементомобразуют второй правый класс.

Так как левое разбиение не совпало с правым, то рассмотренная подгруппа H не является нормальным делителем. Любая подгруппа индекса два, порядок которой вдвое меньше порядка самой группы, является нормальным делителем. Первый смежный класс – это сама подгруппа, а второй – это те элементы, что не попали в первый класс. Значит, подгруппа H = {e,,} – нормальный делитель симметрической группы степени три.

Для определения вида делителя – подгруппы можно воспользоваться следующим утверждением: H – нормальный делитель G если для каждого g и для каждого h существуют h` и h``, такие что, g*h = h`*g и h*g = g*h``. Отсюда у коммутативной группы все её подгруппы (если они есть) нормальные делители, так как здесь h = h` = h``.

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

Из теоремы Лагранжа не следует, что у не циклической группы имеются все подгруппы, порядок которых является делителем порядка группы. У циклической группы имеются все подгруппы, порядок которых является делителем порядка группы. Например, у не циклической группы порядка двенадцать (единичный элемент – 1) элементы 2, 3, … , 9 имеют порядок три, а элементы 10, 11 и 12 – порядок два и вместе с групповой единицей образуют четвертную группу Клейна. У этой группы нет подгруппы порядка шесть, а подгруппы порядка два, три и четыре есть:

Групп порядка 6 может быть только две: циклическая и симметрическая степени 3. Циклической подгруппы порядка 6 у этой группы порядка 12 нет, так как у неё нет элементов порядка 6. В симметрической подгруппе степени три имеются два элемента порядка три и три элемента порядка два. Возьмём в качестве примера подтаблицу таблицы Кэли для группы порядка двенадцать с элементами порядка три 2 и 3, которые являются квадратами друг друга, то есть вместе с 1 образуют подгруппу порядка три, и всеми тремя элементами порядка два: 10, 11 и 12:

Полученная подтаблица не является таблицей Кэли для подгруппы, так как в ней кроме элементов 1, 2, 3, 10, 11 и 12 присутствуют и другие элементы группы порядка двенадцать.

Из теоремы Лагранжа также следует, что элементы, обратные сами себе (порядка два), есть только у групп чётного порядка, но количество их в группе обязательно нечётное. Общее число элементов группы, не обратных самим себе, вместе с их обратными элементами – чётное. Из оставшегося чётного числа элементов группы чётного порядка один – это единичный элемент (e), отсюда общее число элементов, обратных самим себе, нечётное. Например, у симметрической группы степени три имеется три элемента порядка два, у циклических групп порядка четыре и шесть – один, у четвертной группы Клейна V4 порядка четыре – три.

Элементы симметрической группы степени n имеют порядки 2, 3, … , n. Из этих элементов можно получить и не циклические подгруппы симметрической группы степени n, порядок которых больше n, но не все подгруппы такого порядка. Например, имеется группа порядка двенадцать с циклической подгруппой порядка шесть. Эта группа не может быть подгруппой симметрической группы степени четыре:

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

У второй группы порядка двенадцать элементы 2 и 6 имеют порядок шесть, элементы 4, 7, 8, 9, 10, 11 и 12 – порядок два, а элементы 3 и 5 имеют порядок три. Эта группа имеет похожее устройство, как и у не циклических групп порядков десять, восемь (с циклической подгруппой порядка четыре) и шесть. У них у всех есть циклическая подгруппа индекса два, а оставшиеся (не попавшие в подгруппу индекса два) элементы имеют порядок два.

Воспользуемся теоремой Лагранжа и уточнённой теоремой Кэли для построения таблицы истинности симметрической группы степени три (порядка шесть). Элементы нумеруются от 1 до 6, причём 1 – это операционная единица по групповой операции, как и раньше:

Таблица 1 Таблица 2

Таблица 3 Таблица 4

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

В таблице Кэли 1 для симметрической группы степени три полностью заполнены только первая строка и первый столбец, потому что как работает единичный элемент в группе всегда понятно. Элементы 2 и 3 имеют порядок три, а остальные (4, 5 и 6) – порядок два. В таблице Кэли 1 заполнены подтаблицы для этих циклических подгрупп. Поскольку элемент 2 имеет порядок три, то вторая строка должна быть равноцикловым беспорядком из двух циклов порядка три. Элемент 2 – это квадрат элемента 3, и наоборот, элемент 3 – это квадрат элемента 2.

На трёх элементах 4, 5 и 6 можно сделать только два беспорядка: этоиВ таблице Кэли 2 для второй строки взят первый беспорядок, и сразу получаем для элемента 4, что 1 переходит в 4 и 4 – в 1, 2 переходит в 5 и, значит, 5 должен переходить в 2, 3 – в 6 и наоборот, 6 в 3, так как элемент 4 обратен сам себе и его столбец является равноцикловым беспорядком из трёх циклов длины два.

В таблице Кэли 3 для третьей строки взят второй беспорядок:и аналогично четвёртому в таблице 2 заполнены столбцы для двух оставшихся элементов порядка два (5 и 6). Осталось заполнить два неполных столбца для элементов порядка три или, что то же самое, три неполных строки для элементов порядка два. Если заполнять в таблице 4 строку для элемента 4 группы, то 6 переходит в 2, и, значит, 2 в 6, а так как 5 переходит в 3, то и 3 – в 5. Аналогично в таблице 4 заполним и две оставшихся строки и получим не симметричную таблицу Кэли для не коммутативной симметрической группы порядка шесть.

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

Здесь элемент 6 имеет порядок два, а 3, 4 , 5 и 2 – порядок три. Для всех трёх циклических подгрупп заполнены их подтаблицы. В любой таблице Кэли все элементы любой строки и любого столбца разные. Возьмём четвёртый столбец, в нём нет трёх элементов. Во второй и третьей строках четвёртого столбца можно поставить только элемент 6, так как 4 и 5 в столбце уже есть, а элементы 1, 2 и 3 уже есть во второй и третьей строках таблицы. Но одного элемента на две позиции четвёртого столбца недостаточно.

Подобным образом строились и вышеприведённые таблицы Кэли для двух не циклических групп порядка двенадцать. Для циклических групп таблица Кэли использовать такой способ построения нет необходимости. Если расположить элементы циклической группа, начиная с единичного, а затем в порядке возрастания степени образующего эту циклическую группу элемента, то каждая последующая строка таблицы Кэли будет циклическим сдвигом влево предыдущей. Например, циклическая группа порядка шесть, в которой 2 – образующий элемент, элемент 3 – это квадрат элемента 2, элемент 4 – куб элемента 2, …, элемент 6 – пятая степень элемента 2, 1 – единичный элемент и шестая степень элемента 2:

Глава 6. Кольца и поля

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

Значит, кроме проверки кольца на группу по сложению и на полугруппу по умножению, надо проверить и дистрибутивность этих операций. Если умножение коммутативно, то кольцо тоже называют коммутативным; если по умножению в кольце есть моноид, то это кольцо с единицей. В кольце с единицей есть и нуль (0 – кольцевая (операционная) единица по сложению) и единица (1 – кольцевая единица по умножению).

В кольце:

1.  Сложение не выводит из множества – носителя кольца.

2.  a + (b + c) = (a + b) + c для каждых a, b и c. Сложение ассоциативно.

3.  Существует кольцевой 0 (единица по сложению), такой, что для каждого элемента a кольца a + 0 = 0 + a = a.

4.  Для каждого a существует обратный элемент –a по сложению: = - a + a = a + (-a) = 0.

5.  Для каждых a и b кольца a + b = b + a. Сложение коммутативно, то есть кольцо – абелева группа по сложению.

6.  Умножение не выводит из множества – носителя кольца.

7.  a * (b * c)= (a * b) * c для каждых a, b и c. Умножение ассоциативно, то есть кольцо – полугруппа по умножению.

8.  (a+b)*c=a*c+b*c и c*(a+b)= c*a+c*b для каждых a, b и c. Умножение дистрибутивно относительно сложения и справа и слева.

Если какой-то из восьми пунктов не выполняется, то остальные пункты можно не проверять, так как рассматриваемая алгебраическая структура кольцом не является.

В кольце могут существовать и подкольца, и пересечение подколец тоже подкольцо. Примером бесконечного коммутативного кольца с единицей является множество целых чисел с обычными операциями сложения и умножения Примером бесконечного коммутативного кольца без единицы является множество целых чисел, кратных целому числу n (n > 1), с обычными операциями сложения и умножения.

Примером конечного коммутативного кольца с единицей является множество классов вычетов по модулю n (n>1) C, C, … , C, обозначаемое как Z. Кольцо Z:

В кольце Z при операции сложения (+) целочисленно по модулю n складываются индексы элементов кольца, а при операции умножения (*) целочисленно по модулю n умножаются индексы элементов кольца. C + C = C, где mod(a + b) = d. C * C = C, где mod(a * b) = d. Операция mod(x) – это получение остатка от целочисленного деления числа x на число n.

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

Свойства колец:

1.  Для каждого элемента a кольца a * 0 = 0 * a = 0, так как a + 0 = a, значит, a * (a + 0) = a * a = a * a + a * 0 = a * a + 0. Отсюда a * 0 = 0.

2.  (-a) * b = a * (-b) = - (a * b), так как 0 = a * 0 = a * (b – b) = a * (b + (-b)) = (a * b) + (a *(-b)). Отсюда a * (-b) = - (a * b).

3. –a = (-1) * a, так как –a = (-a) * 1 = (-1) * a.

В кольцах целых чисел с операциями обычных сложения и умножения из того, что a * b = 0, следует, что или a = 0, или b = 0. В кольце Z это не так: C* C= 0 = C и C не равен C.

Если в кольце a*b=0 и a0, b0, то a – левый, а b – правый делитель нуля. В кольце Z элемент C - это делитель нуля. Если в кольце нет делителей нуля, то это кольцо без делителей нуля и в нём выполняется закон сокращения: если a * b = a * c и a не равно 0, то в = с. Доказательство: a * b – a * c = 0, отсюда по дистрибутивности a * (b – c) = 0, значит, b – c = 0 и b = c.

Кольцо Z не имеет делителей нуля, так как в таблице Кэли кольца по операции умножения нули (C = 0) есть только в первом столбце и первой строке:

Рассмотрим кольцо на множестве пар целых чисел с операциями сложения <a, b> + <c, d> = <a+c, b+d> и операцией умножения <a, b> * <c, d> = <a*c, b*d>. Это коммутативное кольцо с единицей (кольцевая единица – это пара <1,1>). Кольцевым нулём в этом кольце является пара <0,0> = 0. Делители нуля: <1,0>*<0,1> = <0,0>. В этом кольце пары вида <a,0> и <b,0> - это делители нуля при a и b, которые не равны нулю.

В кольце с единицей могут быть обратимые элементы по операции умножения. Обратимый элемент не может быть делителем нуля, так как если a * b = 0, то a * (a * b) = 0 = (a * a) * b = 0 = 1 * b = 0 и, значит, b = 0.

Все обратимые элементы кольца с единицей образуют группу относительно операции умножения. Например, в кольце Z обратимый элемент – это C. C обратен сам себе и вместе с кольцевой единицей C образует коммутативную группу по операции умножения:

Поле – это коммутативное кольцо, в котором каждый ненулевой элемент обратим. В поле не может быть делителей нуля. Аддитивная группа поля (по операции сложения) содержит все его элементы, а мультипликативная его группа (по операции умножения) не содержит полевого нуля, т. е. содержит на один элемент меньше, чем аддитивная группа. Конечные поля Z, число элементов p в которых является простым числом, называются полями Галуа. Например, Z является полем:

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

Можно считать, что в поле четыре операции: сложение, вычитание, умножение и деление. Уравнение b * x = a в поле имеет решение при b не равном полевому нулю: x = a / b = a * b.

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

1.  Сложение не выводит из множества – носителя поля.

2.  a + (b + c)= (a + b) + c для каждых a, b и c. Сложение ассоциативно.

3.  Существует полевой 0 (единица по сложению), такой, что для каждого элемента a поля a + 0 = 0 + a = a.

4.  Для каждого a существует обратный элемент по сложению –a: = - a + a = a + (-a) = 0.

5.  Для каждых a и b поля a + b = b + a. Сложение коммутативно, то есть поле – это абелева группа по сложению.

6.  Умножение не выводит из множества – носителя поля.

7.  a * (b * c)= (a * b) * c для каждых a, b и c. Умножение ассоциативно.

8.  Существует полевая 1 (единица по умножению), такая, что для каждого элемента a поля a * 1 = 1 * a = a.

9.  Для каждого не равного 0 элемента a существует обратный элемент по умножению a: = a * a = a * a = 1.

10.  Для каждых a и b поля a * b = b * a. Умножение коммутативно, то есть поле – это абелева группа по умножению без 0.

11.  c*(a+b)= c*a+c*b для каждых a, b и c. Умножение дистрибутивно относительно сложения.

Если какой-то из одиннадцати пунктов не выполняется, то оставшиеся пункты можно не проверять, так как рассматриваемая алгебраическая структура полем не является.

Кольца и поля не единственные алгебры с двумя операциями, зато они самые изученные. Интересной является алгебра на положительных целых числах с двумя операциями: обычными сложением и умножением. По сложению – это моноид, а по умножению – полугруппа.

В этой алгебре работает недавно доказанная теорема Ферма: уравнение a + b = c имеет решение в целых положительных числах только при n = 2. Такие тройки чисел a, b и c называют пифагоровыми тройками:,,,и так далее. Если в левой части уравнения увеличивать число слагаемых, то для n = 2 число слагаемых может быть равно трём, четырём и так далее.

Для n = 3 число слагаемых должно быть не менее трёх, и тогда будет решение уравнения в целых положительных числах:,и так далее. Для n = 4 число слагаемых должно быть не менее пяти (произошёл скачок в числе слагаемых):5),5) и так далее. Для n = 5 число слагаемых должно быть не менее шести, что косвенно подтверждает достоверность скачка слагаемых для n = 4:2),29 30) и так далее.

Во времена Ферма такие результаты получить было невозможно, так как не было компьютеров. Даже сейчас шестая степень (n = 6) не берётся. Возможно, что при дальнейшем развитии компьютеров удастся получить результаты по расширению теоремы Ферма для n > 5. Можно считать каждую вновь полученную степень n следующим этапом в развитии компьютеров.

Теория кодирования

Глава 7. Расстояние Хемминга

Кодирование и декодирование производится для распознавания или исправления ошибок при передаче данных (не путать с шифрованием). При кодировании исходные двоичные слова длины m переводятся в кодовые слова длины n (m < n). При декодировании полученные после передачи данных кодовые слова анализируются, при возможности исправляются, и затем переводятся в исходные слова.

Это двоичный (m, n)-код, он содержит 2 исходных и, соответственно, 2 кодовых слов, так как каждому исходному слову соответствует своё собственное кодовое слово. Исходными словами являются все двоичные слова длины m, а кодовыми – некоторое подмножество мощности 2 двоичных слов длины n. Между исходными и кодовыми словами существует взаимно однозначное соответствие.

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

Например, код (m, m+1) с проверкой чётности. Кодовое слово получается приписыванием к исходному слову так называемой контрольной суммы (к. с.), которая равна единице, если в исходном слове нечётное число единиц, и равна нулю в противном случае. Исходное слово 011011 переходит в кодовое слово 0 а исходное слово 110010 - в кодовое слово 1100101. Этот код обнаруживает ошибку в нечётном числе позиций кодового слова: в одной, трёх, пяти и так далее позициях.

Пример кода с исправлением ошибок – это (1, 3) – код или код с тройным повторением. Каждый бит исходного слова для получения кодового слова заменится тремя битами. Исходное слово 0100 переводится в кодовое слово . При получении искажённого (ошибочного) кодового слова из любой тройки битов для получения исходного слова берётся то значение бита, которого большинство в рассматриваемой тройке. Искажённое кодовое слово переводится при декодировании в исходное слово 0100. Этот код очень медленный, хоть и очень эффективный.

Расстоянием Хемминга d(a, b) между двумя двоичными словами a и b называют число несовпадающих позиций в них. Например, d(01101,00111) = 2. Для получения расстояния слова a и b удобно писать друг под другом.

Расстояние Хемминга удовлетворяет трём аксиомам расстояний: 1) расстояние неотрицательно и равно нулю, только если a=b; 2) d(a, b)=d(b, a); 3) d(a, b)+d(b, c)d(a, c) (неравенство треугольника). Вес w(a) двоичного слова a равен числу единиц среди его координат (разрядов, бит). Например, w(1100101) = 4. d(a, b)=w(a+b), где «+» - это операция покоординатного (поразрядного, побитного) сложения двоичных слов a и b по модулю два.

Теорема: для того чтобы код позволял обнаруживать ошибки в k (или менее) позициях, необходимо и достаточно, чтобы минимальное расстояние между кодовыми словами было k+1. Доказательство: пусть b1 и b2 два не совпадающих друг с другом кодовых слова, тогда по условию d(b1,b2) k + 1. Если при передаче кодового слова b1 произошло Rk ошибок (в слове b1 инвертировано R позиций), то принято искажённое кодовое слово c1 вместо кодового слова b1 и d(b1,c1) = Rk.

По неравенству треугольника d(b1,c1) + d(c1,b2) d(b1,b2) k+1. Так как d(b1,c1) k, то d(c1,b2) 1, то есть искажённое кодовое слово c1 никогда не совпадёт с другим кодовым словом b2, отличным от «родного» для c1 кодового слова b1. Обнаружение ошибки при передаче данных и состоит именно в том, чтобы определить, что полученное слово не является кодовым. Теорема доказана.

Теорема: для того чтобы код позволял исправлять ошибки в k (или менее) позициях, необходимо и достаточно, чтобы минимальное расстояние между кодовыми словами было 2k+1. Доказательство: пусть b1 и b2 два не совпадающих друг с другом кодовых слова, тогда по условию d(b1,b2) 2k + 1. Если при передаче кодового слова b1 произошло Rk ошибок, то принято искажённое кодовое слово c1 вместо кодового слова b1 и d(b1,c1) = Rk.

По неравенству треугольника d(b1,c1) + d(c1,b2) d(b1,b2) 2k+1. Так как d(b1,c1) k, то d(c1,b2) k + 1, то есть кодовое слово b1 («родное» для c1) является ближайшим кодовым словом к принятому искажённому кодовому слову c1 из всех кодовых слов. Исправление ошибки при передаче данных и состоит именно в том, чтобы найти для каждого искажённого кодового слова c1 его «родное» кодовое слово b1. Теорема доказана.

Например, рассмотрим (2,3) код с контрольной суммой (к. с.):

Исходные слова Кодовые слова

00  000

01  011

10 101

11  110

Для нахождения минимального расстояния между кодовыми словами надо рассмотреть (4*3)/2 = 6 =((2)*(2-1))/2 пар кодовых слов. Эти шесть расстояний равны: 2, 2, 2, 2, 2, 2. Минимальное расстояние между кодовыми словами равно 2 и этот код обнаруживает однократную ошибку (ошибку в одной позиции).

Рассмотрим (2,5) код, состоящий из повтора исходного слова и к. с.:

Исходные слова Кодовые слова

00  00000

01  01011

10 10101

11 11110

Шесть расстояний между всеми возможными парами кодовых слов равны: 3, 3, 4, 4, 3, 3. Минимальное расстояние между кодовыми словами равно 3 и этот код или обнаруживает двукратную ошибку или исправляет однократную.

Матричное кодирование. Групповые коды

Любой (m, n)-код можно задать, указав 2 кодовых слов, то есть непосредственно для каждого исходного слова указать его кодовое слово. При больших m это будет довольно трудоёмко.

Матричные коды можно задать более экономно с использованием порождающей матрицы G порядка mn. b=aG, где a – исходное двоичное слово длины m (a … a), а b – кодовое двоичное слово длины n (b … b). j b=aG+ … + aG, где «+» означает сложение по модулю два. В матричном коде всегда нулевое исходное слово (m нулей) переводится в нулевое кодовое слово (n нулей).

Если первые m столбцов матрицы G образуют единичную матрицу, то различным исходным словам a1 и a2 будут приписываться различные кодовые слова b1 = a1 G и b2 = a2G.

Теперь вместо 2 кодовых слов достаточно задать m кодовых слов, являющихся строками порождающей матрицы G. Первая строка матрицы G является кодовым словом для исходного слова, в котором единица стоит только на первой позиции, вторая – для исходного слова, в котором единица стоит только на второй позиции, … , m-я строка – для исходного слова, в котором единица стоит только на последней, m-й позиции.

Например, для (3,6) кода возьмём порождающую матрицу G1:

Первые 3 (m=3) столбца этой матрицы G1 образуют единичную матрицу 3 на 3 и, значит, различным исходным словам a1 и a2 будут приписываться различные кодовые слова b1 и b2.

Первая строка b1 матрицы G1 является кодовым словом для исходного слова a1 = 100, вторая b2 – для исходного слова a2 = 010, последняя, третья строка b3 – для исходного слова a3 = 001. Полная таблица кодирования для этого кода с порождающей матрицей G1 имеет вид:

Исходные слова Кодовые слова Вес кодовых слов

Как видно, все кодовые слова этого кода с порождающей матрицей G1 различны. Кодовое слово b для исходного слова a = 110 можно получить, поразрядно складывая по модулю два кодовые слова b1 и b2, кодовое слово b для исходного слова a = 011 можно получить, поразрядно складывая по модулю два кодовые слова b2 и b3, а кодовое слово b для исходного слова a = 111 можно получить, поразрядно складывая по модулю два b1, b2 и b3.

Для вышеприведённого (2,3) кода с контрольной суммой порождающая матрица имеет вид:

.

Двоичный (m, n)-код называется групповым, если его кодовые слова образуют коммутативную группу с операцией покоординатного (поразрядного) сложения по модулю 2. Множество всех исходных слов длины m образует такую группу, в которой каждое исходное слово обратно самому себе (a + a = групповой единице), а групповая единица – это двоичное слово из m нулей (нулевое исходное слово).

Для кода с порождающей матрицей G множество кодовых слов b длины n b = aG образует подгруппу группы двоичных слов длины n с операцией покоординатного сложения по модулю 2. Для доказательства возьмём b1 = a1 G и b2 = a2G, тогда b1 + b2 = a1 G + a2G = (a1 + a2) G = b3, где «+» - это покоординатное сложение по модулю 2. Сумма исходных слов a1 + a2 = a3 – тоже исходное слово, а кодовым словом для исходного слова a3 является b3. Следовательно, матричные коды являются групповыми.