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


 

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

42773. Социальная реабилитация инвалидов и методика её осуществления 441.99 KB
  Сущность и содержание социальной реабилитации Основные цели и задачи социальной реабилитации Принципы социальной реабилитации Инвалиды составляют особую категорию населения, численность которой постоянно увеличивается. Мировым сообществом социальная защита инвалидов рассматривается как проблема первостепенной важности.
42774. Проектирование системы теплоснабжения промышленного предприятия 219.1 KB
  Определение количества теплоты на подогрев воды для горячего водоснабжения Выбор основного и вспомогательного оборудования системы транспорта теплоты Выбор основного и вспомогательного оборудования источника теплоты.Определение потребности в топливе для производства теплоты.
42775. Организация работы коктейль-бара «Малибу» 804 KB
  Целью работы является рассмотрение вновь созданного коктейль - бара на 50 посадочных мест. Моему коктейль-бару я решил дать название «Малибу», так как моим основным спонсором является «Allied Distillers Limited»
42776. Компьютерная реализация решения инженерной задачи по решению дифференциальных уравнений в частных производных 1.38 MB
  Микроэлектроника является одной из наиболее динамично развивающихся и востребованных отраслей науки и техники. Элементы современных СБИС и микрооптикоэлектромеханических систем (МОЭМС) представляют собой сложные структуры, в основу функционирования которых положены разнообразные физические эффекты. Разработка подобных элементов практически невозможна без решения уравнений математической физики, представляющих
42777. Разработка технологического процесса механической обработки шкива в условиях ЗАО «МРК» 190.3 KB
  Технический прогресс в машиностроении характеризуется как улучшением конструкций машин, так и непрерывным технологии их производства. Развитие новых прогрессивных технологических процессов обработки способствует конструированию современных машин и снижению их себестоимости. Актуальной является задача повышения качества выпускаемых машин и, в первую очередь, их точности
42778. Особенности развития силовых способностей у школьников старшей возрастной группы 351.46 KB
  Динамика силовых качеств детей старшего школьного возраста под воздействием занятий физическими упражнениями. Данный режим работы мышц имеет место в силовых упражнениях с преодолением внешнего отягощения штанги гирь гантелей отягощений на блочном устройстве. Величина прикладываемой к снаряду силы при выполнении упражнения в изотоническом режиме изменяется по ходу траектории движения так как изменяются рычаги приложения силы в различных фазах движений. Упражнения со штангой или другим аналогичным снарядом с высокой скоростью...
42779. ТЕХНОЛОГИЧЕСКИЙ ПРОЦЕСС РАБОТЫ УЧАСТКОВОЙ СТАНЦИИ 364.29 KB
  Определение среднего времени нахождения на станции транзитных вагонов без переработки Среднее время нахождения на станции транзитных вагонов с переработкой Общий простой вагонов на станции Рабочий парк вагонов
42780. Организация и планирование предприятий 198.55 KB
  Обоснование выбора варианта технологического процесса Годовые фонды времени в данной работе принимаются следующие: фонд времени оборудования Фдо = 3530 ч 2 смены фонд времени производственных рабочих Фдр = 1590 ч 1 смена фонд времени вспомогательных рабочих Фдв = 1860 ч 1 смена Таблица 1 Необходимые данные для выполнения задания № п п Наименование расчётных показателей Обозначение Значение показателя 1 Норма затрат на содержание оборудования руб. Нз 640000 2 Коэффициент обслуживания рабочих мест Кобс 10 3 Средние капитальные...
42781. Розрахунок електричних навантажень силової мережі 4.67 MB
  Електроенергетичній галузі притаманні специфічні особливості, зумовлені одноманітністю вироблення і споживання енергії, надзвичайно складним технологічним циклом її одержання, необхідністю централізованого диспетчерського оперативно-технологічного керування всім комплексом у цілому, забезпечення надійності і безпеки функціонування обладнання. Все це робить енергетику надзвичайно матеріалоємною, енергоємною галуззю, з великим інвестиційним циклом і, що дуже важливо, — інтелектуально і наукоємною.