Контрольная на тему Контрольная работа 060417

Содержание


Вопрос 2. Когда понятия энтропия и количества информации полностью совпадают? 3
Вопрос 4. В чем состоит процедура Шеннона - Фано? 3
Вопрос 5. Как, исходя из теоремы кодирования Шеннона, добиться безызбыточного кодирования? 4
Вопрос 8. Каким образом решают проблему помехоустойчивости кода? 6
Задачи 7
Задача № 2 7
Задача № 5 8
Задача № 6 10
C помощью процедуры Шеннона-Фано закодировать сообщения. Определить среднюю длину кодового слова и избыточность кода 14
Список используемой литературы 18



Вопрос 2. Когда понятия энтропия и количества информации полностью совпадают?

Понятия энтропии и количества информации совпадает тогда, когда количество информации на знак (энтропии) совпадает с количеством двоичных вопросов.
Это не ответ. Тогда я спрошу "а когда количество информации на знак (энтропии) совпадает с количеством двоичных вопросов"?
Количество информации, содержащееся в знаке, задается частотой появления этого знака: ld(1/Pi ) бит.
Тогда среднее количество информации, приходящееся на один произвольный знак, равно бит, причем .
Таким образом, понятия энтропии и количества информации совпадают, когда знаки имеют одинаковую вероятность появления.

Вопрос 4. В чем состоит процедура Шеннона - Фано?

Кодирование Шеннона-Фано является одним из самых первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано.
Главная идея этого метода - заменить часто встречающиеся символы более короткими кодами, а редко встречающиеся последовательности более длинными кодами. Таким образом, алгоритм основывается на кодах переменной длины. Для того, чтобы декомпрессор впоследствии смог раскодировать сжатую последовательность, коды Шеннона-Фано должны обладать уникальностью, то есть, не смотря на их переменную длину, каждый код уникально определяет один закодированный символ и не является префиксом любого другого кода.

А где описание процедуры Шеннона - Фано?

Результат одного отдельного альтернативного выбора может быть представлен как 0 или 1. Тогда выбору всякого знака соответствует некоторая последовательность двоичных знаков 0 или 1, то есть двоичное слово. Это двоичное слово называют кодировкой знака, а множество кодировок всех знаков источника сообщений - кодом источника сообщений. Если количество знаков представляет собой степень двойки (n = 2N) и все знаки равновероятны Pi = (1/2)N, то все двоичные слова имеют длину N и H=N=ld(n). Такие коды называют равномерными кодами.
Если ld(n) не целое число, то это означает, что ld(n) не может быть одинаковым для всех знаков количеством необходимых альтернативных выборов. Тем не менее, выбор из n знаков всегда можно осуществить с помощью N альтернативных выборов, где N-1 ld(n) N. Для этого достаточно разбивать всякое множество знаков так, чтобы количество знаков в двух получающихся подмножествах различалось не более, чем на 1. Таким образом, для источника с n знаками всегда существует кодирование словами постоянной длины N, где N-1 ld(n) N.

Вопрос 5. Как, исходя из теоремы кодирования Шеннона, добиться безызбыточного кодирования?

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