Файл: Бездудный, В. Г. Техника безопасности в шахтном строительстве.pdf

широкое распространение в устройствах передачи дискретной инфор­ мации.

В качестве примера построения рекуррентных Кодов рассмотрим функциональные схемы кодирующего и декодирующего устройств цепного кода, исправляющего шестиразрядные пакеты ошибок [5J. Информационные символы поступают на вход регистра рис. 28, а. Синхронный переключатель подключает поочередно информационные и проверочные разряды. Каждый информационный элемент а,- участвует

Рис. 28. Функциональные схемы кодирующего (а) и декодирующего (б) устройств гюпного кода.

в формировании двух проверочных элементов Ь,- (сначала на сум­ матор по модулю два поступает импульс после ячейки 1, потом, пройдя последующие ячейки, он вновь поступит на сумматор, формируя уже другой проверочный элемент). Вместе с тем, каждый проверочный элемент bj формируется двумя информационными элементами at ^элементом, который находится в данный момент в ячейке 1, и элементом, который находится в ячейке 4). Таким образом, количество информа­ ционных и проверочных элементов всегда одинаково, и передаются

определяется длиной защитного промежутка и в данном случае равно f = 2 f + l = 2 - 3 + I = 7.

Декодирование цепного кода происходит следующим образом. Переключатель, работающий синхронно с переключателем шифратора, поочередно подключает на вход декодирующего устройства информа­ ционный и проверочный регистры (рис. 28, б). Если искажений в линии не было, то, когда в информационном регистре записаны: сц,-t-з в ячей­ ке 1, а,- в ячейке 4, а,_3 в ячейке 7, в проверочном регистре в этот момент в ячейке 7 записан bj+3 — аг+3 + alt а в ячейке 10 6/_3 =

120

= a{ -f- й;__з. Из информационных импульсов, поступивших в инфор­ мационный регистр, вновь образуются проверочные импульсы, как и в шифраторе. Если эти вновь образованные проверочные импульсы

ном случае с выхода сумматоров а2 и Ь2 сигналы подаются на схему совпадения И, которая выдает разрешение на прохождение корректи­ рующего импульса только тогда, когда совпадут сигналы а2 и Ь2.

бинация отличается от предыдущей одним символом. Такой код удобен при передаче телемеханической информации о медленно изменяющихся процессах. Как известно, подавляющее большинство телемехани­ ческих объектов имеет плавные характеристики, и для передаваемой телемеханической информации характерен плавный переход от одного значения к другому. Если при использовании кода Грея в принятом сообщении одновременно изменяются несколько символов, то это говорит либо о помехах в канале связи, либо о нарушении режима работы контролируемого объекта. В этом случае простой двоичный код использовать неудобно, так как в нем имеются комбинации, в

121

которых кодовые символы предыдущей комбинации отличаются от кодовых символов последующей комбинации всеми символами (напри­ мер, 3 — 011; 4 — 100; 7 — 011; 8 — 1000; 15 — 01111; 16 — 10000 и т. д.).

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

диодов изменяется одновременно не больше чем на 1. Если на фотодиод падает свет, его сопротивление на­ много уменьшается. В этот момент ток резко возрастает. Это равно­ сильно передаче единицы кода. На

W рис. 29 младшие разряды располо­

IIIжены дальше от центра. Если идти по часовой стрелке, то сначала все семь диодов будут затемнены (код

янным количеством единиц в каждой кодовой комбинации. К таким ко­ дам относятся широко используемые в телеграфии коды с постоянным соотношением разнополярных импульсов, например международный телеграфный код № 3 содержит три токовых и четыре бестоковых импульса. Увеличение или уменьшение количества токовых посылок в коде говорит о наличии ошибки.

Код Плоткина [57] — равномерный блочный код, позволяющий эффективно корректировать симметричные и независимые ошибки. Широкого применения он не нашел, так как требует для своей реали­ зации сложные декодирующие и кодирующие устройства.

Разделимые коды делятся на систематические и несистематические. Примером несистематических разделимых кодов могут служить коды Бергера. В этих кодах передаваемые сообщения разбиваются на под­ блоки. Обычно подблоком бывает стандартная шестиразрядная комби­ нация телеграфного кода. Проверочные символы определяются в ре­ зультате суммирования подблоков и представляют собой запись их суммы. Коды Бергера, подобно циклическим кодам, распространены в технике передачи данных по телеграфным каналам и позволяют обнаружить пакеты ошибок с длиной пакета, не превышающей длины отдельного подблока. Коды Бергера особенно эффективны для двоич­ ных каналов с асимметричными ошибками.

122

К систематическим кодам относятся коды Хэмминга, Голея, Рида — Мюллера, Макдональда, Варшамова, Элайеса, Галагера [26, 53, 54, 561, а также обширная группа циклических кодов.

Систематические коды отличаются от рекуррентных тем, что в них формирование проверочных элементов происходит по k информа­ ционным элементам кодовой комбинации. В канал связи идет п-эле­ ментная комбинация, состоящая из k информационных и п — k про­ верочных разрядов, тогда как в рекуррентных кодах проверочные элементы формируются путем сложения двух или нескольких инфор­ мационных элементов, сдвинутых друг от друга на расстояние, равное шагу сложения. Кроме того, в систематических кодах провероч­ ные символы могут образовываться путем различных линейных ком­ бинаций информационных символов. Декодирование систематических кодов также основано на проверке линейных соотношений между символами, стоящими на определенных проверочных позициях. В случае двоичных кодов этот процесс сводится к проверке на четность. Если число единиц четно, линейная комбинация символов дает О, в противном случае— 1.

Построение систематических кодов основано на использовании свойств двоичных кодов. Одна из важнейших закономерностей систе­ матического кода вытекает непосредственно из правила сложения по модулю 2, а именно: сумма по модулю 2 комбинаций систематического кода всегда является комбинацией этого кода. Большинство система­ тических кодов отображаются при помощи производящей и проверочной матриц (см. тему 7), которые строят на основании следующих рассуждений. Общее число комбинаций ^-разрядного двоичного кода

(включая нулевую) N = 2k, число ненулевых комбинаций N — 2к —

— 1. Для того чтобы код обладал корректирующими способностям», в нем должно быть какое-то количество добавочных символов d, создаю­ щих Определенную избыточность. Наличие добавочных символов

вкоде приведет к тому, что для передачи N сообщений потребуется не k, а п > k разрядов.

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

вдвоичном коде, указывали номер искаженного символа.

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

Используя выражение (44), можно записать d >• log2и + 1, или2

123

Так как d = п — k, то

Формулы (92) и (93) устанавливают зависимость между числом информационных и проверочных разрядов систематических кодов. При этом производящая матрица уже не может быть квадратной, так как такой код содержит п >• & разрядов, а число ненулевых комби­

наций не увеличилось, а осталось равным 2* — 1. Ранг такой матрицы и число ее строк определяется числом к, а число столбцов — числом

tt ~ к -f- d.

Производящую матрицу строят при помощи единичной матрицы ранга k (матрица состоит из k столбцов и k строк, имеет единицы по главной диагонали и нули на оставшихся позициях) и некоторой добавочной матрицы, имеющей k строк и п — к столбцов. Комбинации строк добавочной матрицы выбирают, исходя из следующих условий: каждая строка добавочной матрицы должна содержать не менее чем 4 — 1 единиц, а сумма по модулю 2 любых строк — не менее d — 2 единиц. Такое построение позволяет находить все оставшиеся кодовые комбинации путем суммирования по модулю 2 строк производящей матрицы во всех сочетаниях: по две, по три и т. д., пока не дойдем, в конце концов, до суммы всех строк.

Декодирование принятого сообщения и обнаружение возможных ошибок осуществляется при помощи проверочной матрицы. Построение проверочной матрицы производят следующим образом: строят единич­ ную матрицу с числом столбцов <i = п ■— к и слева приписывают матрицу, содержащую k столбцов и d строк. Сумма по модулю 2 ин-

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

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

Пример 10. Пусть требуется передать 16 сообщений. Построим систематиче­ ский код. исправляющий одну ошибку.

Из условия имеем: 16 = 2fe = 2*. Следовательно, k = 4; число добавочных символов для исправления одиночной ошибки d = 2S 1 = 3; п — k -f- d = 7. Строим производящую матрицу.

При построении добавочной матрицы необходимо следить не только за тем, чтобы число единиц в каждой ее строке было п > d — 1 (в рассматриваемом при-

124