Эффективное кодирование - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Эффективное кодирование. Доклад-сообщение содержит 43 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Эффективное кодирование

Слайд 2

Описание слайда:

Эффективное кодирование Эффективное кодирование решает задачу более компактной записи сообщений, вырабатываемых источником за счет их перекодировки. Применяется практически во всех архиваторах типа Rar, Zip и др. Позволяют сжать информацию в в 2-3, max в 4 раза, но при этом происходит полное восстановление сжатой информации «бит в бит»

Слайд 3

Описание слайда:

Сжатие в большее число раз Применяется, если же не требуется восстановление информации «бит в бит» Например, при передаче речи можно допускать искажения, которые получатель голосового сообщения не заметит из-за нечувствительности слухового аппарата человека к этим изменениям.

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Схема системы передачи информации ИИ – источник информации КИ – кодер источника КК –кодер канала М – модулятор ЛС –линия связи ДМ - демодулятор ДК- декодер канала ДИ – декодер источника П - приемник

Слайд 6

Описание слайда:

Сообщению X на выходе источника информации (ИИ) необходимо поставить в соответствие определенный сигнал. Сообщению X на выходе источника информации (ИИ) необходимо поставить в соответствие определенный сигнал. Дискретные сообщения складываются из букв, а непрерывные сообщения можно представить последовательностью цифр в каждый момент отсчета, то можно использовать конечное число образцовых сигналов, соответствующих отдельным буквам алфавита источника. При большом объеме алфавита прибегают к представлению букв в другом алфавите с меньшим числом букв, которые будем называть символами. Т. е. выполняется КОДИРОВАНИЕ Поскольку алфавит символов меньше алфавита букв, то каждой букве соответствует некоторая последовательность символов, называемая кодовой комбинацией. Число символов в кодовой комбинации называется ее значностью.

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

В процессе преобразования букв в символы нужно: 2. Второй целью кодирования является на основании теорем Шеннона – согласование свойств источника сообщений со свойствами канала связи. При отсутствии помех это непосредственно дает выигрыш во времени передачи или в объеме запоминающего устройства. Такое кодирование получило название эффективное кодирование.

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Выбор кодирующих и декодирующих устройств зависит от статистических свойств источника, а так же уровня и характера помех в канале связи Если избыточность источника сообщений (ИС) и помехи в канале связи практически отсутствуют, то введение как КИ, так и КК нецелесообразно. Если избыточность ИС высока, а помехи малы, целесообразно введение только КИ. Когда избыточность источника мала, а помехи велики, целесообразно введение КК. При большой избыточности и высоком уровне помех целесообразно введение обоих дополнительных кодирующих и декодирующих устройств.

Слайд 12

Описание слайда:

После кодера канала КК кодированный сигнал поступает в устройство кодирования символов сигналами – модулятор М. Получаемый на выходе модулятора сигнал Y подготовлен к передаче по конкретной линии связи ЛС. В устройство декодирования сигналов в символы (демодулятор ДМ) из линии связи приходит сигнал, искаженный шумом, который обозначен на схеме – Z.

Слайд 13

Описание слайда:

Устройства декодирования Устройство декодирования помехоустойчивого кода декодер канала ДК и устройство декодирования сообщений (декодер источника ДИ) выдают декодированное сообщение W получателю П (человеку или машине).

Слайд 14

Описание слайда:

Итак При кодировании каждая буква исходного алфавита представляется различными последовательностями, состоящими из кодовых букв (цифр). Если исходный алфавит содержит m букв, то для построения равномерного кода с использованием k кодовых букв необходимо удовлетворить соотношение m ≤ kq , где q - количество элементов в кодовой последовательности.

Слайд 15

Описание слайда:

Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их коды как q - разрядные числа в k-ичной системе счисления Например, при двоичном кодировании 32 букв русского алфавита используется q = log232 = 5 разрядов, на чем и основывается телетайпный код.

Слайд 16

Описание слайда:

Кроме двоичных кодов, наибольшее распространение получили восьмеричные коды. Например, необходимо закодировать алфавит, состоящий из 64 букв. Для этого потребуется q = log264 = 6 двоичных разрядов или q = log864 = 2 восьмеричных разрядов. При этом буква с номером 13 при двоичном кодировании получает код 001101, а при восьмеричном кодировании 15.

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

теорема Шеннона В этом случае среднее количество информации, переносимое одним символом, можно считать: J(Z; Y) = Hапр(Z) – Hапост(Z) = Hапр(Y), так как H(Y) = H(Z) и H(Y/Z) = 0, а max{J(Z; Y)} = Hmax(Y) – max энтропия источника сигнала, получающаяся при равномерном распределении вероятностей символов алфавита Y. p( y1) = p( y2) = ... = p( ym) = 1/My, т.е. Hmax(Y) = logaMy

Слайд 19

Описание слайда:

Теорема Шеннона следовательно, пропускная способность дискретного канала без помех в единицах информации за единицу времени равна: Cy = Vy · max{J(Z; Y)} = Vy · Hmax(Y) = Vy · logaMy или Ck = Vk · logaMy, Vk – скорость передачи определяется частотными переключательными способностями канала:

Слайд 20

Описание слайда:

