Почти всякий канал передачи данных предполагает шанс их искажения. В случае оптоволокна или изолированного ethernet-кабеля шансы не так высоки, тогда как при беспроводной передаче это случается постоянно.
Для решения этой проблемы возникает очевидная идея — передавать вместе с основной информацией какую-то вспомогательную, которая помогла бы найти ошибку или даже восстановить испорченный бит.
Самое простое решение — передавать каждый бит три раза. Это позволят исправить одну ошибку на каждый такой триплет. Однако это уменьшает пропускную способность канала в три раза.
Среди более сложных способов выделим два: линейное и блочное кодирование.
Линейное кодирование подразумевает, что мы вычисляем какую-то линейную функцию от блока битов, затем смещаем границы блока на несколько шагов вправо, вычисляем эту же самую функцию и так далее. Результаты вычислений этих функций передаются вместе с данными, а затем используются для проверки корректности переданный данных. Если при вычислении тех же самых функций принимающей стороной значения не сходятся — значит произошла ошибка и значение, возможно, надо заменить.
Блочное кодирование подразумевает, что мы передаём блок данных, а вместе с ним блок некий проверочной информации, вычисляемой из данных. Принимающая сторона сравнивает полученные проверочные данные с вычисленными заново и если они отличаются пытается восстановить значение ошибочных битов.
В современных стандартах связи идёт напряжённая борьба между двумя алгоритмами кодирования: Турбо-кодами и LDPC (проверки чётности с малой плотностью). Они имеют почти одинаковую производительность и качество кодирования.
Рассмотрим подробнее LDPC-коды. Для работы с ними понадобится определить граф Таннера.
Графами Таннера называют двудольные графы, множество вершин которых условно делят на проверочные и информационные. Информационные вершины соответствуют битам передаваемой инфомрации (как собственно информации, так и допольнительных данных для проверки ошибок), тогда как проверочные нужны для самого алгоритма кодирования.
Предполагается, что если сложить по модулю 2 все биты в информационных вершинах, связанных с конкретной проверочной вершиной — получим ноль. Проверочные данные выбираются таким образом, чтобы это ограничение соблюдалось.
После передачи битов через канал, мы проверяем, сохранилось ли ограничение. Если нет — значит произошла ошибка и мы можем итеративно восстановить её, распространяя вероятности ошибок из проверочных узлов, в которых не выполнилось условие чётности.
LDPC-коды применяются в стандартах WiFi, стандартах спутникового вещания, а так же являются сильными кандидатами на использование в протоколе 5G.