МОДЕМНЫЕ ПРОТОКОЛЫ КОРРЕКЦИИ ОШИБОК

1. Принципы коррекции ошибок

Не вдаваясь глубоко в теорию кодирования и помехозащищенности передачи информации, можно лишь констатировать, что: избыточность - единственный реальный базис обнаружения и коррекции ошибок. Избыточность в широком смысле. Она может быть "последовательной", в случаях применения любого из методов кодирования, т.е. передача дополнительной по отношению к "полезной" информации. Либо "параллельной", в случаях как использования параллельных каналов связи (возможно, различной физической природы), так и применения информационной обратной связи, т.е. возврат (используя дуплексный канал) принятой информации для анализа передатчиком ее правильности. Применение кодирования с решающей обратной связью - это пример комбинированной, "последовательно-параллельной" избыточности.

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

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

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

Третьим фактором, оказывающим огромное влияние на выбор методов коррекции ошибок, является помеховая обстановка в канале передачи данных. А она такова (особенно в "отчих пределах"), что ограничиться простым контролем четности, чего бывает достаточно для локальных сетей, - не кажется удачным решением. Представляется на первый взгляд, что применение симплексного корректирующего кодирования - неплохое решение поставленной задачи. Это кодирование позволяет не только обнаруживать ошибки, но и указывать на их местоположение, т.е. исправлять их, что позволяет отказаться от обратной связи. Однако, степень избыточности при этом весьма высока: объем дополнительной информации сравним с объемом "полезной". Для исправления только одиночной ошибки необходимы по крайней мере три дополнительных бита на байт. И этот объем стремительно возрастает с ростом глубины коррекции ошибок, что в конечном счете может свести выигрыш от высокой надежности и отсутствия повторов к глобальному и стабильному проигрышу в стоимости "излишнего" трафика, который, к тому же, будет совершенно индифферентен к помеховой обстановке (возможно, неплохой).

Разумным компромиссом было сочтено применение циклического помехозащищенного кодирования с решающей обратной связью. Суть этого метода состоит в следующем. Вся "полезная" информация разбивается на "порции" - кадры. Передача каждого кадра завершается передачей специальной контрольной последовательности кадра, подсчитанной по некоему, заранее определенному алгоритму. Этот рекуррентный алгоритм в процессе выдачи кадра модифицирует контрольную последовательность с помощью очередного выдаваемого байта. Удаленная сторона, принимая кадр, также подсчитывает контрольную последовательность по известному алгоритму. По окончании приема кадра производится сравнение подсчитанной контрольной последовательности с принятым в конце кадра ее значением. По результатам сравнения приемник решает гамлетовский вопрос: быть ли данному кадру, или его следует повторить. Результат решения этого вопроса приемник сообщает передатчику посредством некоей "квитанции". Отсюда другое название этого метода: метод автоматического повтора запроса (ARQ, Automatic Repeat reQuest).

Основная ответственность за надежность обнаружения ошибок при этом методе лежит на алгоритме вычисления контрольной последовательности кадра. Здесь используется аппарат циклического избыточного контроля (CRC, Cyclic Redundancy Check). Циклическое кодирование базируется на математической теории групп, алгебре многочленов и теории колец. Оставив для другого раза теоретические основы циклического кодирования, стоит отметить его свойства, обусловившие выбор циклических кодов.

Главное - это то, что циклические коды обладают высокой надежностью коррекции ошибок при весьма невысокой избыточности. Особенно они эффективны при обнаружении пакетов ошибок. Например, для кадра размером в 256 байт и контрольной последовательности в 16 бит (СRС-16) минимальное кодовое расстояние - 3, т.е. одна разрешенная кодовая комбинация отличается от другой, разрешенной же, минимум 3 битами, причем не любыми, а расположенными на вполне определенных местах во всей 2064-битовой последовательности. Вероятность появления нераспознаваемой ошибки, т.е. того, что вследствие ошибок одна разрешенная комбинация перейдет в другую, не превосходит 10-14. При уменьшении размера кадра или при увеличении длины контрольной последовательности минимальное кодовое расстояние растет, что еще более уменьшит вероятность появления нераспознаваемой ошибки.

Другое немаловажное свойство - простота кодирования: рекуррентный характер алгоритма при минимальном расходе вычислительных ресурсов. Причем, существуют по крайней мере два алгоритма, дающих идентичный результат. Один - битовый, модификация результата в котором производится по каждому биту. Его удобно реализовывать на аппаратном уровне с помощью сдвигового регистра. Другой - байтово-табличный, в котором модификация результата производится после приема/передачи целого байта. Этот алгоритм больше подходит для реализации на программном уровне, поскольку требует некоторого объема памяти для хранения таблиц.

Данные принципы циклического помехозащищенного кодирования с решающей обратной связью положены в основу .всех аппаратных и программных реализации наиболее широко распространенных протоколов коррекции ошибок MNP2/MNP3 и V.42ITU-T.

2. Протоколы коррекции ошибок

Строго говоря, противопоставление протокола. V.42ITU-T и МNР (the Microcom Networking Protocol) не вполне корректно. Дело в том, что Рекомендация V.42ITU-T - единый стандарт (по традиции называемый "Рекомендация"), описывающий все рассматриваемые протоколы коррекции ошибок. То, что в обиходе называется МNР2 и МNРЗ, есть соответственно байт-ориентированный и бит-ориентированный режимы протокола, описанного в Дополнении А к РекомендацииV.42, а то, что называется протоколом V.42, - протокол, описанный в основной части Рекомендации. Однако исторически сложилось так, что появление протоколов фирмы Microcom предшествовало выходу "Синей Книги" ITU-T с Рекомендацией V42. Поэтому в дальнейшем применяется сложившаяся терминология, которая хоть и не вполне корректна, зато проста и компактна.

То, что по недоразумению называют протоколом МNР4, протоколом на самом деле не является. Это не более, чем модифицированная реализация протоколов МNР2 и МNРЗ. Протокол коррекции ошибок определяет формат кадра, перечень допустимых типов кадров, логическую структуру кадра каждого типа и собственно протокол, т.е. порядок установки режима коррекции ошибок, выхода из режима и допустимого чередования кадров.

MNP-протоколы.

MNP (Microcom Network Protocol) - серия наиболее распространенных аппаратных протоколов, впервые реализованная на модемах фирмы Microcom. Эти протоколы обеспечивают автоматическую коррекцию ошибок и компрессию передаваемых данных.

Сейчас известны 10 протоколов:

MNP1. Протокол коррекции ошибок, использующий асинхронный полудуплексный метод передачи данных. Это самый простой из протоколов MNP.

MNP2. Протокол коррекции ошибок, использующий асинхронный дуплексный метод передачи данных.

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

Так как при асинхронной передаче используется десять бит на байт - восемь бит данных, стартовый бит и стоповый бит, а при синхронной только восемь, то в этом кроется возможность ускорить обмен данными на 20%.

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

Эффективность этого метода составляет около 20% по сравнению с простой передачей данных.

MNP5. Дополнительно к методам MNP4, MNP5 часто использует простой метод сжатия передаваемой информации. Символы, часто встречающиеся в передаваемом блоке, кодируются цепочками битов меньшей длины, чем редко встречающиеся символы. Дополнительно кодируются длинные цепочки одинаковых символов. Обычно при этом текстовые файлы сжимаются до 35% своей исходной длины. Вместе с 20% MNP4 это дает повышение эффективности до 50%.

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

MNP6. Дополнительно к методам протокола MNP5 автоматически переключается между дуплексным и полудуплексным методами передачи в зависимости от типа информации. Протокол MNP6 также обеспечивает совместимость с протоколом V.29.

MNP7. По сравнению с ранними протоколами использует более эффективный метод сжатия данных.

MNP9. Использует протокол V.32 и соответствующий метод работы, обеспечивающий совместимость с низкоскоростными модемами.

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

Все протоколы MNP совместимы между собой снизу вверх. При установлении связи происходит установка наивысшего возможного уровня MNP-протокола. Если же один из связывающихся модемов не поддерживает протокол MNP, то MNP-модем работает без MNP-протокола.

Режимы MNP-модемов.

MNP-модем обеспечивает следующие режимы передачи данных:

Протоколы V.42 и V.42bis.

Протокол с коррекцией ошибок и преобразованием асинхронный - синхронный. Протокол использует метод компрессии, при котором определяется частота появления отдельных символьных строк и происходит их замена на последовательности символов меньшей длины. Этот метод компрессии носит название Lempel-Ziv. Данный метод компрессии обеспечивает 50% сжатие текстовых файлов.

Вместе с 20% выигрышем от синхронного преобразования это увеличивает эффективность на 60%.

previous home next

Hosted by uCoz