"ТЕОРИЯ ИНФОРМАЦИИ"

(16 ч. лекций)

Цели и задачи курса

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

Введение

Понятие об информации. Различные определения информации. Содержание и практическое значение современной теории информации. Определение количества информации по Фишеру.

Темы

Определение количества информации по Шенону. Энтропия системы. Связь информационного и физического понятия энтропии. Свойства информации (энтропии). Условная энтропия и ее свойства.

Энтропия непрерывного сигнала (дифференциальная энтропия).

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

Теорема Шенона для канала без помех. Эффективные коды. Теорема Шенона для канала с помехами. Избыточность кода.

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

Итеративные коды. Адаптивное кодирование. Оценка эффективности корректирующего кодирования. Понятие о методах криптографии.

Заключение

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

Литература

1. Дмитриев В.И. Прикладная теория информации. М.: Высшая школа, 1989. 319 с.
2. Игнатов В.А. Теория информации и передачи сигналов. М.: Радио и связь, 1991. 279 с.
3. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. 576 с.

Приложение

Типовые задачи по теории информации

1. Величина Z, распределенная нормально со средним 100 и дисперсией 25, измерена двумя независимыми приборами; первый имеет дисперсию результата измерения 0.04, а второй 0.25. Оцените количество полученной в этих двух измерениях информации:
   1) по Фишеру, 2) по Шенону.
    
2. Зависимость у(х) аппроксимируется полиномом у(х) = b₁ + b₂ x². Выполнить измерения у(х) в точках х = 0,1,2,... Оценка дисперсии у для всех случаев S_y² = 5. Постройте информационную матрицу Фишера для коэффициентов b₁, b₂.
    
3. В Петрозаводске 280000 жителей. Какое минимальное количество вопросов, требующих ответа "да" или "нет", необходимо, чтобы однозначно найти одного жителя.
    
4. Орудие стреляет по удаленной цели. При каждом выстреле она поражается с вероятностью р = 0.1. Разведка может только один раз проверить, поражается ли цель хоть один раз. Через некое количество выстрелов k следует провести проверку, чтобы она дала максимальное количество информации?
    
5. В лотерее N билетов, из них k выигрышных. Студент купил M билетов и после розыгрыша сообщил вам, что выиграл (но, возможно, и не на один билет). Какое количество информации вы получили?
    
6. Бросаются одновременно две игральные кости. Определить количество информации, содержащееся в сообщении о том, что произведение числа выпавших очков четно.
    
7. Два стрелка, для которых вероятности попадания в мишень равны соответственно 0.6 и 0.7, производят по одному выстрелу. В результате оказалось, что мишень поражена. Какое количество информации содержится в этом сообщении?
    
8. Источник генерирует знак z₁ с вероятностью 0.8 и z₂ с вероятностью 0.2. Какова энтропия источника?
    
9. Найти число значений m случайной величины Y, все значения которой одинаково вероятны, при котором энтропия Y будет равна энтропии случайной величины X, вероятности значений которой заданы таблицей:

   xj	x1	x2	x3	x4	x5	x6	x7	x8
   p(xj)	1/2	1/4	1/8	1/16	1/32	1/64	1/128	1/128

   
   
10. Символы азбуки Морзе могут появиться в сообщении с вероятностями: для точки - 0.51, для тире - 0.31, для промежутка между буквами - 0.12, между словами - 0.06. Определить среднее количество информации в сообщении из 500 символов данного алфавита, считая, что связь между последовательными символами отсутствует.
     
11. Имеется n одинаковых монет, одна из которых легче. Сколько взвешиваний на чашечных весах необходимо и достаточно, чтобы ее найти?
     
12. Во сколько раз средняя мощность сигнала с равномерным распределением значений отсчетов должна быть больше мощности сигнала с нормальным распределением отсчетов при условии, что оба сигнала имеют одинаковые дифференциальные энтропии?
     
13. В информационном канале используется алфавит с четырьмя различными символами. Длительности всех символов одинаковы и равны t = 1 мкс. Определить пропускную способность канала при отсутствии шумов.
     
14. По каналу в одну секунду передается 10⁶ символов (скорость передачи 10⁶ бод). Символы "0" и "1" поступают на вход канала с равной вероятностью. Определите пропускную способность канала при следующих условиях:
           1) символ "1" воспринимается как 1 с вероятностью 0.9, и как 0 с вероятность 0.1, так же искажается и символ "0";
           2) в пакете из 4-x символов с вероятностью 0.1 искажается один символ.
     
