Главная > Теория информаци и связи > Теория информации и надежная связь
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КАНАЛА С ШУМАМИ

5.1. БЛОКОВЫЕ КОДЫ

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

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

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

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

Если является целым числом, то время, необходимое для того, чтобы двоичных символов поступили в кодер, равно времени, требуемому для передачи кодового слова из N символов канала.

Рис. 5.1.1.

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

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

каким бы это соответствие ни было, оно будет считаться фиксированным, и когда двоичная последовательность, соответствующая целому числу поступает на кодер, то кодовое слово передается по каналу. Рис. 5.1.2 дает пример блокового кода с длиной блока 5 для канала, входной алфавит которого состоит из трех букв. Если, например, на кодер поступает последовательность (0,1), то по каналу передается последовательность (2, 2, 1,0, 1). Предположим здесь, что так что 5 символов канала могут быть переданы за время, требуемое для поступления двух двоичных символов в кодер.

Скорость R блокового кода определяется как

Если является целым числом, то согласно (5.1.1) это выражение преобразуется к виду

Рис. 5.12. Код с блоковой длиной кодовыми словами.

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

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

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

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

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

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

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

При построении хороших блоковых кодов главными параметрами, на которые будет обращено внимание, являются: вероятность ошибки при блоковом декодировании, обозначаемая через длина блока N и скорость Не удивительным является то, что уменьшением R (которое можно достичь уменьшением числа двоичных символов в секунду, поступающих на кодер) можно также уменьшить Удивительным является то, что если R меньше, чем пропускная способность канала, то можно при фиксированной увеличивая найти коды, для которых экспоненциально убывает с ростом Это составляет существо теоремы кодирования, доказываемой в § 5.6. Существует, конечно, цена для расплаты за то, что длина блока увеличивается. Во-первых, происходит задержка в системе. Первый двоичный символ блока поступающих данных, вообще говоря, должен быть задержан на сек до того, как будет сформировано кодовое слово и после этого еще на сек, необходимых для передачи кодового слова, по которому этот двоичный символ будет декодирован. Во-вторых,

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

<< Предыдущий параграф Следующий параграф >>
Оглавление