Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Клодом Шенноном. Он сформулировал теорему для дискретного канала с шумом: при любой скорости передачи двоичных символов, меньшей, чем пропускная способность канала, существует такой код, при котором вероятность ошибочного декодирования будет сколь угодно мала.
Построение такого кода достигается путем введения избыточности. Такие коды называют избыточными или корректирующими. Корректирующие свойства избыточных кодов зависят от правил построения этих кодов и параметров кода (длительности символов, числа разрядов, объема избыточности и др.).
По сути, кодирование — это добавление к исходной информации дополнительной, проверочной информации. Для кодирования на передающей стороне используются кодер, а на принимающей стороне — используют декодер для получения исходного сообщения.
Избыточность кода — это количество проверочной информации в сообщении. Рассчитывается она по формуле:
k/(i+k), где
k — количество проверочных бит,
i — количество информационных бит.
Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит — избыточность составит 1/(3+1) = 1/4 (25%).
Код с проверкой на четность
Проверка четности – простой метод для обнаружения ошибок в передаваемом пакете данных. С помощью данного кода нельзя восстановить исходные данные, но можно обнаружить одиночную ошибку.
В каждом пакете данных есть один бит четности, или, так называемый, паритетный бит. Этот бит устанавливается во время записи (или отправки) данных, и затем рассчитывается и сравнивается во время чтения (получения) данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно . Изменение этого бита (например ,с 0 на 1) сообщает о возникшей ошибке.
Пример:
Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10110 (изменился второй бит)
Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка.
Этот метод служит только для определения одиночной ошибки. В случае изменения состояния двух битов, возможна ситуация, когда вычисление контрольного бита совпадет с записанным. В этом случае система не определит ошибку, а это не есть хорошо.
Например:
Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10010 (изменились 2 и 3 биты)
В принятых данных число единиц четно, и, следовательно, декодер не обнаружит ошибку.
Так как около 90% всех нерегулярных ошибок происходит именно с одиночным разрядом, проверки четности бывает достаточно для большинства ситуаций.
Код Хэмминга
Ричард Хэмминг разработал код, который обеспечивает обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительных проверочных бит. Для каждого числа проверочных символов используется специальная маркировка вида (k,i)=(2i-1, 2i-1-i), где k — количество символов в сообщении, i — количество информационных символов в сообщении.
Например, существуют коды (7, 4), (15, 11), (31, 26). Каждый проверочный символ в коде Хэмминга представляет сумму по модулю 2 некоторой подпоследовательности данных. Рассмотрим пример, когда количество информационных бит i в блоке равно 4 — это код (7,4), количество проверочных символов равно 3. Классически, эти символы располагаются на позициях, равных степеням двойки в порядке возрастания:
но можно и разместить их в конце передаваемого блока данных (тогда формула для их расчета будет другая). Рассчитаем эти проверочные символы:
r1 = i1 + i2 + i4
r2 = i1 + i3 + i4
r3 = i2 + i3 + i4
Итак, в закодированном сообщении получится следующее:
r1 r2 i1 r3 i2 i3 i4
Минимальное кодовое расстояние является важнейшей характеристикой помехоустойчивых кодов, указывающей на гарантируемое число обнаруживаемых или исправляемых заданным кодом ошибок.
e0,e1,e2 опрделяются как функции, зависящие от принятых декодером бит k1 — k7:
e0 = k1 + k3 + k5 + k7 mod 2
e1 = k2 + k3 + k6 + k7 mod 2
e2 = k4 + k5 + k6 + k7 mod 2
Набор этих значений e2e1e0 есть двоичная запись позиции, где произошла ошибка при передаче данных. Декодер эти значения вычисляет, и если они все не равны 0 (то есть не получится 000), то исправляет ошибку.
Пример работы кодера Хэмминга:
Имеется входная последовательность: 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 (16 бит)
Прежде всего, необходимо вставить контрольные биты. Они вставляются в строго определённых местах — это позиции с номерами, равными степеням двойки. В нашем случае это будут позиции 1, 2, 4, 8, 16. Соответственно, получилось 5 контрольных бит (выделены красным цветом):
0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1
Таким образом, длина всего сообщения увеличилась на 5 бит. До вычисления самих контрольных бит, мы присвоили им значение «0».
Вычисление контрольных бит.
Теперь необходимо вычислить значение каждого контрольного бита. Значение каждого контрольного бита зависит от значений информационных бит, но не от всех, а только от тех, которые этот контрольных бит контролирует. Закономерность такова: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N.
Знаком «X» обозначены те биты, которые контролирует контрольный бит, номер которого справа. К примеру, бит номер 12 контролируется битами с номерами 4 и 8. Чтобы узнать, какими битами контролируется бит с номером N надо просто разложить N по степеням двойки.
Вычисление значений контрольных битов: берём каждый контрольный бит и смотрим сколько среди контролируемых им битов единиц, получаем некоторое целое число и, если оно чётное, то ставим ноль (операция сложения по модулю 2), в противном случае ставим единицу.
Высчитав контрольные биты для нашего информационного слова получаем следующее:
1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1
Декодирование и исправление ошибок.
Допустим, закодированное первой частью алгоритма сообщение пришло с ошибкой. Например, 11-ый бит исказился:
1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1
Необходимо заново вычислить все контрольные биты (так же как и в первой части) и сравнить их с контрольными битами, которые мы получили. Так, посчитав контрольные биты с неправильным 11-ым битом мы получим
0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1
Контрольные биты под номерами: 1, 2, 8 не совпадают с такими же контрольными битами, которые мы получили. Сложив номера позиций неправильных контрольных бит (1 + 2 + 8 = 11), получаем позицию ошибочного бита.
Классификация помехоустойчивых кодов