Устройство для сжатия данных

Устройство для сжатия данных

Иллюстрации

Показать все

Реферат

 

Изобретение относится к телемеханике и может использоваться в телеметрических системах. Изобретение осуществляет на каждом интервале аппроксимации передачу только необходимой части информации в виде первых коэффициентов существенных групп коэффициентов Уолша-Пэли и существенных погрешностей аппроксимации остальных коэффициентов Уолша-Пэли, которая позволяет восстановить сигналы с заданной погрешностью по всей длине реализации, что повышает информативность устройства. 2 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) (51) 4 G 08 С 19/28

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4349905/24-24 (22) 25.11.87 (46) 15. 11. 09. Бюл. 1(42 (71) Хозрасчетный научно-исследовательский институт "Алгоритм" при

Узбекском научно-производственном объединении "Еибернетика" А11 УЗССР (72) И.И.Исмагилов (53) 621.398(088.8) (56) Авторское свидетельство СССР

У 1012313, кл. С 08 С 19/28, 1981.

Авгорское свидетельство СССР

Ф 645153, кл. G 06 F 7/04, 1977.

Изобретение относится к телемеханике и может использоваться в телеметрических системах.

Цель изобретения — повышение информативности устройства.

На фиг. 1 представлена функ(иональная схема устройства, на фиг. 2функциональная схема блока 6 кодирования.

Устройство (фиг. 1) содержит информационный вход 1, ортогональный преобразователь 2 Уолша-Пэли, блоки 3(-3 1 делителей напряжения, блоки 4, -4 „, вычитателей первый ключ 5,, первые группы 5 -5„ ключей, второй ключ 5„+< . блок 6 кодирования, первый дискриминатор 7,, блоки 7 -7„ дискриминаторов, второй дискриминатор 7„+,, первый дифференцирующий элемент 8,, блоки 8 -8

2 (54) УСТРОЙСТВО ДЛЯ СЖАТИЯ ДАННЫХ (57) Изобретение относится к телемеханике и может использоваться в телеметрических системах. Изобретение осуществляет на каждом интервале аппроксимации передачу только необходимой части информации в виде первых коэффициентов существенных групп коэффициентов Уолша-Пэли и существенных погрешностей аппроксимации остальных коэффициентов Уолша-Пэли, которая позволяет восстановить сигналы с заданной погрешностью по всей длине реализации, что повышает, информативность устройства.

2 ил. дифференцирующих элементов, второй диф" ференцирующий элемент 8,„+,, первый триггер 9,, блоки 9,2- 9„триггеров, второй триггер 9 „„, генератор 10 пилообразного напряжения, элементы 11(-11 „, ИЛИ, элементы 12,—

12 „, И, вторая группа 13 ключей, первый формирователь 14(модуля числа, блоки 14 -14„формирователей модуля числа, второй формирователь 14д+, модуля числа, сумматор 15, блок 16 сравнения, третий триггер 17, третий дифференцирующий элемент 18, информационный управляющий выходы 19 и 20, установочный и синхронизирующий входы 21 и 22.

Блок 6 кодирования (фиг. 2) содержит информационные входы 23,-23„, 24,-24„, синхронизирующий вход 25, 1522268 элементы 26, 27 задержки, генератор

28 тактовых импульсов, аналого-.цифровые преобразователи 29„-29» буферные регистры 30,-30„, регистр 31 сдвига, коммутаторы 32-34, блок 35 постоянной памяти, компаратор 36, счетчик 37 им.— пульсов.

В основу алгоритма сжатия данных, l заложенного в устройство, положено следующее свойство разложения степенных функций по функциям Уолша-Пэли

r-го ранга:

Р, Р. т, -(К.,. а„ 15

С +2+...+2 (-1) р-„»<2 где С +2 ...+2 р р р,, Т

Р 1 1 1 И 0,1,...,п-r-1; И И + 1, ° ° ° Q-Г

° ° ° ° ° 4 4 ° ° ° ° ° ° ° ° ° °

Р И1,, +1,...,n-1.

Двоичная зависимость между коэффициентами разложения функции набпюдается также в пределах группы коэффициентов (r-1)-го ранга.

40 Коэффициенты разложения в пределах групп коэффициентов r-ro и (r-1)-го рангов могут быть получены соответствующим двоичным масштабированием первых коэффициентов соответствующего ранга.

С +2 ° ° .+2 "=С о+2 +...+2

i" -@т fLIp к2

j(1 2+„° + v-+(о,+ и,+ „, fU Q

) 50

С +2 ...+2 Ñ +2 ...+2

Я- о ((1 2+,.,>l--L}-I p, p Ф„, р„,Д (3) 55

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

Область изменения должна удовлетворять ме равенства.. коэффициенты разложения с порядковым номером 20 к=2 +2, ° .+2 "; длительность интервала преобразования, номер разряда 25 двоичного кода К, содержащий 1. всех И;(з.1,r) следующей систе30 (нулевой коэффициент и соответственно первые коэффициенты групп коэффициентов первого и второго рангов), по ним можно точно восстановить исходный сигнал, восстанавливая остальные коэффициенты по формулам (2,3). Дпя полиномиальных сигналов более высоких по рядков (r >,2) соотношения (2,3) точно выполняются лишь для групп коэффициентов (l 1)-го и r-го рангов, а для остальных групп коэффициентов соответственно с некоторой погрешностью

ДС +2 +...+2 * С +2 +...+

Р Р2 1М Р Ра

1,-с +2 + „, +2 ((к ...+ - )-(р,+р +...+р, )).

+2 2

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

В широком классе реальных сигналов диапазон изменения величины погрешности аппроксимации коэффициентов разложения меньше, чем диапазон изменения самих коэффициентов разложения, что приводит к возможности увеличения коэффициента сжатия данных. Наибольший выигрыш в коэффициенте сжатия достигается в классе полиномиальных сигна- ° лов невысоких порядков. Например, для разложения полинома первого порядка выигрыш относительно прототипа оцении+1 вается величиной К вЂ” — раз а для

Э

rl+1+С2 полинома второго порядка К

3 раз, где С „ — биномиальный коэффициент, т.е. при п=З-7; K„ 2-4, К 2-9 при нулевой погрешности аппроксимации сигнала.

Устройство работает следующим образом.

После прихода синхроимпульса на вход триггера 17 триггеры 9 устанавливаются в состояние "О" после срабатывания триггера. 1 7.

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

5 152226

С, (КТ ) = S » S (t) pa1i (t-KTp) dt, Первый коэффициент группы коэффи-: циентов Уолша-Пэли i-ro i=1,n-1 ранга при наличии хотя бы одной существенной погрешности аппроксимации . где ра1i (t) — функция Уолша-Пэли, Т вЂ” временная база функций

Уолша-Пэли

К вЂ” текущий номер анализируемого интервала входного сигнала S(t).

В результате разложения аналогового 0 сигнала S(t) в ряд Уолша-Пэли на выходе преобразователя 2 имеем спектр Уолша-Пэли в аналого-дискретной форме.

Первый коэффициент Уолша-Пэли

i5

i-ro(i=1 и-1) ранга подается на вход

i-го блока 3 делителей напряжения, с выходов которого аппроксимированные значения коэффициентов Уолша-Пэли

i-,ro ранга, начиная со второго коэф. фициента группы коэффициентов этого. ранга, С (К = i) подаются на третие входы въ1читателей i-го блока 4, на первые и вторые входы которых поступают истинные значения этих коэффици- 25 ентОВ с со Ответствующих выходов Ор тогонального преобразователя 2. Сформированные в вычитателях значения по-. грешности аппроксимации 5 С = С, С ,1 1 и первЬ|е члены групп коэффициент ов

i-ro (i O,n) ранга подаются на входы соответствующих ключей 5 и дискриминаторов 7. Значения первых коэффициентов Уоша-Пэли i-го (i=O,n) ранга и погрешности аппроксимации остальных коэффициентов Уолша-Пэли с помощью дискриминаторов 7 и генератора 10 пилообразного напряжения, который формирует парафазное нарастающее пилообразное напряжение, преобразуются в ши рину импульсов. После дифференцирования выходных сигналов дискриминаторов

7 с помощью дифференцирующих элементов 8 импульсы поступают на входы установки в единицу триггеров 9. Благодаря широтно-импульсному преобразованию значений первых коэффициентов .

Уолша-Пэли i-го (i=O,n) ранга и погрешностей аппроксимации остальных коэффициентов, сначала замыкаются те 50 ключи 5, которые коммутируют значения погрешностей аппроксимации коэффициФ ентов Уолша-Пэли, нулевой и (И-1)-ый коэффициенты Уолша-Пэли (первые коэффициенты Уолша-Пэли нулевого и и-ro

55 ранга) с наименьшими по модулю значениями. Эти значения нулево" î и (Б-1)"

ro коэффициентов, погрешностей аппроксимации коэффициентов Уолша-Пэли поступают через соответствующие формирователи 14 модуля числа в сумматор

15. Поступление первых коэффициентов групп коэффициентов Уолша-Пэли i-го (i=1 и-1) ранга через ключ 13 на вход формирователя 14,, модуля числа производится лишь при срабатывании всех дискриминаторов блока 7,,, так как управляющее воздействие ключа 13 формируется элементом 12; И при наличии уровня "1" на выходах всех триггеров блока 9;q<

Таким образом, в сумматоре 15 формируется максимальная погрешность восстановления сигнала, равная сумме модулей отброшенных первых коэффициентов групп коэффициентов УолшаПэли i-гo (! =О,п) ранга, погрешностей восстановления аппроксимированных коэффициентов Уолша-Пэли. Как только выходное напряжение сумматора 15 становится равным или больше заданной максимальной г.огрешности восстановления блок 16 сравнения срабатываег и перебрасывает триггер 17 в "1".

При срабатывании триггера 17 и дифференцирующего элемента 18 триггеры

9 устанавливаюгся в нулевое состояние, размыкая ключи 5 и снимая сигналы с информационных входов 23 блока

6 кодирования. При этом первые коэффициенгы групп коэффициентов УолшаПэли соотвегствующнх рангов и погреш- ности аппроксимации коэффициентов. которые имеют более высокие уровни значений амплитуды, чем наибольшая из амплитуд первых коэффициентов групп коэффициентов Уолша-Пэли и погрешностей аппроксимации коэффициентов, отбрасывание которых обеспечивает заданную погрешность аппроксимации f, окажутся подключенными к блоку 6 кодирования уже после срабатывания триггера 17 и дифференцирующего элемента 18. Эro связано с тем, что по мере нарастания напряжения генератора 10 будут срабатывать дискриминаторы 7, что приведет к установке соответствующих триггеров 9 в единичное состояние, которые замкнут соответствующие ключи 5, подключая сигналы к информационным входам 23 блока 6 кодирования.

1522268 ос тапьпых коэффициентов з того ранга также окаже.гся подключенным к блоку 6 коцирования, так как управление ключем 5, „, осуществляется с выхода

5 элемента 11„ ИЛИ, который объединяет выходные сигналы соответствующих тригi геров 9.

Блок 6 кодирования осуществляет аналого-цифровое преобразование суще- 10 ственных первых коэффициентов групп коэффициентов Уопша-Пэли и погрешностей аппроксимации остальных и обеспечивает их выдачу потребителю в виде кодограммы с адресной информацией.

В качестве адресной информации используется кодовое слово-маска в ко1 гором уровень "1" в каком-либо разряде указывает на существенность соответствующего коэффициента Уолша-Пзли или погрешности их аппроксимации, а уровень "0" информируег о том, что ,соответствующий згому номеру коэффици; ент Уолша-Пзли или погрешность аппрокlснмации не передается потребителю.

Блок b кодирования работает следую, щим образом.

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

1, ре Уэлша-Пзли входного сигнала (сов, падаег с длительностью участка линей-ного нарастания напряжения генератора . 10 п ьчообразного напряжения) . Задер xàHíûé синхроимпульс поступает на управляющие входы преобразователей 29, на информационные входы которых к згому моменту поданы сущесгвенные пер-. вые коэффициенты групп коэффициентов

Уолша-Пэли и погрешности аппроксимации коэффициентов„ сохранение которых обеспечивает заданную погрешность представления сигнала Я . Импульс с выхода элемента 27 задержки (время задержки определяется временем преобразования в преобразователях 29) запускаег r åíåðàòoð 28 тактовых импульсов, сбрасывает счечитк 37 и поступает на входы разрешения записи буферных

55 регистров 30 и регистра 31 маски, вследствие чего первым импульсом генератора 28 кодовые слова с выходов преобразователей 29 запишутся в соответствующие регистры 30. Также произойС,=1

С,=0, Запись И вЂ” L означает подключение

М-го входа коммутирующего элемента к

L-ому выходу.

Каждый i-ый коммутатор 33 управляется сигналами с (i+1)-ro и (i+2)-ro информационных входов 24. Логику работы коммутаторов 33 можно задать в виде следующего правила."

2- 2

21

12

1 — 1

С 1Ф(6;,+, < 1<с;., где G;+<, С;, z — сигналы соответственно с (i+1)-го и (i+2)-ro информационного входа 24 ° Коммутатор 34 управляется сигналами i-го информа— ционного входа 24 согласно правилу:

При рассмотренной логике работы коммутаторов 32-34 формируется последовательная цепочка из регистра 31 маски и тех регистров 30<-30,, в которых записаны кодовые слова величин существенных первых коэффициентов групп коэффициентов Уолша-Пэли и погрешностей аппроксимации коэффициентов, сохранение которых обеспечивает дет запись информации (состояний соответствующих триггеров 9 и выходов злеменгов 11 ИЛИ) с информационных входов 24 в регистр 31 маски.

Последующие тактовые импульсы осу— ществляют вывод данных путем их сдвига в регистрах 30 и 31. При этом включение регистров 30 в последовательную цепочку осуществляется при помощи коммутаторов 32-34, управляемых сигналами с информационных входов 24 таким образом, что из последовательной цепочки регистров 30 исключаются те регистры 30, информация которых несущественна.

Достигается это следующим образом.

Коммутатор 32 обеспечивает включение либо исключение регистра 30 .из последовательной цепочки и управления сигналом C с информационного входа

24 по следующему правилу:

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

28. Сигнал конца вывода информации вырабатывается цифровым компаратором

36, где производится сравнение кода числа тактовых импульсов, подсчитанных счетчиком 37, с кодом требуемого числа0 тактовых импульсов, необходимых для вывода кодограммы текущего интервала обработки сигнала. Код требуемого числа тактовых импульсов выставляется на выходах блока 35 постоянной памяти, на адресные входы которого подаются сигналы с информационных входов 24.

Необходимость такого способа формирования сигнала конца вывода информации связано с тем, что данные в пре.20 образователях 29 могут кодироваться двоичными кодами разной разрядности, вследствие чего приходится на каждом цикле вывода информации заново определять количество тактов, необходимых 25 для вывода кодограммы. Количество этих тактов определяется количеством тактов для вывода кодового слова-маски (эти величина постоянна) и количеством тактов для вывода кодовых слов 30 существенных первых коэффициентов группы коэффициентов Уолша-Пэли и погрешностей аппроксимации коэффициентов (именно эта часть кодограммы может из— меняться от цикла к циклу).

Сигналом конца вывода информации с выхода компаратора 36 производится останов генератора 28, выход которого является также выходом 20 блока

6 кодирования (тактовые импульсы используются при выводе как синхроимпульсы сопровождения информации).

Кодограмма выдается потребителю с выхода регистра 3 1 маски, являющегося выходом 19 блока 6 кодирования. 45

Таким образом, в устройстве в каж— дом интервале аппроксимации передается только необходимая часть информации (первые коэффициенты существенных групп коэффициентов Уолша-Пэли и суще-50 ственные погрешности аппроксимации ос— тальных коэффициентов Уолша-Пэли), которая позволяет восстановить сигнал с заданной погрешностью по всей длине реализации. При этом коэффициент сжа- 55 тия (информативность устройства) повышается для широкого класса реальных сигналов, в особенности для гладких сигналов, достаточно хорошо описываемьгх алгебраическими полиномами невысоких порядков. В качестве примера можно привести сигналы изображений некоторых классов, в которых большинство участков характеризуется линейным изменением яркости.

Формула из обр ет ения

Устройство для сжагия данных, содержащее ортогональный преобразователь „юцц ормационный вход которого является. информационным входом устройсгва ;первый выход ортогонального преобразователя соединен с информационным входом первого ключа и первым входом первого дискриминатора, второй выход ортогонального преобразователя соединен с информационным входом второго ключа н первым входом второго дискриминатора генефатрр пилообразного напряжения, первый и второй выходы которого соединены соответсгвенно с вторыми и третьими входами первого и второго дискриминаторов, выходы которых соединены через одноименные первый и второй дифференцирующие элементы с входами установки в "1" соответственно первого н второго триггеров, выходы которых соединены с управляющими входамн соответственно первого и второго ключей, выходы которых соединены соответственно с первым и вторым информационными входами блока кодирования и через одноименные первьпЪ и второй формирователи модуля числа — с соответствуюшими первым и вторым входами сумматора, первый выход блока кодирования является информационным выходом устройства, выход сумматора соединен с первым входом блока сравнения, второй вход которого является установочным входом усгройства, а выход соединен с входом установки "1" третьего триггера, выход которого соединен через третий дифференцирующий элемент с входами установки в

"0" первого н второго триггеров, вход генератора пилообразного напряжения объединен с синхронизирующим входом ортol o÷àëüíîãо преобразователя и входом установки в "0" третьего триггера и является синхронизирующим входом устройства, о т л и ч а ю— щ е е с я тем, что, с целью повьппения информативности устройства, в него введены блоки делителей напряжения, блоки вычитателей, группы ключей, ll f52226 блоки дискриминаторов, блоки дифференцирующих элементов блоки триггеров, элементы ИЛИ, элементы И и блоки формирователей модуля числа, третьи выходы ортогонального преобразователя соединены с входами одноименных блоков делителей напряжения, первькчи входами одноименных блоков вычитатепей, информационными входами первых ключей f0 соответствующих первых rpyaa è первыми входами одноименных блоков дискри- минаторов, вторые и третие входы которых объединены и подключены соответственно к первому и второму выходам f5 генератора пилообразного напряжения, выходы групп выходов ортогонального преобразователя соединены с одноименными вторыми входами соответствующих блоков вычитателей, выходы блоков де- 20 лителей напряжения соединены с одноименным третьима входами соответствующих блоков вьиитателей, выходы которых соединены с информационными входами одноименньк вторых ключей со- 2 ответствующих первых групп и одноименными четвертье и входаии соответствующих блоков дискриминаторов, выходы которых соединены с одноименнюа входами соответствующих блоков диФФереици"ЗО рующих элементов, выходы которых соединены с одноименными входамн установки в "1" соответствукицих блоков., триггеров, входы установки в "О" которых объединены и подключены к выходу третьего дифференцирующего элемента, 12 выходы блоков триггеров соединены с одноименными входами соответствующих элементов ИЛИ, управляющими входами одноименных вторых ключей соответствующих первых групп, соответствующими третьими информационными входами блока кодирования и одноименными входами соответствующих элементов И,.выходы которых соединены с управляющими входами соответствующих ключей второй группы, выходы которых соединены с первыми входами одноименных блоков

Формирователей модуля числа, выходы которых соединены с соответствующими

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

15Z226b

1522268

Состаьи.гель М. Никуленков

Редактор М.Товгин Техред Jl. Серд окова Коррекгор О.Ципле

Заказ 6967/49 Тираж 518 Подпис ное

ВНИИПИ Государственного комитета по изобретениям и открьгтиям ври ГКНТ. СССР

1 13035, Москва, Б-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. ужгород, ул. Гагарина, 10 1