ЧАСТЬ 3 ДВОИЧНЫЕ ЦИКЛИЧЕСКИЕ КОДЫ И КОДЫ БЧХ

Цель этой части состоит в том, чтобы дать минимальный набор понятий, необходимых для понимания конструкции циклических кодов и эффективной реализации их алгоритмов кодирования и декодирования. Кроме того, в этой части дается введение в двоичные коды БЧХ. Коды Боуза-Чоудхури-Хок-Вингема (БЧХ) относятся к семейству циклических кодов, обладающих четкой алгебраической структурой, которая существенно упрощает процедуры кодирования и декодирования. Двоичные БЧХ коды сминимальным расстоянием 3, известные также как коды Хемминга, имели широкое применение в компьютерных сетях и устройствах памяти из-за простого и быстрого кодирования и декодирования. Кроме того, укороченные (48, 36, 5) БЧХ коды использованы в Американской сотовой системе с временным разделением каналов (TDMA, стандарт IS-54).

3.1. Двоичные циклические коды.

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

3.1.1. Порождающий и проверочный полиномы.

Обозначим С линейный блоковый (n, k)код. Пусть u сообщение и v соответствующее ему кодовое слово кода С. Циклические

Рис. 16 Циклический регистр сдвига

коды обладают свойствами, которые делают их удобными для аппаратурной (микросхемной) реализации. Сопоставим каждому кодовому слову v полином v(x):

Переменная х служит индикатором относительного положения элемента v_i в кодовом слове в виде терма (монома) v_ixⁱ полинома v(x).

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

В полиномиальном представлении циклический сдвиг на одну позицию, обозначенный v¹(x), соответствует умножению на x по модулю (х^п — 1),

Операция циклического сдвига реализуется на регистре сдвига, показанном на Рисунке 16.

Пример 19.Рассмотрим случай п = 7. Циклический сдвиг на одну позицию вектора v = (0101011) равен v⁽¹⁾ = (1010101). В полиномиальном представлении и двоичной арифметике получаем:

3.1.2. Порождающий многочлен

Важным свойством циклических кодов является то, что все кодовые слова-полиномы кратны одному фиксированному полиному g(x), который называется порождающим полиномом кода. Этот полином (многочлен), как и всякий другой, задается своими корнями, которые обычно называют нулями кода. Легко показать, что порождающий полином g(x) является делителем бинома (х^п - 1). (По аналогии с целыми числами «а(х) делит b(х)» (иначе b(х)/a(х)), если b(x) = a(x) q(x).) Таким образом, для того, чтобы найти некоторый порождающий многочлен, надо знать разложение бинома (х^п - 1) на неприводимые множители φ_j(x) ,j = 1, 2, ..., s

(3.1)

Заметим, что в двоичной арифметике операции а + b и а — b (по модулю 2) дают одинаковый результат. Так как ниже рассматриваются только двоичные коды или коды над конечными полями характеристики два, т.е. использующие двоичную арифметику, то в дальнейшем мы не будем различать эти операции (т.е. знаки «+» и «-»).

Из вышесказанного следует, что

(3.2)

Пример 20.На множестве двоичных многочленов, т.е. полиномов с коэффициентами из Z₂={0,1}, бином х⁷ - 1 имеет следующее разложение,

Приведем примеры циклических кодов длины 7.

· Двоичный циклический (7,4,3) код Хемминга с порождающим полиномом g(x) = х³ + х + 1.

· Двоичный циклический (7,6,2) код с проверкой на четность порождается полиномом g(x) = (х + 1).

· Дуальный коду Хемминга двоичный (7,3,4) код (код максимальной длины) имеет порождающий многочлен g(x) = (х + 1)(х³ + х + 1).

3.1.3. Кодирование и декодирование двоичных циклических кодов.

Размерность двоичного циклического (n, k) кода равна

где deg[.] есть степень аргумента. Так как циклический код С является линейным кодом, то любое множество kлинейно независимых векторов (кодовых слов) может быть выбрано в качестве порождающей матрицы кода. В частности, двоичные векторы, ассоциированные с многочленами g(x), xg(x), ..., х^k-1g(x), линейно независимы. Эти векторы могут быть использованы в качестве строк порождающей матрицы кода С. В этом случае реализуется несистематическое кодирование. Другими словами, сообщение не появляется в неизмененном виде на каких-либо позициях кодового слова.

Пример 21.Рассмотрим циклический (7,4,3) код Хемминга с порождающим полиномом g(x) = х³ + х+1 (1101). Порождающая матрица этого кода имеет вид:

где первый столбец соответствует x⁰ степени, а последний x⁶ степени.

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

С их помощью реализуется систематическое кодирование, показанное в примере ниже.

