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

10. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

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

сти (рис. 10.1) [4].

Корректирующие коды

Алгебраические Неалгебраические

Рекуррентные Блоковые

Систематические Несистематические

Групповые Циклические

Разделимые Неразделимые

Рис. 10.1. Классификация корректирующих кодов

211

В рекуррентных кодах процесс кодирования и декодирования носит непрерывный характер. В блоковых кодах каждому сообщению сопоставляется кодовая комбинация из n символов. Блоки кодируются и декодируются отдельно друг от друга. В систематических кодах применяются линейные операции над символами. Групповые и циклические являются частным случаем систематических кодов и в своей основе имеют алгебраические структуры – группы и кольца. В разделимых кодах происходит простое разделение информационных разрядов и разрядов избыточных (контрольных). Коды, получившие наиболее широкое развитие, в схеме выделены жирными линиями.

10.1. ОСНОВНЫЕ ПРИНЦИПЫ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

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

n

n

k

k

ИИ

КДии

КДк

ДКк

ДКии

ПИ

Канал

Bi

Di

Ai

Рис. 10.2. Средства помехоустойчивого кодирования

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

Всего может быть 2 k различных входных последовательностей

B и 2 n	различных выходных последовательностей D . Из обще-
i			i
го числа	2 n выходных последовательностей	D	только 2 k соот-
		i

ветствуют входным и носят название разрешенных кодовых ком-

212

бинаций. Остальные Di последовательности, число которых

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

A1

B

1

2

…

k

1

2

…

n

…

1

КДк

…

A2k

B2k

1

2

…

k

1

2

…

n

Рис. 10.3. Введение избыточных символов

Искажение информации в процессе передачи сводится к тому, что часть символов заменяется другими (ошибки типа сбоя 1 в 0 или наоборот). В результате разрешенные кодовые комбинации после передачи заменяются или трансформируются в другие. Возможные трансформации разрешенных кодовых комбинаций при прохождении по каналу с помехами представлены на рис. 10.4.

Отметим, что существует 2k 2n возможных переходов комбинаций из одной в другие. При этом число случаев переходов из раз-

решенных B в разрешенные D – 2k 2k , среди которых правиль-
i	i
ных переходов –	2k . Число случаев, когда переход осуществляется
из разрешенных комбинаций в запрещенные, –					2k (2n 2k ) .
B	D
1			1
B2	D2					Разрешенные
B3	D3
						комбинации
...	...
	D
B2 k		2		k
	...					Запрещенные
	D2 n					комбинации

Рис. 10.4. Комбинации возможных переходов вследствие ошибок

213

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

pобн	2k (2n 2k )	1	2k 1	1 2 (n k ) .
	2k (2n 1)		2n 1

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

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

ва полученных комбинаций Di на непересекающиеся подмноже-

ства	W , i 1,2k		или классы (рис. 10.5). При получении кодовой
	i

последовательности Di , принадлежащей Wi , принимается решение о том, что передавалась по каналу последовательность Bi . Ошибка может быть исправлена правильно в том случае, если действительно передавалась Bi .

B1

B2

...

B2 k

W1

A1 Di

(2n 2k )

W2

A2 2k

...

W2k A2k

Рис. 10.5. Принцип исправления ошибок

Суть исправления ошибки состоит в том, что каждому классу Wi сопоставляется одна из входных последовательностей Ai дли-

ны k . Последовательность Ai длины k можно так закодировать в последовательность Bi длины n , что воздействие ошибок в канале

214

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

ками принятая последовательность Di длины n , и тем самым точно восстановить исходную последовательность символов Ai дли-

ны k .

Условная вероятность правильного исправления ошибки при условии, что она имеет место, в этом случае равна

	pисп	2n 2k		1		1	2 k 2 n .
		2k (2n 1)		2k		2n

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

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

жения служит модель ДСК.

Будем называть количество искаженных разрядов r кратностью ошибки. Вероятность искажения r символов в кодовой ком-

