Учебное пособие по дисциплине СиСПИ

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

Процесс исправления ошибок рассмотрим сначала для симметричного канала без памяти. В таком канале по определению, вероятность правильного приема символа 1—p не зависит от того, какой символ передается, а также от того, как приняты остальные символы. Вероятность того, что вместо переданного

символа bi- будет принят символ	€	( j i)	равна р/(т—1). От-
	b j

сюда легко вывести, что вероятность получения на выходе «ка-

€	, если на вход подана комбинация bi
нала комбинации bj
	€	| bi ) [ p /(m 1)]	d (i; j )	(1	p)	n d (i; j )	.	(1.41)
P(bj

Это следует непосредственно из теоремы умножения вероятностей независимых событий и из того, что для перехода bi

в

€
b	j

необходимо, чтобы на определенных d(i; j) разрядах про-

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

Таким образом, в симметричном канале без памяти P(bj|bi) зависит только от кодового расстояния между bi и bj. В случаях, когда р<(т— 1)/т, что практически всегда выполняется, выражение (5.3) монотонно убывает с увеличением d(i; j).

Следовательно, вероятность принять комбинацию

€
b	j

тем боль-

ше, чем меньше ее кодовое расстояние от переданной комбина-

ции bi.

Задачей декодера является принятие решения о том, какая кодовая комбинация передавалась, если принята комбинация

€ . Разумеется, решение, принимаемое декодером, не всегда bj

верное. Однако можно добиваться минимума вероятности ошибочного декодирования. Пусть Р (bi | bj) — условная вероятность того, что передавалась комбинация bi, если принята комбинация

50

€ bj . Эту условную вероятность называют апостериорной веро-

ятностью в отличие от безусловной априорной вероятности Р (bi) того, что передается bi, когда ничего еще не известно о принятой комбинации. Предположим, что декодер по принятой

€ комбинации bj решил, что передавалась комбинация bk. Веро-

€ ятность того, что это решение верно, очевидно, равна P(bk| bj ).

Чтобы эта вероятность была максимально возможной, декодер должен из всех разрешенных комбинаций bi(i=1, ..., М) выбрать ту, для которой апостериорная вероятность максимальна. Это правило декодирования по максимуму апостериорной вероятности можно записать сокращенно так:

max P(bi	| b j ) .
i

Из теории вероятностей известно, что

					P(b	j	| b	)
P(b		| b		) P(b )			i
	i		j
				i	b
							j

,

(1.42)

(формула Байеса).

Если, как часто бывает на практике, все разрешенные кодовые комбинации равновероятны (P(bi ) const 1/M), то мак-

симум апостериорной вероятности совпадает с максимум услов-

нойвероятности P(b j | bi ) , которую называют функцией правдо-

подобия. Правило декодирования по максимуму правдоподобия можно сокращенно записать так:

	max P(b	j
	i

|

b	)
i

,

(1.43)

51

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

	€	, которые
множество Вi - следует включить все те комбинации bj
€	, чем в любой другой разрешен-
ближе (в смысле Хэмминга) к bi

ной комбинации.

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

Исправляющая способность кода при этом правиле декодирования определяется следующей теоремой.

Если код имеет d>2 и используется декодирование с исправлением ошибок по наименьшему расстоянию, то все ошибки кратностью g<d/2 исправляются. Что же касается ошибок большей кратности, то одни из них исправляются, а другие нет.

Для доказательства покажем, что в условиях теоремы (при q<.d/2) действительно переданная комбинация bi ближе (в смысле Хэмминга) к принятой комбинации bj, нежели любая другая разрешенная комбинация. Предположим противное, т. е. что существует разрешенная комбинация bk, для которой d(k; j)<d(i;j). На основании отсюда следует, что d(k;i)≤d(k;j)+d(i;j)<2d(i;j). Но по условию теоремы d(i;j)=q<d/2.

Отсюда d(k;i)<d, что противоречит определению d. Это противоречие и свидетельствует о справедливости теоремы.

Полученные результаты можно выразить следующими формулами:

q0 d,

qи d / 2,

(1.44)

52

где q0 — кратность гарантированно обнаруживаемых ошибок в режиме, когда ошибки только обнаруживаются; qи — кратность гарантированно исправляемых ошибок.

1.4.4Линейные двоичные блочные коды

Линейными называются такие двоичные коды, в которых множество всех разрешенных блоков является линейным пространством относительно операции поразрядного сложения по модулю 2. Очевидно, что оно является подпространством линейного пространства, образуемого множеством всех (а не только разрешенных) двоичных последовательностей длины п. Чтобы разрешенные блоки были линейным пространством, они должны содержать нулевой элемент, т. е. блок, состоящий из п нулей, должен быть разрешенным, а сумма (поразрядная по модулю 2) любых разрешенных блоков должна быть также разрешенным блоком. Линейные коды называют также групповыми. Двоичный линейный ,код можно построить следующим образом. Среди всех 2n последовательностей кодовых символов можно выбрать различными способами п линейно-независимых. В частности, ими могут быть (но не обязательно) элементы, образующие ортогональный базис. Выберем из них k любых ли- нейно-независимых блоков, которые обозначим

	,	,...,	(k n),
1	2	k

и образуем все линейные комбинации вида

	k
bi	ail l ,	(1.45)
	l 1

где аil принимает значения 0 или 1, а суммирование — поразрядное по модулю 2. Легко видеть, что множество {bj} этих комбинаций образует линейное пространство, содержащее 2k блоков, т. е. линейный код.

Действительно, множество {bi} содержит нулевой элемент, получающийся, когда все аil = 0 (l=1, ..., k). Сумма любых

53

двух элементов

			k
b b	j			(a	a	jl	)	l
i				il
			l 1

представляет собой также

элемент этого множества, поскольку аil + аjl принимает значение 0 или 1. Число элементов множества {bi} определяется количеством различных наборов из k двоичных коэффициентов аij, которое, очевидно, равно 2k. Если записать k линейно-независимых блоков, используемых для построения линейного кода, в виде k строк, то получится матрица размером n , которую называют порождающей или производящей матрицей кода G.

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

	b		b	b	...
		1,1	1,2	1,3
		b	b	b	...
		2,1	2,2	2,3
	... ... ... ...
		b	b	b	...
		k ,1	k ,2	k ,3

b1,n

b2,n ...

bk ,n

    

.

(1.46)

Здесь bij — двоичный символ (0 или 1), находящийся на j- м разряде i-гo кодового слова (входящего в выбранный базис).

Полученный таким образом код, содержащий 2k блоков длиной я, обозначают (n, k). При заданных п и k существует много различных (п, k) -кодов с различными кодовыми расстояниями d, определяемых различными порождающими матрицами. Все они имеют избыточность R 1 / n или относитель-

ную скорость Vk = k/n.

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

54

Чаще всего применяют систематические линейные коды, которые строят следующим образом. Сначала строится простой код длиной k, т. е. множество всех k-последовательностей двоичных символов, называемых информационными. Затем к каждой из этих последовательностей приписывается r=n—k проверочных символов, которые получаются в результате некоторых линейных операций над информационными символами. Можно показать, что для каждого линейного кода существует эквивалентный ему систематический код.

Простейший систематический код (п, п—1) строится добавлением к комбинации из п-1 информационных символов одного проверочного, равного сумме всех информационных символов по модулю 2. Легко видеть, что эта сумма равна нулю, если среди информационных символов содержится четное число единиц, и равна единице, если число единиц среди информационных символов нечетное. После добавления проверочного символа образуются кодовые комбинации, содержащие только четное количество единиц, т. е. комбинации с четным весом.

Такой код (n, п-1) имеет d=2, поскольку две различные кодовые комбинации, содержащие по четному числу единиц, не могут различаться в одном разряде. Следовательно, он позволяет обнаружить одиночные ошибки. Легко убедиться, что, применяя этот код в схеме декодирования с обнаружением ошибок, можно обнаруживать все ошибки нечетной кратности. Для этого достаточно подсчитать число единиц в принятой комбинации и проверить, является ли оно четным. Если при передаче комбинации произойдут ошибки в нечетном числе разрядов q, то принятая комбинация будет иметь нечетный вес и, следовательно, окажется запрещенной. Такой код называют кодом с одной проверкой на четность.

Обозначим через bi символ кода (0 или 1), стоящий на i-M месте в кодовой комбинации. Тогда для систематического (п, k)- кода общего вида получаем следующее правило построения комбинаций (b1, ..., bk ,bk+1,, ..., bn): символы b1, ..., bk выбирают в

55

соответствии с передаваемой информацией, а bi - при i>k определяют так, чтобы удовлетворялись условия

n
		ij	b 0
			i
i 1

j

i 1,..., n k 1, k 2,..., n

,

(1.47)

где γij коэффициенты (0 или 1), характеризующие данный код. Если набор все коэффициентов γij собрать в таблицу (матрицу), и получим так называемую проверочную матрицу кода H раз-

мерности	n (n k)	:

					...
			1,k 1				n,k 1
	H ...				...			...
					...
				1,n				n,n

(1.48)

Единицы в каждой j-той строке матрицы H показывают, какие информационные символы нужно сложить по модулю 2, чтобы получить нуль.

Из (1.46) можно придти к выводу, что произведение порождающей и транспонированной проверочной матриц

GH' 0.	(1.49)

Для рассмотренного примера кода (п, n—1) с четным весом проверочная матрица вырождается в вектор-строку длиной

п:

H (1,1,1,...,1),

а порождающая матрица имеет вид

56

	1,		0,	0,	0,	...,
		0,	1,	0,	0,	...,
	G	0,	0,	1,	0,	...,
		... ... ... ... ...
		0,	0,	0,	0,	...,

...1

.

(1.50)

Рассмотрим другой пример систематического кода — код, заданный порождающей матрицей

	1,		0,	0,	0,	1,	1,
		0,	1,	0,	0,	0,	1,
	G
		0,	0,	1,	0,	1,	1,
		0,	0,	0,	1,	1,	0,

или проверочной матрицей

1,		0,	1,	1,	1,	0,
	1,	1,	1,	0,	0,	1,
H
	0,	1,	1,	1,	0,	0,

	0
	1
			,
	1
	1

0.

(1.51)

(1.52)

Этот код имеет d=3 и позволяет обнаруживать все одиночные и двойные ошибки или исправлять (по алгоритму Хэмминга) все одиночные ошибки.

Заметим, что строки проверочной матрицы являются линейно независимыми векторами. Следовательно, проверочная матрица может служить порождающей для другого линейного кода (п, n—k), называемого двойственным. Так, например, матрица (1.51) является порождающей матрицей кода, имеющего d=4. Матрица (1.50) является проверочной для этого кода.

Преимуществом линейных, в частности систематических, кодов является то, что в кодере и декодере не нужно хранить

57

список из 2k блоков, а при декодировании не нужно вычислять 2k расстояний. Вместо этого достаточно хранить, например, n—k строк проверочной матрицы и при декодировании проверять выполнение n—k равенств. Так, например, при коде (100, 50) нужно хранить 50 строк по 100 символов, т. е. всего 5000 символов, а не 1017, как при табличном кодировании, и проверять 50 равенств, вместо перебора 1015 расстояний.

Обнаруживать и исправлять ошибки при систематическом коде можно следующим образом. В режиме обнаружения ошибок проверяют выполнение равенств (1.45) и если хотя бы одно из них не выполнено, принятый блок бракуют как ошибочный. В режиме исправления ошибок после проверки равенства (5.19) строится последовательность с= (с1, с2, ..., cn-k), называемая синдромом, где Cj(j=l, ..., п—k) —двоичный символ, равный нулю, если j-е равенство в (1.45) выполнено, и единице, если оно не выполнено. Нулевой синдром указывает на то, что все проверки выполнены, т. е. принятый блок является разрешенным. Всякому ненулевому синдрому соответствует определенная конфигурация ошибок, которая и исправляется. Так, например, для рассмотренного кода в табл. 1.1 представлены ненулевые синдромы и соответствующие конфигурации ошибок.

				Таблица 1.1
Синдром	001	010	011	100
Конфигурация	0000001	0000010	0100000	0000100
ошибок
Синдром	101	110	111
Конфигурация	0001000	1000000	0010000
ошибок

58

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

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

Как неоднократно отмечалось, для получения высокой верности связи следует применять коды с достаточно большой длиной. Однако с ростом п, если отношение k/n (скорость кода) фиксировано, растет и разность п—k, а следовательно, и объем таблицы исправлений, равный 2n-k. Так, для кода он равен 218 = 262 144.

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

Если (п, k) -код используется для обнаружения ошибок, то в теории кодирования доказывается, что при любой вероятности ошибочного приема символа р≤1/2 найдется код, для которого

p		1/ 2	n k	.
	н.о.

(1.53)

Более того, при любых п и k существует код, который в любом двоичном симметричном канале без памяти обеспечивает выполнение неравенства (5.25), какова бы ни была вероятность ошибки n 1/ 2. Такие коды называются равномерно обнаруживающими ошибки.

59