Пример 22.Пусть С циклический (7,4,3) код Хемминга с порождающим многочленом g(x) = х³ + х + 1. Тогда имеем (делим x⁶ на (x³+x+1) получаем (x³-x-1) и остаток x²+1 с учётом того, что сложение идёт по модулю 2 ):

Следовательно, систематическая порождающая матрица кода С имеет вид:

(первый столбец соответствует степени х⁶, а последний x⁰)

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

• Несистематическое кодирование

(3.3)

Для кода С(7, 4, 3) с порождающим полиномом g(x) = х³ + х + 1 найдём кодовое слово v(x), соответствующее информационной посылке u(1,0,1,0), т.е.u(x) = 1 + x². Найдём v(x) используя выражение(3.3) v(x)=u(x)g(x)=1+x+x²+x⁵ , что соответствует кодовому слову v(1,1,1,0,0,1,0). Этот же результат можно получить, воспользовавшись матрицей G из примера 21.

• Систематическое кодирование

(3.4)

Для кода С(7, 4, 3) с порождающим полиномом g(x) = х³ + х + 1 найдём с помощью выражения (3.4) кодовое слово v(x) соответствующее информационной посылкой u(0,1,0,1), т.е. u(x) = x² +1, тогда v(x)=x³u(x) + x³u(x)mod(g(x))= x⁵+x³+x², что соответствует кодовому слову v(0,1,0,1,1,0,0). Этот же результат можно получить, воспользовавшись матрицей G из примера 22.

3.1.4. Проверочный полином.

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

g(x)h(x)=xⁿ+1 (3.5)

Если известен порождающий полином, то проверочный полином легко вычисляется как h(х)= (хⁿ + 1) /g(x) = h₀ + h₁x + ... +h_k x^k. Проверочную матрицу кода С легко построить, используя в качестве строк п-k-1циклических сдвигов проверочного полинома,

(3.6)

Теперь рассмотрим схемную реализацию деления двоичных мно­гочленов в общем случае. Пусть заданы: делимое степени m

f(X) = f₀ + f₁X + f₂X² + … + f_mX^m (3.57)

и делитель степени r, причем, r < m

. (3.58)

В результате деления мы должны получить разложение

f(X) = а(Х) (Х) + b(Х) (3.59)

с сомножителем а(Х) степени т — r и остатком b(Х) со степенью, на превышающей r — 1.

Схема деления многочленов общего вида представлена на рис. 3.6.

Сначала регистр сдвига полностью загружается старшими раз­рядами делимого. Ключ S1 включен, а переключатель S2 находится в верхнем положении. Далее начинается сам процесс деления. В пер­вом такте производится сдвиг содержимого регистра на один разряд вправо. Так как f_т = 1, эта единица, в соответствии с коэффициен­том двигателя (Х), суммируется с аналогичными разрядами дели­мого. В результате, мы получаем укороченный многочлен

(3.60)

со степенью

. (3.61)

Рис. 3.6. Схема деления многочленов f(х) : (х) = = а(х) (х) + b(х).

На последующих l = т - r тактах алгоритм деления остается таким же. Так, если степень укороченного многочлена (X) в (3.60), равная k₁ (3.61), остается большей и равной r, то с помощью цепи об­ратной связи производится укорочение теперь уже многочлена из (3.60).

(3.62)

со степенью

. (3.63)

Таким образом, после l = т — r тактов мы получаем разложение (3.59), причем, в регистре делимого находится остаток от деления b(Х). После этого, ключ S1 размыкается, переключатель S2 перево­дится в нижнее положение и на следующих r тактах остаток b(Х) заносится в регистр формирователя остатка.

Пример 23.Циклический (7,4,3) код Хемминга с порождающим многочленом g(x)=x³+x+1 имеет проверочный многочлен h(x) = (х⁷ + 1)/(х³+x+1) = x⁴ +x²+x + 1. Проверочная матрица этого кода имеет, например, следующий вид:

Так же как и для линейных кодов, систематическое кодирование циклического кода можно реализовать как решение уравнения

Рассмотрим следующее правило систематического кодирования. Предположим, что код имеет скорость k/п ≤ 0,5. Пусть сообщение представлено многочленом и(х) = u₀ + u₁x +… + и_k-1х^k-1, степень которого меньше k. Пусть v(x) кодовое слово кода С, соответствующее информационному многочлену и(х). На первом шаге v_l = и_l l = 0, 1, ..., k - 1.

Из циклической природы этого кода следует, что проверочные символы кода v_l, l = к, к+1,..., п - 1, могут быть вычислены рекурсивно с помощью проверочного уравнения

(3.7)

Рис. 17. Устройство систематического кодирования делением на g(х).

