9 Блоковые линейные помехозащитные коды
Курс “Теория информации и кодирования”

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

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

9.1 Понятие о блоковых линейных кодах

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

Конкретные свойства линейных кодов определяются областью их применения. Например:
  • код Хэмминга используется для коррекции ошибок в серверной памяти. Исходя из этого он должен исправлять наиболее вероятные одиночные ошибки и обладать высоким быстродействием. При этом длина кодовых слов фиксирована и невелика (обычно 4-8 байтов);
  • циклический CRC-код используется для обнаружения одиночных и групповых ошибок при хранении или передаче длинных кодовых блоков (например, при хранении на носителях или передаче по сети). При этом исправление ошибок обеспечивается за счет повторной передачи поврежденных блоков. Требования к быстродействию кода здесь не актуальны.

Общей основой построения линейных кодов является использование так называемой образующей матрицы G. Для блоков, включающих k информационных и m контрольных разрядов, такая матрица состоит из k строк и n=k+m столбцов — рисунок.

При этом все N = 2k разрешенных кодовых слов X1...XN являются линейными комбинациями строк этой матрицы (они могут быть получены суммированием по модулю 2 строк матрицы в разных сочетаниях). Одновременно сами строки образующей матрицы G должны быть линейно независимыми (ни одна из них не является суммой других в разных сочетаниях).
При построении матрицы G учитывается необходимое значение dmin (оно автоматически распространяется на весь код). Кроме того, вид матрицы задает дополнительные полезные свойства кода - например, способность обнаруживать локальные группы (“пачки”) ошибок.

На следующем рисунке приведены три примера образующей матрицы линейных кодов для длины информационного блока k=4:
  • матрица А) соответствует коду с проверкой на четность (здесь dmin=2);
  • матрица B) генерирует код Хэмминга с коррекцией однократных ошибок (dmin=3);
  • матрица C) отвечает циклическому CRC-коду, позволяющему обнаруживать “пачки” ошибок длиной до трех соседних разрядов (dmin=3).

В последних двух случаях полная длина кодового слова n=7 при числе информационных разрядов k=4. Такие параметры кода сокращенно записывают как 7,4.

Для матрицы Ga показано образование всех возможных кодовых слов как линейных комбинаций строк образующей матрицы. При этом полное количество допустимых кодовых слов 24=16. Четыре из них отвечают строкам образующей матрицы, а 12 образуются линейными комбинациями таких строк. Если например k=10 такое соотношение гораздо более выразительно: всего 10 строк матрицы позволяют задать 210=1024 кодовых слова. Таким образом, образующая матрица представляет компактный и удобный способ описания кода.

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

Контрольные вопросы
1) Какие помехозащитные коды называют блочными. Что означает термин линейные коды.
2) Приведите примеры различных требований к свойствам линейных кодов исходя из областей их применения.
3) Поясните принцип задания свойств линейных блочных кодов с помощью образующей матрицы. В чем преимущество такого способа.


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

Исходя из требований к быстродействию кода Хэмминга, применяется математический аппарат, основанный на векторном представлении кодовых слов: каждый i-й разряд кода представляется как элемент xi вектора X. Такой подход позволяет параллельно обрабатывать все разряды, что обеспечивает высокую скорость кодирования и декодирования.

В качестве условия принадлежности коду используется ортогональность кодового вектора X проверочной матрице U. Такая проверочная матрица состоит из m строк и n столбцов ортогональна образующей матрице G. Это означает, что любой вектор кода, задаваемого матрице G, будет также ортогонален U. Из данного условия следует система m линейных уравнений, включающих разряды кода xi (рисунок).

Уравнения ортогональности используются для кодирования и декодирования:
  • при кодировании - для нахождения m контрольных разрядов кода через k известных информационных разрядов (из m уравнений ортогональности, каждое из которых отвечает строке матрицы U);
  • при декодировании - для получения указателя на ошибочный разряд (в предположении, что ошибка может быть только однократной).

Поясним процедуру декодирования дополнительно:
  • если передача кодового слова прошла без ошибок, условие ортогональности кодового вектора X матрице U не нарушено и для всех разрядов zi=0 (i=1,m);
  • если произошла однократная ошибка, то для уравнений, в которых участвует ошибочный разряд zi=1. Вектор Z в этом случае является указателем на ошибочный разряд и последний может быть исправлен за счет его инверирования;
  • в случае многократных ошибок вектор Z очевидно не способен указать на них все и код не может такие ошибки исправить.

