Помехоустойчивость и кодирование

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

Общая схема применения кодов с обнаружением и исправлением ошибок показана на рис. 8.1. Исходная кодовая комбинация U расширяется добавлением дополнительных корректирующих разрядов в кодирующем устройстве k. Полученная кодовая комбинация x передается через канал связи C или записывается в памяти П. При этом могут возникать ошибки либо из-за технической неисправности С или П, либо из-за сбоев. В результате передается или считывается кодовая комбинация x*, которая после декодирования устройством D приобретает вид исходной кодовой комбинации U.

Рис. 8.1. Общая схема применения кодов с обнаружением и исправлением ошибок

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

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

d d

Σ Cⁱ_n ≤ 2^n-k, откуда k ≤ n – log₂ Σ Cⁱ_n,

i=0 i=0

где n — число разрядов кода x=(x₁,x_2, ...,х_n) с обнаружением и исправлением ошибок; k — число информационных разрядов (разрядность кода U=(U₁,U₂, …,U_k), d — количество исправляемых ошибок).

Ниже приведены некоторые-результаты расчета по неравенству Хэмминга:

n … 7 63 63

d … 1 1 3

k … 4 57 47

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

Расстоянием ρ(x¹,x²) между двумя n-кодовыми комбинациями x¹ и x² называется величина

n

ρ(x¹,x²) = Σ (x¹_i + x²_i),

i=1

где + — сложение по модулю 2.

Чтобы кодовые комбинации, окружаемые гиперсферой с радиусом d (в такую гиперсферу вписываются все кодовые комбинации с ошибками кратности не более d), были взаимно различимы, достаточно, если расстояние ρ между этими кодовыми комбинациями удовлетворяет неравенству

ρ ≥ 2d + 1 (8.1)

(рис. 8.2). Рассуждая аналогично, можно установить, что кодовые комбинации, позволяющие обнаружить d₁ ошибок, должны быть разнесены друг от друга на расстояние

ρ ≥ d₁ + 1 (8.2)

Действительно, для обнаружения ошибки достаточно, чтобы ошибочная кодовая комбинация не совпадала с другой, правильной кодовой комбинацией. Это гарантируется единичным (минимальным) расстоянием, поэтому в (8.2) к d₁ прибавляется единица (рис. 8.3). В общем случае существует также неравенство ρ ≥ d + d₁ + 1. Следовательно, проблема помехоустойчивого кодирования сводится к проблеме максимально плотной упаковки гиперсфер заданного радиуса в заданном двоичном гиперпространстве и установления их центров — отдельных «разрешенных» кодовых комбинаций.

Матричное представление кодов с обнаружением и исправлением ошибок. Указанная выше задача может быть разрешена при помощи линейной матричной операции x = UG_k×n, где G_k×n — некоторая матрица двоичных элементов, называемая порождающей матрицей. Матричные операции в данном случае производятся по обычным правилам, только взамен сложения по правилам элементарной алгебры применяется операция сложения по модулю 2 (обозначение +). Тогда все элементы матриц и векторов остаются в множестве {0,1}. Для декодирования вводится матрица Н_(n-k)×n, называемая контрольной матрицей. Произведение xН^T_(n-k)×n = S называется синдромом. Синдром позволяет получить представление о наличии и характере ошибок в коде x. Допустим, что

G = [E_k | A_k×(n-k)], (8.3)

где

и требуем, чтобы xН^Т= [0], тогда Н(UG)^T=[0] или HG^TU^T=[0] или HG^T=[0], или G^TH^T=[0]. Произведение G^TH^T=[0], если

Н = [A^T_kx(n-k) | E_n-k] (8.4)

Действительно

[E_k | A_kx(n-k)] [A^T_(n-k)×k | E_n-k]^T = [E_k | A_k×(n-k)] = A_k×(n-k) +

A_k×(n-k) ≡ [0].

Если корректирующая матрица составлена по (8.4), то в случае, когда код х* содержит ошибки, что обозначается звездочкой, х*Н^Т ≠ [0], иначе х*H^Т ≠ [0]. Далее необходимо расшифровать синдром х*Н^Т ошибочного кода, т. е. локализовать и затем исправить возникшую ошибку.

