конспект ТЭС кодирование сообщений нов

гарантированно исправляемых tисп ошибок определяется минимальным кодовым расстоянием d0:

tобн≤ d0-1 и tисп≤ d0 −21( 2 ) .

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

Правило декодирования с обнаружением ошибки однозначно определяется кодом. Декодер лишь определяет, относится принятая комбинация к разрешенным или не относится.

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

Существуют различные методы декодирования блочных помехоустойчивых кодов с исправлением ошибок. Рассмотрим три из них:

а) декодирование по максимуму правдоподобия; б) декодирование по синдрому; в) мажоритарное декодирование (по большинству).

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

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

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

Структурная схема декодера, реализующего декодирование по максимуму правдоподобия, приведена на рисунке 5. Генера-

51

тор кодовых слов генерирует все возможные кодовые комбинации А1, А2,…,АМ, каждая из которых поступает на соответствующий коррелятор. На другой вход каждого из корреляторов поступает принятая последовательность символов. В корреляторах принятая последовательность и кодовые слова от генератора перемножаются. Решающее устройство анализирует информацию от корреляторов и принимает решение, в каком из корреляторов выявлено максимальное сходство, и выдает на выход декодера соответствующее разрешенное кодовое слово (без проверочных символов).

А*	К1
Вход
		К2
			РУ	Выход
			Км
	А1	А2	Ам
	Генератор кодовых слов

Рисунок 5 − Электрическая структурная схема декодера по максимуму правдоподобия

К1, К2,…,Км – корреляторы; РУ – решающее устройство

Структурная схема декодера по минимуму расстояния аналогична схеме, приведенной на рисунке 5, но вместо корреляторов используют устройства сравнения УС1, УС2,…, УСм. Рассмотренные способы декодирования обеспечивают минимальную вероятность ошибки, но сложны в реализации и требуют больших вычислительных затрат. Декодирование по минимуму расстояния целесообразно использовать лишь в кодах с малым числом информационных символов (r>>k), а по максимуму правдоподобия − в кодах с малым числом символов n.

Декодирование по синдрому

52

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

При декодировании систематических линейных блочных кодов проверяют выполнение условия (14) G ×НТ=0. Если принята неразрешенная комбинация, это произведение будет отлично от нуля.

При декодировании циклических линейных кодов используется их свойство делиться без остатка на порождающий полином g(х), т.е. проверяется выполнение условия (24) h(x)·g(x)=0. Если принята неразрешенная комбинация, остаток от деления R(x) будет не равен нулю.

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

Декодирование систематических линейных блочных кодов Хэмминга синдромным способом

Для декодирования по синдрому принятую декодером последовательность символов А* умножают на транспонированную проверочную матрицу НТ (транспонирование необходимо для изменения ранга матрицы с [r×n ] на [n ×r ]). Если полученный в результате перемножения синдром S= А*∙ НТ равен нулю, декодер принимает решение о безошибочном приеме и выдает на выход k-разрядную последовательность информационных символов. На практике она может отличаться от поступившей на вход кодера. Это происходит в тех случаях, когда переданная разрешенная комбинация переходит в другую разрешенную. Ес-

53

ли синдром S= А*∙НТ не равен нулю, декодер обнаруживает наличие ошибки, по виду синдрома определяет соответствующий вектор ошибки Е и корректирует принятую последовательность символов.

Для кодов Хэмминга, исправляющих одну ошибку, векторы ошибки Еi представляют собой n-разрядные комбинации, содержащие по (n-1) нулевых символов и одному ненулевому (единичному). Этот единичный разряд и указывает номер неверно принятого символа в кодовой комбинации. Нулевому синдрому соответствует нулевой вектор ошибки. Для кодов Хэмминга синдромы единичных ошибок совпадают со строками транспо-

нированной проверочной матрицы HnT,r .

Рассмотрим метод синдромного декодирования подробнее. Транспонируем проверочную матрицу H 3,7 (5.8) путем преобразования каждой из ее строк в соответствующий столбец матри-

цы H7T,3 :
				011
	0111 100			101
H 3,7=				110	= Н7Т,3	(29)
	1011 010			111
	1101 001			100
				010
				001