Рассмотрим эти общие положения на примере кода Хэмминга 7,4, образующая и проверочная матрицы которого показаны на рисунке.

Здесь образующая матрица G обеспечивает минимальное кодовое расстояни dmin = 3, что позволяет исправлять однократные ошибки. Проверочная матрица U отвечает условию ортогональности образующей матрице (это несложно проверить). При этом показанный на рисунке вариант матрицы U не единственный (всего таких вариантов 2m=8), однако именно он обеспечивает дополнительное удобство, которое мы позже сможем оценить.

Уравнения кодирования и декодирования для данного случая показаны на рисунке. Их особенности таковы:

  • при записи условий ортогональности вектора X матрице U в уравнениях участвуют только те значения xi, для которых ui не равны 0;
  • уравнения кодирования могут быть получены, если неизвестные значения контрольных разрядов (x5-x7) выразить через известные информационные разряды (x1-x4);
  • уравнения декодирования по своей структуре совпадают с исходными уравнениями ортогональности, где xi заменяются на yi, а вместо нулей в правых частях появляются значения zj. Поскольку уравнений m=3, вектор опознавтель Z может иметь 23=8 значений, из которых 7 указывают на номера ошибочных разрядов, а одно (Z=000) является признаком безошибочной передачи.

Рассмотрим теперь конкретный пример применения кода Хэмминга 7,4 (рисунок):

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

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

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

Контрольные вопросы
1) Почему в математическом аппарате кода Хэмминга используют векторное представление разрядов кода.
2) Поясните, как условие ортогональности кодового вектора проверочной матрице кода используется при кодировании и декодировании по Хэммингу.
3) Поясните получение уравнений кодирования и декодирования по Хэммингу исходя из заданной образующей матрицы кода.
4) Выполните пример кодирования, используя приведенные выше уравнения кода 7,4. В качестве информационных разрядов используйте двоичный код вашего номера в подгруппе по выполнению лабораторных работ.


9.3 Циклический код с обнаружением пачек ошибок

Как мы уже знаем, особенностью циклических кодов является соотношение строк образующей матрицы G: все они получаются в результате циклического сдвига одной ключевой строки. В примере на рисунке это первая строка матрицы. Структура ключевой строки может быть также представлена в виде полинома g(x) - рисунок.

Представление кода в виде вектора (строки матрицы G) и в виде полинома g(x) эквивалентны. Однако каждому из этих вариантов отвечает свой математический аппарат и, соответственно, свои ограничения. В частности, аппарат, базирующийся на применении полиномов, позволяет работать с длинными кодовыми словами и в то же время использует относительно «медленные» операции деления многочленов. Такие свойства хорошо подходят для кодирования блоков данных, которые передаются по компьютерным сетям или записываются на внешние носители. Еще одно преимущество данного подхода — возможность обнаружения длинных пакетов («пачек») ошибок, которые могут появляться при передаче по каналам связи, а также при хранении на магнитных или оптических носителях (максимальная длина гарантированно обнаруживаемой пачки равна числу контрольных разрядов).

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

Обозначим полиномы, принадлежащие циклическому коду, как f(x). Исходя из сказанного выше, процедура кодирования должна состоять в том, чтобы по заданным k информационным разрядам, постороить полином f(x), который нацело делится на образующий многочлен g(x).

Эта процедура включает такие шаги (рисунок):
  • к информационным разрядам кода x1-xk - многочлен b(x) - добавляется m “нулей” для последующего размещения контрольных разрядов. Это соответствует операции b(x) xm;
  • находится остаток r(x) от деления многочлена b(x) xm на образующий многочлен g(x). В дальнейшем этот остаток будет интерпретирован как контрольные разряды кода;
  • многочлен кода получается по формуле f(x) = b(x) xm + r(x). Остаток r(x), который «мешал» b(x) xm делиться на g(x), теперь компенсируется за счет сложения по модулю 2.

То, что описанная процедура гарантирует делимость f(x) на g(x), наглядно иллюстрирует рисунок.

Процедура декодирования включает деление полученного многочлена f*(x) на образующий. При этом, если свойство делимости на g(x) нацело подтверждается — остаток r*(x) =0, - это означает отсутствие ошибок. В противном случае f*(x) не совпадает с f(x), что означает наличие ошибок передачи.