Коды Хэмминга. Расшифровка синдрома наиболее проста, когда порождающая матрица строится по способу Хэмминга. Исходным при этом является некоторая вспомогательная матрица Н₀, состоящая из возрастающих двоичных чисел (начиная от единицы), читаемых сверху вниз. На основании матрицы Н₀ строится матрица Н перестановкой столбцов матрицы Н₀ так, чтобы справа образовалась единичная подматрица. Затем, переставляя единичную подматрицу Е и подматрицу A между собой и транспонируя в соответствии с (8.3) и (8.4), получаем порождающую матрицу G. Замечательным свойством синдрома кодов Хэмминга является то, что синдром, читаемый как двоичное число, указывает номер разряда, где произошла ошибка. Однако при переходе от матрицы Н₀ к матрице Н последовательность столбцов изменяется. Исправляемый разряд определяется по столбцу матрицы Н, совпадающему с синдромом.

Пример. Кодирование и декодирование кода Хэмминга. Пусть

Если имеется, например, кодовая комбинация U=1110, то x = UG = 1110000.

Пусть ошибка возникает в пятом элементе кодовой комбинации x, т. е. x* = 1110100. Тогда синдром S = x*Н^T = 100, что указывает на то, что отказал пятый элемент кодовой комбинации х.

Код Хэмминга дает возможность исправлять только одиночные ошибки. Модифицированный код Хэмминга позволяет обнаруживать двойные ошибки и часть ошибок более высокой кратности, а также исправлять одиночные ошибки. Модифицированный код Хэмминга образуется путем прибавления к кодовой комбинации кода Хэмминга x = (x₁, …x_n) дополнительного разряда x_n+1, который образуется по следующей формуле:

_n

x_n+1 = Σ ₊ x_i,

ⁱ⁼¹

где Σ ₊ означает суммирование по модулю 2. Следовательно, минимальное кодовое расстояние между двумя кодовыми комбинациями модифицированного кода Хэмминга d ≥ 4.

Декодирование модифицированного кода Хэмминга осуществляется на основании табл. 8.1.

Таблица 8.1

Синдром	xn+1	Описание ситуации
= 0		Ошибок нет или 4,6,… ошибок
≠ 0		Две ошибки обнаруживаются
= 0 или ≠0		3,5… ошибок
≠0		Одна ошибка, исправляется

Формально модифицированный код Хэмминга может быть образован с помощью порождающей матрицы G, к которой добавлен столбец, образующий дополнительный (U+1)-й разряд. Рассмотрим образование этого разряда на примере кодирования по Хэммингу, рассмотренного выше.

Продолжение примера. По определению,

x₈ = x₁ + x₂ + x₃ + x₄ + x₅ + x₆ +x₇ =

x₅

= U₁ + U₂ + U₃ + U₄ +U₂ + U₃ + U₄ +

x₆ x₇

+ U₁ + U₃ + U₄ + U₁ + U₂ + U₄ = U₁ + U₂ + U₃

Следовательно, матрица модифицированного кода Хэмминга G_M приобретает вид

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

Коды Хэмминга могут быть построены также с основанием системы счисления q > 2. В этом случае матрица Н₀ строится из столбцов, представляющих собой возрастающие q-ичные числа. Однако при этом могут возникать линейно зависимые столбцы, т. е. столбцы, сумма которых (по модулю q) равна нулю. Например, при q = 3

0 + 0 = 0,

……….

1 + 2 = 0,

……….

2 + 1 = 0,

где + означает сложение по модулю 3. Поскольку линейно зависимые столбцы в матрице Н₀ (и H) не позволяют построить код Хэмминга, в случае q = 3 рекомендуется исключить из матрицы все столбцы, которые начинаются с двойки или с двойки после нуля или нулей.

Пример. Построить матрицы Н₀, Н и G для кода Хэмминга с основанием q=3 и с числом контрольных разрядов m = n - k =3.

Тогда матрица Н₀ приобретает следующий вид:

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

Порождающая матрица образуется тогда путем перестановки подматриц A и Е, т.е.

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

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

Матрица G₀ — это единичная строка, т. е.

G₀ = [11…1].

