Математические модели для источников информации

Август 22, 2022

Главная
Разное
Математические модели для источников информации

Содержание

2. Простейший тип дискретного источника – это такой, который выдаёт последовательность букв (символов), выбираемых из определенного алфавита.
3. Чтобы конструировать математическую модель для дискретного источника предположим, что каждый символ алфавита {x1, x2, …, xL}
4. Рассмотрим две математические модели для дискретных источников. Предположим, что символы выходной последовательности источника статистически независимы, т.е.
5. Если отдельные выходные символы дискретного источника статистически взаимозависимы, как, например, в английском тексте, мы можем сконструировать
6. Аналоговый источник выдает сигнал x(t), который является реализацией случайного процесса X(t). Предположим, что X(t) - стационарный
7. Где X{(n/2W)} - отсчёты процесса X(t) взятые со скоростью Найквиста fs=2W, 1/c. Используя теорему отсчётов, мы
8. Заметим, что выходные отсчёты стационарного источника обычно непрерывны, и, следовательно, их нельзя представить в цифровой форме
9. «ЛОГАРИФМИЧЕСКАЯ МЕРА ИНФОРМАЦИИ»
10. Чтобы разработать подходящую меру для информации, рассмотрим две дискретные случайные величины X и Y с возможными
11. Заметим, что если X и Y статистически не зависят друг от друга, выбор Y=yj не даёт
12. Подходящая мера информации, которая удовлетворяет указанным условиям, - это логарифм отношения условной вероятности: P(X=xi | Y=yj)=P(xi
13. Это значит, что количество информации, полученное при появлении события Y=yj относительно события X=xi определяется как: названа
14. Единица измерения I(xi;yj) определяется основанием логарифма, в качестве которой обычно выбирается или 2, или е. Когда
15. Когда случайные величины X и Y статистически независимы, то P(xi|yj)=P(xi), следовательно, I(xi; yj)=0. С другой стороны,
16. Но (2) как раз определяет информацию X=xi Исходя из этих соображений, её называют собственной информацией события
17. Пример 1 Предположим, что имеется дискретный источник, который выдаёт двоичную цифру 0 или 1 с равной
18. Теперь предположим, что последовательные цифры на выходе источника статистически независимы, т.е. источник не имеет памяти. Рассмотрим
19. Она выдаётся на временном интервале Kτx. Таким образом, логарифмическая мера количества информации обладает желаемыми свойствами аддитивности,
20. вернёмся к определению взаимной информации, определяемой (1), и умножим числитель и знаменатель отношения вероятностей на p(yj)
21. Таким образом, информация, содержащаяся в выборе события Y=yj относительно события X=xi идентична информации, содержащейся в выборе
22. Пример 2 Предположим, что X и Y -двоичные {0,1} случайные величины, представляющие вход и выход канала
23. Определим, сколько информации об X=0 и X=1 содержится в событии Y=0 . Из заданных вероятностей получим:
24. Рассмотрим несколько частных случаев. В первом, когда, p0=p1=0 канал называют каналом без шумов и I(0;0)=log22=1бит. Следовательно,
25. Помимо определения взаимной информации и собственной информации полезно определить условную собственную информацию как: (5) Тогда, комбинируя
26. Мы интерпретируем I(xi|yj) как собственную информацию о событии X=xi после наблюдения события Y=yj . Из условия
27. «Средняя взаимная информация и энтропия»
28. Зная взаимную информацию, связанную с парой событий (xi;yj), которые являются возможной реализацией двух случайных величин X
29. Таким образом получим: как среднюю взаимную информацию между X и Y (1)
30. Видно, что I(X;Y)=0, когда X и Y статистически независимы и P(xi;yj)=P(xi)P(yj) Важным свойством средней взаимной информации
31. Аналогично определим среднюю собственную информацию, обозначенную H(X) (2) Если X представляет собой алфавит возможных символов источника,
32. В общем случае H(X) ≤ logn при любых заданных вероятностях символов источника. Другими словами, энтропия источника
33. Пример 1 Рассмотрим двоичный источник, который выдаёт последовательности независимых символов, причём выходной кодовый символ «0» с
34. Рисунок 1. Энтропия двоичного источника
35. Среднее значение условной собственной информации называется условной энтропией и определяется как: Мы интерпретируем H(X|Y) как неопределённость
36. Из условия I(X,Y) ≥0 следует, что H(X)≥H(X|Y) и H(Y)≥H(Y|X), причём равенство имеет место тогда, и только
37. т.е. имевшейся до наблюдения, тогда I(X;Y) определяет взаимную информацию (уменьшение среднего значения неопределённости, имеющейся относительно X
38. Пример 2 Определим H(X|Y) и I(X,Y) для канала с двоичным входом и выходом, рассмотренного выше в
39. Рис.3.1. Средняя взаимная информация для двоичного симметричного канала Рис. 3. Условная энтропия для двоичного симметричного канала
40. Когда условную энтропию H(X|Y) рассматривают применительно к каналу с входом и выходом Y, то называют ненадёжностью
41. Результаты, приведённые выше, легко обобщаются на случай произвольного числа случайных величин. В частности, предположим, что мы
42. Тогда энтропия определяется как: Поскольку совместную вероятность P(X1X2…,Xk) можно выразить в виде: P(x1x2…xk)≡P(x1)P(x2|x1)P(x3|x1x2)…P(xk|x1x2…xk-1) то следует (7)
43. С учётом результата H(X)≥H(X|Y) где X=Xm и Y=X1X2…Xm-1 из (7) следует причём равенство имеет место тогда,
44. «Кодирование для дискретных источников без памяти»
45. Предположим, что ДИБП выдает буквы или символы каждые τx секунд. Каждый символ выбирается из конечного алфавита
46. Кодовые слова фиксированной длины Сначала рассмотрим схему блокового кодирования, которая сопоставляет уникальный ряд из R двоичных
47. когда L равно целой степени основания 2, и R=[log2 L]+1 когда не равно целой степени основания
48. R будем называть скоростью кодирования. Она определяет число символов кодера на один символ источника. Поскольку, H(X)
49. Если log L>>1, эффективность такой схемы кодирования высока. С другой стороны, если L мало, эффективность кода
50. Теперь среднее число символов кода на символ источника R=N/J , и, таким образом, неэффективность кодирования сокращается
51. Методы кодирования, не приводят к искажениям, так как кодирование символов источника или блоков таких символов в
52. Предположим, что мы пытаемся уменьшить скорость кодирования R путем смягчения условия однозначности процесса кодирования. Предположим, что
53. Теорема кодирования источника I Пусть X - это ансамбль символов ДИБП с конечной энтропией H(X). Блоки
54. Исходя из этой теоремы мы видим, что среднее число бит на символ источника требуемое для кодирования
55. Кодовые слова переменной длины
56. Если символы источника неравновероятны, более эффективный метод кодирования сводится к использованию кодовых слов переменной длины. Примером
57. Таблица 1. Коды переменной длины Для примера предположим, что выходные символы ДИБП а1 а2 а3 а4
58. Код II в табл. 1 обеспечивает однозначное и немедленное декодирование. Удобно представлять кодовые слова этого кода
59. Заметим, что ни одно кодовое слово этого кода не является префиксом (началом) другого кодового слова. В
60. Другими словами, нет кодовых слов длины l l. Это свойство делает кодовые слова немедленно декодируемыми. Код
61. Наша главная цель – создать систематическую процедуру для конструирования однозначных декодирующих кодов переменной длины, эффективных в
62. Неравенство Крафта Необходимым и достаточным условием существования двоичного кода с кодовыми символами длины n1 ≤ n2
63. Выберем некоторый узел порядка в качестве первого кодового слова C1. Этот выбор устраняет конечных узлов. От
64. Таким образом, создали кодовое дерево, которое встроено в полное дерево из узлов, как иллюстрируется на рис.
65. Рис. 3. Конструирование двоичного дерева, встроенного в полное дерево
66. Чтобы доказать, что (2) является необходимым условием, мы заметим, что в дереве порядка n = nL
67. Теорема кодирования источника II. Пусть X- ансамбль символов двоичного источника без памяти с конечной энтропией H(X)
68. Используя неравенство ln x ≤ x-1 , из (5) находим: Верхняя граница в (4) может быть
69. Если умножить обе части неравенства (6) на pk и просуммировать по 1 ≤ k ≤ L.
70. Алгоритм кодирования Хаффмена
71. Хаффмен (1952) разработал алгоритм кодирования переменной длины, основанный на знании априорных вероятностей символов P(xi), i=1,2,…L .
72. Пример 1. Рассмотрим ДИБГТ с семью возможными символами, имеющими вероятности выбора, иллюстрируемое ниже. Среднее число двоичных
73. Заметим, что полученный код не единственно возможный. Например, на предпоследнем шаге процедуры кодирования мы имеем равный
74. Рис. 2. Альтернативный код для ДИБП в примере 1
75. Пример 2. В качестве второго примера определим код Хаффмена для выхода ДИБП, иллюстрируемый на рис. 3.
76. Алгоритм кодирования переменной длины (Хаффмена), генерирует префиксный код, имеющий среднюю длину. Однако вместо посимвольного кодирования более
77. так как энтропия J -символьного блока от ДИБП равна JH(X), и RJ - среднее число бит
78. Рис. 3.Код Хаффмена для примера 2
79. Пример 3 Выход ДИБП состоит из символов x1, x2 и x3 с вероятностями 0,45, 0,35 и
80. Таблица 1. Код Хаффмена
81. Таблица 2. Код Хаффмена для кодирования пар символов
82. Дискретные стационарные источники
83. Рассмотрим дискретные источники, для которых последовательность символов выхода является статистически зависимой. Мы ограничим наше исследование источниками,
84. Оценим энтропию некоторой последовательности символов от стационарного источника. Энтропия блока случайных переменных X1 ,X2 … Xk
85. Мы определяем количество информации стационарного источника как энтропию на символ в (2) в пределе при ,
86. Этот результат также установлен ниже. Наше изложение использует подход Галлагера (1968). Во-первых, мы покажем, что: H(Xk|X1X2…Xk-1)≤
87. Во-вторых, мы имеем результат: Hk (X) ≥ H(Xk|X1X2...Xk-1) B-третьих, по определению Hk(X): что приводит к: Hk
88. Поскольку Hk (X) и условная энтропия H(Xk|X1X2…Xk-1) не отрицательны и не возрастающие (с ростом k), оба
89. Для фиксированного k в пределе для (10) при j→∞ получаем: H∞ (X) ≤ H(Xk|X1X2...Xk-1) Но (11)
90. Предположим, что мы имеем дискретный стационарный источник, который даёт J символов с энтропией на символ HJ(X).
91. Деля обе части (13) на J, мы получаем границы для среднего числа R=RJ /J бит на
92. Алгоритм Лемпела-Зива
93. Алгоритм кодирования Хаффмена приводит к оптимальному кодированию источника в том смысле, что кодовые слова удовлетворяют префиксному
94. В отличие от алгоритма кодирования Хаффмена алгоритм кодирования Лемпела-Зива разработан так, чтобы быть независимым от статистики
95. В алгоритме Лемпела-Зива последовательность с выхода дискретного источника делится на блоки переменной длины, которые называются фразами.
96. Рассмотрим бинарную последовательность : 10101101001001110101000011001110101100011011. Деление последовательности, как описано выше, производит следующие фразы: 1,0,10, 11,01,00. 100,
97. Таблица 1. Словарь для алгоритма Лемпела-Зива
98. Ячейки словаря пронумерованы последовательно, начиная с 1 и далее, в данном случае до 16, что является
99. Декодер источника создает идентичную таблицу на приемном конце системы связи и соответственно декодирует полученную последовательность. Можно
100. Алгоритм Лемпела-Зива широко используется при сжатии компьютерных файлов. «Сжимающие» и «разжимающие» программы (утилиты) в операционной системе
101. «Кодирование для аналоговых источников - оптимальное квантование»
102. Аналоговый источник выдаёт непрерывный сигнал x(t), который является выборочной функцией случайного процесса X(t). Если X(t) является
103. Применяя теорему отсчётов, выход аналогового источника преобразуется в эквивалентную дискретную во времени последовательность отсчётов. Затем отсчёты
104. Следовательно, если мы имеем L уровней, нам необходимы R=log2L бит/отсчёт (если L есть степень числа 2)
105. Квантование амплитуд дискретизированного во времени сигнала обеспечивает сжатие данных, но это также приводит к некоторому искажению
106. Функция скорость-искажение R(D) Под термином «искажение» мы понимаем некоторую меру разности между фактическими выборками источника {xk}
107. Используемое для определения ошибки квантования при ИКМ: (2) Где p- принимает значения из ряда положительных целых
108. На выходе источника имеет место случайный процесс, и, следовательно, n отсчётов Xn в являются случайными величинами.
109. где I(X,X)- средняя взаимная информация между X и X.Вообще, скорость R(D) уменьшается при увеличении D или,
110. «Функция скорость-искажение для гауссовского источника без памяти»
111. Теорема: Функция скорость-искажение для гауссовского источника без памяти (Шеннон, 1959). Минимальная скорость кодирования, необходимая для представления
112. Заметим, что (1) подразумевает, что, если искажение, D ≥ σx² никакой информации передавать не нужно. Конкретно
113. Рис. 1. Функция скорость-искажение для непрерывного по амплитуде гауссовского источника без памяти Функция скорость-искажение R(D)источника связана
114. Теорема: Кодирование источника с заданной мерой искажения (Шеннон, 1959). Существует схема кодирования, которая отображает выход источника
115. Вернёмся к результату в (1) для функции скорость-искажение гауссовского источника без памяти. Если мы поменяем функциональную
116. Верхняя граница для функции скорость-искажение
117. Теорема: Верхняя граница для R(D) Функция скорость-искажение непрерывного по амплитуде источника без памяти с нулевым средним
118. Доказательство этой теоремы дано Бергером (1971). Подразумевается, что гауссовский источник требует максимальную скорость кодирования среди всех
119. Существует также нижняя граница функции скорость-искажение. Её называют нижней границей Шеннона для среднеквадратической ошибки искажения, и
120. Следовательно, функция скорость-искажение для произвольного источника без памяти с непрерывной амплитудой ограничена сверху и снизу: R*(D)
121. так что нижняя граница R*(D) в (3) уменьшается до Rg(D).Теперь, если выразить D*(R) в децибелах и
122. В таблице 1 даны четыре типа ФПВ, которые являются моделями распределения, обычно используемыми для источника сигнала.
123. Таблица 1. Дифференциальная энтропия и сравнение скорости и искажений четырёх распространённых ФПВ для моделей сигнала
124. Следовательно, эквивалентный дискретный во времени гауссовский источник является источником без памяти. Поэтому функция скорость-искажение для белого
125. Скалярное квантование
126. При кодировании источника квантователь может быть оптимизирован, если известна ФПВ уровней сигнала на входе квантователя. Например,
127. В общем, оптимальный квантователь минимизирует D путём оптимального выбора выходных уровней и входного диапазона для каждого
128. У равномерного квантователя выходные уровни определяются как для амплитуды входного сигнала в диапазоне , где ∆-
129. В этом случае минимизация D выполняется с учётом параметра размера шага ∆. Путём дифференцирования D по
130. Для среднеквадратичного критерия ошибки, кода f(x)=x², Макс(1960) рассчитал оптимальный размер шага ∆опт и минимальное значение среднеквадратической
131. Таблица 1. Оптимальные размеры шага при равномерном квантовании гауссовских случайных величин Видим, что минимальная среднеквадратическая ошибка
132. Результирующее искажение: (4) снова минимизируется путём оптимального выбора Необходимые условия для минимальных искажений можно получить дифференцированием
133. Соответствующие уравнения, определяющие Таким образом, является центроидом области p(x) между xk-1 и xk. Эти уравнения могут
134. Таблица 2. Оптимальный 4-уровневый квантователь для гауссовской случайной величины Dмин=0,1175 10lgDмин = - 9,3Дб
135. Таблица 3. Оптимальный 8-уровневый квантизатор для гауссовской случайной величины (Макс, 1960) Dмин=0,03454 10lgDмин = - 14,62Дб
136. Таблица 4. Сравнение оптимальных равномерного и неравномерного квантизаторов для гауссовской случайной величины (Макс, 1960; Паез и
137. Поучительно построить кривые зависимости минимальных искажений от битовой скорости R=log2L бит на отсчёт (на символ) источника
138. Рис. 1. Кривые зависимости искажение-скорость для гауссовского источника без памяти с дискретным временем
139. Для примера: оптимальный четырёхуровневый неравномерный квантователь для распределённой по Гауссу амплитуды приводит к вероятностям p1=p4=0,1635 для
140. Таблица 5. Энтропия выхода оптимального неравномерного квантователя гауссовской случайной величины (Макс, 1960)
141. Из этого обсуждения мы заключаем, что качество квантователя можно анализировать, когда известна ФПВ непрерывного выхода источника.
142. Дискретные выходы квантователя характеризуются рядом вероятностей {pk}, которые можно использовать для расчёта эффективных неравномерных кодов для
143. Если мы сравним характеристики оптимального неравномерного квантователя с функцией искажение-скорость, мы найдём, например, что для искажения
144. Тема: Векторное представление сообщений и сигналов. Теория построения инфокоммуникационных систем и сетей
145. В современной теории передачи информации для описания, анализа и преобразования сообщений и сигналов широко используется геометрическое
146. Для определения расстояния между элементами пространства используют некоторый функционал d, который обычно берется таким, чтобы удовлетворялись
147. Сигналы можно алгебраически суммировать друг с другом. При этом результатом сложения является также сигнал. Сигналы можно
148. 4. Любой элемент пространства можно умножить на любой элемент, принадлежащий скалярному множеству ,на котором определены операции
149. Векторное пространство определяет простые алгебраические взаимосвязи между своими элементами. В частности, любой сигнала как вектор может
150. Любой сигнал можно описать действительной или комплексной функцией, определенной на интервале , который может быть и
151. Для N-мерного линейного пространства действительных или комплексных чисел , j = 1, 2,…, норма определяется как
152. Для N-мерного линейного пространства действительных или комплексных чисел с учетом (3) и(5) , (6) а для
153. В линейном пространстве можно ввести понятие скалярного произведения двух элементов, которое весьма полезно при рассматривании линейных
154. В функциональном анализе доказывается, что в пространстве со скалярным произведением можно ввести норму, удовлетворяющую соотношению ,
155. Векторное представление применимо как для детерминированных функций, так и для случайных. В последнем случае скалярные произведения
156. Тема: Дискретизация непрерывных сообщений с учетом их характеристик и реальных способов восстановления. Теория построения инфокоммуникационных систем
157. Под дискретизацией понимается процесс представления непрерывного сообщения , заданного на интервале ,совокупностью координат . В общем
158. При линейных процессах представления и восстановления выражения (1) и (2) можно представить в виде (3) (4)
159. В данном случае используется система весовых функций , , где – дельта-функция. При этом, как это
160. Для модели сообщения с ограниченным спектром решение указанных задач содержится в теореме Котельникова, на основании которой
161. Они образуют ортогональную на бесконечном интервале Систему функций. Любую функцию можно получить на выходе идеального фильтра
162. Теорему Котельникова можно распространить и на случайный сигнал. Тогда она формулируется следующим образом: для случайного процесса
163. Теорема Котельникова дает предельные соотношения для идеализированных условий, среди которых следует отметить ограниченность спектра по частоте
164. Ограничение спектра сообщения частотой путем фильтрации приводит к погрешности восстановления, относительный средний квадрат которой (7) т.
165. т. е. она представляет собой с точностью до несущественного множителя сумму бесконечного числа «копий» спектра исходного
166. При восстановлении сообщения идеальным фильтром нижних частот с полосой пропускания возникает ошибка, относительный квадрат которой с
167. При этом (10) и, следовательно, предварительная фильтрация сообщения с целью ограничения его спектра является целесообразной. Заметим,
168. При линейной интерполяции (рис. 2,б) используются два отсчета. Функции а Рис. 2. Диаграммы, иллюстрирующие ступенчатую (а)
169. Относительный средний квадрат погрешности интерполяции зависит от нормированной корреляционной функции исходного процесса , способа интерполяции и
170. При заданной погрешности интерполяции формы (11) и (12) используется для нахождения частоты дискретизации. Расчеты показывают, что
171. В данном случае координаты сообщения в (3) представляют собой коэффициенты некоторого ряда. При решении рассматриваемой задачи
172. Пусть – случайный процесс с нулевым математическим ожиданием и непрерывной корреляционной функцией Тогда можно показать, что
173. Собственные функции являются ортогональными и определяются уравнениями с точностью до постоянного множителя, который можно выбрать таким,
174. Выражение (15) позволяет находить число координат N, при котором обеспечивается заданная погрешность дискретного представления. Разложение случайного
175. В данном случае в качестве весовых функций используют линейные комбинации дельта-функций: (16) где – число сочетания
176. В данном случае координатами являются мгновенные значения непрерывного сигнала в некоторых точках опроса, неравноотстоящих друг от
177. Известны различные способы адаптивной дискретизации, отличающиеся алгоритмом формирования существенных отсчетов и видов служебной информации. Простейшим алгоритм
178. При адаптивной дискретизации отсчеты передаются в случайные моменты. Поэтому для восстановления непрерывного сообщения по отсчетам приемная
179. Физическая модель непрерывного канала связи, представляющего наибольший интерес при анализе работы РСПИ, включает в свой состав
180. Проходя по непрерывному каналу связи, сигнал претерпевает ряд изменений. Эти изменения сводятся к ослаблению, искажению сигнала
181. Рис. 2. Модель непрерывного канала связи Искажения сигналов в непрерывных каналах
182. Линейные искажения проявляются в изменении спектра (корреляционной функции) сигналов и помех. В зависимости от того, каковы
183. Характер рассеяния сигнала определяется диапазоном используемых частот и типом системы. Если раньше типичными каналами с рассеянием
184. Пусть в точку приема приходят сигналы, переотраженные от совокупности бесконечно малых по размеру отражателей, размещенных в
185. фазу, изменяющиеся соответственно по рэлеевскому и равномерному законам. Скорость изменения (ширина спектра флуктуации или время корреляции)
186. В общем случае сигнал на выходе линейного канала с изменяющимися параметрами можно найти, используя интеграл Дюамеля
187. Фурье и т.п. Если полоса частот сигнала, передаваемого по каналу, ограничена интервалом то достаточно рассматривать функцию
188. Физическая модель канала, построенная в соответствии с (1), (рис. 3), содержит линию задержки с L отводами
189. В частотной области модель канала можно построить в предложении конечности времени рассеяния сигнала. Тогда функция по
190. Рис. 4. Модель канала с ограниченным временем рассеяния сигнала Линейные искажения в непрерывных каналах
191. Важно знать характер изменения комплексных коэффициентов передачи и в каждой ветви. Если рассеивающий объем состоит из
192. Время корреляции или ширина спектра флуктуации характеризуют скорость изменения параметров канала. Например, для КВ канала ширина
193. Тема: Модели дискретно-непрерывных каналов. Теория построения инфокоммуникационных систем и сетей
194. Дискретно-непрерывный канал имеет дискретный вход и непрерывный выход. Примером такого канала является канал, образованный совокупностью технических
195. Для его описания необходимо знать алфавит входных символов вероятность появления символов алфавита полосу пропускания непрерывного канала
196. Ширина спектра сигнала не может превышать значение Поэтому В соответствии с теоремой Котельникова его можно представить
197. При независимых отсчетах шума Если плотность вероятности для любого сочетания и не зависимы от времени, то
198. Тема: Модели непрерывных каналов связи. Теория построения инфокоммуникационных систем и сетей
199. Искажения сигналов и помехи в реальных каналах связи весьма многообразны. Тем не менее математическая канала должна
200. Канал с гауссовским белым шумом представляет собой идеальный канал, в котором на сигнал накладывается помеха Коэффициент
201. Гауссовский канал с неопределенной амплитудой и фазой сигнала вносит в сигнал наряду с флуктуациями фазы и
202. В радиосистемах передачи дискретной информации, когда время памяти канала соизмеримо с длительностью посылки (а тем более
203. Возможно дальнейшее усложнение модели с нелинейными искажениями, если предположить наличие в канале еще и линейных искажений,
204. Тема: Нелинейные искажения в каналах связи. Теория построения инфокоммуникационных систем и сетей
205. Нелинейные искажения возникают в результате прохождения сигнала по звеньям с нелинейной амплитудной характеристикой . Так как
206. Так как приемное устройство обычно содержит на входе полосовой фильтр, пропускающий только спектральные составляющие в области
207. Картина искажения сигнала существенно усложняется, когда одновременно с полезным сигналом действуют другие сигналы или помехи. В
208. Особый интерес как нелинейность представляет так называемый предельный ограничитель, для которого . Пусть на его входе
209. Рис. 1. Диаграмма подавления слабого сигнала сильным на нелинейном элементе (штриховой линией обозначен сильный сигнал) Нелинейные
210. Для помехи, представляющей собой сумму гармонического сигнала и гауссовской помехи, коэффициент подавления полезного сигнала можно рассчитать
211. Из рис. 2 видно, что в предельном ограничитель подавления гармонического сигнала будет наибольшим при воздействии гармонической
212. Тема: Неравномерное квантование. Теория построения инфокоммуникационных систем и сетей
213. Неравномерное квантование, хотя и сложнее в реализации, чем равномерное, довольно часто используется при передаче речевых сигналов.
214. Неравномерное квантование можно реализовать различными способами, например квантованием с соответствующей амплитудной характеристикой (непосредственное неравномерное квантование). При
215. Неравномерное квантование можно реализовать различными способами, например квантованием с соответствующей амплитудной характеристикой (непосредственное неравномерное квантование). При
216. Рис. 1. Структурная схема компандирования При неравномерном квантовании дисперсия погрешности квантования (1) где и – нижняя
217. (2) (3) Из выражений (2) и (3) находим, что оптимальным значение является абсцисса центра тяжести криволинейной
218. В частности, из (2) и (3) нетрудно видеть, что если распределение Равномерное, то квантование с постоянным
219. Двоичный натуральный код – это код, комбинации которого представляют собой двоичные номера уровней квантования. Он прост
220. Код Грея связан с двоичным натуральным кодом следующими соотношениями: где – кодовая комбинация натурального кода, –
221. Рассмотренные коды обеспечивают одинаковую погрешность восстановления из-за ошибок в канале связи при условии, что ошибки возникают
222. Тема: Общие сведения о каналах связи. Теория построения инфокоммуникационных систем и сетей
223. Каналы связи можно классифицировать по различным показателям. В теории передачи сигналов каналы классифицируются по характеру сигналов
224. Таблица 1. Классификация каналов по диапазонам используемых ими частот Общие сведения о каналах связи
225. По способу распространения радиоволн различают каналы с открытым и с закрытым распространением. В каналах с закрытым
226. стабильностью. Особенностью этих диапазонов является также способность волн проникать в толщу Земли и воды на глубину
227. проникновения в ионосферу зависит от длины волны, то для передачи информации между двумя пунктами можно указать
228. дальних радионавигации. Гектометровые волны днем распространяются как земные, а ночью – как ионосферные. Дальность распространения земной
229. сигналов и возможностью использования одинаковых частот для организации связи в зонах, удаленных на расстояния, превышающие радиогоризонт.
230. Стремление увеличить дальность радиолинии в этих диапазонах без промежуточной ретрансляции нашел свое решение в РСПИ, использующих
231. Новую эру в освоению высокочастотной области радиодиапазона для средств связи открыл запуск искусственных спутников Земли (ИСЗ).
232. земной поверхности от одного ИСЗ или, иначе говоря, максимальное расстояние вдоль поверхности Земли между двумя стациями
233. спутников, орбиты которых выбраны так, что над любой точкой на поверхности Земли находится по крайней мере
234. Тема: Помехи в каналах связи. Теория построения инфокоммуникационных систем и сетей
235. Ошибки, возникающие при приеме сообщения, в значительной степени определяются видом и интенсивностью помех, действующих в канале.
236. Различают тепловой и дробовый шумы. Тепловой шум обусловлен тепловым движением носителей заряда, приводящим к появлению случайной
237. Шумы электровакуумных и полупроводниковых приборов (дробовые шумы) обусловлены дискретной природой носителей заряда. Статистические характеристики дробового шума
238. Атмосферные помехи возникают в результате различных электрических процессов, происходящих в земной атмосфере. Наиболее мощными источником является
239. Земная поверхность, как и всякое нагретое тело, излучает электромагнитные волны. Они могут попадать в антенну по
240. Одним из распространенных видов помех являются помехи от посторонних радиостанций. Насыщенность радиосредствами (радиосвязь, радиолокация, радионавигация и
241. Станционные помехи присутствуют практически во всех диапазонах, и особенно в коротковолновом, где из-за ионосферного распространения радиоволн
242. Спектральную плотность мощности помех (рис. 1) как случайный процесс можно достаточно полно охарактеризовать плотностью вероятности и
243. Если число стационарных помех, попадающих в полосу сигнала, ограничено, то рассмотренная модель не всегда применима. В
244. Тема: Преобразование непрерывных сообщений в цифровую форму. Операция квантования по уровню. Теория построения инфокоммуникационных систем и
245. Непрерывные сообщения можно передавать по дискретным системам связи. Для этого их преобразуют в цифровую форму (в
246. Различают равномерное и неравномерное квантование. При равномерном квантовании шаг берется постоянным, а уровень соответствует середине i-го
247. Замена непрерывного множества возможных значений сообщения дискретным множеством фиксированных значений приводит к погрешности, называемой шумом квантования.
248. Таким образом, для рассматриваемого случая дисперсия погрешности равномерного квантования зависит только от значения шага или при
326. Скачать презентацию

Слайд 2

Простейший тип дискретного источника – это такой, который выдаёт последовательность букв

(символов), выбираемых из определенного алфавита.
Например, двоичный источник выдает двоичную последовательность вида 100101110..., причём алфавит состоит из двух символов {0,1}. В более общем случае источник дискретен информации с алфавитом из L символов,{x1, x2, …, xL} выдает последовательность букв, выбираемых из этого алфавита.

Слайд 3

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

алфавита {x1, x2, …, xL} имеет заданную вероятность выбора Pk т.е
pk =P(X = xk), 1 ≤ k ≤ L
где:

Слайд 4

Рассмотрим две математические модели для дискретных источников.
Предположим, что символы выходной последовательности

источника статистически независимы, т.е. выбираемый текущий символ статистически независим от всех предыдущих и последующих. Источник, выход которого удовлетворяет условиям статистической независимости символов в выбранной последовательности, называется источником без памяти. Такой источник называется дискретным источником без памяти (ДИБП).

Слайд 5

Если отдельные выходные символы дискретного источника статистически взаимозависимы, как, например, в

английском тексте, мы можем сконструировать математическую модель, основанную на статической стационарности. По определению дискретный источник называется стационарным, если совместные вероятности двух последовательностей длины n, допустим {a1,a2,…, an} и {a1+m,a2+m,…, an+m} одинаковые для всех
n ≥ 1 и при всех сдвигах m. Другими словами, совместные вероятности для последовательностей источника произвольной длины инвариантны по отношению к произвольному сдвигу во времени.

Слайд 6

Аналоговый источник выдает сигнал x(t), который является реализацией случайного процесса X(t).

Предположим, что X(t) - стационарный случайный процесс с автокорреляционной функцией фxx(τ) и спектральной плотностью мощности Фxx(f) .
Если X(t) - частотно-ограниченный случайный процесс, т.е. Фxx(f) =0 для | f | ≥ W , можно использовать теорему отсчётов для представления X(t) в виде:

Слайд 7

Где X{(n/2W)} - отсчёты процесса X(t) взятые со скоростью Найквиста fs=2W,

1/c.
Используя теорему отсчётов, мы можем преобразовать аналоговый источник в эквивалентный источник с дискретным временем. После этого выход источника характеризуется совместной ФПВ p(x1 x2, … xm) для всех m≥1, где Xn{(n/2W)}, 1 ≤ n ≤ m - случайные величины, соответствующие отсчётам X(t).

Слайд 8

Заметим, что выходные отсчёты стационарного источника обычно непрерывны, и, следовательно, их

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

Слайд 9

«ЛОГАРИФМИЧЕСКАЯ МЕРА ИНФОРМАЦИИ»

Слайд 10

Чтобы разработать подходящую меру для информации, рассмотрим две дискретные случайные величины

X и Y с возможными значениями соответственно xi , i=1,2,…n и j=1,2,…m
Допустим, мы наблюдаем некоторый выход Y=yj и мы желаем количественно определить величину информации, которую обеспечивает выборка события Y=yj относительно события X=xi , i=1,2,…n

Слайд 11

Заметим, что если X и Y статистически не зависят друг от

друга, выбор Y=yj не даёт информации о выборе события X=xi .
С другой стороны, если X и Y полностью зависимы, так что выбор Y=yj однозначно определяет выбор X=xi информационное содержание этого выбора точно такое же, как при выборе события X=xi .

Слайд 12

Подходящая мера информации, которая удовлетворяет указанным условиям, - это логарифм отношения

условной вероятности:
P(X=xi | Y=yj)=P(xi | yj)
к вероятности:
P(X = xi ) ≡ P(xi )

Слайд 13

Это значит, что количество информации, полученное при появлении события Y=yj относительно

события X=xi определяется как:

названа взаимной информацией между xi и yj

(1)

Слайд 14

Единица измерения I(xi;yj) определяется основанием логарифма, в качестве которой обычно выбирается

или 2, или е. Когда основание логарифма равно 2, единицей измерения I(xi; yj) является бит, а когда основание равно е, единицей измерения I(xi;yj) является нат (натуральная единица). (Стандартная аббревиатура для log e- это ln .)

Слайд 15

Когда случайные величины X и Y статистически независимы, то P(xi|yj)=P(xi), следовательно,

I(xi; yj)=0.
С другой стороны, когда выбор события Y=yj полностью определён выбором события X=xi условная вероятность в числителе (1) равна единиц и, следовательно:

(2)

Слайд 16

Но (2) как раз определяет информацию X=xi
Исходя из этих соображений,

её называют собственной информацией события X=xi. Она обозначается :

(3)

Слайд 17

Пример 1
Предположим, что имеется дискретный источник, который выдаёт двоичную цифру 0

или 1 с равной вероятностью каждые τx секунд. Количество информации при каждом появлении новой цифры:

Слайд 18

Теперь предположим, что последовательные цифры на выходе источника статистически независимы, т.е.

источник не имеет памяти. Рассмотрим блок символов источника из k двоичных цифр, который существует на интервале kτx . Имеется таких возможных k-битовых блоков, каждый с равной вероятностью . Собственная информация k-битового блока равна:

Слайд 19

Она выдаётся на временном интервале Kτx.
Таким образом, логарифмическая мера количества

информации обладает желаемыми свойствами аддитивности, когда определённое число единичных выходов источника рассматривается как один блок.

Слайд 20

вернёмся к определению взаимной информации, определяемой (1), и умножим числитель и

знаменатель отношения вероятностей на p(yj) :

Отсюда делаем вывод:
I(xi ; yj) = I(yj; xi)

Слайд 21

Таким образом, информация, содержащаяся в выборе события Y=yj относительно события X=xi

идентична информации, содержащейся в выборе события X=xi относительно события Y=yj .

Слайд 22

Пример 2
Предположим, что X и Y -двоичные {0,1} случайные величины, представляющие

вход и выход канала с двоичным входом и двоичным выходом. Входные символы равновероятны, а условные вероятности выходных символов при заданном входе определяются так:
P(Y=0|X=0)=1-p0
P(Y=1|X=0)=p0
P(Y=1|X=1)=1-p1
P(Y=0|X=1)=p1

Слайд 23

Определим, сколько информации об X=0 и X=1 содержится в событии Y=0

. Из заданных вероятностей получим:

Тогда взаимная информация о символе X=1 при условии, что наблюдается Y=0, равна:

Аналогично взаимная информация о символе X=1 при условии, что наблюдается Y=0 , равна

Слайд 24

Рассмотрим несколько частных случаев. В первом, когда, p0=p1=0 канал называют каналом

без шумов и I(0;0)=log22=1бит.
Следовательно, когда выход точно определяет вход, нет потери информации. С другой стороны, если p0=p1=1/2, канал становится непригодным так как I(0;0)=log21=0
Если p0=p1=1/4, то

Слайд 25

Помимо определения взаимной информации и собственной информации полезно определить условную собственную

информацию как:

(5)

Тогда, комбинируя (1), (3) и (5), получаем соотношение:
I(xi;yj)=I(xi)-I(xi|yj)

(6)

Слайд 26

Мы интерпретируем I(xi|yj) как собственную информацию о событии X=xi после наблюдения

события Y=yj . Из условия I(xi)≥0 и I(xi|yj) ≥0 следует, что I(xi ,yj)<0 когда I(xi|yj) > I(xi ), и I(xi ,yj) > 0 , когда I(xi ,yj)

Слайд 27

«Средняя взаимная информация и энтропия»

Слайд 28

Зная взаимную информацию, связанную с парой событий (xi;yj), которые являются возможной

реализацией двух случайных величин X и Y, мы можем получить среднее значение взаимной информации простым взвешиванием I(xi;yj), с вероятностью появления этой пары и суммированием по всем возможным событиям.

Слайд 29

Таким образом получим:
как среднюю взаимную информацию между X и Y
(1)

Слайд 30

Видно, что I(X;Y)=0, когда X и Y статистически независимы и P(xi;yj)=P(xi)P(yj)
Важным

свойством средней взаимной информации является то, что I(X;Y) ≥ 0

Слайд 31

Аналогично определим среднюю собственную информацию, обозначенную H(X)
(2)
Если X представляет

собой алфавит возможных символов источника, H(X) представляет среднюю собственную информацию на символ источника, и её называют энтропией источника. В частном случае, когда символы источника равновероятны, P(xi) =1/n
для всех i, и, следовательно

(3)

Слайд 32

В общем случае H(X) ≤ logn при любых заданных вероятностях символов

источника. Другими словами, энтропия источника максимальна, когда выходные символы равновероятны.

Слайд 33

Пример 1
Рассмотрим двоичный источник, который выдаёт последовательности независимых символов, причём выходной

кодовый символ «0» с вероятностью q, а символ «1» с вероятностью 1-q. Энтропия такого источника
H(X) = H(q)= - q log q - (1-q)log (1-q)
Функцию H(q) иллюстрирует рисунок 1.

(4)

Слайд 34

Рисунок 1. Энтропия двоичного источника

Слайд 35

Среднее значение условной собственной информации называется условной энтропией и определяется как:
Мы

интерпретируем H(X|Y) как неопределённость X (дополнительную информацию, содержащуюся в Y ) после наблюдения Y.
Комбинация (1), (2) и (4) даёт соотношение:
I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)

(5)

(6)

Слайд 36

Из условия I(X,Y) ≥0 следует, что H(X)≥H(X|Y) и H(Y)≥H(Y|X), причём равенство

имеет место тогда, и только тогда, когда X и Y статистически независимы. Если мы интерпретируем как среднее значение неопределённости (условной собственной информации) X после наблюдения Y и H(X) как среднее значение априорной неопределённости (собственной информации)

Слайд 37

т.е. имевшейся до наблюдения, тогда I(X;Y) определяет взаимную информацию (уменьшение среднего

значения неопределённости, имеющейся относительно X после наблюдения Y).
Так как H(X)≥H(X|Y) то ясно, что при условии наблюдения Y энтропия H(X) не увеличится.

Слайд 38

Пример 2
Определим H(X|Y) и I(X,Y) для канала с двоичным входом и

выходом, рассмотренного выше в примере 1, для случая, когда p0=p1=p. Пусть вероятность входных символов равна P(X=0)=q и P(X=1)= 1- q. Тогда:
H(X)=H(q)= – q lg – q – (1 – q) lg(1 – q)

Где H(q)- функция энтропии. Зависимость H(X|Y) в бит/символ как функция от q и p параметра показана на рис. 3. График средней взаимной информации I(X,Y) в бит/символ дан на рис. 3.1.

Слайд 39

Рис.3.1. Средняя взаимная информация для двоичного симметричного канала
Рис. 3. Условная энтропия

для двоичного симметричного канала

Слайд 40

Когда условную энтропию H(X|Y) рассматривают применительно к каналу с входом и

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

Слайд 41

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

В частности, предположим, что мы имеем блок из k случайных величин X1X2X3…Xk с совместной вероятностью P(X1 X2 …Xk) ≡ P(X1=x1,X2 =x2,…,Xk=xk)

Слайд 42

Тогда энтропия определяется как:
Поскольку совместную вероятность P(X1X2…,Xk) можно выразить в виде:
P(x1x2…xk)≡P(x1)P(x2|x1)P(x3|x1x2)…P(xk|x1x2…xk-1)
то

следует

(7)

Слайд 43

С учётом результата H(X)≥H(X|Y) где X=Xm и Y=X1X2…Xm-1 из (7) следует
причём равенство

имеет место тогда, и только тогда, когда случайные величины X1X2X3…Xk статистически независимы.

Слайд 44

«Кодирование для дискретных источников без памяти»

Слайд 45

Предположим, что ДИБП выдает буквы или символы каждые τx секунд. Каждый

символ выбирается из конечного алфавита xi , i=1,2,…L, с вероятностью P(xi),i=1,2,…L. Энтропия ДИБП в битах на символ:
причем равенство имеет место, если все символы равновероятны. H(X) определяет среднее число бит на символ источника, а производительность источника в битах определяется как H(X)/ τx

(1)

Слайд 46

Кодовые слова фиксированной длины
Сначала рассмотрим схему блокового кодирования, которая сопоставляет уникальный

ряд из R двоичных символов с каждым символом источника. Поскольку имеется L возможных символов источника, то числа двоичных символов кодера на один символ источника при уникальном кодировании
R=log2 L

(2)

Слайд 47

когда L равно целой степени основания 2, и
R=[log2 L]+1
когда не равно

целой степени основания 2. Здесь [x] означает наибольшее целое, меньшее, чем x.

(3)

Слайд 48

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

один символ источника. Поскольку,
H(X) ≤ log2 L, то R ≥ H(X)
Эффективность кодирования для ДИБП определяется отношением H(X) / R. Видим, что если L равно степени числа 2 и символы источника равновероятны, то R=H(X). Следовательно, код фиксированной длины с R двоичными символами на символ источника в данном случае обеспечивает стопроцентную эффективность. Однако, если L не равно степени 2, но символы источника всё ещё равновероятны, R отличается от H(X) самое большее на один бит на символ.

Слайд 49

Если log L>>1, эффективность такой схемы кодирования высока. С другой стороны,

если L мало, эффективность кода с фиксированной длиной можно увеличить путем кодирования последовательности из J символов источника за время JτS . Чтобы выполнить такое кодирование, мы должны выбрать уникальных кодовых слов. Используя кодовую последовательность из N двоичных символов, мы можем образовать возможных кодовых слов. Число N должно быть выбрано так, чтобы:
N ≥ J log2 L

Следовательно, требуется минимальное целое значение для N, равное
N =[ J log2 L]+1

(4)

Слайд 50

Теперь среднее число символов кода на символ источника R=N/J , и,

таким образом, неэффективность кодирования сокращается примерно в J раз по сравнению с посимвольным кодированием, описанным выше.
Взяв J достаточно большим, можно делать эффективность процедуры кодирования, измеренную отношением JH(X)/N, как годно близкой к единице.

Слайд 51

Методы кодирования, не приводят к искажениям, так как кодирование символов

источника или блоков таких символов в кодовые слова выполняется однозначно (уникально). Такие типы кодов названы бесшумными.

Слайд 52

Предположим, что мы пытаемся уменьшить скорость кодирования R путем смягчения условия

однозначности процесса кодирования. Предположим, что только доля блоков символов источника кодируется однозначно. Выберем
наиболее вероятных J -символьных блоков и будем кодировать каждый из них однозначно, в то время как оставшиеся блоков длины J представим одним оставшимся кодовым словом. Эта процедура кодирования вызовет ошибку декодирования каждый раз, когда источник выдаст такой маловероятный блок.

Слайд 53

Теорема кодирования источника I
Пусть X - это ансамбль символов ДИБП с

конечной энтропией H(X). Блоки из J символов источника кодируются в двоичные кодовые слова длиной N. Для любого ɛ >0 вероятность Pe ошибки декодирования можно сделать сколь угодно малой, если
J достаточно велико.
Наоборот, если R ≤ H(X) - ɛ
тогда Pe сколь угодно близка к 1 при достаточно больших J.

Слайд 54

Исходя из этой теоремы мы видим, что среднее число бит на

символ источника требуемое для кодирования выхода ДИБП с произвольно малой вероятностью ошибки декодирования, ограничено снизу энтропией источника H(X). С другой стороны, если R

Слайд 55

Кодовые слова переменной длины

Слайд 56

Если символы источника неравновероятны, более эффективный метод кодирования сводится к использованию

кодовых слов переменной длины. Примером такого кодирования является код Морзе. В коде Морзе символам, возникающим более часто, сопоставляются более короткие кодовые слова, а символам, возникающим менее часто, сопоставляются более длинные кодовые слова.

Слайд 57

Таблица 1. Коды переменной длины
Для примера предположим, что выходные символы ДИБП

а1 а2 а3 а4 соответствующими вероятностями Р(а1)=1/2, Р(а2)=1/4, Р(а3)=Р(а4)=1/8, кодируются так как показано в табл.1. Код I имеет переменную длину и имеет принципиальный недостаток. Чтобы увидеть этот недостаток, предположим, что мы приняли последовательность 001001... Ясно, что 00 декодируется как а2. Однако последующие четыре бита декодируются неоднозначно. Они могут декодироваться или как а4а3 , или как а1 а2 а1.

Слайд 58

Код II в табл. 1 обеспечивает однозначное и немедленное декодирование. Удобно

представлять кодовые слова этого кода графически как узлы на дереве, как показано на рис. 1. Видно, что 0 указывает на окончание кодового слова в первых трех кодовых словах. Эта характеристика вместе с тем обстоятельством, что ни одно кодовое слово не содержит более трех двоичных символов, что делает этот код немедленно декодируемым.

Слайд 59

Заметим, что ни одно кодовое слово этого кода не является префиксом

(началом) другого кодового слова. В общем, префиксное условие кода требует, чтобы для данного кодового слова Сk длины k с элементами (b1, b2,…bk) не существовало других кодовых слов длинны l

Слайд 60

Другими словами, нет кодовых слов длины l < k, которые совпадают

с первыми l двоичными символами другого кодового слова длины k > l. Это свойство делает кодовые слова немедленно декодируемыми.
Код III из табл. 1 имеет кодовое дерево, показанное на рис. 2. Видим, что в этом случае имеет место однозначное декодирование, однако требующее задержки. Ясно, что этот код не удовлетворяет префиксному условию.

Рис. 1. Кодовое дерево для кода II в табл.1

Рис. 2. Кодовое дерево для кода III в табл.1

Слайд 61

Наша главная цель – создать систематическую процедуру для конструирования однозначных декодирующих

кодов переменной длины, эффективных в том смысле, что среднее число бит на один символ источника, определяемое соотношением, было бы минимальным. Условие существования кода переменной длины, которое удовлетворяет префиксному условию, дается неравенством Крафта.

(1)

Слайд 62

Неравенство Крафта
Необходимым и достаточным условием существования двоичного кода с кодовыми символами

длины n1 ≤ n2 ≤…≤ nL,
удовлетворяющего условию префиксности, является
Сначала мы докажем, что (2) является достаточным условием для существования префиксного кода. Чтобы построить такой код, мы начнем с полного двоичного дерева порядка n = nL, которое имеет конечных узлов, причем от каждого узла порядка k-1 «растут» по два узла порядка k , 1 ≤ k ≤ n.

(2)

Слайд 63

Выберем некоторый узел порядка в качестве первого кодового слова C1. Этот

выбор устраняет конечных узлов. От остающихся доступных узлов порядка n2 мы выбираем один узел для второго кодового слова C2. Этот выбор устраняет конечных узлов. Этот процесс продолжается, пока последнее кодовое слово не определено в конечном узле n = nL. Следовательно, в узле порядка j < L доля числа отсечённых конечных узлов:

(3)

Слайд 64

Таким образом, создали кодовое дерево, которое встроено в полное дерево из

узлов, как иллюстрируется на рис. 3. для дерева, имеющего 16 конечных узлов, и источника, состоящего из пяти символов, отображаемых кодовыми словами длиной n1=1,n2=2,n3=3,n4=4.

Слайд 65

Рис. 3. Конструирование двоичного дерева, встроенного в полное дерево

Слайд 66

Чтобы доказать, что (2) является необходимым условием, мы заметим, что в

дереве порядка n = nL , число конечных узлов, отсечённых от общего числа конечных узлов равно:
Неравенство Крафта можно использовать для доказательства следующей теоремы кодирования источника (без шумов), которое применяется к кодам, удовлетворяющим префиксному условию.

Следовательно,

Слайд 67

Теорема кодирования источника II.
Пусть X- ансамбль символов двоичного источника без

памяти с конечной энтропией H(X) и выходными символами xk , 1 ≤ k ≤ L с соответствующими вероятностями выбора pk , 1 ≤ k ≤ L. Существует возможность создать код, который удовлетворяет префиксному условию и имеет среднюю длину , которое удовлетворяет неравенству:
Чтобы установить нижнюю границу в (4), обратим внимание на то, что для кодовых слов, которые имеют длину nk , 1 ≤ k ≤ L , разность может быть выражена в виде

(4)

(5)

Слайд 68

Используя неравенство ln x ≤ x-1 , из (5) находим:
Верхняя граница

в (4) может быть установлена при предположении что nk , 1 ≤ k ≤ L - целые числа, выбираемые из условия . Но если pk≥2
просуммированы по 1 ≤ k ≤ L, получаем неравенство Крафта, для которого демонстрировали, что там существует код, удовлетворяющий префиксному условию другой стороны, если мы берем логарифм,
получаем: log pk < –nk +1

или, что эквивалентно: nk<1 – log pk

(6)

Слайд 69

Если умножить обе части неравенства (6) на pk и просуммировать по

1 ≤ k ≤ L. , получаем желательную верхнюю границу, данную в (6). Это завершает доказательство (6).
Мы установили, что коды переменной длины, которые удовлетворяют префиксному условию, - это эффективные коды для любого дискретного источника без памяти (ДИБП) с символами, имеющими различную априорную вероятность. Опишем теперь алгоритм для построения таких кодов.

Слайд 70

Алгоритм кодирования Хаффмена

Слайд 71

Хаффмен (1952) разработал алгоритм кодирования переменной длины, основанный на знании априорных

вероятностей символов P(xi), i=1,2,…L . Этот алгоритм оптимален в том смысле, что среднее число двоичных символов, требуемых для представления исходных символов, минимально. Получаемые кодовые слова удовлетворяют префиксному условию, что позволяет уникально и мгновенно декодировать полученную последовательность.

Слайд 72

Пример 1.
Рассмотрим ДИБГТ с семью возможными символами, имеющими вероятности выбора, иллюстрируемое

ниже.

Среднее число двоичных элементов на символ этого кода 2,21 бит/символ. Энтропия источника – 2,11 бит/символ.

Слайд 73

Заметим, что полученный код не единственно возможный. Например, на предпоследнем шаге

процедуры кодирования мы имеем равный выбор между x1 , и x2 имеющими одинаковые вероятности. В этом пункте мы соединили x1 и x2. В альтернативном коде мы можем соединить x2 и x3'. Результирующий код для этого случая иллюстрируется на рис.2

Слайд 74

Рис. 2. Альтернативный код для ДИБП в примере 1

Слайд 75

Пример 2.
В качестве второго примера определим код Хаффмена для выхода

ДИБП, иллюстрируемый на рис. 3. Энтропия этого источника H(X)=2,63 бит/символ. Код Хаффмена, показанный на рис. 3, имеет среднюю длину R=2,70 бит/символ. Следовательно, его эффективность составляет 0,97.

Слайд 76

Алгоритм кодирования переменной длины (Хаффмена), генерирует префиксный код, имеющий среднюю длину.

Однако вместо посимвольного кодирования более эффективной является процедура, основанная на кодировании блоков из символов одновременно, таком случае границы в H(X) ≤ R < H(X)+1 в теореме кодирования источника II становятся другими:

Слайд 77

так как энтропия J -символьного блока от ДИБП равна JH(X), и

RJ - среднее число бит в J -символьном блоке. Если мы разделим (1) на J , то получим:
Где RJ /J ≡ R- среднее число битов на исходный символ. Следовательно, R можно сделать как угодно близким к H(X), выбирая J достаточно большим.

(1)

(2)

JH(X) ≤ RJ < JH(X)+1

Слайд 78

Рис. 3.Код Хаффмена для примера 2

Слайд 79

Пример 3
Выход ДИБП состоит из символов x1, x2 и x3 с

вероятностями 0,45, 0,35 и 0,20 соответственно. Энтропия этого источника H(X)=1,518бит/символ. Код Хаффмена для этого источника, данный в табл.1, требует R1=1,55бит/символ и приводят к эффективности 97,9%, Если посредством алгоритма Хаффмена символы закодированы парами, результирующий код выглядит так, как показано в табл.1. Энтропия источника для пар символов 2H(X)=3,036бит/пара символов. С другой стороны, код Хаффмена требует R2=3,0675 бит/пара символов. Таким образом, эффективность кодирования увеличилась до 2H(X)R2=0,990(до 99,0 %)

Слайд 80

Таблица 1. Код Хаффмена

Слайд 81

Таблица 2. Код Хаффмена для кодирования пар символов

Слайд 82

Дискретные стационарные источники

Слайд 83

Рассмотрим дискретные источники, для которых последовательность символов выхода является статистически зависимой.

Мы ограничим наше исследование источниками, которые являются статистически стационарными (однородными во времени)

Слайд 84

Оценим энтропию некоторой последовательности символов от стационарного источника. Энтропия блока случайных

переменных X1 ,X2 … Xk равна
Где H(Xi | X1X2Xi-1) - условная энтропия i-го символа при условии, что источник выдал предыдущие i-1 символов. Энтропия на символ для k-символьного блока определяется как:

(1)

(2)

Слайд 85

Мы определяем количество информации стационарного источника как энтропию на символ в

(2) в пределе при , k→∞ т.е.
В качестве альтернативы мы можем определять энтропию на символ источника как условную энтропию H(Xk|X1X2…Xk-1) в пределе при k→∞. Этот предел также существует и идентичен пределу в (3). То есть

(3)

(4)

Слайд 86

Этот результат также установлен ниже. Наше изложение использует подход Галлагера (1968).

Во-первых, мы покажем, что:
H(Xk|X1X2…Xk-1)≤ H(Xk-1|X1X2...Xk-2)
для k ≥ 2. С учётом предыдущего результата, согласно которому наложение условий на случайную переменную не может увеличивать её энтропию, мы имеем:
H(Xk|X1X2…Xk-1)≤ H(Xk|X2X3...Xk-1)
В силу стационарности источника имеем:
H(Xk|X2X3…Xk-1)= H(Xk-1|X1X2...Xk-2)

(5)

(6)

(7)

Слайд 87

Во-вторых, мы имеем результат:
Hk (X) ≥ H(Xk|X1X2...Xk-1)
B-третьих, по определению Hk(X):
что приводит

к:
Hk (X) ≤ Hk-1(X)
Следовательно, Hk(X)- не возрастающая последовательность (с ростом k )

(6)

(7)

(8)

Слайд 88

Поскольку Hk (X) и условная энтропия H(Xk|X1X2…Xk-1) не отрицательны и не

возрастающие (с ростом k), оба предела должны существовать. Их предельные выражения могут быть установлены с использованием (1) и (2), чтобы выразить Hk +j(X) как:
Так как условная энтропия не возрастает, первый член в квадратных скобках является верхней границей для других слагаемых. Следовательно,

(9)

(10)

Слайд 89

Для фиксированного k в пределе для (10) при j→∞ получаем:
H∞

(X) ≤ H(Xk|X1X2...Xk-1)
Но (11) справедливо для всех k; следовательно, это справедливо и для k →∞. Поэтому
С другой стороны, с учётом (6) мы получаем в пределе для k→∞

(11)

(12)

(13)

устанавливает (4).

Слайд 90

Предположим, что мы имеем дискретный стационарный источник, который даёт J символов

с энтропией на символ HJ(X). Мы можем кодировать последовательность J символов кодом Хаффмена переменной длины, который удовлетворяет префиксному условию при использовании процедуры. Результирующий код имеет cреднее число бит для блока с J символами, который удовлетворяет условию:
H(X1…XJ) ≤ RJ < H(X1…XJ)+1

(13)

Слайд 91

Деля обе части (13) на J, мы получаем границы для среднего

числа R=RJ /J бит на исходный символ как:
HJ (X) ≤ R < H J (X) + 1/J
Увеличивая размер блока J:
H∞ (X) ≤ R < H ∞ (X) + ξ
где ξ стремится к нулю как 1/J. Таким образом, эффективное кодирование стационарных источников может быть выполнено, если кодировать большие блоки символов в кодовые слова.

Слайд 92

Алгоритм Лемпела-Зива

Слайд 93

Алгоритм кодирования Хаффмена приводит к оптимальному кодированию источника в том смысле,

что кодовые слова удовлетворяют префиксному условию и средняя длина кодового блока минимальна. Конструируя код Хаффмена для ДИБП, мы должны знать вероятности появления всех исходных символов. В случае дискретного источника с памятью мы должны знать совместные вероятности всех блоков длины n ≥ 2.

Слайд 94

В отличие от алгоритма кодирования Хаффмена алгоритм кодирования Лемпела-Зива разработан так,

чтобы быть независимым от статистики источника. Следовательно, алгоритм Лемпела-Зива принадлежит классу универсальных алгоритмов кодировать источника.

Слайд 95

В алгоритме Лемпела-Зива последовательность с выхода дискретного источника делится на блоки

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

Слайд 96

Рассмотрим бинарную последовательность :
10101101001001110101000011001110101100011011.
Деление последовательности, как описано выше, производит следующие

фразы:
1,0,10, 11,01,00. 100, 111,010, 1000,011,001, 110, 101, 10001, 1011.
Видим, что каждая фраза в последовательности - соединение одной из предыдущих фраз с новым выходным символом источника. Для кодирования фразы мы конструируем словарь, как показано в табл. 1

Слайд 97

Таблица 1. Словарь для алгоритма Лемпела-Зива

Слайд 98

Ячейки словаря пронумерованы последовательно, начиная с 1 и далее, в данном

случае до 16, что является числом фраз в последовательности. Различные фразы, соответствующие каждой ячейке, также перечислены, как показано в таблице. Кодовые слова конструируются путём соединения двух частей. Первая часть представляет собой номер ячейки словаря (в двоичной форме) предыдущей фразы, которая соответствует новой фразе, кроме последнего символа. Вторая часть — это новый символ, выданный источником. Он добавляется в конец к первой части, т.е. к номеру ячейки предыдущей фразы. Первоначальный номер ячейки 0000 используется, чтобы кодировать «пустую» фразу

Слайд 99

Декодер источника создает идентичную таблицу на приемном конце системы связи и

соответственно декодирует полученную последовательность.
Можно заметить, что таблица закодировала 44 исходных бита в 16 кодовых слов по пять битов каждый, что привело к 80 кодированным битам. Следовательно, алгоритм вообще не обеспечил никакое сжатие данных. Однако неэффективность является следствием того, что последовательность, которую мы рассмотрели, очень коротка. По мере увеличения длины последовательности процедура кодирования становится более эффективной и приводит к сжатию последовательности на выходе источника.

Слайд 100

Алгоритм Лемпела-Зива широко используется при сжатии компьютерных файлов. «Сжимающие» и «разжимающие»

программы (утилиты) в операционной системе UNIX и многочисленные алгоритмы в операционной системе MS DOS являются воплощениями различных версий этого алгоритма.

Слайд 101

«Кодирование для аналоговых источников - оптимальное квантование»

Слайд 102

Аналоговый источник выдаёт непрерывный сигнал x(t), который является выборочной функцией случайного

процесса X(t). Если X(t) является стационарным случайным процессом с ограниченной полосой, теорема отсчётов позволяет нам представить X(t) последовательностью отсчётов, выбираемых равномерно со скоростью Найквиста.

Слайд 103

Применяя теорему отсчётов, выход аналогового источника преобразуется в эквивалентную дискретную во

времени последовательность отсчётов. Затем отсчёты квантуются по уровням и кодируются. Один тип простого кодирования - представление каждого дискретного уровня амплитуды последовательностью двоичных символов.

Слайд 104

Следовательно, если мы имеем L уровней, нам необходимы R=log2L бит/отсчёт (если

L есть степень числа 2) или R=[log2L]+1(в противном случае).
Если уровни не равновероятны, но вероятности уровней на выходе источника известны, мы можем использовать процедуру кодирования Хаффмена (называемую также энтропийным кодированием), чтобы улучшить эффективность процесса кодирования.

Слайд 105

Квантование амплитуд дискретизированного во времени сигнала обеспечивает сжатие данных, но это

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

Слайд 106

Функция скорость-искажение R(D)
Под термином «искажение» мы понимаем некоторую меру разности между

фактическими выборками источника {xk} и соответствующими квантованными значениями, xk которую обозначим d{xk, xk}. Например, обычно используемая мера искажения - квадрат ошибки, определенная как:

(1)

Слайд 107

Используемое для определения ошибки квантования при ИКМ:
(2)
Где p- принимает значения из

ряда положительных целых чисел. Случай p=2 имеет предпочтительную математическую трактовку.

Если d{xk, xk}- мера искажения на отсчёт, искажение между последовательностью отсчётов n и Xn соответствующими n квантованными значениями Xn является средним значением искажения по n отсчётам, т.е.

(3)

Слайд 108

На выходе источника имеет место случайный процесс, и, следовательно, n отсчётов

Xn в являются случайными величинами. Поэтому - случайная величина. Её математическое ожидание определяет искажение D , т.е

(4)

предположим, что мы имеем источник без памяти с непрерывно-амплитудным выходом X, который имеет ФПВ отсчёта p(x), квантованный амплитудный алфавит и меру искажения на отсчёт , где x є X и

Слайд 109

где I(X,X)- средняя взаимная информация между X и X.Вообще, скорость R(D)

уменьшается при увеличении D или, наоборот, R(D) увеличивается при уменьшении D.

(5)

Тогда минимальная скорость в битах на отсчёт, требуемая для представления выхода X источника без памяти с искажением, меньшим или равным D называется функцией скорость-искажение и определяется как:

Слайд 110

«Функция скорость-искажение для гауссовского источника без памяти»

Слайд 111

Теорема: Функция скорость-искажение для гауссовского источника без памяти (Шеннон, 1959).
Минимальная скорость

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

(1)

где σx² - дисперсия выхода, гауссовского источника.

Слайд 112

Заметим, что (1) подразумевает, что, если искажение,
D ≥ σx² никакой

информации передавать не нужно. Конкретно при D = σx² для реконструкции сигнала достаточно воспроизвести нули. При D > σx² для реконструкции сигнала мы можем использовать статистически независимые гауссовские шумовые выборки с дисперсией D-σx². График функции Rg(D) представлен на рис.1.

Слайд 113

Рис. 1. Функция скорость-искажение для непрерывного по амплитуде гауссовского источника без

памяти

Функция скорость-искажение R(D)источника связана со следующей основной теоремой кодирования источника в теории информации.

Слайд 114

Теорема: Кодирование источника с заданной мерой искажения (Шеннон, 1959).
Существует схема

кодирования, которая отображает выход источника в кодовые слова так, что для любого данного искажения D минимальная скорость R(D) бит на символ (на отсчёт) источника является достаточной для восстановления исходного сигнала со средним искажением, которое является произвольно близким к D.
Это очевидно, потому что функция скорость-искажение R(D) для любого источника представляет нижнюю границу скорости источника, которая является возможной для данного уровня искажения.

Слайд 115

Вернёмся к результату в (1) для функции скорость-искажение гауссовского источника без

памяти. Если мы поменяем функциональную зависимость между D и R, мы можем выразить Dg через R как

Эта функция называется функцией искажение-скорость для дискретного во времени гауссовского источника без памяти
Если искажение в (2) выразить в децибелах, мы получаем
10log10Dg(R)= - 6 R+10log10 σx²

(2)

(3)

Слайд 116

Верхняя граница для функции скорость-искажение

Слайд 117

Теорема: Верхняя граница для R(D)
Функция скорость-искажение непрерывного по амплитуде источника без

памяти с нулевым средним и конечной дисперсией σx² при использовании среднеквадратичной меры искажений ограничена сверху величиной:
R(D) ≤ 1/2 log2 (σx² /D); (0 ≤ D ≤ σx²)

(1)

Слайд 118

Доказательство этой теоремы дано Бергером (1971). Подразумевается, что гауссовский источник требует

максимальную скорость кодирования среди всех других источников при заданном уровне среднеквадратической ошибки. Следовательно, функция скорость-искажение R(D) для произвольного непрерывного источника без памяти с нулевым средним и конечной дисперсией σx² удовлетворяет условию R(D)≤Rg(D) .
Аналогично функция искажение-скорость того же источника удовлетворяет условию:

(2)

Слайд 119

Существует также нижняя граница функции скорость-искажение. Её называют нижней границей Шеннона

для среднеквадратической ошибки искажения, и она определяется так:
R*(D) = h(X) - 1/2 log2 2πeD

(3)

где h(X) - дифференциальная энтропия источника без памяти с непрерывной амплитудой. Функция искажение-скорость, соответствующая (3), равна:

(4)

Слайд 120

Следовательно, функция скорость-искажение для произвольного источника без памяти с непрерывной амплитудой

ограничена сверху и снизу:
R*(D) ≤ R(D) ≤ Rg(D)

(5)

и соответствующая функция искажение-скорость ограничена:
D*(R) ≤ D(R) ≤ Dg(R)

(6)

Дифференциальная энтропия гауссовского источника без памяти:
hg (X)=1/2 log2 2πeσx²

(7)

Слайд 121

так что нижняя граница R*(D) в (3) уменьшается до Rg(D).Теперь, если

выразить D*(R) в децибелах и нормировать к σx²=1 мы получаем из (4):
10log10D*(R)=-6R-6[hg(X)-h(X)]

(8)

или, что эквивалентно,

(9)

Соотношения в (8) и (9) позволяют сравнивать нижнюю границу искажений с верхней границей, которая определяет искажения для гауссовского источника.

Слайд 122

В таблице 1 даны четыре типа ФПВ, которые являются моделями распределения,

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

Слайд 123

Таблица 1. Дифференциальная энтропия и сравнение скорости и искажений четырёх распространённых ФПВ

для моделей сигнала

Слайд 124

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

Поэтому функция скорость-искажение для белого гауссовского источника с ограниченной полосой частот в бит/отсчёт равна:

Соответствующая функция искажение-скорость:

Выражая в децибелах и нормируя к σx² , получаем:
10logDg(R)/ σx² = -3R/W

Большое количество случаев, в которых гауссовский процесс не является ни белым, ни с ограниченной полосой, было рассмотрено Галлагером (1968) и Гобликом и Холсингером (1967).

Слайд 125

Скалярное квантование

Слайд 126

При кодировании источника квантователь может быть оптимизирован, если известна ФПВ уровней

сигнала на входе квантователя. Например, предположим, что последовательность {xn} на входе квантователя имеет ФПВ p(x) и - желаемое число уровней квантования. Необходимо рассчитать оптимальный скалярный квантователь, который минимизирует некоторую функцию ошибки квантования , где - квантованное значение x. Для дальнейшей разработки предположим, что
определяет желательную функцию ошибки. Тогда искажение, возникающее за счёт квантования сигнальных уровней, равно:

(1)

Слайд 127

В общем, оптимальный квантователь минимизирует D путём оптимального выбора выходных уровней

и входного диапазона для каждого выходного уровня. Эту оптимизационную проблему рассматривали Ллойд (1982) и Макс (1960), и полученный оптимальный квантователь назван квантователем Ллойда-Макса.

Слайд 128

У равномерного квантователя выходные уровни определяются как для амплитуды входного сигнала

в диапазоне , где ∆- размер шага квантования. Если квантователь симметричен (относительно нуля) с конечным числом уровней, среднее искажение (1) может быть выражено в виде:

(2)

Слайд 129

В этом случае минимизация D выполняется с учётом параметра размера шага

∆. Путём дифференцирования D по ∆ получаем:

(3)

где f´(x) означает производную f(x). При выборе критериальной функции ошибки f(x) можно получить численное решение (3) для оптимального размера шага на компьютере для произвольной заданной ФПВ p(x).

Слайд 130

Для среднеквадратичного критерия ошибки, кода f(x)=x², Макс(1960) рассчитал оптимальный размер шага

∆опт и минимальное значение среднеквадратической ошибки, когда ФПВ p(x) является гауссовской с нулевым средним и единичной дисперсией. Некоторые из этих результатов даны в табл.1

Слайд 131

Таблица 1. Оптимальные размеры шага при равномерном квантовании гауссовских случайных величин
Видим, что минимальная среднеквадратическая ошибка

Dmin уменьшается немного больше, чем на 5 дБ, при каждом удвоении числа уровней L. Следовательно, каждый бит, который используется равномерным квантователем с оптимальным размером числа ∆опт для гауссовского входного сигнала уменьшает искажение более чем на 5 дБ.

Слайд 132

Результирующее искажение:
(4)
снова минимизируется путём оптимального выбора
Необходимые условия для минимальных искажений можно

получить дифференцированием D по . Результат такой оптимизации выражается двумя уравнениями:

(5)

(6)

Как частный случай рассмотрим минимизацию среднеквадратических значений искажений. В этом случае, f(x)=x² , и, следовательно, из (5) следует:

(7)

Слайд 133

Соответствующие уравнения, определяющие
Таким образом, является центроидом области p(x) между xk-1

и xk.
Эти уравнения могут быть решены численно для произвольных ФПВ p(x) . Таблицы 2 и 3 дают результаты оптимизации Макса (1960) для оптимального четырёхуровневого и восьмиуровневого квантователя сигнала, распределённого по Гауссу с нулевым средним и единичной дисперсией.

(8)

Слайд 134

Таблица 2. Оптимальный 4-уровневый квантователь для гауссовской случайной величины
Dмин=0,1175
10lgDмин = -

9,3Дб

Слайд 135

Таблица 3. Оптимальный 8-уровневый квантизатор для гауссовской случайной величины (Макс, 1960)
Dмин=0,03454
10lgDмин

= - 14,62Дб

Слайд 136

Таблица 4. Сравнение оптимальных равномерного и неравномерного квантизаторов для гауссовской случайной

величины (Макс, 1960; Паез и Глиссон, 1972)

В таблице 4 сравниваются минимальные среднеквадратические искажения для гауссовской амплитуды сигнала в равномерном и неравномерном квантователях.

Слайд 137

Поучительно построить кривые зависимости минимальных искажений от битовой скорости R=log2L бит

на отсчёт (на символ) источника для равномерного и неравномерного квантователей.
Эти кривые даны на рис.1. Функциональную зависимость D искажений от битовой скорости R можно выразить как D(R) - функцию искажение-скорость. Мы видим, что функция искажение-скорость для оптимального неравномерного квантователя лежит ниже, чем для равномерного квантователя. Если отсчёты сигнала амплитуды статистически независимы, то на выходе квантователя имеем дискретный источник без памяти, и, следовательно, его энтропия:

(9)

Слайд 138

Рис. 1. Кривые зависимости искажение-скорость для гауссовского источника без памяти с

дискретным временем

Слайд 139

Для примера:
оптимальный четырёхуровневый неравномерный квантователь для распределённой по Гауссу амплитуды

приводит к вероятностям p1=p4=0,1635 для двух внешних уровней и p2=p3=0,3365 для двух внутренних уровней. В этом случае энтропия дискретного источника H(X)=1,911 бит/символ. Следовательно, при помощи энтропийного кодирования (кодирование Хаффмена) блоков выходных символов мы можем достичь минимальных искажений (-9,30 дБ) посредством 1,911 бит/символ вместо 2 бит/символ. Макс (1960) определил энтропию для дискретных символов источника после процесса квантования. Зависимость R(D) для этого случая также показана кривой на рис. 1 и обозначена как энтропийное кодирование.

Слайд 140

Таблица 5. Энтропия выхода оптимального неравномерного квантователя гауссовской случайной величины (Макс,

1960)

Слайд 141

Из этого обсуждения мы заключаем, что качество квантователя можно анализировать, когда

известна ФПВ непрерывного выхода источника. Оптимальный квантователь с уровнями обеспечивает минимальное искажение D(R) , где R=log2L бит/отсчёт. Такого уровня искажений можно достичь простым представлением каждого квантованного отсчёта битами. Однако возможно более эффективное кодирование.

Слайд 142

Дискретные выходы квантователя характеризуются рядом вероятностей {pk}, которые можно использовать для

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

Слайд 143

Если мы сравним характеристики оптимального неравномерного квантователя с функцией искажение-скорость, мы

найдём, например, что для искажения в -26 дБ энтропийное кодирование требует скорость на 0,4 бит/отсчёт больше, чем минимальная скорость, а простое блоковое кодирование каждого символа требует скорость на 0,68 бит/отсчёт больше, чем минимальная скорость. Мы также видим, что функция искажение-скорость для оптимального равномерного и неравномерного квантователей гауссовского источника асимптотически приближается к наклону -6 дБ/бит для больших .

Слайд 144

Тема: Векторное представление сообщений и сигналов.
Теория построения инфокоммуникационных систем и сетей

Слайд 145

В современной теории передачи информации для описания, анализа и преобразования сообщений

и сигналов широко используется геометрическое представление, при котором сигналы рассматриваются – как свойства пространства, преобразование сигналов – как отображение одного пространства в другое.
Введем понятие пространства сигналов. Пусть имеется множество сигналов S, обладающий некоторым общим свойством. Элементы этого множества отличаются друг от друга теми или другими параметрами (амплитудой, длительностью, частотой и т. п.). В общем случае отличия между двумя любыми элементами можно характеризовать некоторым положительным числом, которое трактуется как количественная мера различия сигналов и называется расстоянием. Множество сигналов S с подходящим образом определенным расстоянием между элементами называется пространством сигналов.

Векторное представление сообщений и сигналов

Слайд 146

Для определения расстояния между элементами пространства используют некоторый функционал d, который

обычно берется таким, чтобы удовлетворялись требования, являющиеся формализацией свойств, интуитивно связываемых с понятием расстояния:
(1)
Функционал, удовлетворяющий условиям (1), называется метрикой. Множество S с метрикой d называется метрическим пространством.

Векторное представление сообщений и сигналов

Слайд 147

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

является также сигнал. Сигналы можно усиливать или ослаблять. Все эти свойства находят отражения, если в качестве пространства сигналов взять так называемое линейное, или векторное, пространство. Оно удовлетворяет следующим условиям:
1. Для любых двух элементов пространства можно определить третий элемент, называемый суммой и входящий в данное пространство, такой, что
.
2. В пространстве сигналов имеется нулевой элемент 0, такой, что
для любых .
3. Для любого элемента , существует противоположный ему элемент
, принадлежащий данному пространству, такой, что .

Векторное представление сообщений и сигналов

Слайд 148

4. Любой элемент пространства можно умножить на любой элемент, принадлежащий скалярному

множеству ,на котором определены операции сложения и умножения с коммутативными и дистрибутивными свойствами и которое содержит в качестве элементов нуль и единицу, причем также является элементом пространства сигналов,
.
Элементы линейного пространства обычно называются векторами. Практически все реальные сигналы можно рассматривать как векторы в некотором пространстве. Так, если сигналы представлены последовательностями N действительных чисел, то такие сигналы можно представить N-мерными векторами. В общем случае любой непрерывный сигнал можно рассматривать как бесконечномерный вектор.

Векторное представление сообщений и сигналов

Слайд 149

Векторное пространство определяет простые алгебраические взаимосвязи между своими элементами. В частности,

любой сигнала как вектор может быть представлен в виде комбинация независимых векторов , i = 1, 2, …, N, т.е.
. (2)
Представление (2) является единственным, если векторы , i = 1, 2, …, N, образует линейно независимую систему.
Множество всех линейных комбинаций (2) образует N-мерное пространство. Множество линейно независимых векторов , i = 1, 2, …, N, называется базисом этого пространства. Упорядоченную последовательность скаляров , в (2) обычно интерпретируют как координаты вектора в базис
, i = 1, 2, …, N. При этом базис интерпретируют как некоторую систему координат, в общем случае косоугольную.

Векторное представление сообщений и сигналов

Слайд 150

Любой сигнал можно описать действительной или комплексной функцией, определенной на интервале

, который может быть и бесконечным. Множество таких функций образует также линейное пространство. Оно называется функциональным. В большинстве случаев функциональное пространство бесконечномерное. Для количественной характеристики сигналов в линейном пространстве вводят норму, определяющую длину векторов , обычно обозначаемую символом и удовлетворяющую условиям:
, если ;
, где - модуль скаляра .

Векторное представление сообщений и сигналов

Слайд 151

Для N-мерного линейного пространства действительных или комплексных чисел , j =

1, 2,…, норма определяется как
, (3)
а для функционального пространства – как
. (4)
При таком определении квадрат нормы представляет собой энергию сигнала.
В линейном нормированном пространстве в качестве метрики используется функционал
. (5)

Векторное представление сообщений и сигналов

Слайд 152

Для N-мерного линейного пространства действительных или комплексных чисел с учетом (3)

и(5)
, (6)
а для функционального пространства
. (7)
Метрика (7) имеет определенный физический смысл: ее квадрат равен энергии разности двух сигналов, она полностью характеризует различие между сигналами (чем больше ,тем больше это различие) и является удобной при расчетах.

Векторное представление сообщений и сигналов

Слайд 153

В линейном пространстве можно ввести понятие скалярного произведения двух элементов, которое

весьма полезно при рассматривании линейных способов обработки сигналов. Скалярное произведение определяют как
(8)
для функционального пространства и как
(9)
для N-мерного линейного пространства, где символ * означает комплексно-сопряженную функцию или величину.

Векторное представление сообщений и сигналов

Слайд 154

В функциональном анализе доказывается, что в пространстве со скалярным произведением можно

ввести норму, удовлетворяющую соотношению
, (10)
и метрику
. (11)
Таким образом, пространство со скалярным произведением можно всегда сделать нормированным и метрическим. Такое пространство при конечном числе N называется эвклидовым (обозначается ), а при бесконечном N – гильбертовым (обозначается ).
Введенные понятия пространства, нормы, метрики, базиса позволяют формализовать процессы, связанные с передачей и приемом сигналов.

Векторное представление сообщений и сигналов

Слайд 155

Векторное представление применимо как для детерминированных функций, так и для случайных.

В последнем случае скалярные произведения (8) и (9), норма (10) и расстояние (11) – случайные величины. Для случайных процессов также справедливо представление в виде (2). При этом коэффициенты являются случайными величинами, а само разложение понимается в смысле среднеквадратической сходности, т.е.
. (12)
В общем случае коэффициенты разложения коррелированные. Решение многих задач существенно облегчается, если выбрать ортогональный базис, в котором эти коэффициенты оказываются некоррелированными. Разложение случайного процесса по такому базису называется каноническим. Для стационарных процессов каноническое разложение всегда возможно.

Векторное представление сообщений и сигналов

Слайд 156

Тема: Дискретизация непрерывных сообщений с учетом их характеристик и реальных способов

восстановления.

Теория построения инфокоммуникационных систем и сетей

Слайд 157

Под дискретизацией понимается процесс представления непрерывного сообщения , заданного на интервале

,совокупностью координат
. В общем случае процессы представления и восстановления описываются выражениями:
, (1)
, (2)
где – оператор дискретного представления; – оператор восстановления.
Операторы дискретного представления и восстановления могут быть как линейными, так и нелинейными. На практике обычно используют линейные операторы как более простые в реализации.

Общие сведения

Слайд 158

При линейных процессах представления и восстановления выражения (1) и (2)

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

Общие сведения

Слайд 159

В данном случае используется система весовых функций ,
, где –

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