Файл: Методы кодирования данных (Сущность теории кодирования, ее цели и задачи).pdf

Для подавления паттернинга в этом случае определим для каждого возможного двоичного кодового слова длины n величину:

где Ti – элементарные паттерны, из которых состоит данное кодовое слово.

Например кодовое слово 0110010 состоит из элементарных триплетов 011, 110, 100, 001 и 010. Данная величина фактически является вероятностью того, что внутренние биты кодового слова будут переданы без ошибок. Такая величина определяется для каждого кодового слова, количество которых равно, очевидно, 2ⁿ. Получается совокупность пар (i; P_ne(i)), которая упорядочивается в порядке убывания величины P_ne(i). Такой подход позволяет получить кодовую таблицу W, первые элементы которой являются наиболее пригодными кодовыми словами для передачи по линии, поскольку обладают максимальной вероятностью безошибочной передачи.

Перед тем как начать кодирование, определяется, код с какой кодовой скоростью m/n необходимо получить. В данном случае m – количество битов исходного сообщения, соответствующих одному кодовому слову длины n в закодированном сообщении. Далее будем обозначать за A(m,n) адаптивный код со скоростью m/n. Чем ниже кодовая скорость (и, соответственно, больше кодовая избыточность), тем меньше кодовых слов из таблицы W будет задействовано в кодировании а, значит, будут задействованы только самые надёжные кодовые слова, порождающие минимум ошибок при их трансмиссии по оптоволоконному каналу связи. Кодирование ведётся путём поиска по таблице (table lookup), в результате чего из исходных кодовых слов размера m получаются кодовые слова, каждое из которых лежит среди первых 2^m элементов таблицы W.

Декодируется сообщение путём поиска по обратной таблице W^-1, ставящей в соответствие кодовому слову его индекс в «прямой» таблице W.

Код был применён к результатам моделирования линии в 5 каналов каждый по 40 Гбит/с WDM RZ-OOK SMF/DCF с гибридным усилением. Статистика ошибок в сигнале после прохождения им 4500 км по линии имеет вид, показанный гистограммой на рис.4.

Рис.4. Гистограмма статистики ошибок

Красные столбцы представляют собой триплетную частоту ошибок, а голубые – частоту ошибок по квинтуплетам. Например, голубые столбцы, окружающие столбец 101, соответствуют квинтуплетам 01010, 01011, 11010, 11011, если их просматривать слева направо.

В ходе эксперимента были построены 16- и 24-битные адаптивные коды, результаты для расстояния в 3400 км и в 6400 км приведены на рис.5.

---

Начальные уровни значений частоты ошибок BER=10^-2 и BER=10^-1 соответственно могут быть уменьшены до 10^-3, что показывает эффективность использованного метода кодирования.

Рис.5. Уменьшение частоты ошибок в зависимости от избыточности кода

Особо стоит отметить специальные свойства ограниченных кодов, по сравнению с корректирующими кодами, действующими в одних и тех же условиях. Обозначим за BER’ частоту ошибок после декодирования сигнала, а за BER_L – максимальную частоту ошибок в канале, при которой корректирующий код способен удовлетворительно работать (выше этой частоты коррекция ошибок не способна их уменьшить, вне зависимости от избыточности кода). Последнее значение можно найти экспериментально для всякого известного корректирующего кода; как правило, оно заключено между 5⋅10^-2 и 10^-1. Хотя некоторые корректирующие коды способны немного превзойти величину 10^-1, в силу своей сложности они не могут быть использованы в быстрых оптических линиях. Далее полагаем, что при BER<BER_L корректирующая схема работает идеально и число ошибок на выходе схемы равно нулю, а при частоте ошибок больше предельного значения корректирующий код не уменьшает количество ошибок. Это соответствует действительности, так как качество работы корректирующих кодов носит пороговый характер.

Именно на границе возможностей корректирующего кода применение ограниченных кодов является наиболее эффективным, поскольку они, хотя и не способны скорректировать ошибки, могут уменьшить их общее количество прежде, чем сообщение будет декодировано FEC-кодом. Уменьшение ошибок, как было показано выше, связано с наличием в канале неравномерной статистики передачи информации, обусловленной наличием внутриканальных нелинейностей. В рассмотренном случае с помощью ограниченного кода с избыточностью 5% можно уменьшить частоту ошибок на 30%, как показано на рис.5. Учитывая, что методы сочетания ограниченных кодов с корректирующими хорошо разработаны [4], объединённый код сможет сделать работу корректирующего кода более эффективной.

2.2. Применение алгоритма дельта - кодирования при обработке радиолокационных данных

---

При испытании бортовых радиолокационных комплексов специальной контрольно - записывающей аппаратурой (КЗА) выполняется регистрация реализаций эхо-сигнала и результатов его обработки в трактах РЛС для последующего пост-полетного анализа с целью оценки эффективности работы комплекса [5]. Объем регистрируемых данных составляет несколько десятком Мбайт на каждую секунду работы комплекса, что предъявляет очень высокие требования к производительности КЗА. Естественно стремление сжимать регистрируемые данные «на лету» и без потерь [4]. Однако предложенные методы сжатие требуют значительных аппаратурных и временных затрат. Авторами ставится задача предложить алгоритм сжатия, обладающий простатой аппаратной реализации, что особо важно для бортовой системы.

Исходные данные получены в результате регистрации потоков данных контрольно-записывающей аппаратурой импульсно-доплеровской радиолокационной станции. Зарегистрированная информация, формируемая радиолокационной станцией, разбита на кадры. Кадр представляет совокупность m строк дальности, каждая строка содержит d элементов дальности (рис.6).

Рис.6. Обработка входного потока данных

Файл с исходными данными содержит в квадратурном представлении отсчеты на каждом элементе дальности (рис.7). Отсчет представляет собой пару значений (синус и косинус) размерностью по 2 байта каждое. Двадцать первых отсчетов в начале каждой дальности представляют собой вспомогательную информацию (рис.7), эти отсчеты будут исключены при выполнении сжатия сигнала.

Рис. 7. Визуализация исходных данных

После получения отсчетов из исходного файла выполнили визуализацию сигнала на первой дальности (рис.7). В дальнейшем все рисунки будут представлены для этой дальности. Далее была выполнена фильтрация сигнала с помощью средств MATLAB. Был использован фильтр Баттерворта 5-го порядка с частотой среза 0,05. Эти параметры были вы- браны путем подбора. Была использована функция пакета Signal Processing Toolbox filtfilt [2]. Эта функция позволяет компенсировать фазовый сдвиг, вносимый при обычной фильтрации. Осуществляется это путем двунаправленной обработки сигнала. Этот метод фильтрации предусмотрен только в рамках проводимого эксперимента, так как аппаратно двунаправленную обработку сигнала реализовать нельзя. Аппаратная фильтрация в режиме реального времени – тема для дальнейших разработок. Сигнал после фильтрации представлен на рис.8.

---

Разница между исходным сигналом и гладкой составляющей – шум, который был выделен для хранения и последующего восстановления исходного сигнала.

После фильтрации сигнала к гладкой составляющей был применен алгоритм дельта-кодирования [6].

Рис. 8. Фильтрация сигнала

Первый отсчет хранится неизменным в файле с шумом. Это делается для уменьшения алфавита при последующем применении алгоритма арифметического кодирования Хаффмана. Все дальнейшие значения представляются в виде разницы между предыдущим и данным отсчетом (рис.9).

Рис. 9. Результаты применения алгоритма дельта-кодирования

Разница была взята по модулю. Использование абсолютных значений позволит в дальнейшем сократить алфавит для арифметического кодирования. В результате существенно снизилась размерность данных: с 2 байт до 6 бит.

Было составлено два алфавита: для синусов, который содержит 26 символов, и для косинусов, который содержит 43 символа. Для составления алфавитов в матрице с данными, полученными в результате применения дельта-кодирования, производится поиск уникальных значений, которые заносятся в массив с последующим подсчетом количества повторений каждого из этих значений.

Затем, используя эти данные, был построен словарь Хаффмана [3], который и использовался при сжатии сигнала, с помощью функции huffmandict.

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

1. Эффективность алгоритма дельта-кодирования определяется коэффициентом сжатия, равным 2,8. Это значение получено из отношения размера несжатого файла с исходным зашумленным сигналом к суммарному размеру файлов, полученных в результате применения этого алгоритма.

где S_исх – размер исходного файла,

S_дельта – размер закодированного файла,

S_шум –размер файла с шумовой компонентой,

S_зн –размер файла с матрицами знаков,

K₁ – коэффициент сжатия после дельта-кодирования.

2. Чтобы оценить эффективность алгоритма арифметического кодирования, было вычислено отношение размера файлов, полученных на предыдущем этапе, к суммарному размеру файлов, полученных в результате сжатия методом Хаффмана. Коэффициент сжатия в этом случае составил 1,3.

---

где S_арифм –размер файла после применения арифметического кода,

S_алф –размер файла со словарем Хаффмана,

K₂ – коэффициент сжатия после применения арифметического кодирования.

3. Также в процессе выполнения работы была произведена попытка сжатия шумовой компоненты методом арифметического кодирования без предварительной обработки дельта-кодированием. Коэффициент сжатия для шума составил 0,8, то есть на выходе получили файл большего размера, чем исходный. Отсюда можно сделать вывод, что применение алгоритма Хаффмана для шумовой компоненты нецелесообразно.

4. Суммарный коэффициент сжатия, показывающий отношение размера исходного несжатого файла к размеру набора выходных файлов, составил 3,6. Этот коэффициент немного меньше ожидаемого, что объясняется потребностью хранения дополнительной информации. Однако он является приемлемым.

где K_сум – итоговый коэффициент сжатия.

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

Заключение

Все данные и команды в ЭВМ циркулируют в виде двоичных чисел. Информацию можно кодировать числами в различных системах счисления. Особая значимость двоичной системы счисления в информатике определяется тем, что с технической точки зрения разработчикам компьютерной техники такое представление информации казалось самым простым. Требовалось различать только два устойчивых состояния устройства: включено и выключено. Достаточно сложно создать устройство, которое могло бы обеспечить десять устойчивых состояний, да еще и быстрый переход из одного в другое. Поэтому вся сложная начинка микропроцессора сводится к поддержке двух легкоразличимых состояний: высокий сигнал – 1, низкий сигнал – 0.

Наиболее распространены две системы кодирования – ASCII и Unicode. ASCII (American Standart Information Interchange) была создана в 1963 г. В своей первоначальной версии это система семибитного кодирования. В следующей версии фирма IBM перешла на 8-битную кодировку символов. В ней первые 128 кодов отданы под буквы английского алфавита, цифры и некоторые специальные символы.

---