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

в 22:12, , рубрики: алгоритм, Алгоритмы, Восстановление данных, помехоустойчивое кодирование, метки: ,

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

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

Предположим у нас есть канал связи 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-й позиции.

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

Автор: web_loki

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js