ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
ВОРОНЕЖСКИЙ ИНСТИТУТ МВД РОССИИ Кафедра высшей математики Думачев В.Н. ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ Воронеж - 2016-06 УДК 519.72 Д82 Рассмотрены и одобрены на заседании кафедры высшей математики протокол №3 от 22.11.2011 г. Рассмотрены и одобрены на заседании методического совета протокол №3 от 26.11.2011 г. Д82 Думачев В.Н. Теория информации и кодирования - Воронеж: Воронежский институт МВД России, 2012. – 200 с. Учебник содержит систематическое изложение всего материала по курсу "Теория информации и кодирования" и предназначен для выполнения типового расчета, проведения практических занятий, лабораторных работ и самоподготовки для курсантов радиотехнического факультета, обучающихся по специальности 090302.65 - Информационная безопасность телекоммуникационных систем. Д 1203021300 - 39 1(III) УДК 519.72 221 - 08 c Воронежский институт МВД России, 2015 Оглавление 1 Энтропия и информация 5 1.1 Энтропия и информация дискретных источников сообщений . . . . . 5 1.2 Энтропия непрерывных источников сообщений . . . . . . . . . . . . . 10 1.3 Условная энтропия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Задачи информационного поиска . . . . . . . . . . . . . . . . . . . . . 20 1.5 Взаимная информация . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.6 Кодирование информации методом Шеннона . . . . . . . . . . . . . . 36 1.7 Избыточность сообщения . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2 Каналы связи 41 2.1 Пропускная способность каналов связи . . . . . . . . . . . . . . . . . . 41 2.2 Теоремы Котельникова и Шеннона . . . . . . . . . . . . . . . . . . . . 58 2.3 Теория массового обслуживания . . . . . . . . . . . . . . . . . . . . . . 61 2.3.1 Цепи Маркова . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.3.2 Работа телефонного коммутатора . . . . . . . . . . . . . . . . . 64 2.3.3 Система массового обслуживания с ожиданием . . . . . . . . . 72 2.4 Стандарт сотовой связи GSM . . . . . . . . . . . . . . . . . . . . . . . 74 2.5 Стандарты зписи CD и DVD . . . . . . . . . . . . . . . . . . . . . . . . 80 3 Теория помехоустойчивого кодирования 83 3.1 Коды Хэмминга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.2 Циклические коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.2.1 Исправление 1 ошибки . . . . . . . . . . . . . . . . . . . . . . . 96 3.2.2 Исправление 2 ошибок . . . . . . . . . . . . . . . . . . . . . . . 102 3.3 Коды Рида-Миллера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.4 Сверточные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 3.4.1 Блочное чередование . . . . . . . . . . . . . . . . . . . . . . . . 109 3.4.2 Теория автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.4.3 Сверточные коды . . . . . . . . . . . . . . . . . . . . . . . . . . 115 3.4.4 Коррекция ошибок сверточным кодом . . . . . . . . . . . . . . 117 3.4.5 Алгоритм Витерби . . . . . . . . . . . . . . . . . . . . . . . . . . 124 3.5 Турбокоды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 3.6 Вычисления в полях Галуа . . . . . . . . . . . . . . . . . . . . . . . . . 137 3 4 Оглавление 3.7 Коды БЧХ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 3.7.1 Прямой алгебраический метод PGZ . . . . . . . . . . . . . . . . 144 3.7.2 Коды БЧХ над GF (2 3 ) . . . . . . . . . . . . . . . . . . . . . . . 145 3.7.3 Коды БЧХ над GF (2 4 ) . . . . . . . . . . . . . . . . . . . . . . . 150 3.7.4 Расширенный алгоритм Евклида . . . . . . . . . . . . . . . . . 159 3.8 Совершенные недвоичные коды . . . . . . . . . . . . . . . . . . . . . . 161 3.8.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 3.8.2 Совершенный код в GF (2 2 ) . . . . . . . . . . . . . . . . . . . . . 161 3.8.3 Совершенный код в GF (2 3 ) . . . . . . . . . . . . . . . . . . . . . 163 3.9 Коды Рида-Соломона . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 3.9.1 Исправление 1 ошибки несовершенного кода [n, k] q = [7, 5] 8 166 3.9.2 Исправление 2 ошибок несовершенного кода [n, k] q = [7, 3] 8 172 3.10 Алгоритм Берлекемпа-Месси . . . . . . . . . . . . . . . . . . . . . . . . 181 3.11 Расширенный алгоритм Евклида для кода RS . . . . . . . . . . . . . . 183 4 Квантовая информация 187 4.1 Основы квантовых вычислений . . . . . . . . . . . . . . . . . . . . . . 187 4.2 Матрица плотности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 4.3 Редуцированные матрицы плотности . . . . . . . . . . . . . . . . . . . 206 4.4 Разложение Шмидта . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 4.5 Зацепленные квантовые состояния . . . . . . . . . . . . . . . . . . . . 221 4.6 Квантовые алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 4.6.1 Алгоритм Дойча . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 4.6.2 Квантовое плотное кодирование . . . . . . . . . . . . . . . . . . 227 4.6.3 Квантовая телепортация . . . . . . . . . . . . . . . . . . . . . . 232 4.7 Коррекция ошибок в квантовых каналах информации . . . . . . . . . 233 4.8 Клонирование квантовой информации . . . . . . . . . . . . . . . . . . 236 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 Глава 1 Энтропия и информация 1.1 Энтропия и информация дискретных источников сообщений Теорией информации называется наука, изучающая количественные закономерности, связанные с получением, передачей, обработкой и хранением информации. Одной из задач теории информации является отыскание наиболее экономных методов кодирования, позволяющих передать заданную информацию с помощью минимального количества символов. Эта задача решается как при отсутствии, так и при наличии искажений (помех) в канале связи. Другая типичная задача теории информации ставится следующим образом: имеется источник информации (передатчик), непрерывно вырабатывающий информацию, и канал связи, по которому эта информация передается в другую инстанцию (приемник). Какова должна быть пропускная способность канала связи для того, чтобы канал «справлялся» со своей задачей, т.е. передавал всю поступающую информацию без задержек и искажений? Ряд задач теории информации относится к определению объема запоминающих устройств, предназначенных для хранения информации, к способам ввода информации в эти запоминающие устройства и вывода ее для непосредственного использования. Любое сообщение, с которым мы имеем дело в теории информации, представляет собой совокупность сведений о некоторой физической системе. Очевидно, если бы состояние физической системы было известно заранее, не было бы смысла передавать сообщение. Сообщение приобретает смысл только тогда, когда состояние системы заранее неизвестно, случайно. Поэтому в качестве объекта, о котором передается информация, будем рассматривать некоторую физическую систему X, для которой событием будет возможность оказаться в том или ином состоянии, т. е. систему, которой заведомо присуща какая-то степень неопределенности. Интуитивно понятно, что если вероятность появления события равна 1, то само появление этого события для нас информации никакой не несет (мы и так знали, что оно появится). Например, если кто то вам скажет, что занятия в 5 6 Глава 1. Энтропия и информация нашем институте начинаются в 9-00, то для вас это не будет новостью, вероятность этого события равна 1 и вы не получите в этом сообщении никакой дополнительной информации о системе образования в нашем вузе. Рассмотрим другой крайний случай: допустим, стало известно, что всем двоечникам в нашем ВУЗе будут давать дополнительный отпуск и надбавку к стипендии. Вот это уже новость. Эту новость все будут друг другу пересказывать, опубликуют в газетах, возможно даже приедет телевидение. Ведь появление такого события очень маловероятно, поэтому оно очень значимо с точки зрения информации и дает огромные знания относительно того, как (оказывается) организован учебный процесс в нашем институте. Из этого примера видно, что вероятность появления события должна играть ключевую роль в формальном определении информации. В математике за меру информации принимают величину I = log 2 1 p = − log 2 p. Заметим, что в теории информации используется двоичный (битовый) логарифм lb a = log 2 a, а при практических вычислениях на ЭВМ используется натуральный логарифм log e a = ln a. Переход от натурального основания к битовому осуществляется по формуле lb a = log 2 a = log e a log e 2 = ln a ln 2 Информация о системе дается знанием того, какое именно из состояний примет данная система при проведении испытания и вычисляется по формуле I = − lbp. Для случайной величины x с плотностью f(x) I(x) = − lbf(x). Единица измерения информации называется бит (1 bit или 1 b). Бит – информация, хранящаяся в 1 ячейке с двумя значениями (0,1): x 0 1 p 0.5 0.5 Тогда I 0 = − lbp 0 = − log 2 1 2 = log 2 2 = 1 bit, I 1 = − lbp 1 = − log 2 1 2 = log 2 2 = 1 bit. 1.1. Энтропия и информация дискретных источников сообщений 7 Пример 1.1. Какая информация содержится в сообщении о том, что монетка упала гербом? Решение. Вероятность того, что монетка упадет гербом, равна p = 1 2 . Поэтому, проведение данного испытания дало нам I = − lbp = − lb 1 2 = lb2 = 1 bit т.е. 1 бит информации. N Пример 1.2. В ящике 10 гранат, из которых 8 без взрывателя. Из ящика наудачу выбирается 3 гранаты. Какое количество информации содержится в сообщении о том, что все 3 выбранные гранаты оказались без взрывателя? Решение. Определим вероятность выбора из ящика 3 гранат без взрывателя: p = 8 10 · 7 9 · 6 8 = 7 15 = 0.467. Количество информации в сообщении определяется по формуле I = lb 1 p = lb 15 7 = 1.1 bit. N Пример 1.3. В группе 20 курсантов, среди которых 4 отличника, 6 хорошистов, 7 троечников, остальные – двоечники. По списку наудачу отобраны 5 курсантов. Какое количество информации содержится в сообщении о том, что среди отобранных курсантов 3 отличника, 1 хорошист и 1 троечник? Решение. Приведем обозначения задачи в соответствие с формулой обобщенной гипергеометрической вероятности. Согласно условию задачи: N=20. Определим состав группы: имеем выбираем Отличники n 1 = 4 m 1 = 3 Хорошисты n 2 = 6 m 2 = 1 Троечники n 3 = 7 m 3 = 1 Двоечники n 4 = 3 m 4 = 0 Всего N=20 M=5 Вспоминая, что C m n = n! m!(n − m)! , по формуле гипергеометрической вероятности получим P = C m 1 n 1 · C m 2 n 2 · C m 3 n 3 · C m 4 n 4 C M N = C 3 4 · C 1 6 · C 1 7 · C 0 3 C 5 20 = 7 17 · 19 · 2 = 0.011. 8 Глава 1. Энтропия и информация Тогда количество информации есть I = lb 1 P = − lb (P ) = − lb0.011 = 6.528 bit. N Задача 1.1. 1. В коробке 7 одинаковых деталей, причем 3 из них окрашены. Наудачу извлечены 4 изделия. Какое количество информации содержится в сообщении о том, что среди двух извлеченных изделий 2 два окрашенных. 2. В партии из 10 деталей имеется 8 стандартных. Наудачу отобраны 3 детали. Какое количество информации содержится в сообщении о том, что среди них 1 бракованная. 3. В отделе работают 6 мужчин и 4 женщины. По табельным номерам наудачу отобраны 7 человек. Какое количество информации содержится в сообщении о том, что среди отобранных лиц окажутся 3 женщины. 4. На складе имеются 15 мониторов, причем 10 из них Samsung. Какое количество информации содержится в сообщении о том, что среди 5 взятых наудачу мониторов 3 окажутся Samsung. 5. В группе 12 курсантов, среди которых 8 отличников. По списку наудачу отобраны 9 курсантов. Какое количество информации содержится в сообщении о том, что среди отобранных курсантов 5 отличников. 6. В коробке 5 одинаковых купюр, причем 3 из них помечены. Наудачу извлечены 4 купюры. Какое количество информации содержится в сообщении о том, что среди извлеченных купюр 2 помеченых. 7. В конверте среди 10 фотокарточек находится 2 разыскиваемых. Из конверта наудачу извлечены 8 карточек. Какое количество информации содержится в сообщении о том, что среди них оказалась 1 нужная. 8. В урне 7 белых и 5 черных шаров. Из урны вынимают сразу 5 шаров. Какое количество информации содержится в сообщении о том, что 2 из них будут белыми. 9. Среди 10 лотерейных билетов 3 выигрышных. Наудачу взяли 5 билетов. Какое количество информации содержится в сообщении о том, что среди них 2 выигрышных. 10. Во время гололеда на трассе М4-ДОН столкнулись 6 автомобилей, причем 3 из них - Mersedes. Инспектор ДПС наудачу оштрафовал 3 водителей. Какое количество информации содержится в сообщении о том, что среди них 2 будут водителями Mersedes. 1.1. Энтропия и информация дискретных источников сообщений 9 11. Во время летнего отпуска 4 человека полетели в Турцию, а 6 - на Тайвань. Внезапно прибывший начальник решил провести совещание и вызвал из отпуска 5 человек. Какое количество информации содержится в сообщении о том, что среди них 2 прибудут из Турции. 12. В урне 3 белых, 4 черных и 5 красных шаров. Из урны вынимают сразу три шара. Какое количество информации содержится в сообщении о том, что все шары будут разного цвета. 13. В урне 5 белых, 6 черных и 7 красных шаров. Из урны вынимают сразу три шара. Какое количество информации содержится в сообщении о том, что все шары будут белые. 14. Имеются изделия четырех сортов, причем число изделий каждого сорта равно n 1 = 2, n 2 = 3, n 3 = 1, n 4 = 3. Для контроля наудачу берутся 5 изделий. Какое количество информации содержится в сообщении о том, что среди них m 1 = 2 первосортных, m 2 = 1 второго, m 3 = 0 третьего и m 4 = 2 четвертого сорта. 15. ППС задержали 6 хулиганов, причем 3 из них без российского гражданства. Наудачу вызывают 3 задержанных. Какое количество информации содержится в сообщении о том, что среди них 2 будут без гражданства. 16. На складе из 10 деталей имеется 8 нелицензионных. Наудачу отобраны 3 детали. Какое количество информации содержится в сообщении о том, что среди них 1 нелицензионная. 17. В отделе работают 8 мужчин и 4 женщины. По табельным номерам наудачу отобраны 7 человек. Какое количество информации содержится в сообщении о том, что среди отобранных лиц окажутся 4 женщины. 18. Через границу проезжает 15 КАМазов, причем 10 из них с наркотиками. Какое количество информации содержится в сообщении о том, что среди 5 проверенных наудачу КАМазов 3 окажутся с наркотиками. 19. В бандгруппе 15 боевиков, среди которых 8 вакхабитов. По списку наудачу отобраны 9 боевиков. Какое количество информации содержится в сообщении о том, что среди отобранных боевиков 5 вакхабитов. 20. В ящике 6 гранатометов, причем 3 из них российского производства. Наудачу извлечены 2 гранатомета. Какое количество информации содержится в сообщении о том, что среди двух извлеченных гранатометов 2 российских. 21. В конверте среди 10 фотокарточек находится одна разыскиваемая. Из конверта наудачу извлечены 5 карточек. Какое количество информации содержится в сообщении о том, что среди них окажется нужная. 10 Глава 1. Энтропия и информация 22. На позициях стояло 8 БМП и 5 БТР. Установкой ГРАД было поражено сразу 5 единиц боевой техники. Какое количество информации содержится в сообщении о том, что 2 из них будут БМП. 23. Среди 10 олигархов было 3 депутата. Наудачу взяли 5 олигархов. Какое количество информации содержится в сообщении о том, что среди них 2 депутата. 24. В камере 3 таджика, 4 грузина и 6 азербайджанцев. Из камеры наудачу вызывают трех человек. Какое количество информации содержится в сообщении о том, что все вызываемые будут разной национальности. 25. В камере 3 таджика, 4 грузина и 6 азербайджанцев. Из камеры наудачу вызывают трех человек. Какое количество информации содержится в сообщении о том, что все вызываемые будут грузины. 26. Имеются изделия четырех сортов, причем число изделий каждого сорта равно n 1 = 4, n 2 = 3, n 3 = 5, n 4 = 3. Для контроля наудачу берутся 5 изделий. Какое количество информации содержится в сообщении о том, что среди них m 1 = 1 первосортных, m 2 = 1 второго, m 3 = 0 третьего и m 4 = 3 четвертого сорта. 1.2 Энтропия непрерывных источников сообщений Поскольку возможные состояния x = (x 1 , x 2 , ..., x n ), случайно принимаемые системой, образуют полную группу несовместных событий, то в дальнейшем все изучаемые системы мы будем описывать некоторой случайной величиной x с плотностью вероятностей f (x) = X p i δ(x − x i ). В этом случае, за меру информации, содержащейся в значении x непрерывной случайной величины x, принимают выражение I = − lbf(x). Напомним, что математическое ожидание (среднее значение) случайной величины x вычисляется по формуле M(x) = hxi = x = Z x · f(x)dx. Если случайная величина x является дискретной, то M(x) = Z x · f(x)dx = X Z x · p i δ(x − x i )dx = X x i p i = ( x · p). Здесь мы воспользовались фильтрующим свойством δ-функции Z f (x)δ(x − a)dx = f(a). 1.2. Энтропия непрерывных источников сообщений 11 Очевидно, сведения, полученные о системе, будут, вообще говоря, тем ценнее и содержательнее, чем больше была неопределенность системы до получения этих сведений («априори»). В качестве меры априорной неопределенности системы (или случайной величины x) в теории информации применяется специальная характеристика, называемая энтропией. Энтропией H(x) называется среднее количество информации, содержащееся в случайной величине x H(x) = M(I) = hIi = Z I · f(x)dx. Подставляя сюда I = − lbf(x), для непрерывной случайной величины получим H(x) = − Z f · lbf dx, а для дискретной: H(x) = − X p i lbp i причем f lbf = 0, если f = 0. Свойства энтропии. 1. H(x) ≥ 0; 2. H(x) ≤ lb|x|; 3. Если x и y независимы, то H(xy) = H(x) + H(y) 4. Обработка информации не приводит к увеличению энтропии H(g(x)) ≤ H(x). Энтропия является мерой неопределенности случайной величины x. Чем больше энтропия, тем больше неопределенности в распределении случайной величины. Условная энтропия случайной величины x относительно случайной величины y дается выражениями H(x/y) = − X p(x/y) lbp(x/y), H(x/y) = − Z f (x/y) lbf (x/y)dx. Математическое ожидание условной энтропии M [H(x/y)] называется средней условной энтропией: H y (x) = M y [H(x/y)] = X p(y)H(x/y) = − X X p(y)p(x/y) lbp(x/y), H y (x) = − Z Z f (y)f (x/y) lbf (x/y)dxdy. 12 Глава 1. Энтропия и информация Количество информации о случайной величине x, которое может быть получено в результате наблюдения значений y, измеряется разностью энтропии H(x) и ее средней условной энтропии относительно y: I y (x) = H(x) − H y (x). Если после получения сообщения о дискретной случайной величине y значение x полностью определено, то H y (x) = 0 и I y (x) = H(x). Если x и y независимы, то H(x) = H y (x) и I y (x) = 0. Отметим свойство симметрии условной информации I y (x) = I x (y). Энтропия H(x), как мы увидим в дальнейшем, обладает рядом свойств, оправдывающих ее выбор в качестве характеристики степени неопределенности. Во-первых, она обращается в нуль, когда одно из состояний системы достоверно, а другие – невозможны. Во- вторых, при заданном числе состоянии она обращается в максимум, когда эти состояния равновероятны, а при увеличении числа состояний – увеличивается. Наконец, и это самое главное, она обладает свойством аддитивности, т. е. когда несколько независимых систем объединяются в одну, их энтропии складываются. Определение 1. Среди всех законов распределения, ограниченных на интервале, наибольшую энтропию имеет равномерное. Пример 1.4. Энтропия равномерного, на конечном интервале, распределения x = (x 1 , x 2 , ..., x n ) есть H(x) = lb n. Действительно, поскольку вероятность всех событий данного распределения одинакова и равна p i = 1 n , то H(x) = − n X i=1 p i · lb p i = − n X i=1 1 n · lb 1 n = 1 n · lb n n X i=1 1 = 1 n · lb n · n = lb n. N 1.2. Энтропия непрерывных источников сообщений 13 0 |