ЗАДАЧИ

3.1. Рассмотрим совместный эксперимент из задачи 2.1 с заданной совместной вероятностью . Допустим, мы наблюдаем выходы , , эксперимент .

a. Определите взаимную информацию для и в битах.

b. Определите среднюю взаимную информацию .

3.2. Предположим, что выходы , , в задаче 3.1 представляют три возможных выходных слова ДИБП. Определите энтропию источника.

3.3. Докажите, что и продемонстрируйте законность этого неравенства, построив кривые и .

3.4. и являются двумя дискретными случайными величинами с вероятностями . Покажите, что , причём равенство имеет место тогда, и только тогда, когда и статистически независимы.

[Подсказка: используйте неравенство для , чтобы доказать, что .]

3.5. Выход ДИБП состоит из возможных символов , которые появляются с вероятностями соответственно. Докажите, что энтропия источника не превышает .

3.6. Определите дифференциальную энтропию равномерно распределённой случайной величины с ФПВ

для следующих трёх случаев:

a) ;

b) ;

c) .

Обратите внимание, что из расчётов следует, что является не абсолютной, а только относительной мерой неопределённости.

3.7. ДИБП имеет алфавит из восьми символов , , с вероятностями 0,25; 0,2; 0,15; 0,12; 0,10; 0,08; 0,05 и 0,05.

a) Используйте процедуру кодирования Хаффмена, чтобы определить двоичный код для выхода источника.

b) Определите среднее число двоичных символов на символ источника.

c) Определите энтропию источника и сравните с .

3.8. ДИБП источника имеет алфавит из пяти символов , , каждый из которых появляется с вероятностью 1/5 . Вычислите эффективность равномерного двоичного кода, если:

a) Каждый символ кодируется отдельно в двоичную последовательность.

b) Два символа вместе кодируются в двоичную последовательность.

c) Три символа вместе кодируются в двоичную последовательность.

3.9. Напомним (3.2.6)

Докажите, что

a) ;

b) , где .

3.10. Пусть - геометрически распределённая случайная величина, т.е. ,

a) Найдите энтропию .

b) Известно, что , где - заданное целое положительное число. Чему равна энтропия ?

3.11. Пусть и обозначают две совместно распределённые дискретные случайные величины.

a) Покажите, что

b) Используйте полученный выше результат, чтобы показать, что . Когда наступает равенство?

c) Покажите, что и что равенство имеет место тогда, и только тогда, когда и независимы.

3.12. Две двоичные случайные величины и распределены согласно совместным вероятностям . Вычислите , , , и .

3.13. Дан марковский процесс с одношаговой памятью, т.е. такой процесс, что для всех . Покажите, что для стационарного марковского процесса энтропийная скорость определяется через .

3.14. Пусть , где обозначает детерминированную функцию. Покажите, что в общем . Когда наступает равенство?

3.15. Покажите, что .

3.16 Покажите, что для статистически независимых событий

3.17. Покажите, что в канале без шумов .

3.18. Покажите, что и что .

3.19. Пусть является случайной величиной с ФПВ и пусть - линейное преобразование , где и - две константы. Определите дифференциальную энтропию через .

3.20. Выходы , и от ДИБП с вероятностями , и преобразуются линейным преобразованием , где и - константы. Определите энтропию и поясните влияние преобразования на энтропию сигнала.

3.21. Оптимальный четырёхуровневый неравномерный квантователь для сигнала с гауссовским распределением амплитуд выдаёт четыре уровня , , и с вероятностями и .

a) Определите код Хаффмена, который кодирует отдельные уровни, и определите среднюю битовую скорость.

b) Определите код Хаффмена, который кодирует два выходных уровня вместе, и определите среднюю битовую скорость.

c) Какую минимальную битовую скорость можно получить, кодируя выходных уровней, когда .

3.22. Марковский источник первого порядка характеризуется вероятностями состояния , , и переходными вероятностями , и . Энтропия марковского источника , где - энтропия источника при условии, что он находится в состоянии .

Определите энтропию двоичного источника первого порядка, показанного на рис. 3.22, который имеет переходные вероятности и [заметим, что условные энтропии и определяются двоичными энтропийными функциями и соответственно]. Как соотносится энтропия марковского источника с энтропией двоичного ДИБП с теми же вероятностями выходных символов и ?

Рис. Р.3.22

3.23. Источник без памяти имеет алфавит с соответствующими вероятностями {0,05; 0,1; 0,1; 0,15; 0,05; 0,25; 0,3}.

a) Найдите энтропию источника.

b) Предположив, что источник квантуется согласно правилу квантования

найдите энтропию квантованного источника.

3.24. Постройте троичный код Хаффмена, использующий выходные символы 0, 1 и 2 при кодировании источника с вероятностями выходных символов алфавита {0,05; 0,1; 0,15; 0,17; 0,18; 0,22; 0,13}. Какова результирующая средняя длина кодового слова? Сравните среднюю длину кодового слова с энтропией источника. (С каким основанием будете вычислять логарифмы в выражении для энтропии для полностью осмысленного сравнения?).

