Методическое пособие 640

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

Однако этот метод обладает двумя существенными недостатками.

Во-первых, при формировании ЦК методом умножения в полученной комбинации Bj(X) в явном виде не содержатся информационные символы. Код получается неразделимым с "перетасованными" информативными и проверочными символами, что затрудняет его декодирование.

При таком способе декодирования в памяти запоминающего устройства (ЗУ) декодера необходимо хранить все разрешённые кодовые комбинации No, что требует на стороне приёма больших объёмов ЗУ и большого времени обработки при декодировании. Эти обстоятельства являются вторым недостатком метода умножения при кодировании ЦК.

Задача декодирования простым перебором и сравнением непосильна даже для современных ЭВМ. В соответствии с этим, основным направлением в теории кодирования является поиск таких кодов и алгоритмов их формирования и обработки, для которых не требуется хранение в ЗУ разрешённых кодовых комбинаций. Эти задачи решаются, в частности, при построении кодеров на основе деления полиномов, а при декодировании – на основе синдромного метода декодирования (СМД).

Метод деления полиномов позволяет представить разрешённые к передаче кодовые комбинации в виде разделённых информационных Аi(Х) и проверочных Ri(X) символов, т. е. получить блочный код.

Поскольку число проверочных символов равно r, то для компактной их записи в последние младшие разряды кодового слова надо предварительно к Аi(Х) справа приписать r "нулей", что эквивалентно умножению Ai(X) на оператор сдвига Xr (см. свойство 5 ЦК).

На практике предпочитают использование метода деления полиномов при построении кодеков, поскольку при этом

221

имеется возможность представить кодовую комбинацию в виде разделённых информационных и проверочных символов:

Bi(X) = Ai(X)·Xr + Ri(X),

(7.28)

где Ri(X) – остаток от деления Ai(X)·Xr / G(X).

В алгоритме (7.28) можно выделить три этапа формирования разрешённых кодовых комбинаций в кодирующем устройстве:

1)к комбинации первичного кода Ai(X) дописывается справа r нулей» что эквивалентно умножению Ai(X) на Хr;

2)произведение Ai(X)·Xr делится на соответствующий порождающий полином G(X) и определяется остаток Ri(X), степень которого не превышает r - 1, этот остаток и даёт группу проверочных символов;

3)вычисленный остаток присоединяется справа к

Ai(X)·Xr.

Пример. Рассмотрим процедуру кодирования по алгоритму (7.28): для кодовой комбинации А=1001 сформировать кодовую комбинацию циклического кода (7,4),

В заданном ЦК n = 7, k = 4, r = 3, и из таблицы 7.1 выберем порождающий полином G(X) = X3 + X + 1 (код Хэмминга). Выполним три необходимые операции для получения кодовой комбинации ЦК согласно алгоритму (7.28):

Аi(X) = 1001 ~ X3 + 1 , (знак " ~ " – тильда – означает соответствие).

1. Ai(X)·Xr = (X3 + 1) · X3 = X6 + X3 ~ 1001000, (n = 7). 2. Ai(X)·Xr / G(X) = X6 + X3 | Х3 + Х+1

+---------------

X6 + X4 + X3 | X3 + X

----------------

X4

+

X4 + Х2 + X

----------------

Х2 + X

– остаток Ri(X) = X2+X ~ 110.

222

3. Bi(X) = Ai(X)·Xr + Ri(X) = 1001110 – итоговая комбина-

ция ЦК.

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

Для исправления ошибки на стороне приёма необходимо знать не только факт ее существования, но и ее местонахождение, которое определяется по установленному виду вектора ошибки z(X).

После передачи по каналу с помехами принимается кодо-

вое слово

( ) = ( ) + ( ),

где Bi(X) – передаваемая кодовая комбинация; z(X) - полином (вектор) ошибки, имеющий степень от 1 до n - 1.

При декодировании принятое кодовое слово делится на

G(X)

( ) = ( ) + ( ),

где остатокот деления Si(X) и является синдромом.