Матрица G₁ образуется как матраца Н₀ в виде возрастающих m-разрядных двоичных чисел, только с добавлением нулевого столбца слева, т. е.

Следующие подматрицы G₂, G₃, …,G_i, …, G_r образуются из строк, полученных как произведения всех комбинаций строк матрицы G₁, взятых по i. Следовательно, число строк матрицы G

_r

k = Σ Cⁱ_n,

ⁱ⁼⁰

где n — число столбцов матрицы G. Минимальное кодовое расстояние между кодовыми комбинациями Рида—Маллера

d_min ≤ 2 ^m-r.

Например, если m = 4, r = 2, n = 16, то k = C¹₄ + C²₄ = 1 + 4 + 6 = 11, d_min ≤ 2 ^m-r = = 2 ^{4 – 2} = 4.

Следовательно, код позволяет обнаруживать две ошибки и исправлять одну. Если же m = 6, r = 3, n = 64, то k = 42 и d_min = 8, т. е. обнаруживается до семи и исправляется до трех ошибок.

В первом случае порождающая матрица имеет вид

x₀x₁x₂x₃ x₄x₅x₆x₇ x₈x₉x₁₀x₁₁ x₁₂x₁₃x₁₄x₁₅

Кодирующее устройство строится аналогично тому, как построено кодирующее устройство для кода Хэмминга, выполняющее операцию умножения вектора на матрицу x = UG.

Декодирование кода Рида-Маллера осуществляется по особому алгоритму, основанному на том, что отдельные составляющие вектора U можно получить виде сумм различных комбинаций составляющих вектора x*. Если отдельные составляющие искажены, то полученные. значения составляющего U могут различаться и правильное значение каждого составляющего находится методом голосования. Например, в случае приведенной порождающей матрицы имеется четыре варианта U₁₀,

U₁₀⁽¹⁾ = x^*₀ + x^*₁ + x^*₂ + x^*₃,

U₁₀⁽²⁾ = x^*₄ + x^*₅ + x^*₆ + x^*₇,

U₁₀⁽³⁾ = x^*₈ + x^*₉ + x^*₁₀ + x^*₁₁,

U₁₀⁽⁴⁾ = x^*₁₂ + x^*₁₃ + x^*₁₄ + x^*₁₅.

I

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

Аналогичным образом могут быть составлены варианты дла U₉,

U₉⁽¹⁾ = x^*₀ + x^*₁ + x^*₂ + x^*₃,

U₉⁽²⁾ = x^*₄ + x^*₅ + x^*₆ + x^*₇,

U₉⁽³⁾ = x^*₈ + x^*₉ + x^*₁₀ + x^*₁₁,

U₉⁽⁴⁾ = x^*₁₂ + x^*₁₃ + x^*₁₄ + x^*₁₅.

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

На рис.8.4 приведен фрагмент схемной реализации выше приведенных уравнений с последующим голосованием.

x^*₀

x^*₁

x^*₂

x^*₃

x^*₄

x^*₅

x^*₆

x^*₇

x^*₈

x^*₉

x^*₁₀

x^*₁₁

x^*₁₂

x^*₁₃

x^*₁₄

x*₁₅

Рис. 8.4. Фрагмент схемной реализации дешифратора для кода Рида-Маллера

Циклические коды. При передаче данных, осуществляемых последовательно, большое значение имеют циклические коды — коды, для которых циклическая перестановка кодовых символов некоторого кодового слова порождает также кодовое слово. Например, если задано некоторое кодовое слово x = (x₀, …,x_n), то при циклической перестановке образуются кодовые слова x⁽¹⁾ =(x_n,x₀,...,x_n-1), x⁽²⁾ =(x_n-1,x_n, x₀,...,x_n-2) и т. д. Циклические коды удобно представлять в виде полиномов, тогда говорят о циклических полиномиальных кодах. Полиномиальное представление кода заключается в том, что код представляется в виде полинома, причем степень каждого слагаемого соответствует позиции данного ненулевого кодового элемента.

Например, двоичное кодовое слово 11010 может быть представлено виде полинома 1 · x⁴ + 1 · x³ + 0 · x² + 1 · x¹ + 0 · x⁰ = x⁴ + x³ + x. Полиномиальные циклические коды позволяют обнаруживать и исправлять ошибки. Кодирование при циклических кодах осуществляется путем деления полинома, изображающего исходное кодовое слово, на подходящим образом подобранный полином, называемый порождающим полиномом. Остаток, образовавшийся при делении, приписывается к исходному кодовому слову в качестве набора контрольных символов.

Обозначая через U — исходное кодовое слово в полиномиальной форме, g — порождающий полином, q — частное и r — остаток, получаем соотношение Ux^(n-k)/g = = q + r/g откуда Ux^(n-k) = qg + r. Здесь и далее подразумевается, что сложение производятся по модулю 2 и поэтому вычитание равноценно сложению, следовательно, кодовое слово ν = qg = Ux^(n-k) + r. При этом исходное кодовое слово умножается на коэффициент x^(n-k), где n — общая длина кодового слова, а k — количество информационных разрядов. Эта операция означает, что информационная часть кодового слова сдвигается влево на n – k разрядов, а на освободившееся справа свободное место записывается остаток r. Поскольку операция сложения остатка r по модулю 2 равноценна вычитанию этого остатка, получающееся кодовое слово ν, подлежащее передаче, делится на порождающий многочлен g без остатка. Если же при передаче кодовое слово ν исказятся, т. е. образуется кодовое слово (или соответственно многочлен) ν^*‚ то в результате деления на приемном конце канала связи ν* на g образуется остаток, который служит синдромом, позволяющим обнаруживать и исправлять ошибку.

Приведем пример кодирования и декодирования циклического кода. Пусть порождающий полином g имеет вид g = x⁴ + x + 1, а общая длина кодовых слов с коррекцией n = 9 при числе информационных разрядов k = 4. Пусть передается кодовое слово 1101, что соответствует полиному U = x³ + x² + 1. Произведение

Ux^(n-k) = (x³ + x² + +1)x⁵ = x⁸ + x⁷ + x⁵.

При делении Ux^(n-k)/g получается, что частное q = x⁴ + x³, а остаток r = x³. Все вместе дает полином ν = x⁸ + x⁷ + x⁵ + x³, что соответствует передаваемому кодовому слову 110101000.

Если это кодовое слово передается без искажений, то при его делении на g получается, что остаток r = 0. При одиночкой ошибке возможны девять различных векторов ошибок, приведенных ниже, в табл. 8.2.

В таблице приведены синдромы, полученные при делении, принятого кодового слова на порождающий полином. Например, если передается кодовое слово 110101000 и искажается старший разряд, то получается кодовой слово 010101000, которому соответствует полином x⁷ + x⁵ + x³. При делении этого полинома на порождающий полином вида x⁴ + x + 1

Таблица 8.2

Вектор ошибок	Полиномиальная запись ошибки	Синдром (остаток)	Полиномиальная запись остатка
	x^8		x^2 + 1
	x^7		x^3 + x + 1
	x^6		x^3 + x^2 + 1
	x^5		x^2 + x
	x^4		x + 1
	x^3		x^3
	x^2		x^2
	x^1		x

x⁷ + x⁵ + x³ |_ x⁴ + x + 1

x⁷ + x⁴ + x³ x³ + x + 1

x⁵ + x⁴

x⁵ + x² + x

x⁴ + x² + x

x⁴ + x + 1

x² + 1

получим остаток r = x² + 1. Аналогично находятся также и другие остатки.

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

Вследствие того что кодовое слово делится на порождающий полином без остатка, вектор ошибок определяется однозначно синдромом (остатком). Векторы ошибок, соответствующие отдельным синдромам, могут быть установлены заранее и использованы при декодировании. Основным преимуществом полиномиальных циклических кодов перед линейными блоковыми кодами, кодируемыми и декодируемыми при помощи матричных операций, является простота схемной реализации. Сложность, т.е. количество элементов в преобразователе, определяется при операциях типа деления полиномов как величина пропорциональная n. Количество элементов для схемной реализации матричных операций пропорционально n². Преимущество циклических кодов проявляется при последовательном представлении кодов. Поэтому циклические полиномиальные коды применяются для повышения помехоустойчивости каналов связи, НМЛ и НМД, в которых информация передается и представляется последовательными кодами. Отметим, что при помощи последовательных кодов, в том числе циклических полиномиальных кодов, нельзя повысить отказоустойчивость устройств, поскольку отказ канала передачи или запоминания влечет за собой искажение всех элементов кода.

Устройства для деления полиномов (цифровые фильтры) реализуются схемно достаточно просто. На рис. 8.5 в качестве примера изображена схема фильтра для деления некоторого полинома на полином x⁴ + x + 1. Фильтр состоит из регистра сдвига P с разрядами 1-4 и из двух сумматоров по модулю 2.

Рис. 8.5. Схема устройства для деления полиномов

Таблица 8.3

Такт	Вход	Содержание регистра	Выход
		P1	P2	P3	P4

В качестве примера на вход подается кодовое слово 110100000, начиная со старшего разряда, что соответствует полиному x⁸ + x⁷ + x⁵. В таблице 8.3 изображены такты работы устройства, начиная с момента достижения старшим разрядом делимого ячейки Р₄. Строки таблицы соответствуют тактам работы схемы, столбцы — содержанию ячеек регистра. По бокам таблицы изображены входящие и выходящие элементы кодов, не записанные в регистре.

При продвижении элементов кода слева направо происходит деление. В результате деления образуется кодовая комбинация 11000, соответствующая частному (x⁴ + x³).

В регистре при этом остается остаток x³ в виде кодовой комбинации 1000.

В общем случае умножение двух полиномов ν(x) = U(x)g(x), где

U(x) = U_nxⁿ + U_n-1x^n-1 +…+ U₁x + U₀,

g(x) = g_mx^m + g_m-1x^m-1 +…+ g₁x + g₀,

ν(x) = ν _sx^s + ν _s-1x^s-1 +…+ ν ₁x + ν ₀

осуществляется на основании следующего уравнения:

ν = U_ng_mx^n+m + (U_ng_m-1 +U_n-1g_m)x^n+m-1 + (U_ng_m-2 + U_n-1g_m-1 + U_n-2g_m)x^n+m-2 + …

…+ (U₁g₀ + U₀g₁)x + U₀g₀,

которое получено путем упорядочения членов произведения двух полиномов по степеням х.

Аппаратно умножение может быть осуществлено с помощью устройства, схема которого изображена на рис.8.6. Устройство предназначено для умножения полинома, g(x), задаваемого схемой, на полином U(x), подаваемые на вход схемы в виде последовательности импульсов, соответствующих ненулевым коэффициентам полинома, начиная со старшего разряда. Произведение выходит из устройства также в виде последовательности импульсов, начиная со старшего разряда. В схеме (рис.5.13) квадратиками обозначены элементы задержки 3 (триггерные ячейки), знаком + обозначены одноразрядные сумматоры по модулю 2, а знак i означает прямое соединение, если коэффициент многочлена g_i = 1 и отсутствие соединения в противоположном случае.

ν₀ν_1…ν_s-1ν_s

U₀U₁…U_n-1U_n

Рис. 8.6. Общая схема устройства для умножения полиномов

В первый такт работы устройства коэффициент U_n умножается на коэффициент g_m и результат поступает через элементы + на выход как ν_s. Во втором такте на вход поступает U_n-1 и, умноженный на g_m, поступает на вход левого сумматора +. В то же время на нижний вход этого же сумматора поступает задержанный сигнал U_n, умноженный на g_m-1, а сумма выдается как ν_s-1 в полном соответствии с вышеприведенной формулой. После s + 1 = m + n -1 тактов работы на выходе произведение появляется полностью. Деление полиномов ν(x): g(x) = U(x) в общем случае осуществляется с помощью устройства, схема которого изображена на рис. 8.7.

ν₀ν_1…ν_s-1ν_s U₀U₁…U_n-1U_n

Рис 8.7. Общая схема устройства для деления полиномов

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

sⁱ⁺¹ = Asⁱ + Be_i,

где А — матрица переходов состояний регистра, В — матрица-столбец входов, sⁱ — матрица-столбец, описывающее состояние регистра в i-м такте и e_i — значение входа в i-м такте.

Так, для примера рис. 5.12

е₀ = x₈ = 1, e₁ =x₇ = 1, е₂ = x₆ = 0, е₃ = x₅ = 1,

