2 Проектная часть
1. Разработать систему для сжатия информации, применяя любой алгоритм сжатия без потерь.
2. Объём памяти данных не должен превышать 64 килобайт).
3. Алгоритм не должен требовать сложных арифметических вычислений.
4. Обеспечить максимально возможное быстродействие.
2.2 Выбор метода кодирования.
При разработке алгоритма эффективного кодирования неудовлетворение вышеприведённым требованиям технического задания приведёт к тому, устройство, реализованное на его основе, будет иметь высокую стоимость, а также может иметь низкое быстродействие.
Аппаратная реализация кодирующего алгоритма может быть реализована как с использованием микропроцессорных устройств, а также без них.
В первом случае можно использовать существенно более сложный алгоритм, а значит, добиться большей степени сжатия. Разработка устройства будет существенно проще, а стоимость может быть ниже. Данный вариант является более предпочтительным, вследствие того, что устройство должно обрабатывать данные произвольного типа и иметь высокую степень сжатия.
Во втором случае разработка такого устройства будет существенно сложнее, и реально может быть осуществлено лишь с очень простыми алгоритмами, например с алгоритмом кодирования серий (RLE). К тому же стоимость подобных устройств может быть выше вследствие большей элементной базы. Поэтому такие устройства могут использоваться в том случае, если требуется сверхвысокое быстродействие и приемлема низкая степень сжатия, кроме того, эффективная работа может быть осуществлена только с данными определенного типа.
Алгоритм кодирования должен быть адаптивного типа, это позволит не анализировать пакеты большого объема перед осуществлением кодирования, что сокращает объем памяти кодера. Степень сжатия при этом, в случае обработки пакетов данных большого объема, как правило, не уменьшается, а в некоторых случаях может быть выше.
Для аппаратной реализации не подходят алгоритмы, требующие большого объема вычислений (например, арифметические алгоритмы). Алгоритмы кодирования серий так же не приемлемы вследствие низкой степени сжатия.
За базовый для данной аппаратной реализации выберем словарный метод кодирования Лемпела-Зива, модифицированный Велчем (LZW). Этот метод обладает сравнительно высоким быстродействием при хорошей степени сжатия и невысокой сложности алгоритма. Кроме того, он требует небольшого объема памяти. В качестве преимущества над другими алгоритмами семейства следует отметить и переменную величину скользящего окна, что является гибким инструментом для увеличения вероятности нахождения кодируемой последовательности в словаре.
Для некоторой увеличения степени сжатия можно применить адаптирующийся кодирующий фильтр Хаффмана, однако стоимость такой работы существенно повышается, также как и время обработки данных.
В ходе данного дипломного проекта, базовый вариант алгоритма Лемпеля-Зива-Велча (LZW) был несколько модифицирован, что позволило уменьшить накладные расходы по памяти и при этом существенно увеличить быстродействие. Как было указано выше, алгоритм LZW является малотребовательным к памяти, что позволяет эффективно реализовать данный алгоритм на микроконтроллере, объём адресуемой памяти которого как правило не превышает 64 килобайтов. Устройство полностью берёт на себя работу по LZW-сжатию даннных. Сжатие производится блоками длиной до 16 килобайт.
Для любого алгоритма сжатия можно подобрать такие данные, для которых сжатие не уменьшит, а увеличит объём информации. Данные могут быть уже сжаты, или просто иметь малую избыточность, тогда кодирование информации только увеличит объём. Поэтому необходимо предусмотреть способ сообщить программе-клиенту, что попытка сжать данные не удалась. Так как программное обеспечение всё равно будет читать буфер данных, чтобы узнать о длине передаваемого пакета, можно вывести в поле длины величину 0, которая означает, что производить дальнейшее чтение данных из устройства нет смысла, ввиду несжимаемости данных.
2.3 Описание базового алгоритма.
2.3.1 Краткое описание базового алгоритма кодирования.
Алгоритм LZW-сжатия в простейшей форме приведён ниже:
Процедура LZW-сжатия: СТРОКА = очередной символ из входного потока WHILE входной поток не пуст DO СИМВОЛ = очередной символ из входного потока IF СТРОКА+СИМВОЛ в таблице строк THEN СТРОКА = СТРОКА+СИМВОЛ ELSE вывести в выходной поток код для СТРОКА добавить в таблицу строк СТРОКА+СИМВОЛ СТРОКА = СИМВОЛ END of IF END of WHILE вывести в выходной поток код для СТРОКА
Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
