www.chms.ru - вывоз мусора в Балашихе |
Динамо-машины Сигналы и спектры
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
Чтобы улучшить эффективность кодирования или достичь большего сжатия, следует переопределить алфавит источника. Больший алфавит источника увеличивает разнообразие, что является одним из требований при сокращении средней длины кода и увеличении числа ветвей дерева для присвоения кода переменной длины. Это делается посредством выбора знаков (по два) из алфавита источника, которые становятся новыми знаками в расширенном алфавите. Если предположить, что символы независимы, вероятность каждого нового элемента является произведением отдельных вероятностей. Алфавит расширения имеет следующий вид.
X, Р{Х,) Код п, п,Р{Х,)
0,5329 | 0,5329 | |||
0,1825 | 0,3650 | |||
0,1825 | 0,5475 | |||
0,0625 | 0101 | 0,2500 | ||
0,0146 | 01000 | 0,0730 | ||
0,0146 | 010011 | 0,0876 | ||
0,0050 | 0100100 | 0,0350 | ||
0,0050 | 01001011 | 0,0400 | ||
0,0002 | 01001010 | 0,0016 п = 1,9326 бит/два символа = 0,9663 бит/символ |
Здесь i = 1,9, а кодовая последовательность для каждого X, была найдена с использованием выше приведенной процедуры Хаффмана. Коэффициент сжатия для этого кода расширения равен 2,076, а эффективность кодирования - 97,7%. Коды расширения предлагают очень мощную технологию включения эффектов множеств символов, которые не являются независимыми. Например, в английском алфавите соседние буквы являются высоко коррелированными. Очень часто встречаются следующие пары букв.
th ге in
sh he е
de ed s
ng at r
te es d
Здесь подчеркивание представляет пробел. Наиболее общими английскими наборами трех букв являются следующие.
the and for
ing ion ess
Таким образом, вместо того чтобы производить кодирование Хаффмана отдельных букв, более эффективно расширить алфавит, включив все 1-кортежи плюс распространенные 2- и 3-кортежи, а затем произвести кодирование с помощью кода расширения.
13.7.3. Групповые коды
Во многих приложениях последовательность символов, которую необходимо передать или запомнить, характеризует последовательное кодирование определенных символов. Иногда, вместо того чтобы кодировать каждый символ последовательности, есть смысл описать группу с помощью подстановочного кода. В качестве примера рассмотрим случай, когда последовательности пробелов (наиболее употребимый символ в
тексте) кодируются во многих протоколах связи с помощью символа управления, за которым следует счетчик символов. Протокол IBM 3780 BISYNC имеет опцию замены последовательности пробелов с помощью знака IGS (если имеем дело с EBCDIC) или GS (если имеем дело с ASCII), за которым следует счетчик от 2 до 63. Более длинные последовательности делятся на серии по 63 знака.
Групповое подстановочное кодирование может быть применено к исходному алфавиту символов или двоичному представлению этого алфавита. В частности, групповое кодирование является удачным для двоичных алфавитов, полученных от специфических источников. Наиболее важным коммерческим примером является факсимильное кодирование, используемое для передачи документов по мгновенной электронной почте [22].
13.7.3.1. Кодирование Хаффмана для факсимильной передачи
Факсимильная передача - это процесс передачи двухмерного образа как последовательности последовательных строчных разверток. В действительности наиболее распространенными образами являются документы, содержащие текст и цифры. Положение строчной развертки и положение вдоль развертки квантуются в пространственные расположения, которые определяют двухмерную координатную сетку элементов картинки, называемых пикселями. Ширина стандартного документа МККТТ определяется равной 8,27 дюймов (20,7 см ), а длина - 11,7 дюймов (29,2 см), почти 8,5 дюймов на 11,0 дюймов. Пространственное квантование для нормального разрешения составляет 1728 пикселей/строку и 1188 строк/документ. Стандарт также определяет квантование с высоким разрешением с теми же 1728 пикселями/строку, но с 2376 строками/документ. Общее число отдельных пикселей для факсимильной передачи с нормальным разрешением составляет 2 052 864, и оно удваивается для высокого разрешения. Для сравнения, число пикселей в стандарте NTSC (National Television Standards Committee - Национальный комитет по телевизионным стандартам) коммерческого телевидения составляет 480 х 460, или 307 200. Таким образом, факсимильное изображение имеет разрешение в 6,7 или 13,4 раза больше разрешения стандартного телевизионного образа.
Относительная яркость или затемненность развернутого образа в каждом положении на строке развертки квантуется в два уровня: Ч (черный) и Б (белый). Таким образом, сигнал, наблюдаемый на протяжении линии развертки, - это двухуровневая модель, представляющая элементы Ч и Б. Легко видеть, что горизонтальная развертка данной страницы будет представлять последовательность, состоящую из длинных групп уровней Ч и Б. Стандарт МККТТ схемы группового кодирования для сжатия отрезков Ч и Б уровней базируется на модифицированном коде Хаффмана переменной длины, который приведен в табл. 13.1. Определяются два типа шаблонов, группы Б и Ч. Каждый отрезок описывается кодовыми словами деления. Первое деление, названное созданное кодовое слово, определяет фуппы с длинами, кратными 64. Второе деление, именуемое оконечное кодовое слово, определяет длину оставшейся фуппы. Каждая серия из знаков Ч (или Б), длиной от О до 63, обозначает единственное кодовое слово Хаффмана, как и каждая фуппа длины 64 х ЛГ, где ЛГ= 1, 2,27. Также кодом определен уникальный символ конца строки (end of line - EOL), который указывает, что дальше не следуют черные пиксели. Следовательно, должна начаться следующая строка, что подобно возврату каретки пишущей машинки [23].
Таблица 13.1. Модифицированный код Хаффмана для стандарта факсимильной связи МККТТ
Длина группы | Белые | Черные | Длина группы | Белые | Черные |
Созданные кодовые слова | |||||
0000001111 | 011010100 | 0000001110011 | |||
10010 | 000011001000 | 1024 | 011010101 | 0000001110100 | |
010111 | 000011001001 | 1088 | 011010110 | 0000001110101 | |
0110111 | 000001011011 | 1152 | 011010111 | 0000001110110 | |
00110110 | 000000110011 | 1216 | 011011000 | 0000001110111 | |
00110111 | 000000110100 | 1280 | 011011001 | 0000001010010 | |
01100100 | 000000110101 | 1344 | 011011010 | 0000001010011 | |
01100101 | 0000001101100 | 1408 | 011011011 | 0000001010100 | |
01101000 | 0000001101101 | 1472 | 010011000 | 0000001010101 | |
01100111 | 0000001001010 | 1536 | 010011001 | 0000001011010 | |
011001100 | 0000001001011 | 1600 | 010011010 | 0000001011011 | |
011001101 | 0000001001100 | 1664 | 011000 | 0000001100100 | |
011010010 | 0000001001101 | 1728 | 010011011 | 0000001100101 | |
011010011 | 0000001110010 | 000000000001 | 000000000001 | ||
Длина группы | Белые | Черные | Длина группы | Белые | Черные |
Оконечные кодовые слова | |||||
00110101 | 000110111 | 00011011 | 000001101010 | ||
000111 | 00010010 | 000001101011 | |||
0111 | 00010011 | 000011010010 | |||
1000 | 00010100 | 000011010011 | |||
1011 | 00010101 | 000011010100 | |||
1100 | 00010110 | 000011010101 | |||
1110 | 0010 | 00010111 | 000011010110 | ||
1111 | 00011 | 00101000 | 000011010111 | ||
10011 | 000101 | 00101001 | 000001101100 | ||
10100 | 000100 | 00101010 | 000001101101 | ||
00111 | 0000100 | 00101011 | 000011011010 | ||
01000 | 0000101 | 00101100 | 000011011011 | ||
001000 | 0000111 | 00101101 | 000001010100 | ||
000011 | 00000100 | 00000100 | 000001010101 | ||
110100 | 00000111 | 00000101 | 000001010110 | ||
110101 | 000011000 | 00001010 | 000001010111 | ||
101010 | 0000010111 | 00001011 | 000001100100 | ||
101011 | 0000011000 | 01010010 | 000001100101 | ||
0100111 | 0000001000 | 01010011 | 000001010010 |