Устройство для сжатия информации

 

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

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

РЕСПУБЛИК (51)4 G 08 С 15/06

„,-г„цр11 4% 1.";,",13

Ы6 БмОТЕМА

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3990777/24-24 (22) 10.12 ° 85 (46) 30.04.88. Бюл. N - 16 (7 1) Научно-исследовательский институт прикладной математики и кибернетики при Горьковском государственном университете им. Н.И.Лобачевского (72) Ю.Г.Васин и А.Ф.Смирнов (53) 62 1.398(088.8) (56) Авторское свидетельство СССР

В 1244692, кл. G 08 С 15/06, 1984. (54) УСТРОЙСТВО ДЛЯ СЖАТИЯ ИНФОРМАЦИИ (57) Изобретение относится к технике передачи сигналов, может быть использовано при необходимости сокращеиия избыточности,при повышенном

„„SU„„1392584 A1 быстродействии, например в автоматике, телеметрии, в связи и т.д. Устройство содержит информационные каналы, включенные последовательно, реализующие последовательно-параллельную обработку входной информации.

Обработка входной информации выполняется параллельно в информационных каналах, что обеспечивает высокое быстродействие устройства в целом и повышает достоверность информации.

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

1392584

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

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

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

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

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

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

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

А с которыми работает и-й информаtn > 45. ционный канал.

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

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

Информационный канал содержит ре55 гистр 6 сдвига, обеспечивающий хранение и сдвиг двух отсчетов входной информации А и соответствующих им значений рангов К в дополнительных разрядах регистра, вычитатель 7 и сумматор 8,предназначенные для вычисления текущей ошибки кодирования в канале, вычитатель 9, выполняющий проверку критерия сжатия (П ь — at „) в канале, триггер 10 и элемент ИЛИ 11, формирующие сигналы управления для и-го и (и+ 1) -ro информационных каналов.

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

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

R, соответствующих отсчетам входной информации А, в регистре 6 канала.

Значение ранга R, равное нулю, в регистре 6 первого информационного канала формируется путем подключения входа дополнительных разрядов регистра 6 к шине 15 нулевого потенциала.

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

Устройство для сжатия информации (фиг. 1) имеет два входа 16 и 17 и один выход 18. На первый вход 16 поступают отсчеты входной информации

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

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

2584

P = 2 — 1, R

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

В процессе прохождения через устройство входных отсчетов А соответ(п ствующий им ранг может увеличиваться.

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

1имеет простую физическую интерпретацию где R — ранг отсчета А, P — число входных отсчетов, которые исключены при сжатии между отсчетами А „, и А „.

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

К=2 где К вЂ” максимальный коэффициент сжатия входных отсчетов А

11,Ю

N — число каналов.

Для предлагаемого устройства N =

4, поэтому К = 16 .

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

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

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

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

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

Отсчеты входных данных А с соФ ответствующими значениями рангов

/ 11 !! 11 11 (0 или 1 ) с выхода первого модуля сжатия записываются в регистр 6 модуля 2 по сигналам э а пи си с пе рв о го модуля 1 сжатия . Каждый второй отсчет А, поступивший на вход модуля 2, вызывает выполнение записи данных с выхода второго модуля 2 сжатия в регистр 6 третьего модуля 3 .

Каждый от сч е т A с нечетным номером

35 инициирует проверку критерия сжатия в модуле 2, а затем занесение в блок

12 коррекции модуля 2 начального значения порога сжатия, равного значению, установленному на втором входе

17 устройства. Если критерий сжатия выполняется, то присваивается значение ранга равное двум (вообще присваивается значение ранга равное номеру информационного канала (модуля))

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

55 сжатия, выполняется внеочередная запись данных с выхода второго модуля

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

3, а также изменяется состояние триггера 10 модуля 3 на противоположное.

1392584

15

Пп

П = д, где τ— д „

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

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

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

К = R> 2 = (n-1); (h-i) где n — номер информационного канала (модуля сжатия);

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

d модуль ошибки кодирования

Аа и--го модуля сжатия;

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

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

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

6 п-ro модуля сжатия коду, установленному на третьем входе элемента

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

Значение порога сжатия П 1 для

45 первого модуля 1 сжатия имеет постоянную величину и равно значению максимальной ошибки кодирования 4, установленному на втором входе 17 устройства. Поэтому сжатие данных первым модулем сжатия выполняется на основе критерия Л вЂ” d, 7i О.

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

) А + Am- 2 л

2 Ь - q ih-1t где А,„ — отсчеты входных данных; п — номер модуля сжатия.

Значения текущих порогов сжатия

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

Для остальных модулей сжатия (и 7 1) значения порогов П д формируются согласно выражению:

П = П „+,, если П = Р„-(П„-<Р„) (П„ — значение разности вычисляемой вычитателями 9 в модулях сжатия (n — 1 — N) при проверке критерия сжатия; значение порога сжатия, хранящегося в блоке 12 коррекции (и+1)-го модуля сжатия; коэффициент коррекции, постоянный для и-го модуля сжатия (n = 1, Р, = 2;

n-=2,Ç; Р, =Р,=О,5;

n, 4, Р )ф=

= 1).

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

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

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

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

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

h;<= 1 °

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

П вЂ” „ с соответствующим коэффициентом P поступает на вход блока 12 коррекции (и+1)-го модуля сжатия. В блоке 12 коррекции сравнивается значение порога сжатия с выхода блока с тем, что поступило на его вход.

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

h+

1)-го модуля сжатия.

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

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

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

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

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

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

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

139?584 канала, кроме последнего, соединен с входом триггера и первым управляющим входом регистра последующего информационного канала выход элемента ИЛИ

У

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

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

1392584 сигнал на Баде дслроисюда

e = ) б =Й

/.игнап на ЮюмФ услоойсл/а

Л7дуЛ

//одул

Раздул ф( биянал на быкоде услроислЮа

Составитель Н. Бочарова

Редактор Е.Копча Техред М.Моргентал Корректор Г.Решетник

Закаэ 2591

Проиэводственно-полиграфическое предприятие, r, Ужгород, ул. Проектная1 4

/&дую

Yodgns

Роду,в

/Ждут

Тираж 558 Подписное

ВНИИЛИ Государственного комитета СССР по делам иэобретений и открытий

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