Методические указан. к КТР по ТОАТ Соколов

- корректирующей способности кода по обнаружению и исправлению ошибок различных кратностей

Решение:

1. Определяем необходимое число информационных разрядов m в кодовых комбинациях из неравенства:

2m N 1 ;

2m 7 1,

отсюда получаем m=3 разряда.

2. Определяем число контрольных (избыточных) разрядов k из неравен-

ства:

2k m k 1;

2k 3 k 1,

тогда получаем k=3 разряда.

3 Определяем общее число разрядов n в кодовых комбинациях: n=m+k;

n=3+3=6 разрядов.

4 Строим проверочную матрицу H:

5 По матрице H записываем систему линейных уравнений, используемых для кодирования сообщений:

k		m	m	,
	1	1	2		(7)
k2		m1	m3,
k3		m2
			m3.

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

m m		k	0,
1	2	1	0,		(8)
m1	m3	k2

m2 m3 k3 0.

Уравнения системы (7) позволяют определить значения контрольных символов по известным значениям информационных символов в каждом кодируемом сообщении.

6 Получаем кодовые комбинации, используя для этого систему уравнений (7). Результаты кодирования заносим в таблицу 1.

По минимальному весу полученных кодовых комбинаций определяем, что минимальное кодовое расстояние синтезированного кода равно d=3.

Избыточные сообщения кода							Таблица 1
	Десят.	информационные символы			контрольные символы
	номера	m1	m2	m3	k1	K2		k3
	сообще-	22	21	20
	ний
	1	0	0	1	0	1		1
	2	0	1	0	1	0		1
	3	0	1	1	1	1		0
	4	1	0	0	1	1		0
	5	1	0	1	1	0		1
	6	1	1	0	0	1		1
	7	1	1	1	0	0		0

7 Строим функциональную электрическую схему кодера (рис.1), используя линейные уравнения (7).

Кодирующее устройство состоит из трёх сумматоров по модулю два (по числу контрольных символов k=3). В каждом из них вычисляется значение одного контрольного символа k1, k2, k3 путём суммирования соответствующих информационных символов m1, m2, m3 в соответствии с уравнениями (7).

Рис.1 Кодер кода Хэмминга

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

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

синдром

Рис. 2. Декодер кода Хэмминга с обнаружением ошибок

Схема декодера состоит из двух устройств:

-устройства вычисления синдромов, реализованного на трёх сумматорах по

M2;

- устройства обнаружения ошибок, включающего логические элементы ИЛИ и И.

Каждый из сумматоров по M2 реализует соответствующее линейное уравнение системы (8).

Обнаружение ошибок при приёме сообщения основано на вычислении синдрома (обнаружителя ошибок) в указанных сумматорах по M2 и определении его веса схемой обнаружения ошибок. При этом элемент ИЛИ определяет (на каждом такте работы) вес вычисляемого синдрома по принципу: вес синдрома равен нулю или его вес больше нуля. Элемент И служит для считывания, по сигналу «ОПРОС», значения веса вычисленного синдрома на последнем n=6 такте работы, когда приняты все символы сообщения.

Если вес вычисленного синдрома на n=6 такте равен нулю, то на выходах элементов ИЛИ и И будут нулевые сигналы, и обнуление приёмного регистра RG не произойдёт. При этом на n+1=7 такте в дешифраторе DC по сигналу разрешения на входе E произойдет дешифрация принятого сообщения. В результате сработает соответствующий исполнительный элемент ИЭ, который включит или выключит выбранный объект управления.

Изложенному событию может соответствовать один из двух вариантов декодирования и исполнения команды:

-в принятом разрешенном сообщении ошибок нет. При этом будет исполняться то сообщение, которое и передавалось;

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

Если же вес синдрома окажется больше нуля, то на выходе элемента И сформируется сигнал ошибки, который обнулит приёмный регистр RG. Дешифрация нулевого сообщения будет свидетельствовать о том, что принятое сообщение является запрещенным, оно забраковано и не исполняется.

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

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

При этом для каждого варианта искажений вычисляются синдромы по следующим правилам:

-синдромами для однократных ошибок в передаваемых сообщениях являются столбцы матрицы H.

-синдромами для ошибок кратностей 2, 3, …, n ,будут являться столбцы, получаемые поразрядным суммированием по М2 соответствующих столбцов матрицы H.

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

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

2.3Методика синтеза циклических кодов [7]

2.3.1Понятие о циклических кодах и порождающих многочленах (полиномах)

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

Эти коды являются подклассом групповых линейных кодов, но кодовые комбинации которых связаны двумя дополнительными условиями: условием цикличности (циклического сдвига) и делимостью нацело (без остатка) на неко-

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

Код называется циклическим, если циклический сдвиг любой разрешенной n – разрядной кодовой комбинации Vi последовательно на 1, 2,…, n-1 разрядов влево или вправо также образует разрешенные кодовые комбинации, входящие в состав кода.

Для построения кодовых комбинаций циклического кода любого типа ис-

пользуется порождающий полином Р(х) вида:
P(x) = Px X k + Px-1 X k-1 + … + P1 X + P0,	(1)

где Pi – двоичные коэффициенты (i=0÷k).

При этом коэффициенты Р0 и Рк всегда равны единице, а остальные коэффициенты Р1, Р2, … , Рк-1 могут принимать значения или 1, или 0.

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

Сформулируем сначала требования к полиному Р(х) при синтезе циклических кодов с d=3, позволяющих обнаруживать все однократные и двукратные ошибки и исправлять все однократные ошибки [1, 2, 3, 4].

1. Полином Р(х) должен быть делителем бинома (двучлена) Хn+1, т.е. он должен входить в разложение (этого бинома) на неприводимые многочлены. Причем, значение показателя степени n этого бинома связано с числом избыточных разрядов k в коде соотношением:

n=2k-1. (2)

Из формулы (2) видно, что показатель степени n бинома вида Xn+1, из разложения которого необходимо выбирать полином Р(х), может принимать только нечетные значения n = 1, 3, 7, 15, 31, 63, … (при значениях k = 1, 2, 3, 4, 5, 6 … ).

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

Приведем разложение биномов вида Хn+1 на неприводимые полиномы для некоторых степеней n , (n=1, 2, 3, …, 63).

X +1 – неприводимый (не разлагается);

Х2 +1 = (Х+1)·(Х+1); Х3 +1 = (Х+1)·(Х2+Х+1);

Х4+1=(Х2+1)·(Х2+1)= (Х+1)·(Х+1)·(Х+1)·(Х+1); Х5+1=(Х+1)·(Х4+Х3+Х2+Х+1); Х6+1=(Х3+1)·(Х3+1)= (Х+1)·(Х+1)· (Х2+Х+1)·(Х2+Х+1); Х7+1=(Х+1)·(Х3+Х+1)·(Х3+Х2+1);

Х8+1=(Х4+1)·(Х4+1)=(Х+1)·(Х+1)·(Х+1)·(Х+1)·(Х+1)·(Х+1)·(Х+1)·(Х+1); Х9+1=(Х+1)·(Х2+Х+1)·(Х6+Х3+1);

………………………………………………………………………………

Х15+1=(Х+1)·(Х2+Х+1)·(Х4+Х+1)·(Х4+Х3+1)·(Х4+Х3+Х2+Х+1);

………………………………………………………………………………

Х31+1=(Х+1)·(Х5+Х2+1)·(Х5+Х3+1)·(Х5+Х4+Х3+Х2+1)·(Х5+Х3+Х2+Х+1)· ·(Х5+Х4+Х2+Х+1)·(Х5+Х4+Х3+Х+1);

………………………………………………………………………………...

Х63+1=(Х+1)·(Х2+Х+1)·(Х3+Х2+1)·(Х3+Х+1)·(Х6+Х+1)·(Х6+Х5+1)·(Х6+

+Х5+Х2+Х+1)·(Х6+Х5+Х3+Х2+1)·(Х6+Х5+Х4+Х+1)·(Х6+Х4+Х3+Х+1)· ·(Х6+Х3+Х+1)·(Х6+Х4+Х2+Х+1)·(Х6+Х5+Х4+Х2+1).

Из приведенных разложений видно, что если степень n бинома Хn+1 равна n=2k-1, то такой бином разлагается на неприводимые (простые) полиномы степени k и на неприводимые полиномы меньших степеней ki , которые кратны k. Например, для бинома Х15+1 его степень n=15 может быть представлена как 15=24-1 (при k = 4). Следовательно, бином Х15+1 разлагается на простые полиномы степеней 4, 2, 1.

2. Полином Р(х) должен быть неприводимым и примитивным.

Примитивным (порождающим) для данного показателя степени n бинома Xn+1 называется такой неприводимый многочлен степени k, который удовлетворяет двум условиям:

1)его степень k связана со степенью n исходного бинома Xn+1 соотношением (2);

2)являясь делителем бинома Xn+1, он не должен входить в разложение ни одного бинома вида Xλ+1, степень которого λ меньше n ( λ < n ).

В приведенных выше разложениях биномов Xn+1 все примитивные поли-

номы для соответствующих нечетных значений показателей n подчеркнуты. Например, в разложении бинома X15+1 неприводимый полином четвертой степени Х4+Х3+Х2+Х+1 не является примитивным, поскольку для него выполняется первое условие, но не выполняется второе условие (он входит не только в разложе-

ние данного бинома 15-й степени, но и в разложение бинома пятой степени

Х5+1, меньшей 15).

