Динамо-машины  Сигналы и спектры 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 [ 286 ] 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358

Окончание табл. 13.1

Пример 13.8. Код группового кодирования

Используйте модифицированный код Хаффмана для сжатия строки

200 Б, 10 Ч, 10 Б, 84 Ч, 1424 Б,

состоящей из 1728 пиксельных элементов. Решение

Используя табл. 13.1, определим, каким должно быть кодирование для этой модели (для

удобства чтения введены пробелы).

010111 10011 0000100 00111 192Б 8Б 104 10Б

0000001111 00001101000 644 204

000000000001 EOL

Итак, требуется всего 56 бит, чтобы послать эту строку, содержащую последовательность 1188 бит.

13.7.3.2. Коды Лемпеля-Зива (ZIP)

Основной сложностью при использовании кода Хаффмана является то, что вероятности символов должны бьпъ известны или оценены и как кодер, так и декодер должны знать дерево кодирования. Если дерево строится из необычного для кодера алфавита, канал, связывающий кодер и декодер, должен также отправлять кодирующее дерево как заголовок сжатого файла. Эти служебные издержки уменьшат эффективность сжатия, реализованную с помощью построения и применения дерева к алфавиту источника. Алгоритм Лемпеля-Зива (Lempel-Ziv) и его многочисленные разновидности используют текст сам по себе для итеративного построения синтаксически вьщеленной последовательности кодовых слов переменной длины, которые образуют кодовый словарь.

Код предполагает, что существующий словарь содержит уже закодированные сегменты последовательности символов алфавита. Данные кодируются с помощью просмотра существующего словаря для согласования со следующим коротким сегментом кодируемой последовательности. Если согласование найдено, код следует такой фило-

софии: поскольку получатель уже имеет этот сегмент кода в своей памяти, нет необходимости пересылать его, требуется только определить адрес, чтобы найти сегмент. Код ссылается на расположение последовательности сегмента и затем дополняет следующий символ в последовательности, чтобы образовать новую позицию в словаре кода. Код начинается с пустого словаря, так что первые элементы являются позициями, которые не ссылаются на более ранние. В одной форме словаря рекуррентно формируется выполняемая последовательность адресов и сегмент символов алфавита, содержащийся в ней. Закодированные данные состоят из пакета lt;адрес словаря, следующий знак данных gt;, а каждый новый входной элемент словаря образован как пакет, содержащий адрес того словаря, за которым следует следующий символ. Рассмотрим пример такой технологии кодирования.

Закодируйте последовательность символов[abaababbbbbbbabbbba]

Закодированные lt;0,а gt;, lt;0,Ь gt;, lt;1,а gt;, lt;2,а gt;, lt;2,Ь gt;, lt;5,Ь gt;, lt;5,а gt;, lt;6,Ь gt;, lt;4,- gt; пакеты:

Адрес: 1 2 3 4 5 6 7 8

Содержимое: а b аа Ьа bb bbb bba bbbb

Начальный пакет lt;0,а gt; показывает нулевой адрес, потому что в словаре еще нет ни одной позиции. В этом пакете знак а является первым в последовательности данных, и он приписан к адресу 1. Следующий пакет lt;0,Ь gt; содержит второй знак данных Ь, который еще не был в словаре (следовательно, адресное значение есть 0); b приписывается адресу 2. Пакет lt;1,а gt; представляет кодирование следующих двух знаков аа с помощью вызова адреса 1 для первого и присоединения к этому адресу следующего знака а . Пара знаков аа приписывается адресу 3. Пакет lt;2,а gt; представляет кодирование следующих двух знаков данных Ьа с помощью вызова адреса 2 для знака Ь и присоединения к этому адресу следующего знака а . Пара знаков данных Ьа приписывается адресу 4 и т.д. Отметим, как завершается фупповое кодирование. Восьмой пакет составлен из адреса 6, содержащего три знака Ь , за которыми следует другой знак Ь . В этом примере закодированные данные могут быть описаны с помощью трехбитового адреса с последующим битом О или 1 для определения присоединенного знака. В закодированной последовательности существует последовательность из 9 символов для общего содержимого в 36 бит для кодирования данных, содержащих 20 знаков. Как во многих схемах сжатия, эффективность кодирования не достигается для коротких последовательностей, как в этом примере, и имеется только для длинных последовательностей.

В другой форме алгоритма Лемпеля-Зива закодированные данные представлены как три словесных пакета вида lt;число знаков сзади, длина, следующий знак gt;. Здесь концепция адреса не используется. Наоборот, имеются ссылки на предшествующие последовательности данных, а также допускаются рекуррентные ссылки на параметр длины. Это показано в следующем примере, представленном как позиция lt;1,7,а gt;.

Закодируйте последовательность символов [abaababbbbbbbabbbbba]

Закодированные lt;0,0,а gt;, lt;0,0,Ь gt;, lt;2,1,а gt;, lt;3,2,Ь gt;, lt;1,7,а gt;, lt;6,5,а gt;

пакеты:

Содержимое: а b аа bab bbbbbbba bbbbba

Текущий текст: а аЬ аЬаа abaabab abaababbbbbbbba вся

последовательность

Здесь также не видно эффективности кодирования для короткой серии данных. Разновидности кода ограничивают размер обратной ссылки, например 12-битовая для максимума в 4 096 пунктов обратной ссылки. Это Офаничение уменьшает размер памяти, требуемой для словаря, и сокращает вероятность перефузки памяти. Возможны также модификации кода, Офаничивающие длину префикса или фразы, определенной первыми двумя аргументами lt;назац п1, вперед п2, ххх gt;, которые должны быть меньше некоторого значения (например, 16) с целью Офаничения сложности обратного поиска во время кодирования. Алгоритм Лемпеля-Зива присутствует во многих коммерческих и пробных профаммах, которые включают сжатие LZ77, Gzip, LZ78, LZW и UNIX.

13.8. Примеры кодирования источника

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

13.8.1. Аудиосжатие

Аудиосжатие широко применяется в потребительских и профессиональных цифровых аудиопродуктах, таких как компакт-диски (compact disc - CD), цифровая аудиолента (digital audio type - DAT), мини-диск (mini-disk - MD), цифровая компакт-кассета (digital compact cassette - DCC), универсальный цифровой диск (digital versatile disc - DVD), цифровое аудиовещание (digital audio broadcasting - DAB) и аудиопродукция в формате МРЗ от экспертной группы по вопросам движущегося изображения (Motion Picture Experts Group - (MPEG). К тому же сжатие речи в телефонии, в частности сотовой телефонии, требуемое для экономии полосы частот и сбережения времени жизни батареи, дало начало процессу разработки множества стандартов сжатия речи. Различные алгоритмы применимы к речевым и потребительским сигналам более широкой полосы частот. Аудио- и речевые схемы сжатия можно для удобства разделить согласно приложениям, что отражает некоторую меру приемлемого качества. Рассмотрим параметры, описывающие это деление [24, 25].

Типичные значения параметров для трех классов аудиосигналов

Диапазон Частота Бит Скорость

частот дискретизации РСМ/выборку передачи

битов РСМ