Корректирующие коды. 
Радиотехнические системы

Как правило, используются обычные коды. Для них справедливо неравенство: 2″ > К (К — объем алфавита, п — разрядность кода).

Идея обнаружения ошибок принятой кодовой комбинации Ь_к состоит в том, что для передачи используются нс все N = 2″ возможных кодовых комбинаций b, а лишь часть: К < 2″ = N используемых К комбинаций Ь_х, Ь₂Ь_ъ,…, Ь_к) разрешенные, а остальные N — К возможных комбинаций (b_k+l, b_k+2,…, b_k+_n} запрещенные. Если при передаче вследствие действия помех разрешенная комбинация превращается в запрещенную, число которых в месте приема NК, из-за стирания символов может быть больше, чем на передаче, то тем самым и обнаруживаются ошибки или стирания символов. Если же совокупность ошибок превращает одну разрешенную комбинацию в другую разрешенную, то ошибки нс обнаруживаются. Различают системы с обнаружениями и системы с исправлением ошибок. Пространство принимаемых кодовых комбинаций Ь'_к разбивается на N'> N непересека;

ющихся областей. Если эти комбинации попадают в подпространство П* с номерами к = к +1, к + 2…N' (не сопоставляемыми разрешенным комбинациям), декодирование не производится и информация либо теряется, либо приобретается методом переспроса — посылкой сигнала, требующего повторения ошибочно принятой кодовой комбинации. Обнаружение ошибок кодовых комбинаций при избыточном кодировании можно сочетать с исправлением стираний символов, если, например, принимаемую кодовую комбинацию Ь'_к1, попавшую в запрещенную зону, отождествляют с гой из разрешенных, с когорой она совпадает в нестертых позициях. Если таких комбинаций будет несколько, то она отождествляется с любой из них либо относится к ошибочно принятым. В системах с исправлением ошибок запрещенные комбинации декодируются в соответствии с выбранным алгоритмом, причем пространство принимаемых комбинаций Ь'_к разбивается теперь на к непересекающихся пространств, приписываемых отдельным решениям. Такое разбиение стремятся выполнить так, чтобы при декодировании запрещенных комбинаций восстановить ту из разрешенных, которая могла бы быть передана с наибольшей вероятностью. В двоичном дискретном канале без памяти это та из разрешенных комбинаций, которая по Хеммингу ближе к принятой запрещенной комбинации, ибо в таком канале вероятность ошибки кратности q в кодовой комбинации длины п

при Р_п< 0,5 быстро убывает с ростом ее кратности.

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

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

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

В теории кодирования существует понятие совершенный и квазисовсршенный код. Код называют совершенным, если вся его избыточность расходуется на исправление ошибок заданной кратности q, т. е. такой код не исправляет ни одной ошибки более высокой кратности. Квазисовершенный код исправляет и некоторую часть ошибок кратности q + 1, но не исправляет ни одной ошибки более высокой кратности. Поскольку во многих каналах более вероятны ошибки минимальном кратности, то ясно, что понятие совершенного и квазисовершенного кода имеет право на существование. Квазисовершенный, а тем более совершенный коды являются также и «оптимальными».

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

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

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

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

Контрольные вопросы

• 1. Назовите основные понятия теории информации.
• 2. Назовите основные свойства энтропии.
• 3. Что такое «взаимная информация»?
• 4. Что такое кодирование?
• 5. Дайте классификацию кодов.
• 6. Нарисуйте сигналы кодовой последовательности для разной позиционности кодов.
• 7. Что такое кодовые деревья?
• 8. Что такое примитивный равномерный код?
• 9. Что такое корректирующие коды?