Следует отметить, что только неприводимые примитивные полиномы дают максимальное число n различных остатков Ri(x), получаемых от деления на полином Р(х) двоичных n-разрядных кодовых комбинаций кода с искажениями в одном разряде. Это является необходимым условием для возможности исправления однократных ошибок в кодовых комбинациях кода с d=3, [1÷4].

В таблице 1 приведены все неприводимые примитивные многочлены и их двоичные эквиваленты до седьмой степени включительно.

В [3] дан перечень всех неприводимых многочленов до 34-й степени с указанием их примитивности или не примитивности.

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

Это объясняется тем, что полиному Р(х) степени k будет соответствовать двоичное число Р, имеющее k+1 разрядов. Но это же двоичное число представляет собой первую разрешенную кодовую комбинацию кода, порождаемую по-

линомом Р(х), т.е. V1=Р. Поэтому в k+1 разрядах этой комбинации один разряд должен быть информационным, а остальные k разрядов контрольными (избыточными).

4. Число ненулевых членов полинома Р(х) (т.е. его вес) должно быть не меньше минимального кодового расстояния d, т.е. Wp(x)≥d.

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

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

1.Для кодов с d=2 порождающий полином Р(х)d=2 = Х + 1. Этот двучлен входит в разложение биномов Хn+1 любой степени n. Порождаемый им циклический код является аналогом кода с проверкой на четность и позволяет обнаруживать все ошибки нечетных кратностей.

2.Для кодов с d=3 порождающий полином Р(х)d=3 должен:

-быть неприводимым и примитивным;

-иметь степень kd = 3, равную числу избыточных (контрольных) разрядов в коде с d=3;

-содержать три (d=3) или более членов;

-выбираться из таблицы 1 неприводимых примитивных многочленов (полиномов).

3. Для кодов с d=4 полином Р(х)d=4 выбирается в виде произведения бинома Х+1 и неприводимого примитивного полинома Р(х)d=3, который нами был бы выбран при синтезе кода с d=3, т.е.

P(x)d 4

(x 1) P(x)d 3 .

(3)

Из этого следует, что при синтезе кода с d=4 вначале по исходным данным определяется число контрольных разрядов Кd=3 для кода с d=3 и выбирается полином Р(Х)d=3, а затем по формуле (3) определяется полином Р(х)d=4. Полученный полином Р(х)d=4 должен иметь степень Кd=4, равную числу избыточных разрядов в коде с d=4, и содержать четыре (d=4) или более членов.

4. Для кодов, имеющих значение d≥5, полином Р(х)d=5 выбирается в виде произведения нескольких неприводимых примитивных полиномов по специальной методике, изложенной в [1, 2, 4]. Циклические коды с d≥5 называют кодами Боуза – Чоудхури – Хоквингема (кодами БЧХ) по именам авторов, разработавших эти коды.

В данном пособии исследуются циклические коды двух типов:

-получаемые способом умножения полиномов;

-получаемые способом вычисления и добавления полиномов (разрядов, символов) остатков.

Рассмотрим принципы кодирования, декодирования сообщений в кодах указанных типов, а также принципы построения и работы кодирующих (КУ) и декодирующих (ДКУ) устройств.

			Таблица 1
	Неприводимые примитивные многочлены
		и их двоичные эквиваленты
Неприводимые			Неприводимые
примитивные		Двоичные	примитивные	Двоичные
полиномы		эквивален-	полиномы	эквиваленты
		ты
1		2	1	2
X 1		11	X7+X3+1	10001001
X2+X+1		111	X7+X4+X	10010001
X3+X+1		1011	X7+X+1	10000011
X3+X2+1		1101	X7+X6+1	11000001
X4+X+1		10011	X7+X3+X2+X+1	10001111
X4+X3+1		11001	X7+X6+X5+X4+1	11110001
X5+X2+1		100101	X7+X4+X3+X2+1	10011101
X5+X3+1		101001	X7+X5+X4+X3+1	10111001
X5+X4+X3+X2+1		111101	X7+X6+X5+X4+X2+X+1	11110111
Х5+Х3+Х2+Х+1		101111	X7+X6+X5+X3+X2+X+1	11101111
Х5+Х4+Х2+Х+1		110111	X7+X5+X4+X3+X2+X+1	10111111
Х5+Х4+Х3+Х+1		111011	X7+X6+X5+X4+X3+X2+1	11111101
Х6+Х+1		1000011	X7+X6+X4+X2+1	11010101
Х6+Х5+1		1100001	X7+X5+X3+X+1	10101011
Х6+Х5+Х2+Х+1		1100111	X7+X6+X3+X+1	11001011
Х6+Х5+Х4+Х+1		1110011	X7+X6+X4+X+1	11010011
Х6+Х5+Х3+Х2+1		1101101	X7+X6+X5+X2+1	11100101
Х6+Х4+Х3+Х+1		1011011	X7+X5+X2+X+1	10100111

