Березкин Основы теории информации и кодирования Лабораторный практикум 2009

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

Лабораторная работа 8

ПОСТРОЕНИЕ КОДИРУЮЩИХ И ДЕКОДИРУЮЩИХ УСТРОЙСТВ ЦИКЛИЧЕСКОГО КОДА ХЭММИНГА

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

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

Структура фильтра описывается матрицей связей между его элементами

M = m ij , i , j = 1, r ,

где r – количество элементов задержки в фильтре, а m ij = 1 , если выход j -го элемента задержки связан со входом i -го элемента задержки, в противном случае mij = 0 .

Вектор-столбцам матрицы M поставим в соответствие полиномы

r

μj (x) = ∑mij xi−1 , j =1, r .

i=1

Тогда матрицу M можно записать в виде

M = μ1 (x),μ2 (x),...,μr (x) .

Полиномы μ j (x) выберем таким образом, чтобы

71

μ1 ( x) ≡ g1 + g 2 x + ... + g r x r −1

≡ x −1 ,

μ2 ( x) ≡ xμ1 ( x) ≡ 1 ,

μ3 ( x) ≡ x 2μ1 ( x) ≡ x ,

mod g ( x) ,

...

μr ( x) ≡ x

r −1

μ1 ( x)

≡ x

r −2

где g(x) =1+ g1 x + g2 x2 +...+ gr xr –

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

Тогда схема, описываемая матрицей связей

g 1

1

0 ...

0

g 2

0

1 ...

0

M =

x −1 ,1, x ,..., x r − 2

=

...

,

g r −1

0

0 ...

1

g r

0

0 ...

0

позволяет выполнять деление на полином g(x) .

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

если

исходному

состоянию

фильтра

Ω(0) = (ω , ω

2

,..., ω

r

)

поставить

в

соответствие

полином

1

Ω( 0) ( x) = ω1 + ω2 x + ... + ωr x r −1 , то состояние фильтра в следующем такте (на вход схемы информация не поступает) равно

Ω(1) ( x) ≡ Ω( 0 ) M t = ω1 x −1 + ω2 + ω3 x + ... + ωr x r −2 ≡

≡ (ω1 + ω2 x + ... + ωr x r −1 ) x −1 = Ω( 0 ) ( x) x −1 mod g ( x),

где M t – транспонированная матрица связей.

Входную цепь фильтра построим таким образом, чтобы

Ω( i ) ( x ) ≡ [Ω( i −1) ( x ) + si −1 ]x −1 mod g ( x ) ,

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

Если начальное состояние Ω(0) (x) = 0 и на вход фильтра поступает последовательность символов s0 , s1 ,..., sn −1 , а эта по-

72

следовательность соответствует коэффициентам произвольного полинома степени n −1: S(x) = s0 + s1 x +... + sn−1 xn−1 , то фильтр будет последовательно принимать состояния

Ω(1) (x) ≡ s0 x−1,

Ω(2) (x)

≡ (s x−1

+ s )x−1 = s x−2 + s x−1

,

0

1

0

1

mod g(x) .

...

Ω(n) (x)

≡ s

0

x−n

+ s x−(n−1)

+...+ s

n−1

xn−1

1

Следовательно, Ω( n) (x) ≡ s

0

+ s x + ... + s

n−1

x n−1 mod g(x)

,

1

так как xn

≡1mod g(x) .

После

поступления последнего

символа

sn−1 содержимое

фильтра будет равно остатку от деления полинома S(x) на g(x) .

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

Кодер работает следующим образом. Сначала ключ находится в 1-м положении, и информационные разряды поступают на вход фильтра, который вначале находится в нулевом состоянии, и непосредственно в линию связи. Затем ключ переключается во 2-е положение. В этом случае обратная связь в фильтре размыкается и контрольные разряды последовательно "выдвигаются" в линию. Таким образом, к концу передачи кодового слова фильтр оказывается в нулевом состоянии.

Формально работа кодера описывается следующим образом. После поступления k информационных символов содержимое фильтра равно

Ω(k ) (x) ≡ s			0	x−k + s x−k +1 +... + s			k −1	x−1 ≡
				1