3.25. Найдите код Лемпела-Зива при кодировании двоичной последовательности источника 000100100000011000010000000100000010100001000000110100000001100.

Восстановите исходную последовательность по коду Лемпела-Зива. [Подсказка: Вам потребуются два прохода двоичной последовательности, чтобы принять решение о размере словаря.]

3.26. Найдите дифференциальную энтропию непрерывной случайной величины в следующих случаях:

a) - случайная величина с экспоненциальным распределением с параметром , т.е.

b) - случайная величина с распределением Лапласа с параметром , т.е.

c) - случайная величина с треугольным законом распределения с параметром , т.е.

3.27. Можно показать, что для источника с рапределением Лапласа функция скорость-искажение с абсолютной величиной меры ошибки искажений определяется как

(См. Бергер, 1971)

a) Сколько требуется бит/отсчёт для представления выходов источника со средним искажением, не превышающим?

b) Постройте график для трёх различных значений и обсудите влияние изменения на этих кривых.

3.28. Можно показать, что если - непрерывная случайная величина с нулевым средним и дисперсией , то её функция скорость-искажение при среднеквадратичной мере искажений удовлетворяет нижней и верхней границам, определяемым неравенствами

где означает дифференциальную энтропию случайной величины (см. Ковер и Томас, 1991)

a) Покажите, что для гауссовской случайной величины верхней и нижней границ совпадают.

b) Постройте график для нижней и верхней границ для источника с лапласовским распределением при .

c) Постройте график для нижней и верхней границ для источника с треугольным распределением при .

3.29. Стационарный случайный процесс имеет автокорреляционную функцию и известно, что случайный процесс никогда не превышает по амплитуде величину 6. Сколько требуется уровней квантования амплитуды, чтобы гарантировать отношение сигнал/шум квантования не хуже 60 дБ?

3.30. Канал с аддитивным белым гауссовским шумом имеет выход , где - вход канала, а - шум с ФПВ:

Для случая, когда - гауссовский белый шум с параметрами и , определите:

a) условную дифференциальную энтропию ;

b) среднюю взаимную информацию .

3.31. ДИБП имеет алфавит из восьми символов , с вероятностями из задачи 3.7. Используйте процедуру кодирования Хаффмена для нахождения троичного кода (с символами 0, 1 и 2) для кодирования выхода источника. [Подсказка: прибавьте символ с вероятностью и группируйте по три символа на каждом шаге.]

3.32. Определите, существует ли двоичный код с кодовыми словами длиной , удовлетворяющий условию префиксности.

3.33. Рассмотрите двоичный блоковый код с кодовыми словами одинаковой длины . Покажите, что неравенство Крафта выполняется для такого кода.

3.34. Покажите, что энтропия -мерного гауссовского вектора с нулевым средним матрицей ковариаций равна

3.35. Рассмотрите ДИБП с равновероятными двоичными выходными символами (0,1). Установите меру искажений как , где - вероятность ошибки при передаче двоичных символов пользователю через двоичный симметричный канал (ДСК). Тогда функция скоросгь-искажеине равна (Бергер. 1971)

, .

Постройте график для

3.36. Вычислите функцию скорость-искажение для -ичного симметричного канала

для и 16. - вероятность ошибки.

3.37. Рассмотрите пользу от взвешенной СКО как меры искажений, определённом как

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

3.38. Рассмотрите стационарную случайную сигнальную последовательность с нулевым средним и автокорреляционной функцией

a) Определите коэффициенты предсказания для предсказателя первого порядка с минимизацией СКО для , заданной посредством соотношения

и соответствующее значение минимальной СКО .

b) Повторите (a) для предсказателя второго порядка

3.39. Рассмотрите кодирование случайных величин и которые характеризуются СФПВ , заданной как показано на рис. Р.3.39. Вычислите битовую скорость, требуемую при равномерном раздельном квантовании и (скалярное квантование) и комбинированном (векторном) квантовании . Определите разницу в битовой скорости при .

Рис. Р.3.39

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

Рис.Р.3.40

a) Найдите и .

b) Предположите, что каждая из случайных величин и квантуется с использованием четырёхуровневого равномерного квантователя. Каково результирующее искажение? Каково результирующее число бит на пару ?

c) Предположите, что вместо скалярного квантования и мы используем векторный квантователь для достижения того же уровня искажений, как в (b). Каково результирующее число битов на выходную пару источника ?

3.41. Две случайные величины и распределены равномерно в квадрате, показанном на рис. Р3.41.

Рис. Р.3.41

a) Найдите и .

b) Предположите, что каждая из случайных величин и квантуется посредством четырёхуровневого равномерного квантователя. Каково результирующее искажение? Каково результирующее число бит на пару источника ?

c) Предположите, что вместо скалярного квантования и мы используем векторный квантователь с тем же числом бит на пару источника , что в (b). Каково результирующее искажение для этого векторного квантователя?