Каналы связи симметричные асимметричные динамические. Передача информации

Описание

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

ДСК часто употребляется теоретиками как простейший канал с шумом . В теории связи множество проблем сводится к ДСК.

Определение

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

Первый аргумент условной вероятности соответствует случайному передаваемому символу, второй полученному значению.

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

Пропускная способность ДСК

Пропускная способность канала вычисляется формулой:

Cм. также

Wikimedia Foundation . 2010 .

Смотреть что такое "Двоичный симметричный канал" в других словарях:

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

- (англ. channel, data line) система технических средств и среда распространения сигналов для передачи сообщений (не только данных) от источника к получателю (и наоборот). Канал связи, понимаемый в узком смысле (тракт связи),… … Википедия

Канал связи, переходная функция к рого обладает тем или иным свойством симметрии. Однородный канал без памяти с дискретным временем и конечными пространствами состояний У и компонент сигналов на входе и выходе, задаваемый матрицей переходных… … Математическая энциклопедия

Раздел математики, исследующий процессы хранения, преобразования и передачи информации. В основе его лежит определенный способ измерения количества информации. Возникшая из задач теории связи, теория информации иногда рассматривается как… … Энциклопедия Кольера - Терминология ГОСТ 22670 77: Сеть связи цифровая интегральная. Термины и определения оригинал документа: 10. n ичный сигнал электросвязи n агу digital signal Цифровой сигнал электросвязи, имеющий п возможных состояний представляющего параметра,… … Словарь-справочник терминов нормативно-технической документации

- (ДСК) это простейший канал связи, на вход которого подаются двоичные символы с предположением, что данные всегда будут передаваться корректно. Этот канал часто используется в теории кодирования, как один из самых простейших для анализа… … Википедия

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

- (англ. channel, data line) система технических средств и среда распространения сигналов для передачи сообщений (не только данных) от источника к получателю (и наоборот). Канал связи, понимаемый в узком смысле (тракт связи),… … Википедия

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

Канал связи, переходная функция к рого обладает тем или иным свойством симметрии. Однородный канал без памяти с дискретным временем и конечными пространствами состояний У и компонент сигналов на входе и выходе, задаваемый матрицей переходных… … Математическая энциклопедия

I Канал (от лат. canalis труба, жёлоб) в гидротехнике, искусственное русло (водовод) правильной формы с безнапорным движением воды, устроенное в грунте. К. сооружают в открытой выемке или в насыпи (при пересечении балок, оврагов и др.),… … Большая советская энциклопедия

Цифровой канал передачи - 3.8 Цифровой канал передачи комплекс технических средств и среды передачи, обеспечивающий передачу цифрового сигнала электросвязи со скоростью передачи, характерной для данного канала передачи. Источник …

цифровой канал передачи данных - цифровой канал ПД Канал передачи данных, по которому может передаваться только цифровой сигнал данных. Примечание Цифровому каналу передачи данных присваивается название в зависимости от вида передаваемого сигнала, например, двоичный цифровой… … Справочник технического переводчика

Цифровой канал передачи данных - 164. Цифровой канал передачи данных Цифровой канал ПД Е. Digital data channel Канал передачи данных, по которому может передаваться только цифровой сигнал данных. Примечание. Цифровому каналу передачи данных присваивается название в зависимости… … Словарь-справочник терминов нормативно-технической документации

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

ГОСТ Р 51385-99: Элементы процедур передачи и форматы служебных пакетов (сообщений) в широкополосной цифровой сети интегрального обслуживания с быстрой коммутацией пакетов. Требования к процедурам и форматам - Терминология ГОСТ Р 51385 99: Элементы процедур передачи и форматы служебных пакетов (сообщений) в широкополосной цифровой сети интегрального обслуживания с быстрой коммутацией пакетов. Требования к процедурам и форматам оригинал документа: 2.2… … Словарь-справочник терминов нормативно-технической документации

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

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

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

Рис. 7.1. Общая схема передачи информации

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

Рис. 7.2. Схема двоичного симметричного канала

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

Некоторые типы ошибок:

Чаще других встречается замена знака. Этот тип ошибок исследован наиболее полно.

Способы повышения надежности передачи сообщений

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

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

