Первичные коды

Код Морзе

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

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

Первичный код МТК-2

Пятибитный код МТК-2 позволяет образовывать N = 2⁵ = 32 кодовых комбинаций. Для передачи букв, цифр и знаков препинания этого количества кодовых комбинаций недостаточно. Поэтому код является трехрегистровым. Это означает, что каждой кодовой комбинации соответствует три знака из таблиц, соответствующих русскому, латинскому и цифровому тексту. Так, например, для передачи цифрового текста, после буквенного, необходимо нажать клавишу «Циф».

Использование рассматриваемого кода в системах передачи данных практически не эффективно, так как отсутствуют функциональные символы «Квитанция», «Ждите», «Понял» и др. Однако, в ряде случаев вместо этих символов передаются комбинации, которые не встречаются в смысловом тексте. Например, для обозначения начала текста используется сочетание знаков ЗЦЗЦ.

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

Первичный семибитный код КОИ-7

На смену коду МТК-2 был разработан и в настоящее время широко применяется при передаче данных семибитный международный код №5 (МТК-5). На его основе в 1974 г. разработан семибитный код КОИ-7. Он состоит из 3-х таблиц:

кодовой таблицы КОИ-7 Н₀;

кодовой таблицы КОИ-7 Н₁;

кодовой таблицы КОИ-7 С₁.

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

Недостаток кода КОИ-7 состоит в том, что он является регистровым, т.е. все три таблицы выбираются с помощью символов «ВХ» (выбор КОИ-7 Н₀), «ВЫХ» (КОИ-7 Н₁), «АР2» (КОИ-7 С₁). Это приводит к снижению помехоустойчивости. Поэтому были разработаны безрегистровые первичные восьмиэлементные коды для передачи данных и их обработки - КОИ-8 и ДКОИ (двоичный код обмена данными). Оба кода содержат один и тот же набор символов, но различаются расположением в кодовых таблицах размерностью 16 строк на 16 столбцов (всего 256 кодовых позиций).

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

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

Декодирование состоит в восстановлении сообщения по принимаемым кодовым символам. Устройства, осуществляющие кодирование и декодирование, называют соответственно кодером и декодером. Как правило, кодер и декодер выполняются физически в одном устройстве, называемым кодеком.

Рассмотрим основные принципы построения корректирующих кодов или помехоустойчивого кодирования.

Напомним, что расстоянием Хэмминга между двумя кодовыми n-последовательностями, b_i и b_j, которое будем далее обозначать d(i;j), является число разрядов, в которых символы этих последовательностей не совпадают.

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

Рассматривая все разрешенные кодовые комбинации и определяя кодовые расстояния между каждой парой, можно найти наименьшее из них d = min d(i;j), где минимум берется по всем парам разрешенных комбинаций. Это минимальное кодовое расстояние является важным параметром кода. Очевидно, что для простого кода d=1.

Обнаруживающая способность кода характеризуется следующей теоремой. Если код имеет d>1 и используется декодирование по методу обнаружения ошибок, то все ошибки кратностью q<d обнаруживаются. Что же касается ошибок кратностью q>d, то одни из них обнаруживаются, а другие нет.

Исправляющая способность кода при этом правиле декодирования определяется следующей теоремой. Если код имеет d>2 и используется декодирование с исправлением ошибок по наименьшему расстоянию, то все ошибки кратностью q<d/2 исправляются. Что же касается ошибок большей кратности, то одни из них исправляются, а другие нет.

Задача кодирования состоит в выборе кода, обладающего максимально достижимым d. Впрочем, такая формулировка задачи неполна. Увеличивая длину кода n и сохраняя число кодовых комбинаций М, можно получить сколь угодно большое значение d. Но такое «решение» задачи не представляет интереса, так как с увеличением n уменьшается возможная скорость передачи информации от источника.

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

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

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

Таким образом, применение достаточно эффективных (а значит, и достаточно длинных) кодов при табличном методе кодирования и декодирования технически невозможно.

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