7. Основы помехозащитного кодирования
Курс “Теория информации и кодирования”

Уровень кодирования с защитой от ошибок
Коррекция ошибок избыточным кодированием
Потоковое и блоковое избыточное кодирование
Помехозащитное кодирование на примере контроля четности
Оценка вероятности правильной передачи
Оценка корректирующей способности кодов
Исправление ошибок повторной передачей
Направления практического использования помехозащитных кодов

7.1 Уровень кодирования с защитой от ошибок

До сих пор мы рассматривали методы кодирования, направленные на устранение избыточности исходного (первичного) кода сообщений. Этот уровень принято называть “кодированием Источника” (рисунок). Его цель состоит в том, чтобы максимально приблизить среднюю длину кода знака к величине энтропии Источника.

Теперь нам предстоит изучить коды, которые обеспечивают защиту от ошибок, возникающих в канале передачи. Они составляют отдельный слой или уровень, который называется “кодированием Канала”.

На этом уровне избыточность наоборот искусственно вводится в код в виде контрольных разрядов, которые позволяют обнаруживать и исправлять ошибки передачи. Такие “накладные расходы” неизбежно снижают пропускную способность канала.

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

Познакомимся с методами кодирования, которые реализуют такой подход.

Коррекция ошибок избыточным кодированием

Рассмотрим простейший случай передачи одного информационного двоичного разряда кода. Если при его передаче возникнет ошибка, распознать ее будет невозможно, поскольку Декодер не в состоянии отличить правильное значение разряда от неверного (рисунок).

Однако, уже использование одного контрольного разряда, в котором повторяется значение информационного («00» вместо “0” или “11” вместо “1”), позволяет обнаруживать возможную ошибку, поскольку при ее появлении полученные значения двух разрядов будут различаться (может быть получено «01» или «10») - рис.

Если значение информационного разряда дублировать дважды, то ошибку можно будет исправить по принципу «похожести». Действительно, если полученный код содержит одну «1» и два «0», то они могли появиться в результате искажения исходного кода “000” одиночной ошибкой . Напротив, если получен код с двумя «1», то он «ближе» к «111» - рис.

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

При этом правила использования избыточного кода опираются на тот факт, что одновременное появление большего количества ошибок значительно менее вероятно.

Разумеется, за это приходится платить уменьшением скорости передачи информации.

7.3 Потоковое и блоковое избыточное кодирование

Избыточное кодирование применяется в двух вариантах (рисунок):
- потоковое кодирование предусматривает выделение контрольных разрядов по мере поступления информационных;
- в блоковом кодировании контрольные разряды защищают целый блок информации.

На практике находят применение оба способа. При этом очевидно, что блоковое кодирование требует меньшей избыточности, а потоковое — более “оперативно” реагирует на появление ошибок.

Принято обозначать число информационных разрядов в блоке буквой k, количество контрольных — буквой m, а общую длину блока — буквой n. Часто блок избыточного кода характеризуют парой n,k – рис.

Например обозначение, «код 7,4» подразумевает, что каждый блок такого кода включает 4 информационных и 3 контрольных разряда (общая длина блока 4+3=7).

Для потоковых кодов принимается k=1. Соответственно, рассмотренные выше примеры кодов с одним или двумя контрольными разрядами на один информационный, могут быть обозначены как 2,1 и 3,1

Отношение R=n/k характеризует избыточность кода.

7.4 Помехозащитное кодирование на примере контроля четности

Простейшим блоковым помехозащитным кодом, который широко применяется на практике, является код с проверкой четности.

При кодировании блока длиной k он формирует один контрольный разряд (n=k+1), значение которого дополняет количество «1» в блоке до четного.

При декодировании нарушение условия четности количества «1» трактуется как признак ошибки, а соблюдение этого условия — как признак правильности передачи.

Очевидно, что при этом код распознает все ошибки нечетной кратности (1, 3, 5 и т.д) и не распознает ошибки нечетной кратности (2, 4 и т. д.).

Такой код применяется, в частности, в com-портах настольных ПК, обеспечивающих передачу данных от клавиатуры к системному блоку.

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

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

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

На практике «матричный» код широко использовался в накопителях информации на магнитных лентах (в частности, стримерах).

9.5 Оценка вероятности правильной передачи