≡ x−k (s	0	+ s x +... + s			k −1	xk −1 ) ≡ x−k		S(x) ≡ xn−k S(x) mod g(x),
			1

которое совпадает с контрольным вектором.

73

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

последовательно. В этом случае необходимо уметь строить линейные фильтры (кодеры), содержащие ν входов и ν выходов.

Последовательные состояния и значения выхода рассмотренных одноканальных линейных фильтров описываются матричными уравнениями

Ω(i) = Ω(i−1) Mt +si F ,

yi = Ω( i−1) B + si Ψ ,

где Ω( i ) = (ω1(i ) ,..., ω(ri ) ) – вектор состояния фильтра в момент времени (i) ; Mt – транспонированная матрица связей; si ( yi ) – значение входного (выходного) символа в момент времени (i) ; F – матрица связей (1×r) между входом и элементами задержки фильтра; B – матрица связей (r ×1) между элементами задержки и выходом фильтра; Ψ – матрица связей (1×1) между входом и выходом фильтра.

Если известны Mt , F, B и Ψ , то соответствующие уравнения

для ν -канального аналога фильтра, содержащего ν входов и ν выходов, имеют следующий вид (известный результат из математического аппарата линейных последовательностных машин):

Ω( i) = Ω(i−1) Mtν + S(i) F ,

Y(i) = Ω(i−1) B + S(i) Ψ ,

где S (i) = (s1(i) ,..., sν(i) ) – входной вектор в момент времени (i) ; Y (i) = ( y1(i) ,..., yν(i) ) – выходной вектор в момент времени (i) ;

74

B =

B

Mt B

... Mtν −1 B

– матрица связей

( r × ν )

между

элементами задержки и ν выходами фильтра;

F Mtν−1

F =

F M ν−2

– матрица связей ( ν×r ) между входами фильтра

t

...

F

и элементами задержки;

Ψ

F B

F Mt B ...

F Mtν−2 B

0

Ψ

F B ...

F Mtν−3 B

–

матрица

связей

Ψ =

...

0

0

0

...

Ψ

(ν × ν) между входами фильтра и его выходами.

В

качестве

примера

рассмотрим построение

одноканального

(ν =1) и двухканального кодера (ν = 2) для разделимого цикличе-

ского кода (7,4), порождаемого многочленом g(x) =1 + x2 + x3 . Структура одноканального кодера задается матрицами

M =	0	1	0	, Mt =	0	1	1
	1	0	1		1	0	0	,
	1	0	0		0	1	0

									1
F =		g1 g2 ... gr		=		0 1 1		, B =	0	, Ψ =		1		.
									0
и имеет вид, представленный на рис. 8.1.

При известных схемотехнических решениях матрицы B(B ) и Ψ(Ψ* ) , в принципе, можно и не строить. В большей степени они

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

75

D1 D2 D3

Выход 2

Вход

1

Рис. 8.1. Структура одноканального кодера

Матричное описание двухканального аналога имеет вид

Mt2 =	0				1		1			0	1	1	=	1		1	0				, F =				F Mt					=		1 1 0
	1			0		0				1 0 0				0		1	1																		,
	0				1		0			0	1	0		1		0	0									F						0 1 1
M 2 =			1		0		1			, F Mt =											0	1	1			=
			1 1 0												0	1 1					1	0	0					1 1 0						,
			0		1		0														0	1	0

аего структура представлена на рис. 8.2.

Врассмотренном примере количество информационных разря-

дов k кратно ν. В общем случае это условие не выполняется и

	k
после выполнения	z =			тактов (квадратные скобки означают
		ν

ближайшее целое большее число), содержимое ν-канального кодера будет равно: R (x) = R(x) x−(zν−k ) mod g(x) , где R(x) соответствует контрольному коду. Поэтому требуется коррекция содержимого фильтра, если (z ν − k) ≠ 0 . Однако коррекции мож-

но избежать, если полином S ( x) , соответствующий информаци-

онным разрядам, умножить на x( zν−k ) .	В этом	случае
R (x) ≡ R(x) x−( z ν−k ) x( z ν−k ) ≡ R(x) mod g(x) .	Известно,	что ум-

ножение равносильно операции сдвига. Реализация сдвига заключается в том, что перед младшим информационным разрядом s0

76

