Шаг 4. Находим среднюю энтропию, приходящуюся на 1 букву сообщения. - раздел Образование, Теория информации и кодирования Как Описано В Теоретическом Введении, Средняя Энтропия Находится По Формулам ...
Как описано в теоретическом введении, средняя энтропия находится по формулам 1 и 2. В обоих случаях нужно найти вероятности появления букв или двухбуквенных комбинаций..
Вероятности можно найти приближенно, исследуя частоты.
Для получения по этим частотам приближенных значений (оценок) вероятностей появления букв в тексте нужно сложить все частоты учитываемых букв и поделить частоту появления каждой буквы на эту сумму. Это удобно сделать в дополнительном столбце, расположенном рядом со столбцом, содержащим частоты появлений отобранных символов - букв.
До расчета средней энтропии появления букв без учета статистических связей между ними нужно найти слагаемые в формуле суммы и, наконец, просуммировать их. Это довольно просто. Напомним только, что log2X = lnX / ln2. Можно также воспользоваться имеющейся в Excel стандартной функцией log(1 аргумент, 2 аргумент). Здесь 1 аргумент – аргумент логарияма, 2 аргумент – основание логарифма, в данном случае 2.
Для расчета оценок вероятностей появления двухбуквенных комбинаций нужно повторить вышеописанные шаги обработки информации, начиная с преобразования символов в числа. В отличие от предыдущего в этом случае в числа нужно преобразовывать не отдельные символы, а комбинации из двух символов. Здесь нужно выбрать такой способ преобразования, чтобы каждой комбинации их двух символов было поставлено в соответствие определенное число, связанное именно с этой комбинацией.
Этого можно достичь, если считать буквы символами некоторой системы счисления, а двухбуквенные комбинации – двухразрядными числами, записанными в этой системе счисления. Основание системы счисления в этом случае будет равно числу букв в алфавите. например, большинство языков, использующих латиницу, имеют в алфавите всего 26 букв. Следовательно, двухбуквенные комбинации на этом языке можно считать двухразрядными 26-ричными числами. Известно, что общее число чисел, которое может быть записано в общем случае n-разрядным m-ичным числом равно mn. В данном случае это число = 262 = 676.
Сразу оговоримся, что, если в алфавите более 255 букв (языки с иероглифической письменностью), возможностей табличного процессора Excel для расчета энтропии с учетом статистической зависимости между соседними буквами становятся недостаточными и в этом случае расчет энтропии мы производить не будем.
Если же учитываемых букв в алфавите меньше 256, каждую встреченную в тексте двухбуквенную комбинацию, которую мы теперь понимаем как число, записанное в недесятичной системе счисления, нужно заменить на соответствующее число, записанное в десятичной системе счисления.
Для этого используется формула, которая студентами должна быть известна еще из школьного курса информатики:
, (3)
где В10 – результат преобразования исходного m-ичного числа Аm в десятичную систему счисления;
n – количество разрядов исходного числа, записанного в m-ичной системе счисления;
m – основание системы счисления;
ai – разряды числа Аm = ana(n-1)….a1 , записанные в виде десятичных чисел.
В нашем случае n=2, а m= 26 (в некоторых вариантах латиницы).
Из вышесказанного следует такой план действий:
· отдельные буквы преобразуем не в коды, а номера их следования в алфавите (номера будем отсчитываю не с 1, а с 0):
· для образования уникального для каждой двухбуквенной комбинации числа используем формулу 3.
Преобразование символа в его номер в алфавите удобно выполнять при помощи функции ВПР.
Напомним, что функция ВПР предназначена для поиска одних значений по другим. Она имеет 3 аргумента: первый – для указания искомой величины, второй – для указания местоположения таблицы, в первом столбце которой ищется искомая величина; третий – для указания столбца из клетки которого выбирается результат поиска. Более подробное описание функции ВПР смотрите в приложении 3.
Создадим еще один рабочий лист (Лист4). В нем на месте, под которым на исходном листе нет символов, создадим таблицу, в первом столбце которого будут находиться учитываемые символы алфавита, а справа во втором столбце – их номера по порядку, начиная с номера 0.
Теперь можно заняться преобразованием символов в их номера в алфавите. Для этого можно использовать, например, такую формулу:
A1 ← = если ( еошибка ( впр (………!A1; $BR$1 : $BS$26; 2 ) ); -1; впр (………!A1; $BR$1:$BS$26 ; 2 ) )
Функция еошибка в этой формуле предназначена для проверки возможности найти в таблице букву, а по ней ее номер. Если аргумент функции еошибка - функция впр - букву в таблице не находит, она принимает значение ошибки, и тогда функция еошибка принимает логическое значение Истина. В этой ситуации функция если становится равной своему второму аргументу, т.е. -1. Ранее мы условились считать значение -1 признаком неверных данных. Если же функция еошибка равна логическому значению Ложь, это означает что ее аргумент – функция впр - нашла букву в таблице, что приводит к приданию функции если значения ее третьего аргумента, т.е. впр, которая в этом случае равна номеру буквы в алфавите.
Эту формулу надо размножить на все клетки, которые соответствуют клеткам с буквами исходного листа.
В результате мы только получаем вместо букв их номера и -1 там, где находятся пустые клетки или другие неучитываемые символы. Теперь можно приступить к образованию из двух соседних букв, понимаемых как 2 разряда 26-тиричного (в данном примере) числа, соответствующего ему десятичного числа. Для этого нужно воспользоваться формулой 3.
Но прежде, для размещения этих числе создадим еще один новый рабочий лист (Лист5).
Расчетная формула, преобразующая двухбуквенную комбинацию в число, может быть следующей:
А1 ← =ЕСЛИ ( ИЛИ ( Лист4!A1 < 0; Лист4!B1 < 0); -1; Лист4!A1 * 26 + Лист4!B1 )
Здесь функция если предназначена для проверки того, что в соседних клетках находятся номера букв (признаком небуквы является число -1). Условие проверки сформировано при помощи функции или.
Эту формулу нужно размножить на ту же область, что занимают буквы в исходном листе, кроме последнего его столбца, т.к. комбинации из двух букв берутся из двух соседних столбцов.
Последующие действия почти совпадают с аналогичными действиями, ранее выполненными при расчете энтропии в случае неучена статистических связей между буквами.
Отличия заключаются в следующем:
· Интервал карманов должен содержать числа от -1 до m2 , где m – число учитываемых букв алфавита (в нашем примере m = 26, значит m2=676).
· После нахождения при помощи инструмента Гистограмма частот появления двухбуквенных комбинаций, некоторые частоты окажутся равными нулю. Из можно не подавлять фильтром, однако при расчете слагаемых pilog2pi нужно использовать функцию если для принудительного приравнивания таких слагаемых к 0, поскольку напрямую такие выражения Excel вычислить не может.
· Полученная энтропия будет относиться не к одной, а к двум буквам. Для приведения же результат к одной букве следует поделить его на 2.
Все темы данного раздела:
Курс лекций
Эффективная организация обмена информации приобретает все большее значение как условие успешной практической деятельности людей. Объем информации, необходимый для нормального функционирования совре
Определение понятия информация
Слово информация происходит от латинского informare – изображать, составлять понятие о чем-либо, осведомлять.
Информация наряду с материей и энергией является первичны
Фазы обращения информации
Система управления состоит из объекта управления, комплекса технических средств, состоящего из компьютера, входящих в его состав устройств ввода-вывода и хранения информации, устройств сбора переда
Некоторые определения
Данные или сигналы, организованные в определенные последовательности, несут информацию не потому, что они повторяют объекты реального мира, а по общественной договоренности о кодировании, т.е. одно
Меры информации
Прежде, чем перейти к мерам информации, укажем, что источники информации и создаваемые ими сообщения разделяются на дискретные и непрерывные. Дискретные сообщения слагаются из конечно
Геометрическая мера
Определение количества информации геометрическим методом сводится к измерению длины линии, площади или объема геометрической модели данного носителя информации или сообщения. По геометрическим разм
Аддитивная мера (мера Хартли)
Аддитивную меру можно рассматривать как более удобную для ряда применений комбинаторную меру. Наши интуитивные представления об информации предполагают, чтобы количество информации увеличивалось пр
Энтропия и ее свойства.
Существует несколько видов статистических мер информации. В дальнейшем будем рассматривать только одну их них ─ меру Шеннона. Мера Шеннона количества информации тесно связана с понятие
Энтропия и средняя энтропия простого события
Рассмотрим подробнее понятие энтропии[1] в разных вариантах, так как оно используется в шенноновской теории информации. Энтропия - мера неопределенности некоторого опыта. В простейшем случае его ис
Метод множителей Лагранжа
Если нужно найти экстремум (максимум, минимум или седловую точку) функции n переменных f(x1, x2, …, xn), связанных k<n условиями зависимости, котор
Вывод формулы среднего значения энтропии на букву сообщения
Предположим, имеется сообщение, состоящее из n букв: , где j=1, 2, …, n ─ номера букв в сообщении по порядку, а i1, i2, … ,in номера букв
Энтропия сложного события, состоящего из нескольких зависимых событий
Теперь предположим, что элементы сообщения (буквы) взаимозависимы. В этом случае вероятность появления последовательности из нескольких букв не равна произведению вероятностей появ
Избыточность сообщения
Как отмечалось, энтропия максимальна, если вероятности сообщений или символов, из которых они составлены, одинаковы. Такие сообщения несут максимально возможную информацию. Если же сообщение имеет
Содержательность информации
Мера содержательности[5] обозначается cont (от английского Content ─ содержание).
Содержательность события I выражается через функцию меры содержательности его о
Целесообразность информации
Если информация используется в системах управления, то ее полезность разумно оценивать по тому эффекту, который она оказывает на результат управления. В связи с этим в 1960 г. советским ученым А.А.
Динамическая энтропия
Здесь энтропия рассматривается как функция времени. При этом преследуется цель – избавиться от неопределенности, т.е. добиться положения, когда энтропия равна 0. Такая ситуация характерна для задач
Энтропия непрерывных сообщений
Исходные данные часто представляются в виде непрерывных величин, например, температура воздуха или морской воды. Поэтому представляет интерес измерение количества содержащейся в таких сообщениях ин
Первый случай (значения сл. величины ограничены интервалом)
Случайная величина a ограничена интервалом [b,c]. В этом случае определенный интеграл ее плотности распределения вероятностей (дифференциального закона распределения вероятностей) на
Второй случай (заданы дисперсия и математическое ожидание сл. величины)
Предположим теперь, что область определения значений случайной величины не ограничена, но задана ее дисперсия D и математическое ожидание M. Заметим, что дисперсия прямо пропорциональ
Квантование сигналов
Непрерывные сигналы – носители информации – представляют собой непрерывные функции непрерывного аргумента – времени. Передача таких сигналов может выполняться при помощи непрерывных каналов связи,
Виды дискретизации (квантования)
Наиболее простыми и часто используемыми видами квантования являются:
· квантование по уровню (будем говорить просто квантование);
· квантование по времени (будем называть
Критерии точности представления квантованного сигнала
В результате обратного преобразования из непрерывно-дискретной формы в непрерывную получается сигнал , отличающийся от исходного на величину ошибки . Сигнал называется воспроизводящей функц
Элементы обобщенной спектральной теории сигналов
Обобщенная спектральная теория сигналов объединяет методы математического описания сигналов и помех. Эти методы позволяют обеспечить требуемую избыточность сигналов с целью уменьшения влияния помех
О практическом использовании теоремы Котельникова
Возможную схему квантования-передачи-восстановления непрерывного сигнала можно представить в виде, изображенном на рис. 2.5.
Рис. 2.5. Возможная схема квантования-передачи-
Выбор периода дискретизации (квантования по времени) по критерию наибольшего отклонения
В результате квантования по времени функции x(t) получается ряд значений x(t1), x(t2), … квантуемой величины x(t) в дискретные моменты времени t
Интерполяция при помощи полиномов Лагранжа
Воспроизводящая функция в большинстве случаев рассчитывается по формуле: , где − некоторые функции. Эти функции обычно стремятся выбрать так, чтобы
. (2.14)
В этом случае ,
Оценка максимального значения ошибки при получении воспроизводящей функции на основе полинома Лагранжа
Найдем погрешность интерполяции. Представим ее виде:
, (2.16)
где K(t) – вспомогательная функция, которую надо найти.
Для произвольного t* имеем:
(
Обобщение на случай использования полиномов Лагранжа произвольного порядка
Интерполяция полиномами n-го порядка рассматривается аналогично предыдущим случаям. При этом наблюдается значительное усложнение формул. Обобщение приводит к формуле следующего вида:
Выбор интервала дискретизации по критерию среднеквадратического отклонения
Рассмотрим случай дискретизации случайного стационарного эргодического процесса x(t) с известной корреляционной функцией . Восстанавливать будем при помощи полиномов Лагранжа. Наиболее часто
Оптимальное квантование по уровню
Рисунком 2.13 иллюстрируется принцип квантования по уровню[7].
Рис. 2.13. Квантование по уровню.
Это квантование сводится к замене значения исходного сигнала уровн
Расчет неравномерной оптимальной в смысле минимума дисперсии ошибки шкалы квантования.
Рис. 2.19. Обозначения
Зададимся теперь числом шагов квантования n, границами интервала (xmin, xmax
Общие понятия и определения. Цели кодирования
Кодирование − операция отождествления символов или групп символов одного кода с символами или группами символов другого кода.
Код (франц. code), совокупность зна
Элементы теории кодирования
Некоторые общие свойства кодов[8].
Рассмотрим на примерах. Предположим, что дискретный источник без памяти, т.е. дающий независимые сообщения – буквы – на выходе, име
Неравенство Крафта
Теорема 1. Если целые числа n1, n2, …, nk удовлетворяют неравенству
, (3.1)
существует префиксный код с алфавитом объемом m,
Теорема 2.
Формулировка. Пусть задан код с длинами кодовых слов n1, n2, … , nk и с алфавитом объема m. Если код однозначно декодируем, неравенство Крафта удовле
Теорема 3.
Формулировка. При заданной энтропии H источника и объеме m вторичного алфавита существует префиксный код с минимальной средней длиной nср min
Теорема о минимальной средней длине кодового слова при поблочном кодировании (теорема 4)
Рассмотрим теперь случай кодирования не отдельных букв источника, а последовательностей из L букв.
Теорема 4.
Формулировка. Для данного дискретного источника
Оптимальные неравномерные коды
Определения.
Неравномерными называют коды, кодовые слова которых имеют различную длину.
Оптимальность можно понимать по-разному, в зависимости о
Лемма 1. О существовании оптимального кода с одинаковой длиной кодовых слов двух наименее вероятных кодируемых букв
Формулировка. Для любого источника с k>=2 буквами существует оптимальный (в смысле минимума средней длины кодового слова) двоичный код, в котором два наименее вероятных сло
Лемма 2. Об оптимальности префиксного кода нередуцированного ансамбля, если префиксный код редуцированного ансамбля оптимален
Формулировка. Если некоторый префиксный код редуцированного ансамбля U'является оптимальным, то соответствующий ему префиксный код исходного ансамбля т
Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа.
Наибольший эффек
Параметры эффективности оптимальных кодов
Таких параметров 2: коэффициент статистического сжатия и коэффициент относительной эффективности. Оба параметра характеризуют степень уменьшения средней длины кодового слова. При этом средняя длина
Особенности эффективных кодов.
1. Букве первичного алфавита с наименьшей вероятностью появления ставится в соответствие код с наибольшей длиной (лемма 1), т.е. такой код является неравномерным (с разной длиной кодовых слов). В р
Помехоустойчивое кодирование
Как следует из названия, такое кодирование предназначено для устранения вредного влияния помех в каналах передачи информации. Уже сообщалось, что такая передача возможна как в пространстве, так и в
Простейшие модели цифровых каналов связи с помехами
Свойство помехоустойчивых кодов обнаруживать и исправлять ошибки в сильной степени зависит от характеристик помех и канала передачи информации. В теории информации обычно рассматривают две простые
Расчет вероятности искажения кодового слова в ДСМК
Положим, кодовое слово состоит из n двоичных символов. Вероятность неискажения кодового слова, как несложно доказать, равна:
.
Вероятность искажения одного символа (однокра
Общие принципы использования избыточности
Для простоты рассмотрим блоковый код. С его помощью каждым k разрядам (буквам) входной последовательности ставится в соответствие n-разрядное кодовое слова. Количество разного вида
Граница Хэмминга
Граница Хэмминга Q, определяет максимально возможное количество разрешенных кодовых слов равномерного кода при заданных длине n кодового слова и корректирующей способности кода КСК
Избыточность помехоустойчивых кодов
Одной из характеристик кода является его избыточность. Увеличение избыточности в принципе нежелательно, т.к. увеличивает объемы хранимых и передаваемых данных, однако для борьбы с искажениями избыт
Линейные коды
Рассмотрим класс алгебраических кодов, называемых линейными.
Определение: Линейными называют блоковые коды, дополнительные разряды которых образуются
Определение числа добавочных разрядов m.
Для определения числа добавочных разрядов можно воспользоваться формулой границы Хэмминга:
.
При этом можно получить плотноупакованный код, т.е. код с минимальной при заданных пар
Построение образующей матрицы
Линейные коды обладают следующим свойством: из всего множества 2k разрешенных кодовых слов, образующих, кстати, группу, можно выделить подмножества из k слов, обладающих св
Порядок кодирования
Кодовое слово КС получается путем умножения матрицы информационной последовательности ||X|| на образующую матрицу ||OM||:
||KC1*n|| = ||X
Порядок декодирования
В результате передачи кодового слова через канал оно может быть искажено помехой. Это приведет к тому, что принятое кодовое слово ||ПКС|| может не совпасть с исходным ||КС||.
Двоичные циклические коды
Вышеприведенная процедура построения линейного кода имеет ряд недостатков. Она неоднозначна (МДР можно задать различным образом) и неудобна в реализации в виде технических устройств. Этих недостатк
Некоторые свойства циклических кодов
Все свойства циклических кодов определяются образующим полиномом.
1. Циклический код, образующий полином которого содержит более одного слагаемого, обнаруживает все одиночные ошибки.
Построение кода с заданной корректирующей способностью
Существует несложная процедура построения кода с заданной корректирующей способностью. Она состоит в следующем:
1. По заданному размеру информационной составляющей кодового слова длиной
Матричное описание циклических кодов
Циклические коды можно, как и любые линейные коды, описывать с помощью матриц.
Вспомним, что KC(X) = gm(X)*И(Х) .
Вспомним также на примере порядок умножения пол
Выбор образующего полинома
Ясно, что полиномы кодовых слов КС(Х) должны делиться на образующий полином g(X) без остатка. Циклические коды относятся к классу линейных. Это означает, что для этих кодов существует
Виды каналов передачи информации
Рассмотрим каналы, отличающиеся по типу используемых в них линий связи.
1. Механические, в которых для передачи информации используется перемещение каких-либо твердых, жид
Пропускная способность каналов связи
Эта тема является одной из центральных в теории информации. В ней рассматриваются предельные возможности каналов связи по передаче информации, определяются характеристики каналов, влияющие на эти в
Пропускная способность дискретного канала связи с шумом
Исследуем теперь пропускную способность дискретного канала связи с шумом.
Существует большое количество математических моделей таких каналов. Простейшей из них является канал с независимой
Типичные последовательности и их свойства
Будем рассматривать последовательности статистически независимых букв. Согласно закону больших чисел, наиболее вероятными будут последовательности длиной n, в которых при количества N
Основная теорема Шеннона для дискретного канала с шумом
Формулировка
Для дискретного канала в шумом существует такой способ кодирования, при котором может быть обеспечена безошибочная передача все информации, поступающей от источ
Обсуждение основной теоремы Шеннона для канала с шумом
Теорема Шеннона для канала с шумом не указывает на конкретный способ кодирования, обеспечивающий достоверную передачу информации со скоростью, сколь угодно близкой с пропускной способности канала с
Пропускная способность непрерывного канала при наличии аддитивного шума
Рассмотрим следующую модель канала:
1. Канал способен пропускать колебания с частотами ниже Fm.
2. В канале действует помеха n(t), имеющая нормальный (гау
Шаг 2. Ввод текстовых файлов в Excel-таблицу с разбиением каждой строки текста на отдельные символы.
При вводе ранее сохраненного текстового файла следует указать тип файла *.*. Это позволит во время выбора видеть в списке все файлы. Укажите свой файл. После этого на экран будет выведено окно М
Шаг 8. Напишем отчет о выполненной работе с описанием всех вычислений и о том, как они выполнялись. Прокомментируйте результаты.
Результаты вычислений представьте в виде таблицы:
<Язык 1>
<Язык
Подключение возможности использования нестандартных функций.
Программное управление приложениями, входящими в состав Microsoft Office, осуществляется при помощи так называемых макросов.
Слово Макрос – греческого происхождения. В перево
Создание нестандартной функции
Перед созданием нестандартных функций нужно открыть файл в рабочей книгой, содержащей информацию, которую нужно обработать с применением этих нестандартных функций. Если ранее эта рабочая книга был
Запись голоса и подготовка сигнала.
Запись начинается и заканчивается нажатием кнопки Record (рис. 5), помеченной красный кружком. В процессе записи кнопка Recоrd выглядит вдавленной и более светлой (подсвеченной).
Импорт текстовых данных в Excel
Двойным кликом откройте текстовый файл с экспортированные из программы Wavosaur данными (рис. 23).
Рис. 23. Примерный вид данных
Видно, что экспортированные
Квантование по уровню сводится к замене значения исходного сигнала уровнем того шага, в пределы которого это значение попадает.
Квантование по уровню – необходимое условие преобразования непрерывного сигнала в цифровую форму. Однако одного лишь квантования по уровню для этого недостаточно – для преобразования в цифровую фор
Коды Хаффмена
На этом алгоритме построена процедура построения оптимального кода, предложенная в 1952 году доктором Массачусетского технологического института (США) Дэвидэм Хаффменом[17]:
5) буквы перви
Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа.
Наибольший эффек
Параметры эффективности оптимальных кодов
Таких параметров 2: коэффициент статистического сжатия и коэффициент относительной эффективности. Оба параметра характеризуют степень уменьшения средней длины кодового слова. При этом средняя длина
Особенности эффективных кодов.
5. Букве первичного алфавита с наименьшей вероятностью появления ставится в соответствие код с наибольшей длиной (лемма 1), т.е. такой код является неравномерным (с разной длиной кодовых слов). В р
Выполнение работы
Лабораторная работа №4 выполняется под управлением специально написанной управляющей программы. Эта управляющая программа написана на языке Visual Basic 6. Исполняемый файл программы носит и
Построение образующей матрицы
Линейные коды обладают следующим свойством: из всего множества 2k разрешенных кодовых слов можно выделить подмножества из k слов, обладающих свойством линейной независимост
Порядок кодирования
Кодовое слово КС получается путем умножения матрицы информационной последовательности ||X|| на образующую матрицу ||OM||:
||KC1*n|| = ||X
Порядок декодирования
В результате передачи кодового слова через канал оно может быть искажено помехой. Это приведет к тому, что принятое кодовое слово ||ПКС|| может не совпасть с исходным ||КС||.
Выполнение работы
Лабораторная работа №5, как и работа №4, выполняется под управлением управляющей программы, написанной на алгоритмическом языке Visual Basic 6. Исполняемый файл программы носит имя Помехо
Новости и инфо для студентов