конспект ТЭС кодирование сообщений нов
.pdfа1 |
0,12 |
|
|
1 |
|
101 |
а7 |
0,10 |
|
1 |
0 |
|
110 |
а5 |
0,07 |
|
1 |
0 |
1110 |
|
а2 |
0,03 |
|
|
1 |
1111 |
|
|
|
|
В результате кодирования получен неравномерный префиксный код, обеспечивающий однозначное декодирование сообщений. Для расчета полученной степени сжатия определим число n двоичных символов "0" и " 1", необходимых для кодирования любого из сообщений равномерным двоичным кодом, и среднее число кодовых символов nср, затрачиваемых на кодирование одного сообщения в таблице 3.2. Значения чисел n и nср находят из
М
выражений n≥log2M и nср = ∑ p( ai ) ni ,
i=1
где ni - количество символов, затраченных для кодирования сообщения аi.
Для сообщений из таблицы 2
n = log2 8 = 3 ; nср=0,2·2+0,2·3+0,15·3+0,13·3+0,12·3+0,10·3+0,07·4+0,03·4=2,9
Энтропия источника сообщений составляет
Н( А) = −∑8 |
p( аi )log2 p( ai ) = 2,81 |
бит |
|
сообщение |
|||
1 |
|
Степень сжатия будет равна: n/nср = 3/2,9 ≈1,0345. Потери информации при кодировании сообщений неравномерным кодом не произойдет, поскольку, как видно из примера, nср больше Н(А), то есть энтропия источника не уменьшится.
Кодирование по алгоритму Шеннона-Фано не всегда приводит к однозначному построению кода, поскольку при разбиении сообщений на группы можно сделать больше по вероятности как верхнюю, так и нижнюю группу сообщений. Этот метод не обеспечивает отыскания оптимального множества кодовых слов для кодирования данного множества сообщений. Под оптимальностью подразумевается то, что никакое другое однозначно кодируемое множество кодовых слов не имеет меньшую среднюю длину кодового слова, чем заданное множество.
11
Коды Хаффмана
Метод сжатия, предложенный Хаффманом, свободен от недостатков метода Шеннона-Фано и широко применяется в настоящее время.
Алгоритм кодирования по методу Хаффмана состоит в следующем:
1 Все сообщения источника располагают в таблице в один (основной) столбец в порядке убывания их вероятностей.
2 Два самых маловероятных сообщения (два последних) объединяют в одно и вычисляют их суммарную вероятность.
3 Вероятности сообщений, не участвующих в объединении, и вероятность полученного вспомогательного сообщения располагают во вспомогательном столбце в порядке убывания вероятностей. При необходимости во вспомогательном столбце проводят перегруппировку вероятностей.
4 Два самых маловероятных сообщения полученного вспомогательного столбца объединяют в одно и вычисляют их суммарную вероятность.
5 Повторяют шаги 3 и 4, создавая новые вспомогательные столбцы, до тех пор, пока не получат единственное сообщение, вероятность которого Р=1,0.
6 Строят кодовое дерево Хаффмана, начиная от сообщения вероятностью Р=1,0. От этой вероятности отводят две ветви, соответствующие двум вероятностям, давшим в сумме вероятностьР=1,0. Ветви с большей вероятностей присваивают символ "1", а с меньшей − "0". Затем каждую из полученных ветвей вновь разветвляют на две и так продолжается до тех пор, пока не доходят до концевых узлов, соответствующих вероятностям каждого из исходных сообщений аi. При присвоении ветвям символов «1» и «0» необходимо соблюдать постоянство в расположении ветвей (например, левая ветвь всегда «1»). При разветвлении ветви на две равновероятные одной из них присваивается "1", а другой "0".
7 Кодируют исходные сообщения, двигаясь по ветвям кодового дерева в направлении от вероятности Р=1,0 к концевым узлам, соответствующим определенным сообщениям.
12
Пример 2. Требуется закодировать кодом Хаффмана восемь
сообщений а1, а2, а3, а4, а5, а6, а7, а8, с вероятностями р(а1)=0,16;
р(а2)=0,10; р(а3)=0,04; р(а4)=0,16; р(а5)=0,22; р(а6)=0,02; р(а7)=0,20; р(а8)=0,10.
Этапы объединения вероятностей сообщений а1…а8 во вспомогательные столбцы продемонстрированы в таблице 3. На рисунке 2 приведено кодовое дерево, построенное по результатам данных таблицы 3. Кодовые комбинации, полученные в результате кодирования, приведены в таблице 4. Они представляют собой неравномерный префиксный код.
Таблица 3−Формирование вспомогательных столбцов кода Хаффмана
Сообщения |
|
|
Вероят- |
|
|
|
|
|
|
|
|
|
Вспомогательные столбцы |
|
|||||||||||
|
аi |
|
ности р(аi) |
|
1 |
|
|
|
2 |
|
3 |
4 |
5 |
6 |
|
7 |
|||||||||
а5 |
|
0,22 |
|
|
|
|
0,22 |
|
|
0,22 |
0,26 |
0,32 |
0,42 |
0,58 |
1,00 |
||||||||||
а7 |
|
0,20 |
|
|
|
|
0,20 |
|
|
0,20 |
0,22 |
0,26 |
0,32 |
0,42 |
|
||||||||||
а1 |
|
0,16 |
|
|
|
|
0,16 |
|
|
0,16 |
0,20 |
0,22 |
0,26 |
|
|
|
|||||||||
а4 |
|
0,16 |
|
|
|
|
0,16 |
|
|
0,16 |
0,16 |
0,20 |
|
|
|
|
|
||||||||
а2 |
|
0,10 |
|
|
|
|
0,10 |
|
|
0,16 |
0,16 |
|
|
|
|
|
|
||||||||
а8 |
|
0,10 |
|
|
|
|
0,10 |
|
|
0,10 |
|
|
|
|
|
|
|
|
|||||||
а3 |
|
0,04 |
|
|
|
|
0,06 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
а6 |
|
0,02 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,58 |
|
|
0,42 |
|
|
|
|
|||||
|
|
0,32 |
|
|
0,26 |
|
|
"1" |
|
|
|
"0" |
0,22 |
0,2 |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
0,16 |
"1" |
|
|
" 0" |
|
|
|
0,1 |
|
|
|
|
|
" 1" |
" 0" |
|
|
||||||||
0,16 |
|
|
|
|
|
0,16 |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
"1" |
"0" |
|
|
|
|
|
"1" |
|
|
|
"0" |
|
|
|
|
|
|
|
|
|
||||
|
0,1 |
|
|
|
|
|
|
|
а5 |
а7 |
|
||||||||||||||
|
|
|
|
|
|
0,06 |
|
|
|
|
|
а2 |
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
а |
1 |
|
а |
|
|
"1" |
"0" |
|
0,02 |
|
|
|
|
|
|
|
|
|
|||||||
|
|
4 |
|
|
|
0,04 |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
а |
8 |
|
"1" |
|
|
"0" |
|
|
|
|
|
|
|
|
|
|
||||
а3 а6
Рисунок 2 − Кодовое дерево кода Хаффмана
13
Таблица 4 − Кодовые комбинации кода Хаффмана
Сообще- |
а1 |
а2 |
а3 |
а4 |
а5 |
а6 |
а7 |
а8 |
ние |
|
|
|
|
|
|
|
|
Код |
111 |
100 |
10101 |
110 |
01 |
10100 |
00 |
1011 |
Для полученного кода среднее число символов «0» и «1», приходящихся на одно закодированное сообщение, составит: nср=0,22·2+0,2·2+0,16·3+0,16·3+0,10·3+0,10·4+0,04·5+0,02·5=2,8
Степень сжатия равна 3/2,8=1,071.
Словарные методы сжатия
Метод специальных словарей используется при кодировании сообщений, между которыми выявлены статистические связи. Поясним на примерах.
Так, если элементарными сообщениями являются буквы русского алфавита (примем, что их число М=32=25) и они передаются равновероятно и независимо, то энтропия источника, при-
ходящаяся |
на |
одну |
букву, |
составит |
||
H (A) = log2 |
M = log2 |
32 = 5 |
бит |
. |
То есть |
каждую букву |
|
||||||
|
|
|
букву |
|
|
|
можно закодировать последовательностью из пяти двоичных символов. Если же буквы составляют связный русский текст, то они оказываются неравновероятными (например, буква А передается значительно чаще, чем буква Ф) и, главное, зависимыми. Так, после гласных не может появиться "ь" и др. Подсчитано, что для текстов русской художественной прозы энтропия оказывается менее 1,5 бит/букву и, следовательно, возможен способ эффективного кодирования текстов без потери информации, при котором в среднем на одну букву будет затрачено не 5, а немногим более 1,5 двоичных символов, то есть на 70% меньше. Существует довольно много способов сокращения избыточности текста. Так вместо "ААА" можно закодировать "3А" или же сокращать слова, как это делается в стенографии. Особенно большой эффект дает укрупнение алфавита, когда кодируются не отдельные буквы, а целые слова.
14
Рассмотрим следующий пример. В достаточно большом словаре имеется около 10000 слов, содержащих в среднем по 7 букв. Как указывалось выше, на кодирование одной буквы русского алфавита требуется 5 двоичных символов, а на одно слова,
состоящее из 7 букв - 5×7 =35 символов. Для кодирования
10000 слов необходимо затратить 350000 тысяч символов. Если же кодировать не буквы, а эти 10000 слов и дополнительно еще по две грамматические формы на каждое слово, то на каждое из 30000 слов придется затратить по 15 двоичных символов вместо 35 (215=32768). Таким образом, в среднем на букву придется немногим больше двух символов, т.е. сжатие достигнет 60%. Слова, не вошедшие во вновь созданный словарь, придется передавать обычным способом, затрачивая по пять символов на букву.
Существуют различные способы создания словарей. Большинство из них базируются на универсальных алгоритмах сжатия LZ77 и LZ78, разработанных в 70-е годы ХХ века совместно Зивом (Ziv) и Лемпелем (Lempel). Сжатая информация содержит меньше битов, чем исходная, но по ней возможно однозначное восстановление каждого бита исходных данных. Процесс восстановления информации называется разжатием. Используют и такие пары терминов: компрессия/декомпрессия, кодирование/декодирование, упаковка/распаковка. Очевидно, что, кроме собственно словаря, созданный сжатый файл должен содержать последовательность ссылок на этот словарь.
Принципиальным отличием алгоритмов LZ77 и LZ78 является способ формирования фраз. В алгоритмах LZ77 в качестве словаря используется блок уже закодированной последовательности данных. Как правило, по мере выполнения обработки потока информации положение этого блока относительно начала входной последовательности постоянно меняется, словарь "скользит" по входному потоку данных. Поэтому алгоритмы сжатия, в основе которых LZ77, называют алгоритмами со скользящим словарем, или скользящим окном. Алгоритм LZ77 эффективен для сжатия сравнительно длинных последовательностей и мало эффективен – для коротких.
15
Алгоритмы группы LZ78 не используют скользящего окна и в создаваемый словарь помещают не все встречаемые при кодировании строки, а лишь "перспективные" с точки зрения вероятности последующего использования. В начале обработки словарь пуст. Далее, теоретически, словарь может расти бесконечно, т.е. на его рост сам алгоритм не налагает ограничений. На практике при достижении определенного объема занимаемой памяти словарь должен очищаться полностью или частично.
Разработано большое число модификаций алгоритмов LZ77 и LZ78. Их наименования содержат буквы LZ и первые буквы фамилий авторов модификации. Например: LZBW - авторы Бендер
(Bender) и Вулф (Wolf); LZCB - автор Блум (Bloom).
Сжатие информации с потерями
Для увеличения степени сжатия звуковых сигналов (аудио) и сигналов изображения (видео) целесообразно устранять (сокращать) психофизиологическую избыточность, вызванную тем, что человек не способен воспринимать звуковые и оптические сообщения в полном объеме из-за особенностей строения органов слуха и зрения. Несмотря на то, что при сжатии с потерями часть информации безвозвратно теряется, это не должно отражаться на качестве сообщения при его получении.
Алгоритм устранения психофизиологической избыточности (модель) строится с учетом цели сжатия и особенностей источника и приемника информации. Так, если требуется компьютерная обработка изображения или звука, то требования к потерям гораздо более жесткие, чем для случая, когда получателем сообщения является человек. После устранения психофизиологической избыточности точное восстановление первичного звукового или видеосигнала при декодировании оказывается уже невозможным. Энтропия источника сообщений после сжатия информации с потерями уменьшается.
Работы по анализу качества и оценке эффективности алгоритмов компрессии цифровых аудио- и видеоданных с целью их последующей стандартизации начались в 1988 году, когда Международным союзом электросвязи была образована междуна-
родная экспертная группа MPEG (Moving Pictures Experts
16
Group). Итогом работы этой группы на первом этапе явилась разработка в 1992 году международного стандарта MPEG-1. В дальнейшем были разработаны стандарты сжатия MPEG-2, MPEG-4, MPEG-7, MPEG-21. Стандарт MPEG-2 разработан для использования в системах вещательного телевидения.
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
Основные принципы помехоустойчивого кодирования
Помехоустойчивое кодирование повышает достоверность приема сообщений. Его можно реализовать различными способами, в том числе путем преднамеренного введения избыточности в информационное сообщение.
Теория помехоустойчивого кодирования информации развивается с 1946 года, после опубликования американским ученым К.Шенноном фундаментальной теоремы теории информации, известной как основная теорема кодирования К.Шеннона. Для дискретного канала теорема формулируется следующим образом: если производительность источника сообщений Н'(A) меньше пропускной способности канала С, т.е. Н'(A)<C, то с у- ществует способ кодирования, при котором вероятность ошибочного декодирования может быть сколь угодно мала. Если же Н'(A)≥C, то таких способов не существует.
Согласно теореме Шеннона, ошибки в канале не являются препятствием для безошибочной передачи информации, поскольку ошибки могут быть обнаружены и скорректированы. Однако в доказательстве теоремы не указывается конкретный код, исправляющий все ошибки. Тем не менее, вскоре американским ученым Р. Хэммингом был разработан первый помехоустойчивый код. Но, как и все ныне существующие коды, он обеспечивал обнаружение и исправление не всех, внесенных при передачи информации ошибок, а только определенного их числа.
Наиболее простым способом реализации помехоустойчивого кодирования является метод многократной передачи либо каждого информационного символа, либо всего блока в целом
17
(кратность передачи ≥3). Решение о каждом принятом символе принимается по большинству одинаковых символов. Например:
10110 - передаваемое сообщение,
10010 - принятое сообщение при первой передаче,
10100 - принятое сообщение при повторной передаче,
00110 - принятое сообщение при третьей передаче,
10110 - восстановленное сообщение.
Этот способ обладает высокой избыточностью, что резко уменьшает скорость передачи информации по каналу связи.
Более эффективным является метод, при котором все множество возможных комбинаций, принимаемых декодером, разбивается на две части. В одну часть входят разрешенные кодовые комбинации (слова), формируемые кодером, а в другую - запрещенные кодовые комбинации, в которые могут перейти разрешенные кодовые слова под воздействием помех. Для реализации этого метода необходимо использовать избыточный код − код, в котором для кодирования используют только часть возможных кодовых комбинаций, называемых разрешенными: Мразр<Мобщ. Остальные комбинации считают запрещенными.
Простой (примитивный) код, в котором для кодирования задействованы все возможные кодовые комбинации, не может обеспечить помехоустойчивого кодирования, так как в этом слу-
чае Мраз= М общ=mn, где m-основание кода; n-число разрядов в кодовом слове. Избыточный код формируют из простого кода
путем введения определенным образом дополнительных проверочных символов в исходную информационную кодовую комбинацию.
Пример 3. Для передачи двух сообщений простым двоичным кодом достаточно использовать одноразрядный код, поскольку при этом число возможных кодовых комбинаций Мобщ=2n=21=2. Одному из исходных сообщений присваивается символ "0", а другому − символ "1". Если при передаче любого из сообщений произойдет ошибка ("1" перейдет в "0" или наоборот), то ее невозможно обнаружить, так как и "0" и " 1" являются разрешенными комбинациями. Если же ввести в кодовые слова по два дополнительных символа, код станет трехразрядным (n=3) и число возможных комбинаций увеличится до восьми
18
(Мобщ=23=8). Для передачи двух исходных сообщений выбирают из этих восьми возможных только две разрешенные комбинации, максимально отличающиеся друг от друга. Очевидно, что ими должны быть 000 и 111 или 001 и 110 и т.д. Благодаря введенной избыточности, одна и даже две ошибки, возникшие при передаче любого из двух сообщений, переводят разрешенную кодовую комбинацию в запрещенную, и будут обнаружены. Трехкратная ошибка в данном случае не обнаруживается, так как передаваемая разрешенная комбинация в результате трех ошибок переходит в другую разрешенную комбинацию.
Рассмотрим подробнее работу кодера и декодера (кодека) помехоустойчивого двоичного кода в системе передачи дискретных сообщений. Структурная схема включения помехоустойчивого кодека в тракт передачи приведена на рисунке 3 (устройству «Дискретный канал передачи» на рисунке 3 соответствует совокупность трех устройств на рисунке 1, а именно: линейного кодера, линии передачи и линейного декодера).
|
|
|
|
|
|
|
|
|
|
a ,a2 ...ak |
Помехоустой |
b ,b2 ...bk ...bn |
Дискретный |
||||||
канал |
|||||||||
Ak |
|
чивый кодер |
B |
|
|
||||
|
передачи |
||||||||
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Источники |
|
||
|
|
|
|
|
|
помех |
|
||
|
|
|
|
|
|
|
|
|
|
b* ,b*2 ...b*k ...b*n |
Помехоустой- |
a′,a2′...ak′ |
B* |
чивый |
|
декодер |
Ak′ |
|
|
|
Рисунок 3 ─ Электрическая структурная схема включения помехоустойчивого кодека в тракт передачи
На вход кодера поступает безызбыточная кодовая комбинация Аk, состоящая из k двоичных информационных сигналов а, а2…аk. При этом возможное число входных комбинаций не превышает 2k. Кодер из принятых k символов по определенному правилу формирует r дополнительных проверочных символов и выдает на выход n-разрядную разрешенную кодовую комбинацию В с символами b1b2…bk…bn, где n-общее число символов в кодовом слове (n=k+r). Поскольку n > k, то увеличивается общее число возможных комбинаций:
19
Мобщ =2n=2k+ r |
(1) |
Кодер формирует только разрешенные кодовые комбинации, причем их максимальное число Мразр равно числу входных комбинаций. Таким образом, благодаря введению дополнительных поверочных символов r, стало возможным разделение всего множества возможных комбинаций на разрешенные и запрещенные:
Мзапр= Мобщ - Мразр |
(2) |
Принятая декодером n-разрядная кодовая последовательность В*( b1*b2*...bk*...bn* ) обозначается со звездочкой, так как в резуль-
тате воздействия помех она может в любом разряде отличаться от переданной кодовой комбинации В. В декодере комбинация
B* сравнивается со всеми разрешенными для данного кода комбинациями. Если установлено, что принята разрешенная комбинация, то декодер формирует и выдает на выход k-разрядную
последовательность информационных символов Аk′(a1′a2′...ak′) ,
которая может совпадать с исходной комбинацией Аk (ошибка отсутствует) или не совпадать (под воздействием помехи разрешенная кодовая комбинация перешла в другую разрешенную). Если же принята запрещенная комбинация, то декодер обнаруживает наличие ошибки. Необходимым условием обнаружения ошибки является переход разрешенной кодовой комбинации в одну из запрещенных.
Существует два алгоритма декодирования помехоустойчивых кодов: с обнаружением ошибок и с исправлением ошибок. В
первом случае при обнаружении ошибки декодер не выдает получателю заведомо ошибочную последовательность из k символов, а по цепи обратной связи направляет в передатчик запрос на повторную передачу сообщения. Если в системе передачи не предусмотрена обратная связь, то используются другие возможности. Например, в телевидении взамен ошибочно принятого демонстрируют предыдущий кадр изображения или на экране телевизора отображается информация «Нет сигнала» и т.д.
20