Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

7-G. ЗАЩИТА ИНФОРМАЦИИ ПРИ ПЕРЕДАЧЕ ДАННЫХ М Е Ж Д У ЦВМ

Существует два основных принципа построения си­ стем .передачи данных: 1) без использования обратной связи; 2) с использованием обратной связи. В первом случае 'борьба с ошибками производится с помощью корректирующих кодов с исправлением ошибок. Во вто­ ром случае исправление обнаруженных ошибок произво­ дится с помощью повторной передачи данных.

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

ав системах с переспросом — на принимающую.

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

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

258

коды требуют меньшей избыточности. Например, укоро­ ченный циклический (240, 228)-код обеспечивает вероят­ ность пропуска ошибки 10~7, если вероятность появления ошибки в канале равна Ю - 4 . При увеличении количества контрольных разрядов до 16 вероятность пропуска ошиб­ ки становится менее Ю - 8 . В последнем случае избыточ­ ность кода равна (16/244) • 100% =6,5%'. Аналогичную достоверность простейший двумерный итеративный код обеспечивает при избыточности порядка 15%: (Л. 7]. Как уже упоминалось, международным стандартом к приме­ нению рекомендован циклический код длиной до 980 разрядов, порождаемый полиномом л:1 е +д:1 2 +д;5 + 1.

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

В ряде случаев целесообразно использование и дру­ гих классов кодов — сверточных, кодов с постоянным ве­ сом и др. Коды с постоянным весом хорошо приспособ­ лены для обнаружения ошибок в асимметричных кана­ лах. Поэтому они нашли широкое применение в системах передачи информации. Этот факт нашел отражение в разработке международного стандарта на код с по­ стоянным весом. Этот код длиной 7 разрядов известен как стандартный код № 3. Каждый символ кода содер­ жит 3 единицы, что позволяет при использовании одного регистра кодировать 35 символов [Л. 55].

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

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

Разработка и практическая проверка декодирующих программ для кодов Хэмминга, Рида — Маллера, БЧХ и Файра показала, что время декодирования является значительным {Л. 56]. Декодирующие программы, состав­ ленные для трехадресной машины со средним быстро­ действием 103 операций в секунду, имели следующие параметры. Максимальное время декодирования кодово­ го слова длиной п=31 разрядов (код Хэмминга) состав­ ляет 0,3 с. Для хранения программы требуется 67 ячеек памяти. Программа декодирования кодов Рида — Мал­ лера длиной я = 6 4 разряда, d = 8 занимает 310 ячеек па­ мяти, а время ее работы не превышает 4 с. Время декоди­ рования кодов БЧХ длиной /г=30 разрядов и d^'10 ко­ леблется от 0,2 до 3 с.

Приведенные оценки показывают, что при декодиро­ вании групповых кодов, длина п которых не превышает разрядности ЦВМ, требуется выполнить от 10 до 100 операций на один декодируемый символ в зависимости от количества исправляемых ошибок. Таким образом, средняя скорость декодирования

с « 1/(10-5-100) J„,

где tK — среднее время выполнения команды (операции) в используемый ЦВМ. Например, если FK =10 мкс, то и:«104 -г-103 бод. Это достаточно низкая скорость декоди­ рования, если учесть, что по телефонному каналу связи можно передавать информацию со скоростью порядка 103 бод. Введение в состав операций ЦВМ специальных команд (счет единиц в ячейке, сдвиг вправо до первой единицы, сдвиг влево до первой единицы и др.), учиты­ вающих специфику алгоритмов декодирования, позволя­ ет существенно (иногда на порядок) уменьшить количе­ ство операций, затрачиваемых на декодирование одного символа. Если при декодировании необходимо только об­ наружить ошибки, то скорость декодирования резко воз­

260

Приложение 1

ОСНОВНЫЕ АЛГЕБРАИЧЕСКИЕ ПОНЯТИЯ

ИТЕРМИНЫ

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

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

деляющими их законами композиции и, во-вторых, аксиомами, кото­

тивное обозначение; закон, обозначаемый знаком «•», называют умно­

пу), если: 1) он ассоциативен; 2) он обладает нейтральным элемен­ том; 3) для каждого элемента из множества М в М существует эле­ мент, симметричный ему относительно этого закона.

Если на множестве определено сложение, то нейтральный эле­

262