е₄ …e₈ = x₄ … x₀ = 0,

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

Порождающий многочлен кодов БЧХ образуется по следующей формуле:

g(x) = HOK[f₁(x),f₂(x), …,f_2t(x)],

где НОK означает наименьшее общее кратное некоторого числа заданных многочленов; f_i(x) — i-й минимальный многочлен кода, а t — число исправляемых ошибок.

Величина d = 2t + 1 носит название конструктивного расстояния. Практически минимальное расстояние между двумя генерированными кодовыми комбинациями может быть и больше.

Минимальный многочлен f_i(x) — это многочлен минимального порядка, который равен нулю, если в качестве аргумента x подставить элемент поля Галуа αⁱ. Элемент поля Галуа α выбирается так, чтобы все другие элементы поля могли быть найдены как степени этого элемента. Кроме степенного представления существует полиномиальное представление каждого элемента поля Галуа в виде полинома от z. Такая двойственность представления элементов поля Галуа полезна тем, что умножение многочленов удобно осуществлять в степенной, а сложение — в полиномиальной форме.

Значение i-го элемента поля в полиномиальной форме находится по условию

βⁱ(z) = R_p(z)(zⁱ), (8.5)

где функция R_p(z) означает вычисление остатка по модулю p(z).

От выбора примитивного многочлена p(z) зависит число элементов поля, определяемое как q^m - 1, где q — основание системы счисления, а m — степень примитивного многочлена p(z). В табл. 8.4 приведены значения примитивных полиномов для различных значений m в случае, когда q = 2.

Таблица 8.4

m	p(z)
	z^2 + z + 1
	z^3 + z + 1
	z^4 + z + 1
	z^5 + z^2 + 1
	z^6 + z + 1
	z^7 + z^3 + 1
	z^8 + z^4 + z^3 + z^2 + 1
	z^9 + z^4 + 1
	z^10 + z^3 + 1

На основании примитивного многочлена составляются элементы поля. В случае, когда m = 4, элементы поля будут следующими (табл. 8.5).

Таблица 8.5

Степенная форма α^i	Полиномиальная форма	Минимальный многочлен
α^0		x + 1
α^1	z	x^4 + x + 1
α^2	z^2	x^4 + x + 1
α^3	z^3	x^4 + x^3 + x^2 + x + 1
α^4	z+1	x^4 + x + 1
α^5	z^2 + z	x^2 + x + 1
α^6	z^3 + z^2	x^4 + x^3 + x^2 + x + 1
α^7	z^3 + z + 1	x^4 + x^3 +1
α^8	z^2 + 1	x^4 + x + 1
α^9	z^3 + z	x^4 + x^3 + x^2 + x + 1
α^10	z^2 + z +1	x^2 + x + 1
α^11	z^3 + z^2 + z	x^4 + x^3 +1
α^12	z^3 + z^2 + z +1	x^4 + x^3 + x^2 + x + 1
α^13	z^3 + z^2 + 1	x^4 + x^3 +1
α^14	z^3 + 1	x^4 + x^3 +1

Таким образом, элементы поля в полиномиальной форме находятся по выражению (8.5).

До третьей степени степенная форма элемента поля совпадает с полиномиальной формой. Однако уже α⁴ не равно z⁴, а образуется как остаток от деления z⁴ на примитивный полином при m = 4, т. е. на полином z⁴ + z + 1. Очевидно, остаток при делении будет z +1. Таким образом определяют всё полиномиальные элементы данного поля. Интересно отметить, что, поступая таким образом получают, что элемент α¹⁵ = α⁰ =1, элемент α¹⁶ = α¹ = z и т. д. Другими словами, степени α начнут циклически повторяться по модулю 15.

Кодирование кодов БЧХ осуществляется обычным способом, т. е. каждый многочлен U(x) умножается на порождающий полином g(х). Декодирование при этих кодах сложнее и осуществляется, как правило, программными средствами, особенно в случае длинных кодов.

Алгоритм декодирования кодов БЧХ заключается в следующем.

1. Вычисляются синдромные многочлены S_i = n* (αⁱ), для i = 1,..., n‚ при n = t. Многочлен n*(x) является многочленом, описывающим принятую, возможно, с ошибками кодовую комбинацию.

