ridsolomon

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО

ПРИБОРОСТРОЕНИЯ, каф. Информационных Систем

В.Д.КОЛЕСНИК

УЧЕБНОЕ ПОСОБИЕ ПО КУРСУ

«КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ СООБЩЕНИЙ

(Алгебраическая теория блоковых кодов)»

Глава 4. Коды Боуза-Чоудхури-Хоквингхема (БЧХ-Коды)

Санкт-Петербург

2005-2006

1

4.1.2 Алгебраическое декодирование циклических кодов с минимальным расстоянием 5

Пусть f1 (x)- примитивный полином, порождающий поле GF(q), q = 2m , и его корень α - это примитивный элемент этого поля. Рассмотрим декодирование

двоичного циклического кода С с длиной n = 2m −1 и минимальным расстоянием 5. Как мы убедимся позже, проверочная матрица для такого кода может быть взята в виде:

c(α) = 0, c(α3 ) = 0.

Другими словами, величины α и α3 являются корнями каждого кодового слова и, следовательно, корнямипорождающегополинома. Очевидно, чтоэтидвевеличиныполя

GF(q), q = 2m , порождают два различных циклотомических класса. Следовательно, полином f3 (x), корнем которого является α3 , неприводим над полем GF (2) и отличен от полинома f1 (x). Поэтому порождающий полином кода С равен

g(x) = f1 (x) f3 (x) .

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

n = 2m −1 позициям кодового слова различные ненулевые величины поля GF (2m ) , например, сопоставляя i ↔ αi для всех i = 0,1,…n - 1. Если при передаче произошли две ошибки на позициях с номерами i и j, то этим двум ошибкам соответствуют два локатора X1 =αi , X 2 =α j . Эти локаторыоднозначноопределяют позицииошибок, i = logα X1 и j = logα X 2 . Поэтомузадачудекодированиядвоичногокода можно трактовать, как задачу отыскания соответствующих локаторов ошибок.

В случае двойной ошибки слово на входе декодера имеет следующий вид: r(x) = c(x) + xi + x j . Декодеру при этом известно, что с(α) = 0, с(α3) = 0. Введем

в рассмотрение две величины S1 = r(α) =αi +α j , S3 = r(α3 ) =α3 i +α3 j , которые назовем компонентами синдрома. Их можно вычислить по полиному r(x) , поэтому

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

корнями σ( x) . По теореме Безу многочлен локаторов ошибок можно представить следующим образом:

4

Таким образом, зная компоненты синдрома S1 , S3 , мы можем вычислить

коэффициенты полинома локаторов ошибок. Декодирование происходит следующим образом. Мы рассмотрим 3 случая.

σ(x) = x2 − S1 x = x(x − S1 ). Локатор ошибки это корень полинома σ( x) . В данном случае ненулевой корень равен S1 и он единственный, поэтому позиция ошибки

~

i = logα S1 . Выходом декодера является слово r(x) , в котором символ на позиции i инвертирован.

С) Предположим, что S1 ≠ 0, S3 ≠ S13 . Мыможемвычислитькоэффициенты полинома

σ( x) как это указано в (4.1.6). Для отыскания позиций ошибок нужно найти корни этого полинома. Корни можно найти, например, перебирая все ненулевые

элементы X GF (2m ) и находя те Х, для которых σ( X ) =0. При двух ошибках будут найдены два локатора ошибок X1 , X 2 . Позиции ошибок будут найдены как i1 = logα X1 , i2 = logα X 2 . Выходомдекодераявляетсяслово y(x) , в котором символы на позициях i1 , i2 инвертированы.

§4.2 Матрица Вандермонда

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

где X1 , X 2 ,..., X m−1 - элементы произвольного поля.

5

Теорема 4.2.1 Определитель матрицы Вандермонда можно вычислить следующим образом:

i, j {1,....,m}, j>i

Доказательство: Будем доказывать по индукции. Очевидно, V1 =1 . При m=1 множествоиндексовв(4.2.2) пусто. Произведениепустогомножествасомножителей принимается равным единице. Легко найти, что detV2 = X 2 − X1 , следовательно, (4.2.2) верно в этом случае. Предположим, что равенство (4.2.2) верно для матрицы порядка

Докажем, чтоприэтомравенствобудетвернымидляматрицыпорядка m ×m . Дляэтого

~

рассмотрим матрицу V m (x) , которая получается из Vm заменой X m на переменную х:

~

Определитель этой матрицы detV m (x) представляет собой полином степени m −1, коэффициенты которого являются произведениями и суммами величин X1 , X 2 ,..., X m−1 .

Следствие. Определитель матрицы Вандермонда (4.2.1) не равен нулю, если все величины X1 , X 2 ,..., X m различны, и равен нулю, если хотя бы две величины из

X1 , X 2 ,..., X m совпадают.

§ 4.3 Коды Боуза-Чоудхури-Хоквингхема

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

1)среди БЧХ - кодов присутствуют весьма хорошие коды;

2)для этих кодов известны относительно простые методы кодирования и декодирования;

3)коды Рида-Соломона, являются широко известным подклассом недвоичных БЧХ - кодов, которые обладают определенными оптимальными свойствами;

6

4) полное понимание кодов БЧХ, по-видимому, является наилучшей отправной точкой для изучения многих других классов кодов.

4.3.1 Определение БЧХ-кодов

q-ичные БЧХ-коды задаются следующим образом. Пусть ε - примитивный элементполя GF (qm ) и β =εs - элементпорядкаn, т.е. βn =1, причемn естьнаименьшее

ненулевоецелоестакимсвойством. Напомним, что {1,ε,ε2 ,...,εq m −2}- сутьвсеразличные ненулевые элементы поля GF (qm ) , а β - порождает циклическую подгруппу

Будем предполагать, что Н является проверочной матрицей некоторого линейного кода длины n, т.е. c HT = 0 для любого слова c = (c0 , c1 ,..., cn−1 ) этого кода.

Теорема 4.3.1. Линейный код C с проверочной матрицей (4.3.1) является циклическим кодом с длиной n. Порождающий полином этого кода имеет среди своих

корнейd–1 последовательныхстепеней β , аименно, β1 = βl0 , β2 = βl0 +1 ,..., βd −1 = βl0 +d −2 . Минимальное расстояние кода не меньше, чем d.

Доказательство: Покажем, что вес w(c) любого ненулевого кодового слова c C не меньше, чем d. Для этого предположим противное, а именно, что

столбцов, линейная комбинация которых равна нулю. Другими словами, в матрице Н можно выделить квадратную (d −1) ×(d −1) подматрицу Р с нулевым

определителем. Выпишемэтуподматрицу, обозначивчерез i1 , i2 ,..., id −1 номерастолбцовв Н, которые образуют Р:

Матрицу Р можно представить в виде следующего произведения:

7

произведению диагональных членов. Определитель матрицы Р равен произведению определителей сомножителей. Поскольку {i1 , i2 ,..., id −1} - различные числа из множества

{0,1,..., n −1}, то βi1 ,..., βid −1 - различныененулевыеэлементы GF (qm ) . Отсюдавытекает,

что det P ≠ 0 . Это противоречит исходному предположению о том, что в матрице Н имеются d −1 линейнозависимыхстолбцови, следовательно, тому, чтоимеетсякодовое слово с весом меньшим, чем d .

Теперь докажем, что код с проверочной матрицей Н является циклическим и порождающийполиномимеетуказанныйвтеоременаборкорней. Пусть c = (c0 , c1 ,..., cn−1 )

- кодовое слово и c(x) = ∑ci xi - соответствующий этому слову полином. Рассматривая

i

произведение c HT = 0 , мы можем заметить, что

c HT = [c(β1 ) c(β2 ) ... c(βd −1 )] ,

