ГЛАВА 3. КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ 5 глава

где h(ξ) — дифференциальная энтропия одного отсчетного значения помехи.

Для помехи с нормальным распределением и дисперсией σ она составит (3.49)

Будем считать, что отсчетные значения входных функций u_T(t) независимы. При воздействии на них независимых значений помехи отсчетные значения выходных сигналов V_T(t) также независимы.

Тогда H(V) можно выразить через дифференциальную энтропию h(V) одного отсчета выходного сигнала:

Подставив (4.32) и (4.33) в (4.29), получим

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

Определим теперь пропускную способность гауссова канала.

Найдем ансамбль входных сигналов, при котором обеспечивается максимальное значение h(V) в выражении (4.35).

Так как выходные сигналы образуются в результате суммирования входных сигналов и помехи, средние мощности которых ограничены, то и средняя мощность выходных сигналов ограничена. Для таких сигналов, как было установлено (см. § 3.5), наибольшее значение h(V) достигается при распределении V по нормальному закону. Известно также, что сумма двух нормально распределенных случайных величин имеет такую же функцию распределения с суммарной дисперсией. Отсюда следует, что при нормально распределенной помехе ξ выходной сигнал V будет распределен по нормальному закону лишь при нормально распределенном входном сигнале u.

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

Они также должны иметь широкий и равномерный энергетический спектр, поскольку только в этом случае можно говорить о независимости отсчетов и использовать соотношение (2.23).

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

Максимальная величина дифференциальной энтропии

Подставляя (4.36) в (4.35), получаем выражение для пропускной способности гауссова канала:

Выясним, как зависит пропускная способность гауссова канала от ширины полосы пропускания F_K.

Из выражения (4.37) следует, что эта зависимость нелинейна, поскольку F_K также влияет на мощность помехи. Учитывая равномерность энергетического спектра белого шума, представим его мощность Р через удельную мощность Р₀ на единицу частоты.

Выражение (4.37) примет вид

Рост пропускной способности канала при неограниченном расширении его полосы пропускания ограничен пределом С_M:

Обозначив по правилу Лопиталя определяем предел С_н при :

О характере зависимости можно судить по графику, представленному на рис. 4.7.

§ 4.6. СОГЛАСОВАНИЕ ФИЗИЧЕСКИХ ХАРАКТЕРИСТИК СИГНАЛА И КАНАЛА

Конкретный канал связи обладает определенными физическими параметрами, от которых зависит возможность передачи по нему тех или иных сигналов. Независимо от назначения непрерывного канала его можно характеризовать тремя основными параметрами: временем, в течение которого он предоставляется для передачи сигнала Т_к, шириной полосы пропускания сигнала F_K и допустимым превышением сигнала над помехой в канале H_к. Превышение H_к характеризуется разностью максимально допустимого сигнала в канале P_{u max} и уровня помех Р (в логарифмическом масштабе). Для проводных каналов превышение в основном определяется пробивным напряжением и уровнем перекрестных помех, для радиоканалов — возможностями выявления сигнала на соответствующих расстояниях.

Произведение указанных основных параметров канала связи принято называть объемом (емкостью) канала и обозначать V_K:

При оценке возможностей передачи сигнала по каналу с заданными физическими характеристиками также ограничиваются рассмотрением трех основных параметров сигнала: его длительности Т_с, ширины спектра F_c и превышения над помехой H_с, причем

где Р_u — средняя мощность передаваемого сигнала; Р — средняя мощность помехи в канале.

Превышение H_с связано с возможностями передатчика и дальностью передачи. Чем больше H_с, тем меньше вероятность ошибочного приема. Аналогично объему канала вводится понятие объема (емкости) V_c передаваемого сигнала:

Как объем сигнала, так и объем канала могут быть представлены в трехмерном пространстве с соответствующими координатами Т, F, Η (рис. 4.8).

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

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

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

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

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

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

В соответствии с выражением (4.37) предельное количество информации, которое может быть передано по каналу связи за время Т_к,

Отсюда следует, что если Р_u/Р >> 1, то при условии обеспечения посредством преобразования сигнала полного использования физических возможностей канала максимальное количество информации, которое можно получить о сигнале, близко к емкости канала:

§ 4.7. СОГЛАСОВАНИЕ СТАТИСТИЧЕСКИХ СВОЙСТВ ИСТОЧНИКА СООБЩЕНИЙ И КАНАЛА СВЯЗИ

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

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

где w(t) — сообщение, поступающее с выхода канала; z(t) — сообщение на входе канала.

Достоверность характеризует помехоустойчивость информационной системы.

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

Скорость передачи информации характеризует эффективность системы.

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

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

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

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

Считается, что символы на вход модулятора поступают равновероятно и статистические связи между ними отсутствуют. Из множества сигналов, удовлетворяющих заданным ограничениям по мощности и полосе частот, для отображения символов отбираются такие, которые в предположении воздействия на них аддитивного гауссова шума обеспечивают наибольшую достоверность приема каждого отдельного символа. Одновременно определяется и структура оптимального приемника. Наиболее полно эти вопросы рассмотрены для случая двоичного канала (m = 2).

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

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

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

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

