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

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

Более эффективно используются дискретные каналы при применении корректирующих кодов. В однонаправленных системах это должны быть коды, исправляющие ошибки. Широкое распространение на практике получили двоичные корректирующие коды, т.е. коды, при формировании которых используются только два типа элементов:

0 и 1. Только такие коды и будут рассматриваться в данной главе.

Построение корректирующих кодов. Каждому символу исходного алфавита сообщений объема Л/а поставим в соответствие л-элементную двоичную последовательность - кодовую комбинацию. Возможное (общее) число последовательностей длины п составляет Л/о = 2 , причем должно соблюдаться условие Л/о > Л/а.

Если Л/о = Л/а, то все возможные последовательности л-элемент-ного кода используются для передачи или, как говорят, являются разрешенными. Полученный таким образом код называется простым.

Пример 12.1. Для передачи сообщений, число которых равно восьми (Л/а = 8), используется трехэлементный код. Число кодовых комбинаций, которое можно при этом получить. Л/о = 2 = 8. Из табл. 12.1 видно, что комбинация под номером О отличается от комбинации

1 только в одной позиции. Следовательно, если при передаче комбинации ООО произойдет ошибка в третьем элементе, то получим комбинацию 001.

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

01 10

поэтому расстояние Хемминга cf = 2. Иначе его определяют как вес суммы по модулю два (® - условное обозначение суммы) этих кодовых комбинаций. Весом W кодовой комбинации называется число входящих в нее ненулевых элементов.

Таблица 12.1. Кодовые комбинации трехэлементного кода

Перебрав все возможные пары кодовых комбинаций, можно найти минимальное хеммингово расстояние, которое принято называть кодовым и обозначать do- Для примера 12.1 кодовое расстояние do = 1. Рассмотренный в примере код простой. Любая ошибка (даже одиночная!) при использовании такого кода приведет к тому, что переданная разрешенная кодовая комбинация перейдет в другую разрешенную. Таким образом, простой код не способен обнаруживать и тем более исправлять ошибки и имеет do = 1.

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

Пример 12.2. Алфавит передаваемых сообщений Л/а = 2. Выберем из числа комбинаций, представленных в табл. 12.1, две. Очевидно, что ими должны быть комбинации ООО, 111 или 001 и 110 и т.д. Кодовое расстояние do = 3. Ошибки кратности один или два превращают любую разрешенную кодовую комбинацию в запрещенную. Следовательно, максимальная кратность обнаруживаемых таким образом ошибок равна двум ((Ьош = 2).

Нетрудно догадаться, что минимальное кодовое расстояние do и гарантированно обнаруживаемая кратность ошибок связаны соотношением to.ow = do - 1.

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

Связь между do и кратностью исправляемых ошибок определяется выражением t ош = (сЬ/2) - 1 для четного do и ош = = (do - 1 )/2 для нечетного do.

Итак, задача получения кода с заданной корректирующей способностью сводится к задаче выбора (путем перебора) из Л/о = 2 кодовых комбинаций Л/а комбинаций с требуемым кодовым расстоянием do- Если п достаточно мало, то такой перебор не представляет особого труда. При больших п перебор может оказаться непосильным даже для современной ЭВМ, поэтому на практике

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

Блочные

Непрерывные

Равномерные Неравномерные

Разделимые

Неразделимые

Систематические Несистематические

Рис. 12.1. Классификация корректирующих кодов

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

Классификация корректирующих кодов. Помехоустойчивые или корректирующие коды (рис. 12.1) делятся на блочные и непрерывные. К блочным относятся коды, в которых каждому символу алфавита сообщений соответствует блок (кодовая комбинация) из n(i) элементов, где /- номер сообщения. Если n(i) = п, т.е. длина блока постоянна и не зависит от номера сообщения, то код называется равномерным. Такие коды чаще применяются на практике. Если длина блока зависит от номера сообщения, то блочный код называется неравномерным. Примером неравномерного кода служит код Морзе. В непрерывных кодах передаваемая информационная последовательность не разделяется на блоки, а проверочные элементы размещаются в определенном порядке между информационными.

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

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

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