где h_(l-k),j есть j-ый элемент (l - к)-ой строки матрицы (3.6).

В случае высокой скорости кода, к/п > 0,5, кодирование с помощью деления х^n-kки(х) на порождающий полином эффективнее. В любом случае, кодовое слово получается в систематической форме, kпервых символов которого совпадают с символами сообщения, а последние п-к являются проверочными символами.

На Рисунке 17 показана структурная схема кодера двоичного кода с порождающим полиномом g(x). Первые kтактов переключатель (правая нижняя часть схемы) находится в положении 1, а информационные символы передаются в канал связи и одновременно вводятся в схему умножения на х^n-k и деления на порождающий многочлен g(x). За эти kтактов в регистре сдвига вычисляется остаток от деления, после чего переключатель переводится в положение 2 и содержимое регистра передается в канал.

Дуальные циклические коды и последовательности максимальной длины

По аналогии с линейными кодами, дуальным кодом циклического кода С, порождаемого полиномом g(x), является циклический код С┴, порождаемый полиномом h(х). Важный класс циклических кодов, словами которого являются все сдвиги последовательности максимальной длины (MLS), дуален циклическому коду Хемминга. Множество сдвигов MLS является (2^т – 1, m, 2^m-1) циклическим кодом, который порождается полиномом g(x)=(xⁿ - 1 )/p(x), где р(х) примитивный полином. В дальнейшем этот код будем называть MLS-код.

3.1.5. Укороченные циклические коды и CRC коды

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

Например, нужна простая FEC/ECC схема для обнаружения/исправления двоичных одиночных ошибок в информационном блоке длиной 64 символа. Задача состоит в том, чтобы найти или выбрать (ЕСС) схему кодирования для исправления однобитовой ошибки, используя не более 8 избыточных символов, т.е. при максимальной длине кода 72 (64 информационных и 8 проверочных) символа».

Так как 72 не является числом вида 2^т — 1, то, очевидно, не существует подходящего циклического кода, среди тех, с которыми мы уже познакомились. Одним из возможных решений может быть использование циклического (127, 120, 3) кода Хемминга, укороченного до необходимой размерности 64. Этот вариант дает укороченный (71, 64, 3) код Хемминга.

Укорочение (в обсуждаемом здесь варианте) сводится к отбрасыванию информационных позиций исходного кода. Пусть s есть число неиспользуемых информационных символов, которое называют глубиной (длиной) укорочения. Пусть С циклический (п, k, d) код. Укороченное сообщение получается за счет фиксированной установки нулевых значений в некоторых (произвольных) информационных позициях. Остальные k-s позиций могут принимать произвольные значения. Без потери общности, можем считать, что старшие позиции сообщения устанавливаются в нулевые состояния. Тогда и(х) = и₀ + u₁x +...+u_k-1-sx^k-1-s. Данное сообщение преобразуется систематическим кодером в кодовое слово,

степень которого не превышает n-s-1. Таким образом, укороченный код Су является линейным (n-s, k-s, d_s) кодом с кодовым расстоянием d_s ≥ d. В общем случае укороченный код не остается циклическим кодом.

Пример 24. Пусть С циклический (7,4,3) код Хемминга с порождающим полиномом 1 + х + х³. Новый код, полученный из С установкой в нулевое состояние двух старших информационных разрядов, имеет два информационных символа и три проверочных, вычисляемых кодером кода С. Множество полученных кодовых слов образует укороченный линейный (5,2,3) код.

Фундаментальное свойство укороченных циклических кодов C_s состоит в том, что могут быть использованы те же самые кодеры и декодеры, хотя эти коды и не сохраняют устойчивость к циклическому сдвигу. Для компьютерного моделирования гораздо проще дополнять слова нулями на старших позициях и использовать те же самые алгоритмы кодирования и декодирования, которые обсуждаются в этом пособии. Этот способ (дополнения нулями) широко используется в микросхемной реализации кодов Рида-Соломона. Очевидно, что нули на старших позициях сообщения не должны включаться в кодовое слово. Более того, декодер модифицируется так, что принятое слово r(х) умножается на x^n-k+s вместо умножения на х^n-k по модулю g(x) в обычном декодере.

Другим возможным решением может быть попытка построения других классов циклических кодов с требуемыми параметрами. Интересными классами таких кодов, которые не рассматриваются в этом пособии, являются не примитивные коды БЧХ, евклидово-геометрические (EG) и проективно-геометрические (PG) коды. Еще одна возможность состоит в применении недвоичных циклических кодов в двоичном представлении, таких как коды Рида-Соломона, рассматриваемые в следующей части. Двоичное отображение PC кодов обладает дополнительно способностью исправления многократных пакетов ошибок.