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

которые трансформировали передаваемое сообщение в другое разрешенное сообщение. Тогда частное Qi ≠ Gi и вместо сообщения Gi будет исполняться ложное сообщение. Этот процесс называют режимом ложного декодирования.

Если вес вычисленного в декодере остатка Ri будет больше нуля, т.е. WRi>0, то декодер принимает решение о том, что принятое сообщение Vi является запрещенным, в нем обнаружены ошибки, оно бракуется и не исполняется.

Декодирующее устройство ДКУ (декодер) с обнаружением ошибок, реализующее алгоритм декодирования (8) (или (9)), представлено на рис. 2.

Оно включает схему деления полиномов Vi(X) на Р(Х) и схему обнаружения ошибок. Схема деления полиномов состоит из регистра сдвига и сумматоров по mod2, вторые входы и входы которых включаются между D-триггерами регистра. Число D-триггеров в регистре сдвига равно степени k выбранного полинома Р(Х), а их нумерация производится слева направо от 1 до k. Электрические связи на первые входы сумматоров по mod2 в цепях обратных связей устанавливаются в соответствии со структурой (видом) полинома Р(Х). Если в составе полинома Р(Х) отсутствует переменная Х в некоторой степени i, т.е. Хi=0 (i ≠ n и i ≠ 0), то связь на соответствующий сумматор не проводится и он исключается из схемы. При этом прямой выход предыдущего триггера соединяется напрямую с входом D следующего триггера.

На вход схемы деления от демодулятора DM поразрядно подается декодируемое i-е сообщение Vi, которое будет делиться на полином Р. Через n тактов работы на ее выходе формируется m-разрядное частное Qi, а k-разрядный остаток Ri от деления Vi на Р зафиксируется в D-триггерах регистра сдвига их состояниями.

Схема обнаружения ошибок состоит из логических элементов ИЛИ и И. Элемент ИЛИ определяет вес вычисленного остатка Ri по принципу вес WRi = 0 или WRi > 0. Элемент И предназначен для съема значения сигнала ошибки с входа элемента ИЛИ на последнем n-м такте работы ДКУ, когда все n разрядов декодируемого сообщения Vi поступили на его вход. Если вес остатка Ri окажется

больше нуля, то на выходе элемента И появится единичный сигнал ошибки, который поступит на вход R приемного регистра и установит его в нулевое состояние. При этом принятое сообщение будет забраковано. Если вес остатка Ri будет равен нулю, то сигнал ошибки будет отсутствовать, и сброс в нулевое состояние приемного регистра не произойдет. Принятое сообщение будет дешифровано на (n+1)-м такте.

Исходными данными при синтезе кода любого типа являются: - число передаваемых сообщений N;

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

Задачами синтеза кода являются:

-получение заданного числа N кодовых комбинаций кода с минимальным числом избыточных разрядов К и с заданным кодовым расстоянием d;

-техническая реализация полученного кода, то есть построение структурных или функциональных электрических схем кодера (КУ) и декодера (ДКУ).

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

1. Определение числа информационных (неизбыточных) разрядов m в комбинациях кода, обеспечивающих передачу требуемого числа сообщений N, из соотношения:

	N 2m	(22)
или	m log2	N .

2. Определение минимального числа избыточных (контрольных) разрядов К, обеспечивающих требуемые корректирующие свойства, с использованием

следующих выражений [1÷4]
- для кода с d=2: К=1;	(23)
- для кода с d=3: 2к≥m+k+1;	(24)
- для кода с d=4: 2k-1≥m+k;	(25)
- для кода с d≥5 минимальное значение К [3,4] лежит между нижней оцен-
кой (границей Хемминга)
d 1
2	(26)
2K Cmi K

i0

иверхней оценкой числа К (границей Варшамова-Гилберта)

d 2
2K Cmi K 1 .	(27)

i 0

Нижняя граница (26) определяет то, что не существует кода с заданным значением d≥5 и имеющего число контрольных разрядов К меньшее, чем определяемое по формуле (26). Верхняя граница (27) определяет гарантированную возможность построения кода с d≥5 и числом избыточных разрядов К, определяемым по формуле (27).

3. Определение общего числа разрядов n в комбинациях кода

n = m + k.

(28)

4.Выбор порождающего полинома Р(Х) по методике, изложенной в п. 2.1.

