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

					7	6	5	3		4 2 1
					0	0	0	1	:	0	1	1		,
M n,k		IkT : Bn k ,k			0 0 1 0 : 1						1	0
					0	1	0	0	:	1	1	1
					1	0	0	0	:	1	0	1

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

10.3. n -разрядные комбинации неразделимого циклического кода получаются умножением многочленов, соответствующих k - разрядным информационным комбинациям, на порождающий многочлен g(x) .

Искажение произошло в разряде 6. Следовательно, передавался код 0111, после кодирования которого на выходе кодера была ком-

бинация 0100011.

10.4. Параметры группового кода определяются в соответствии

с неравенствами	2k 1 3 ,	2n k 1	n n(n 1)	, т.е.
			2

k 2 , n 7 .

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

Удовлетворить этому требованию можно только при параметрах группового кода (8,2), который в свою очередь характеризуется образующей матрицей

						8			5		7	6	4	3	2	1
								0
M	n,k			I T : B	n k ,k				1	:	0	0	1	1	1	1	.
				k				1	0	:	1	1	0	0	1	1

10.5. Циклический код строится путем приписывания к каждой неизбыточной комбинации информационных символов остатка от деления этой комбинации на g(x) . При этом под информацион-

291

ные символы принято отводить k						старших разрядов, а под прове-
рочные –		( n k ) младших. Процесс построения кода приведен в
табл. 11.5.
							Таблица 11.5
Код	ai (x)x		3	ai (x)x3			~	3	ri (x)
				ri (x)	g(x)		ai (x) ai (x)x
0001		x3		x2 1			x3 x2 1		0001:101
0010		x4		x2 x 1			x4 x2 x 1		0010:111
0100		x5		x 1			x5 x 1		0100:011
1000		x6		x2 x			x6 x2 x		1000:110

10.6. Известно, что неразделимый циклический код получается умножением многочленов, соответствующих k -разрядным информационным комбинациям, на порождающий многочлен g(x) . Процесс построения кода приведен в табл. 11.6.

				Таблица 11.6
Информационный	ai (x)	~			Циклический
код		ai (x) ai (x) g(x)			код
0001	1	x3 x 1			0001011
0010	x	x4 x2	x		0010110
0100	x2	x5 x3	x2		0101100
1000	x3	x6 x4	x3		1011000

10.7. Параметры циклического кода определяются в соответст-

вии	с неравенствами:	2k 1 1,	2n k 1 n n(n 1) / 2 ,	т.е.
k 1,	n 5 .
Выбираем порождающий многочлен deg g(x) n k 4 ,				кото-
рый являлся бы делителем двучлена			x5 1 0 mod g(x) . В разло-
жении x5 1 (x 1)(x4		x3 x2 x 1) такой многочлен единст-

292

венный – g(x) x4 x3 x2 x 1. Тогда образующая матрица принимает вид M5,1 1:1111 .

Таблица одиночных и двойных ошибок приведена в табл. 11.7.

				Таблица 11.7
i	i (x)		i (x)	Код -
				опознаватель
		g(x)
1	1		1	0001
2	x		x	0010
3	x2		x2	0100
4	x3		x3	1000
5	x4	x3 x2 x 1		1111
6	x 1		x 1	0011
7	x2 1		x2 1	0101
8	x3 1		x3 1	1001
9	x4 1	x3 x2 x		1110
10	x2 x		x2 x	0110
11	x3 x		x3 x	1010
12	x4 x	x3 x2 1		1101
13	x3 x2	x3 x2		1100
14	x4 x2	x3 x 1		1011
15	x4 x3	x2 x 1		0111

10.8.Аппаратная реализация группового кода Хэмминга (3,1) с образующей матрицей M 3,1 1:11 приведена на рис. 11.24.

10.9.Аппаратная реализация циклического кода Хэмминга (3,1)

собразующей матрицей M 3,1 1:11 приведена на рис. 11.25.

10.10.Коды БЧХ строятся по заданным N и T. Значение k (число информационных разрядов) неизвестно, пока не найден порождающий многочлен кода G(x). В конкретном случае

293

G(x) НОК[F1(x), F3 (x),...,Fi (x),...,FD 2 (x)] ,

где Fi (x) – минимальные многочлены, а D=2T+1 – минимальное расстояние Хэмминга кода БЧХ. Длина кода БЧХ, как правило,

определяется из выражения N 2m 1, где m - любое целое число. Иногда возникает ситуация, когда вычисленное по формуле

