Способ сжатия телеметрических кадров данных
Владельцы патента RU 2697794:
Федеральное государственное бюджетное образовательное учреждение высшего образования "Тихоокеанский государственный университет" (RU)
Изобретение относится к области кодирования и декодирования без потерь с сокращением избыточности передаваемой информации и может использоваться для сжатия и восстановления телеметрических кадров данных в информационно-измерительных системах. Технический результат - повышение скорости сжатия. Данный способ заключается в отображении исходных кадров, представленных в битовом виде на поверхность тора с последующим поиском на ней прямоугольных областей и фиксацией такого числа двух пар координат, которое позволит описать все сжимаемые области, размер которых больше количества бит, отводимого на хранение координат, и фиксирующих положение левого верхнего и правого нижнего углов каждой из выделенных областей согласно изобретению, битовое представление кадра данных отображается на прямоугольник, поверхность которого затем разбивается на множество полностью покрывающих ее прямоугольных областей произвольного размера, которые могут состоять из бит только одного типа, с последующей фиксацией для каждой области глубины рекурсивного разбиения поверхности прямоугольника, проведенного для получения области, что позволяет сжимать области, которые содержат в себе число бит, больше количества бит, отводимого на хранение кода, описывающего глубину рекурсивного разбиения, проведенного для получения каждой зафиксированной области, а также бита их типа. 3 ил., 2 табл.
Изобретение относится к области кодирования и декодирования без потерь с сокращением избыточности передаваемой информации и может использоваться для сжатия и восстановления телеметрических кадров данных в информационно-измерительных системах.
Известен способ сжатия телеметрических кадров данных, в основе которого лежит отображение кадров, представленных в битовом виде, на поверхность тора с последующим поиском прямоугольных областей, которые могут включать либо биты только одного типа, либо двух типов одновременно. После обнаружения, каждую из найденных областей предлагается кодировать двумя парами координат Р1,k[х1,k, у1,k] и P2,k[x2,k, у2,k], которые задают положение левого верхнего и правого нижнего углов k-ой области соответственно (Богачев И.В., Левенец А.В., Чье Ен Ун. Геометрический подход к сжатию данных телеметрических систем // Информатика и системы управления, 2015. - №4(46). - С. 16-22).
Недостатком данного способа является то, что он не позволяет сжимать области, размер которых меньше количества бит, отводимого на хранение двух пар координат области, так же невысок показатель скорости работы способа, не всегда оптимально число пар координат, отводимых на фиксацию областей и в некоторых случаях присутствует необходимость отдельной фиксации единичных бит.
Наиболее близким аналогом заявляемого изобретения является способ сжатия двоичных данных в виде структурированных информационных блоков заключающийся в том, что для входного потока данных, который содержит символы, представленные битовыми последовательностями фиксированного размера, производят подсчет частоты повторяемости символов. Затем для обозначения часто и редко встречающихся символов производят выработку, соответственно, более короткой и более длинной битовых последовательностей, которые объединяют в совокупную битовую последовательность. Такая последовательность отличается тем, что из нее исключены битовые последовательности, соответствующие повторяющимся символам входного потока двоичных данных (патент РФ №2497277 Н03М 7/30 (2006.01) от 29.07.2010).
Недостатком данного способа является его ориентация исключительно на одномерное представление потока данных.
Технической задачей, на решение которой направлено заявленное изобретение, является повышение скорости сжатия телеметрических кадров данных.
Поставленная задача достигается тем, что в способе сжатия телеметрических кадров данных, заключающемся в отображении исходных кадров, представленных в битовом виде на поверхность тора с последующим поиском на ней прямоугольных областей и фиксацией такого числа двух пар координат, которое позволит описать все сжимаемые области, размер которых больше количества бит, отводимого на хранение координат, и фиксирующих положение левого верхнего и правого нижнего углов каждой из выделенных областей согласно изобретению, битовое представление кадра данных отображается на прямоугольник, поверхность которого затем разбивается на множество полностью покрывающих ее прямоугольных областей произвольного размера, которые могут состоять из бит только одного типа, с последующей фиксацией для каждой области глубины рекурсивного разбиения поверхности прямоугольника, проведенного для получения области, что позволяет сжимать области, которые содержат в себе число бит, больше количества бит, отводимого на хранение кода, описывающего глубину рекурсивного разбиения, проведенного для получения каждой зафиксированной области, а также бита их типа.
Принцип действия изобретения поясняется чертежом, где на фиг. 1 приведено концептуальное изображение для объяснения работы предложенного способа сжатия, при этом приняты следующие обозначения: di - результат дельта-кодирования одного отсчета в двух соседних кадрах, полученный от источника данных (датчика Дi), n - число источников данных разрядности m, Δbi - представление отсчета Δdi в виде последовательности бит, Р2,k - точка, фиксирующая положение на плоскости одной пары координат правого нижнего угла k-ой выделенной области.
Способ работает следующим образом. Телеметрический кадр данных, содержащий отсчеты n датчиков с разрядностью m, представляется в виде разностного кадра, как вектор-столбец Δd размерностью n:
Δd=(Δd1, Ad2, …, Δdi, …, Δdn)T.
Каждый элемент вектор-столбца Δdi представляется в виде битовой последовательности и записывается в виде вектор-строки Δb размерности m:
Δdi=Δbi=(bi,1, bi,2, …, bi,j, …, bi,m).
В конечном счете, вектор-столбец Δd представляется в виде разностной битовой матрицы ΔВ, размерностью n х m:
ΔВ=(Δbi, Δb2,, Δbi, …, Δbn)Т.
Далее предлагается отобразить телеметрический кадр данных, представленный матрицей ΔВ на прямоугольник, поверхность которого затем разбивается на прямоугольные однородные области, состоящие либо только из нулевых, либо только из единичных бит.
После разбиения, полученные области предлагается кодировать при помощи глубины рекурсивного разбиения, проведенного для их получения и состоянием их левого верхнего бита, кодирующим тип области (нулевая либо единичная). При этом код представляет собой битовую последовательность следующего вида:
где 
- глубина рекурсивного разбиения необходимая для получения j-ой выделенной области.
Такой подход позволяет сжимать области, которые содержат в себе число бит, больше количества бит, отводимого на хранение кода, описывающего глубину рекурсивного разбиения, проведенного для получения каждой зафиксированной области, а также бита их типа.
На фиг. 2 показан пример разбиения отображенного на прямоугольник кадра телеметрических данных с глубинами рекурсии 
требуемыми для получения каждой j-ой из всех областей равными единице и приняты следующие обозначения: 1-4 - номера областей, получившихся в результате разбиения; h1 - число столбцов 1-ой и 3-ей областей; h2 - число столбцов 2-ой и 4-ой областей; w1 - число строк 1-ой и 2-ой областей; w2 - число строк 3-ей и 4-ой областей; х, у - пара координат точки описывающей верхний левый угол области, для которой происходит разбиение; h - число строк области, для которой проводилось разбиение; w - число столбцов области для которой проводилось разбиение.
Важно заметить, что разбиение происходит строго по часовой стрелке начиная с левого верхнего угла.
Непосредственно процедуру разбиения кадра можно описать как последовательность, состоящую из следующих шагов:
1. Переменные h, w, х, у и 
определяются следующим образом: h=n; w=m; х=0; у=0 и 
Создается буфер кодов (БК) в который предлагается помещать коды, описывающие однородные области;
2. Область с параметрами h, w, х и у проверяется на однородность. Если область однородна, то 
принимает значение 
и текущая ветвь рекурсии прерывается, а в БК заносится код, описывающий полученную однородную область, в противном случае происходит переход к шагу 3;
3. Переменные h1, h2 и w1, w2 соответственно определяются согласно следующим формулам:
4. Если значение переменных h и w строго больше единицы, то разбиение выполняется последовательно для четырех областей, параметрам которых присваиваются следующие значения:
а. х=х; у=у; h=h1; w=w1 и 
После чего происходит переход к шагу 2;
б. х=х+w1; у=у; h=h1, и w=w2 и 
После чего происходит переход к шагу 2;
в. х=х; у=у+h1, h=h2, и w=w1 и 
После чего происходит переход к шагу 2;
г. x=x+w1; y=y+h1; h=h2; и w=w2 и 
После чего происходит переход к шагу 2.
5. Если значение переменной h строго больше единицы, a w=1, то разбиение выполняется последовательно для двух областей, параметрам которых присваиваются следующие значения:
а. х=х; у=у; h=h1; w=w и 
После чего происходит переход к шагу 2;
б. х=х; у=у+h1; h=h2, w=w и 
После чего происходит переход к шагу 2.
6. Если значение переменной w строго больше единицы, a h=1, то разбиение выполняется последовательно для двух областей, параметрам которых присваиваются следующие значения:
а. х=х; у=у; h=h; w=w1 и 
После чего происходит переход к шагу 2;
б. х=х+w1, у=у; h=h1; w=w2 и 
После чего происходит переход к шагу 2.
7. Если в БК помещены коды, описывающие все возможные однородные области, то выполнение рекурсивного разбиения кадра завершается.
Таким образом для примера, представленного на фиг. 2 будут получены следующие четыре кода: 1. 101; 2. 100; 3. 100; 4. 100.
Для фиксации результатов работы алгоритма предлагается использовать следующий формат, представленный на фиг.3. В общем случае заголовок такого формата состоит из пяти бит флагов Fэ.сж, Fconst, Fcm, F2 и Fn, после которых идет поле описания кодов полученных областей С.
Важно отметить, что при формировании формата могут возникнуть следующие ситуации:
- кадр данных не поддается сжатию. В этом случае заголовок состоит из одного бита флага Fэ.сж и бит несжатого кадра;
- кадр поддается сжатию и при этом значения всех отсчетов не изменились (такой кадр предлагается называть нулевым). В этом случае заголовок состоит из двух бит флагов Fэ.сж и Fconst;
- кадр данных стационарный, поддается сжатию и при этом значения хотя бы некоторых отсчетов изменились. В этом случае заголовок состоит из пяти бит флагов Fэ.сж, Fconst, Fcm, F2 и Fn, после которых идет поле описания С.
Флаги имеют следующий смысл: флаг Fcm фиксирует стационарность отсчетов кадра (устанавливается, если кадр содержит только стационарные отсчеты); флаг Fconst фиксирует неизменность значений отсчетов кадра (устанавливается если результат дельта-кодирования над всеми отсчетами кадра равен нулю); флаг Fn фиксирует наличие отрицательных отсчетов (устанавливается если результат дельта-кодирования хотя бы одного отсчета является отрицательным); флаг F2 фиксирует использование второго разряда во всех отсчетах (устанавливается если второй разряд хотя бы одного отсчета содержит единичный бит).
Процедура декодирования основывается на состоянии управляющих флагов, в связи с этим при декодировании необходимо учесть следующие ситуации:
- кадр данных не поддается сжатию. В этом случае биты данных разбиваются на n m-разрядных отсчета, после чего декодированный кадр данных формируется как сумма соответствующих отсчетов, полученных на текущем и предыдущем шагах;
- кадр данных поддается сжатию и при этом значения всех отсчетов не изменились (нулевой кадр данных). В этом случае декодированный кадр данных формируется из соответствующих отсчетов, полученных на предыдущем шаге;
- кадр данных стационарный, поддается сжатию и при этом значения хотя бы некоторых отсчетов изменились. В этом случае процесс декодирования основывается на значениях, хранящихся в поле описания, при этом выполняется следующая последовательность шагов:
1. Переменные h, w, х и у определяются следующим образом: h=n; w=m; х=0 и у=0;
2. вчитывается код описания первой полученной области;
3. Считывается первый бит кода описания текущей области;
4. Если считаный бит является нулевым, то считывается следующий за ним бит, который определяет тип восстанавливаемой области, после чего происходит ее восстановление с параметрами h, w, x, y и происходит переход к шагу 9, в противном случае происходит переход к шагу 5;
5. Переменные h1, h2 и w1, w2 определяются согласно формулам (1) и (2) соответственно. Если значение переменных h и w строго больше единицы, то восстановление выполняется для одной из четырех областей, параметрам которых присваиваются следующие значения:
а. Если область с параметрами х, у, h1 и w1 не была восстановлена, то параметрам h и w присваиваются значения h=h1 и w=w1, после чего происходит переход к шагу 9;
б. Если область с параметрами х+w1, у, h1 и w2 не была восстановлена, то параметрам h, w и х присваиваются значения h=h1, w=w2 и х=х+w1, после чего происходит переход к шагу 9;
в. Если область с параметрами х, у+h1, h2 и w1 не была восстановлена, то параметрам h, w и y присваиваются значения h=h2, w=w1 и у=у+h1, после чего происходит переход к шагу 9;
г. Если область с параметрами х+w1, у+h1, h2 и w2 не была восстановлена, то параметрам h, w, х и у присваиваются значения h=h2, w=w2, х=х+w1 и у=у+h1, после чего происходит переход к шагу 9.
6. Если значение переменной h строго больше единицы, a w=1, то восстановление выполняется для одной из двух областей, параметрам которых присваиваются следующие значения:
а. Если область с параметрами х, у, h1 и w не была восстановлена, то параметру h присваивается значения h=h1, после чего происходит переход к шагу 9;
б. Если область с параметрами x, у+h1, h2 и w не была восстановлена, то параметрам h и у присваиваются значения h=h2 и y=y+h1, после чего происходит переход к шагу 9.
7. Если значение переменной w строго больше единицы, a h=1, то восстановление выполняется для одной из двух областей, параметрам которых присваиваются следующие значения:
а. Если область с параметрами х, у, h и w1 не была восстановлена, то параметру w присваивается значения w=w1, после чего происходит переход к шагу 9;
б. Если область с параметрами х+w1, у, h и w2 не была восстановлена, то параметрам w и x присваиваются значения w=w2 и x=x+w1, после чего происходит переход к шагу 9.
8. Считывается следующий бит кода описания текущей области и происходит переход к шагу 5;
9. Если считаны все коды, то восстановление кадра данных завершается, в противном случае считывается код описания следующей области, после чего происходит переход к шагу 3.
Важно отметить, что код, описывающий полученные области, не содержит никакой информации о координатах самой области и лишь указывает на глубину рекурсивного разбиения, проведенного для ее получения и тип бит, которые в ней содержатся, в связи с чем для предложенного алгоритма процедура восстановления является симметричной.
Предложенный способ сжатия тестировался с помощью нескольких наборов телеметрических кадров данных (НКД), полученных от разных технических объектов. Для исследования использовались данные, как со стационарными свойствами, так и данные нестационарного характера.
Кадр данных представлял собой набор однобайтных отсчетов датчиков, причем для разных наборов данных кадры включали в себя разное число датчиков (от 32-х до 56-и). Все наборы отличаются друг от друга числом кадров данных. Так, набор НКД1 содержит 17 тыс.кадров данных, НКД2 - 11 тыс.кадров данных, а НКД3 - 19,5 тыс.кадров данных, а НКД4 - 19 тыс.кадров данных и НКД5 - 19 тыс.кадров данных.
В таблице 1 приведен средний коэффициент сжатия (СКС) наборов кадров данных, а в таблице 2 - среднее время сжатия (СВС), необходимое для сжатия одного кадра данных.
Таким образом, данный способ позволяет повысить скорость сжатия, за счет того, что: вместо поиска областей, которые могут включать либо биты только одного типа, либо двух типов одновременно происходит полное разбиение кадра данных на области, которые могут состоять из бит только одного типа; битовое представление кадра данных отображается на прямоугольник; фиксируется только глубина рекурсивного разбиения, проведенного для получения области, а также бит ее типа.
Способ сжатия телеметрических кадров данных, заключающийся в отображении исходных кадров, представленных в битовом виде на поверхность тора с последующим поиском на ней прямоугольных областей и фиксацией такого числа двух пар координат, которое позволит описать все сжимаемые области, размер которых больше количества бит, отводимого на хранение координат, и фиксирующих положение левого верхнего и правого нижнего углов каждой из выделенных областей, отличающийся тем, что битовое представление кадра данных отображается на прямоугольник, поверхность которого затем разбивается на множество полностью покрывающих ее прямоугольных областей произвольного размера, которые могут состоять из бит только одного типа, с последующей фиксацией для каждой области глубины рекурсивного разбиения поверхности прямоугольника, проведенного для получения области, что позволяет сжимать области, которые содержат в себе число бит, больше количества бит, отводимого на хранение кода, описывающего глубину рекурсивного разбиения, проведенного для получения каждой зафиксированной области, а также бита их типа.
