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

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

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

10.1 Коды с проверкой четности

Проверка четности «по строкам»
Приступим к более детальному рассмотрению простых помехозащитных кодов с контролем четности. Напомним, что здесь контрольные разряды дополняют количество “1” в коде до четного.
На рис.10.1 показан пример использования такого способа при передаче одного байта данных:
  • при кодировании в примере 1 контрольный разряд получает значение 0, а примере 2 — значение 1 (в обоих случаях итоговое число 1 оказывается четным);
  • при декодировании в отсутствие ошибок сохраняется четность количества 1 и делается вывод о правильности передачи (строка 1);
  • в случае ошибки при передаче одного из разрядов кода четность кодичества 1 нарушается и декодер считает, что блок кода принят неверно (строка 2). Аналогичной будет ситуация для 3 ошибок (строка 4), а также для любого нечетного количества ошибок передачи;
  • если произошли одновременно две ошибки, то четность количества 1 сохраняется и декодер неправильно фиксирует, что передача прошла верно (строка 3). Такая же ситуация возникнет при любом четном количестве ошибок передачи.

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

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

Проверка четности «по строкам и столбцам»
Возможности кода четности могут быть значительно расширены, если его использовать для контроля последовательности строк. Пример такого способа показан на рис.10.2:
  • при кодировании разряды контроля четности добавляются в каждую строку кода, а также образуют дополнительную контрольную строку, где каждый разряд обеспечивает четность по столбцу;
  • при декодировании для одиночной ошибки можно определить не только строку, в которой она находится, но и номер ошибочного разряда (за счет контроля по столбцам). На практике, это означает, что такую ошибку можно исправить (инвертируя значение обнаруженного искаженного разряда);
  • кроме того в такой модификации кода обнаруживаются ошибки любой четной кратности по строке (они фиксируются за счет нарушения четности по столбцам). Правда, ошибки будут пропущены декодером, если они окажутся в вершинах усовного прямоугольника на поле разрядов кода (в этом случае сохраняется четность как по строкам, так и по столбцам), однако на практике такие ситуации возникают исключительно редко.

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

Восстановление поврежденных блоков с использованием контроля четности
Еще одна важная модификация кода с контролем четности используется для восстановления блоков поврежденных данных. Необходимым условием здесь является передача наряду с информационными блоками также дополнительного контрольного, разряды которого создаются по принципу четности. В примере на рис.10.3:
  • при кодировании по трем исходным блокам X1-X3 строится контрольный блок Y (дополнению до четности здесь отвечает операция суммирования по модую 2);
  • при передаче одного из блоков происходит одна или несколько ошибок (в примере это ошибка в блоке X3), что обнаруживается декодером;
  • за совместной обработки правильно переданных и контрольного блоков содержание поврежденного блока полностью восстанаваливается (в примере это обеспечивается суммированием по модулю 2 сток X1, X2, Y);
  • возможность исправления нескольких ошибок в ланном случае обеспечивается за счет учета дополнительного условия: известно, что все ошибки сосредоточены в одном блоке (строке). В таком случае контроль по столбцам однозначно выявляет позиции ошибочных разрядов.

На практике такой способ используется для резервирования и восстановления блоков архивных файлов и даже для восстановления содержимого отдельных поврежденных дисков в так называемых RAID-массивов серверов (это блоки из нескольких дисков, функционирующие как единое устройство). При этом, разумеется, для фиксации повреждения отдельной длинной “строки” могут использоваться значительно более мощные коды, чем рассмотренный нами код с проверкой четности. С ними мы познакомимся в дальнейшем.

Контрольные вопросы
1) Опираясь на рис.10.1, поясните особенности кода с проверкой четности по строке
2) В чем состоят преимущества и ограничения кода с проверкой четности по строке. Приведите примеры его использования на практике.
3) Опираясь на рис.10.2, поясните особенности кода с проверкой четности по строкам и столбцам
4) В чем состоят преимущества и ограничения кода с проверкой четности по строкам и столбцам. Приведите примеры его использования на практике.
5) Опираясь на рис.10.3, поясните особенности кода с восстановлением поврежденных блоков на основе проверки четности
6) В чем состоят преимущества и ограничения кода с восстановлением поврежденных блоков на основе проверки четности. Приведите примеры его использования на практике.


10.2 Корректирующая способность избыточных кодов

