Первая страница / Теория / Кодирование /

Циклические коды

Голосование: 29, 7

Общие сведения о принципах построения циклических кодов

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

(a1a2, …, an) → (ana1a2, …, an−1)

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

Эти свойства используются при построении кодов, кодирующих и декодирующих устройств, а также при обнаружении и исправлении ошибок.

Циклические коды — это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей коды Хэмминга, но в целом обеспечивающее большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправления ошибок, возникающих при передаче кодовых комбинаций по каналу связи. Циклический код относится к систематическим блочным (nk)-кодам, в которых k первых разрядов представляют собой комбинацию первичного кода, а последующие (n − k) разрядов являются проверочными.

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

При декодировании принятой n-разрядной кодовой комбинации опять производится деление на порождающий полином.

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

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

Пусть общее число бит в блоке равно n, из них полезную информацию несут в себе m бит, тогда в случае ошибки имеется возможность исправить s бит. Зависимость s от n и m для кодов можно найти [6] в таблице:

n, общее число бит m, число полезных бит s, число исправляемых бит
31 26 1
21 2
16 3
63 57 1
51 2
45 3
127 120 1
113 2
106 3

Увеличивая разность n − m, можно не только нарастить число исправляемых бит s, но открыть возможность обнаружить множественные ошибки. Процент обнаруживаемых множественных ошибок, можно найти [6] в таблице:

k, число полезных бит n − k, число избыточных бит
6 7 8
32 48% 74% 89%
40 36% 68% 84%
48 23% 62% 81%

Представление кодовой комбинации в виде многочлена

Описание циклических кодов и их построение удобно проводить с помощью многочленов (или полиномов). Запись комбинации в виде полинома понадобилась для того, чтобы отобразить формализованным способом операцию циклического сдвига исходной кодовой комбинации. Так, n-элементную кодовую комбинацию можно описать полиномом (n − 1) степени, в виде:

An−1(x) = an−1 xn−1 + an−2 xn−2 + … + a1 x + a0,

где ai = {0, 1}, причем ai = 0 соответствуют нулевым элементам комбинации, ai = 1 — ненулевым.

Запишем полиномы для конкретных 4-элементных комбинаций:

1101 ⇔ A1(x) = x3 + x2 + 1
1010 ⇔ A2(x) = x3 + x

Операции сложения и вычитания выполняются по модулю 2. Они являются эквивалентными и ассоциативными:

  • G1(x) + G2(x) ⇒ G3(x)
  • G1(x) − G2(x) ⇒ G3(x)
  • G2(x) + G1(x) ⇒ G3(x)

Примеры

  • G1(x) = x5 + x3 + x
  • G2(x) = x4 + x3 + 1
  • G3(x) = G1(x) ⊕ G2(x) = x5 + x4 + x + 1

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

  • G1(x) = x6 + x4 + x3
  • G2(x) = x3 + x2 + 1

x6 + x4 + x3       | x3 + x2 + 1
                  +------------
x6 + x5 + x3       | x3 + x2
------------
     x5 + x4
     x5 + x4 + x2
     ------------
              x2

Циклический сдвиг кодовой комбинации

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

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

Допустим, задана исходная кодовая комбинация и соответствующий ей полином:

a(x) = anxn−1 + an−1xn−2 + … + a2x + a1

Умножим a(x) на x:

a(x) · x = anxn + an−1xn−1 + … + a2x2 + a1x

Так как максимальная степень x в кодовой комбинации длиной n не превышает (n − 1), то из правой части полученного выражения для получения исходного полинома необходимо вычесть an(xn − 1). Вычитание an(xn − 1) называется взятием остатка по модулю (xn − 1).

Сдвиг исходной комбинации на i тактов можно представить следующим образом: a(x) · xi − an(xn − 1), то есть умножением a(x) на xi и взятием остатка по модулю (xn − 1). Взятие остатка необходимо при получении многочлена степени, большей или равной n.

Порождающий полином

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

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

V =    p(x)
p(x) · x − C2 (xn − 1)
p(x) · x2 − C3 (xn − 1)

p(x) · xm−1 − Cm (xn − 1)
  ,

где p(x) — исходная кодовая комбинация, на базе которой получены все остальные (m − 1) базовые комбинации, Ci = 0 или Ci = 1 («0», если результирующая степень полинома p(x) · xi не превосходит (n − 1), «1», если превосходит).

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

Порождающий полином должен удовлетворять следующим требованиям:

  1. p(x) должен быть ненулевым;
  2. вес p(x) не должен быть меньше минимального кодового расстояния: v(p(x)) ≥ dmin;
  3. p(x) должен иметь максимальную степень k (k — число избыточных элементов в коде);
  4. p(x) должен быть делителем полинома (xn − 1).

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

Для определения степени порождающего полинома можно воспользоваться выражением r ≥ log2(n+1), где n — размер передаваемого пакета за раз, т. е. длина строящегося циклического кода.

Примеры порождающих полиномов, можно найти [5] в таблице:

r, степень полинома P(x), порождающий полином
2 111
3 1011
4 10011
5 100101, 111101, 110111
6 1000011, 1100111
7 10001001, 10001111, 10011101
8 111100111, 100011101, 101100011

Алгоритм получения разрешенной кодовой комбинации циклического кода из комбинации простого кода

Пусть задан полином P(x) = ar−1 xr + ar−2 xr−1 + … + 1, определяющий корректирующую способность кода и число проверочных разрядов r, а также исходная комбинация простого k-элементного кода в виде многочлена Ak−1(x).

Требуется определить разрешенную кодовую комбинацию циклического кода (nk).

  1. Умножаем многочлен исходной кодовой комбинации на xr:
    Ak−1(x) · xr
  2. Определяем проверочные разряды, дополняющие исходную информационную комбинацию до разрешенной, как остаток от деления полученного в предыдущем пункте произведения на порождающий полином:
    Ak−1(x) · xr ⁄ Pr(x) ⇒ R(x)
  3. Окончательно разрешенная кодовая комбинация циклического кода определится так:
    An−1(x) = Ak−1(x) · xr + R(x)

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

Пример. Пусть требуется закодировать комбинацию вида 1101, что соответствует A(х) = х3 + х2 + 1.

Определяем число контрольных символов r = 3. Из таблицы возьмем многочлен P(х) = х3 + х + 1, т. е. 1011.

Умножим A(х) на хr:

A(x) · xr = (x3 + x2 + 1) · x3 = x6 + x5 + x3 ⇒ 11010000

Разделим полученное произведение на образующий полином g(х):

A(x) · xr ⁄ P(x) = (x6 + x5 + x3) ⁄ (х3 + х + 1) = х3 + х2 + х + 1 + 1 ⁄ (х3 + х + 1) ⇒ 1111 + 001 ⁄ 1011

При делении необходимо учитывать, что вычитание производится по модулю 2. Остаток суммируем с h(х) · хr. В результате получим закодированное сообщение:

F(x) = (x3 + x2 + 1) · (x3 + x + 1) = (x3 + x2 + 1) · x3 + 1 ⇒ 1101001

В полученной кодовой комбинации циклического кода информационные символы A(х) = 1101, а контрольные R(х) = 001. Закодированное сообщение делится на образующий полином без остатка.

Алгоритм определения ошибки

Пусть имеем n-элементные комбинации (n = k + r) тогда:

  1. Получаем остаток от деления Е(х) соответствующего ошибке в старшем разряде [1000000000], на порождающий полином Pr(x):
    E1(x) ⁄ Pr(x) = R0(x)
  2. Делим полученный полином Н(х) на Pr(x) и получаем текущий остаток R(x).
  3. Сравниваем R0(x) и R(x).
    • Если они равны, то ошибка произошла в старшем разряде.
    • Если нет, то увеличиваем степень принятого полинома на x и снова проводим деления:
      H(x) · x ⁄ Pr(x) = R(x)
  4. Опять сравниваем полученный остаток с R0(x).
    • Если они равны, то ошибки во втором разряде.
    • Если нет, то умножаем Н(х) · х2 и повторяем эти операции до тех пор, пока R(x) не будет равен R0(x).

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

Например: H(x) · x3 ⁄ Pr(x) = R0(x)

БЧХ

Французский ученый А. Хоквингем (1959 г.) и американцы Р. К. Боуз и Д. К. Рой-Чоудхури (1960 г.) нашли большой класс кодов, обеспечивающий произвольное минимальное кодовое расстояние dmin ≥ 5. Они получили название БЧХ (Боуза-Чоудхури-Хоквингема). Порождающие полиномы для таких кодов в зависимости от предъявляемых к ним требований, можно найти [7] в таблице:

k n m s dmin Порождающий полином
Символическая запись Запись в виде полинома
37413131011
41511132310011
815713721111010001
1015537246710100110111
531261345100101
10312125355111101101001
153116371076571000111110101111
2531115115423325101100010011011010101

Где n — общее число элементов, m — число информационных элементов, k — число избыточных элементов (n = m + k).

Процедура построения кода БЧХ по заданным M и dmin:

  1. по dmin найти значение, при котором обеспечивается необходимое число информационных элементов m при минимальной избыточности kmin;
  2. найти в таблице соответствующий порождающий полином;
  3. если dmin четное, умножить найденный полином на (x + 1);
  4. если mтабл >> mзадан, то можно перейти к укороченному циклическому коду, вычеркивая в порождающей матрице исходного кода с параметрами mтабл, kmin (mтабл − mзадан) столбцов слева и столько же строк сверху.

Визуализатор

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

Обзор источников

В книгах [1], [2] и на сайтах [3], [4] представлены теоретические сведения, способы построения, а также примеры использования циклических кодов.

На сайтах [5], [6], [7], в основном, представлены практические исследования, их некоторые результаты, интересные зависимости и таблицы по циклическим кодам.

Литература

  1. Вернер М. Основы кодирования. — М.: Техносфера, 2004.
  2. Питерсон В., Уэлдон Ф. Коды, исправляющие ошибки. — М.: Мир, 1976.
  3. http://informkod.narod.ru/5_5item.htm
  4. http://yourtutor.narod.ru/cyclic/CyclicCodes.htm
  5. http://dvo.sut.ru/libr/opds/i285vino/2.htm
  6. http://book.itep.ru/2/28/corec_28.htm
  7. http://stor.boom.ru/uch/din/1/15/153.htm

Вадим Козлов


Данил / 2009-11-11 19:00:06

Очень хорошая статья, мне помогла.

Есть пара заметок по ошибкам.

>>>7. http://stor.boom.ru/uch/din/1/15/153.htm

статья переместилась сюда - http://stor.boom.ru/InfoTeory/1/15/153.htm

>>> Таблица БЧХ, взятая с приведеного выше сайта.

Строка

25 31 11 5 11 5423325 101100010011011010101

скорее всего содержит ошибку в первом числе - вместо 25 должно быть 20 (по определению, k = количество_бит_в_полиноме - 1, а также должно выполняться условие k+m = n).

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий