Новости
09.05.2023
с Днём Победы!
07.03.2023
Поздравляем с Международным женским днем!
23.02.2023
Поздравляем с Днем защитника Отечества!
Оплата онлайн
При оплате онлайн будет
удержана комиссия 3,5-5,5%








Способ оплаты:

С банковской карты (3,5%)
Сбербанк онлайн (3,5%)
Со счета в Яндекс.Деньгах (5,5%)
Наличными через терминал (3,5%)

ОЦЕНКА КОЭФФИЦИЕНТА СЖАТИЯ КОДЕРА ХАФФМАНА В ВИРТУАЛЬНОМ ЛАБОРАТОРНОМ ЭКСПЕРИМЕНТЕ LABVIEW

Авторы:
Город:
Таганрог
ВУЗ:
Дата:
22 февраля 2016г.

Алгоритм кодирования Хаффмана используется в протоколах сжатия данных MNP большинства модемов. Согласно данному протоколу размер передаваемого блока можно изменять от 64 до 256 байт с шагом в 64 байта, что зависит от качества канала связи и требуемой скорости передачи. Так, например, протокол MNP5 реализует комбинацию адаптивного кодирования с применением кода Хаффмана и группового кодирования. Протокол MNP7 использует более эффективный (по сравнению с MNP5) алгоритм сжатия данных и позволяет достичь коэффициента сжатия порядка 3:1. MNP7 использует улучшенную форму кодирования методом Хаффмана в сочетании с марковским алгоритмом прогнозирования для создания кодовых последовательностей минимально возможной длины.

При изучении разделов дисциплин «Основы кодирования и шифрования информации», «Основы теории связи» и др. на кафедре РТС ЮФУ сопровождается прививанием студентам практических навыков в построении технических средств, обеспечивающих кодирование передаваемой информации в системах радиосвязи. Эта задача решается с использованием технологии создания виртуальных приборов в среде LabVIEW [1].

Целью работы является оценка коэффициента сжатия алгоритма Хаффмана основе технологии виртуальных приборов LabVIEW для выполнения кодирования различных видов сообщений в канале без помех с использованием вероятностного метода сжатия.

Используя среду LabVIEW [1], создан виртуальный прибор для реализации алгоритма кодирования Хаффмана с целью исследования степени сжатия различных типов сообщений. В качестве эксперимента взяты текстовые сообщения различной длины и оценена степень сжатия по алгоритму Хаффмана. Аналогичные измерения можно провести  и для других сообщений – статического изображения (формат BMP), речевого сообщения (формат WAV) и др.

Процесс создания виртуального прибора LabVIEW для эксперимента выполнен в несколько этапов.

На первом этапе производится считывание текстового файла, подсчет размера алфавита передаваемого сообщения и расчет вероятностей встречаемости символов алфавита.

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

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

На четвертом этапе формируется кодовая таблица Хаффмана.

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

Расчет коэффициентов сжатия проведен для следующих случаев: статистический коэффициент сжатия вычисляется как отношение размерности входного двоичного кода к средней длине кодового сообщения Хаффмана (сумме произведений вероятности встречаемости символов на длину соответствующего кодового слова Хаффмана); оптимальный коэффициент сжатия – как отношение длины исходного сообщения в битах к длине закодированного по Хаффману сообщения и реальный коэффициент сжатия – как отношение длины исходного сообщения в битах к длине закодированного по Хаффману сообщения вместе с размерностью кодовой таблицы.

В итоге, пользуясь возможностями LabVIEW, создан библиотечный модуль – вложенный виртуальный прибор кодера Хаффмана (на Рисунке 1 – для текстового сообщения), который можно использовать при создании других виртуальных приборов для анализа протоколов сжатия информации [2].

По результатам эксперимента при изменении числа кодируемых символов (количества байт информации) от 8 до 256, т.е. при изменении количества бит от 64 до 2048, для заданного фрагмента текстового сообщения можно получить зависимость коэффициентов сжатия от количества байт, которая изображена на Рисунке 2. Из приведенных результатов следует, что максимальный статистический коэффициент сжатия 3,2 может быть достигнут при кодировании 8 символов текстовой информации, при этом реальный коэффициент сжатия, получаемый с учетом передачи кодовой таблицы Хаффмана, показывает, что сжатия при передаче не происходит. Увеличения скорости передачи информации при динамическом методе кодирования по Хаффману за счет сжатия можно достичь лишь при передаче блока данных более 192 байт. В этом случае может быть достигнут реальный коэффициент сжатия »1,2. Для того, чтобы увеличить реальный коэффициент сжатия при передаче блоков меньшей длины нужно использовать комбинированные алгоритмы сжатия: сочетание алгоритма Хаффмана с групповым кодированием и с марковским алгоритмом прогнозирования для создания кодовых последовательностей минимально возможной длины.

Таким образом, получены следующие результаты:

1.          Создан библиотечный модуль LabVIEW кодера Хаффмана текстового сообщения (формат TXT).

2.          Оценены коэффициенты сжатия текстового сообщения статистический и реальный (с учетом передачи кодовой таблицы).

3.          Виртуальный прибор кодера Хаффмана используется в лабораторных экспериментах для студентов по направлению «инфокоммуникационные технологии и системы связи»

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



Список литературы

1.     Бутырин П.А., Васьковская Т.А., Каратаев В.В., Материкин С.В. Автоматизация физических исследований и эксперимента: компьютерные измерения и виртуальные приборы на основе LabVIEW7. - М.: ДМК- пресс, 2005.

2.     2.Корниенко В.Т. Руководство к лабораторно-практическим занятиям «Основы алгоритмов кодирования информации с примерами на LabVIEW» по дисциплине «Алгоритмы кодирования и шифрования информации». – Т а г а н р о г : И з д - в о Ю Ф У , 2 0 1 4 .