Березкин Основы теории информации и кодирования 2010

ме), то последовательные состояния фильтра будут равны

			(0)		i	e(x) ,
				(x) x
	(1) (x) xi 1e(x) ,
				...			mod g(x) ,
	(i)			0
		(x) x			e(x) e(x)

т.е. вычет вида ошибки будет воспроизведен точно через i тактов. В простейшем случае, когда возникла одиночная ошибка

E ( x) x i , т.е.

e(x) 1, то на i -м такте

(i) (x) 1 или

(i) 00...01. При появлении такой комбинации на выходе логи-

r ... 2 1

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

Логическая схема

…

			r	...	1
				Фильтр
Вход											Выход
				Буферное ЗУ

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

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

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

251

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

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

(i) (i 1) Mt ai 1 F , yi (i 1) B ai 1 ,

где (i ) ( 1(i ) ,..., (ri ) ) – вектор состояния фильтра в момент времени i ; Mt – транспонированная матрица связей; ai 1 ( yi ) –

значение входного (выходного) символа в момент времени i 1 ( i ); F – (1 r) матрица связей между входом и элементами за-

держки фильтра; B – (r 1) матрица связей между элементами задержки и выходом фильтра; – (1 1) матрица связей между входом и выходом фильтра.

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

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

матического аппарата линейных последовательностных машин):

			(i) (i 1) Mt A(i 1) F ,
			Y (i) (i 1) B A(i 1)			,
где A(i 1)		(a(i 1) ,..., a(i 1) ) – входной вектор в момент времени
		1
i 1; Y (i)		( y(i) ,..., y(i) ) – выходной вектор в момент времени i ;
		1
	F Mt 1
F	F	M 2	– ( r ) матрица связей между входами фильтра
		t
		...
		F
и элементами задержки; B					B Mt B ...	Mt 1 B		– ( r )

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

252

		F B	F Mt B	...	F Mt 2 B
	0		F B	...	F M 3	B
					t		– ( ) матрица
ра;				...
	0	0	0	...

связей между входами фильтра и его выходами.

В качестве примера рассмотрим построение двухканального кодера ( 2) для разделимого циклического кода (7,4), порож-

даемого многочленом g( x) 1 x2 x3 .

Матричное описание одноканального кодера задается матрица-

ми

M		0	1	0			M t		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

Структура одноканального кодера представлена на рис. 10.15. При известных схемотехнических решениях матрицы B(B ) и

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

тины построения	-канального аналога одноканальной линейной
последовательностной машины.
=	D1	D2	D3
Выход	2
	Вход
	1

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

253

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

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

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

=	D1	D3

Выход 1

Вход 1

= D2

Выход 2

Вход 2

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

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

	k
после выполнения	z			тактов (квадратные скобки означают
				число), содержимое -канального
наименьшее большее целое

254

кодера будет равно R (x) R(x) x (z k) modg(x) ,		где R(x)
соответствует контрольному коду. Поэтому, если	(z k) 0 ,
требуется коррекция содержимого фильтра. Однако		коррекции
можно избежать, если полином Ak ( x) , соответствующий ин-
формационным разрядам, умножить на x( z k ) .	В этом случае
R (x) R(x) x (z k) x(z k) R(x) modg(x) .	Известно, что

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

a0	приписывается (z k)				фиктивных нулей. При этом разряд
a0	поступает на (z k) 1 вход (канал) кодера, разряд a1 – на
(z k) 2 канал и т.д.
	Блок-схема канального декодирующего устройства представ-
лена на рис. 10.17.
							1
					ω1
					ω2		2
									Логическая
	...		Фильтр				…
									схема
					ωn-k
							n-k

1		1
2	Буферное	2

...	ЗУ	...

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

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

255

z	n			тактов. Поэтому при наличии ошибки вида xi	состояние

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

0 (x) xi (z n) modg(x) ,

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

1 (x) xi ( z n) mod g(x),

2 (x) xi ( z n) 2 mod g(x),

3 ( x) xi ( z n ) 3 mod g ( x),

... .

Пусть i j ( ) , т.е. ошибка должна быть исправ-

лена в такте j . Тогда на j -м такте автономной работы состояние фильтра равно

j (x) x j ( z n) j x ( z n) mod g(x) ,

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

при	0	x ( z n )
при	1	x1 ( z n )
	...

,

,mod g(x) .

при 1
	x 1 ( z n)

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

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