Рассмотрим теперь особенности статистического согласования различных источников сообщений и каналов связи.

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

В основной теореме Шеннона о кодировании для дискретного канала без помех утверждается, что посредством преобразования сообщений в статистически независимые и равновероятные символы можно повысить скорость передачи вплоть до пропускной способности этого канала (подробно о теореме и методах кодирования говорится в § 5.4).

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

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

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

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

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

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

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

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

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

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

Утверждается также, что при такую передачу никаким способом обеспечить невозможно.

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

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

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

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

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

Контрольные вопросы

1. Назовите основные информационные характеристики источника сообщений.

2. В чем сущность понятия эргодического источника сообщений?

3. Как вычислить энтропию дискретного источника сообщений с памятью?

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

5. Что понимают под избыточностью алфавита источника сообщений?

6. Каковы причины наличия избыточности в сообщении?

7. Определите производительность источника дискретных сообщений и укажите пути ее повышения.

8. Назовите основные характеристики дискретного канала.

9. Какие исходные данные необходимы для создания информационной модели канала с помехами?

10. Охарактеризуйте двоичный симметричный канал без памяти.

11. В чем различие между технической и информационной скоростями передачи?

12. Поясните сущность понятия пропускной способности канала.

13. Запишите выражения для пропускной способности дискретного канала с помехами и без помех.

14. Что понимают под ε-производительностью источника непрерывных сообщений?

15. Какие допущения приняты в модели, известной как гауссовый канал?

16. Как определяют скорость передачи информации и пропускную способность непрерывного канала?

17. Напишите и поясните выражение для пропускной способности гауссова канала.

18. Что подразумевается под объемом: а) сигнала? б) канала?

19. Определите условия неискаженной передачи сигнала по каналу.

20. Сформулируйте теорему Шеннона о кодировании для непрерывного канала с помехами.

21. Назовите основные цели кодирования.

ГЛАВА 5. КОДИРОВАНИЕ ИНФОРМАЦИИ ПРИ ПЕРЕДАЧЕ ПО ДИСКРЕТНОМУ КАНАЛУ БЕЗ ПОМЕХ

§ 5.1. КОДИРОВАНИЕ КАК ПРОЦЕСС ВЫРАЖЕНИЯ ИНФОРМАЦИИ В ЦИФРОВОМ ВИДЕ

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

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

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

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

где i — номер разряда данного числа; l — количество разрядов; a_i — множитель, принимающий любые целочисленные значения в пределах от 0 до m-1 и показывающий, сколько единиц ί-го разряда содержится в числе.

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

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

Учитывая оба обстоятельства, целесообразно выбрать систему, обеспечивающую минимум произведения количества различных символов m на количество разрядов l для выражения любого числа. Найдем этот минимум по графику на рис. 5.1, где показана связь между величинами m и l при воспроизведении определенного достаточно большого числа Q (Q ≈ 60 000).

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

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

Правила Правила Правила

сложения: вычитания: умножения

Наиболее распространенная при кодировании и декодировании логическая операция — сложение по модулю. В двоичной системе она также наиболее проста и определяется равенствами:

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

Пример 5.1. Найдем десятичный эквивалент двоичного числа 1001. После первой единицы слева стоит 0. Удваиваем эту единицу. Получаем число 2. Цифрой следующего младшего разряда также является 0. Удваивая число 2, получаем 4. В самом младшем разряде стоит единица. Удваивая число 4 и прибавляя 1, окончательно получаем 9.

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

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

7 4 5

111 100 101

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

Чтобы сохранить преимущества двоичной системы и удобство десятичной системы, используют двоично-десятичные коды. В таком коде каждую цифру десятичного числа записывают в виде четырехразрядного двоичного числа (тетрады). С помощью четырех разрядов можно образовать 16 различных комбинаций, из которых любые 10 могут составить двоично-десятичный код. Наиболее целесообразным является код 8-4-2-1 (табл. 5.1). Этот код относится к числу взвешенных кодов. Цифры в названии кода означают вес единиц в соответствующих двоичных разрядах. Двоично-десятичный код обычно используется как промежуточный при введении в вычислительную машину данных, представленных в десятичном коде.

Таблица 5.1

В табл. 5.1 представлены два других двоично-десятичных кода с весами 5-1-2-1 и 2-4-2-1, которые широко используются при поразрядном уравновешивании в цифровых измерительных приборах.

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

Наибольшее распространение получил код Грея, часто называемый циклическим или рефлексно - двоичным. Код Грея используется в технике аналого-цифрового преобразования, где он позволяет свести к единице младшего разряда ошибку неоднозначности при считывании. Комбинации кода Грея, соответствующие десятичным числам от 0 до 15, приведены в табл. 5.2.

Таблица 5.2

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