Файл: infoteh3part.docx

• При получении одной из трех верхних кодовых комбинаций, мы считаем, что был отправлен код 000 (при условии однократной ошибки).

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

Т.е. получили возможность исправления.

Графическая интерпретация

Единичные ошибки на окружности , ошибки –кратные на окружности . Для исправления необходимо:

Для задачи обнаружения ошибок кратности и исправления ошибок кратности , требуется:

Геометрическая интерпретация

Оценки необходимой разрядности кода для обеспечения возможности построения помехозащищенного кода.

• Хэмминг:

25+1

• Плоткин: верхняя граница для кодового расстояния для заданных значений :

• Разрядность, необходимая для передачи сообщений (000 не используется):

Код Хэмминга код с , позволяющий исправлять все однократные ошибки. Для него количество информационных разрядов:

Уравнение имеет целочисленные решения , которые определяют коды : (3,1); (7,4); (15,11) и т.д.

Граница Варшамова-Гильберта

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

(Групповые) блоковые помехозащищенные коды обычно обозначают, как коды, где:

– число информационных разрядов;

– общее число разрядов;

– дополнительные избыточные или поверочные разряды.

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

Самый простой принцип задания дополнительных разрядов и соответственно поверки наличия ошибки при приеме следующий:

То есть:

Тогда на приемной стороне достаточно при получении кодовой комбинации проверить выполнение равенства (проверка на четность):

Вектор ошибок - кодовая комбинация, имеющая «1» в разрядах, подвергшихся искажению, и «0» во всех остальных разрядах. Любую искаженную кодовую комбинацию можно рассматривать как -сумму разрешенной кодовой комбинации и вектора ошибки. Возвратимся к примеру.

---

Разрешенные комбинации	Искаженные комбинации	Вектор ошибок
	001	001
	010	010
000	100	100
111	011	100
	101	010
	100	011

---

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

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-ом разрядах.

---