бинации длины n равна q		n		q)n r . При q 1 строятся
	r		qr (1
		r

коды для исправления ошибок малой кратности. Этот случай наиболее интересен практически с учетом достаточно высокой надежности передачи цифровых данных по современным каналам связи.

Пакетом ошибок длины l называется любая комбинация ошибок, число разрядов в которой между первой и последней ошибками, включая и эти ошибки, равно l . Например, пакет ошибок дли-

ной 4 имеет вид 0…00110100.

Степень отличия двух кодовых слов оценивают через расстояние Хэмминга d( X ,Y ) . Это расстояние равно числу позиций, в

которых	различаются	два	кода	X (x1 , x2 ,..., xn )	и
Y ( y1 , y2 ,..., yn ) . Определим вес кода				W как число единиц в

215

данном коде. Тогда	расстояние по Хэммингу	равно
d( X ,Y ) W (x1 y1 , x2	y2 ,..., xn yn ) W (X Y ) , где	знак
означает суммирование по модулю 2.

Слово на выходе канала можно рассматривать как входное слово X , искаженное при передаче по каналу с шумом Y X E ,

где E (e1 , e2 ,..., en ) – вектор ошибки, содержащий единицы на тех позициях, которые были искажены при передаче.

Например, Y X E (10100101) (10001000 ) (00101101) .

Учитывая d(X ,Y ) W ( X Y ) , получаем d(X ,Y ) d(X , X E)W ( X X E) W (E) , т.е. расстояние между переданным и принятым словами равно весу вектора ошибки.

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

минимальным расстоянием Хэмминга d этого кода. Под d по-

нимают минимальное расстояние, взятое по всем парам кодовых комбинаций данного кода.

Рассмотрим трехразрядные кодовые последовательности. Если d 1, то все кодовые слова образуют равнодоступный код: 000, 001,…, 111. Этот код не обладает обнаруживающими и корректи-

рующими способностями. Возьмем				d 2 и образуем, например,
такие две группы:
000	011	101	110	001	100	010	111 .
Разрешенныекомбинации				Запрешенныекомбинации
Этот код обнаруживает все ошибки кратности 1.
Для обнаружения ошибки кратности					rо необходимо и доста-

точно, чтобы минимальное кодовое расстояние разрешенных кодовых комбинаций удовлетворяло неравенству d rо 1.

Возьмем d 3 и представим запрещенные комбинации в виде непересекающихся подмножеств (рис. 10.6). Этот код обнаруживает однократные и двухкратные ошибки, а также исправляет все однократные.

216

Для исправления любой ошибки кратности rи необходимо, что-

бы минимальное расстояние кода удовлетворяло неравенству d 2rи 1.

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

	001
000	010
Разрешенна
	100 Запрещенные
Разрешенна	110 Запрещенные
111	101
	011

Рис. 10.6. Переходы разрешенных комбинаций в запрещенные

Справедливость введенных неравенств d rо 1 и d 2rи 1 может быть наглядно продемонстрирована с помощью рис. 10.7.

	d
	ro
1-я разр.	rи	2-я разр.
комбинация		комбинация

3-я разр. комбинация

Рис. 10.7. К определению зависимости кратности обнаруживаемых

иисправляемых ошибок от d

Ввесьма общем виде содержание современной алгебры можно охарактеризовать так: изучение алгебраических операций над элементами произвольной природы [17].

217

ОПРЕДЕЛЕНИЕ 10.1. Под алгебраической операцией, опреде-

ленной в данном множестве M , понимается соответствие, в силу которого произвольным элементам x, y M , взятым в определен-

ном порядке (x, y) , соотносится вполне определенный элемент

z M .

Такое определение операции приводит к понятию внутреннего закона композиции. Если же второй элемент берется из другого

множества y N и (x, y) z M , то такая алгебраическая опе-

рация носит название внешнего закона композиции.

Задание на множестве M одного или нескольких законов композиции (внутренних или внешних) определяет на множестве M алгебраическую систему (структуру). Часто используемыми алгебраическими системами в соответствии с усложнением их математической структуры являются: группа; кольцо; поле.

Теория групп, колец и полей является математической основой построения корректирующих кодов, нашедших широкое применение на практике.

10.2.МАТЕМАТИЧЕСКОЕ ВВЕДЕНИЕ

КГРУППОВЫМ КОДАМ

ОПРЕДЕЛЕНИЕ 10.2. Группой G называется множество элементов, если для каждой его пары определена операция сложения и выполняются следующие аксиомы:

1)	замкнутость x y z;	x, y G z G ;
2)	закон ассоциативности	(x y) z x ( y z) ;
3)	существование нейтрального элемента 0 x x ;
4)	существование обратного элемента x G x G;

