24445

Технология сжатия информационных данных (Алгоритмы Шеннона-Фано, Хаффмана)

Контрольная

Информатика, кибернетика и программирование

Выполнив выше сказанное для всех символов получим: C = 00 2 бита A = 0100 4 бита D = 0101 4 бита F = 011 3 бита B = 10 2 бита E = 11 2 бита Каждый символ изначально представлялся 8ю битами один байт и так как мы уменьшили число битов необходимых для представления каждого символа мы следовательно уменьшили размер выходного файла. Из этих комбинаций лишь 2 по длиннее равны 8 битам. Поэтому для дискретного управления в реальном масштабе времени наличие в системе команд операций...

Русский

2013-08-09

182 KB

4 чел.

1. Технология сжатия информационных данных (Алгоритмы Шеннона-Фано, Хаффмана).

Теорема Шеннона

Если поток информации, вырабатываемый источником, достаточно близок к пропускной способности канала, т.е. справедливо равенство

I(x)=C-б (1.13)

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

I(z,y)=c

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

I(x)>c

Таким образом, Т Шеннона утверждает, что при выполнении условия (1,13) скорость передачи информации может быть сколь угодно приближена к пропускной способности канала. Это может быть обеспечено соответственным методом кодирования.

Однако Т не отвечает на вопрос, каким образом нужно осуществить кодирование.

Хаффман.

  Сжимая файл по алгоритму Хаффмана первое что мы должны сделать - это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.

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

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее:

       |-----------------|-----|-----|-----|-----|-----|-----|

       |     cимвол      |  A  |  B  |  C  |  D  |  E  |  F  |

       |-----------------|-----|-----|-----|-----|-----|-----|

       | число вхождений |  10 |  20 |  30 |  5  |  25 |  10 |

       |-----------------|-----|-----|-----|-----|-----|-----|

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

       |-----------------|-----|-----|-----|-----|-----|-----|

       |     cимвол      |  C  |  E  |  B  |  F  |  A  |  D  |

       |-----------------|-----|-----|-----|-----|-----|-----|

       | число вхождений |  30 |  25 |  20 |  10 |  10 |  5  |

       |-----------------|-----|-----|-----|-----|-----|-----|

Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A.

Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A:

  Частота         30    10     5     10     20     25

  Символа          C     A     D      F      B      E

                         |     |

                         |--|--|

                           ||-|

                           |15|  = 5 + 10

                           |--|

Номер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния узлов:

  Частота         30    10     5     10     20     25

  Символа          C     A     D      F      B      E

                         |     |      |

                         |     |      |

                         | |--||      |

                         |-|15||      |

                           ||-|       |

                            |         |

                            |    |--| |

                            |----|25|-| = 10 + 15

                                 |--|


Рассматриваем таблицу снова для следующих двух символов (B и E ). Мы продолжаем в этот режим пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу.

  Частота         30    10     5     10     20     25

  Символа          C     A     D      F      B      E

                   |     |     |      |      |      |

                   |     | |--||      |      |      |

                   |     |-|15||      |      |      |

                   |       ||-|       |      |      |

                   |        |    |--| |      | |--| |

                   |        |----|25|-|      |-|45|-|

                   |             ||-|          ||-|

                   |    |--|      |             |

                   |----|55|------|             |

                        |-||                    |

                          |   |------------|    |

                          |---| Root (100) |----|

                              |------------|

Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всегда начинать из корня ( Root ). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 (и запомним 0), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C - 00. Для следующего символа ( А ) у нас получается - лево, право, лево, лево, что выливается в последовательность 0100. Выполнив выше сказанное, для всех символов получим:

  C = 00   ( 2 бита )     A = 0100 ( 4 бита )    D = 0101 ( 4 бита )    F = 011  ( 3 бита )

  B = 10   ( 2 бита )     E = 11   ( 2 бита )

Каждый символ изначально представлялся 8-ю битами (один байт), и так как мы уменьшили число битов необходимых для представления каждого символа, мы следовательно уменьшили размер выходного файла. Сжатие складывается следующим образом:

      |----------|----------------|-------------------|--------------|

      | Частота  |  первоначально |  уплотненные биты | уменьшено на |

      |----------|----------------|-------------------|--------------|

      |  C 30    |  30 x 8 = 240  |    30 x 2 = 60    |      180     |

      |  A 10    |  10 x 8 =  80  |    10 x 3 = 30    |       50     |

      |  D 5     |   5 x 8 =  40  |     5 x 4 = 20    |       20     |

      |  F 10    |  10 x 8 =  80  |    10 x 4 = 40    |       40     |

      |  B 20    |  20 x 8 = 160  |    20 x 2 = 40    |      120     |

      |  E 25    |  25 x 8 = 200  |    25 x 2 = 50    |      150     |

      |----------|----------------|-------------------|--------------|

    Первоначальный размер файла : 100 байт - 800 бит;

           Размер сжатого файла :  30 байт - 240 бит;

      240 - 30% из 800 , так что мы сжали этот файл на 70%.

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

В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной.

Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся наши символы ) , всего 11. 4 байта 11 раз - 44. Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику - наша таблица будет приблизительно 50 байтов длинны.

Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт. Учитывая , что первоначальная длинна файла в рассматриваемом примере была 100 байт - мы получили 20% сжатие информации.

Не плохо. То что мы действительно выполнили - трансляция символьного ASCII набора в наш новый набор требующий меньшее количество знаков по сравнению с стандартным.

Что мы можем получить на этом пути ?

Рассмотрим максимум, который мы можем получить для различных разрядных комбинаций в оптимальном дереве, которое является несимметричным.

   Мы получим что можно иметь только :

                4 - 2 разрядных кода;

                8 - 3 разрядных кодов;

               16 - 4 разрядных кодов;

               32 - 5 разрядных кодов;

               64 - 6 разрядных кодов;

              128 - 7 разрядных кодов;

    Необходимо еще два 8 разрядных кода.

                4 - 2 разрядных кода;

                8 - 3 разрядных кодов;

               16 - 4 разрядных кодов;

               32 - 5 разрядных кодов;

               64 - 6 разрядных кодов;

              128 - 7 разрядных кодов;

            --------

         итого:     254

Итак, мы имеем итог из 256 различных комбинаций которыми можно кодировать байт. Из этих комбинаций лишь 2 по длиннее равны 8 битам. Если мы сложим число битов которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%, таким образом максимально идеализированный Huffman может достигать сжатия в 33% когда используется на уровне байта.

Все эти подсчеты производились для не префиксных кодов Хаффмана т.е. кодов, которые нельзя идентифицировать однозначно. Например, код A - 01011 и код B - 0101. Если мы будем получать эти коды побитно то, получив биты 0101, мы не сможем сказать какой код мы получили A или B , так как следующий бит может быть как началом следующего кода, так и продолжением предыдущего.

Необходимо добавить, что ключом к построению префиксных кодов служит обычное бинарное дерево и если внимательно рассмотреть предыдущий пример с построением дерева, можно убедится, что все получаемые коды там префиксные.

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


2. Битовый процессор.
Арифметические операции двойной точности

Пригодность архитектуры каждого компьютера для конкретного класса задач определяется тем, насколько его система команд соответствует задачам, которые должны быть выполнены. Поэтому для дискретного управления в реальном масштабе времени наличие в системе команд операций непосредственно над битами приводит к созданию более производительных систем и программ обработки входной и выходной двоичной информации. С этой целью в ОМЭВМ семейства MCS-51 введены специальные средства, называемые битовым процессором, которые поддерживают прямые логические операции с отдельными битами и операции их тестирования и позволяют использовать однобитовые переменные в логических операциях. Цель данной главы - показать и объяснить применение битового процессора ОМЭВМ семейства MCS-51.

Общие седения

В систему команд ОМЭВМ семейства MCS-51 введены специальные команды для выполнения операций с битовыми переменными. Имеется 17 таких команд, которые перечислены в табл. 26. Эти команды в зависимости от выполняемой функции могут быть одно-, двух- или трехбайтовые. Те из них, которые оперируют с флагом переноса, имеют однобайтный код или код, за которым следует байт смещения, использующийся для вычисления адреса условного перехода (рис. 41, а). В более обобщенных командах битовых операций после кода добавляется байт адреса прямоадресуемого бита, образуя двух- или трехбайтовые команды (рис. 40, б). На рис. 41 для справки приведены коды этих команд.

С помощью указанных команд можно обращаться непосредственно к 128 битам внутреннего ОЗУ и к 83 битам 11-ти 8-разрядных регистров ОМЭВМ.

Таблица 26

Команды для

выполнения операций с битовыми переменными

Мнемоническое обозначение

Описание команды

Число байтов

Число циклов

SETB  С

Установка флага переноса

1

1

SETB  bit

Установка бита

2

1

CLR    С

Сброс флага переноса

1

1

CLR   bit

Сброс бита

2

1

CPL    С

Инверсия флага переноса

1

1

CPL    bit

Инверсия бита

2

1

MOV  С, bit

Пересылка бита во флаг переноса

2

1

MOV  bit, С

Пересылка флага переноса в бит

2

2

ANL   С, bit

«ЛОГИЧЕСКОЕ И» бита и флага переноса

2

2

ANL   С, /bit

«ЛОГИЧЕСКОЕ И» инверсии бита и флага переноса

2

2

ORL   C, bit

«ЛОГИЧЕСКОЕ ИЛИ» бита и флага переноса

2

2

ORL   C, /bit

«ЛОГИЧЕСКОЕ ИЛИ» инверсии бита и флага переноса

2

2

JC      rel8

Переход, если флаг переноса установлен

2

2

JNC    rel8

Переход, если флаг переноса сброшен

2

2

JB      bit, rel8

Переход, если бит установлен

3

2

JNB    bit, rel8

Переход, если бит сброшен

3

2

JBC    bit, rel8

Переход, если бит установлен, и сброс этого бита

3

2

Примечание. В таблице использованы следующие обозначения: С - флаг переноса; bit — 128 программно-доступных битов, любой I/O вывод, бит управления или состояния; /bit - 128 программно-доступных битов, любой I/O вывод, бит управления или состояния, взятые с инверсией; геl8 - байт относительного смещения (условный переход осуществляется в диапазоне от -128 до +127 байт относительно адреса первого байта следующей команды).

Арифметические операции двойной точности

Команды ADDC и SUBB учитывают предыдущее состояние флажка переноса (заема), что позволяет производить вычисления с двойной точностью путем повторения операции над последующими старшими байтами операнда. Если входными данными для операции является строка целых чисел без знака, то флажок переноса установится после завершения операции при переполнении (для ADDC) или при исчезновении значащих разрядов (для SUBB). Для отрицательных данных, представленных дополнительным кодом, старший разряд старшего байта исходных данных содержит знак строки, поэтому флажок переполнения (OV) будет указывать на переполнение или исчезновение значащих разрядов.

;SUBSTR Вычитает строку, указанную регистром R1, из строки,

;указанной регистром R0, с точностью, указанной регистром R2.

;После выполнения операции проверяется переполнение результата.

SUBSTR:  CLR     С       ;3аем=0

BEGIN:   MOV     A,@R0   ;Загрузка байта уменьшаемого

        SUBB    A,@R1   ;Вычитание байта

        MOV     @R0,A   ;Запоминание байта разности

        INC     R0      ;Установка указателей на следующее

        INC     R1      ;поле

        DJNZ    R2,BEGIN;Выполнение цикла до завершения ;операции

                         ;После завершения цикла проверяется ситуация пере-

                         ;        полнения в последней итерации.

        JNB     OV,OK

;         ..............

;Программа восстановления старших

;разрядов

OK:      RET


 

А также другие работы, которые могут Вас заинтересовать

52115. Акваріум 1.51 MB
  Мета: освітня: закріпити знання студентів про влаштування акваріуму в ДНЗ підбір рибок та правила догляду за ними.html на цій сторінці розміщені поради щодо влаштування акваріуму догляду за ним підбору риб та ін. Саме з посмішкою ви повинні заходити до малят у дитячий садок і нести їм лише позитивні емоції не забувати частіше посміхатись адже посмішка – це ключик який відкриває найпотаємніше в дитячих душах Оголошення теми і мети заняття: Сьогодні ми поговоримо про влаштування акваріуму та його мешканців. – Чи бачили ви проходячи...
52117. Лицеисты за здоровое будущее 59 KB
  Ведущий 1: Здравствуйте Люди часто говорят друг другу при встрече это хорошее доброе слово Ведущий 2: Они желают друг другу здоровья. Вот и мы обращаемся к Вам – здравствуйте дорогие друзья и учителя Гости Ведущий 1: А вы знаете что дороже всего на свете Конечно это жизнь это здоровье. Ведущий 2: Ещё в Древней Руси говорили: Здоровье дороже богатства. Ведущий 1: Здоровье не купишь.
52119. Розвязування раціональних рівнянь 107.5 KB
  Мета: удосконалити вміння розвязувати раціональні рівняння; розвиток уваги і вміння чітко та математично грамотно висловлювати власну думку. Тип уроку: удосконалення знань і вмінь
52120. Означення квадратного рівняння. Неповні квадратні рівняння, їх розвязування 43.5 KB
  Неповні квадратні рівняння їх розв’язування Мета: удосконалити знання учнів про означення квадратного рівняння; удосконалити вміння розв’язувати неповні квадратні рівняння; розвиток концентрації уваги Тип уроку: удосконалення знань і вмінь Обладнання та наочність: картки для усного рахунку опорна схема правила проведення інтерактивної технології “Робота в парахâ€ Хід уроку І. Актуалізація опорних знань Запитання для фронтального опитування: означення квадратного рівняння; коефіцієнти квадратного рівняння; Опорна схема неповні...
52121. Розвязування тригонометричних рівнянь зведенням до однієї тригонометричної функції 7.06 MB
  Розв’язування тригонометричних рівнянь зведенням до однієї тригонометричної функції. Формування в учнів умінь розв’язувати тригонометричні рівняння способом зведення до однієї тригонометричної функції алгебраїчний спосіб розвивати логічне мислення уяву пам'ять виховувати інтерес до математики уважність відповідальність культуру математичних записів. Ми ніколи не станемо математиками...
52122. Розкладання многочленів на множники способом винесення спільного множника за дужки та способом групування 60 KB
  Тема: Розкладання многочленів на множники способом винесення спільного множника за дужки та способом групування. Які вирази називаються многочленами Що означає розкласти многочлен на множники Способи розкладання многочлена на множники Як розкласти многочлен на множники способом групування III.
52123. Решение задач с помощью производной 63 KB
  Активизировать познавательную деятельность учащихся путем решения задач с практическим содержанием. Оборудование: Портреты ученых Карточки с заданиями для устных упражнений Таблица Чертежи к задачам математические модели Минизадачники Ход урока В мире не происходит ничего в чем бы ни был виден смысл какогонибудь максимума или минимума Леонард Эйлер I. Выдающиеся ученые: француз Пьер Ферма 16011665 англичанин Исаак Ньютон 16431727 немец Готфрид Лейбниц16461716 француз Жозеф Лагранж 17361813...