Теорема Шеннона Если источник информации создает поток информации , Такой что, производительность источника информации равна пропускной способности канала , т.е. равна энтропии источника, приходящаяся на единицу времени(бит,сек=бод) а канал связи обладает пропускной способностью С ед. информации в единицу времени, то при H(x) ≤ C : Сообщения, вырабатываемые источником, всегда можно закодировать так, чтобы скорость их передачи была сколь угодно близкой к Не существует способа кодирования, позволяющего сделать эту скорость большей, чем Vx max.

Слайд 21

Описание слайда:

Теорема Шеннона Согласно сформулированной теореме существует метод кодирования, позволяющий при: H(x) ≤ C – передавать всю информацию, вырабатываемую источником при ограниченном объеме буфера; H(x) > C – такого метода кодирования не существует, так как требуется буфер, объем которого определяется превышением производительности источника над пропускной способностью канала, умноженной на время передачи.

Слайд 22

Описание слайда:

Следствия из теоремы Шеннона если источник информации имеет энтропию H(X), то сообщения можно закодировать так, чтобы средняя длина кода lср (количество символов сигнала на одну букву сообщения) была сколь угодно близкой к величине:

Слайд 23

Описание слайда:

Следствия из теоремы Шеннона то есть при а = 2 (бит) и My = 2 {0; 1} имеем: где pi – вероятность встречи данного элемента алфавита; li – количество символов в i-ой кодовой комбинации; ε – бесконечно малая величина ≥ 0, т.е. lim lср = H(x).

Слайд 24

Описание слайда:

Это следует из равенства: . Таким образом, lср выступает критерием эффективности кодирования. Чем ближе lср к H(x), тем лучше мы закодировали. В инженерной практике это различие можно считать допустимым 3÷5% (до 10%).

Слайд 25

Описание слайда:

Следствия из теоремы Шеннона Это следует из равенства: (Производительность ист.=попускн.сп .к=макс.ск. Канала без помех=произ макс. скорости передачи сообщения на ср длину) Таким образом, lср выступает критерием эффективности кодирования. Чем ближе lср к H(x), тем лучше мы закодировали. В инженерной практике это различие можно считать допустимым 3÷5% (до 10%).

Слайд 26

Описание слайда:

Следствия из теоремы Шеннона Из этого же критерия следует, что если буквы имеют равномерное распределение вероятностей их употребления, то H(x) = log2 M, а lср = log2 M. Пределы эффективного кодирования: H(x) ≤ lср ≤ log2 M.

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

Методика Шеннона-Фэно Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.

Слайд 30

Описание слайда:

Методика Шеннона-Фэно Символы первичного алфавита m1 выписывают по убыванию вероятностей. Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1». Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

Методика Шеннона-Фэно Пример:

Слайд 33

Описание слайда:

Методика Шеннона-Фэно В равномерном коде длина сообщения n=3 22

Слайд 34

Описание слайда:

Методика Шеннона-Фэно Условие эффективного кодирования: max H(Z): log2 m ≥ lср ≥ H(Z) + ε, но H(Z)

Слайд 35

Описание слайда:

Методика Шеннона-Фэно кодирование блоками Рассмотрим сообщения, образованные с помощью алфавита, состоящего из 2-х букв Z1 и Z2 с вероятностями появления P(Z1) = 0.7 и P(Z2) = 0.3. Поскольку P(Z1) не равно P(Z2), то последовательность из таких букв будет обладать избыточностью. Однако при буквенном кодировании мы никакого эффекта не получим. Действительно, на передачу каждой буквы требуется либо 1, либо 0, то есть lср = 1 · 0.9 + 1 · 0.1 = 1, в то время как H(Z) = –0.7log2 0.7 – 0.3log2 0.3 = 0.88бит. Избыточность составляет R(A)=0,12 бит/символ.

Слайд 36

Описание слайда:

Методика Шеннона-Фэно кодирование блоками В этом случае средняя длина кодового слова составляет: с =1,81 бит. На один символ алфавита источника приходится в среднем 1,81/2=0,905 бит/символ. Избыточность составляет R(A)=0,905 – 0,88=0,025 бит/символ.

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

Методика Хаффмена Алгоритм: Расположить символы исходного алфавита А в порядке убывания вероятности. Два наименее вероятных символа алфавита А будем считать одним символом нового сжатого алфавита А1. Располагаем символы алфавита А1 в порядке убывания вероятности. И снова подвергаем его сжатию. Повторяем процедуру, пока не придем к алфавиту, содержащему всего два символа.

Слайд 39

Описание слайда:

Методика Хаффмена Припишем символам последнего алфавита кодовые обозначения 0 (например - верхнему) и 1 (в нашем примере – нижнему). Это старшие символы будущих кодовых слов. В предпоследнем алфавите кодовые обозначения получаются следующим образом: • Символ, который сохранился в последнем алфавите, имеет то же кодовое обозначение. • Символам, которые слились в последнем алфавите, приписывают справа 0 (в нашем примере – верхнему символу) и 1 (нижнему символу). Повторяем процедуру, последовательно возвращаясь к исходному алфавиту.

Слайд 40

Описание слайда:

Методика Хаффмена пример 1

Слайд 41

Описание слайда:

Методика Хаффмена пример2

Слайд 42

Описание слайда:

Методика Хаффмена пример 2

Слайд 43

Описание слайда:

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

Теги Эффективное кодирование

Похожие презентации