Анализ способов защиты от ошибок
Обнаружение ошибок
Простейшим способом обнаружения ошибок является контроль по четности. Обычно контролируется передача блока данных (М бит). Этому блоку ставится в соответствие кодовое слово длиной N бит, причем N>M. Избыточность кода характеризуется величиной 1-M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение, тем выше вероятность обнаружения ошибки, но и выше избыточность). При передаче информации она кодируется таким образом, чтобы с одной стороны характеризовать ее минимальным числом символов, а с другой минимизировать вероятность ошибки при декодировании получателем. Для выбора типа кодирования важную роль играет так называемое расстояние Хэмминга. Пусть А и Б две двоичные кодовые последовательности равной длины. Расстояние Хэмминга между двумя этими кодовыми последовательностями равно числу символов, которыми они отличаются. Например, расстояние Хэмминга между кодами 00111 и 10101 равно 2.
Принципы помехоустойчивого кодирования
В теории помехоустойчивого кодирования важным является вопрос об использовании избыточности для корректирования возникающих при передаче ошибок. Здесь удобно рас смотреть блочные коды, в которых всегда имеется возможность выделить отдельные кодовые комбинации. Для равномерных кодов, которые в дальнейшем только и будут изучаться, число возможных комбинаций равно M=2n, где n - значность кода.
В обычном некорректирующем коде без избыточности, на пример, в коде Бодо, число комбинаций М выбирается равным числу сообщений алфавита источника М0, и все комбинации используются для передачи информации. Корректирующие коды строятся так, чтобы число комбинаций М превышало число комбинаций источника М0. Однако в этом случае лишь М0 комбинаций из общего числа используются для передачи информации. Эти комбинации называются разрешенными, а остальные M - М0комбинации носят название запрещенных. На приемном конце в декодирующем устройстве известно, какие комбинации являются разрешенными и какие - запрещенными. Поэтому если переданная разрешенная комбинация в результате ошибки преобразуется в некоторую запрещенную комбинацию, то такая ошибка будет обнаружена, а при определенных условиях - исправлена. Естественно, что ошибки, приводящие к образованию другой разрешенной комбинации, не обнаруживаются.
Различие между комбинациями равномерного кода принято характеризовать расстоянием, равным числу символов, которыми отличаются комбинации одна от другой. Расстояние между двумя комбинациями и определяется количеством единиц в сумме этих комбинаций по модулю два.
Методы обнаружения ошибок
Большая часть протоколов канального уровня выполняет только одну задачу - обнаружение ошибок, считая, что корректировать ошибки, то есть повторно передавать данные, должны протоколы верхних уровней. Однако существуют протоколы канального уровня, которые самостоятельно решают задачу восстановления искаженных или потерянных кадров.
Но нельзя считать, что один протокол лучше другого потому, что он восстанавливает ошибочные кадры, а другой протокол - нет. Каждый протокол должен работать в тех условиях, для которых он разработан.
Все методы обнаружения ошибок основаны на передаче служебной избыточной информации, по которой можно судить с некоторой степенью вероятности о достоверности принятых данных. Эту служебную информацию принято называть контрольной суммой. Контрольная сумма вычисляется как функция от основной информации, причем необязательно только путем суммирования. Принимающая сторона повторно вычисляет контрольную сумму кадра по известному алгоритму и в случае ее совпадения делает вывод о том, что данные были переданы корректно.
Коды Хэмминга
Код Хэмминга представляет собой блочный код, который позволяет выявить и исправить ошибочно переданный бит в пределах переданного блока. Обычно код Хэмминга характеризуется двумя целыми числами, например, (11,7) используемый при передаче 7-битных ASCII-кодов. Такая запись говорит, что при передаче 7-битного кода используется 4 контрольных бита (7+4=11). При этом предполагается, что имела место ошибка в одном бите и что ошибка в двух или более битах существенно менее вероятна. С учетом этого исправление ошибки осуществляется с определенной вероятностью. Например, пусть возможны следующие правильные коды (все они, кроме первого и последнего, отстоят друг от друга на расстояние 4:
При получении кода 00000111 не трудно предположить, что правильное значение полученного кода равно 00001111. Другие коды отстоят от полученного на большее расстояние Хэмминга.
Циклические коды
К числу эффективных кодов, обнаруживающих одиночные, кратные ошибки и пачки ошибок, относятся циклические коды (CRC - Cyclic Redundance Code). Они высоконадежны и могут применяться при блочной синхронизации, при которой выделение, например, бита нечетности, было бы затруднительно.
Один из вариантов циклического кодирования заключается в умножении исходного кода на образующий полином g(x), а декодирование - в делении на g(x). Если остаток от деления не равен нулю, то произошла ошибка. Сигнал об ошибке поступает на передатчик, что вызывает повторную передачу.
Образующий полином есть двоичное представление одного из простых множителей, на которые раскладывается число Xn-1, где Xn обозначает единицу в n-м разряде,n равно числу разрядов кодовой группы.
Логический код 4В/5В
Логический код 4В/5В, используемый в технологиях FDDI и Fast Ethernet, заменяет исходные символы длиной в 4 бита на символы длиной в 5 бит. Так как результирующие символы содержат избыточные биты, то общее количество битовых комбинаций в них больше, чем в исходных. Так, в коде 4В/5В результирующие символы могут содержать 32 битовых комбинации, в то время как исходные символы - только 16. Поэтому в результирующем коде можно отобрать 16 таких комбинаций, которые не содержат большого количества нулей, а остальные считать запрещенными кодами (code violation).
Скремблирование
Это обратимое преобразование цифрового потока без изменения скорости передачи с целью получения свойств случайной последовательности. После скремблирования появление «1» и «0» в выходной последовательности равновероятны.
Линейные блочные коды
Линейные блочные коды - это класс кодов с контролем четности, которые описываются парой чисел (n, k). Блок из k символов сообщения назовем вектором сообщения, а блок из n символов кодового слова - кодовым вектором. В процессе кодирования блок из k символов сообщения преобразуется в больший блок из n символов кодового слова, образованного с использованием элементов данного алфавита. Если алфавит состоит только из двух элементов 0 и 1, код является двоичным и включает двоичные разряды, т.е. биты.
Набор из 2k последовательностей сообщения, которые формируются из k - битовые сообщений, называется k -кортежами, или последовательностями k цифр, а из 2n последовательности могут формироваться n - битовые блоки, которые называются п-кортежами. Процедура кодирования сопоставляет с каждым из 2k k -кортежей сообщения один из 2n п-кортежей. Блочные коды представляют собой взаимно однозначное соответствие, отсюда следует, что 2k k -кортежей сообщения однозначно отображаются во множество из 2n п-кортежей кодовых слов. Отображение производится согласно таблице соответствия. Для линейных кодов преобразование отображения является также линейным.
локальный вычислительный сеть