Помехоустойчивое кодирование, страница 3

Дополнительный проверочный разряд  образуется как дополнение до четности всей последовательности символов, т.е.

, .

При декодировании сначала получают проверку . Далее отбрасывают символ  и получают остальные проверки . По полученному результату  и  расшифровывают передаваемую кодовую комбинацию по правилам:

1.  ; считают, что в кодовой комбинации нет ошибок.

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

3. ; обнаружена двойная ошибка, номер искаженного символа восстановлен неправильно.

4. ; искажен последний контрольный разряд . Этот код может быть использован необязательно для исправления ошибок, но и просто для обнаружения ошибок.

6.3  Классификация кодов

 

6.4  Линейные коды

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

6.4.1  Алгебраические основы теории кодирования

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

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

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

-   образует абелеву группу по сложению,

-  выполняется замкнутость по умножению и

-  ассоциативность по умножению.

В кодировании интерес представляют коммутативные кольца с конечным числом элементов, в частности, кольца многочленов . «Аналогом» подгруппы в кольце будет идеал. Это подмножество элементов кольца, если выполняются условия:

,

, ,  и .

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

-   группа по сложению,

-    без нулевого элемента группа по умножению,

-  выполняется дистрибутивный закон.

Конечные поля называются полями Галуа и обозначаются . Не из любого числа элементов  можно настроить поле. Это возможно только когда  - простое число или ;

Чтобы задать (построить) поле надо привести таблицы сложения и умножения. Легко строится поле из простого числа элементов. Операции сложения и умножения определяются по модулю этого числа . Если  - степень простого числа, поле строить труднее. Надо использовать неприводимый многочлен степени m с коэффициентами из простого подполя. Он играет роль простого числа, операции сложения и умножения определяются по модулю этого многочлена. Конечное поле заданного порядка единственно с точностью до обозначения элементов. Обозначение элементов, тем не менее, не безразлично. Так многочленное обозначение позволяет легко производить операцию сложения, а умножение весьма сложно. Его легче производить используя степенное представление элементов. Если взять какой-то элемент (ненулевой) поля и производить операцию умножения только над ним, то через определенное число шагов nпроизойдет циклическое повторение. Особый интерес представляют элементы, которые порождают все элементы поля. Они называются примитивными. Неприводимый многочлен, по модулю которого элемент х является примитивным, называется примитивным многочленом. Построим поле , т.е. из 16 элементов. В качестве многочлена, по модулю которого будем строить таблицы умножения и сложения возьмем многочлен . Он неприводим над  и является примитивным.

Представление элементов поля

Степенное	Многочлен	Двоичное	Десятичное
0	0	0000	0
	1	0001	1
		010	2
		0100	4
		1000	8
		0011	3
		0110	6
		1100	12
		1011	11
		0101	5
		1010	10
		0111	7
		1110	14
		1111	15
		1101	13
		1001	9

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