Порядок выполнения проверок и обнаружения и коррекции ошибок. Понятие об оптимальном коде. Принцип построения оптимального кода Шеннона-Фэно

Используя формулу для “хеммингова (кодового) расстояния” d =1+Δ+ S, можно определить, что для обнаружения, например, 3-х кратных ошибок и коррекции 2-укратных должно быть d _min=1+3+2=6.

Для реализации изложенной идеи автоматической коррекции ошибок с помощью кода Хэмминга используется следующий алгоритм:

Пусть принята искаженная комбинация кода:

0 1 1 1 0 0 0

1 2 3 4 5 6 7 – позиции

Здесь общее число символов n =7, n = n ₀+ k,

n ₀=4 – информационные элементы;

k =3 – контрольные элементы

Проверяем на четность соответствующие разряды кодовой комбинации. Количество проверок равно k – в данном случае 3.

1-я проверка. Суммируем единицы по модулю 2 на позициях кода 1,3,5,7.

Это суммирование дает 1, т.е. нечетное число единиц, следовательно записывается справа – налево на первой позиции кода.

2-я проверка. Суммируем единицы по модулю 2 на позициях 2,3,6,7 и получаем четное число единицы, следовательно, результат проверки на четность равен 0, каждый записываем в контрольной строке:

7 поз. 6 поз. 5 поз 4 поз. 3 поз. 2 поз 1 поз.

в) 3-я проверка. Суммируем единицы по модулю 2 на позициях (см. справочную таблицу) 4,5,6,7 и получаем нечетное число единиц, следовательно результат 1 (на поз.3).

В результате всех трех проверок (4-ю делать бессмысленно, т.к. в справочной таблице 4-я проверка предусматривает работу с разрядами, начиная с 8 и выше, которых у нас нет) получаем контрольное число 101, которое означает в десятичном счислении цифру 5.

Это означает, что в исходном коде 0111 0 00 искажен элемент кода на 5-ой позиции, т.е. подчёркнутая позиция. Следовательно, восстановленная кодовая комбинация имеет вид:

0111 1 00

Принцип построения оптимального кода Шеннона-Фано следующий:

1. Сообщения, входящие в ансамбль, располагаются в строку (в столбец) по мере убывания вероятностей.

2. Выбирается основание кода K.

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

4. Каждая из групп делится на K подгрупп с равной суммарной вероятностью в каждой подгруппе. Всем сообщениям первых подгрупп в качестве второго символа присваивается 0, всем сообщениям вторых подгрупп – 1, а сообщениям K -х подгрупп – символ (K – 1).

5. Процесс продолжается до тех пор, пока в каждой подгруппе не окажется по одной комбинации.