Принципы коррекции ошибок. Не вдаваясь глубоко в теорию кодирования и помехозащищенности передачи информации, можно лишь констатировать, что: избыточность - единственный реальный базис обнаружения и коррекции ошибок. Избыточность в широком смысле.
Она может быть "последовательной", в случаях применения любого из методов кодирования, т.е. передача дополнительной по отношению к "полезной" информации. Либо "параллельной", в случаях как использования параллельных каналов связи (возможно, различной физической природы), так и применения информационной обратной связи, т.е. возврат (используя дуплексный канал) принятой информации для анализа передатчиком ее правильности. Применение кодирования с решающей обратной связью - это пример комбинированной, "последовательно-параллельной" избыточности.
Степень избыточности определяет глубину и надежность обнаружения ошибок. Представляется очевидным, что чем больше дополнительной информации будет передано, тем большее количество ошибок и с большей достоверностью может быть обнаружено и даже, возможно, исправлено. Но, в то же время, тем меньше доля полезной информации в общем потоке данных и - тем меньше эффективная скорость приема/передачи и, в конечном счете, пропускная способность канала.
Выбор процедуры коррекции ошибок, таким образом, можно рассматривать как оптимизационную задачу, критерием которой является минимизация накладных расходов при заданной надежности приема/передачи информации.
Физическая природа канала передачи информации - коммутируемая телефонная сеть - определяет те факторы, вес которых оказывается наиболее значим при решении поставленной оптимизационной задачи. Отсутствие дублирования канала (по крайней мере на абонентском участке линии) исключает из рассмотрения физическое параллельное дублирование. В то же время, применение обратной связи вполне допустимо вследствие того, что канал дуплексный.
Фактор "стоимость трафика" заставляет с большой осторожностью относиться к таким методам коррекции ошибок, как многократное дублирование передаваемой информации с мажоритарным выбором или применение информационной обратной связи. Объем передаваемой информации в первом случае возрастает как минимум втрое, а то и более. Во втором случае, гонять одну и ту же информацию в полном объеме в обе стороны только для обнаружения факта наличия ошибки с последующим повтором представляется также излишне расточительным.
Третьим фактором, оказывающим огромное влияние на выбор методов коррекции ошибок, является помеховая обстановка в канале передачи данных. А она такова (особенно в "отчих пределах"), что ограничиться простым контролем четности, чего бывает достаточно для локальных сетей, - не кажется удачным решением. Представляется на первый взгляд, что применение симплексного корректирующего кодирования - неплохое решение поставленной задачи. Это кодирование позволяет не только обнаруживать ошибки, но и указывать на их местоположение, т.е. исправлять их, что позволяет отказаться от обратной связи. Однако, степень избыточности при этом весьма высока: объем дополнительной информации сравним с объемом "полезной".
Для исправления только одиночной ошибки необходимы по крайней мере три дополнительных бита на байт. И этот объем стремительно возрастает с ростом глубины коррекции ошибок, что в конечном счете может свести выигрыш от высокой надежности и отсутствия повторов к глобальному и стабильному проигрышу в стоимости "излишнего" трафика, который, к тому же, будет совершенно индифферентен к помеховой обстановке (возможно, неплохой).
Разумным компромиссом было сочтено применение циклического помехозащищенного кодирования с решающей обратной связью. Суть этого метода состоит в следующем. Вся "полезная" информация разбивается на "порции" - кадры. Передача каждого кадра завершается передачей специальной контрольной последовательности кадра, подсчитанной по некоему, заранее определенному алгоритму. Этот рекуррентный алгоритм в процессе выдачи кадра модифицирует контрольную последовательность с помощью очередного выдаваемого байта. Удаленная сторона, принимая кадр, также подсчитывает контрольную последовательность по известному алгоритму.
По окончании приема кадра производится сравнение подсчитанной контрольной последовательности с принятым в конце кадра ее значением. По результатам сравнения приемник решает гамлетовский вопрос: быть ли данному кадру, или его следует повторить. Результат решения этого вопроса приемник сообщает передатчику посредством некоей "квитанции". Отсюда другое название этого метода: метод автоматического повтора запроса (ARQ, Automatic Repeat reQuest).
Основная ответственность за надежность обнаружения ошибок при этом методе лежит на алгоритме вычисления контрольной последовательности кадра. Здесь используется аппарат циклического избыточного контроля (CRC, Cyclic Redundancy Check). Циклическое кодирование базируется на математической теории групп, алгебре многочленов и теории колец. Оставив для другого раза теоретические основы циклического кодирования, стоит отметить его свойства, обусловившие выбор циклических кодов.
Главное - это то, что циклические коды обладают высокой надежностью коррекции ошибок при весьма невысокой избыточности. Особенно они эффективны при обнаружении пакетов ошибок. Например, для кадра размером в 256 байт и контрольной последовательности в 16 бит (СRС-16) минимальное кодовое расстояние - 3, т.е. одна разрешенная кодовая комбинация отличается от другой, разрешенной же, минимум 3 битами, причем не любыми, а расположенными на вполне определенных местах во всей 2064-битовой последовательности. Вероятность появления нераспознаваемой ошибки, т.е. того, что вследствие ошибок одна разрешенная комбинация перейдет в другую, не превосходит 10-14. При уменьшении размера кадра или при увеличении длины контрольной последовательности минимальное кодовое расстояние растет, что еще более уменьшит вероятность появления нераспознаваемой ошибки.
Другое немаловажное свойство - простота кодирования: рекуррентный характер алгоритма при минимальном расходе вычислительных ресурсов. Причем, существуют по крайней мере два алгоритма, дающих идентичный результат. Один - битовый, модификация результата в котором производится по каждому биту. Его удобно реализовывать на аппаратном уровне с помощью сдвигового регистра. Другой - байтово-табличный, в котором модификация результата производится после приема/передачи целого байта. Этот алгоритм больше подходит для реализации на программном уровне, поскольку требует некоторого объема памяти для хранения таблиц.
Данные принципы циклического помехозащищенного кодирования с решающей обратной связью положены в основу всех аппаратных и программных реализации наиболее широко распространенных протоколов коррекции ошибок MNP2/MNP3 и V.42ITU-T.