Составим таблицу 5 соответствия синдромов и векторов ошибок, используя матрицу НТ7,3 (29). Первой строке матрицы

H7T,3 соответствует ошибка в первом разряде принятой комбинации, второй строке − ошибка во втором разряде и т.д.

Таблица 5 − Таблица соответствия синдромов и векторов ошибки кода Хэмминга (7;4)

	Синдром S			Вектор ошибки Е
	s1	s2	s3

54

0	1	1	1 0 0 0 0 0 0
1	0	1	0 1 0 0 0 0 0
1	1	0	0 0 1 0 0 0 0
1	1	1	0 0 0 1 0 0 0
1	0	0	0 0 0 0 1 0 0
0	1	0	0 0 0 0 0 1 0
0	0	1	0 0 0 0 0 0 1

Вначале рассчитаем синдром для разрешенной кодовой комбинации А=0101010, сформированной с использованием проверочной матрицы (15) в примере 8:

011

101
110
S = A × H T =		0101010		× 111	= S = s s		s	.
					1	2	3
100
010
001

Для расчета первого разряда синдрома s 1 поразрядно умножаем принятую комбинацию А на первый столбец матрицы

H7T,3 и полученные символы суммируем по модулю два:

0101010

×0111100

0 1 0 1 0 0 0 = 0 = s1

Аналогично рассчитываем разряды s2 и s3, умножая комбинацию А соответственно на второй и третий столбцы матрицы (29):

0101010 × 1011010 ;

0 0 0 1 0 1 0 =0 = s2

55

0101010 × 1101001 .

0 1 0 1 0 1 0 = 0 = s3

В итоге имеем S = s1s2s3=000. Нулевой синдром свидетельствует об отсутствии ошибки (вектор ошибки Е=0000000). Введем в комбинацию А одну ошибку, например, в четвертый раз-

ряд: А*=0100010. Рассчитаем синдром S * вышеуказанным способом:

	0100010
×	0111100			;
			= 1 = s1
		0 1 0 0 0 0 0
	0100010
×	1011010			;
			= 1 = s2
		0 0 0 0 0 1 0

0100010

×1101001

0 1 0 0 0 0 0 = 1 = s33

В итоге S *= s1 s2 s3 = 111.Получен ненулевой синдром, сви-

детельствующий о наличии ошибок в принятой комбинации. По таблице 5 определяем вектор ошибки, соответствующий синдрому 111: Е=0001000. Поскольку ошибочная комбинация А* представляет собой сумму верного слова А и ошибки

(А*=А Е ), то скорректированное слово

′	*	(30)
А	= A Е.

0100010

Проведем коррекцию А'=А* Е = 0001000 .

0101010 = А

56

Как видим, удалось исправить одну ошибку. На выход декодера выдается k-разрядная комбинация Аk' = 0101 = Ak .

Введем в комбинацию А две ошибки: А**=0110010. Рассчитаем синдром S**= s1 s2 s3 = A ×H7T,3 = 001. Синдрому 001 в

таблице 7.1 соответствует вектор ошибки 0000001. Используя

0110010

(7.2), корректируем ошибку: А''=A Е = 0000001 .

0110011≠ А

На выход декодера выдается ошибочная комбинация Аk′ =0110 ≠ Аk . Несмотря на то, что двукратная ошибка кодом

обнаружена, скорректировать ее не удалось, так как код с d0 =3 обеспечивает tисп=1. Для увеличения кратности tисп и tобн необходимо увеличивать d0, но при этом увеличится число разрядов n и

уменьшится скорость передачи кода R= kn .

Электрическая структурная схема синдромного декодера систематического линейного кода (7;4) приведена на рисунке 6.

7

			3		А*	А’k
	А*	7		4(7)	4(7)
			БВС
				C	БК
			S	E

Рисунок 6 −Электрическая структурная схема синдромного декодера кода (7;4).

БВС – блок вычисления синдрома; С – селектор; БК – блок коррекции

Декодер работает следующим образом. Принятая последовательность символов поступает на декодер в параллельном коде. В блоке вычисления синдрома определяется синдром ошибки S

57

