12. Кодирование и контроль правильности при обмене данными по последовательному цифровому каналу (Лекции по дисциплине "Управляющие ЭВМ и комплексы")

12. Кодирование и контроль правильности при обмене даннымипо последовательному цифровому каналуОсновные режимы передачи данных: симплексный, полудуплексный, дуплексный.Типы синхронизации: а) битовая/тактовая; б) символьная/байтная; в) блочная (блок передается какцепочка битов).На рис. 1 приведены форматы передаваемых данных: а) в асинхронном режиме; б) в синхронномрежиме.АсинхронныйНет обменарежима1Кадр0 D0 D1 D2 D3 D4 D5 D6 D7Стартовый битИнформационные1Бит проверкина чет/нечет101tСтартовый бит1; 2стоповые биты следующего символабиты (5, 6, 7, 8)СинхронныйрежимДанные/символыSYN 1бДанные/символы.......Данные/символыSYN 2t.......Рис.

1. Форматы передаваемых сообщений: а – при асинхронном режиме;б – при синхронномПри передаче блоков данных используется синхронный режим (рис. 1,б). Передатчик (ПД) и прием-ник(ПР) должны быть синхронизированы в течение длительного промежутка времени, поэтому не используетсяобрамление каждого байта, а границы блока фиксируются с помощью специальных начальной и конечнойкомбинаций байтов (SYN 1, SYN 2).

Синхронизация достигается при наличии дополнительной линии,соединяющей 2 узла, однако это дорого. Чаще используется одна линия данных, а тактовая инфор-мациявключается в форму передаваемого сигнала. Для этого используют специальные самосинхронизирующиеся коды,например, Манчестерский.Способы контроля правильности передачи данных (управление ошибками)Под управлением ошибками понимают полный цикл обнаружения/исправления ошибки. Используютсяправила, образующие протокол связи. При этом возможны два подхода:1.

Обнаружение ошибки и автоматическое формирование запроса на повтор сообщения (АЗП);2. Обнаружение и коррекция/исправление ошибки (ОКО).При АЗП - к каждому передаваемому сообщению добавляются дополнительные контрольные биты,которые позволяют приемнику обнаружить некоторые конкретные типы ошибок. Если ошибка обнаружена, тоиспользуются дополнительные процедуры, запрашивающие присылку новой копии сообщений (запрос на повторсообщения).При ОКО - к сообщению добавляется достаточное число служебных битов, позволяющих не толькообнаружить наличие в поступившем сообщении одной или нескольких ошибок, но и локализовать место ошибок.Более того, т.к.

сообщение поступает в двоичном коде, то исправление достигается простым инвертированиемошибочных битов.Если имеется обратный тракт (дуплекс), то более эффективен метод на основе АЗП. Однако, например,при получении информации от космических зондов используется только односторонний канал (симплекс), приэтом задержки передачи от спутников столь велики, что передающая станция успевает передать несколько сотендругих сообщений, прежде чем поступит извещение в обратном направлении. Поэтому зачастую совместно сметодами АЗП используются метод ОКО, что позволяет сократить число повторных передач.Методы обнаружения ошибок при асинхронной передачеИногда достаточно использования одного дополнительного бита «чет/нечет» (вычисляется до пере-дачиданных) на каждый передаваемый символ.