Выбор образующего многочлена подчиняется следующим требованиям:
  • старшая степень многочлена g(x) равна m (это количество контрольных разрядов);
  • g(x) должен быть делителем так называемого модульного многочлена xn+1;
  • g(x) должен быть простым (делиться только на себя и на 1).

На практике образующие многочлены циклических кодов выбираются из готовых таблиц. При этом существуют определенные стандарты таких многочленов для использования в компьютерных сетях и на внешних носителях. В частности, для ленточных накопителей применяются полиномы с m=6, для глобальных сетей — с m=16, а для локальніх сетей — с m=32. Примеры стандартных многочленов — g(x) = x16+x12+x5+1 и g(x) = x16+x15+x2+1. Напомним, что такие коды позволяют гарантированно обнаруживать пакеты ошибок длиной до 16. Исправление обнаруженных ошибок выполняется повторной передачей искаженного кодового слова.
Применение таких кодов позволяет обеспечить вероятность обнаружения ошибок > 0.9999 при их коррекции за счет повторной передачи.

Рассмотрим пример кодирования и декодирования циклическим кодом 7,4. Для данного кода количество контрольных разрядов составляет m=3. Перечисленным выше требованиям отвечают всего два варианта образующего многочлена: g(x) = x3+x +1 и g(x) = x3+x2+1. В дальнейшем в примере используется первый из этих двух многочленов.

Пусть k=4 информационных разряда имеют значения 1010. На рисунке справа показана последовательность выполнения кодирования и декодирования согласно описанной выше процедуре:
  • информационному блоку 1010 отвечает многочлен b(x) = x3+x. Соответственно b(x)*x3= x6+x4;
  • контрольные разряды 011 отображают многочлен r(x) = x+1 - остаток от деления b(x)*x3 на образующий многочлен g(x)=x3+x2+1. В результате кодовый многочлен имеет вид f(x) = x6+x4+x+1;
  • при передаче без ошибок полученный кодовый многочлен f*(x) совпадает с переданным и потому остаток от его деления на образующий равен 0 (это признак правильной передачи);
  • при возникновении ошибок остаток от деления f*(x) на g(x) отличен от 0, что является признаком неправильной передачи. В примере видно, что таким образом обнаруживаются не только однократная ошибка в разряде 3, но и последовательность из трех ошибок в разрядах 1-3.

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

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


9.4 Коды БЧХ с заданными корректирующими свойствами

Рассмотренные выше коды ориентированы на конкретные частные результаты: код Хэмминга исправляет однократные ошибки, а циклический — обнаруживает пачки ошибок с заданным ограничением по их длине. Более общий подход — исправление ошибок любой заданной кратности — обеспечивают коды, созданные по методу Боуза, Чоудхури и Хоквингема (так называемые БЧХ-коды). К данному классу относится также популярный код Рида-Соломона, для которого вместо двоичных элементов могут использоваться например 16-ричные цифры. Эти коды получили ширкое практическое применение. Однако их математический аппарат сложен, поэтому мы рассмотрим их лишь на уровне принципов (рисунок).

Коды БЧХ являются подклассом циклических кодов и отсюда их свойства определяются образующим полиномом g(x). При этом сам такой полином строится специальным способом — исходя из заданного dmin (с учетом кратности исправляемых ошибок s) и длины кодового слова n. Такая длина должна отвечать условию n = 2m-1, где m – целое число. Свойства кода определяются тройкой значений (n, k, dmin). Например, обозначение (15, 7, 5) соответствует коду с длиной блока 15 разрядов, из которых 7 информационные, при этом его минимальное кодовое расстояние 5 позволяет исправлять все ошибки с кратностью s равной 1 и 2. Популярен код (255, 231, 7), который используют для обнаружения ошибок с кратностью до 6 включительно.

Процедура построения g(x) достаточно громозка. Она полно описана, например, [9.1-9.3]. Здесь лишь обозначим, что образующий многочлен строится исходя из заданных значений s, n на базе набора неприводимых многочленов fi(x), которые выбираются из справочных таблиц. Например, для упомянутого кода (15, 7, 5) образующий многочлен получается как g(x)=f1(x) f2(x) = (x4+x+1) (x4+x3+x2+x+1)= x8+x7+x6+x4+1.

Кодирование по заданному g(x) может выполняться по той-же процедуре, что и для любого циклического кода: «хвостовик» блока строится по многочлену r(x) – остатку от деления исходного кодового многочлена f(x) на образующий g(x). Декодирование также начинается с вычисления остатка полученного в результате передачи многочлена f*(x) на образующий. Однако в дальнейшем для выяснения расположения всех ошибок приходится использовать достаточно сложные процедуры. Различные алгоритмы решения такой задачи описаны в [9.1-9.3].