Рассмотрим оценки вероятности безошибочной передачи блоков кода для наиболее распространенного на практике случая «симметричного» канала, где вероятности ошибочной передачи 0→1 и 1→0 одинаковы (обозначим вероятность безошибочной передачи как p, а вероятность ошибки - q). При этом ошибки в разных разрядах считаются независимыми.

Для такого случая вероятность передачи блока длиной n с j ошибками может быть определена по формуле Бернулли (рисунок):

Рассмотрим несколько примеров.

Пример 1. Пусть вероятность ошибочной передачи одного разряда q=0,01. Определим вероятность безошибочной передачи 100 разрядов подряд.
Согласно формуле (9.1) P100 (0) = C1000 p100 q0 = 0,99100 = 0,362. Таким образом, вероятность безошибочной передачи 100 разрядов при p=0,99 составляет всего около 36%. Это наглядно подтверждает необходимость использования помехоустойчивого кодирования.

Пример 2. Для q=0,01 определим вероятность пропуска ошибки при передаче четырех разрядов кода в безизбыточном варианте (код 4,4) и с контролем четности (код 5,4).
При передаче безизбыточным кодом вероятность ошибки Pпр=1- P4 (0) = 1-0,994 = 0,049
При контроле четности пропускаются только двойные и четырехкратные ошибки, вероятности которых составляют:
- P5 (2) = С52 p5-2 q2 = 10х0,993х0,012 = 0,00097030
- P5 (4) = С54 p5-4 q4 = 5х0,991х0,014 = 0,00000005
Таким образом для кода спроверкой четности вероятность пропуска ошибки Pпр = 0,00097035 — примерно в 50 раз меньше, чем для без-избыточного кода.

7.6 Оценка корректирующей способности кодов

Корректирующую способность кода принято оценивать прежде всего по кратности гарантированно обнаруживаемых и исправляемых ошибок (rm и sm).

В целом, чем выше доля контрольных разрядов, тем больше корректирующая способность кода. Однако, эта зависимость не прямая. Для ее строгой оценки используют параметр кода минимальное кодовое расстояние по Хэммингу (dmin).

Кодовое расстояние d между двумя блоками кода по Хэммингу — это количество несовпадающих разрядов (например, для кодов 0110 и 1100 d=2) — рисунок.

Для полного набора разрешенных кодовых блоков определяется минимальное значение кодового расстояния — dmin.

Например, для без-избыточного кода dmin =1, для кода с проверкой четности dmin =2, а для упоминавшегося выше кода Хэмминга с коррекцией однократных ошибок dmin =3.

Связь между значением dmin и кратностью обнаруживаемых и исправляемых ошибок (rm, sm) отображена на рисунке.

Важно, что значение dmin определяет минимальную гарантированную кратность обнаруживаемых и исправляемых ошибок. При этом код может обнаруживать и ошибки большей кратности. Так, например, код с контролем четности обнаруживает ошибки нечетной кратности >1 (3, 5 и т. д.), но пропускает ошибки кратности 2. Это вполне соответствует его значению dmin =2, при котором rm =1.

7.7 Исправление ошибок повторной передачей

Как мы убедились выше, исправление однократных ошибок требует значительно большей избыточности, чем просто их обнаружение. Действительно, чтобы исправить однократную ошибку в блоке, необходимо точно определить номер разряда, в которой она произошла. Если необходимо исправлять также двукратные (в общем случае - многократные) ошибки, задача значительно усложняется, поскольку необходимо учитывать все их возможные сочетания.

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

Передатчик формирует блок избыточного кода и передает его по Прямому каналу связи, сохраняя у себя в памяти копию.

Приемникпроверяет блок на наличие ошибки и возвращает результат проверки по Обратному каналу.

Если блок принят без ошибок, Передатчик стирает его копию из памяти, а если ошибки обнаружены — повторяет передачу до тех пор, пока блок не будет принят верно.

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

При этом обратный канал как правило уже существует в системе связи (в частности, потому, что передача сообщений как правило является двухсторонней).

7.8 Направления практического использования помехозащитных кодов

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

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

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

Для защиты данных в оперативной памяти серверов применяются блоковые коды с исправлением ошибок (поскольку здесь хранение копий привело бы к удвоению требуемого дефицитного объема памяти).

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

Таким образом, на практике применяется широкий спектр помехоустойчивых кодов, свойства которых мы изучим теперь более подробно.
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP