ЗАДАЧИ

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). Каково результирующее искажение для этого векторного квантователя?