Применение метода вейвлет-кодирования для сжатия и реконструкции физиологической информации, передаваемой по каналу радиотелеметрии
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?сти.
Алгоритм относится к разряду очевидных. Недостаток метода состоит в непредсказуемом объеме выходной последовательности и малой эффективности при использовании для кодирования биологических сигналов, для которых характерна шумовая форма с равномерным частотным распределением.
3.1.3Коды Хаффмена
Алгоритм: Пусть I1, тАж IK - положительные целые числа (какими и являются отiеты сигнала). Для того, чтобы существовал префиксный код, длины слов которого равны I1, тАж IK, необходимо и достаточно выполнение неравенства Крафта:
Все префиксные коды являются кодами со свойством однозначного декодирования, но не наоборот. Избыточность дешифрируемого кодирования неотрицательна. Для кода Хаффмена избыточность не превышает 1. Чем больше длина символом входного алфавита, тем меньше избыточность.
Для кода Хаффмена значительными являются требования к памяти данных для раiета алфавита. Недостатком можно назвать непредсказуемый коэффициент компрессии для каждой конкретной последовательности (имеется ввиду его вариабельность).
3.1.4Вероятностное кодирование
Алгоритм: Кодирование осуществляется с построением модели Маркова 2. Осуществляется предсказание очередного кода по известным двух последним. Если предсказание осуществлено верно, то вместо кода передается логическая единица, а приемная сторона по той же модели вычисляет предсказанный код. Если предсказание неверно, то передается логический ноль и собственно код. Для некоторых видов сигналов, например, значение давления в манжете или узкополосные сигналы вроде импедансной пневмограммы или плетизмограммы, модель Маркова 2 может дать неплохие результаты. Однако, унификация протокола магистрали и построение строгой модели информационных потоков требует выбора метода компрессии для всех сигналов. Недостаток метода - непредсказуемость выходного потока в смысле объема информации и неработоспособность для сигналов всплескового характера.
3.1.5Алгоритм LZ77
Алгоритм: Имеется скользящий словарь V объемом 2-32 кБ. Если очередная входная строка совпадает со строкой словаря, то она заменяется на указатель на эту строку вида ptr={prefix, distance, length}. Понятие словаря и строки несколько отличается от обыденного - под строкой подразумевается любая непрерывная последовательность отiетов кода. Длина кода обычно выбирается из диапазона 16 - 256 байт. Алгоритм адаптирующийся, то есть подразумевается составление словаря по составу поступающей информации. Таким образом, в первый момент сжатия информации не происходит. Значительные возможности по эквивалентной компрессии сигнала могут быть получены при существенной предсказуемости сигнала, то есть повторении его последовательностей кода. Код, отсутствующий в словаре транслируется без изменения. Реализация алгоритма построения словаря и поиска по словарю - достаточно сложные и медленные процедуры. Объем выходного кода имеет не предсказуемую величину в известном смысле и не представляется возможным транслировать словарь на приемную сторону.
3.1.6 Алгоритмы LZ78 - LZW84
Модификация метода LZ77, также требующая управления словарем и передачи его на приемную сторону.
Результаты обзора классических методов компрессии сигналов в реальном времени сведены в таблицу 2. Величины степени сжатия, скорости, объема требуемой памяти указаны в условных единицах.
Таблица 2. Методы компрессии сигналов в реальном масштабе времени.
АлгоритмСтепень сжатияСкоростьПамятьСжатие без потерьПроходыРаспространение ошибкиВозрастание избыточностиRLE2-31010Да1НетВозм.VLI2-3910Да1ДаВозм.Хаффмен5-688Да2ДаРедкоВероят- ностное5-696Да1ДаВозм.LZ778-932Да1ДаРедко
Так или иначе ни один алгоритм компрессии сигнала не может обеспечить предсказуемого (в смысле объема выходного потока) коэффициента сжатия.
Особенность измерительного сигнала электрофизиологии - его всплесковый характер. Для обработки подобных сигналов разработан вейвлет-метод декомпозиции и реконструкции сигнала. Основной его идеей является разложение сигнала по заданному алгоритму на коэффициенты во временной области и трансмиссию исключительно последних. На приемной стороне с применением обратного алгоритма производится реконструкция сигнала. Собственно вейвлет-кодирование не предусматривает компрессию сигнала и не дает уменьшения объема информации при передаче коэффициентов разложения, однако, имеется возможность обработки коэффициентов с целью исключения избыточности биологического сигнала.
Всплесковая особенность биологического сигнала позволяет построить декомпозицию на основе вычисления сверток сигнала с выбранными вейвлетами. Серьезной проблемой остается выбор вейвлета, по вычислительным возможностям адекватного способности микроконтроллерного ядра работать по алгоритму в реальном времени.
В этом отношении вейвлеты более высоких порядков позволяют значительно повысить эффективность кодирования. На рис.2 представлены вейвлеты Хаара и Daubechies 3. На рис.3 представлено графическое представление коэффициентов декомпозиции выбранного сигнала (кардиограммы) и их объема.
Рис.2.Вейвлеты Хаара и Daubechies 3.
А) 2500 отiетов 1:1 (исходный сигнал)
Б) 313 отiетов 1:8
В) 161 отiет 1:16
Рис.3.Декомпозиция ЭКГ-сигнала с применением вейвлет- кодирования.
А) Исходный сигнал - 2500 отiетов
Б) Графическое представление коэффициентов декомпозиции по Хаару - 313