2. Двоичный симметричный канал

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

Рис. 1. Двоичный симметричный канал.

Злой шутник, который вводит ошибки в передачу, очень простодушен: у него нет памяти и он "перевирает" символы случайно и независимо друг от друга. Его действия разрушительны, но в нем нет сознательной зловредности и деятельность его устойчива, по крайней мере, в статистическом смысле.

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

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

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

Рис. 2. Передача информации по двоичному симметричному каналу.

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

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

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

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

при будет соответствовать передаваемая последовательность

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

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

В основополагающей работе Шеннона [18] по теории информации доказаны две общие теоремы, которые находятся в явном противоречии с нашими ожиданиями.

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

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

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

Мы видим, что измеряет плотность информации на передаваемый символ.

Пропускная способность полностью определяется самим каналом, и ее также можно отнести к одному передаваемому символу. Можно показать [18], что для двоичного симметричного канала с переходной вероятностью

где

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

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

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