Устройство для сжатия информации Советский патент 1988 года по МПК G08C15/06 

(21)3990777/24-24

(22)10.12.85

(46) 30.04.88. Бюл. № 16

(71)Научно-исследовательский институт прикладной математики и кибернетики при Горьковском государственном университете им. Н.И.Лобачевского

(72)Ю.Г.Васин и А.Ф.Смирнов

(53)621.398(088.8)

(56)Авторское свидетельство СССР № 1244692, кл. G 08 С 15/06, 1984.

(54)УСТРОЙСТВО ДЛЯ СЖАТИЯ ИНФОРМАЦИИ

(57)Изобретение относится к технике передачи сигналов, может быть использовано при необходимости сокращения избыточности,при повышенном

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

§

(Л

11

Изобретение относится к передаче сигналов и может быть использовано там, где требуется сокращение избыточности, при повышенном быстродействии, например, в автоматике, телеметрии, в связи и т.д. .

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

Устройство позволяет также сформировать значение дополнительных разрядов в регистрах информационных каналов.

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

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

На фиг.1 изображена блок-схема ус устройства; на фиг.2 - график, пояс- няющий работу устройства при сжатии постоянного сигнала; на фиг.З - график, поясняющий работу устройства сжатии изменяющегося во времени сигнала.

На фиг.2 и 3 использованы следующие обозначения: х - входные отсчеты, которые исключаются из рассмотрения (при сжатии); О - входные отсчеты А, которые передаются на выход устройства; R - ранг отсчетов А, характеризующий степень сжатия информации; m указывает входные отсчеты

м

с которыми работает п-й информационный канал. .

Устройство для сжатия информации содержит (для примера) четыре информационных канала (модуля сжатия) 1-4, соединенных последовательно, реализующих параллельно-последовательную схему обработки (сжатия) входных данных А. Информация с выхода канала 4 поступает на вход блока 5 памя- ти и далее с его выхода потребителю.

Информационный канал содержит регистр 6 сдвига, обеспечивающий хранение и сдвиг двух отсчетов входной информации А„ и соответствующих им

значений рангов R в дополнительН1.1х разрядах регистра, пычитатель 7 и сумматор 8,предназначенные для вычисления текущей ошибки кодирования ( в канале, вычитатель 9, выполняющий проверку критерия сжатия (HI, - /„ ) в канале, триггер 10 и элемент ИЛИ 11, формирующие сигналы управления для п-го и (п+1)-го информационных каналов.

5

0 5

О

5

0

5.

0

5

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

Все информационные каналы, кроме первого, имеют дополнительно второй элемент ИЛИ 13 и элемент 14 сравнения, предназначенные для формирования текущих значений рангов R, соответствующих отсчетам входной информации Aj, в регистре 6 канала. Значение ранга R, равное нулю, в регистре 6 первого информационного канала формируется путем подключения входа дополнительных разрядов регистра 6 к щине 15 нулевого потенциала.

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

Устройство для сжатия информации (фиг.1) имеет два входа 16 и 17 и один выход 18, На первый вход 16 поступают отсчеты входной информации А„, на втором входе 17 устройства устанавливается максимальное значение ошибки кодирования и . Отсчеты сжатой информации с соответствующими значениями рангов снимаются с выхода блока 5 памяти, который является выходом 18 устройства.

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

31392584

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

В процессе прохождения через -устройство входных отсчетов А соответствующий им ранг может увеличиваться, g Входным данным А, которые записываются в регистр 6 первого информационного канала 1, присваивается нулеое значение ранга R. Ранг данных R меет простую физическую интерпретацию 2Q

Р 2 - 1,

где R - ранг отсчета А,;

Р - число входных отсчетов, ко- 25 торые исключены при сжатии между отсчетами А ц., и А г,. Максимальный коэффициент сжатия входных данных зависит от числа модулей сжатия, включенных в устрой- зо ство:

К 2 где К - максимальньш коэффициент

сжатия входных отсчетов „ N - число каналов.

Для предлагаемого устройства N 4, поэтому К 16.

Включая дополнительные каналы (модули сжатия) в устройство между Q последним модулем и блоком 5 памяти, устанавливаем нужный максимальный ко- эффициент сжатия.Включение дополнительных модулей сжатия не влияет на быстродействие устройства..

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

Входные отсчеты А в темпе поступления записываются в регистр 6 первого модуля сжатия, сдвигая прежнее содержимое регистра вправо. Входным данным присваивается значение ранга, равное нулю. Каждый второй отсчет данных , поступивших на вход 16 устройства, вызывает выполнение за- писи данных с выхода первого модуля

1сжатия в регистр 6 второго модуля

2сжатия. Каждый отсчет А с нечетным номером инициирует проверку критерия сжатия в первом модуле. Если критерий сжатия выполняется, то присваивается значение ранга, равное единице, отсчету А, находящемуся на первом выходе регистра 6 первого модуля 1 сжатия, выполняется коррекция порога сжатия н блоке 12 коррекции второго модуля 2 сжатия, а затем устройство ожидает поступления следующих входных отсчетов. Если критерий сжатия не выполняется, то ранг данных не изменяется, обнуляется порог сжатия в блоке 12 коррекции второго модуля сжатия, выполняется внеочередная запись данных с выхода первого модуля 1 сжатия в регистр 6 второго модуля 2, а также изменяется состояние триггера 10 модуля 2 на противоположное. Эти действия обе-- спечивают продвижение входных отсчетов к выходу устройства без сжатия и без изменения их ранга.

Отсчеты входных данных А

m

с соответствуюпшми значениями рангов (О или 1) с выхода первого модуля сжатия записываются в регистр 6 модуля 2 по сигналам записи с первого модуля 1 сжатия. Каждый второй отсчет А, поступивщий на вход модуля 2, вызывает выполнение записи данных с выхода второго модуля 2 сжатия в регистр 6 третьего модуля 3. Каждый отсчет А „, с нечетным номером инициирует проверку критерия сжатия в модуле 2, а затем занесение в блок 12 коррекции модуля 2 начального значения порога сжатия, равного значению, установленному на втором входе 17 устройства. Если критерий сжатия выполняется, то присваивается значение ранга равное двум (вообще присваивается значение ранга равное номеру информационного канала (модуля) отсчету А, находящемуся на первом выходе регистра 6 второго модуля 2 сжатия, выполняется коррекция порога сжатия в блоке 12 коррекции третьего модуля 3 сжатия, а затем ожидается поступление следующих отсчетов А. Если критерий сжатия не выполняется, то ранг данных не изменяется, обнуляется порог сжатия в блоке 12 коррекции третьего модуля 3 сжатия, выполняется внеочередная запись данных с выхода второго модуля 2 сжатия в регистр 6 третьего модуля 3, а также изменяется состояние триггера 10 модуля 3 на протироположное.

5139

Эти действия обеспечивают продвижение входных отсчетов выходу устройства без сжатия и без изменения их ранга.

Остальные модули сжатия работают аналогично. Запись данных с выхода последнего модуля 4 сжатия выполняется D блок 5 памяти.

В отдельных информационных каналах (модулях сжатия) устройства выполняется сжатие данных на основе критерия:

R RM

„(h-1)

(п-1);

238Д6

дуля ошибки кодирования ляемое п модуле сжатия п вычитателя 7 и сумматора ляется по формуле

J n

2

А ,()

где А - отсчеты входных данных;

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

Пп - f.

о,

п

П

cf,

-номер информационного канала (модуля сжатия);

-текущий порог сжатия п-го модуля сжатия;

р - модуль ошибки кодирования п-го модуля сжатия;

R.

R

m-j

ранг отсчетов А и

А „ 1п-ч) , участвующих в проверке критерия сжа тия в п-м модуле.

Из выражения для критерия сжатия следует, что одним из необходимых условий для выполнения критерия сжатия является равенство рангов данных на первом и втором выходах регистра 6 п-го модуля сжатия коду, установленному на третьем входе элемента 14 сравнения п-го модуля. Так как входным данным А, поступающим на вход первого модуля схсатия, присваивается ранг данных, равный нулю, то очевидно, что для первого модуля 1 сжатия элемент 14 сравнения не нужен, так как условие равенства рангов нулю выполняется всегда.

Значение порога сжатия П , для первого модуля 1 сжатия имеет постоянную величину и равно значению максимальной ошибки кодирования л, ус- тaнoвлeннo ry на втором входе 17 устройства. Поэтому сжатие данных первы модулем сжатия выполняется на основе критерия и - J l 7, 0.

Модуль ошибки кодирования с/ входного процесса представляет собой отклонение среднего отсчета из трех последовательных отсчетов от аппроксимирующей его прямой линии, провоДИМОЙ между крайними отсчетами,участвующими в вычислении. Значение моП, и,

где П, t порог сжатия для первого модуля сжатия; постоянный максимальный допуск ошибки кодирования, установленный на втором входе устройства. Для остальных модулей сжатия (п 1) значения порогов П формируются согласно вьфажению:

П - П „, , если П Р„-(ПП- t/ f,) П „,

5

5

0

где П - cfn

-значение разности, вычисляемой вычи- тателями 9 в модулях сжатия (п

1 - N) при проверке критерия сжатия;

-значение порога сжатия, хранящегося в блоке 12 коррекции

(п+1)-го модуля сжатия;

-коэффициент коррекции, постоянный для п-го модуля сжатия (п 1, Р, 2;

п 2,3; Р, РЗ 0,5;

50

п 7, 4, 1).

,

Для учета коэффициента Р не требуется выполнения дополнительных вычислений, так как значение разности П - ( с необходимым коэффи г циентом для (п+1)-го модуля сжатия следует брать с соответствующих разрядов вычитателей 9. Значение разности с выхода вычитателя 9 модуля 1

сжатия следует подавать на вход блока 12 коррекции модуля 2 сжатия,начиная с второго разряда, на первый, младший разряд входа блока 12 кор- рекции подать значение нуля, что соответствует Р 2.

Значение разности с выходов вичи- тателеР 9 модулей сжатия 2 и 3, начиная с второго разряда (первый, младший разряд разности не учитывается), следует подать на входы блоков 12 коррекции модулей 3 и 4 сжатия, соответственно начиная с младших разрядов входов, что соответствует Р РЗ 0,5.

При включении дополнительных модулей сжатия значение разности П р - (/

р с соответствующих выходов вычитателей 9 на соответствующие входы блоков 12 коррекции передаются без смещения, что соответствует

Р п , t

Коррекция порогов с жатия П выполняется блоками 12 коррекции следующим образом. Значение разности с соответствующим коэффиПп- п

циентом Р поступает на вход блока 12 коррекции (п+1)-го модуля сжатия. В блоке 12 коррекции сравнивается значение порога сжатия с выхода блока с тем, что поступило на его вход. Если значение порога входе меньше, чем то, что хранится в блоке, то при наличии сигнала на втором входе управления блока выполняется запись нового значения порога в блок 12 коррекции, т.е. происходит коррекция .текущего порога сжатия П для (п + 1)-го модуля сжатия.

В исходном состоянии все пороги сжатия П принимают значение, равное 5 , которое поступает в блоки 12 коррекции через второй вход 17 устройства. В процессе работы устройства пороги сжатия П р корректируются и используются при проверках критерия сжатия в отдельных модулях сжатия. После проверки критерия сжатия п-м модулем значение и вновь заносится в порог сжатия П .

Состояние устройства в произвольный момент времени полностью определяется состоянием триггеров 10. Они инициируют проверку критерия сжатия во всех модулях сжатия, образую11Ц1х конвейер обработки входных отсчетов А, осуществляют занесение и коррекцию порогов сжатия П.,, обеспечивают

0

5

0

5

0

5

0

5

0

5

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

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

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

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

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

0

5

0

5

0

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

Фив. f

Сигнал но 6ходе устройства

АО()

Сигнал щ (/cm/}oucmffa

Caanajf на дходе устройства

Модуль 1

М о дум 2

Нодум

АО ) Сигнал на 6ь/ходе устройства

Фаг. 2

A,s

Фиг.З