Глава 3. количественная оценка информации 8 страница

Кодирование очередного знака z_i, выдаваемого источником информации 7, осуществляется посредством подачи через элементы И импульса на ί-ю горизонтальную шину шифраторов от импульсного источника питания 6. При этом в регистр сдвига 3 записывается кодовая комбинация, соответствующая знаку z_i, а в регистр 4 — единица, несущая информацию о конце этой кодовой комбинации. Продвигающими импульсами генератора 5 записанная в регистре 3 кодовая комбинация символ за символом выводится в канал связи. Посредством того же генератора сдвигается и единица в регистре 4. Соответствующий ей импульс появится на выходе регистра в тот момент, когда из регистра 3 будет выведен последний символ кодовой комбинации. Этот импульс используется как управляющий для перехода к кодированию следующего знака.

На рис. 5.18 приведена схема декодирующего устройства, разработанного Гильбертом и Муром.

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

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

За каждым тактовым импульсом следует импульс с источника 6, питающего матричный дешифратор 1. Последний построен в соответствии с комбинациями используемого кода, в котором со стороны старшего разряда приписана лишняя единица. При поступлении в регистр последнего символа декодируемой первой кодовой комбинации очередной импульс от источника 6 приводит к появлению импульса напряжения на выходе i-й шине дешифратора, что соответствует приему знака z_i. Через схему ИЛИ этот импульс записывается в промежуточную ячейку памяти 4 и при считывании очередным импульсом с генератора сброса 3 используется для установления всех ячеек регистра в исходное состояние (в первой ячейке 1, в остальных 0). Далее поступает следующая кодовая комбинация и процесс декодирования повторяется.

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

1. В чем преимущества использования двоичных кодов при передаче, хранении и обработке информации?

2. С какой целью применяется код Грея?

3. В чем сущность метода поразрядного уравновешивания?

4. Сравните различные типы аналого-цифровых преобразователей по быстродействию и точности.

5. Что понимают под криптографическим закрытием информации?

6. Какие требования предъявляются к современным методам криптографического закрытия информации?

7. Назовите основной недостаток шифрования гаммированием.

8. В чем суть эффективного статистического кодирования?

9. Сформулируйте и поясните основную теорему Шеннона о кодировании для канала без помех.

10. Каковы причины эффективности кодирования длинных последовательных знаков?

11. За счет чего при эффективном кодировании уменьшается средняя длина кодовой комбинации?

12. До какого предела может быть уменьшена средняя длина кодовой комбинации при эффективном кодировании?

13. В чем преимущество методики построения эффективного кода, предложенной Хаффманом, по сравнению с методикой Шеннона — Фано?

14. Какому основному условию должны удовлетворить эффективные коды?

15. Перечислите сложности, возникающие при использовании эффективных кодов.

ГЛАВА 6. КОДИРОВАНИЕ ИНФОРМАЦИИ ПРИ ПЕРЕДАЧЕ

ПО ДИСКРЕТНОМУ КАНАЛУ С ПОМЕХАМИ

§ 6.1. ОСНОВНАЯ ТЕОРЕМА ШЕННОНА О КОДИРОВАНИИ

ДЛЯ КАНАЛА С ПОМЕХАМИ

Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Шенноном и сформулированных им в виде теоремы:

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

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

Хотя доказательство этой теоремы, предложенной Шенноном, в дальнейшем подвергалось более глубокому и строгому математическому представлению [34], идея его осталась неизменной. Доказывается только существование искомого способа кодирования, для чего находят среднюю вероятность ошибки по всем возможным способам кодирования и показывают, что она может быть сделана сколь угодно малой. При этом существует хотя бы один способ кодирования, для которого вероятность ошибки меньше средней.

Доказательство теоремы. Будем кодировать сообщения такой длительности Т, чтобы была справедлива теорема об асимптотической вероятности длинных последовательностей букв (см. § 4.2). Тогда при заданной производительности источника сообщений Ī(Ζ) кодированию подлежат только Ν(z) типичных последовательностей, причем:

Ориентируясь на равновероятное поступление в канал любого из m различных элементарных входных сигналов и отсутствие между ними статистической связи на входе канала, можно сформировать N(u) равновероятных последовательностей длительности Т, причем

Если условие существования способа кодирования выполняется, т. е.

то

и

Следовательно, существует способов кодирования, при которых множеству сообщений N(z) случайным образом ставятся в соответствие различные подмножества разрешенных последовательностей элементарных сигналов из множества N(u).

При равновероятном выборе последовательностей элементарных сигналов из множества N(u) для любого подмножества разрешенных последовательностей вероятность ρ того, что конкретная последовательность будет отнесена к числу разрешенных,

В результате действия помех при получении на выходе канала сигналов v остается неопределенность относительно переданных последовательностей u. Она характеризуется условной энтропией H_v(U) и эквивалентна неопределенности выбора из последовательностей. Конкретная последовательность может быть идентифицирована со сколь угодно малой вероятностью ошибки, если среди N_v(U) последовательностей она единственная разрешенная. Отсюда принципиальная необходимость введения избыточности в кодируемые последовательности для компенсации потерь информации в канале из-за действия помех.

Определим среднюю по всем возможным способам кодирования вероятность того, что ни одна из N_v(U)-1 последовательностей не является разрешенной:

Так как (1 — р)<1, то увеличение степени на единицу приведет к неравенству

Правую часть неравенства разложим в ряд

Покажем, что члены ряда убывают по абсолютному значению. Для этого выразим ρ через Nv(U) [14].

Используя соотношение (6.3), запишем

или

где Выражение (6.4) теперь можно привести к виду

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

Тогда для средней вероятности ошибочного приема типичной последовательности _ош запишем:

Вероятность _ош при стремится к нулю. Принимая во внимание, что при неограниченном увеличении Т вероятность появления на входе канала нетипичной последовательности в соответствии с теоремой об асимптотической равновероятности также стремится к нулю, справедливо утверждение: при любом заданном η>0 можно выбрать такое T, при котором средняя вероятность ошибочной передачи информации по каналу будет меньше произвольно малого положительного числа.

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

С доказательством второй части рассматриваемой теоремы (обратного утверждения) можно ознакомиться в [36].

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

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

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

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

§ 6.2. РАЗНОВИДНОСТИ ПОМЕХОУСТОЙЧИВЫХ КОДОВ

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

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

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

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

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

Алгебраические коды можно подразделить на два больших класса: блоковые и непрерывные.

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

Блоковый код называют равномерным, если n остается постоянным для всех букв сообщения.

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

При кодировании неразделимыми кодами разделить символы выходной последовательности на информационные и проверочные невозможно.

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

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

§ 6.3. БЛОКОВЫЕ КОДЫ

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

Всего может быть 2^k различных входных и 2ⁿ различных выходных последовательностей. Из общего числа 2ⁿ выходных последовательностей только 2^k последовательностей соответствуют входным. Назовем их разрешенными кодовыми комбинациями. Остальные 2ⁿ — 2^k возможных выходных последовательностей для передачи не используются. Назовем их запрещенными комбинациями.

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

случаев безошибочной передачи (на рис. 6.1 обозначены жирными линиями);

случаев перехода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам (на рис. 6.1 обозначены пунктирными линиями);

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

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

Пример 6.1. Определим обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (n = k+1). Общее число выходных последовательностей составляет 2^k+1, т.е. вдвое больше общего числа кодируемых входных последовательностей. За подмножество разрешенных кодовых комбинаций можно принять, например, подмножество 2^k комбинаций, содержащих четное число единиц (или нулей).

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

Рассмотрим случай исправления ошибок.

Любой метод декодирования можно рассматривать как правило разбиения всего множества запрещенных кодовых комбинаций на непересекающихся подмножеств M_ί, каждое из которых ставится в соответствие одной из разрешенных комбинаций. При получении запрещенной комбинации, принадлежащей подмножеству M_ί, принимают решение, что передавалась разрешенная комбинация А_i. Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из А_i, т. е. случаях.

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

