Файл: Емельянов Г.А. Передача дискретной информации и основы телеграфии учеб. для вузов.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 264

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

в первой проверке, позиция 2 — во второй, позиция 4 — в третьей и позиция 8 — в четвертой. Эти позиции и следует выбрать в каче­ стве проверочных. Обозначим каждую позицию буквами 0.1, аь аз и т. д. В табл. 11.2 позиции проверочных элементов об­

ведены.

 

 

 

Рассмотрим конкретный пример. Пусть комбинация

обыкновенного кода

10011 преобразуется

в девятизлементный код Хэмминга. Запишем эту комбина­

цию на позиции информационных элементов. Поверочные

разряды получим в

результате четырех проверок:

 

51 = а 3

® а5 ф а, ф д9 = 1 © 0 ф 1 © 1 = 1;

5 2

= а3

ф а„ ф а7 = 1 + 0 ф 1 = 0;

 

5 3

= а5 © ав Ф а, = 0 ф 0 ф 1 = 1;

 

Si

= а9

= 1.

 

Результаты

проверок поставим на позиции 1, 2, 4 и 8.

 

 

 

Пусть при приеме произошла ошибка в шестом разряде. Тогда будет при­

нята комбинация 101101111. На приеме производятся

четыре

проверки

на чет­

ность:

 

 

 

 

 

 

Si = % Ф ая ф аъ ф а7 ф ая = 1 ф 1 ф 0 ф 1 ф 1 = 0;

 

Sa = а2 ф а3 ф ав ф а, = 0 ф 1 Є 1 0 1 = 1;

 

 

 

5 3

= а4 ф аь ф а6 ® а, = 1 ф 0 ф 1 Ф 1 = 1;

 

 

 

5 4

= ай ф а9 = 1 ф 1 = 0 .

форма

записи числа

6 (см. табл.

Полученное

число ОНО — есть двоичная

і 1.1). Оно указывает на номер пораженного

ошибкой

разряда

в кодовой

комби­

нации. Для исправления ошибки необходимо

при приеме заменить

знак

шестого

разряда на противоположный.

 

 

 

с точки зре­

Описанная структура разрядов в кодовой комбинации неудобна

ния построения

кодирующего и декодирующего устройств. Удобнее сначала пе­

редавать информационные разряды, а потом — проверочные. Чтобы

при этом со­

хранить свойства кода Хэмминга, необходимо преобразовать

номера разрядов,

как это указано в табл. 11.3.

 

 

 

 

 

 

Т а б л и ц а Ы.З

 

 

 

 

Исходный код

'ПреоИразодан- ш/й код

После преобразования проверки охватят следующие разряды: первая про­ верка — 1, 2, 4, 5, 6-й (вместо 1, 3, 5, 7, 9-го); вторая проверка — 1, 3, 4, 7-й (вместо 2, 3, 6, 7-го), третья проверка — 2, 3, 4, 8-й (вместо 4, 5, 6, 7-го), чет­ вертая проверка — 5, 9-й (вместо 8, 9-го).

Структурная схема

кодирующего

устройства

приведена

на

рис. 11.5а. В состав

его входит регистр

сдвига на

я = 9 разрядов

и г = 4 сумматоров по

модулю 2. Информационные посылки запи­

сывают в первые k—5

ячеек регистра

сдвига. Одновременно в

сум­

маторах формируются

проверочные

разряды, записываемые в

по-

 

От источника

информации

а)

а р о

О Р

 

 

Рис. US. Структурная схе­ ма кодирующего (а) и де­ кодирующего (б) устройств для кода Хэмминга

,т

Регистр\3\8

\ 7\

8 \ S

| f

1 3

г

\ >

\ Вых.

4

г-ячевк

t 4.

 

к-ячеек

 

 

 

 

 

 

 

 

 

 

Ввод кодовой комбинации

 

 

V

V

V

г*

V

V

V

Ъ Ь

Устр-Во исправления ошибок

14

Выходная комбинация

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