приписывается (z ν −k) фиктивных нулей. При этом разряд

s0

поступает на

(z ν−k) +1 вход (канал)

кодера, разряд s1 –

на

[(z ν−k) +2]-й канал и т.д.

=

D1

D3

Выход 1

Вход 1

= D2

Выход 2

Вход 2

Рис. 8.2. Структура двухканального кодера

Блок-схема одноканального декодирующего устройства представлена на рис. 8.3.

Коэффициенты s0 , s1 ,..., sn−1 полинома S(x) последовательно

поступают на вход буферного ЗУ и одновременно на вход многотактного фильтра, с помощью которого S(x) делится на g(x) . Если

ошибка отсутствует, то после поступления sn−1 содержимое фильтра будет равно нулю. Получение ненулевого результата свидетельствует о наличии обнаруживаемой ошибки E(x) = xie(x) .

Если продолжить работу декодирующего устройства (синхронно производить сдвиги БЗУ и блока деления в автономном режиме), то последовательные состояния фильтра будут равны

77

	C	0		i	e(x) ,
			(x) ≡ x
C1 (x) ≡ xi−1e(x) ,
			...			mod g(x) ,
i			i
C	(x) ≡ x			e(x) = e(x)

т. е. вычет вида ошибки будет воспроизведен точно через i тактов. В простейшем случае, когда возникла одиночная ошибка E ( x) = x i , т.е. e(x) =1, то на i -м такте Ci (x) ≡1 или

C i = 00...01. При появлении такой комбинации на выходе логической схемы должен появиться сигнал, который инвертирует ошибочный символ.

ЛС

…

ФИЛЬТР

Вход	Выход

БЗУ

Рис. 8.3. Структура декодирующего устройства

Блок-схема ν-канального декодирующего устройства представлена на рис. 8.4.

Принцип построения ЛС заключается в следующем. Для приема

	n	n
всего слова длиной		разрядов требуется z′ =			тактов. Поэто-
			ν

му при наличии ошибки вида xi состояние фильтра после приема кодового слова будет равно

78

C 0 (x) = xi−( z′ ν−n) mod g(x) ,

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

C 1 ( x) = x i −( z′ ν−n )−ν ,
C 2			′	ν−n )−2 ν ,
	( x) = xi−( z
	. . .							mod g(x) .
C j			′
	(x) ≡ xi−( z ν−n)− j ν ,
	. . .
							1
							2
			ФИЛЬТР
...							…		ЛС
							n-k

1		1
2	БЗУ	2
...		...
ν		ν

Рис. 8.4. Структура декодирующего устройства

Пусть i = j ν +β на в такте j . Тогда

(β < ν) , т.е. ошибка должна быть исправлена j -м такте автономной работы состояние

фильтра равно C j (x) ≡ x j ν+β−( z′ ν−n)− j ν ≡ xβ−( z′ ν−n) , т. е. логическая схема должна распознавать следующие вычеты:

79

при	β=0	′	ν − n )
		x − ( z
при	β =1	′
		x1−( z ν−n )

...

,
,	mod g(x) .

xν−1−( z′ ν−n)

при β = ν −1

Таким образом, ЛС в ν -канальном декодере содержит ν выходов. Например, пусть n = 7 , ν = 2 , g(x) =1+ x2 + x3 , тогда

z′ = 4 и логическая схема будет представлять собой две схемы совпадения на следующие коды:

при β=0 x−1 ≡ x7−1 ≡ x6 ≡ x + x2 , то есть 0 1 1;

при β=1

x1−1 ≡ x0 ≡1 , то есть 1 0 0 .

ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ

1.Изучить теоретический материал.

2.Построить одноканальное кодирующее устройство цикличе-

ского кода Хэмминга (7,4) с порождающим многочленом g(x) =1+ x + x3 .

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

4.Продемонстрировать процесс формирования проверочных разрядов.

5.Построить структуру трехканального декодирующего устройства циклического кода Хэмминга (7,4) с порождающим много-

членом g(x) =1+ x + x3 .

6.Продемонстрировать процесс исправления произвольной однократной ошибки.

7.Продумать действия, когда количество информационных

разрядов k или длина кода n не кратны канальности ν. 8. Отразить подготовку в лабораторном отчете.

80