Способ разбиения на подмножества зависит от того, какие ошибки должны исправляться данным конкретным кодом.

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

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

Кратностью ошибки называют количество искаженных символов в кодовой комбинации.

При взаимно независимых ошибках вероятность искажения любых r символов в n-разрядной кодовой комбинации

Если учесть, что р«1, то в этом случае наиболее вероятны ошибки низшей кратности. Их и следует обнаруживать и исправлять в первую очередь.

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

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

Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2. Например:

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

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

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

Очевидно, что при d =1 все кодовые комбинации являются разрешенными.

Например, при n = 3 разрешенные комбинации образуют следующее множество: 000, 001, 010, 011, 100, 101, 110, 111.

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

Если d = 2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию. Например, подмножество разрешенных кодовых комбинаций может быть образовано по принципу четности в них числа единиц, как это приведено ниже для n = 3:

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

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

Для исправления одиночной ошибки каждой разрешенной кодовой комбинации необходимо сопоставить подмножество запрещенных кодовых комбинаций. Чтобы эти подмножества не пересекались, хэммингово расстояние между разрешенными кодовыми комбинациями должно быть не менее трех. При n = 3 за разрешенные комбинации можно, например, принять 000 или 111. Тогда разрешенной комбинации 000 необходимо приписать подмножество запрещенных кодовых комбинаций 001, 010, 100, образующихся в результате возникновения единичной ошибки в комбинации 000.

Подобным же образом разрешенной комбинации 111 необходимо приписать подмножество запрещенных кодовых комбинаций: 110, 011, 101, образующихся в результате возникновения единичной ошибки в комбинации 111:

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

Подмножество каждой из разрешенных n-разрядных комбинаций B_i (рис. 6.2) складывается из запрещенных комбинаций, являющихся следствием воздействия:

единичных ошибок (они располагаются на сфере радиусом d=1, и их число равно C ),

двойных ошибок (они располагаются на сфере радиусом d = 2, и их число равно C ) и т. д.

Внешняя сфера подмножества имеет радиус d = s и содержит С запрещенных кодовых комбинаций.

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

Нетрудно убедиться в том (рис. 6.3), что для исправления всех ошибок кратности s и одновременного обнаружения всех ошибок кратности r(r s) минимальное хэммингово расстояние нужно выбирать из условия

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

В реальных каналах связи длительность импульсов помехи часто превышает длительность символа. При этом одновременно искажаются несколько расположенных рядом символов комбинации. Ошибки такого рода получили название пачек ошибок или пакетов ошибок. Длиной пачки ошибок называют число следующих друг за другом символов, начиная с первого искаженного символа и кончая искаженным символом, за которым следует не менее ρ неискаженных символов. Основой для выбора ρ служат статистические данные об ошибках. Если, например, кодовая комбинация 00000000000000000 трансформировалась в комбинацию 01001000010101000 и ρ принято равным трем, то в комбинации имеется два пакета длиной 4 и 5 символов.

Описанный способ декодирования для этого случая не является наиболее эффективным.

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

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

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

Геометрическая интерпретация блоковых корректирующих кодов. Любая n-разрядная двоичная кодовая комбинация может быть интерпретирована как вершина n-мерного единичного куба, т. е. куба с длиной ребра, равной 1.

При n = 2 кодовые комбинации располагаются в вершинах квадрата (рис. 6.4); при n = 3 — в вершинах единичного куба (рис. 6.5); при n = 4 — в вершинах четырехмерного куба (рис. 6.6).

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

Теперь метод декодирования при исправлении одиночных независимых ошибок можно пояснить следующим образом. В подмножество каждой разрешенной комбинации относят все вершины, лежащие в сфере с радиусом (d - l)/2 и центром в вершине, соответствующей данной разрешенной кодовой комбинации. Если в результате действия шума комбинация переходит в точку, находящуюся внутри сферы (d—1)/2, то такая ошибка может быть исправлена.