Общие понятия и определения. Цели кодирования

1 2 3 4 5 6 7

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

Лекция 7.Помехоустойчивые коды

Учебные вопросы:

Общие понятия и определения. Цели кодирования

Оптимальное кодирование

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

Коды с обнаружением ошибок

Код Грея.

Корректирующие коды

Общие понятия и определения. Цели кодирования

Рассмотрим общие принципы кодирования информации. Они справедливы как для систем связи (передача информации в пространстве), так и для систем хранения информации (передача информации во времени). В системах хранения информации линией связи считается среда, в которой хранится информация.

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

Рассмотрим структурную схему системы передачи информации.

Рис. 2.1 - Общая структурная схема системы передачи информации:

ИИ - источник информации; ЛС - линия связи; КИ - кодер источника; ИП - источник помех; КК - кодер канала; ДМ - демодулятор; М - модулятор; ДИ - декодер источника; ДК - декодер канала; П - получатель информации

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

При большом объеме алфавита (источника сообщений) часто прибегают к представлению букв в другом алфавите с меньшим числом букв, которые называют символами. (Пример: код Морзе.) Эта операция - по сути, также кодирование, только в узком смысле. Например, «а» заменим кодом ·-; «б» - - ·- · и т.д., то есть, получим новый алфавит из двух символов - точки и тире.

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

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

Кодер источника (КИ) имеет целью обеспечить такое кодирование, при котором путем устранения избыточности существенно снижается среднее число символов, требующихся на букву сообщения. При отсутствии помех это непосредственно дает выигрыш во времени передачи (системы связи) или в объеме запоминающего устройства (системы хранения), то есть повышает эффективность системы. Поэтому такое кодирование получило название эффективного или оптимального.При наличии помех в канале связи такое кодирование является как бы сжатием сигнала, то есть подготовкой его для дальнейшего преобразования (архивирование информации в ЭВМ).

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

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

Итак, выбор кодирующих и декодирующих устройств зависит от статистических свойств источника сообщений, а также от уровня и характера помех в канале связи:

если избыточность источника сообщений мала, и помехи в канале связи практически отсутствуют, то введение как кодера источника, так и кодера канала нецелесообразно;

когда избыточность источника сообщений высока, а помехи весьма малы, целесообразно введение кодера источника;

когда избыточность источника мала, а помехи велики, целесообразно введение кодера канала;

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

После кодера канала (КК) сигнал поступает в модулятор (М). На выходе модулятора сигнал х подготовлен к передаче по конкретной линии связи.

В линии связи (ЛС) на сигнал накладываются помехи (из источника помех - ИП).

В демодулятор (ДМ) из канала связи приходит сигнал у, искаженный шумом. В демодуляторе сигналы декодируются в символы.

В декодере канала (ДК) и декодере источника (ДИ) происходит преобразование символов в сообщение. Сообщение выдается получателю (П).

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

Многие годы в телеграфии применялся двоичный пятизначный код Ж. Бодо, предложенный им в 1874 г. Пятизначный двоичный код позволяет получить 32 кодовые комбинации, а необходимо передавать 56 комбинаций. Используется двухрегистровый режим работы. Каждому регистру (нижнему и верхнему) выделена специальная кодовая комбинация (адрес регистра). Передача адреса предшествует передаче величин, принадлежащих этому регистру. В конце ХIХ века американский инженер Дж. Муррей предложил двоичный пятизначный код, который отличался от кода Бодо тем, что наиболее часто встречающиеся буквы и знаки кодировались комбинациями с меньшим числом ненулевых разрядов. Такой код уменьшал нагрузку на телеграфную аппаратуру и повышал надежность ее работы.

В 1931 г. Международный консультативный комитет по телеграфии и телефонии (МККТТ) принял стандартный код № 1, в основу которого положен код Бодо. В 1932 г. принят стандартный код № 2, в основу которого положен код Муррея. Код № 2 широко использовался в буквопечатающих телеграфных аппаратах (телетайпах).

С развитием вычислительной техники по каналам связи стали производить обмен данными между ЭВМ. Возникла необходимость введения новых служебных символов, отсутствующих в коде № 2. Был введен новый семиразрядный код КОИ-7 (рис. 2.2), а в последствии - код КОИ-8 (рис. 2.3).