Галкин В.А., Григорьев Ю.А. - Телекоммуникации и сети (1053870), страница 22
Текст из файла (страница 22)
При формировании потока данных исходят из предположения о том, что два соседних кадра в видеопоследовательности мало отличаются. Опорные кадры сжимают по методуJPEG и передают относительно редко. В основном передаются изменения между соседними кадрами.Из приведенного краткого обзора алгоритмов сжатия очевидны два вьгоода:нет алгоритма, одинаково эффективного для данных разной природы;приведенные алгоритмы рассчитаны на сжатие данных, в которых есть последовательности одинаковых символов или одни символы встречаются чащедругих.На практике используют ряд алгоритмов сжатия, каждый из которых применим к определенному типу данных. Некоторые модемы (называемые интеллектуальными) предлагают адаптивное сжатие^ при котором в зависимости от передаваемых данных выбирается определенный алгоритм сжатия.Рассмотрим некоторые общие алгоритмы сжатия данных.Десятичная упаковка.
Когда данные состоят только из чисел, значительную экономию можно получить путем уменьшения количества используемыхна Щ1фру бит с 7 до 4, используя простое двоичное кодирование десятичныхШ1фр вместо кода ASCII. Просмотр таблицы ASCII показывает, что старшиетри бита всех кодов десятичных Щ1фр содержат комбинащпо 011. Если все данные в кадре информащш состоят из десятичных Щ1фр то, поместив в заголовок972. Основы телекоммуникациикадра соответствующий управляющий символ, можно существенно сократитьдлину кадра.Относительное кодирование. Альтернативой десятичной упаковке при передаче числовых данных с небольшими отклонениями между последовательными цифрами является передача только этих отклонений вместе с известнымопорным значением. Такой метод используют, в частности, в разновидностяхрассмотренного выше метода импульсно-кодовой модуляции.
При дифференциальной (разностной) ИКМ (ДИКМ, Differencial PCM, DPCM) вместо кодирования отсчетов кодируются разности между соседними отсчетами. Обычноразности отсчетов меньше самих отсчетов. Адаптивная ДИКМ (АДИКМ,Adaptive Differencial PCM, ADPCM) - система ДИКМ с адаптацией квантователя (АЦП и ЦАП) и предсказателя. При АДИКМ оцифровывается не самсигнал, а его отклонение от предсказанного значения.Символьное подавление.
Часто передаваемые данные содержат большоеколичество повторяющихся байт. Например, при передаче черно-белого изображения черные поверхности будут порождать большое количество нулевыхзначений, а максимально освещенные участки изображения - большое количество байт, состоящих из всех единиц.
Передатчик сканирует последовательность передаваемых байт и, если обнаруживает последовательность из трехили более одинаковых байт, заменяет ее специальной трехбайтовой последовательностью, в которой указывает значение байта, число его повторений, а также отмечает начало этой последовательности специальным управляющим символом.Коды переменной длины.
В этом методе кодирования используется тотфакт, что не все символы в передаваемом кадре встречаются с одинаковойчастотой. Поэтому во многих схемах кодирования коды часто встречающихсясимволов заменяют кодами меньшей длины, а редко встречающихся - кодамибольшей длины. Такое кодирование называется также статистическим кодированием.Одним из наиболее распространенных алгоритмов, на основе которых строятся неравномерные коды, является алгоритм Хаффмена, позволяющий строить коды автоматически, на основании известных частот появления символов.Рассмотрим его подробнее, предварительно определив критерий оценки эффективности кодирования.Эффективное кодирование. Избыточность является одной из основныххарактеристик кода, это - полезное свойство, так как оно повышает помехоустойчивость кода.
Однако для избыточных кодов для передачи по каналам связи требуется больше времени, кроме того, они занимают больший объемпамяти при хранешш информации. Большая избыточность не всегда оправданатребованиями помехоустойчивости при передаче и хранении информации. Поэтому возникает задача устранения избыточности, получившая название эффективного кодирования.982.2. Методы защиты от ошибок и слсатия данныхОпределим А^= {JCJ, jc^,..., JC^} - входной алфавит кода Г\ множество В - выходной алфавит того же кода: 5 = {О, 1, ..., m - 1}, где т - число элементовмножества В, Код Г сопоставляет каждому символу из входного алфавитаX е л;'кодовую комбинацию, составленную из п символов алфавита В- Гх == ь,ь,...ъ„,.Требуется оценить минимальную среднюю длину кодовой комбинации.Обозначим через/7(л:.) вероятность появления сообщения л:., тогда энтропиясообщений А^= {х^^х^^ -^^ху,H(X)=^-±p{x)logp(x),(2.81)I =1а средняя длина кодовой комбинации:« ^t'^,/^^.)^(2.82)/=1Максимальная энтропия, которую может иметь сообщение из символов алфавита В равно^nax = «cpl0g/W.(2.83)Для обеспечения передачи информации, содержащейся в сообщениях X, спомопц>ю кодовых комбинаций в алфавите В должно вьшолняться неравенствоЯ«ах>Я(^.(2.84)В случае строгого неравенства Д„ах > Щ^ имеет место избыточность, которую определяют через коэффициент избыточности К^^ :Ли77•U-85)-'''maxОценим минимальную среднюю длину кодовой комбинации, при которой ещевозможна передача сообщения А'без потери информации.
Учитывая (2.83) и(2.84), получим:«ер > - ^т. е.,(2.86)logm«mi„= - ^ .(2.87)logmВыражение (2.85) для коэффициента избьггочности с учетом (2.87) можнопредставить в следующем виде:п - «.К^ = -^—.(2.88)ср992. Основы телекоммуникацииПод эффективным кодом понимают код, коэффициент избыточности которого равен нулю, т. е. для эффективньпс кодов Яср= п . или с учетом (2.81),(2.82) и (2.83):t n^p{x)\og т=-±р{х)\о% р(х).(2.89)/ =1/ =1Объединив суммы левой и правой части, получим:± p(x)[nAog т + logpix)] = 0.(2.90)Если/7(л:.) ^ О, то необходимо, чтобып.=log/?(x)log/wдлявсех/= 1,2, ...,г.(2.91)Однако отношение (2.91) не всегда является целым числом и, следовательно, не для любого набора сообщений ^ = {лг^ х^,..., х^} с заданным распределе1шем вероятности/7(л:^),/7(л:2), ,..,р(х^) можно построить эффективный код сминимальной избыточностью К^ = 0.
Всегда можно обеспечить вьшолнениенеравенства:logpix)logp(x)..U^<n< - l i ^ \ 1,(2.92)log m""^ log mили умножая части неравенства на р(х) и суммируя по /, получим критерийоценки эффективности реального кода:Н(Х)Н(Х)<п <log т 'Р+ 1.log т(2.93)Выражение для коэффициента избыгочности равномерного двоичного кодаопределим по формуле (2.85), в которой под максимальной энтропией Н^^ будем понимать максимальную энтропию равномерного «-разрядного кода,п^ = п,т = 2.
При этом максимальная энтропия Н^^ = п^ log т = п. Под энтропией сообщений Н(Х) буцем понимать энтропию разрешенных кодовых комбинаций, число которьк обозначим через N, тогда Н(Х) = log N.Подставляя выражения для Н^^ и Н(Х) в (2.85 ), имеемK^=^(n-logN)/n=l-XogN/n,(2.94)Для разделимых кодов формула упрощается:/:^ = 1 - (log 20 / « = 1 - к/п,(2.95)где п - длина кодовой комбинации; к - число информационных разрядов.1002.2. Методы защиты от ошибок и сжатия данныхАнализ формулы (2.85) показьшает, что коэффициент избыточности принимает значения от О (отсутствие избыточности) до 1 (избыточность неограниченно велика).
Коэффициент избыточности характеризует качество помехоустойчивого кода - чем меньше избыточность кода при прочих равных условиях,тем код лучше.Алгоритм Хаффмена. Этот алгоритм применяют для построения кодов сминимальной избыточностью. Пусть Х- {Xj, х^, ..., х^} - входной алфавиткода /", а 5{0, 1} - выходной алфавит.
С каждым символом х. связана вероятность его появления/>(х.). Необходимо каждому символу алфавита Jf сопоставить кодовую комбинацию в алфавите В таким образом, чтобы обеспечитьминимальную избыточность кода Г,Поставленную задачу можно решить построением кодового дерева. Построение графа-дерева начинают с висячих вершин, которым в качестве весовназначают вероятности/7(л:.), / = 1,2,..., г. Висячие вершины графа упорядочивают в соответствии с их весом, что позволяет в дальнейшем уменьшить число пересечений ребер или вовсе исключить их.
Само дерево строится по следующему алгоритму.Шаг 7. Определяют число поддеревьев графа. Если оно меньше двух, тодерево построено, и на этом действие алгоритма заканчивается. Если числоподдеревьев равно или больше двух, то переходят к шагу 2 (Замечание: в начале построения имеется г изолированных вершин графа, являющихся поддеревьями и одновременно корнями поддеревьев).Шаг 2, Выбирают корни двух поддеревьев графа с минимальными весамии осуществляется сращивание выбранных поддеревьев с добавлением при этомодной вершины и двух ребер. Вес вновь образованной вершины определяетсякак сумма весов корней выбранных поддеревьев.
Левому добавленному ребруприписьюается вес, равный единице, правом}^ - равный нулю. Осуществляетсяпереход к шагу 1.В результате образуется кодовое дерево - граф с взвешенными ребрами.Для получения кода символа х. достаточно выписать веса ребер, составляющих путь из корня дерева в соответствующую висячую вершину.Пример. Пусть входной алфавит содержит восемь различных символов дг,, дг^,..., ^g, выходной алфавит является двоичным JB{0,1}, число символов выходного алфавита m = 2.
Известнавероятность (частота) появления каждого символа в передаваемом сообщении: р(дг,) = 0,19; р{х^ = р{х^) =0,16; р{х^ =0,15; р{х^) =0,12; р(х^ =0,11; р{х^) =0,09; р{х^ = 0,02. Необходиморазработать код и определить коэффициент избыточности кода.Процесс построения кодового дерева содержит семь циклов последовательного выполненияшагов 1 и 2 алгоритма (рис. 2.15). Для оценки эффективности кода промежуточные вычислениязанесем в табл.
2.4.Средняя длина кодовой комбинации''cp=Z"/M^.) = 2,92;1012. Основы телекоммуникацииЦиклРис. 2.15. Построение кодового дереваэнтропия сообщения, составленного из символов входного алфавига, равнаЩХ) = - Z p{x)\og^p{x) = 2,855.Таблица 2.4. Промежуточные значения вычисления энтропии для кода ХаффменаДлина кодовойКодоваяriipix)Символ- p{x)\og2p(x)комбинации (w,)комбинация20.38100.455^100030.480.423Xl00130.480.423хг1 х^01030.450.41101130.360.367Х511030.330.350Хб111040.360.313Xl111140.080.1131х%Минимальная длина кодовой комбинации выходного алфавита, необходимая для передачисообщения, составленного из символов входного алфавига, без потери информации:HjX) _ 2,855= 2,855.log m log 2Коэффициент избьпх>чности кода, построенного по алгоритму Хаффмена, в соответствии с(2.88) равенп -пК^ = —^= 0,022,т.
е. построенный код практически избьпочности не имеет.1022.2. Методы защиты от ошибок и сжатия данныхКорневые узлы© ©Листьевые узлыРис. 2.16. Представление части словаря, содержащего строки:А, AN, ANGEL, AND, В, С, СА, CAR, CACHE, D, ЕНаряду с рассмотренным алгоритмом Хаффмена, который требует дополнительного просмотра данных для вычисления значенийp(x.), существуют егоадаптивные модификации, позволяющие строить кодовое дерево «на ходу», помере поступления данных от источника.Протоколы сэюатия MNP5 и V.42bis. В отличие от протокола MNP5 протокол V.42bis не заменяет конкретные, наиболее часто встречающиеся символы на более короткие кодовые слова, а делает это для последовательностейсимволов (строк).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
