Помехоустойчивое кодирование с иcпользованием различных кодов / Хабрахабр. Это продолженеие статьи о помехоустойчивом кодировании, которая очень долго лежала в черновиках.

В прошлой части нет ничего интересного с практической точки зрения — лишь общие сведения о том, зачем это нужно, где применяется и т. В данной части будут рассматриваться некоторые (самые простые) коды для обнаружения и/или исправления ошибок. Итак, поехали. Попытался все описать как можно легче для человека, который никогда не занимался кодированием информации, и без каких- либо особых математических формул. Когда мы передаем сообщение от источника к приемнику, при передаче данных может произойти ошибка (помехи, неисправность оборудования и пр.). Чтобы обнаружить и исправить ошибку, применяют помехоустойчивое кодирование, т. Для кодирования на передающей стороне используются кодер, а на принимающей стороне — используют декодер для получения исходного сообщения.

Есть теорема, гласящая: порождающий многочлен циклического кода g(x) делит (x^n+1) без остатка. Где n – нашем случае размер . Теория помехоустойчивого кодирования базируется на результатах исследований. Циклические коды характеризуются тем, что при циклической . На практике активно применяются полиномиальные коды или циклические избыточные коды (Cyclic .

Циклические коды, кроме более простого декодирования, обладают и другими . Циклический код как разновидность группового кода. Уровень помехозащищенности циклического кода. Циклические коды — это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей коды .

Избыточность кода — это количество проверочной информации в сообщении. Рассчитывается она по формуле: k/(i+k), где k — количество проверочных бит,i — количество информационных бит. Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит — избыточность составит 1/(3+1) = 1/4 (2. Код с проверкой на четность. Проверка четности – очень простой метод для обнаружения ошибок в передаваемом пакете данных. С помощью данного кода мы не можем восстановить данные, но можем обнаружить только лишь одиночную ошибку.

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

Структурная схема кодера циклического кода с порождающим многочленом . Декодирование помехоустойчивых кодов может осуществляться тремя. В теории циклических кодов все преобразования кодовых .

В каждом пакет данных есть один бит четности, или, так называемый, паритетный бит. Этот бит устанавливается во время записи (или отправки) данных, и затем рассчитывается и сравнивается во время чтения (получения) данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно . Изменение этого бита (например с 0 на 1) сообщает о возникшей ошибке.

Ниже показана структурная схемы кодера для данного кода. Пример: Начальные данные: 1. Данные после кодирования: 1.

Принятые данные: 1. Как В Шарараме Получить Шарарам Карту. Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка. В случае изменения состояния двух битов, возможна ситуация, когда вычисление контрольного бита совпадет с записанным.

В этом случае система не определит ошибку, а это не есть хорошо. К примеру: Начальные данные: 1. Данные после кодирования: 1. Инструкция Конвекционный Электрогриль. Принятые данные: 1.

В принятых данных число единиц четно, и, следовательно, декодер не обнаружит ошибку. В частности, он разработал код, который обеспечивает обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительных проверочных бит.

Для каждого числа проверочных символов используется специальная маркировка вида (k, i), где k — количество символов в сообщении, i — количество информационных символов в сообщении. Например, существуют коды (7, 4), (1. Каждый проверочный символ в коде Хэмминга представляет сумму по модулю 2 некоторой подпоследовательности данных. Рассмотрим сразу на примере, когда количество информационных бит i в блоке равно 4 — это код (7,4), количество проверочных символов равно 3.

Классически, эти символы располагаются на позициях, равных степеням двойки в порядке возрастания: первый проверочный бит на 2. Пример работы алгоритма, так что особо подробно описывать в этой статье не вижу смысла.

Вместо этого приведу структурную схему кодера. Набор этих значений e. Декодер эти значения вычисляет, и если они все не равны 0 (то есть не получится 0. Коды- произведения.

В канале связи кроме одиночных ошибок, вызванных шумами, часто встречаются пакетные ошибки, вызванные импульсными помехами, замираниями или выпадениями (при цифровой видеозаписи). При этом пораженными оказываются сотни, а то и тысячи бит информации подряд. Ясно, что ни один помехоустойчивый код не сможет справиться с такой ошибкой.

Для возможности борьбы с такими ошибками используются коды- произведения. Принцип действия такого кода изображён на рисунке. Передаваемая информация кодируется дважды: во внешнем и внутреннем кодерах.

Между ними устанавливается буфер, работа которого показана на рисунке. Информационные слова проходят через первый помехоустойчивый кодер, называемый внешним, т. Здесь к ним добавляются проверочные символы, а они, в свою очередь, заносятся в буфер по столбцам, а выводятся построчно. Этот процесс называется перемешиванием или перемежением. При выводе строк из буфера к ним добавляются проверочные символы внутреннего кода.

В таком порядке информация передается по каналу связи или записывается куда- нибудь. Условимся, что и внутренний, и внешний коды – коды Хэмминга, с тремя проверочными символами, то есть и тот, и другой могут исправить по одной ошибке в кодовом слове (количество «кубиков» на рисунке не критично — это просто схема). На приемном конце расположен точно такой же массив памяти (буфер), в который информация заносится построчно, а выводится по столбцам. При возникновении пакетной ошибки (крестики на рисунке в третьей и четвертой строках), она малыми порциями распределяется в кодовых словах внешнего кода и может быть исправлена.

Назначение внешнего кода понятно – исправление пакетных ошибок. Зачем же нужен внутренний код?

На рисунке, кроме пакетной, показана одиночная ошибка (четвертый столбец, верхняя строка). В кодовом слове, расположенном в четвертом столбце — две ошибки, и они не могут быть исправлены, т. Для выхода из этой ситуации как раз и нужен внутренний код, который исправит эту одиночную ошибку. Принимаемые данные сначала проходят внутренний декодер, где исправляются одиночные ошибки, затем записываются в буфер построчно, выводятся по столбцам и подаются на внешний декодер, где происходит исправление пакетной ошибки. Использование кодов- произведений многократно увеличивает мощность помехоустойчивого кода при добавлении незначительной избыточности. P. S.: Плотно занимался этой темой 3 года назад, когда писал дипломный проект, возможно что- то упустил. Все исправления, замечания, пожелания — пожалуйста через личные сообщения.