Концепция построения помехозащищенного кода.

1. Имеем Q сообщений.

2. Для их передачи требуется min информационных символов (разрядов).

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

4. Выбираем величину или исходя из требуемой кратности корректируемых ошибок ( )

5. Получаем -разрядный код, где значения символов/разрядов для каждого сообщения мы должны как-то задать.

6. Среди возможных полученных на приемной стороне сообщений имеем разрешенных, т.е. соответствующих передачи Q сообщений без помех.

7. Остальные возможные кодовые комбинации – зашумленные, искаженные, запрещенные.

8. Близость зашумленных сообщений к разрешенным/посланным сообщениям оценивается кодовым расстоянием, определяемым по вектору ошибки.

9. Таким образом, на приемной стороне мы имеем множество из кодовых комбинаций, из которых комбинаций являются разрешенными, а остальные – нет.

10. Задача корректировки искаженных кодов заключается в следующем:

• необходимо разбить все множество возможных кодов на подмножеств, непересекающихся, содержащих по одной разрешенной кодовой комбинации и близлежащих к ней искаженных.

• тогда остается:

• задать процедуру идентификации, к какому из подмножеств относится принятая комбинация

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

Вопрос: как разбить множество всех возможных кодов на подмножества и как построить процедуру идентификации подмножеств при приеме.

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

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

Линейная алгебра – теория групп, колец, полей.

Группа – множество элементов , для которых:

• выполняется свойство замкнутости для введенных операций;

• определена хотя бы одна основная операция сложения или умножения;

• или

• существует нулевой или единичный элемент:

или

• существует обратный элемент:

или

Если для любых двух элементов выполняется:

или ,

то группа коммутативная или абелева.

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

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

Свойства смежных классов

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

2. В одном смежном классе нет одинаковых элементов.

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

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

Опознаватель удобно строить так, чтобы он указывал номер разряда, в котором произошла ошибка (код Хэмминга).

Пример: Опознаватель кода (7,4).

Вектор ошибок	Опознаватель
0000001	001
0000010	010
0000100	011
0001000	100
0010000	101
0100000	110
1000000	111

Приведем пример разложения кода (6,3), исправляющего одиночные ошибки ( ):

Образующий элемент, вект. ошибок	Подгруппа
	100101	010111	110010	001011	101110	011100	111001
000001	100100	010110	110011	001010	101111	011101	111000
000010	100111	010101	110000	001001	101100	011110	111011
000100	100001	010011	110110	001111	101010	011000	111101
001000	101101	011111	111010	000011	100110	010100	110001
010000	110101	000111	100010	011011	111110	001100	101001
100000	000101	110111	010010	101011	001110	111100	011001

Появление «1» в младшем разряде опознавателя должно сигнализировать о возникновении ошибки в одном из нечетных разрядов переданной кодовой комбинации. Во втором разряде – во втором, или третьем, или в 6-ом, или 7-ом разрядах. В третьем – об ошибке в 4-ом, или в 5-ом, или в 6-ом, или в 7-ом разрядах.

Тогда уравнения связи для символов опознавателя и символов кода должны быть:

Операция вычисления на приемной стороне – проверка на четность. При отсутствии ошибок все . Если проверочное равенство не выполняется (есть ошибки), то в соответствующем разряде опознавателя возникает «1».