ГЛАВА 3. КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ 8 глава

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

то

и

Следовательно, существует способов кодирования, при которых множеству сообщений 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, то такая ошибка может быть исправлена.

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

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

или

Величина R_k, изменяющаяся от 0 до ∞, предпочтительнее, так как лучше отвечает смыслу понятия избыточности. Коды, обеспечивающие заданную корректирующую способность при минимально возможной избыточности, называют оптимальными.

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

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

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

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

или

Эта верхняя оценка найдена Хэммингом. Для некоторых конкретных значений кодового расстояния d соответствующие Q указаны в табл. 6.1.

Таблица 6.1

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

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

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

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

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

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

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

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

Множества, для которых определены некоторые алгебраические операции, называют алгебраическими системами. Под алгебраической операцией понимают однозначное сопоставление двум элементам некоторого третьего элемента по определенным правилам. Обычно основную операцию называют сложением (обозначают а + b = с) или умножением (обозначают а∙b=с), а обратную ей — вычитанием или делением, даже если эти операции проводятся не над числами и неидентичны соответствующим арифметическим операциям.

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

Группой называют множество элементов, в котором определена одна основная операция и выполняются следующие аксиомы: