Лабораторная №1. «Энтропия. Свойства энтропии».

Лабораторный практикум

По курсу «Теория информации и кодирование»

Для студентов специальностей

351400 «Прикладная информатика (в экономике)»

220200 «Автоматизированные системы обработки информации и управления»

075500 «Комплексное обеспечение информационной безопасности автоматизированных систем»

Астрахань 2005

Авторы: Ефремов Н.М., к.ф.-м.н., доцент кафедры ПМК,

Лежнина Ю.А., ассистент кафедры ПМК

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

Рецензент: зав. каф. ПМК проф. Попов Г.А.

Методические указания утверждены на заседании каф. ПМК

Содержание.

Содержание. 3

Общие требования к выполнению лабораторных работ. 4

Лабораторная №1. «Энтропия. Свойства энтропии». 5

Лабораторная работа №2. «Обработка алфавита введенного сообщения» 10

Лабораторная работа №3. «Оптимальное кодирование». 14

Лабораторная работа №4. «Код Хемминга». 19

Лабораторная работа №5. «Циклические коды». 22

Лабораторная работа №6. «Коды БЧХ». 27

Приложение. 32

Список литературы.. 36

Общие требования к выполнению лабораторных работ

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

При отчёте о выполнении лабораторной работы студент должен:

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

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

Лабораторная №1. «Энтропия. Свойства энтропии».

Теоретическая часть

Определение 1.1. Вероятностной схемой Х называется

Х	х₁	х₂	...	х_n
Р	р₁	р₂	...	р_n

где х_1, х_{2, …,}х_n- полная группа попарно несовместных событий, а р₁, р₂, …, р_n – соответствующие вероятности.

Определение 1.2. Количеством информации, содержащимся в сообщении х, называется . (Основание логарифма, если не оговорено противное, принимается равным 2.)

Определение 1.3. Энтропией вероятностной схемы Х, называется .

Значение функции f(t) = t∙log t при t = 0 считаем равным нулю, доопределяя её в этой точке по непрерывности. Таким образом, эта функция определена, по крайней мере, на отрезке [0;1].

Пусть имеются две схемы Х и У

Х	х₁	х₂	...	х_n
Р	р₁	р₂	...	р_n

У	у₁	у₂	...	у_m
Р	q₁	q₂	...	q_m

Определение 1.4. Энтропией произведения вероятностных схем Х и У, называется

Если схемы Х и У независимы, то энтропия произведения вероятностных схем равна сумме энтропий каждой схемы: .

Определение 1.5. Условной энтропией вероятностной схемы У относительно схемы Х называется:

где p(y_j | x_i) – условная вероятность события y_j при условии, что получено сообщение x_i.

Энтропия произведения и условная энтропия связаны между собой соотношениями:

ПРИМЕР

Задание. Событие А в каждом из n повторных независимых испытаний происходит с вероятностью р. Найти энтропию числа появлений события А. Составить соответствующую вероятностную схему. Выяснить характер изменения энтропии в зависимости от изменения р на промежутке [0;1] при значении n = 1, построив график соответствующей функции H(р). Определить её наименьшее и наибольшее значение.

Рассмотрим энтропию числа появлений события А в серии из n испытаний.

Если n=1 и Х- число появлений события А в серии из n испытаний, то

Х
Р	q	p

где q=1-p.

По определению 1.3, функция . Построим график Н(р) (рис.1):

Рис.1 График функции Н(р)

При р=0,5 функция Н(р) достигает максимума Н(0,5)=1, при р=0 или р=1 функция Н(р) достигает минимума Н(0)=Н(1)=0. Функция возрастает на промежутке [0;0,5] и убывает на отрезке [0,5;1].

Таким образом, наименьшее значение, равное нулю, энтропия рассматриваемой вероятностной схемы принимает при р=0 и при р=1, то есть в тех случаях, когда исход опыта с вероятностной схемой Х однозначно определён до его проведения. Наибольшее же значение, равное одному биту, энтропия данной схемы принимает только при р=0,5 , то есть в том случае, когда с равными вероятностями можно предполагать, что в результате испытания произойдёт или не произойдёт событие А, что соответствует наибольшей неопределённости исхода опыта с вероятностной схемой Х до его проведения. При приближении р к 0,5 , то есть с увеличением неопределённости, энтропия возрастает, а при приближении р к концам отрезка [0;1], то есть с уменьшением неопределённости, энтропия убывает. Следовательно, приведённые выше рассуждения подтверждают тезис о том, что энтропия является мерой неопределённости вероятностной схемы до проведения испытаний с ней.

