Олифер В.Г., Олифер Н.А. - Компьютерные сети. Принципы, технологии, протоколы (4-ое изд.) - 2010 - обработка (953099), страница 69
Текст из файла (страница 69)
Передатчик сканирует последовательность передаваемых байтов и если обнаруживает последовательность из трех или более одинаковых байтов, заменяет ее специальной трехбайтовой последовательностью, в которой указывает значение байта, количество его повторений, а также отмечает начало этой последовательности специальным управляющим символом. Этот метод носит вювание символьного подавления. Метод кодирования с помощью кодов переменной длины опирается на тот факт, что не все символы в передаваемом кадре встречаются с одинаковой частотой.
Поэтому во многих схемах кодирования коды часто встречающихся символов заменяют кодами меньшей вливы, а редко встречающихся — кодами большей длины. Такое кодирование называется также статистическим кодированием. Из-за того что символы имеют разную длину, для передачи кадра возможна только бит-ориентированная передача. При статистическом кодировании коды выбираются таким образом, чтобы при анализе последовательности битов кожно было бы однозначно определить соответствие определенной порции битов тому вли иному символу или же запрещенной комбинации битов.
Если данная последовательность битов представляет собой запрещенную комбинацию, то необходимо к ней добавить еще один бит и повторить анализ. Например, если при неравномерном кодировании для наиболее часто встречающегося символа «Р» выбран код 1, состоящий из одного бита, то значение 0 однобитного кода будет запрещенным. Иначе мы сможем закодировать только два символа.
Для другого часто встречающегося символа «О» можно использовать код 01, а код 00 оставить как запрещенный. Тогда для символа «А» можно выбрать код 001, для символа «П» — код 0001 и т. п. Неравномерное кодирование наиболее эффективно, когда неравномерность распределения частот передаваемых символов велика, как при передаче длинных текстовых строк. Напротив, при передаче двоичных данных, например кодов программ, оно малоэффективно, гак как 8-битные коды при этом распределены почти равномерно. Одвям из наиболее распространенных алгоритмов, на основе которых строятся неравноксрпне коды, является алгоритм Хафманв, позволяющий строить коды автоматически на «свовании известных частот появления символов. Существуют адаптивные модификации хеюда Хафмана, которые позволяшт строить дерево кодов «на ходу», по мере поступления ынвых от источника.
Многие модели коммуникационного оборудования, такие как модемы, мосты, коммутаторы в шршрутизаторы, поддерживают протоколы динамической компрессии, позволяющие ге«рати«в объем передаваемой информации в 4, а иногда и в 8 раз. В таких случаях говорят, ~то вротокол обеспечивает коэффициент сжатия 1 4 или 1:8. Существуют стандартные паотоколы компрессии, например Ч42Ь|з, а также большое количество нестандартных фирменных протоколов. Реальный коэффициент компрессии зависит от типа передаваеяих данных. Так, графические и текстовые данные обычно сжимаются хорошо, а коды щюграим — хуже. 274 Глава 9. Кодирование и мультиплексирование данных Обнаружение и коррекция ошибок Надежную передачу информации обеспечивают различные методы.
В главе 6 были рассмотрены принципы работы протоколов, которые обеспечивают надежность за счет повторной передачи искаженных или потерянных пакетов. Такие протоколы основаны на том, что приемник в состоянии распознать факт искажения информации в принятом кадре. Еще одним, более эффективным подходом, чем повторная передача пакетов, является использование самокорректирующихся кодов, которые позволяют не только обнаруживать, но и исправлять ошибки в принятом кадре.
Методы обнаружения ошибок Методы обнаружения ошибок основаны на передаче в составе блока данных избыточной служебной информации, по которой можно судить с некоторой степенью вероятности о достоверности принятых данных. В сетях с коммутацией пакетов такой единицей информации может быть Р1Н) любого уровня, для определенности будем считать, что мы контролируем кадры. Избыточную служебную информацию принято называть контрольной суммой, или контрольной последовательностью кадра (Ргаше Спеси Яеоцепсе, РСБ). Контрольная сумма вычисляется как функция от основной информации, причем не обязательно путем суммирования. Принимающая сторона повторно вычисляет контрольную сумму кадра по известному алгоритму и в случае ее совпадения с контрольной суммой, вычисленной передающей стороной, делает вывод о том, что данные были переданы через сеть корректно.
Рассмотрим несколько распространенных алгоритмов вычисления контрольной суммы, отличающихся вычислительной сложностью и способностью обнаруживать ошибки в данных. Контроль по паритету представляет собой наиболее простой метод контроля данных. В то же время это наименее мощный алгоритм контроля, так как с его помощью можно обнаруживать только одиночные ошибки в проверяемых данных. Метод заключается в суммировании по модулю 2 всех битов контролируемой информации. Нетрудно заметить, что для информации, состоящей из нечетного числа единиц, контрольная сумма всегда равна 1, а при четном числе единиц — О. Например, для данных 100101011 результатом контрольного суммирования будет значение 1. Результат суммирования также представляет собоп один дополнительный бит данных, который пересылается вместе с контролируемой информацией.
При искажении в процессе пересылки любого одного бита исходных данньп (или контрольного разряда) результат суммирования будет отличаться от принятого контрольного разряда, что говорит об ошибке. Однако двойная ошибка, например 1101010! й будет неверно принята за корректные данные. Поэтому контроль по паритету применяетсп к небольшим порциям данных, как правило, к каждому байту, что дает коэффициент избыточности для этого метода 1/8.
Метод редко используется в компьютерных сетях из-зп значительной избыточности и невысоких диагностических возможностей. Вертикальный и горизонтальный контроль по паритету представляет собой модификацию описанного метода. Его отличие состоит в том, что исходные данные рассматриваютсп в виде матрицы, строки которой составляют байты данных. Контрольный разряд пой считывается отдельно для каждой строки и для каждого столбца матрицы. Этот метод по зволяет обнаруживать большую часть двойных ошибок, однако он обладает еще больше1 избыточностью. На практике этот метод сейчас также почти не применяется при передан информации по сети.
275 Обнаружение н коррекция ошибок Циклический избыточный контроль (Сус!(с Кедппдапсу СЬеск, СКС) является в настояшее время наиболее популярным методом контроля в вычислительных сетях (и не только а сетях, например, этот метод широко применяется при записи данных на гибкие и жесткие диски). Метод основан на представлении исходных данных в виде одного многоразрядного двоичного числа. Например, кадр стандарта Ег(уегпег, состоящий из 1024 байт, рассматривается как одно число, состоящее из 8192 бит.
Контрольной информацией считается остаток от деления этого числа на известный делитель Я. Обычно в качестве делителя выбирается семнадцати- или тридцатитрехразрядное число, чтобы остаток от деления имел длину 16 разрядов (2 байт) или 32 разряда (4 байт). При получении кадра данных снова вычисляется остаток от деления на тот же делитель В, но при этом к данным кадра добавляется н содержащаяся в нем контрольная сумма. Если остаток от деления на Я равен нулю, то делается вывод об отсутствии ошибок в полученном кадре, в противном случае кадр считается искаженным.
Этот метод обладает более высокой вычислительной сложностью, но его диагностические юзможности гораздо выше, чем у методов контроля по паритету. Метод СКС позволяет обнаруживать все одиночные ошибки, двойные ошибки и ошибки в нечетном числе битов. Метод обладает также невысокой степенью избыточности.
Например, для кадра Ейегпег размером 1024 байт контрольная информация длиной 4 байт составляет только 0,4 К. Методы коррекции ошибок Техника кодирования, которая позволяет приемнику не только понять, что присланные ывные содержат ошибки, но и исправить их, называется прямой коррекцией ошибок (гопуагд Еггог Соггесг(оп, ГЕС). Коды, которые обеспечивают прямую коррекцию ошибок, требуют введения ббльшей избыточности в передаваемые данные, чем коды, только абнаружнваюшие ошибки.
Прв применении любого избыточного кода не все комбинации кодов являются разрешениями. Например, контроль по паритету делает разрешенными только половину кодов. Пши иы контролируем три информационных бита, то разрешенными 4-битными кодами г дополнением до нечетного количества единиц будут: 000 1, 001 О, 010 О, 011 1, 100 О, 101 1, 110 1, 111 0 Тоесть всего 8 кодов из 16 возможных. яха того чтобы оценить количество дополнительных битов, требуемых для исправления аавбок, нужно знать так называемое расстояние Хемминга между разрешенными комбишцкямн кода. Расстоянием Хемюппп называется минимальное число битовых разрядов, а вторых отличается любая пара разрешенных кодов.
Для схем контроля по паритету 1ягстояние Хемминга равно 2. яакяо доказать, что если мы сконструировали избыточный код с расстоянием Хемминга, (вами я, то такой код будет в состоянии распознавать (я — 1)-кратные ошибки и исправить(я-1)/2-кратные ошибки. Так как коды с контролем по паритету имеют расстояние Таиянга, равное 2, то они могут только обнаруживать однократные ошибки и не могут вщавлять ошибки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