На практике необходим компромисс между экономностью кода и защитой от ошибок.

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

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

передача в контексте;

дублирование сообщений;

передача с переспросом.

Рассмотрим подробней каждый из этих способов.

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

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

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

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

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

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

7.5. Пропускная способность канала

Величина I (X ; Y ) играет особую роль в теории информации и опи-сывает передачу информации по каналу связи. Из определения (7.9) следует, что I (X ; Y ) зависит как от переходных вероятностей кана-ла, так и от распределения вероятностей символов на входе канала. Для дальнейших рассуждений рассмотрим дискретный канал без памяти с фиксированными переходными вероятностями и зададим-ся вопросом: Какое максимальное количество информации можно передать по данному каналу?

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

Замечание. Размерность пропускной способности - бит/символ. Если, например, по каналу передается один символ в сек, то можно также говорить о размерности бит/сек.

Так как максимум ищется по всем допустимым входным источ-никам, то пропускная способность зависит только от переходных ве-роятностей канала.

С математической точки зрения, поиск пропускной способности дискретного канала без памяти сводится к поиску распределения ве-роятностей входных символов источника, обеспечивающего максимум информации I (X ; Y ). При этом, на вероятности входных сим-волов накладываются ограничения

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

Теорема 7.5.1. В симметричных дискретных каналах без памяти пропускная способность достигается при равномерном распределе-нии вероятностей входных символов источника Х.

Замечание. В приводится также метод, позволяющий опре-делить, является ли канал симметричным или нет.

7.5.1. Пропускная способность

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

Используя (7.9), получаем

Подставляя числовые значения, имеем

Энтропия ДСК определяется через (2.32)

Окончательно получаем пропускную способность ДСК в компактной форме

Интересными являются два граничных случая:

1. Передача информации по бесшумному каналу:

и

2. Канал полностью зашумлен:

И

Важным частным случаем ДСК является двоичный симметричный канал со стираниями (ДСКС) или двоичный канал со стирания-ми (Binary Erasure Channel, ВЕС - англ.). Как и ДСК, двоичный канал со стираниями может служить упрощенной моделью переда-чи информации по каналу с аддитивным белым гауссовским шумом (АБГШ). Правило принятия решения в ДСКС приведено на рис. 7.11. Из рисунка видно, что наряду с решениями о переданном символе «0» или «1», здесь иногда принимается решение о стирании приня-того символа «е»(Erasure-англ.). Стирание происходит в случае, ес-ли продетектированный аналоговый сигнал V попадает в зону, для которой значения условных функций плотности распределения ве-роятностей f (V/0) и f (V /1) оказываются близкими к нулю.

Рис. 7.11. Условные функции плотности распределения ве-роятностей продетектированного сигнала и об-ласти принятия решений.

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

Рис. 7.12.

Обозначим вероятность стирания через q , а вероятность ошибки нестертого символа через р.

Диаграмма переходов для капала с двумя входными и тремя вы-ходными символами приведена на рис. 7.12. Соответствующая мат-рица канала, содержащая переходные вероятности, имеет вид

Найдем пропускную способность канала со стираниями. Так как ка-нал симметричен, пропускная способность достигается при равно-мерном распределении входных символов

Отсюда следует, что вероятности выходных символов равны

Теперь все необходимые вероятности известны. Воспользовавшись (7.9), имеем

Используя свойство симметрии канала, получаем

Как мы видим, пропускная способность канала со стираниями зави-сит только от вероятностей р и q . График С = f (p , q ) представляет собой пространственную трехмерную поверхность, расположенную над плоскостью (p , q ). Здесь мы ограничимся только рассмотрением двух важных частных случаев.

1. При q = 0, мы имеем двоичный симметричный канал, уже рас-смотренный ранее. Подставляя q = 0 в (7.59) мы, как и ожидалось, получаем (7.49).

2. В канале присутствуют только стирания, т.е. при р = 0 ошиб-ки или не присутствуют, или мы ими пренебрегаем. В этом случае

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