Если при делении получается нулевой остаток Si(X) = 0, то выносится решение об отсутствии ошибки z(X) = 0. Если остаток (синдром) не нулевой Si(X) = 0, то выносится решение о наличии ошибки и определяется шумовой вектор (полином) z(X), а затем передаваемое кодовое слово находится следую-

щим образом:

( ) = ( ) + ( ) .

Отсюда следует, что по синдрому S(x) можно однозначно определить вектор ошибки e(x), а следовательно, исправить эту ошибку (ошибки).

223

7.15.4. Построение простых многочленов

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

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

В случае многочленов степени 0 имеется один тривиальный многочлен (если этот вырожденный элемент заслуживает названия многочлена), а именно Р = 1. В обычной арифметике ему соответствует число 1.

Имеется ровно два унитарных многочлена степени 1, а именно х, x+1 и оба они являются простыми (аналогично тому, что тривиальный множитель 1 не учитывается при разложении чисел на множители, при разложении многочленов не учитывается тривиальный многочлен 1).

Имеется четыре различных унитарных многочлена степени 2 (каждый коэффициент при х и при 1 может быть 0 или 1):

х2		= х·х
х2	+ 1	= (х+1)·(х+1)
х2	+ х	= х·(х+1)
х2	+ х + 1 - простой.

Равенство х2 + 1 = (х+1)2 - может показаться на первый

224

взгляд странным. Однако, раскрывая скобки в правой части, получаем х2+2х+1. Поскольку 2=0 mod 2, имеем х2+2х+1=х2+1.

Уверены ли мы в том, что многочлен х2+х+1 является простым? Попробуем разделить его на каждый из двух многочленов меньшей степени. Если бы многочлен х2+х+1 был приводим, то соответствующими сомножителями могли бы быть только указанные два многочлена первой степени. Ясно, что х не является делителем. Попробуем провести деление на х+1:

х2	+ х + 1 |		x + 1
х2		----------
	+ х	| x	0

------------

01

00

------

1= остаток.

Таким образом, х2+х+1 действительно является простым многочленом.

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

x3 x3 + 1 x3 + x

x3 + x + 1 x3 + x2 + 1 x3 + x2 + x

x3 + x2 + x + 1

=x·x·x

=не простой

=x·(x2 +1)

=простой

=простой

=x·(x2+x+1)

=не простой

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

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

225

заны в таблице, осталось рассмотреть сомножитель х+1. Для x3+1 имеем x3+1 = (х+1)(х2+х+1). Т.е. это не простой многочлен.

Возьмем теперь многочлен х3+х+1. Имеем

1011 | __11__

11__ | 110

10

11_

01

00

1 = остаток.

Поэтому многочлен х3+х+1 является простым. Аналогич-

но, простым является многочлен x3 + x2 + 1, поскольку x3 + +x2

+ 1 =х2(x+1)+1.

Наконец, рассмотрим многочлен x3 + x2 + x + 1. Приведенные выше вычисления подсказывают, как разложить этот многочлен на множители, т. е. можно записать x2(x+1)+(x+1)= =(х2+1)(x+1) и многочлен не является простым.

Таким образом, простыми унитарными многочленами степени 3 будут только многочлены x3 + x+ 1, x3 + x2 + 1.

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

226

7.15.5. Матричное представление циклических кодов

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

Способ 1. Пусть образующий многочлен задан в виде

( ) =

+ + + .

Тогда образующая матрица может быть построена путем умножения g(x) на одночлен xk-1, k = n - m и последующим циклическим сдвигом так, что каждая i -я строка образующей матрицы составляется из коэффициентов многочлена g(x)·xk-i

(i=1,…,k).

,		0				0	0	(7.29)
	=						0
							.
		0		0

Способ 2. Рассматриваются многочлены Qi (x), соответствующие коду, содержащему только один ненулевой разряд: Qi (x) = xn-i, i =1,k . Для них вычисляются остатки

Ri (x) = Qi (x) / g (x).

Каждая i -я строка образующей матрицы формируется путем сложения по модулю два указанных многочленов и соответствующих им остатков. При этом образующая матрица (в данном случае систематического кода) представляется двумя подматрицами:

, = , , ,

где Ek – единичная k x k - матрица, а строками матрицы дополнения Pk,n-k являются остатки Ri (x), i =1,k.

227

7.15.6. Построение проверочной матрицы циклического кода

Проверочная матрица в данном случае может строиться так же, как в случае обычного группового кода, например, с использованием проверочных равенств и/или матрицыдополнения. Однако для циклического кода существует еще один способ построения проверочной матрицы, заключающийся в делении многочлена xn +1 на многочлен g-1(x), являющийся дополнением к образующему. Многочлен дополнения соответствует кодовой комбинации, которая получается из комбинации, соответствующей образующему многочлену путем перестановки символов в обратном порядке [6].

Предположим, что в результате деления двучлена xn +1 на многочлен дополнения получен некоторый многочлен:

+1	=	+ + + .	(7.30)
( )

Из коэффициентов этого многочлена составляется первая строка проверочной матрицы, а остальные строки образуются циклическим сдвигом:

	0			0	0	(7.31)
=					0
					.
	0		0

В качестве примера построим проверочную матрицу для кода (7,4), порождаемого образующим многочленом g(x)= x3+ + x2 +1. Соответствующий многочлен дополнения g-1= x3 + x2 +1. В результате деления на него двучлена x7 + 1 получаем многочлен x4 + x3 + x2 +1. Соответствующая этому многочлену проверочная матрица имеет вид

=	1	1	1	0	1	0	0
	0	1	1	1	0	1	0 .
	0	0	1	1	1	0	1

Нетрудно убедиться, что любая разрешенная комбинация

228

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

7.15.7. Линейные переключательные схемы

Цикличность перестановок при формировании разрешённых кодовых комбинаций ЦК лежит в основе техники построения кодирующих устройств и декодирующих устройств циклических кодов. Эта техника применяет сдвигающие регистры (CP) в виде триггерных цепочек с теми или иными обратными связями. Такие CP называют также многотактными линейны-

ми переключательными схемами (ЛПС) и линейными кодовы-

ми фильтрами Хаффмена, который первым начал изучение ЛПС с точки зрения линейных фильтров. При построении ЛПС используется 3 вида элементарных устройств:

1)сумматор, имеющий, как правило, два входа и один выход, причём для двоичных кодов суммирование осуществляется по mod 2;

2)запоминающее устройство, имеющее один вход и один выход и представляющее собой одну триггерную ячейку (один разряд) CP;

3)устройство умножения на постоянную величину, имеющее один вход и один выход. Эти устройства изображаются на схемах так, как показано на рис. 7.13.

Рис. 7.13. Основные элементы ЛПС

Линейными переключательными схемами с конечным числом состояний называются любые схемы, содержащие ко-

229

нечное число сумматоров, устройств памяти и устройств умножения на константу, соединённых любым допустимым способом.

В бинарном случае сумматор (равно как и вычитатель) представляет собой логический элемент "исключающее ИЛИ", а устройство памяти является устройством задержки (D-триггером). Устройства задержки, включённые последовательно, составляют CP, в ячейках которого выходной символ совпадает с входным символом в предшествующий момент времени. К CP подводится шина сдвига, с помощью которой тактовыми импульсами осуществляется продвижение по разрядам CP записанной кодовой информации. Как правило, шина сдвига не показывается на схемах с изображениями ЛПС.

При формировании и обработке двоичных ЦК введение в

схему ЛПС умножителя на константу, равную 1, эквивалентно введению дополнительного соединения, а умножитель на константу, равную 0, соответствует отсутствию такого соединения.

Предполагается, что на вход CP, входящего в состав ЛПС, кодовая комбинация подаётся последовательно, с периодичностью, равной периоду следования тактовых импульсов в шине сдвига. Аналогично, последовательно во времени, появляются кодовые символы на выходе СР. Когда входом или выходом является многочлен, представляющий при двоичной обработке набор"1" и "0", то на входном или выходном конце CP появляются только коэффициенты ("1" или "0"), начиная с коэффициентов высших порядков. Это обуславливается тем, что при делении у делителя сначала должны быть обработаны коэффициенты высших порядков.

7.15.8. Умножение полиномов на базе линейных переключательных схем

Схема, изображенная на рис. 7.14, используется для умножения любого полинома на входе

230