15. Источник создает последовательность из алфавита в 16 равновероятных и статистически независимых букв. При передаче по каналу с шумом буквы искажаются так, что четверть всех букв принимается неправильно, причем все ошибки одинаково вероятны. Определить среднюю информацию в принятой букве относительно переданной.
     
16. Известно, что из 100 изготовленных деталей в среднем 10 деталей имеют дефекты. Для выявления брака используется метод, дающий всегда отрицательный эффект, если деталь изготовлена с браком. Если брак отсутствует, то деталь признается годной лишь в 80% случаев. Какое количество информации о качестве детали можно получить в среднем по результату такого метода отбраковки?
     
17. Двоичный стирающий канал является одним из наиболее простых типов канала с шумом. В нем переданные символы могут быть "стертыми", но никогда не могут быть приняты ошибочно. Найти среднее количество информации, переносимое одним символом в таком канале, если вероятность стирания равна 0.1 и не зависит от переданного символа; вероятности символов на входе одинаковы.
     
18. Известно, что жители некоторого города А всегда говорят правду, а жители соседнего города Б всегда обманывают. Наблюдатель Н знает, что он находится в одном из этих двух городов, но не знает, в каком именно. Какое наименьшее количество вопросов, требующих ответа "да" или "нет" ему нужно, чтобы определить:
           а) в каком городе он находится;
           б) в каком городе живет его собеседник (в каждом пункте можно с одинаковой вероятностью встретить жителей обоих городов);
           в) то и другое вместе? (Все предположения равновероятны.)
     
19. Имеются три города (А, Б и В), причем жители А во всех случаях говорят правду, жители Б - только неправду, а жители В через раз отвечают на вопросы верно и неверно. Наблюдатель Н хочет выяснить, в каком городе он находится и в каком городе живет встреченный им человек. Сколько вопросов ему потребуется задать этому встречному, если на все вопросы он отвечает лишь "да" или "нет"? (Все предположения равновероятны.)
     
20. Имеется 12 монет одного достоинства; 11 из них имеют одинаковый вес, а одна - фальшивая - отличается по весу от остальных (причем неизвестно, легче она или тяжелее настоящих). Каково наименьшее число взвешиваний на чашечных весах без гирь, которое позволяет обнаружить фальшивую монету и выяснить, легче она, чем остальные монеты, или тяжелее?
     
21. Источник генерирует знак z₁ с вероятностью 0.8 и z₂ с вероятностью 0.2. Постройте эффективные коды Шенона-Фано и Хаффмана для последовательности из трех знаков z_i, z_j, z_k. Каково среднее число символов на знак? Сравните с энтропией источника.
     
22. Радиотехническое устройство состоит из 5 блоков (А, Б, В, Г, Д). Блок А в среднем выходит из строя 1 раз в 100 дней, блок Б - 1 раз в 25 дней, В - 1 раз в 5 дней, Г - 1 раз в 4 дня и Д - 1 раз в 2 дня. Контрольный прибор позволяет за одно измерение проверить работоспособность в целом любой комбинации блоков. Как нужно проводить контроль, чтобы затратить на поиски неисправного блока в среднем минимальное количество проверок? Найти это среднее значение.
     
23. Постройте проверочную матрицу к порождающим:

    

24. Код Хемминга (7,4) имеет порождающую матрицу:

    

    a) зашифруйте число 13;
    б) исправьте ошибку в кодовых словах и найдите передаваемое число
    0110001
    0111010
     
25. Циклический код порождается многочленом g(x) = х³ + х + 1;
    а) закодируйте числа "7" и "10";
    б) найдите и исправьте ошибку в принятых кодовых комбинациях:
    0111000;
    0111001.
    Какие числа были закодированы?
     
26. Сообщения источника с производительностью 850 бит/с поступают на вход двоичного симметричного канала с вероятностью искажения p = 0.05. Длительность символов сигнала в канале t = 10^-3 с. Достаточна ли пропускная способность канала для передачи всей информации, поступающей от источника?
     
27. Расшифруйте сообщение, закодированное кодом Вижинера с использованием русского алфавита из 32 букв без пробелов. Ключевое слово "праздник". ЯЯИМХОМЦППТЩЛЮЬEЬСРЩКЩИ
     
28. Сообщение кодируется алгоритмом RSA. Открытый ключ (55, 23), закрытый ключ (55, 7). Получено число 27, какое число было отправлено?
     
29. Фотопластинка размером 5 x 5 см² имеет разрешение 100 штрихов/мм. Каким способом: фотографическим или голографическим на ней можно записать больше информации? Оцените максимальное количество информации, которое можно записать на ней. В чем преимущество голографической записи?
     

Составила профессор КИИСиФЭ Луизова Л.А.