2. Вычисляется значение определителя

S₁ S₂ S₃ …S_n

S₂ S₃ S₄ …S_n-1.

………….

Sn S_n+1 …S_2n-1

3. Если detМ=0, то n = n - 1, следует возвращаться к п. 2. Иначе‚ n — фактическое число ошибок и следует переходить к следующему пункту.

4. Вычисляются вспомогательные величины L₁, L₂, … L_n по следующему матричному уравнению:

L_n S_n+1

L_n-1 S_n+2

… = - M^-1 ….

L₁ S_2n

В случае q = 2 минусы в правой матрице отпадают.

5. Составляется полином

L(x) = L_nxⁿ + L_n-1x^n-1 + … + L₁x + 1.

б. Определяются корни полинома п. 5 в виде элементов поля (степеней α).

7. Определяются номера разрядов ошибок как дополнения показателей степеней корней, найденных в п. б, по модулю q^m -1.

Отметим, что все операции производятся над элементами поля Галуа в виде степеней a, причем операции умножения заключаются в сложении показателей степеней a по модулю q^m -1, операции сложения — в сложении членов полинома одинакового порядка по модулю q в полиномиальной форме элементов кода.

Пример. Пусть m = 4 и q = 2, t = 3. Тогда порождающий многочлен

Пусть принятое кодовое слово n* (х) = х⁵ + x⁴.

Тогда по п. 1 алгоритма

S₁ = a⁵ + a⁴ = z² + z + z + 1 = z² + z + z + 1 = a⁸,

S₂ = a¹⁰ + a⁸ = z² + z + 1 + z² + 1 = z = a¹,

S₃ = a¹⁵ + a¹² = a⁰ + a¹² = 1 + z³ + z² + z + 1 = a¹¹,

S₄ = a⁵ + a¹⁶ = a⁵ + a¹ = z² + z + z = z² = a²,

S₅ = a¹⁰ + a²⁰ = a¹⁰ + a⁵ = z² + z + 1 + z² + z = a⁰,

S₆ = a¹⁵ + a²⁴ = a⁰ + a⁹ = 1 + z³ + z = a¹.

По п. 2 алгоритма

a⁸ a¹ a¹¹

a¹ a¹¹ a² = a⁸( a¹¹ + a⁴) + a¹(a¹ + a¹³) + a¹¹(a³ + a⁷) =0.

a¹¹ a² a⁰

По п. З алгоритма n = n -1 = 2 и по п. 1 определитель вычисляется снова:

a⁸ a¹

= a⁴ + a⁷ = z +1 +z² = a¹⁰¹ 0.

a¹ a¹¹

Следовательно, фактическое число ошибок n = 2.

По п. 4 вычисляются вспомогательные величины L₁, L₂. Для этого находится обратная матрица.

a⁸ a^{1 -1} a¹¹/a¹⁰ a¹¹/a¹⁰ a¹ a⁶

M^-1= = =.

a¹ a¹¹ a¹/a¹⁰ a⁸/a¹⁰ a⁶ a¹³

Так как определитель матрицы

a⁸ a¹

= a⁴ + a² = z +1 +z² = a¹⁰,

a¹ a¹¹

то тогда

L₂ S₃ a¹ a⁶ a¹¹ a¹² + a⁸ a⁹

=M^-1 = = =.

L₁ S₄ a⁶ a³ a² a² + a⁰ a⁸

По п. 5 составляем полином

L(x) = a⁹ x² + a⁸x + 1.

Корни находятся из условия

a⁹ x² + a⁸x + 1 = 0.

Если полином представить в виде

(a^a x + 1)( a^bx + 1) = a^a+b x² + (a^a + a^b)x +1,

то имеем ограничения a + b = 9 и a^a + a^b = a⁸. Кроме того, требуется, чтобы a + =15 и

b + = 15, где и – степени искомых корней. Очевидно, тогда требуется, чтобы +=21. Путем проб и ошибок можно определить, что a^a + a^b = a⁸ при a = 5 и b = 4.

Эти значения и указывают номера ошибочных разрядов. Следовательно, правильный полином n(x) = 0.

Дата добавления: 2014-01-06