m log 2 (N 1) получается не целым. Тогда необходимо пользоваться формулой m log 2 (NC0 1) , подбирая минимальное C 0 такое, чтобы результат оказался целочисленным. Число проверочных разрядов кода БЧХ r mT , отсюда число информаци-

онных разрядов k 2m 1 mT .

C0

Кодер

3		2		1

Декодер

Канал

3

2

1

Дешифратор

=

						=
			Рис. 11.24. Кодер и декодер группового кода (3,1)
	Если r		2 m	1	, то код БЧХ не определен, так как число про-
			C0

верочных разрядов не может быть больше длины кода.

294

		Кодер
			Декодер
=	1	2
Выход		Фильтр	1	Логическая
			0	схема
	Вход
		Буферное
	Канал	запоминающее
		устройство

Рис. 11.25. Кодер и декодер циклического кода (3,1)

Порождающий многочлен кода длины N=21, служащий для исправления двухкратных ошибок T=2, получается следующим

образом. Формула m log 2 (N 1) к положительным результатам не приводит, а формула m log 2 ( NC 0 1) при C0 3 дает m=6. Далее обращаемся к таблице минимальных многочленов (табл. 10.6). Выбираем минимальные многочлены F1 (x) и F3 (x) ,

так как D-2=3. Умножаем индексы выбранных многочленов на C0 и окончательно получаем

G(x) НОК[F3 (x), F9 (x)]

НОК[x6 x4 x2 x 1, x3 x2 1]x9 x8 x7 x5 x4 x 1 .

Следовательно, r deg G(x) 9 и k 12 . Строки образующей матрицы кода (21,12) находятся как остаток от деления произведения x j G ( x ) на двучлен x N 1 (рис. 11.26).

295

	000000000001:110110011
	000000000010:011010101
	000000000100:110101010
	000000001000:011100111
	000000010000:111001110
M21,12	000000100000:000101111	Рис. 11.26. Образующая
	000001000000:001011110
	000010000000:010111100	матрица кода БЧХ (21,12)
	000100000000:101111000
	001000000000:101000011
	010000000000:100110101
	100000000000:111011001

Традиционный подход исправления ошибок достаточно трудо-

емкий, так как получить	T	N			опознавателей не представляется
			i
	i 1

целесообразным. Воспользуемся следующим алгоритмом декоди- рования.

Допустим, что передавалась кодовая комбинация A(x) , постро-

енная на основе образующей матрицы кода БЧХ (N, k) с порождающим многочленом G(x) , способным исправлять ошибки крат-

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

В результате воздействия помех в канале связи в приемнике получена комбинация A* (x) A(x) E(x) , где E(x) – многочлен

ошибки. Делим A* (x) на G(x) и вычисляем вес W полученного

остатка. Если W T , производим циклический сдвиг предыдущего делимого влево на один разряд и опять выполняем деление на многочлен G(x) .

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

Процесс исправления ошибок для циклического кода БЧХ

(21,12) приведен на рис. 11.27.

10.11. Образующая матрица кода БЧХ (31,1) имеет вид

M 31,1 1:1111111111 1111111111 1111111111 .

296

2m 1.

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

ражения g(x) p(x)(xc 1) , где p(x) – неприводимый много-

член степени m . Длина кода n равна наименьшему общему кратному e и c : n НОК{e,c} , где e – показатель для p(x) , т.е.

наименьшее число, при котором

xe 1 0 mod p(x) .

Передаваемое сообщение:
A(X)= 110000000000011101100.
Кратность ошибки: T= 2.
Вектор ошибки:
E(X)= 110000000000000000000.
В результате действия помех в канале связи на приемном конце была приня-
та комбинация:
A"(X)=000000000000011101100.
Проводим деление принятой комбинации на G(X) .
		Цикл N 1
Остаток: 11101100 с весом W = 5.
Так как W>T , то надо произвести циклический сдвиг			A"(X)	влево	на	1
разряд и снова произвести деление на G(X) .
		Цикл N 2
Остаток: 111011000 с весом W = 5.
Так как W>T , то надо произвести циклический сдвиг			A"(X)	влево	на	1
разряд и снова произвести деление на G(X) .
		Цикл N 3