x ( x) 0 .

Ясно, что группа обладает единственным нейтральным элементом. Если операция, определенная на множестве G , коммутативна x y y x , то группа называется коммутативной (абелевой).

Группа конечна, если число ее элементов конечно. Порядок группы – число ее элементов.

218

Например, множество всех n разрядных двоичных чисел обра-

зует абелеву группу порядка 2n относительно операции поразрядного сложения. Нейтральный элемент группы: 00…000. Обратным элементом является сам элемент.

ОПРЕДЕЛЕНИЕ 10.3. Подмножество A множества G называется подгруппой группы G , если оно само является группой относительно операции, определенной в G .

При проверке того, является ли A подгруппой группы G , достаточно проверить следующее:

–содержится ли в A сумма любых двух элементов из A ;

–содержит ли A вместе со всяким своим элементом и его обратный.

ОПРЕДЕЛЕНИЕ 10.4. Пусть A – подгруппа группы G . Тогда множество всех элементов вида x xA , получающееся при сложе-

нии x G с каждым элементом xA A , называют левым смеж-

ным классом группы G по подгруппе A , определяемым элементом x , и обозначают x A .

Аналогично определяется правый смежный класс группы G

по подгруппе A : A x . В абелевой группе левый смежный класс совпадает с правым смежным классом и называется просто смежным классом.

Например, множество G {000,001,010,011,100,101,110,111}

является группой. Подмножество A {000,001,010,011} – под-

группа, так как имеет место замкнутости относительно операции поразрядного сложения 000 001 001,...,010 011 001.

Смежные классы группы G по подгруппе A можно образовать, беря последовательно элементы из x G :

A 000 {000,001,010,011},	A 100 {100,101,110,111};
A 001 {001,000,011,010},	A 101 {101,100,111,110};
A 010 {010,011,000,001},	A 110 {110,111,100,101};
A 011 {011,010,001,000},	A 111 {111,110,101,100}.

219

Мы показали, что любые два смежных класса группы G по

подгруппе A либо совпадают, либо не имеют ни одного общего элемента. Одним из смежных классов является сама подгруппа

A A 0 . Кроме того, A xA A , так как xA A .

ОПРЕДЕЛЕНИЕ 10.5. Число различных смежных классов группы G по подгруппе A называют индексом подгруппы A в группе G и обозначают indexAG .

Разложение группы по подгруппе приводит к разбиению группы G на непересекающиеся подмножества, а порядок группы равен порядку подгруппы умноженному на индекс этой подгруппы в группе: G A indexAG .

Таким образом, беря последовательно некоторые элементы группы x G , которые не вошли в уже образованные классы, можно разложить всю группу G на смежные классы по подгруппе A . Элементы x , по которым производится разложение, называют

образующими элементами смежных классов.

Например, дадим таблицу разложения группы четырехразряд-

ных двоичных чисел G {0000,0001,0010,0011,0100,0101,0110, 0111,1000,1001,1010,1011,1100,1101,1110,1111} по подгруппе двухразрядных чисел A {0000,0001,0010,0011}, представленных в едином формате:

0000		0100			1000			1100
0001	A 0000	0101		A 0100	1001		A 1000	1101		A 1100 .
0010		0110			1010			1110
0011		0111			1011			1111

Группа G разложилась на четыре смежных классов по подгруппе A . В общем случае, число смежных классов при разложении группы n -разрядных чисел по подгруппе k -разрядных двоичных чисел равно:

indexAG 2n 2n k .

2k

220