5.Составление N неизбыточных m-разрядных комбинаций, соответствующих информационным полиномам Gi(X).

6.Получение всех комбинаций избыточного циклического кода по фор-

муле (5).

7.Построение функциональной электрической схемы кодера (КУ), реализующей умножение полиномов в соответствии с выражением (4) (см. рис. 1).

8.Построение функциональной электрической схемы декодера (ДКУ) с обнаружением ошибок, реализующей деление принимаемых сообщений на полином Р(Х), вычисление остатков Ri(X) и определение их весов (см. рис. 2).

2.3.3Циклические коды, получаемые способом вычисления

идобавления разрядов остатков Ri(X) к произведению Gi(X)*Xk и их синтез

Формула, определяющая правила кодирования, имеет вид:

V (X) G		(X) X K R (X);		(10)
i	i		i
или в двоичных числах:				(11)
Vi	Gi 10...0		Ri ;

где i=1,2,…,N.

Код, получаемый по алгоритмам (10) или (11), является систематическим разделимым, в котором m старших разрядов занимают информационные символы, а k = n - m младших разрядов занимают контрольные символы.

Для получения такого разделимого кода применяется следующая процедура кодирования:

1)каждый информационный полином Gi(X) умножается на одночлен Xk, что эквивалентно дописыванию справа к комбинациям Gi неизбыточного кода k нулей;

2)полученное произведение Gi(X)*Xk делится на порождающий многочлен Р(Х). Результат такого деления можно представить в следующем виде:

Gi (X) X K	Qi	(X)	Ri (X)	,	(12)
P(X)
			P(X)

где Qi(X) – полином частного степени, не старше m-1; Ri(X) – полином остатка степени, не старше k.

Вычисленный i-й остаток Ri(X) используется для образования i-й комбинации циклического кода Vi(X) в соответствии с формулой (10).

Докажем, что код, полученный по алгоритму (10) является циклическим. Для этого умножим обе части уравнения (12) на Р(Х) и перенесем остаток Ri(X) влево без изменения его знака (так как операции сложения и вычитания по mod2 идентичны), тогда получим:

G	(X) X K R (X) Q		(X) P(X).	(13)
i	i	i

Подмножества информационных полиномов {Gi(X)}={G1(X), G2(X), …, GN(X)} и полиномов частных {Qi(X)}={Q1(X), Q2(X),…, QN(X)} совпадают, так

как каждое из них порождает одно и то же подмножество m-разрядных двоичных чисел, то есть:

{Gi(X)}= {Qi(X)}.

Следовательно, правая часть уравнения (13) может быть заменена выражением Gi(X)*P(X)=Vi(X), а оно определяет первый способ получения кодовых комбинаций циклического кода. На основании этого можно заключить, что обе части уравнения (13) делятся нацело на полином Р(Х), поэтому формула (10) порождает циклический код, кодовые комбинации которого будут обладать и свойствами циклического сдвига.

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

Эти матрицы имеют m строк и n столбцов. В строках матриц записываются кодовые полиномы Vi(X) (кодовые комбинации Vi) кода, получаемые по формулам кодирования (10) или (11), соответственно, а их десятичные номера i=1,2,4,…,2m-1 равны целым степеням двойки.

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

Например, V3= V1+V2 , V5= V1+ V4 и т.д.

Функциональная электрическая схема кодирующего устройства (рис. 3), реализующая алгоритм кодирования (10) или (11), состоит из схемы деления входного i-го полинома Gi(X)*Xk на порождающий полином Р(Х) и элементов коммутации (ключей) S1 и S2.

Схема деления состоит из регистра сдвига на D-триггерах и сумматоров по mod2, включаемых между триггерами так, как показано на рис. 3. Число D- триггеров равно степени k порождающего полинома, а их нумерация выполняется слева направо. Электрические связи на первые входы сумматоров по mod2 проводятся в соответствии со структурой выбранного порождающего полинома Р(Х). Если в составе полинома Р(Х) отсутствует переменная Хi ( i ≠ k и i ≠ 0), то связь на соответствующий сумматор не проводится и он исключается из схемы.

Схема деления состоит из регистра сдвига на D-триггерах и сумматоров по mod2, включаемых между триггерами так, как показано на рис. 3. Число D- триггеров равно степени k порождающего полинома, а их нумерация выполняется слева направо. Электрические связи на первые входы сумматоров по mod2 проводятся в соответствии со структурой выбранного порождающего полинома Р(Х). Если в составе полинома Р(Х) отсутствует переменная Хi ( i ≠ k и i ≠ 0), то связь на соответствующий сумматор не проводится и он исключается из схемы.

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

Работа схемы. В течение первых m тактов ключ S1 замкнут, а ключ S2 устанавливается в нижнее положение. Поэтому за m тактов работы m-разрядное неизбыточное сообщение Gi поступит на выход схемы КУ и на схему деления.

В результате деления сообщения Gi на полином Р сформируется k- разрядный остаток Ri, который зафиксируется в D-триггерах схемы деления их состояниями. Затем ключ S1 размыкается, а ключ S2 устанавливается в верхнее положение. В этих положениях ключи будут находиться в течение последних k тактов работы КУ. Размыкание ключа S1 приведет к разрыву цепи обратной связи, и схема деления будет работать как обычный регистр сдвига.

В результате этого вычисленные символы остатка Ri будут поразрядно выдаваться из регистра на выход схемы в течении k тактов (вслед за информационной частью Gi).

Следует отметить, что вместо контактных ключей S1 и S2 целесообразно использовать бесконтактные ключи, выполненные на трех элементах И, что будет показано ниже.

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

Функциональная электрическая схема ДКУ с обнаружением ошибок для данного типа циклического кода (рис. 4) включает следующие функциональные узлы:

-схему деления принимаемого сообщения Vi(X) на полином Р(Х), состоящий из регистра сдвига на D-триггерах и сумматоров по mod2;

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

И;

-приемный m-разрядный регистр сдвига RG.

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

Принципы построения и работы схем деления полиномов Vi(Х) на Р(Х) и обнаружения ошибок были рассмотрены в п. 2.2. Основное отличие рассматриваемой схемы ДКУ рис. 4 от схемы ДКУ, представленной на рис. 2, состоит в том, что частное Qi(X) в данной схеме не используется. Это связано с тем, что в разделимом циклическом коде даже при отсутствии ошибок частное Qi(X) не будет совпадать с принимаемой информационной частью Gi(X), которая записывается в приемный регистр за первые m тактов работы ДКУ. В случае выявления схемой обнаружения ошибок на n-м такте нулевого синдрома принятое и записанное в регистре сообщение будет дешифровано дешифратором на (n+1)- м такте. В случае выявления на n-м такте синдрома с весом, большим нуля, содержимое регистра будет обнуляться сигналом ошибки, поступающим с выхода элемента И. Дешифратор сообщений при этом будет дешифровать на (n+1)-м такте нулевое сообщение, т.е. принятое сообщение будет забраковано.

На рис. 5 изображена функциональная электрическая схема ДКУ с исправлением однократных ошибок.

В этой схеме ДКУ вместо схемы обнаружения ошибок включен дешифратор синдромов (остатков) Ri(X). Исправление того или иного двоичного символа на противоположное значение в принятом сообщении выполняется соответствующим сумматором по mod2, подключенном к выходу регистра. Для однозначного определения десятичных номеров выходов дешифратора синдромов и номеров сумматоров по mod2, к которым должны подключаться эти выходы

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

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

Этапы синтеза кода, получаемого способом вычисления и добавления остатков

1.Определение параметров кода m, K, n (как и в п. 2.5.1).

2.Выбор порождающего полинома Р(Х).

3.Составление N неизбыточных m-разрядных комбинаций, соответствующих информационным полиномам Gi(X).

4.Умножение полиномов Gi(X) на переменную ХК.

5.Вычисление остатков Ri(X) от деления произведений Gi(X)*ХК на Р(Х).

6.Получение кодовых комбинаций циклического кода по алгоритму (11).

7.Построение функциональной электрической схемы кодера, реализующей вычисление и добавление остатков Ri(X) к информационной части (рис. 3).

8.Построение функциональной электрической схемы декодера с обнаружением (рис.4) или с обнаружением и исправлением ошибок (рис.5).

Примеры синтеза циклических кодов приведены в [6].

2.4 Методика синтеза корреляционного кода [9]