Важным частным случаем БЧХ-кодов является недвоичный код Рида-Соломона (РС). Здесь вместо двоичной переменной, значение которой соотвествует одному биту, могут применяться переменные значительно большей размерности. Например, используются коды с 16-ричной переменной, значение которой кодируется полубайтом. Популярны коды с 256-ричным основанием (значение представляется байтом). При том, что все процедуры для РС-кодов отвечают правилам БЧХ-кодов, их корректирующая способность значительно выше. Такие коды используются, например для восстановления данных, постардавших из-за царапин на оптических дисках.

Контрольные вопросы
1) В чем состоят основные особенности кодов БЧХ как подкласса циклических кодов.
2) Как строятся образующие многочлены БЧХ-кодов.
3) Каковы особенности кодирования и декодирования для кодов БЧХ.
4) Охарактеризуйте важнейшие особенности кодов Рида-Соломона как подкдасса кодов БЧХ.


9.5 Аппаратная реализация кода Хэмминга и циклического кода

Для кода Хэмминга уравнения кодирования и декодирования могут быть аппаратно реализованы в виде комбинационных схем (рисунок).

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

При практическом применении в 64-разрядной оперативной памяти серверов используются m=8 микросхем с количеством входных переменных при кодировании k=64, а при декодировании n=72. Это вполне приемлемый уровень сложности. Количество микросхем сумматоров определяется необходимым числом контрольных разрядов. Оно составляет log264+1=7, однако на практике принимается кратным байту.

Использование комбинационных схем означает, что работа кода максимально быстра. С другой стороны, необходимость аппаратной реализации накладывает ограничения на размер уравнений. Оба условия вполне подходят для применения кода в оперативной памяти.

На практике описанное решение реализуется в рамках контроллеров серверной оперативной памяти ECC (Error Correct Code). Оно обеспечивает исправление всех однократных ошибок, которые могут произойти во время хранения информации. Такое исправление выполняется контроллером в момент считывания данных. Поскольку все разряды хранятся в разных микросхемах, вероятность одновременной ошибки в более, чем одном разряде пренебрежимо мала.

Для циклического кода аппаратная реализация выполняется на базе регистров сдвига с обратными связями (пример на рисунке). Расположение обратных связей задано структурой образующего полинома g(x).

Обратим внимание на следующие общие особенности:
  • разрядность регистра равна m. То-есть, сложность схемы зависит только от длины "хвостовика" и никак не связана с длинами кодируемых блоков. На практике это означает, что такие схемы достаточно компактны;
  • в каждом такте деления элементы памяти (триггеры Ti) сохраняют значения, которые формируются на выходах сумматоров по модулю 2, после чего выполняется сдвиг. Это прямо соответствует рассмотренной выше математической процедуре деления;
  • остаток от деления многочленов формируется схемой за k тактов, то есть, за время, которое пропорционально длине кодируемого блока. При этом обработка выполняется по мере поступления информационных разрядов, то есть, формирование остатка не требует дополнительного времени;
  • в результате при использовании этой схемы для кодирования на регистре формируются контрольные разряды, которые затем передаются вслед информационным, а при декодировании полученный код указывает на правильность передачи (ошибок не было только если содержание регистра полностью нулевое).

Подобные схемы используются в составе контроллеров дисков, сетевых картах и модемах. Длина регистра — 16 или 32 разряда.

Контрольные вопросы
1) Поясните работу схем кодирования и декодирования по Хэммингу, приведенных на рисунке.
2) Определите, сколько элементов схем кодирования и декодирования потребуется для случая, когда количество информационных разрядов составляет 32.
3) Поясните работу схем кодирования и декодирования циклическим кодом, приведенных на рисунке.
4) Определите, сколько элементов памяти должен содержать сдвиговый регистр кодирования в случае, когда длина обнаруживаемой пачки ошибок должна составлять 8 разрядов.


Литература
9.1 Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования. Киев, издательское объединение «Вища школа», 1977, 280 с.
9.2 Бернард Скляр. Цифровая связь: Теоретические основы и практическое применение. Издательский дом "Вильямс", 2004, 1104 с.
9.3 В.В.Лидовский Теория информации. Учебное пособие. - М.: Компания Спутник+. 2004., 111 с.

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

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

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

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

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