Кодовое расстояние по Хэммингу
Способность кода обнаруживать и корректировать ошибки во многом определяется параметром, который называют минимальным кодовым расстоянием по Хэммингу. Важно, что такой параметр может быть определен для любого кода (рис.10.4):
  • расстояние d по Хэммингу между двумя кодовыми блоками определяется как число несовпадающих разрядов. Выяснив значения dij для всех возможных пар блоков, можно найти его минимальную величину dmin. Такое значение является является атрибутом любого кода;
  • на рисунке показаны наборы трехразрядных кодовых блоков, для которых значения составляют 1 (безызбыточный код), 2 (код с четным количеством 1) и 3 (код с максимальной избыточностью). Как видно, значение dmin определяет “слабость” кода: именно в тех случаях, когда кодовое расстояние минимально, вероятнее всего может произойти ошибка распознавания;
  • нетрудно видеть, что при dmin=1 (блок А) принципиально невозможно выявить появление ошибки передачи: любое полученное содержание блока в принципе может быть верным (все значения кода разрешены). При этом избыточность отсутствует;
  • для dmin=2 (блок Б) к разрешенным относится только половина возможных значений кода (в данном случае — те, для которых соблюдается условие четности количества 1). При этом однократная ошибка уже гарантированно обнаруживается, поскольку значение кодового блока из набора разрешенных переходит в запрещенные;
  • для dmin=3 (блок В) всего четвертая часть значений относится к разрешенным. Такая избыточность позволяет не только распознавать, но и исправлять ошибки. Дело в том, что все значения, возникающие вследствие однократной ошибки, будут «ближе» по кодовому расстоянию к одному из разразрешенных значений. При этом возникновение однократной ошибки намного более вероятно, чем ошибок большей кратности. Соотвественно, исправление сводится к тому, что полученное запрещенное значение заменяется на ближайшее по величине d разрешенное.

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

Формулы для оценки корректирующей способности
Наиболее употребимыми параметрами корректирующей способности кода являются кратность гарантированно обнаруживаемых ошибок rm и кратность гарантированно исправляемых ошибок sm. Рис.10.7 позволяет формализовать связь этих параметров с величиной минимального кодового расстояния dmin:
  • слева на рисунке показано исходное разрешенное значение кода, которое соответствует переданным данным. Вследствие ошибок при передаче могут возникать запрещенные значения, которые распознаются кодом (на рисунке они показаны пунктиром). Ошибка распознавания появится, если в результате искажений при передаче возникнет одно из разрешенных значений кода, отличных от исходного (на рисунке справа);
  • для распознания ошибок передачи, достаточно, чтобы полученное значение было хотя бы на единицу кодового расстояния удалено от разрешенного. Отсюда следует условие rm=dmin-1. В нашем примере значения dmin=5 достаточно, чтобы распознавались ошибки вплоть до четвертой кратности (rm=4);
  • для исправления ошибок передачи необходимо, чтобы промежуточное запрещенное состояние было ближе к исходному, чем к любому другому разрешенному состоянию. В нашем примере состояние, возникшее в результате двукратной ошибки (sm=2) все еще ближе к исходному состоянию, чем к альтернативному, так что исправление возможно. Если рассмотреть случай dm=6, то дополнительное промежуточное состояние окажется равноудаленным от исходного и альтернативного, так что исправление трехкратной ошибки будет все еще невозможно. Отсюда следует формула sm=int [(dmin-1)/2] (здесь функция int означает отбрасывание дробной части). Для случаев dmin=5 и dmin=6 эта формула дает одинаковые значения sm=2.

Практическая оценка корректирующей способности кодов
Рассмотрим особенности применения полученных формул, а также дополнительные параметры корректирующей способности кода (рис.10.6):
  • как мы помним, код с проверкой четности по строке характеризуется значением dmin=2 и следовательно для него rm=1 (гарантированно обнаруживаются однократные ошибки), а sm=0 (исправление ошибок невозможно). Однако, нам известно, что такой код позволяет обнаруживать ошибки любой нечетной кратности.
    Здесь проясняется особенность полученных выше формул: значение rm характеризует нижний предел возможностей кода. Таким образом использование только значение rm и sm характеризует корректирующую способность кода не полностью;
  • для кода с проверкой по строке и по столбцу значение dmin определяется как произведение минимальных кодовых расстояний по строке и столбцу, таким образом здесь dmin=4. Отсюда следует rm=3 и sm=1. Действительно, такой код позволяет исправлять однократные ошибки, а в ситуации с четырехкратной ошибкой возможен “прокол”, когда она не однаруживается из-за того, что ошибки “в вершинах прямоугольника” сохраняют четность по строкам и столбцам. При этом реальные возможности такого кода, как мы уже знаем, могут далеко превосходить гарантированные ограничения.
  • то-же самое относится к способу кодирования с восстановлением поврежденных блоков, где при формальном значении dmin=4 (когда по строкам используется контроль четности, а не более мощные коды) возможно исправление многократных ошибок. Здесь опять-таки роль играют дополнительные условия кодирования (в данном случае — допущение о нахождении всех ошибок в одной строке).

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

