книги из ГПНТБ / Бовбель, Е. И. Элементы теории информации

Г Л А В А 3

ДИСКРЕТНЫЕ КАНАЛЫ БЕЗ ШУМОВ

§ 1. Модель информационной системы передачи дискретных сообщений в отсутствие шумов

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

Простейшая блок-схема дискретного канала связи без шумов приведена на рис. 3.

Рис. 3

Выходным сообщением источника может являться пе­ чатный текст, графическое изображение, звуковая волна, показания прибора и т. п. Назначение кодирующего уст­ ройства (кодер) состоит в том, чтобы представить выход­ ное сообщение источника в некоторой стандартной форме, например в виде последовательности двоичных сигналов. -Однако основная задача кодирования заключается в том, чтобы стандартное представление было наиболее эконом­ ным, т. е. требоъало в среднем наименьшего возможного числа двоичных сигналов, а также чтобы в случае отсут­ ствия шумов на приемной стороне по полученным кодиро­ ванным сигналам можно было однозначно восстановить вид переданных сообщений, т. е. чтобы W—X. Последнее накладывает некоторые ограничения на допустимый вид кодированных сигналов (см. § 3 этой главы).

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

61

§ 2. Пропускная способность канала связи

Введем определение пропускной способности канала

ствующую ей последовательность примятых сообщений,

канала о последовательности X уліа его выходе. I(Wr X T) зависит от вероятностных характеристик источника сооб­ щений и характеристик шумов, действующих в линигГсвязи, ‘метода кодирования сообщений, а также от промежут­ ка времени Т.

Предел

(3.1)

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

представиться следующие случаи:

1)канал связи определен полностью: заданы способы кодирования и декодирования сообщений, длительности передаваемых сигналов, полоса канала связи и вероятно­ стные характеристики помех; тогда максимальная ско­ рость передачи информации отыскивается по статистиче­ ским характеристикам источника сообщений, т. е. разыс­ кивают такое распределение вероятностей по сообщениям X, при котором скорость передачи информации наиболь­ шая;

2)статистические показатели источника сообщений за­ даны; в этом случае способы модуляции, кодирования и декодирования выбираются так, чтобы скорость передачи информации была максимальной;

62

3) канал связи полностью не определен — имеется* возможность изменять те или иные его параметры: дли­ тельности символов, способ кодирования и т. и.; в этом случае параметры канала, которые не заданы, выбирают из условия получения возможно большей скорости пере­ дачи информации, а максимум в (3.2) снова отыскивают

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

При отсутствии шумов wT=x.n zT = у т. На основании

Обозначим через N(T) число~всех возможных последова­ тельностей сообщений, вырабатываемых источником, дли­ тельностью Т. Тогда энтропия Н(ХГ) максимальна/если

где Nk(T) — число всех возможных кодированных после­ довательностей длительностью Т.

63

Задача 1. Определить пропускную способность линии связи, использующей для передачи сообщений код с осно­ ванием т (т. е. с т различными символами). Длитель­ ность всех символов кода одинакова и равна т. Ограни­ чения на допустимый вид кодовых последовательностей символов не накладываются.

Р е ш е н и е. Рассмотрим последовательность из М ко­ довых символов. Длительность ее Г= Мт. Количество различных последовательностей, которое можно составить из т символов по М штук в каждой,

Nk(T) = m ■VI

Подставляя (*) в (3.5), получаем

Если используется двоичный код, то т —2 и Сс=Д((5ит/с).

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

где H(Y) — энтропия кодовых символов, вычисленная с учетом наложенных ограничений. Подставляя (3.7) в (3.6), получаем

где максимум отыскивается с учетом наложенных ограни­ чений.

Задача 3. В информационном канале используется код, при котором запрещается передача подряд двух одинаковых символов. Алфавит кода состоит из четырех различных символов. Вероятности передачи всех разре­

= 1, 2, 3, 4). Число различных пар, которое можно соста-

64

%

вить из четырех различных символов, равно 42= 16. Че­ тыре из них (уі,Уі) запрещены. По условию,-вероятности разрешенных пар кодовых символов одинаковы. Поэтому

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

По формуле полной вероятности

Из теоремы умножения вероятностей

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

Д о к а з а т е л ь с т в о . Внутренняя сумма энтропии

Щ У ) = - S P (y j)S p ( y tly j)1 o g Р ІУ і/y j)

j= 1 /»1

максимальна, когда условные вероятности Р(уіІУу) всех разрешенных переходов i=£j равны между собой.(см. свойства энтропии), т. е.

При этом по формуле полной вероятности

4

Р(Уі) = Уі) = РШ Р(УіІУг) + Р(Уз) Р(УіШ +

/=1

+ Р(уд Р(Уі/У4) = 4- Иѵ>) + р (У*) + Р ( У Л

H ( Y y имеет максимальное значение, равны соответствую­

щим величинам, полученным в предыдущей задаче, и, сле­ довательно, найденная там скорость передачи, согласно (3.8), равна пропускной способности линии связи.

Задача 5. Длительности каждого из т кодовых сим­ волов составляют t u /2, із, t nr Определить число всех

возможных последовательностей длительностью Т, кото­ рые можно составить из этих пі кодовых символов.

Р е ш е н и е. Обозначим искомое число последователь­ ностей через /Ѵ(Т). Тогда число различных последователь­ ностей длительностью (Т—/,*) равно /Ѵ( Т — /,*). Эти после­

Уравнение (3.9) есть линейное уравнение в конечных раз­ ностях. Методы решения таких уравнении аналогичны методам решения линейных дифференциальных уравне­ ний с постоянными коэффициентами.

Решение уравнения (3.9) будем искать в виде

66

то левая часть (3.11) тождественно обращается в нуль и, следовательно, (3.10) является решением уравнения (3.9). При этом-существенно заметить, что N(T) должно быть вещественно и неотрицательно при всех положительных значениях Т.

Если /*і— максимальный корень уравнений (3.12), при достаточно большом Т слагаемое С\гхг значительно боль­ ше суммы остальных слагаемых в правой части (3.10). Поэтому можно записать искомое, число последователь­ ностей в виде

N ( T ) ~ c xr ( = c r r ( Г » 1 ) . ■ (3.13)

Задача 6. Пусть длительности кодовых символов оди­ наковы и равны т0. Показать, что в этом случае N(T) —

==сг топределяет число всех возможных последователь­ ностей длиной в М символов, которые можно составить из m различных кодовых символов ( Т = М ^ 0).

Решение . Если длительности всех кодовых симво­ лов одинаковы, то из уравнения (3.12)

_і_

Подставляя (3.14) в выражение (3.13) предыдущей зада­ чи, получаем

67

Р е ш е н и е . Подставляя выражение N(T) из (3.13)

Задача 8.'Источник вырабатывает три различных сим­ вола a, b и с соответственно с длительностями 2, 3 и 4 ед. времени. Определить число различных сообщений, кото­ рые может выработать источник в течение Т— 20 ед. вре­ мени.

Р е ш е и и е. Уравнение (3.9) из задачи 5 в нашем слу­ чае имеет вид

ных длительностей сообщений для выполнения последне­ го равенства необходимо положить

Результаты непосредственного расчета по формуле (3.16) с учетом (3.17) сведем в табл. И.

Задача 9. Для передачи сообщений по линии связи ис­ пользуют три-различных символа с длительностями t\ — = 10~6с, /2= f 3= 2-10“°с. При отсутствии ограничений на

68

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

Р е ш е н и е . Искомая пропускная способность пахо- -дится по формуле (см. задачу 7)

C= log г,

где /‘ — максимальный корень уравнения

Введем

= 0,5. Логарифмируя обе части последнего равенства, на­

Задача 10. Для передачи сообщений используются ко­ довые символы одинаковой длительности ѵ Вероятности появления кодовых символов на входе линии связи одина­ ковы и равны Р (уі) = \/т ( / =1, 2, ..., т). Показать, что • при этом фактическая скорость передачи кодовых симво­ лов равна пропускной способности линии связи.

Так как по условию кодовые символы равновероятны, эн­ тропия

•т

09