Н. И. Сорока, Г. А. Кривинченко
Теория передачи информации.
Сборник задач
Рекомендовано УМО по образованию в области информатики
и радиоэлектроники в качестве пособия для специальности
1–53 01 07 «Информационные технологии и управление
в технических системах»
Минск БГУИР 2015
УДК 621.391.3(076.1)
ББК 32.811я73
С65
К82
Р е ц е н з е н т ы:
кафедра информационных технологий
Белорусского государственного университета (протокол №8 от 20.05.2014);
доцент кафедры управления информационными ресурсами
Академии управления при Президенте Республики Беларусь,
кандидат технических наук, доцент Н. И. Белодед
К82 Кривинченко, Г.А.
С12 Сорока, Н.И. Теория передачи информации. Сборник задач: пособие /
Н.И. Сорока, Г.А. Кривинченко. – Минск: БГУИР, 2015. – 67 c.
ISBN 978-985-543-104-7.
Сборник содержит задачи по расчету информационных характеристик источников и каналов связи, по кодированию информации в каналах связи с помехами и без помех, по сжатию информации и криптографическому закрытию информации. В начале каждого раздела приводятся основные расчетные формулы и примеры решения задач. В приложении приведены необходимые справочные данные. Материалы могут быть использованы в курсовом и дипломном проектировании.
УДК 621.391.3(076.1)
ББК 32.811я73
ISBN 978-985-543-104-7 © Сорока Н.И., Кривинченко Г.А., 2015
© УО «Белорусский государственный
университет информатики
и радиоэлектроники», 2015
СОДЕРЖАНИЕ
1. Количественная оценка информации. 4
1.1. Основные формулы.. 4
1.2. Задачи и упражнения. 8
2. Источники дискретных сообщений. 12
2.1. Основные формулы.. 12
2.2. Задачи и упражнения. 16
3. Источник непрерывных сообщений. 19
3.1. Основные формулы.. 19
3.2. Задачи и упражнения. 20
4. Информационные характеристики непрерывных каналов. 21
4.1. Основные формулы.. 21
4.2. Задачи и упражнения. 22
5. Информационные характеристики дискретных каналов связи. 24
5.1. Основные формулы.. 24
5.2. Задачи и упражнения. 26
6. Кодирование информации при передаче по дискретному каналу без помех. 28
6.1. Основные формулы.. 28
6.2. Правила построения эффективных кодов. 29
6.3. Задачи и упражнения. 33
7. Кодирование информации при передаче по дискретному каналу с помехами. 35
7.1. Основные формулы.. 35
7.2. Общие правила построения корректирующих кодов. 37
7.3. Задачи и упражнения. 41
8. Кодирование как средство криптографического закрытия информации. 43
8.1. Правила шифрования. 43
8.2. Задачи и упражнения. 45
9. Сжатие данных. 46
9.1. Основные понятия. 46
9.2. Задачи и упражнения. 49
10. Преобразование непрерывных сообщений в дискретные сигналы.. 50
10.1. Основные формулы.. 50
10.2 Задачи и упражнения. 53
Приложение 1. 55
Приложение 2. 57
Приложение 3. 58
Приложение 4. 60
Приложение 5. 66
Приложение 6. 66
Литература. 67
Количественная оценка информации
Основные формулы
Ёмкость устройства, состоящего из n ячеек, каждая из которых может находиться в одном из m равновероятных состояний:
(1.1)
Энтропия дискретного источника, имеющего m равновероятных состояний:
(1.2)
Количество информации при неполной достоверности результатов опыта:
(1.3)
где Р 2 и Р 1 – апостериорная и априорная вероятности соответственно.
Энтропия ансамбля:
(1.4)
где Рi – вероятность того, что источник находится в i- м состоянии.
Средняя неопределённость, приходящаяся на одно состояние ансамбля Y при известном состоянии ансамбля X (условная энтропия):
. (1.5)
Энтропия объединения двух статистически связанных ансамблей X и Y:
(1.6)
(1.7)
. (1.8)
Энтропия статистически независимых ансамблей:
. (1.9)
Точные количества неопределённости в совместном событии xi и yj:
.
Точные значения неопределённостей в наступления события yj при известном исходе некоторого события xi:
.
Основные соотношения между вероятностями:
(1.10)
(1.11)
(1.12)
(1.13)
. (1.14)
Если неопределённость передачи некоторого сигнала X до опыта H (X), а после опыта H (X/Y), то количество информации, имеющееся в Y о X:
(1.15)
(1.16)
. (1.17)
Пример 1.1. Опыт X имеет два исхода 
, 
с соответственными вероятностями 
= 0,3, 
= 0,7. Найти точные и среднее количества информации, несомые исходами 
и . Вычислить дисперсию случайной величины 
и величину отклонения от своего среднего значения 
.
Решение. Точные количества информации, несомые исходами 
, 
, равны:
Так как числа 
() = 1,737 и 
() = 0,515 появляются с соответственными вероятностями 0,7 и 0,3, среднее количество информации по К. Шеннону будет иметь значение
Дисперсию случайной величины 
вычислим из выражения
Таким образом, случайная величина 
отклоняется от своего значения 
в среднеквадратичном на величину 
Пример 1.2. Вероятности совместного появления 
объединения двух статистически зависимых ансамблей заданы в виде табл. 1.1.
Таблица 1.1
Вероятности совместного появления P (xi, yj)
| Определить точные и среднее количества неопределенности совместного наступления событий хi и yj, а также точные и средние количества неопределенности в yj при известном исходе хi.
Решение. Точные количества неопределенности в совместном наступлении событий  и  находим из формулы
|
Подставляя в данное выражение 
из табл. 1.1, получим точные количества 
, которые помещены в табл. 1.2.
| Таблица 1.2 Точные количества H (xi, yj) | Среднее количество неопределенности в любом совместном наступлении событий хi, yj равно
| ||||
| yj | xi | ||||
| х 1 | х 2 | ||||
| y 1 | 2,32 | 1,51 | |||
| y 2 | 1,32 | 4,32 | |||
Найдём точные значения неопределенностей в наступлении события при известном исходе некоторого события 
. Для этого необходимо знать условные вероятности 
, а затем воспользоваться формулой
Найдём сначала безусловные вероятности 
и 
по формулам полной вероятности
; 
.
В результате вычислений получим:
= 0,6; 
= 0,4;
= 0,55; 
= 0,45.
Наконец, по формуле умножения вероятностей вычислим
Результаты вычислений представлены в табл. 1.3.
Таблица 1.3
Условные вероятности P (yj / xi)
| yj | xi | |
| х 1 | х 2 | |
| y 1 | 0,33 | 0,87 |
| y 2 | 0,67 | 0,13 |
Результаты расчета 
представлены в табл. 1.4.
Таблица 1.4
Точные условные энтропии H (yj / xi)
| yj | xi | |
| х 1 | х 2 | |
| y 1 | 1,6 | 0,20 |
| y 2 | 0,58 | 2,94 |
Найдём частные условные энтропии путём усреднения точных условных энтропий.
.
Результаты расчёта следующие:
Эти результаты образуют случайную величину, значения которой наступают с вероятностью 
. Поэтому только среднее 
, усреднённое с весом 
, не случайно, а именно:
Если испытания будут независимы, то энтропия объединения будет
Таким образом
= 1,74 бит < 
1,96 бит.
Задачи и упражнения
1.2.1. В некотором городе 25 % населения составляют студенты. Среди студентов 50 % юношей. Всего юношей в городе 35 %. Сколько дополнительной информации содержится в сообщении, что встреченный юноша – студент.
Ответ: I = 1,486 бит.
1.2.2. Определить минимальное число взвешиваний, которое необходимо произвести на равноплечных весах, чтобы среди 27 внешне неотличимых монет найти одну фальшивую, более лёгкую. Указать алгоритм определения фальшивой монеты.
Ответ: 3.
1.2.3. Опыт Х имеет три исхода x 1, x 2, x 3 с соответственными вероятностями Р (x 1) = 0,2; Р (x 2) = 0,5; Р (x 3) = 0,3. Найти точные и средние количества информации, несомые исходами x 1, x 2, x 3.
Ответ: 1,49 бит.
1.2.4. По условию предыдущей задачи вычислить дисперсию D (I) случайной величины 
и величину отклонения 
.
Ответ: D (I) = 0,277; 
1.2.5. Вероятности совместного появления Р (xi, 
yj) объединения двух статистически зависимых ансамблей заданы в табл. 1.5. Определить точные и средние количества неопределённости в совместном наступлении событий xi и yj, а также точные и средние количества неопределённости в yj при известном исходе xi.
Таблица 1.5
Вероятности совместного появления, Р (xi, yj)
| yj | xi | ||
| x 1 | x 2 | x 3 | |
| y 1 | 0,1 | 0,15 | 0,05 |
| y 2 | 0,05 | 0,03 | 0,02 |
| y 3 | 0,3 | 0,2 | 0,1 |
Ответ: точные количества H (x 1, y 1) = 3,32; H (x 2, y 1) = 2,74; H (x 3, y 1) = 4,32; H (x 1, y 2) = 4,32; H (x 2, y 2) = 5,06; H (x 3, y 2) = 5,64; H (x 1, y 3) = 1,74; H (x 2, y 3) = 2,32; H (x 3, y 3) = 3,32; среднее количество 
точные количества условных энтропий H (y 1/ x 1) = 2,171; H (y 1/ x 2) = 1,361; H (y 1/ x 3) = 1,766; H (y 2/ x 1) = 3,171; H (y 2/ x 2) = 3,662; H (y 2/ x 3) = 3,074; H (y 3/ x 1) = 0,584; H (y 3/ x 2) = 0,908; H (y 3/ x 3) = 0,766; среднее количество 
.
1.2.6. По условию задачи 1.2.5 определить энтропию объединения когда источники независимы.
Ответ: 
.
1.2.7. Известно, что телеизмеряемая величина должна быть в пределах от 21 до 40 В. Измерение произвели прибором, который показал 30 В, но он имеет погрешность 
В. Определить количество информации, полученной в результате опыта.
Ответ: I = 2 бита.
1.2.8. Студент может сдать зачёт по теории передачи информации с вероятностью α, не проработав весь материал, и с вероятностью β, проработав весь материал курса; или не сдать зачёт с вероятностью γ, не проработав весь материал, и с вероятностью δ, проработав весь материал курса 
. Определить среднее количество информации, которое может получить преподаватель, о подготовленности студента по результатам сдачи зачёта.
Ответ: 
.
1.2.9. По линии связи с помехами передаётся одно из двух сообщений х 1 или х 2с вероятностями соответственно p и g, причём p + g = 1. На приёмном конце канала сигналу х 1 соответствует y 1, а сигналу х 2 соответствует y 2. Заданы условные вероятности правильного приёма 
и 
. Определить количество информации I (Y, X), содержащее в Y o X.
Ответ: 
.
1.2.10. По каналу связи передаётся один из двух сигналов х 1 или х 2 с одинаковыми вероятностями. На выходе канала сигналы х 1 и х 2 преобразуются в сигналы y 1 и y 2, причём из-за помех, которым одинаково подвержены сигналы х 1 и х 2, в передачу вносится ошибка, так что в среднем один сигнал из ста принимается неверно. Определить среднее количество информации на один символ. Сравнить её с количеством информации при отсутствии помех.
Ответ: при отсутствии помех I (X,Y) = 1 бит; при наличии помех I (Y,X) = 0,919 бит.
1.2.11. Из выражения для количества информации
получить выражение для точного количества информации, содержащего в сообщении yj, о сообщении xi.
Ответ: 
.
1.2.12. По цели может быть произведено n независимых выстрелов, вероятность поражения цели при каждом выстреле равна Р. После k -го выстрела 
производится разведка, сообщающая, поражена или не поражена цель. Если поражена, стрельба прекращается. Определить k из условия, что количество информации, доставляемое разведкой, было максимальным.
Ответ: 
.
1.2.13. На вход линии связи, в которой действует помеха, поступает сообщение Х в двоичном коде 11111000. На выходе линии связи зафиксирована последовательность 11100001. Определить точное и среднее количество информации, содержащееся в Y о Х.
Указание. Для удобства расчётов обозначить Х = АААААВВВ и Y = CCCDDDDC.
Ответ: точные количества информации I (A, C) = I (C, A) = 0,263 бит,
I (A, D) = I (D, A) = –0,322 бит, I (B, D) = I (D, B) = 0,415 бит, I (B, C) = I (C, B)=
= – 0,585 бит, среднее количество информации I (Y, X) = 0,049 бит.
1.2.14. Сигнал состоит из семи двоичных элементов. Определить количество информации в сигнале, когда элементы равновероятны, т. е. Р 1 = Р 2 = 1/2, и когда Р 1 = 3/4, а Р 2 = 1/4.
Ответ: 
бит; 
бит.
1.2.15. Определить энтропии H(X), H(Y), H(X/Y), H(X,Y), если задана матрица вероятностей состояний системы, объединяющей источники X и Y:
.
Ответ: H (X) = 1,485 дв.ед.; H (Y) = 1,57 дв.ед.; H (X/Y) = 0,55 дв.ед.;
H (X,Y) = 2,12 дв.ед.
1.2.16. Известны энтропии двух зависимых источников Н (Х) = 5 дв.ед., H (Y) = 10 дв.ед. Определить, в каких пределах будет изменяться условная энтропия H (Y/X) при изменении H (X/Y) в максимально возможных пределах.
Указание. Использовать графическое отображение связи между энтропиями.
Ответ: H (Y/X) будет уменьшаться до значения H (Y) – H(X) = 5 дв.ед.
1.2.17. Ансамбли событий X и Y объединены. Вероятности совместных событий (x, y) описываются матрицей, представленной ниже.
| Определить: 1) энтропию ансамблей X и Y; 2) энтропию объединённого ансамбля (X, Y); 3) условные энтропии ансамблей; 4) количество информации, содержащейся в событиях y относительно x. | ||||||
| x 1 | x 2 | x 3 | ||||
| y 1 | 0,1 | 0,2 | 0,3 | |||
| y 2 | 0,25 | 0,15 | ||||
Ответ: H (X) = 1,512 
H (Y) = 0,971 H (X,Y) = 2,228 H (X/Y) = 1,257 H (Y/X) = 0,716 I (Y, X) = 0,255 дв.ед.
Источники дискретных сообщений
Основные формулы
Энтропия источника сообщений при наличии связей между двумя соседними символами:
(2.1)
Энтропия источника сообщений, когда коррелятивные связи имеются между тремя символами:
(2.2)
Число типичных последовательностей длиной М:
(2.3)
где Н (Х) – энтропия эргодического источника.
Число всевозможных последовательностей, которое можно составить из n букв:
(2.4)
Число последовательностей, у которых из М мест nА мест представлено букве А, равно числу сочетаний из М элементов nА:
. (2.5)
Вероятность того, что в выработанной источником последовательности длиной М содержится nА символов А, определяется из биномиального закона:
. (2.6)
Избыточность источника:
. (2.7)
Скорость создания сообщений или поток информации
, (2.8)
где 
– средняя длительность, которая определяется формулой
. (2.9)
Пример 2.1. Источник, используя алфавит из двух символов и , вырабатывает последовательности 
и т. д. Вероятностные связи в данной последовательности имеют место между тремя символами. Определить все возможные состояния источника и порядок их следования в данной последовательности.
Решение. В условии задан эргодический источник второго порядка 
. Поэтому число различных состояний источника равно 
. Выпишем их, нумеруя состояния соответствующими индексами:
Чтобы установить, в каком состоянии находится источник, необходимо подождать, пока он выработает два символа. Поэтому в последовательности 
и т. д. первым состоянием является 
. Затем источник после появления символа 
переходит в состояние 
и т. д. Получается следующая последовательность состояний, проходимая источником:
Пример 2.2. Источник сообщений вырабатывает три различных символа , , 
с соответственными вероятностями 0,2; 0,5; 0,3.
Вероятности появления пар заданы в табл. 2.1. Определить энтропию и сравнить её с энтропией источника, у которого отсутствуют вероятностные связи. Определить избыточность источника.
Таблица 2.1
Вероятности появления пар символов P (xi, xj)
| 
|  
|  
| 
| 
| 
| 
|
|
|
| 0,2 | 0,1 | 0,3 | 0,1 | 0,1 | 0,2 |
Решение. Энтропию найдём из выражения
. (2.10)
Для этого вычислим условные вероятности по формуле
Результаты расчёта сведём в табл. 2.2.
Таблица 2.2
Условные вероятности P (xi / xj)
| 
| 
| 
| 
| 
| 
| 
| 
| 
|
| 0,5 | 0,25 | 0,6 | 0,25 | 0,4 |
Подставляя полученные значения вероятностей 
и 
в формулу (2.10), получим:
Энтропия источника, у которого вероятностные связи между символами отсутствуют:
Энтропия источника с независимым появлением равновероятных символов равна
Избыточность с учётом статистических связей
.
Избыточность из-за неравноверояности появления символов
.
Следовательно, наличие коррелятивных (статистических) связей между символами также приводит к уменьшению энтропии и увеличению избыточности.
Пример 2.3. Источник вырабатывает два символа 
и 
с вероятностью P (A) = 0,4 и P (B) = 0,6. Определить количество возможных последовательностей, содержащих 
символов , причём 
= 4. Определить вероятность события, которое заключается в том, что в выработанной источником последовательности длиной 
содержится 
символов 
.
Решение. Число всевозможных последовательностей, которое можно составить из двух букв, по букв в каждой, N = 2 M. Число последовательностей, у которых из мест мест представлено букве , равно числу сочетаний из M элементов по :
Вероятность того, что в выработанной источником последовательности длиной 
содержится символов 
, определяется из биномиального закона
Более подробно рассмотрим работу данного источника для 
. Тогда 
Выпишем эти 16 возможных последовательностей, вычислив для каждой из них 
и 
| Возможные последовательности | 
| 
| 
| 
|
| 0,0256 | |||
| 0,154 | |||
| 0,346 | |||
| 0,346 | |||
| 0,130 |
Из таблицы видно, что источник чаще вырабатывает последовательности, содержащие одинаковое число символов A и B. И 3 символа B.
Пример 2.4. Эргодический источник с энтропией H = 2 бита вырабатывает 8 различных символов. Оценить, какую долю общего числа возможных последовательностей следует учитывать в практических расчетах, если длина последовательностей М = 30.
Решение. Всевозможное число последовательностей
Число типичных последовательностей
откуда
Следовательно, к типичным последовательностям относится только одна миллиардная доля всевозможных реализаций.
Задачи и упражнения
2.2.1. Источник, используя алфавит из двух символов х 1 и х 2, вырабатывает последовательность х 1 х 2 х 2 х 1 х 2 х 1 х 2 х 1 и т. д. Вероятностные связи в данной последовательности имеют место между четырьмя символами. Определить все возможные состояния источника и порядок их следования в данной последовательности.
Ответ: х 1 х 1 х 1 х 1 х 1 х 2 х 1 х 2 х 1 х 2 х 1 х 1 х 1 х 2 х 2 х 2 х 1 х 2 х 2 х 2 х 1 х 2 х 2 х 2;
2.2.2. Источник сообщений вырабатывает три различных символа х 1 х 2 х 3 с соответственными вероятностями 0,4; 0,5; 0,1.
Вероятности появления пар заданы в табл. 2.3. Определить энтропию и сравнить её с энтропией источника, у которого отсутствуют вероятностные связи и вероятность появления символов одинакова.
Таблица 2.3
| хi, xj | x 1 x 1 | x 1 x 2 | x 1 x 3 | x 2 x 1 | x 2 x 2 | x 2 x 3 | x 3 x 1 | x 3 x 2 | x 3 x 3 |
| P (xi, xj) | 0,1 | 0,2 | 0,1 | 0,2 | 0,3 | 0,1 |
Ответ: H (X) = 1,086 бит; 
= 1,36 бит; 
= 1,58 бит.
2.2.3. Источник сообщений вырабатывает символы a и b. Условные вероятности P (a/b) = 0,1; P (b/b) = 0,9; P (b/a) = 0,7; P (a/a) = 0,3. Определить энтропию источника.
Ответ: 
2.2.4. Источник генерирует два равновероятных символа х 1 и х 2, условные вероятности Р (х 1 /x 1) = P (x 2/ x 2) = 0,7; P (x 1 /x 2) = P (x 2 /x 1) = 0,3. Определить энтропию и избыточность источника.
Ответ: 
2.2.5. Элементы сигнала принимают два состояния m 1 и m 2. Определить количество информации (энтропию) и избыточность, если две полные и четыре условные вероятности имеют следующие значения: P (m 1) = 3/4; P (m 2) = 1/4; P (m 1/ m 1) = 2/3; P (m 2/ m 2) = 0; P (m 1/ m 2) = 1; P (m 2/ m 1) = 1/3, т. е. после m 2 всегда следует m 1.
Ответ: 
2.2.6. Вероятности появления символов источника равны Р (х 1) = 1/2, Р (х 2) = 1/4, Р (х 3) = Р (х 4) = 1/8. Коррелятивные связи имеют место между двумя соседними символами, которые описываются в табл. 2.4. Определить энтропию и избыточность источника.
Таблица 2.4
| xi, xj | P (xi, xj) | xi, xj | P (xi, xj) | xi, xj | P (xi, xj) | xi, xj | P (xi,xj) |
| x 1 x 1 | 13/32 | x 2 x 1 | 1/32 | x 3 x 1 | x 4 x 1 | 1/16 | |
| x 1 x 2 | 3/32 | x 2 x 2 | 1/8 | x 3 x 2 | x 4 x 2 | 1/32 | |
| x 1 x 3 | x 2 x 3 | 3/32 | x 3 x 3 | x 4 x 3 | 1/32 | ||
| x 1 x 4 | x 2 x 4 | x 3 x 4 | 1/8 | x 4 x 4 |
Ответ: 
2.2.7. Эргодический источник с энтропией Н (Х) = 1,9 бит вырабатывает четыре различных символа. Найти отношение числа типичных к общему числу всевозможных последовательностей длиной М = 100 символов.
Ответ: 
2.2.8. Источник вырабатывает с одинаковой вероятностью два символа
А и В. Определить количество возможных последовательностей, содержащих nА символов А, причём nА + nВ = M = 4. Определит