т.е. полином c(x) удовлетворяетследующимусловиям: c(βi ) = 0, i =1,..., d −1 . Другими словами, каждоекодовоеслово, аследовательно, порождающийполином g(x) , должны иметьсредисвоихкорней d −1 последовательныхстепеней βl0 , βl0 +1 ,..., βl0 +d −2 GF(qm ) . Другими корнями полинома g(x) являются величины поля GF (qm ) , сопряженные с βl0 , βl0 +1 ,..., βl0 +d −2 . Такимобразом, корнипорождающегополиномаявляютсястепенями элемента β . Порядок β равен n, поэтому все корни порождающего полинома имеют порядокn, т.е. являютсякорнямидвучлена xn −1 . Следовательно, порождающийполином g(x) является делителем xn −1 и код является циклическим.

Наосноветеоремы4.3.1 строятсяразличныециклическиекоды, параметрыкоторых зависят от выбора полей и порождающих элементов. Эти коды были открыты Боузом и Рой-Чоудхури(1960) инезависимоотнихХоквингхемом(1959). Длинакодаопределяется порядкомn выбранногопорождающегоэлемента β . Кодназываетсяпримитивным, если

n = qm −1, т.е. если β является примитивным элементом GF (qm ) . Главное требование,

обеспечивающее минимальное расстояние d, это требование существования d −1 последовательных степеней элемента β среди корней порождающего полинома. Не

существенно с какого элемента βl0 начинается ряд последовательных степеней.

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

называется конструктивным расстоянием БЧХ-кода.

Число проверочных символов определяется для выбранного поля GF(q) суммарной степенью неприводимых сомножителей порождающего полинома.

8

4.3.2 Двоичные примитивные БЧХ-коды

Мыначнем изучение БЧХ-кодовс построения двоичных примитивных кодов. Для этого выберем q=2 и n = 2m −1 . Обозначим через ε -примитивный элемент GF (2m ) и через f1 (x) неприводимый над GF (2) полином, корнем которого является ε . Этот полином имеет степень m , поэтому его корнями служат элементы циклотомического

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

d-1 величин поля. Поскольку каждый такой класс соответствует неприводимому над GF (2) полиному, степень которого равна длине циклотомического класса, и g(x)

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

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

степени примитивного элемента ε и используя тождество ε15 =1 , а также укажем соответствующие неприводимые полиномы, корнями которых являются элементы циклотомических классов:

Отметим сразу, что в двоичном случае все циклотомические классы, исключая класс I0 ={0}, в логарифмическойформепорождаютсянечетнымичислами, поскольку четное

число 2l, l ≠ 0, принадлежиттомужеклассу, чтоичисло l . Поэтомуусловиетого, чтобы внекотором множествециклотомическихклассовнашласьсерия {l0 , l0 +1,...,l0 + d − 2},

состоящая из d −1 последовательных натуральных чисел, в двоичном случае эквивалентноусловиютого, чтобынашласьсерия, из [d −1/ 2] идущихподряднечетных

чисел. Отсюдаиизтого, чтодлиныциклотомическихклассовнепревышаютm , вытекает следующее утверждение, справедливое для двоичных БЧХ-кодов.

Теорема 4.3.2. Количество избыточных символов r в двоичном БЧХ-коде с минимальнымрасстоянием d = 2t +1 идлинойn , где n = 2m −1 илиявляетсяделителем этого числа, удовлетворяет неравенству r ≤ mt . Количество избыточных символов в двоичном коде с минимальным расстоянием d = 2t + 2 не превосходит mt +1.

Пример4.3.1. Пустьm=4 иn=15. Вследующейтаблицеприведеныпараметрывсех двоичныхБЧХ-кодовдлины15 сразличнымизначениямиконструктивногорасстояния d . Для кодов из табл.4.3.1 минимальное и конструктивное расстояния совпадают.

9

В таблице 4.3.2 даны паметры некоторых двоичных примитивных БЧХ-кодов, n, k и t = (d −1) / 2 , где d конструктивное расстояние кода. Использована восьмеричное

представление порождающего полинома (например, 23 ↔ (010 011) или x4 + x +1)

10