12. Кодирование и контроль правильности при обмене данными по последовательному цифровому каналу (1245070), страница 2
Текст из файла (страница 2)
контрольные биты.Естественно, что сформированный полином С делится на порождающий полином g без остатка.Обнаружение ошибки основано на том, что разрешенными являются информационные слова, полиномкоторых делится без остатка на порождающий полином (т.е. принятые данные не содержат ошибок), а запрещенными – имеющие ненулевой остаток (содержатся ошибки).Известен алгоритм, в котором образующий (порождающий) двоичный полином g является представлением одного из простых множителей, на которые раскладывается число 2n-1, где 2n обозначает единицу в n-мразряде, n равно числу разрядов кодовой комбинации.Кодирование заключается в умножении каждой кодовой комбинации на образующий полиномдекодирование – в делении принятой кодовой комбинации на g.g, аОбозначим исходные числа/коды как Аi, а закодированные - как Сi= Aig.При обнаружении ошибки, сигнал об ошибке поступает в передатчик (ПД), что вызывает повторную передачу.Пусть, например, передаются данные в виде 10-разрядных кодовых комбинаций, т.е.
n=10.Тогда 210-1 = 1023 = 1193. Выберем в качестве образующего полинома g = (11)10 = (1011)2.Рассмотрим один из широко применяемых алгоритмов кодирования на основе циклических кодовЭтот алгоритм отличается тем, что операция деления на образующий полином g заменяется операциейсложение по модулю 2 () с этим полиномом; выполняются следующие операции:1) ПД формирует новую кодовую комбинацию вида А(2k); т.е. к исходному кодируемому числу А справаприписывается k нулей (число битов в образующем полиноме, уменьшенное на 1);2) над полученным числом А(2k) на каждом шаге осуществляется поразрядная операция с образующим полиномом g(2).
Формально это выглядит аналогично делению “столбиком”, но здесь отсутствуетоперация вычитания на каждом шаге. При этом на каждом шаге получается остаток, который дополняется доразмерности образующего полинома, а затем вновь выполняется поразрядная операция , полученный остатокдополняется и т.д.Окончательный остаток В (тоже полином) и представляет собой дополнительную часть кода (ДЧК), т.е.избыточные k-разрядов; ими заменяют в кодовой комбинации А приписанные справа k нулей, т.е. формируетсяпередаваемая кодовая комбинация С, С= А(2k)+В.На приемном узле выполняются аналогичные операции, но над кодовой комбинацией С (С=А24+В) собразующим полиномом g.Если окончательный остаток не равен 0, то при передаче данных произошла ошибка и нужна повторнаяпередача кода А, в противном случае ошибок нет.Пример (рис.
3): Пусть передается кодовая комбинация А = 1001 1101, n=8, 28-1=255. Представим эточисло в виде произведения простых сомножителей 255 = 3175. Выберем для формирования образующегополинома число 17: g = (17)10 = (10001)2. Число избыточных разрядов k = 5-1 = 4, т.е. дополнительная часть кодадолжна содержать число битов в образующем полиноме, уменьшенное на 1.Выполняемые операции на приемном узле (рис. 3,б,в). Это аналогичные операции (см. выше), но уже надкодовой комбинацией С(С = А24+В = 1001 1101 0100) с образующим полиномом g = 10001. Еслиокончательный остаток равен 0 (рис.
3,б), то при передаче данных ошибок нет, в противном случае (рис. 3,в),т.е. остаток не равен 0, произошла ошибка и нужна повторная передача данных.Положительными свойствами циклических кодов является малая вероятность необнаружения ошибки исравнительно небольшое число избыточных разрядов.5Операции на передающем узле1001110100001 0 0 0 1101011 0 0 0 1а1000010001100ДЧК 0100Передаваемаякодовая комбинация:100111010100Ошибки отсутствуютбОперации на приемном узлеИмеются ошибки10011101010010001101011 0 0 0 110001 100010 0 0 =01001111101001 0 0 0 1101111 0 0 0 1вОстаток равен 0.Ошибок нет.11001100011000010001100Имеется остаток В=10.Обнаружена ошибка.Рис. 3. Иллюстрация кодирования/декодирования на основе циклических кодов:а – на передающем узле;б – в принятых данных не обнаружено ошибок;в – в принятых данных обнаружена ошибка.Практическое применение циклического избыточного контроляНапример, кадр стандарта Ethernet, состоящий из 1024 байт, будет рассматриваться как одно число,состоящее из 8192 битов.
В качестве контрольной информации рассматривается остаток от деления этого числана известный делитель R – тоже представленный в виде полинома.Обычно в качестве делителя выбирается 17- или 33-разрядное число (двоичный полином), чтобы остатокот деления имел длину 16 разрядов (2 байта) или 32 разряда (4 байта).При получении кадра данных снова вычисляется остаток от деления на тот же делитель, но при этом кданным кадра добавляется и содержащаяся в нем контрольная сумма.Если остаток от деления на R равен 0, то делается вывод об отсутствии ошибок в полученном кадре,в противном случае кадр считается искаженным.В протоколе V.42 для кодирования кодовых групп в 240 разрядов с 2 избыточными байтами(называемыми также контрольной суммой КС=2 байтам) используется полином:g(X) = 216+212+25+1, что эквивалентно коду 1 0001 0000 0010 0001.Возможен также образующий полином для КС=4 байта:g(X) = 232+226+223+222+216+212+211+210+28+27+25+24+22+21+20,который используется в локальной сети Ethernet для передачи сообщений объемом 1024 байт = 8192 бита.6Контроль с помощью сторожевых таймеров.
Контроль с помощью сторожевых таймеров (watchdogtimes) является простым и широко употребляемым средством контроля, дополняющим средства на основе кодаХемминга и циклических кодов.Сторожевой таймер обнаруживает ошибки процессора путем слежения за его активностью. Процессорпериодически запускает внешний по отношению к нему таймер (счетчик обратного счета), который начинаетотсчитывать время таймаута (например, 500 мс).
Если процессор исправен, он подает строб на таймер доистечения этого времени. Если за время таймаута процессор не запустит таймер, фиксируется ошибка и выдаетсяпрерывание.Сжатие (компрессия) данныхНа современном этапе развития информационных технологий требования к пропускной способности иобъему памяти сетевых средств довольно жесткие. Например, для показа 5-минутного фрагмента видео-фильма вокне 352 х 288 пикселов при частоте смены кадров 25 Гц и при представлении пиксела 24-разрядным кодомтребуется скорость передачи данных 7,6 Мбайт/с и память 2,3 Гбайт.
Поэтому необходимо сжатие информации.Т.о., при стремлении сократить время передачи данных и сэкономить объем внутренней памятиустройств возникает необходимость ставить вопрос о сжатии (компрессии) данных, т.е. о передаче того жеколичества информации с помощью последовательностей символов меньшей длины.
Это особенно актуально,если вспомнить, что определение и коррекция ошибок при передаче данных требуют избыточности кодов.Для целей сжатия данных используются специальные алгоритмы, уменьшающие избыточность. Эффектсжатия оценивают коэффициентом сжатия K = n/q, где n - число минимально необходимых символов дляпередачи сообщения (число символов на выходе эталонного алгоритма сжатия); q - число символов в сообщении,сжатом данным алгоритмом. Часто степень сжатия оценивают отношением длин кодов на входе и выходеалгоритма сжатия.Компрессия/сжатие и декомпрессия данных осуществляется либо на прикладном программном уровне,либо с помощью аппаратных средств.
Устройства или программы, применяемые для компрессии и декомпрессии,называют кодеками (“кодирование” и “декодирование”).Т.к. на предварительное сжатие данных передатчик тратит дополнительное время, к которому нужнодобавить аналогичные затраты времени на разворачивание этих данных в приемнике, то выгоды от сокращениявремени на передачу сжатых данных обычно бывают заметны только для низкоскоростных каналов – около 64Кбит/с.По способу сжатия относительно текущего времени существующие методы сжатия можно разделить на 2группы:Статические, обеспечивающие предварительное сжатие данных (например, с помощью архиваторов типаARJ, RAR, WinZip), после чего они отсылаются в сеть.
Речь идет о сжатии данных с помощью программ сжатия.Динамические, обеспечивающие компрессию совместно с передачей данных.По способу сжатия относительно сохранности исходной информации существующие методы сжатияможно разделить тоже на 2 группы:- алгоритмы, не уменьшающие количество информации в сообщении, т.е.
сжатие без потерь(алгоритмы Лемпеля-Зива, RLE, кодирование Хаффмена и др.);- алгоритмы сжатия с потерями (JPEG, M-JPEG, MPEG).Алгоритмы сжатия без потерьАлгоритм Лемпеля-Зива – лежит в основе некоторых архиваторов (pkzip, arj, lha) и программдинамического сжатия. Основная идея – второе и последующие вхождения некоторой строки символов всообщении заменяются ссылкой на ее первое появление в сообщении (для сжатия текстов и графики).Алгоритм символьного подавления - наиболее эффективен, когда передаваемые данные содержатбольшое количество повторяющихся байтов. Например, при передаче черно-белого изображения черныеповерхности будут порождать большое количество нулевых значений, а максимально освещенные участки –большое количество байтов, состоящих из единиц.Передатчик сканирует последовательность передаваемых байтов и, если обнаруживает последовательность из 3 или более одинаковых байт, то заменяет ее специальной 3-байтовой последовательностью, вкоторой указывается значение байта, число его повторений, а также отмечает начало этой последовательностиспециальным управляющим символом.К этой же группе примыкают алгоритмы RLE (Run Length Encoding).
В них вместо передачинепрерывной цепочки из одинаковых символов передаются символ и значение длины цепочки – два байта (в7первом – символ, во втором – счетчик, т.е. число, которое показывает, сколько таких символов идет подряд).Метод эффективен при передаче растровых изображений (сжатие графики: файлы формата РСХ и видео), номалополезен при передаче текста.Алгоритм Хаффмена реализует замену информационных символов кодовыми последовательностямиразличной длины (коды переменной длины).Идея метода - часто повторяющиеся символы нужно кодировать более короткими цепочками битов, чемцепочки редких символов. Строится двоичное дерево, листья соответствуют кодируемым символам, код символапредставляется последовательностью значений ребер (эти значения в двоичном дереве суть 1 и 0), ведущих откорня к листу.
Листья символов с высокой вероятностью появления находятся ближе к корню, чем листьямаловероятных символов.Распознавание кода, сжатого по методу Хаффмена, выполняется по алгоритму, аналогичному алгоритмамвосходящего грамматического разбора. Такое кодирование называют также статистическим кодированием.Алгоритм позволяет строить неравномерные коды автоматически, на основании известных частотпоявления символов.Например, пусть набор из 8 символов (А, В, С, D, E, F, G, H) имеет следующие правила кодирования: А 10; E 0001; B 01; F 0000; C 111; G 0011; D 110; H 0010.Тогда при распознавании, например, входного потока 1 0 1 1 0 0 0 0 0 1 1 0 в стек распознавателязаносится 1, но 1 не совпадает с правой частью ни одного из правил. Поэтому в стек добавляется следующийсимвол 0. Полученная комбинация 10 распознается и заменяется на А (есть правило А 10).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