при	0	x 1 x7 1 x6	x2 x ,	т.е. 110;
при	1	x1 1 x0	1 , т.е.	001.

256

ЗАДАЧИ

10.1. Используется групповой код Хэмминга (7,4), исправляющий одиночные ошибки. На приемном конце принята комбинация

1011011. Какой код был передан?
10.2.	Используется		разделимый		циклический		код	(7,4)	с
g(x) x3 x 1.		На	приемном	конце		принята	комбинация
1001:011. Какой код был передан?
10.3.	Используется		неразделимый		циклический		код	(7,4)	с
g(x) x3 x2 1 .		На	приемном	конце		принята	комбинация

0000011. Какой код был передан?

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

10.5.Построить разделимый циклический код Хэмминга (7,4) с

порождающим многочленом g(x) x3 x2 1.

10.6.Построить неразделимый циклический код Хэмминга (7,4)

спорождающим многочленом g(x) x3 x 1.

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

10.8.Построить кодирующее и декодирующее устройства для группового кода Хэмминга (3,1) .

10.9.Построить одноканальное кодирующее и декодирующее

устройства для циклического кода Хэмминга (3,1) с g(x) x2 x 1.

10.10. Построить циклический код Боуза–Чоудхури– Хоквингема (БЧХ), имеющий длину N 21 и служащий для исправления ошибок кратности T 2 включительно. Продемонст-

рировать процесс исправления ошибки.
10.11. Построить	циклический код БЧХ, имеющий	длину
N 31 и служащий	для исправления ошибок кратности	T 15

включительно.

10.12. Построить циклический код Файра, позволяющий обнаружить пакет ошибок длиной b 5 и исправить одиночную вспышку (пакет) ошибок длиной l 5 .

10.13. Определить избыточность кода Файра (279,265) и сопоставить ее с избыточностью циклического кода БЧХ с близким

257

значением n 255 .

10.14. Найти параметры циклических кодов Файра, полагая

l m	1	и	6 l 10 .
10.		5.	Построить четырехканальное кодирующее устройство
( 4)		и декодирующее устройство для разделимого циклическо-
го кода			Хэмминга (31,26), порождаемого многочленом

g(x) x5 x3 1 .

258

11. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО РЕШЕНИЮ ТИПОВЫХ ЗАДАЧ И ОТВЕТЫ

1.1. Для доказательства достаточно воспользоваться известными свойствами:

cos(k 0t) e jk 0t e jk 0t ,

2

sin(k 0t) e jk 0t e jk 0t .

2 j

Тогда

12

Ak

e j (k 0t k )

A k

e j (k 0t k )

Ak

cos(k 0t k ) ,

с учетом того, что

Ak

A k

и k k .

1.2. Тригонометрическая форма ряда Фурье имеет вид

x(t )

A0

Ak

cos( k 0 t k )

2

k 1

A0

(ak cos k 0 t bk sin k 0 t ),

2

k 1

где

A0

– постоянная составляющая функции x(t) ;

A

, k

0

,

k

–

2

k

амплитуда, частота и начальная фаза k-й гармонической состав-

	ляющей;			Ak			cos( k 0t k ) – k-я гармоническая составляющая;
	0	2				– частота основной гармоники (T – период колеба-
		T

ний).

Ряд Фурье с учетом свойств периодической функции x(t) приобретает еще более простой вид:

x(t) bk sin k 0t	– нечетная функция.
k 1

Коэффициент bk вычисляется в соответствии с известным вы-

259

ражением

2

T / 2

bk

Ak

sin k

x(t) sin( k 0t)dt .

T

Итак, поскольку функция x(t)

T / 2

– нечетная, разложение будем

искать в виде ( ak = 0)

bk 4h

T / 2

4h

1

T / 2

0

sin( k 0t)dt

cos k 0t

T

k 0

T

0

2h

4h

, k 1,3,5,...;

(cos k 1)

k

k

2,4,6,... .

0, k

Спектр фаз приобретает вид

bk

bk

k

arctg

arctg

2

.

ak

0

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

x(t)			4h	(sin t			1 sin 3 t 1 sin 5 t ...) .
					0		3		0		5		0
Ak ( )
											0		3 0 5 0		7 0
							k ( )
h/
4h/3
								- /2
		4h/5			4h/7

0 3 0 5 0 7 0

Рис. 11.1. Спектр амплитуд и спектр фаз меандра

260