Структурная схема

декодирующего устройства приведена на

рис. 11.56. Поступающая

из канала связи информация с помощью

входного и распределительного устройств (на рисунке не показа­ ны) преобразуется из последовательного кода в параллельный и подается в наборное устройство и сумматоры проверки на четность. В зависимости от позиции (номера) искаженного разряда (или при отсутствии искажений) выходные сигналы сумматоров могут со­ ставлять одну из десяти возможных комбинаций. Комбинация 0000 соответствует отсутствию искажений, еще пять комбинаций — ис­ кажениям информационных разрядов' и остальные четыре — иска­ жениям проверочных разрядов. Поскольку на выход декодирую­ щего устройства поступают только информационные разряды, то выделять необходимо только пять двоичных комбинаций, которые соответствуют номеру искаженного информационного разряда.

Искажению первого информационного разряда соответствует число ООП (вместо 0001 до преобразования кода), так как перво­ му разряду преобразованного кода ibi (см. табл. 11.3) соответствует третий разряд исходного кода а3. Число 3 в двоичной форме за­

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

вто­

рого разряда >Ь2 соответствует аь, или число 0101. Искажениям

3, 4

и 5-го разрядов соответствуют числа ОНО, 0111, 1001.

 

Указанные двоичные числа выделяются дешифратором ошибок, который выполнен на схемах запрета, реализующих операцию от­ рицания импликации (см. рис. 3.5). После окончания приема кодо­ вой комбинации происходит сброс информации с наборного устрой­ ства и дешифратора ошибок на устройство исправления ошибок. Это устройство состоит из сумматоров по модулю 2. На один вход каждого сумматора поступает соответствующий информационный разряд, на другой—сигнал с выхода дешифратора ошибки в данном разряде. Если ошибки нет, то сигнал с ячейки наборного устрой­ ства поступает на выход декодирующего устройства без изменений.

При наличии ошибки знак разряда наборного устройства

меняется

на противоположный. Этим обеспечивается исправление

ошибки

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

 

ЦИКЛИЧЕСКИЕ КОДЫ

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

При построении циклических кодов кодовые комбинации приня­ то представлять в виде полиномов

G(x) = ап^хп-1 + ап_2хп-2 + . • -сцх + а0, (11.6)

где Оо, аи ..., a,n-i — коэффициенты, принимающие значения 0 или 1. Например, комбинацию 1100101 можно записать как G(x)=x6 +

+ * 5 + л;2+1.

Основное свойство рассматриваемых кодов состоит в том, что циклический сдвиг разрешенной кодовой комбинации также являет­ ся разрешенной кодовой комбинацией. Таким образом, если ком­ бинация 1000111 является разрешенной, то комбинации 0001111, 0011110 и т. д. также принадлежат к числу разрешенных. Нулевая комбинация является разрешенной, поскольку циклический код принадлежит к классу систематических. Заметим, что циклический сдвиг нулевой комбинации есть также нулевая комбинация.

Рассмотрим принцип кодирования сообщения, состоящего из k разрядов, к которым добавляются г проверочных разрядов. При этом условимся, что последовательность передачи разрядов такова: сначала передаются информационные разряды, а потом — провероч­ ные. При такой последовательности передачи полиномы удобнее записывать по возрастающим степеням, а не по убывающим, как это было показано в ф-ле (11.6).

Введем следующие обозначения: G(x)—многочлен,

отобража­

ющий комбинацию информационных разрядов

(степень .многочле­

н а — k—1); R(x)

— многочлен, отображающий

комбинацию прове­

рочных разрядов

(степень многочлена — г—1);

F(x)

— многочлен,

отображающий кодовую комбинацию в целом

(степень многочле­

на — п—1 =k + r—1).

 

 

Поскольку многочлен, отображающий информационные разря­ ды, имеет более высокие показатели степеней в полиноме F(x), то полином

F(x) = R(x)

+ xrG(x).

(11.7)

Иными словами, степень разрядов

информационного

многочле­

на

сдвинута в большую сторону на число проверочных разрядов.

 

Комбинация циклического

кода F(x)

образуется

из исходной

комбинации

информационных

разрядов

G(x) путем

умножения

на

полином

Р(х). Поэтому полином Р

называется

образующим.

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

является условие, при котором

кодовый многочлен F(x)

делится

на образующий

полином Р(х)

без остатка. Это

условие

выпол­

няется, если R(x)

равен остатку от деления xrG(x)

на Р(х).

Обнаруживающие ошибки свойства циклического кода основа­

ны на том, что разрешенные

комбинации кода F(x)

делятся

на об­

разующий полином Р(х)

без остатка, а запрещенные

— с остатком.

Комбинации циклического кода формируются так:

 

—

многочлен G(x),

отображающий

информационную ^-разряд­

ную кодовую комбинацию, умножается

на

хг;

 

 

— произведение xrG(x)

делится на образующий полином

Р(х),

и полученный остаток R(x)

определяет г проверочных разрядов ко­

довой

комбинации;

 

F(x) =R(x)-\-xrG(x)

 

 

—

кодовая комбинация

является

разре­

шенной, так как она делится без остатка на

Р(х).

 

 

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

цессе деления вычитание заменяется сложением по модулю 2. Так, например, деление полинома х6 + х5+х3+\ на полином x2 + x+i (соответствующие двоич­ ные формы 1101001 и 111) производится так:

1101001 111

111 10101

110

е

111

101

е ш

10

Двучлен 10 есть остаток от деления полинома 11 Oil001 на полином 111.

Для построения циклического (п, &)-кода, обеспечивающего об­ наружение или исправление ошибок заданной кратности, необхо­

димо

правильно

выбрать образующий полином Р(х)

степени

r = n—k. Известно

[6; 13], что обнаруживающая ошибки

способ­

ность

циклического

кода определяется степенью полинома

Р(х) и

числом его членов. Поэтому основной задачей при построении цик­ лического кода является выбор образующего полинома.

Рассмотрим некоторые основные

свойства циклических кодов.

1. Код, образованный полиномом

Р(х) = 1 +х обнаруживает лю­

бое нечетное число ошибок. Так как исходный многочлен должен

делиться

на

1 +х

без остатка,

то

 

 

 

 

 

 

 

 

 

 

F(x)=(l

+ x) -

0

^ -

=

(l+x)Q

(х),

 

где

Q(x)—частное

от

деления

xrG(x)

на образующий

полином

Р(х).

Полагая х=

1, получим

 

 

 

 

 

 

 

 

 

 

 

 

^ ( 1 ) = ( 1

+

1)Q(1).

 

 

 

 

Отсюда

следует, что

многочлен

F(x),

делящийся без

остатка

на

\+х,

должен

содержать четное число членов. При нечетном

числе

ошибок многочлен

F(x)

превратится

в

многочлен F'(x), ко­

торый содержит нечетное число членов, а поэтому не будет делить­ ся на 1 +х без остатка.

2. Код, образованный полиномом Р(х), обнаруживает все оди­

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

или рав­

на /. Здесь / — степень двучлена Xі+1,

где / — наименьшее

число,

при котором х1+ \ делится без остатка на Р(х).

Доказательство

это­

го положения приведено в {8, 33].

 

 

 

 

 

 

 

Согласно выражению (11.4) число проверочных разрядов для

кодов, обнаруживающих

двойные ошибки (d 0 =3) ,

равно

r ^ l o g 2 X

Х ( п + 1 ) .

Очевидно,

что

код будет

содержать наименьшее

число

разрядов, если r = loga(n+1). Тогда

n = 2r —1. Поэтому для

построе­

ния циклических кодов необходимо

знать 1 = 2т—1.

В этом

случае

двучлены вида х1+1

являются наибольшим

общим кратным

для

всех без исключения неприводимых полиномов степени т.

Непри­

водимым

полиномом

называется такой,

который делится без

остат-

Смотрите также файлы