Остаток: 11 с весом W = 2.
Теперь, когда	W<=T ,	можно произвести сложение по модулю 2 циклически
сдвинутой комбинации A"(X) и полученного остатка.
Комбинация A"(Х) , циклически сдвинутая влево на 2 разряда:
000000000001110110000.
Сумма циклически сдвинутой комбинации A"(X) и полученного остатка:
000000000001110110011.
Наконец, проведем обратный циклический сдвиг этой суммы вправо на						2
разряда.
Получили переданное сообщение:
110000000000011101100.
	Рис. 11.27. Процесс исправления ошибок
В частности,	если	p(x) является примитивным многочленом,

то e 2m 1 . Степень двучлена должна удовлетворять условию c b l 1 , причем c не должно делиться нацело на

297

Число проверочных разрядов равно r m c . Код позволяет обнаружить пакет ошибок длиной b l и исправить вспышку

ошибок длиной	l m .
В соответствии с условием задачи степень					deg p(x) m l .
Степень двучлена c b l 1 9 .
Выберем	в	качестве	неприводимого			многочлена
p(x) x5 x2 1.		Порождающий		многочлен		имеет вид
g(x) (x5 x 1)(x9 1) .			Длина	кодовой		комбинации
n (25 1)9 279 ,		а	число	проверочных		символов
m 9 5 14 .	Следовательно, код			Файра	имеет	параметры

(279,265).

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

ставит 14/279=0,05.

Любой циклический код, рассчитанный на исправление T - кратных ошибок, может быть использован для исправления пакетов ошибок длины не более T . Однако избыточность кода будет существенно выше по сравнению с циклическим кодом Файра, имеющим ту же корректирующую способность. Так, если для исправления пакетов ошибок длины 5 воспользоваться БЧХ кодом с близким значением n 255 , то при T 5 число проверочных символов составит 40, а избыточность – 40/255=0,16.

Это подтверждает вполне очевидный вывод: исправить пакет ошибок проще, чем то же количество ошибок, рассредоточенных по всей комбинации.

10.14.Параметры циклических кодов Файра с l m приведены

втабл. 11.8.

		Таблица 11.8
i	(n, k)	l m
1	(693,676)	6
2	(1651,1631)	7
3	(3825,3802)	8
4	(8687,8661)	9
5	(19437,19408)	10

298

10.15. Результаты получены с использованием компьютерного учебника ОТИК 4.15 (рис. 11.28).

Рис. 11.28. Результаты синтеза кодера и декодера

299

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

(жирным шрифтом выделена основная литература)

1.Котоусов А.С. Теория информации. Учебное пособие для вузов. – М.: Радио и связь, 2003.

2.Липкин И.А. Статистическая радиотехника. Теория информации и кодирования. – М.: Вузовская книга, 2002.

3.Гоноровский И.С. Радиотехнические цепи и сигналы. – М.: Со-

ветское радио, 1986.

4.Темников Ф.Е. и др. Теоретические основы информационной техники. – М.: Энергия, 1979.

5.Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования. – Киев: Вища школа, 1986.

6.Федосеев Ю.Н. Элементы теории передачи и кодирования дискретной информации в АСУ. – М.: МИФИ, 1981.

7.Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. – М.: Мир, 1986.

8.Абдуллаев Д.А., Арипов Н.Н. Передача дискретных сообщений в задачах и упражнениях. Учебное пособие для вузов. – М.: Радио и связь, 1985.

9.Березкин Е.Ф. Основы теории информации и кодирования.

Лабораторный практикум: Учебно-методическое пособие. – 2-е изд., перераб. и доп. – М.: МИФИ, 2009.

10.Фано Р. Передача информации. Статистическая теория связи. – М.:

Мир, 1965.

11.Дмитриев В.И. Прикладная теория информации. Учебник для вузов по специальности "Автоматизированные системы обработки информации и управления". – М.: Высшая школа, 1989.

12.Хэмминг Р.В. Теория кодирования и теория информации. – М.: Радио и связь, 1989.

13.Хетагуров Я.А., Руднев Ю.П. Повышение надежности цифровых устройств методами избыточного кодирования. – М.: Энергия, 1974.

14.Древс Ю.Г., Реутов В.Ф. Ортогональные преобразования сигналов

иих применение в технике. – М.: МИФИ, 1988.

15.Березкин Е.Ф. Сборник задач по курсу "Основы теории информации и кодирования". – М.: МИФИ, 2002.

16.Панин В.В. Основы теории информации. Ч.1. – М.: МИФИ, 2001.

17.Панин В.В. Основы теории информации. Ч.2. Введение в теорию кодирования. – М.: МИФИ, ФГУП ИСС, 2004.

300