и затем селектор находит соответствующий синдрому S вектор ошибки Е. В блоке коррекции сообщение корректируется путем суммирования принятой последовательности А* и вектора ошибки Е. Проверочные разряды обычно не корректируются. На выход декодера поступают откорректированные информацион-

ные символы Аk' . На рисунке 6 цифрами над соединительными

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

Декодирование циклических кодов синдромным способом

Для определения синдрома циклического кода достаточно поделить принятую комбинацию символов на порождающий полином g(х). Остаток от деления R(х) и есть синдром: S(x)=R(x). При S(x)=0 принято разрешенное слово, а при S(x)≠0 − обнаружено наличие ошибки. При S(x)≠0 по таблице соответствия синдромов и ошибочных символов находят неверный разряд е(х) и корректируют принятое слово. Имеются отличия в декодировании разделимых и неразделимых циклических кодов.

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

Для составления таблицы соответствия синдромов и ошибочных символов надо в любое разрешенное кодовое слово вводить поочередно по одной ошибке в определенные разряды и выполнять деление на полином g(х). Полученные остатки и будут синдромами для соответствующих символов. В таблице 6 приведены синдромы ошибок для двух циклических кодов (7;4) с порождающими полиномами g1(x) g2(x).

58

Таблица 6 − Таблица соответствия синдромов и ошибочных символов для двух циклических кодов (7;4) с порождающими полиномами g1(x) g2(x).

Ошибочный символ е(х)			х0	х1	х2	х3	х4	х5	х6
Синдром	S(x)	при	001	010	100	011	110	111	101
g1(x)=x3+x+1
Синдром	S(x)	при	001	010	100	101	111	011	110
g2(x)=x3+x2+1

Пример 18 Требуется найти и исправить ошибку в принятой комбинации символов разделимого циклического кода:

А*=0100100; g(x)=x3+x+1.

Решение. 1 Переведем А* в полином: а*(х)=х5+х2.

2 Разделим а*(х) на g(x) и найдем остаток от деления R(x):

х5 х+5 х+3 х+2 х2

х3х3 + х+1

х+1 = R(x)

х3 + х+1

х2 +1

Переведем R(х) в двоичный вид с учетом числа проверочных

символов: R(х)=S(х)=011.
3	По таблице 7.2 находим, что синдрому S(х)=011 соответ-
ствует ошибка в символе х3.
4	Корректируем	сообщение:

а'(x)=a*(х) е(х) = х5 + х2 + х3 = х5 + х3 + х2.

5 Переводим а'(х) в двоичный вид и отбрасываем проверочные символы: А'=0101100; Ak' = 0101.

Электрическая структурная схема синдромного декодера циклического разделимого кода (7;4) приведена на рисунке 7. Декодирование проводится за 2∙n тактов. В первые n тактов принятое в последовательном коде слово а*(х), начиная со старших разрядов, записывается в буфер и одновременно поступает в генератор синдрома, где через n шагов находится остаток от деле-

59

ния а*(х) на g(х). При R(х)=S(х)=0 ошибки нет или она не обнаружена (вектор ошибки е(х)=0). При R(х)=S(x)≠0 ошибка обнаружена. За вторые n тактов информация с буфера, исправляясь в сумматоре, поступает на выход. Задача селектора при этом − выдать исправляющий сигнал в тот момент, когда ошибочный символ покидает буферный регистр. Далее необходимо отбросить проверочные символы.

			S(x)			n-
		r-разрядный
		генератор			разрядный
		синдрома			селектор
			а*(х)				е(х)
а*(х)									a'(х)
		n-разрядный
		буферный
Вход					Выход
		регистр

Рисунок 7 − Электрическая структурная схема синдромного декодера разделимого циклического кода (7;4)

В декодере неразделимого циклического кода при обнаружении ошибки необходимо обеспечить повторное деление откорректированной n-разрядной последовательности на полином g(х).

Пример 19 Требуется найти и исправить ошибку в принятой комбинации символов неразделимого циклического кода (7;4):

А*=1100111; g(х)=х3+х+1.

Решение.

1 Переведем А* в полином а*(х)=х6+х5+х2+х+1.

2 Разделим а*(х) на g(х), найдем остаток от деления R(х) и переведем его в двоичный вид с учетом числа проверочных символов:

60