Замечание. Здесь возникает вопрос о возможности увеличения пропускной способности при приеме со стираниями на практике. В этом месте обнаруживается слабость теории информации. Тео-рия информации зачастую не может предложить конструкцию, реализующую теоретически достижимые границы. Тем не менее, небольшой пример, подробно рассмотренный во второй части этой книги, показывает, что введение стираний может иногда снижать вероятность ошибки. Рассмотрим этот пример на интуитивном уровне. Разобьем поток передаваемой информации на блоки, содер-жащие 7 двоичных символов (7 бит). К каждому блоку добавим один бит («О» или «1») проверки на четность. Закодированные та-ким образом блоки из восьми двоичных символов всегда будут со-держать четное число единиц. Пусть вероятность ошибки в ДСК достаточно мала. Введем зону стирания (рис. 7.11) таким образом, чтобы ошибки, в основном, перешли в стирания. При этом, вероят-ность «нестертой» ошибки будет пренебрежимо мала, а вероят-ность стирания будет оставаться достаточно малой. Мы получим стирающий капал (ДСКС), в котором блоки из восьми двоичных символов в подавляющем большинстве случаев или будут приняты правильно или будут содержать только один стертый двоичный символ. Качество приема существенно улучшится, так как одно стирание в блоке с четным числом единиц всегда может быть ис-правлено.

Рис. 7.13. Пропускная способность двоичного симметрич-ного канала С ДСК с вероятностью ошибки ε и двоичного канала со стираниями С ДСКС с ве-роятностью стирания q и вероятностью ошибки р = 0.

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

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

На рис. 7.14 задана переходная диаграмма симметричного канала со стираниями. Определите:

1. Матрицу канала

2. Распределение вероятностей символов источника У, если из-вестно, что символы источника X равномерно распределены, т.е. pa = pi = 1/2;

3. Пропускную способность канала;

4. Диаграмму информационных потоков со всеми энтропиями;

5. Модель канала с матрицей Ру/у.

Решение.

1. С учетом того, что сумма вероятностей в каждой строке мат-рицы равна 1, получим

2. Исходя из равномерного распределения вероятностей символов на входе, согласно (7.52), имеем

3. Так как рассматриваемый канал симметричен, пропускная спо-собность достигается при равномерном распределении входных сим-волов. Из (7.54) с учетом (7.56) имеем

4. Энтропия дискретного двоичного источника, без памяти X с равномерным распределением вероятностей символов равна

Энтропия источника Y р авна

Так как в симметричном канале с равномерным распределени-ем входных символов I (X ; Y ) совпадает с пропускной способностью С из (7,58), совместную энтропию и две условные энтропии мож-но подсчитать, используя таблицу 7.3. Диаграмма информационных потоков изображена на рис. 7.15.

Рис. 7.15. Диаграмма информационных потоков двоичного симметричного канала со стираниями.

5. Пересчет матрицы переходных вероятностей канала в

матрицупредоставляем сделать читателю в качестве самостоятельного упражнения. Диаграмма канала с входным источником Y и выходным X приведена на рис. 7.16 для контроля.

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

7.6. Теорема кодирования для дискретных каналов без памяти

Рассмотрим дискретный канал без памяти с пропускной способно-стью С[бит/символ], в котором каждый символ передается в течении Т s сек. Для этого канала

Пусть энтропия некоторого источника X , измеренная в течении сек, составляет Н(Х) бит. Тогда имеет место следующая теорема.

Теорема 7.6.1. Теорема кодирования для канала (теорема Шенно-на).

Для источника X со скоростью R = H (X )/ T S [бит/сек] и R < С существует некоторый код. с помощью которого информация источ-ника X может быть передана но каналу связи с пропускной способ-ностью С 1 [бит/сек] со сколь угодно малой вероятностью ошибки.*

* Теорема кодирования справедлива не только для дискретных каналов, она так-же верна и при передаче дискретных сообщений по непрерывным каналам. Прим. перев.

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

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

Теорема кодирования определяет также верхнюю границу для скорости передачи R .*

При доказательстве теоремы вводится показатель экспоненци-альной оценки R 0 , который может быть использован для оцен-ки технически достижимой скорости передачи данных .

* Здесь необходимо сделать разъяснение. Существует обратная теорема кодиро-вания, которая говорит о том. что при R > С не существует никакого метода кодирования, позволяющего передавать информацию с как угодно малой веро-ятностью ошибки. Прим. перев.