Контрольные вопросы
1) Опираясь на рис.10.4, поясните понятие кодового расстояния по Хэммингу и минимального кодового расстояния.
2) Как в приведенных примерах проявляется связь минимального кодового расстояния, избыточности и корректирующей способности кода.
3) Поясните как на рис.10.5 отображается возникновение ошибок различной кратности.
4) Поясните смысл формул для определения гарантированной кратности обнаруживаемых и исправляемых ошибок передачи.
5) Как объяснить, что при значении rm=1 код с проверкой четности позволяет обнаруживать например ошибки кратности 3 и 5.
.

10.3 Понятие о линейных кодах

Принципы построения линейных кодов
Для построения избыточных помехозащитных кодов широко используется математический аппарат линейной алгебры (рис.10.7):
  • код как последовательность двоичных разрядов математически может быть представлен в двух разных формах. Во-первых, это вектор X, в котором все разряды x1 … xn независимы и могут обрабатываться параллельно. Во-вторых, это многочлен f(x), где все разряды имеют веса, связанные с их позицией, и могут обрабатываться только во взаимосвязи, а потому - последовательно. Выбор формы для описания конкретных кодов определяется требованиями к их применению (в частности, операции с векторами быстрее, а использование полиномов придает коду масштабируемость);
  • линейные преобразования включают только операции суммирования и умножения на постоянные коэффициенты. Для двоичных переменных такие коэффициенты могут иметь значения 0 или 1. Кроме того для суммирования используется операция сложения по модулю 2. Использование такой операции позволяет получать все результаты в пределах одного разряда;
  • в дальнейшем мы будем рассматривать в основном так называемые “систематические” коды, у которых информационные и контрольные разряды разделены: в общем случае последовательность из n кодовых разрядов включает k информационных и m контрольных (последние образуют так называемый “хвостовик”). Такой код часто обозначают парой параметров n,k. Например, запись 7,4 означает, что длины кодовых блоков n=7, при этом k=4 разряда в блоке — информационные (оставшиеся m=3 разряда контрольные). Данный подход позволяет упростить рассмотрение математического аппарата.

      Образующие матрицы линейных кодов
      Важным преимуществом линейных кодов является возможность их компактного задания с помощью так называемых образующих матриц (рис.10.8):
      • в общем виде образующая матрица G кода n,k включает k строк, которым отвечают n-разрядные вектора X1 – Xk. Все эти строки длиной n должны быть линейно независимыми (то-есть, ни одна из них не может быть получена линейными преобразованиями из остальных строк). Кроме того внутри матрицы G должно обеспечиваться заданное значение dmin;
      • замечательное свойство образующей матрицы в том, что все 2k разрешенных значения кода могут быть получены линейными преобразованиями ее строк. Таким образом матрица G компактно задает весь код. В примере на рис 10.8 для кода четности 5,4 матрица GA включает 4 строки X1 – X4, из которых линейными комбинациями получаются еще 12 оставшихся. При увеличении k эффективность такого способа возрастает. Например, если информационная часть блока включает 1 байт (k=8), то матрица из 8 строк определяет все 256 разрешенных значений кода;
      • вид образующей матрицы задает и дополнительные свойства кода. Так, матрицы GB и GC сходны по структуре (задают код 7,4) и обеспечивают значение dmin = 3. Однако, свойства кодов, которые они определяют, значительно различаются. Код Хэмминга (матрица GB) ориентирован на исправление ошибок в оперативной памяти компьютера, которые в силу ее организации с высокой веротяностью будут однократными. Циклический код (матрица GC) нацелен на обнаружение “пачек” ошибок в соседних разрядах, которые могут возникать при передаче по линиям связи. В последнем случае все строки матрицы могут быть получены из первой строки путем ее циклического сдвига. Это означает, что свойства кода определяются одной первой строкой. Ее описание в виде многочлена имеет вид g(x) = x3+x+1. Такой многочлен, как и матрица, называется образующим.
        Опираясь на описанный математически аппарат, мы можем теперь детально рассмотреть ряд популярных помехозащитных кодов.

      Процедуры кодирования и декодирования
      Общие подходы к процедурам кодирования и декодирования избыточными помехозащитными кодами отображает рис.10.9:
      • кодирование сводится к определению контрольных разрядов (“хвостовика”), которые бы вместе с информационной частью обеспечивали принадлежность всего кодового блока к разрешенным (то-есть, согласование с образующей матрицей). Например, для кода четности хвостовик включает всего один разряд xk+1 и его значение должно приводить весь блок к условию, когда в нем четное число 1 (математически это означает, что значение xk+1 определяется как сумма mod2 для k информационных разрядов);
      • декодирование означает нахождение так называемого “синдрома” ошибки. В случае, когда необходимо просто обнаружить ошибку, синдром может состоять из одного разряда. Например, для кода четности значение синдрома z определяется как сумма по модулю 2 всех n полученных разрядов кода yi. Если z=1 (условие четности нарушено), это указывает на ошибку передачи. Если требуется исправление, синдром должен указать на номера ошибочных разрядов. Например, для кода Хэмминга 7,4, который исправляет однократные ошибки, синдром включает 3 разряда и может иметь 23=8 значений. Семь из них соответствуют ошибкам в каждом из 7 разрядов блока, а восьмое значение указывает на правильную передачу;
      • при кодировании и декодировании могут использоваться различные математические процедуры, требования к которым определяются областью применения кода. Так, для исправления ошибок в оперативной памяти компьютера целесообразно использовать быстрые операции с векторами, а при последовательной передаче кода по линиям связи — более медленные, но масштабируемые операции с многочленами.

      Контрольные вопросы
      1) Используя рис.10.7, поясните, какие существуют формы математического описания кода. Каковы их преимущества и ограничения.
      2) Какие коды называют линейными. Поясните общий вид линейных преобразований и их особенности для двоичных переменных.
      3) Поясните общую структуру блока систематического кода. Почему в данном курсе рассматривается именно такой класс кодов.
      4) Поясните понятие образующей матрицы линейного кода. Какова ее структура.
      5) Опираясь на рис.10.8, поясните особенности образующих матриц приведенных здесь кодов. Как из образующей матрицы можно получить все разрешенные значения кода.
      6) Опираясь на рис.10.9, поясните понятия кодирования и декодирования для избыточных систематических помехозащитных кодов.


      10.4 Код Хэмминга с исправлением однократных ошибок

      Общая характеристика кода Хэмминга
      Код Хэмминга, как мы уже знаем, используется для исправления однократных ошибок в оперативной компьютерной памяти (на практике это решение используется для серверов, которые должны обладать повышенной надежностью). Особенности реализации такого кода характеризует рис.10.10:
      • исходя из требования высокой скорости обработки для кода Хэмминга применяются математический аппарат, ориентированный на векторы. Кроме того, с учетом организации оперативной памяти (разряды кодового слова хранятся здесь независимо) можно исходить из предположения, что ошибки в основном одиночны. Отсюда следует условие sm=1, а значит — dmin=3. Из того же предположения следует условие для определения числа контрольных разрядов: оно должно обеспечивать кодирование n=k+m возможных позиций ошибок, а также той ситуации, когда ошибки отсутствуют. Например, если k=32, то потребуется m=6 контрольных разрядов (26=64>32+6);
      • в основу процедур кодирования и декодирования положено условие ортогональности проверочной матрице кода U. Матрица U строится как ортогональная образующей матрице G (условием ортогональности является равенство нулю скалярных произведений всех строк этих матриц — см. рис.10.10). Поскольку все разрешенные значения кода Х должны соответствовать образующей матрице, они также будут ортогональны проверочной матрице U;
      • процедура кодирования сводится к нахождению m контрольных разрядов (“хвостовика”) исходя из m уравнений ортогональности искомого вектора X матрице U – см. рис.10.10. Процедура декодирования реализуется через проверку ортогональности полученного значения кода Y той же проверочной матрице U. При этом в разрядах, где ортогональность нарушена, вместо нулевых мы получем единичные значения разрядов zj. В совокупности код Z составит “синдром” ошибки, указывающий на позицию искаженного разряда.

      Постороение кода Хэмминга 7,4
      Для лучшего понимания рассмотрим пример построения кода Хэмминга 7,4, включая конкретные процедуры кодирования и декодирования (рис.10.11):
      • при постороении образующей матрицы G линейная независимость строк обеспечивается “диагнальным” расположением 1 в левой квадратной части матрицы. При этом условие dmin=3 обеспечивается выбором значений в правой части матрицы;
      • проверочная матрица U строится из условия ортогональности G при количестве строк m=3 (для проверки можно убедиться в ортогональности произвольной пары строк этих матриц). На самом деле приведенная на рисунке матрица U – лишь один из 8 вариантов, которые будут ортогональны G, при этом любой из них мог быть использован при кодировании. Однако выбранный вариант имеет некоторое дополнительное удобство, которое мы оценим в дальнейшем;
      • условия ортогональности произвольного вектора X матрице U определяются, если подставить в уравнения ортогональности конкретные значения ее элементов. Очевидно, что в уравнения войдут только те значения xij, для которых соответствующие uij=1 (умножение xij на 0 дает нулевой результат);
      • уравнения кодирования получатся, если в уравнениях ортогональности неизвестные значения контрольных разрядов x5-x7 выразить через известные значения информационных разрядов x1-x4. Это можно сделать, в частности, суммируя уравнения ортогональности по модулю 2 так, чтобы исключать некоторые неизвестные: например, просуммировав первое и второе уравнения ортогональности, можно получить уравнение для разряда x5, первого и третьего уравнений — для разряда x5, а по сумме всех трех уравнений ортогональности выразить значение x7;
      • уравнения декодирования по структуре соответствуют уравнениям ортогональности. Только теперь вместо исходных разрядов xij в них будут участвовать полученные в результате передачи yij. Поскольку последние могут содержать ошибки, в правых частях уравнений окажутся уже не фиксированные 0, а переменные zj, значения которых образуют синдром ошибки.

      Пример кодирования и декодирования по Хэммингу
      Пример использования кода Хэмминга 7,4 показан на рис.10.12:
      • пусть информационные разряды x1 - x4 имеют значения 1010;
      • используя уравнения кодирования, получим значения x5-x7 - 101;
      • пусть теперь при передаче возникла ошибка в разряде 3. Данный разряд присутствует в уравнениях 2 и 3, поэтому при декодировании будет получен код z1-z3 = 011;
      • полученное значение вектора Z является двоичным кодом номера ошибочного разряда 3, что позволяет исправить ошибку в данном разряде.

      Отметим, что условие "синдром ошибки равен двоичному номеру ошибочного разряда" в принципе не является обязательным. Важно, что каждое значение опознавателя однозначно соответствует определенному разряду. Однако, совпадение с двоичным номером создает дополнительное удобство. Его наличие определяется вариантом матрицы U (именно поэтому в данном примере использована матрица, показанная на рисунке).

      Обратим внимание, что значение Z=011 будет получено также при одновременном возникновении ошибок в разрядах 1 и 2. При этом код не только не исправит их, но и внесет новую ошибку (в разряде 6). Напомним, что в силу организации оперативной памяти одновременные ошибки в двух разных разрядах кодового слова происходят исключительно редко. В связи с этим подобная ситуация при построении кода не учитывается.

      Контрольные вопросы
      1) Обоснуйте требования к коду Хэмминга, исходя из области его применения
      2) Опираясь на рис.10.10, поясните что означает термин «ортогональность» и как условие ортогональности используется при построении кода Хэмминга.
      3) Используя рис.10.11, подтвердите ортогональность для произвольной пары строк матриц G и U для кода Хэмминга 7,4.
      4) Поясните, каким образом из вида проверочной матрицы U для кода Хэмминга 7,4 получаются уравнения ортогональности.
      5) Поясните как из уравнений ортогональности получаются уравнения кодирования из декодирования.
      6) Самостоятельно выполните пример кодирования и декодирования с применением показанных на рис.10.11 уравнений. В качестве информационных разрядов используйте двоичный код своего номера в списке подгруппы выполнения лабораторных.





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

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

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

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

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