Приемник сам определяет значение этого бита, сравнивает его сполученным, и таким образом выявляет наличие ошибок. Метод позволяет обнаружить ошибку в одном бите.1Нет обмена10Кадр0101110111101t. 3.Информационные биты1001010стоповые битыБит проверкина четность10101101tЕсли возможны ошибки в большем числе (в четном числе) бит, то нужно использовать другие методы (сбольшей избыточностью). Такой метод может быть расширен дополнительным набором битов «чет/нечет»,вычисленных исходя из последовательности символов (рис.

2): каждому символу/строке, передатчикприсоединяет бит «чет/нечет». Кроме того, добавляется еще по одному биту «чет/нечет» на каждый столбец(группы символов).Направлениепередачи(биты)Направлениепередачи(символы/строки)1 11 010011010101 011100110 001110111 1011110110010110001101 00 10 001100001 00B70B6 B5 B4 B3 B2 B1 B0Проверка:в строке - на нечетность;в столбце - на четность.Рис. 2. Обнаружение ошибок при“блочной” передаче данныхИз рассмотрения этого подхода видно, что 2 ошибки в одном символе, не обнаруженные поперечнымбитом «чет/нечет» (в строке), будут обнаружены продольными битами «чет/нечет» (в столбце). Конечно, этосправедливо только при условии, что в одном и том же столбце не возникнут 2 ошибки одновременно.Однако нужно подчеркнуть, что независимо от принятой схемы обнаружения/исправления ошибок несущес-твует средств обнаружения всех возможных комбинаций ошибок с полной гарантией.

Поэтому напрактике целью различных методов обнаружения/исправления ошибок является обеспечение приемлемо низкогоуровня вероятности необнаружения ошибок.Отметим следующее:a) помехозащищенность достигается введением избыточности;б) в дуплексных каналах достаточно применения кодов, обнаруживающих ошибки, т.к. наличие ошибкивызывает повторную передачу данных;в) устранение ошибок с помощью корректирующих кодов реализуют в симплексных каналах связи;г) проверка на четность или нечетность недостаточно надежна.Рассмотрим наиболее широко применяемые коды – коды Хемминга и циклические коды.Управление ошибками на основе кода ХеммингаВведено понятие кодового расстояния D (dij для отдельной пары двоичных кодовых комбинаций) илирасстояния по Хеммингу между двумя кодовыми комбинациями, равное числу несовпадающих разрядов,которое можно определить как число единиц в сумме этих комбинаций по модулю 2 ():011011101001100 0 1 0 0 0 1 (2)10, т.е.

dij=22Если расстояние равно 2, то имеет место двукратная ошибка (r=2). В общем случае, когда искажается rразрядов кодовой комбинации, имеет место r-кратная ошибка.Для кодов в целом рассматривают матрицу расстояний D. Например, для кода х1=00, х2=01, х3=10,х4=11 матрица D имеет вид:00 01 10 11x1 x2 x3 x4x10 1 1 21 0 2 1 x2D = 1 2 0 1 x32 1 1 0 x400011011По горизонтали (i) и по вертикали (j) отмечены все двухразрядные сравниваемые кодовые комбинации(00, 01, 10, 11), а в соответствующих клетках матрицы (ij) – кодовое расстояние по Хеммингу между ними.

Вэтом 2х-разрядном коде исчерпываются все кодовые комбинации (нет избыточности), поэтому любая ошиб-каприведет к тому, что получающаяся неверная кодовая комбинация будет воспринята как разрешенная. Как видноиз полученной матрицы D, для данного кода имеет место соотношение dij,min=1.Рассмотрим 2-разрядный код с проверкой на четность, т.е. код с избыточностью, в нем к каждойкодовой комбинации добавлен 1 разряд, в котором ставится 0, если число единиц четное, и 1 - если нечетное(один избыточный разряд):х1=00 0, х2=01 1, х3=10 1, х4=11 0.Матрица D для него примет вид ( dij,min=2):000 011 101 110x1 x20 22 0D= 2 22 2x3 x42 2 x12 2 x20 2 x32 0 x4000011101110В методах на основе расстояний по Хеммингу возможности обнаружения и исправления (коррекции)ошибок кратности r связаны с минимальным кодовым расстоянием dij,min:- обнаруживаются ошибки кратности r при условии r = dij,min -1;1 d- исправляются ошибки кратности r при r  ent  ij min  , где ent (..) - целая часть от (..).2Т.к.

при контроле на четность dij,min=2, то обнаруживаются только одиночные ошибки, но корректироваться (исправляться) они не могут.Рассмотрим один из алгоритмов формирования и использования кода ХеммингаРассмотрим код Хемминга сdij,min=3, в котором дополнительно вводится k = log2 nразрядов -дополнительная часть кода (ДЧК), где n - число информационных разрядов, k – число избыточных разрядов,округляется до ближайшего большего целого значения.Поскольку dij,min– 1=3 – 1=2, а dij min  1  3  1ent 122то данный код позволяет обнаруживать двукратные ошибки, а исправлять – одиночные ошибки.Алгоритм на передающей стороне.

В передатчике (ПД) применение корректирующего кода, в основном, сводится к вычислению ДЧК посредством выполнения следующих поразрядных операций:31) сложение по модулю 2 двоичных номеров тех информационных разрядов кодовой комбинации,значения которых равны 1; нумерация осуществляется с единицы, а не с нуля !!!2) инвертирование полученной двоичной последовательности (инвертирование результата по п.1).Пример: Передана кодовая комбинация 100110 (n =6), а принята 100010.Следовательно, k = log2 6 = 3(3 – результат округления).Определим ДЧК:010  011  110=111(2)10 (3)10 (6)10где  - символ операции “Сложение по модулю 2”;после инвертирования, окончательно имеем ДЧК, равную 000.010 011110---111ДЧК → 000Теперь вместе с основной кодовой комбинацией будет передаваться и ДЧК(000), т.е.

кодовая комбинация 100110 000.Алгоритм на приемной стороне. В приемнике (ПР) аналогично(см. выше) вновь рассчитывается ДЧК, которая после инвертирования010  110=100(2)10 (6)10ДЧК → 011сравнивается с переданной. Код (результат) сравнения определяетсяпутем выполнения над ними операции сложения по модулю 2, и если он отличен от 0, то его значение (безинверсии !) есть номер ошибочно принятого разряда.Так, если принята кодовая комбинация 100010, то рассчитанная в приемнике ДЧК равна инверсии от000 011Определяем код сравнения, посредством выполнения операции сложение по---модулю 2 (без дальнейшей его инверсии !): 000  011= 011 (3)10, что означает ошибку011 (3)10результата выполнения операции в ПР, т.е.

011.в 3-м разряде.Исправляется/корректируется ошибка инвертированием 3-го разряда в принятой кодовой комбинации.В общем случае для того, чтобы код позволял обнаруживать все ошибки кратности r  rО и корректировать/исправлять все ошибки кратности r  rк, его кодовое расстояние должно удовлетворять нера-венствуd  rО + rк + 1 (rО  rк)Управление ошибками на основе циклических (полиномиальных) кодовК числу эффективных кодов, обнаруживающих одиночные, кратные ошибки и пачки ошибок, отно-сятсяциклические коды “CRC-коды” (Cyclic Redundance Code).Информация (данные) длиной n бит представляется в виде полинома степени, не более n-1.Например, данные вида А = (1011001)2 = (89)10 (n=7) представляются в виде полиномаА = 126 + 025 + 124 + 123 + 022 + 021 + 120 = 26 + 24 + 23 + 1 = 64+16+8+1 = 89.Рассмотрим один из алгоритмов формирования и использования циклического кодаВведем обозначения:А - информационный полином степени n, соответствующий передаваемым данным;g – порождающий полином степени k, определяющий число контрольных/избыточных разрядов (корректирующую способность кода);С – полином степени n+k, соответствующий передаваемому циклическому коду.4Кодирование информации на передающем узле происходит следующим образом.Информационный полином А умножается на 2k, т.е.

сдвигается на k разрядов влево.Полином 2kА делится на полином g и определяется остаток В, т.е. полином степени, меньшей чем k,который записывается в k младших разрядах кодового полинома.Далее формируется кодовый полином С, старшие n разрядов которого представляют информационныйполином А, т.е. передаваемые данные, а k младших разрядов – остаток В, т.е.