Глава 8. Непрерывные источники и каналы

В главе 2 дано определение энтропии как меры неопределенности источника. При этом предполагалось, что энтропия измеряется посредством случайных экспериментов. В данной главе мы будем при-менять аналогичный подход к непрерывным источникам.

Рис. 8.1. Сигнал непрерывного источника.

Вместо источников с конечным алфавитом символов будем рас-сматривать источники, выходом которых являются непрерывные сигналы. Примером таких сигналов может служить изменяющееся во времени напряжение в телефонных каналах и т.д. На рисунке 8.1 , представлен непрерывный источник X , выходом которого является, аналоговый сигнал x (t ), являющийся некоторой случайной функци-ей от времени t . Будем рассматривать значения x (t ) в некоторые фиксированные моменты времени как случайные эксперименты, ко-торые несут некоторую информацию об источнике X .

8.1. Дифференциальная энтропия

На рисунке 8.2 показаны два непрерывных источника X и Y , свя-занные каналом (аналогично рис. 7.4). Здесь, вместо вероятностей, стоят функции плотностей распределения вероятностей стохастических переменных.

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

Рис. 8.2. Два непрерывных источника без памяти, связан-ных каналом.

Преобразуем непрерывный источник X в дискретный. Для это-го проквантуем значения аналогового выхода источника с шагом Δ (рис. 8.3).

Рис. 8.3. Оцифровка непрерывного источника с интерва-лом квантования Δ в моменты наблюдения t 0 , t 1 и т.д.

Кроме этого, как это обычно делается в теории информации, про-изведем дискретизацию источника но времени. В результате, полу-чим последовательность стохастических переменных Следуя таблице 7.2, определим взаимную информацию символов x i , и y j , где x i - значение выходного символа в момент времени t m , a x j - в момент времени t n

Взаимную информацию можно трактовать как «снятую» (утра-ченную) неопределенность попадания переменной Х п в интервале , когда известно, что переменная Х т принадлежит интер-валу или наоборот. Будем считать функцию плотности распределения вероятности непрерывной функцией. Тогда, устрем-ляя ширину интервала квантования к нулю, получим

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

Замечание. Здесь, для приведения в соответствие обозначений этой главы с результатами таблицы 7.2, вместо Х т используется X , а вместо Y n - Y .

Информация источника определяется исходя из аналогичных рас-суждений

В отличие от выражения (8.3) для взаимной информации, в (8.4) появляется слагаемое, зависящее от интервала квантования Δ.

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

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

Средняя информация непрерывного источника, так называемая дифференциальная энтропия, определяется как

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

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

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

Замечание. В информационной технике за исходный параметр принимают σ 2 - дисперсию, которая определяет среднюю мощ-ность стохастического процесса [ 10]. Ясно, что с увеличением мощности передатчика, количество передаваемой информации уве-личивается и, наоборот, с увеличением мощности шумов, возрас-тает неопределенность, т.е. в единицу времени передается меньше информации.

Из теории информации следует, что дифференциальная энтропия достигает своего максимума при гауссовском распределении вероят-ности.

Теорема 8.1.1. При заданной дисперсии σ 2 , максимальной диффе-ренциальной энтропией обладает источник с гауссовским распреде-лением вероятности, причем.

Пример: Дифференциальная энтропия гауссовского источника.

Из (8.5) следует, что дифференциальная энтропия гауссовского источника равна

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

Численные примеры для трех, наиболее употребительных распреде-лений, приведены в таблице 8.1.

Таблица 8.1. Пример дифференциальной энтропии.

Пример: Телефония.

Практическая польза приведенных выше результатов может быть наглядно показана при помощи оценки достижений скорости пере-дачи информации (в битах) в цифровых телефонных линиях. Совре-менные стандартные методы цифровой передачи речи (логарифми-ческие РСМ) требуют затраты 8 бит на кодирование одного отсчета, при частоте отсчетов 8 кГц. Таким образом, скорость передачи речи составляет 64 кбит/сек.

Исходя из равномерного распределения вероятностей в интервале [-1,1], опытным путем получим σ 2 = 1/3. Таким образом, дифферен-циальная энтропия на один отсчет составляет

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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