2.3.2 Циклические коды, получаемые способом умножения информационных полиномов Gi(x) на порождающий полином Р(х) и их синтез

Для циклических кодов данного типа способ кодирования записывается формулами в виде умножения полиномов:

Vi (x) Gi (x) P(x),	(4)
или в виде двоичных чисел:
Vi Gi P,	(5)
где Vi(x) – i-й полином избыточного кода;

Vi - i-я кодовая комбинация избыточного кода;

Gi(x) – i-й информационный полином неизбыточного кода;

Gi – i-я кодовая комбинация неизбыточного кода; i=1,2, …, N;

N – число передаваемых (кодируемых) сообщений, N=2m-1. Кодовые комбинации, получаемые по алгоритмам кодирования (4) или (5)

будут нацело делиться на полином Р(х) и удовлетворять условию циклического сдвига. Получаемый этим способом код является неразделимым, в кодовых комбинациях которого после кодирования невозможно установить номера разрядов, в которых размещаются информационные и контрольные символы. Это является недостатком данного способа кодирования, который проявляется в следующем. Если в полученном коде реализуется исправление ошибок, то принятая n- разрядная комбинация Vi должна дважды делиться на полином Р(х): первый раз для обнаружения и исправления в ней ошибок, а второй раз для выделения информационной части Gi из исправленной комбинации Vi. Это увеличивает время декодирования сообщений в 2 раза. Если же в коде реализуется только обнаружение ошибок, то деление проводится один раз. Поэтому циклические коды данного типа целесообразно использовать в системах телемеханики только с обнаружением ошибок.

Для более быстрого получения всех комбинаций Vi при синтезе кода можно использовать порождающую матрицу G(x) или матрицу G в двоичных кодах.

Число строк в этих матрицах равно m, а столбцов равно n. В первой строке матрицы G(x) записывается выбранный порождающий полином Р(х), а остальные m-1 строк представляют циклические сдвиги полинома Р(х) на 1, 2, …, m-1 разрядов влево. Строки матрицы G(x) являются кодовыми полиномами Vi(x) (кодовыми комбинациями Vi), десятичные номера i. которых равны целым степеням двойки (i=1,2,4,…,2m-1).

Для получения остальных кодовых комбинаций кода необходимо складывать поразрядно по mod2 соответствующие строки матрицы G. Например,

V3 V1 V2 , V5 V1 V4 и т.д.

Кодирующее устройство КУ (или кодер), реализующее умножение полиномов в соответствии с алгоритмами кодирования (4) или (5), состоит из регистра сдвига и сумматоров по mod2 (рис 1).

Рис.1. Функциональная электрическая схема КУ для кода, получаемого способом умножения полиномов

Число D-триггеров в регистре сдвига равно степени k порождающего полинома Р(х), нумерация триггеров выполняется справа налево от 1 до k.

Электрические связи с прямых выходов D-триггеров на вторые входы сумматоров по mod2 устанавливаются в соответствии с видом выбранного полинома Р(х). При этом переменной xi, входящей в состав полинома Р(х), будет соответствовать связь на соответствующий сумматор с выхода того триггера, номер которого будет равен i+1. Если в полиноме Р(х) отсутствует переменная Х в некоторой степени i, т.е. Х i = 0 (i ≠ n и I ≠ 0), то связь с прямого выхода триггера, имеющего номер i+1, на соответствующий сумматор не проводится, и этот сумматор исключается из схемы.

При подаче на вход КУ m-разрядной кодовой комбинации Gi неизбыточного кода на его выходе за n тактов работы (n=m+k) будет сформирована n-раз- рядная кодовая комбинация Vi избыточного кода.

Декодирование принимаемых сообщений Vi(X) в декодирующем устройстве ДКУ (декодере) основано на их делении на полином Р(Х) и последующем определении веса вычисленного остатка Ri(X). Эту процедуру деления полиномов можно записать так:

	Vi (X)		Qi		(X)			Ri (X)	;	(8)
	P(X)							P(X)
или в двоичных числах:
		Vi		Q		Ri	;			(9)
		P
					i	P

где Qi(X) – полином частного; i=1, 2, …, N.

Если при декодировании сообщения вес вычисленного остатка Ri будет равен нулю, т.е. WRi = 0, то декодер принимает решение о том, что принято разрешенное сообщение. Это решение будет соответствовать одному из двух случаев его приема:

1)в принятом сообщении Vi ошибок нет. Тогда вычисленное частное Qi будет равно передаваемому неизбыточному сообщению Gi, которое

ибудет исполняться;

2)в принятом сообщении Vi имеются необнаруживаемые ошибки,