2.4. Дискретные каналы с шумами. Помехоустойчивые коды

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

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

                                                 (2.19)

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

Пусть на вход дискретного канала поступает  символов в единицу времени. Если при некотором распределении вероятностей символов на входе существует предел

                                                 (2.20)

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

В частности, для постоянного канала

                    (2.21)

Вычисление пропускной способности даже для постоянных каналов в общем случае является довольно трудной задачей. Что касается каналов с памятью, то далеко не всегда их пропускная способность вообще может быть определена, поскольку не всегда существует математическое ожидание выражения (2.19) или предел (2.20). Тем не менее для дискретных отображений реальных каналов связи обычно удается построить математические модели в виде информационно устойчивых, т. е. имеющих определенную пропускную способность дискретных каналов. В частности, такими моделями служат каналы с ограниченной памятью, в которых переходные вероятности зависят только от конечного отрезка предыдущей последовательности символов [7], или каналы, описываемые конечным числом состояний, если текущее состояние можно определить по предыдущему состоянию и последнему переданному символу [8].

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

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

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

Из задачи кодирования в дискретном канале развилась теория помехоустойчивых кодов. Не имея возможности изложить эту теорию подробно, ограничимся лишь ее основными положениями и некоторыми результатами, которые будут даны без доказательств, поскольку в настоящее время существует достаточно обширная монографическая литература, относящаяся к двум основным направлениям — вероятностной [9, 10] и алгебраической [11, 12] теории кодирования.

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

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

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

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

              (2.22)

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

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

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

                      (2.23)

Величину  называют эффективностью кода.

Необходимая избыточность корректирующего кода может быть найдена из условия (2.22) с учетом (2.23):

                          (2.24)

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

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

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

С другой стороны, для получения высокой верности приема с помощью корректирующих кодов часто оказывается необходимым применять значения  порядка сотен и даже больше. Поэтому основной задачей современной теории кодирования является отыскание таких кодов, которые позволяют осуществлять обнаружение и исправление ошибок не путем сравнения с хранящимися в памяти кодовыми комбинациями, а с помощью относительно простых операций, производимых над принятой кодовой комбинацией. В этом направлении уже имеются некоторые достижения. Предложены коды, при применении которых сложность кодера и декодера увеличивается с ростом  не экспоненциально, а пропорционально некоторой небольшой степени  [10, 11, 13]. Краткие сведения об этих кодах будут приведены в последующих параграфах. Подробная классификация предложенных корректирующих кодов приведена в [14].

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

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

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

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