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

5 чел.

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


 

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

16649. Дело о послесрочном индоссаменте 89 KB
  Дело о послесрочном индоссаменте Юристы профессионально занимающиеся вексельным правом в свое время наверняка обратили внимание на постановление Президиума ВАС РФ от 5 декабря 2000 г. N 8610/99 так как вопрос разрешенный в нем является едва ли не самым экзотическим о толк...
16650. ДОГОВОР ПЕРЕВОДА ДОЛГА ПО РОССИЙСКОМУ ГРАЖДАНСКОМУ ПРАВУ 301.33 KB
  ДОГОВОР ПЕРЕВОДА ДОЛГА ПО РОССИЙСКОМУ ГРАЖДАНСКОМУ ПРАВУ Материал подготовлен с использованием правовых актов по состоянию на 7 декабря 2000 года В.А. БЕЛОВ Белов Вадим Анатольевич доцент кафедры гражданского права юридического факультета МГУ им. М.В. Ло...
16651. ЮРИДИЧЕСКАЯ ПРИРОДА СДЕЛОК С АКЦИЯМИ, ВЫПУСК КОТОРЫХ НЕ ПРОШЕЛ ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ 82.37 KB
  ЮРИДИЧЕСКАЯ ПРИРОДА СДЕЛОК С АКЦИЯМИ ВЫПУСК КОТОРЫХ НЕ ПРОШЕЛ ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ Материал подготовлен с использованием правовых актов по состоянию на 9 февраля 1999 года В.А. БЕЛОВ Белов Вадим Анатольевич доцент кафедры гражданского права юридиче...
16652. ПРЕДМЕТ ДОГОВОРА СИНГУЛЯРНОЙ СУКЦЕССИИ (УСТУПКИ ТРЕБОВАНИЯ) 77.61 KB
  ПРЕДМЕТ ДОГОВОРА СИНГУЛЯРНОЙ СУКЦЕССИИ УСТУПКИ ТРЕБОВАНИЯ Материал подготовлен с использованием правовых актов по состоянию на 7 декабря 2000 года В.А. БЕЛОВ В.А. Белов доцент кафедры гражданского права юридического факультета МГУ им. М.В. Ломоносова кандид...
16653. ПЕРВЫЕ ШАГИ ЗАКОНА ОБ АО 33.11 KB
  ПЕРВЫЕ ШАГИ ЗАКОНА ОБ АО Материал подготовлен с использованием правовых актов по состоянию на 17 января 2002 года В.А. БЕЛОВ Белов Вадим Анатольевич кандидат юридических наук доцент кафедры гражданского права юридического факультета МГУ. Большинство измен...
16654. РОССИЙСКИЙ АКЦИОНЕРНЫЙ ЗАКОН 22.83 KB
  РОССИЙСКИЙ АКЦИОНЕРНЫЙ ЗАКОН Материал подготовлен с использованием правовых актов по состоянию на 20 декабря 2001 года В.А. БЕЛОВ Белов Вадим Анатольевич доцент кафедры гражданского права юридического факультета МГУ им. М.В. Ломоносова кандидат юридических на...
16655. ФОРМА ДОГОВОРА УСТУПКИ ТРЕБОВАНИЯ И ПОСЛЕДСТВИЯ ЕЕ НЕСОБЛЮДЕНИЯ 34.71 KB
  ФОРМА ДОГОВОРА УСТУПКИ ТРЕБОВАНИЯ И ПОСЛЕДСТВИЯ ЕЕ НЕСОБЛЮДЕНИЯ Материал подготовлен с использованием правовых актов по состоянию на 29 ноября 2000 года В.А. БЕЛОВ Белов Вадим Анатольевич доцент кафедры гражданского права юридического факультета МГУ им. М.В....
16656. УВЕДОМЛЕНИЕ ДОЛЖНИКА ОБ УСТУПКЕ ТРЕБОВАНИЯ И ЕГО ЮРИДИЧЕСКОЕ ЗНАЧЕНИЕ 38.53 KB
  УВЕДОМЛЕНИЕ ДОЛЖНИКА ОБ УСТУПКЕ ТРЕБОВАНИЯ И ЕГО ЮРИДИЧЕСКОЕ ЗНАЧЕНИЕ Материал подготовлен с использованием правовых актов по состоянию на 29 ноября 2000 года В.А. БЕЛОВ Белов Вадим Анатольевич доцент кафедры гражданского права юридического факультета МГУ
16657. ЮРИДИЧЕСКАЯ ПРИРОДА ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРАВ НА НЕДВИЖИМОСТЬ И СДЕЛОК С НЕДВИЖИМОСТЬЮ 58.9 KB
  ЮРИДИЧЕСКАЯ ПРИРОДА ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРАВ НА НЕДВИЖИМОСТЬ И СДЕЛОК С НЕДВИЖИМОСТЬЮ Материал подготовлен с использованием правовых актов по состоянию на 13 сентября 2002 года В.А. БЕЛОВ Белов Вадим Анатольевич доцент кафедры гражданского права юр...