При кодировании этим кодом каждый информационный символ сообщения обыкновенного кода передается двумя символами: символ 1 преобразуется в пару символов 10, а 0 - в 01. Пары символов 10 и 01 являются разрешенными, а две другие пары символов 00 и 11 – запрещенными, которые образуются при

искажениях одного из двух символов в разрешенных парах. Десятинные эквиваленты разрешенных пар символов равны, соответственно, числам 2 и 1, а запрещенных пар – числам 0 и 3.

Функционально электрическая схема кодирующего устройства представлена на рисунке 1 (для примера показано кодирование четырехразрядных неиз-

быточных сообщений, т.е. m=4, k=m=4, n=2m=8).

Тактовые импульсы (ТИ) с соответствующими номерами (нечетными и четными) поступают на логические элементы И схемы КУ от распределителя передатчика.

При декодировании избыточных сообщений осуществляется обработка принимаемых пар символов в декодирующем устройстве (рис.2) приемника по следующему алгоритму: разрешенные пары символов 10 и 01 преобразуются в исходные двоичные символы 1 и 0, соответственно, а запрещенные пары символов 00 и 11 – в сигнал ошибки, по которому приемный регистр сообщений RG2 устанавливается в нулевое состояние и принятое сообщение не исполняется (бракуется).

В схеме рис.2 регистр RG1 и дешифратор DC1 служат для приема и дешифрации принимаемых пар символов избыточных сообщений, а регистр RG2 и дешифратор DC2 – для приема и дешифрации принимаемых неизбыточных сообщений.

От шифратора

Имея минимальное кодовое расстояние dmin=2, корреляционный код позволяет обнаруживать не только все ошибки нечетных кратностей, но и большую часть ошибок четных кратностей таких, которые искажают по одному символу в четном числе разрешенных пар символов. Не будут обнаруживаться только такие ошибки четных кратностей, которые будут одновременно искажать

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

Вход

RG

20

DC

RG

20

DC

0

к ЭИ

D0

Q1

0

D0

Q1

1

Q2

21

1

Вых. “0”

1

&

Q2

21

2

Вых. “1”

2

Q3

22

ТИ 1-8

3

Q4

23

C

1

C

R

E

R

E

15

Сброс

Сигнал на разрешение

Уст. в “0”

дешифрации на (n+1) такте

1

&

ТИ 2,4,6,8

Сигнал

S

T

ошибки

1 R

Сброс

Р И С . 2 .4 . 2 . С Х Е М А Д Е К О Д И Р У Ю Щ Е Г О У С Т Р О Й С Т В А К О Р Р Е Л Я Ц И О Н Н О Г О К О Д А

2.5 Методика синтеза кодов с контролем на четность и на нечетность

[1,2,3]

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

2.5.1 Код с контролем на четность

В таком коде число избыточных разрядов k=1. Кодирование сообщений основано на следующем: если в информационных m разрядах содержится четное число единиц, то в избыточном разряде данного сообщения ставится символ 0, а если содержится нечетное число единиц, то ставится символ 1. В результате этого все избыточные сообщения будут содержать чётное число единиц. Запрещенными будут все n разрядные сообщения, содержащие нечетное число единиц. Декодирование этого кода состоит в определении числа единиц в принимаемом сообщении по принципу:

–если число единиц четное, то принято разрешенное сообщение;

–если число единиц не четное, принято запрещенное сообщение и оно бракуе6тся.

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

2.5.2 Код с контролем на нечетность

В таком коде также вводится один контрольный разряд . Кодирование производится так: если в информационных m разрядах содержится четное число единиц, то в избыточном разряде ставится 1, а если нечетное число единиц, то ставится 0.

Декодирование основано на определении нечетного или четного числа единиц в избыточных сообщениях. Если число единиц нечетное, то принято разрешенное сообщение и оно исполняется , а если четное число единиц, то принято запрещённое сообщение и оно бракуется.

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

2.5.3 Код с постоянным весом ( равновесный код )

В данном коде все избыточные сообщения содержат одинаковое число l единиц в n-разрядах. Такие коды формируются по закону числа сочетаний:

l		n!
Сn			.
		l!(n l)!

Кодирование основано на подборе таких минимальных значений парамет-

ров

k, n=m+k, l чтобы выполнялось следующее неравенство:

Сl	≥N,	(1)
n

где N-число передаваемых сообщений.

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

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

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