практическая часть

1. Событие А в каждом из n повторных независимых испытаний происходит с вероятностью р. Найти энтропию числа появлений события А. Составить соответствующую вероятностную схему. Выяснить характер изменения энтропии в зависимости от изменения р на промежутке [0;1] при фиксированном значении n, построив график соответствующей функции H(р). Определить её наименьшее и наибольшее значение.(Значения параметра n задаются преподавателем.)

2. Событие А в каждом из независимых испытаний происходит с вероятностью р. Найти энтропию числа испытаний до первого появления события А. Составить соответствующую вероятностную схему. Выяснить характер изменения энтропии в зависимости от изменения р на промежутке (0;1], построив график соответствующей функции H(р). Определить её наименьшее и наибольшее значение.

3. В партии из n изделий имеется k (k ≤ n) стандартных. Наудачу отобраны m изделий (m ≤ n). Найти энтропию числа стандартных изделий среди отобранных. Выяснить характер изменения энтропии в зависимости от изменения k на промежутке [0; n] при фиксированных значениях n и m, построив график соответствующей функции H(k). Для этого при каждом значении k составить необходимую вероятностную схему. Определить наименьшее и наибольшее значение H(k). (Значения параметров n и m задаются преподавателем.)

4. Интенсивность простейшего потока событий равна λ. Найти энтропию числа событий из этого потока, появившихся за промежуток времени длительности t. Составить соответствующую вероятностную схему. Выяснить характер изменения энтропии в зависимости от изменения t на промежутке [0;5λ] при фиксированном значении λ, построив график соответствующей функции H(t). Определить её наименьшее и наибольшее значение.(Значения параметра λ задаются преподавателем.)

5. Интенсивность простейшего потока событий равна λ. Найти энтропию числа событий из этого потока, появившихся за промежуток времени длительности t. Составить соответствующую вероятностную схему. Выяснить характер изменения энтропии в зависимости от изменения λ на промежутке [0;3t] при фиксированном значении t, построив график соответствующей функции H(λ). Определить её наименьшее и наибольшее значение.(Значения параметра t задаются преподавателем.)

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

Вопросы

1. Количество информации в сообщении; основные свойства.

2. Количество информации в сообщении относительно другого сообщения; основные свойства.

3. Энтропия, условная энтропия; основные свойства.

4. Взаимная информация вероятностных схем; основные свойства.

Лабораторная работа №2. «Обработка алфавита введенного сообщения»

Теоретическая часть.

Так как информацию можно рассматривать как неопределённость, снимаемую при получении сообщения, то можно дать следующее определение.

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

В частном, но с практической точки зрения очень важном, случае, когда вероятностная схема Х указывает вероятности появления символов алфавита от некоторого стохастического источника сообщений, причём буквы появляются независимо друг от друга, k интерпретируется как длина сообщения, полученного от данного источника, Н(Х) – среднее количество информации, которое несёт в себе одна буква достаточно длинного сообщения, I - количество информации, которое несёт в себе сообщение из k символов.

Для случая равновероятных и взаимно независимых m символов .

Если схемы Х и У статистически зависимы, то возможно измерение количества информации о системе Х, которое дает наблюдение за системой У.

Определение 2.2. Количеством информации, которое несет схема У относительно схемы Х называется:

Определение 2.3. Информационной избыточностью называется величина

Частные виды избыточности.

1. Избыточность, обусловленная неравномерным распределением символов сообщения:

2. Избыточность, обусловленная статистической связью между символами сообщения:

3. Полная информационная избыточность: D=D_p+D_s– D_pD_s.

ПРИМЕР

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

Пусть имеется сообщение:

123423345512331234233455123312342334551233... .

Составим схему появления однобуквенных сочетаний:

Х						∑
n
w

Энтропия схемы Х равна

Составим схему появления двухбуквенных сочетаний

ХУ										∑
n
w

Энтропия, приходящаяся на одно двухбуквенное сочетание, составляет

Количество информации, которое несет появление первой буквы о второй, найдем по определению 2.3:

Найдем длину кода при равномерном кодировании однобуквенных сочетаний[1]:

m=5,

При этом возникает избыточность округления

Подсчитаем информационную избыточность:

, ,

практическая часть

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

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

Вопросы

Вероятностная схема; произведение вероятностных схем.
Количество информации в сообщении; основные свойства.
Количество информации в сообщении относительно другого сообщения; основные свойства.
Энтропия, условная энтропия; основные свойства.
Взаимная информация вероятностных схем; основные свойства.