Файл: Основы автоматического управления..pdf

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

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

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

Л 'Яі

2NHl = п1°в*п ,

то каждой имеющей смысл последовательности из N букв можно поставить в соответствие другую последовательность, составлен­ ную из s — NHJlogz п букв. Иными словами, все имеющие смысл сообщения, составленные из N букв, можно закодировать после­ довательностями, составленными из s букв каждая. При этом все возможные последовательности из s букв будут иметь смысл. Так как для любого европейского языка величина H J log2 п не пре­ вышает 0,5, то все имеющие смысл сообщения можно закодировать приблизительно вдвое более короткими последовательностями букв. Это и доказывает, что лишь около 50% букв в нашей речи независимы, а остальные практически полностью определяются законами грамматики. Иными словами, наш язык обладает боль­ шой избыточностью, и лишь приблизительно 50% букв в нем несут информацию.

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

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

сигнал X не будет полностью определен, а остается случайным. Неопределенность переданного сигнала X будет характеризовать­ ся средней условной энтропией X относительно У. Поэтому коли­ чество информации о переданном сигнале X, содержащееся в при­ нятом сигнале Y, определяется формулой ([54], § 7.4)

Количество информации в каждом знаке передаваемого сигнала в зависимости от способа кодирования будет различным. Поэтому количество информации, передаваемое по каналу в единицу вре­ мени, будет зависеть от способа кодирования и от числа передавае­ мых в единицу времени знаков сигнала. Максимальное количество информации, которое может быть передано по данному каналу в единицу времени, называется пропускной способностью этого канала. Считая, что через Н [X] и Н у [X] в (12.4.1) обозначены соответственно энтропия и средняя условная энтропия сигнала, приходящиеся на единицу времени, и обозначая пропускную спо­ собность канала через С, можем записать сформулированное опре­ деление пропускной способности канала в виде

С = max {ly [X]} = max {Я [X] - H v [X]}. (12.4.2)

Предположим, что информация передается по каналу со ско­ ростью Я, меньшей пропускной способности канала С, и оценим вероятность ошибки при расшифровке принятого сигнала. Для этого обозначим через Я<т> и Я™’ соответственно значения Я [X] и Ну [X], при которых достигается максимум в (12.4.2). Тогда (12.4.2) даст

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

Я [X] достигает максимального значения Я <т>, равно 2™ш\ а число практически возможных реализаций сигнала X, соответ­ ствующих одной реализации принятого сигнала У, при этом равно

2 THym)_ Иными словами, максимальное число практически возмож­ ных различных последователь ностей знаков, каждая из которых может быть передана в течение времени Т по данному каналу, рав­

но 2ГН<?П). При этом каждой принятой последовательности знаков

соответствует 2тнѵп’ практически возможных переданных последо­ вательностей. Это положение схематически изображено на рис. 12.4.1.

Если информация, содержащаяся в сигнале X, передается со скоростью Я бит/с, то число практически возможных реализаций

этого сигнала длительности Т равно 2ГЯ< 2тн(m,. Рассмотрим такой

способ кодирования, при котором каждой из практически возмож­ ных реализаций переданного сигнала сопоставляется одна из 2тн<т>

последовательностей знаков, т. е. из общего числа 2ТН<7П) точек на рис. 12.4.1 выбирается 2ТЯ точек. При этом вероятность того, что данная точка будет занята одной из возможных реализаций

переданной реализации сигнала X, будет меньше

чем 2тн»т> .2—Т(н<т)—н>, т. е.гдля вероятности ошибки рошпри пере­ даче сигнала X имеем неравенство

При Н < С это выражение стремится к нулю при Т -*■ оо. Таким образом, мы доказали, что при передаче информации по каналу с пропускной способностью С со скоростью Я < С можно закоди­ ровать передаваемый сигнал так, что вероятность ошибки будет как угодно мала при достаточно большой длительности переда­ ваемого сигнала Т . Это предложение представляет собой основную теорему Шеннона [75]. Более тонкие математические методы дают

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

Рассмотрим теперь случай передачи информации по каналу, имеющему пропускную способность С, со скоростью Я > С. Из

Таким образом, при передаче информации по каналу с пропускной