Коды для обнаружения ошибок

Помехоустойчивое кодирование

Помехи

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

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

Построение помехоустойчивых кодов в основном связано с добавлением к исходной комбинации из k информационных символов r контрольных символов. Так как закодированная комбинация будет составлять n = k + r символов, то такие коды часто называют (n, k)-кодами.

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

Коды для обнаружения ошибок

Один из самых старых, простых и используемых кодов для обнаружения ошибок образуется путем добавления к передаваемой двоичной комбинации, состоящей из k информационных символов (битов), одного контрольного символа (0 или 1), так, чтобы общее число единиц в передаваемой комбинации было четным. Такой код называется кодом с проверкой на четность и позволяет обнаруживать одиночные ошибки. Например, пусть даны две комбинации 11011 и 11100, для которых нужно построить код с проверкой на четность. Первая комбинация имеет четное, а вторая – нечетное число единиц. Поэтому к первой комбинации добавляется 0, а ко второй – 1. В результате получаем коды 110110 и 111001. Если предположить, что в результате ошибок вместо указанных комбинаций были получены 111110 и 110001, то проверка на четность их обнаружит, так как контрольные символы у принятых комбинаций (если они правильные) должны быть 1 и 0 соответственно.

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

,

где n – общее число символов, m – число единиц в кодовой комбинации. Например, в таблице 7.1 приведены коды с двумя единицами из пяти (число кодируемых комбинаций равно ). Этот код позволяет обнаруживать любые одиночные ошибки и часть многократных ошибок. Однако с помощью этого кода не обнаруживаются ошибки смещения, когда одна единица переходит в ноль и один ноль переходит в единицу или два ноля и две единицы меняются на обратные символы и т. д.

Таблица 7.1

Код с двумя единицами из пяти

Часто также используется корреляционный код (код с удвоением). При его построении 1 преобразуется в 10, а 0 – в 01. Тогда, например, вместо комбинации 1010011 будет передаваться 10011001011010. Ошибка обнаруживается в том случае, если в парных элементах будут одинаковые символы 00 или 11 (вместо 01 и 10).

Еще одним простым кодом является инверсный код. В этом случае к исходной комбинации добавляется такая же комбинация по длине. В линию посылается удвоенное число символов. Если в исходной комбинации четное число единиц, то добавляемая комбинация повторяет исходную комбинацию, если нечетное – то добавляемая комбинация является инверсной относительно исходной. Например, инверсный код для комбинации 11011 будет иметь вид 1101111011 (контрольная комбинация 11011), а для комбинации 11100 – 1110000011 (контрольная комбинация 00011). Прием инверсного кода осуществляется в два этапа. На первом этапе суммируются единицы в первой основной группе символов. Если число единиц четное, то контрольные символы принимаются без изменения, если нечетное, то контрольные символы инвертируются. На втором этапе контрольные символы суммируются с информационными символами по модулю два. Нулевая сумма говорит об отсутствии ошибок. При ненулевой сумме, принятая комбинация считается ошибочной. Обнаруживающие способности данного кода достаточно велики. Данный код обнаруживает практически любые ошибки, кроме редких ошибок смещения, которые одновременно происходят как среди информационных символов, так и среди соответствующих контрольных.

Для снижения ошибок при кодировании угла поворота некоторого объекта (а также и в других случаях) можно использовать код Грея. Пример кода Грея приведен в таблице 7.2. Разряды в коде Грея не имеют постоянного веса. Вес k -го разряда определяется следующим образом:

.

При этом все нечетные единицы, считая слева направо, имеют положительный вес, а все четные единицы отрицательный. Например:

.

Таблица 7.2

Пример кода Грея

Поиск по сайту: