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

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

Для чего это нужно?

Предположим у нас есть канал связи C, содержащий источник помех, а также S — множество отправляемых данных и S’ — множество принятых данных. Рассмотрим следующий пример:
Множество S = {1,0,0,1} мы отправляем данные по каналу связи C и получаем S’ = {1,0,0,0}. Что случилось? Почему данные отличаются? А все потому, что на канале связи была помеха. И из-за этого произошла ошибка типа «замещение разряда», т.е. 1 -> 0, 0 -> 1. Как видно из-за таких ошибок данные могут меняться, а это не допустимо.

Как бороться?

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

Рассмотрим не сложный пример:

У на есть 4 бита, которые мы хотим передать «1011». Как сделать так, чтобы у нас не пропал бит? Мы просто добавим проверочные биты, т.е. будем передавать «111 000 111 111». Мы просто взяли и добавили 2 проверочных бита, теперь когда будет осуществляться передачу данных, декодер будет знать что 2 лишнее бита проверочные и таким образом вероятность потери данных уменьшиться.
Недостатком этого алгоритма является то, что если ошибок будет больше чем две, данные потеряются, чтобы увеличить эффективность алгоритма можно добавить больше проверочных битов, но это уменьшает производительность.

Ошибки могут быть следующих типов:

• — ошибка типа замещения разряда;
• — ошибка типа выпадения разряда;
• — ошибка типа вставка разряда.

Код Хемминга:

Код Хеммига это блочный код, позволяющий исправлять одиночные ошибки, разработанный в середине 1940-х годах Ричардом Хеммингом.
Рассмотрим классический пример:
Передавать будем следующее «1010», чтобы обнаружить ошибку в битах, нужно добавить 3 проверочных бита. Сгруппируем проверочные символы следующим образом:

Получаем:

знак означает сложение по модулю 2.

Теперь наши биты выглядят так: «1010011»
Получение кодового слова выглядит следующим образом:

=
здесь просто умножается наши 4 бита на столбики: 5,6 и 7, после каждого умножение на столбик складываем по модулю два, получаем аналогичный результат предыдущему.

Декодирование данных выглядит так:

Получаем:

называется синдромом последовательности.

Получение синдрома выглядит так:

=
здесь умножается все кодовое слово из 7 бит на столбцы, получаем синдром:

этот синдром указывает на то, что в кодовом слове нет ошибок.
Исказим один бит специально, заменим 0 на 1 в 4-й позиции и получим «1011011».
Посчитаем:

Наш синдром «011», по таблице ниже можно узнать в какой позиции ошибка:

Синдром	001	010	011	100	101	110	111
Ошибка в символе	r3	r2	i4	r1	i1	i3	i2

Из таблицы видно, что ошибка находиться в 4-й позиции.

На этом все, всего доброго.