Устройство для сокращения избыточности информации

 

Союз Советских

Социалистических

Республик

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (»>9591 о9

Ф

--й (61) Дополнительное к авт. свид-ву— (22) Заявлено 22.07.80 (21) 2966739/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51) Ni. К,.з

G 08 С 19/28

Гееударстееннмй комитет (53) УДК 621.398 (088.8) Опубликовано 15.09.82. Бюллетень № 34

IIo делам изобретений и еткрмтий

Дата опубликования описания 15.09.82

) (72) Авторы изобретения

А. Г. Мамедов, А. С.,Лакерннк, В. Я. Зенин и В. С. Да

F

RUE

Институт технической кибернетики АН Белорусской (71) Заявитель (54) УСТРОЙСТВО Д,ЛЯ СОКРАЩЕНИЯ ИЗБЫТОЧНОСТИ

ИНФОРМАЦИИ

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

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

Недостатком такого устройства является низкое быстродействие и сложность аппаратурной реализации.

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

«ыходами первого и второго регистров, выход первого блока вычитания соединен с первым арифметическим блоком, второй арифметический блок, блок синхронизации, соединенный с входными шинами, ключ, первым входом соединенный с выходом пер2 вого регистра, выходом — с выходной шиной, выход блока вычитания соединен через дешифратор и первый арифметический блок с вторым арифметическим блоком и выходным арифметическим блоком, выход которо5 го подключен к второму входу ключа, второму арифметическому блоку и к второму входу счетчика, первый вход которого соединен с входом устройства, а выход подключен к второму входу дешифратора (2).

Недостатками такого устройства являются сложность его аппаратурной реализции, а также ограниченность его использования для сжатия информации процессов с повышенной динамикой, т. е. низкое быстродей.ствие. Это бъясняется тем, что данное устIs ройство реализует критерий выборки в соответствии с выражением где $i = у. — у,, — приращение процесса на i-ом такте; — текущая ордината процесса; у. — предыдущая ордината процесса;

i — текущее число шагоь квантования в выборке;

959129

5 о б — допустимое значение линеййой аппроксимации; л — коэффициент, зависящий от точности аппроксимации.

Реализация указанного критерия требует осуществления операций сложения, вычитания, деления, умножения и возведения в степень. Это приводит к значительным аппаратурным затратам. Обработка одного приращения в устройстве, как показано ниже в технико-экономическом обосновании, происходит за 19 тактов.

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

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

25 зо

55 соединен с управляющим входом регистра сдвига, второго регистра и с третьим входом первого элемента И, второй выход — с управляющими входами блоков вычитания и с

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

Блок анализа содержит элементы ИЛИ, И, ИЛИ-НЕ и элементы задержки, первые входы элементов И и первый и второй входы первого элемента ИЛИ-НЕ подключены к первому и второму входам блока анализа, выходы соединены с входами первого элемента ИЛИ, выход которого подключен к первому входу второго элемента ИЛИ, выход которого через первый элемент задержки соединен с вторым выходом блока анализа, третий и четвертый входы блока анализа соединены с вторыми входами элементов И с третьим и четвертым входами первого и с первым и вторым входами второго элемента ИЛИ-НЕ, третий вход которого подключен к выходу первого элемента ИЛИ-НЕ и к первому выходу блока анализа, выход подключен к первому входу третьего элемента ИЛИ, второй и третий входы которого соединены соответственно с пятым и седьмым входами блока анализа, выход подключен к четвертому выходу блока анализа, к второму входу второго элемента ИЛИ и через второй элемент задержки — к третьему выходу блока анализа, третий вход второго элемента ИЛИ соединен с шестым входом блока анализа.

На. фиг. 1 приведена блок-схема предлагаемого устройства; на фиг. 2 — кривая для пояснения принципа сокращения избыточностии.

Устройство (фиг. 1) содержит регистры 1 и 2, блок 3 вычитания, арифметические блоки 4 и 5, блок 6 синхронизации, соединенный с входными шинами 7 и 8, ключ 9, выходную шину 10, информационную шину 11, регистр 12, элемент И 13, блок 14 вычитания, блок 15 анализа, элемент И 16, блок 17 сравнения, триггер 18, регистр 19 сдвига, элемент И 20 и входную шину 21.

Блок 15 анализа содержит элементы И 22 и 23, элементы ИЛИ 24 и 25, элемент 26 задержки, элементы ИЛИ-HE 27 и 28, элемент ИЛИ 29 и элемент 30 задержки.

Суть метода обработки информации, заложенного в предлагаемом устройстве, состоит в определении отношения — для каждой точки двухмерного информационного массива, сравнения этого отношения с соответствующим отношением для предыдущей точки с заданной точностью, т.е. для 1-й точки определяется отношение аx и сравнивается с отношением - -, полученным для (1 — 1) -й точки, х с- где Л Y < = Y — Y; Л Y„= Ъ ; — Y; а X„Y,; Х; „, Y; Х„., ӄ— координаты

959129 начальной (или информативной), (1 — l)-й и i — и точки соответственно.

Иными словами, реализуется с заданной точностью критерий выборки в соответствии с выражением дч, Дяi -s ц дх;

При этом точность (или погрешность) сравнения задается оператором длиной разрядной сетки сравниваемых отношений

4х . Я -л

Дх," Лх;;

1О

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

Для анализа формы вводимой кривой в устройстве определяются элементарные приращения координат ЛХ, ЛУ каждой последующей точки относительно предыдущей, для чего координаты первой точки записываются в регистр 1, второй — в регистр 12, третьей — в регистр 2, при этом на блок 14 вычитания поступают координаты из регистров 1 и 12, а на блок 3 вычитания — из регистров 1 и 2. Блок 14 определяет разности

ЛХ, и ЛУл, а блок 3 определяет разности

ЛХ, и ЛУ,. Значения ЛХ„и ЛУ„поступают зо

35 в арифметический блок 5, а значения ЛХ, и ЛУ поступают в арифметический блок 4, причем на выходе блока 5 получается частное 4ф, а на выходе блока 4 частное . 4о а л 4ял

Полученные частные являются тангенсами углов наклона элементарных отрезков прямых или элементарными производными вводимой кривой. Сравнивая между собой значения + и ф, можно определить, лежат точки на одйой прямой или нет. При нераВЕНСтВЕ ЧаСтНЫХ л И 4"- даЕтСя раэрЕШЕНИЕ ах„дх„ на вывод координат точки в ЭВМ, а также перезаписи координат первой точки в регистр 1, а второй точки в регистр 12, а при равенстве двух значений дается разрешение только на перезапись координат второй точки в регистр 12, при этом координаты первой точки стираются. В обоих случаях координаты последующей точки записываются в регистр 12. При обнаружении признака прямолинейного участка координаты каждой 55 последующей точки на этой прямой сопоставляются с координатами начальной точки участка, чем достигается высокая точность прямолинейные участки кривой. Точки перехода из криволинейного участка в прямолинейный и наоборот считываются характерными точками данной кривой. В процессе 2о такой, обработки координаты характерных точек поступают на выход устройства для ввода в ЭВМ, а координаты точек, лежащих на прямолинейных участках вводимой кривой, на выход устройства не поступают и в ЭВМ не вводятся. 25 анализа и исключает .я ошибочное представление криволинейных участков с большим радиусом кривизны прямолинейными. При обнаружении криволинейного участка координать1 каждой последующей точки на этой кривой анализируются с координатами каждой предыдущей точки, и при выполнении условия неравенства координаты предыдущей точки передаются в ЭВМ. При этом количество выводимых точек на единицу длины участка кривой зависит от кривизны участка и величины принятой координаты.

При обнаружении участка прямой, параллельной оси координат, т. е. когда ЛХ или лУ равны нулю, работа блоков 4 и 5 запрещается и формируется сигнал, аналогичный сигналу равенства блока 17 сравнения, который также разрешает только перезапись коодинат из регистра 2 в регистр 12, при этс. координаты в регистре 2 стираются, т. с. устройство работает аналогично рассмотренному ранее

ЛY, — ЛУ = YA — Yp„, y УА, прям,.линейному участку, однако без использования блоков 4 и 5 и блока 17 сравнения.

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

Перед началом ввода двухмерного проц..оса по входной шине 7 íà R-вход триг::-ра 18 и на один из входов блока 6 синхронизации поступает сигнал установки.

Триггер !8 устанавливается в нулевое состояние, причем сигнал с нулевого выхода триггера 18 поступает на элемет И 13 и на первый вход регистра 19 сдвига.

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

Одновременно с сигналом ввода по входной шине 11 на входы элемента И 13 и регистра 2 из устройства съема данных поступают координаты Х, Y начальной точки в цифровом параллельном коде. Сигнал с первого выхода (а) блока 6 синхронизации разрешает запись координат Х, Y в регистры 1, 2 и 12 через элемент И 13. Регистры 1, 2 и 12 построены таким образом, что при записи новой информации предыдущая информация стирается (например, на триггерах D-типа).

Сигнал (а) с первого выхода блока 6 про.изводит запись в первый разряд регистра 19 единицы.

Далее при поступлении со второго выхода (б) блока 6 сигнала на S-вход триггера 18 он устанавливается в единичное состояние и блокирует поступление координат Х, Y в регистры 1 и 12 через элемент И 13, а также прекращается поступление единичного сигнала на первый вход регистра 19.

Одновременно сигнал (б) со второго выхода блока 6 поступает на управляющие входы блоков 3 и 14, который дает разрешение на вход в, блоки 3 и 14 координат Х, Y

959129 начальной точки в параллельном двоичном коде из регистра 1, а также на ввод в блок

14 координаты начальной точки из регистра 12 и в блок 3 координаты начальной точки из регистра 2. Блоки 3 и 14 определяют разность координат, поступивших из регистров 1, 2 и 12. В данном начальном случае ЛХ„= ЛУ„= О, ЛХ = ЛУ,, = О, На первых и вторых выходах блоков 3 и 14 формируются сигналы, поступающие на входы элемента ИЛИ-НЕ 27, нулевой выходной сигнал которого блокирует через элемент И 16 прохождение разрешающего работу блоков 4 и 5 сигнала (в) третьего выхода блока 6. Одновременно сигналы

ЛХ„= О и ЛХ„= О с первых выходов блоков 14 и 3 соответственно поступают на 15 входы элемента И 22, а сигналы ЛУ„= О и

ЛЪ = О со вторых выходов блоков 14 и 3 соответственно поступают на входы элемента И 23, а сигналы совпадения с выходом элементов И 22 и 23 через элементы ИЛИ 24 и 25 и элемент задержки 26 поступают

20 на управляющий вход регистра 12, разрешая запись координат начальной точки из регистра 2 в регистр 12, при этом предыдущие координаты в регистре 12 автоматически стираются. 25

Следующий сигнал ввода по шине 8 поступает на первый вход блока 6, который вновь формирует сигнал (а), поступающий на второй вход элемента И 13 и управляющий вход регистра 2, разрешая запись координат следующей первой точки в регистр 2.

Кроме того, сигнал (а) первого выхода блока 6 поступает на второй вход двухразрядного регистра сдвига 19, устанавливая второй разряд регистра 19 в единичное состояние, а нулевой сигнал с нулевого выхода регистра сдвига 19 блокирует по первому входу элемент И 20.

По сигналу (б) второго выхода блока 6 в блоки 3 и 14 поступают координаты начальной и первой точек, причем блок 14 определяет разность координат А — А,, 40 а-блок 3 — А — А . При этом на первом и втором выходах блока 14 формируются сигналы, соответствующие значениям ЛХ„=

= ЛУ„= О, которые поступают на первый и второй входы элемента ИЛИ-НЕ 27. Нулевой выходной сигнал элемента ИЛИ-НЕ 27

45 блокирует элемент И 16, запрещая работу блоков 4 и 5, а единичный выходной сигнал элемента ИЛИ-НЕ 28 через элемент ИЛИ 29 поступает на элемент 30 задержки и через элемент ИЛИ 25 на элемент 26 задержки, а также поступает на элемент И 20, однако элемент И 20 заблокирован выходным сигналом регистра 19 сдвига, как уже говорилось выше. Время задержки элемента 26 больше, чем элемента 30 задержки, следовательно, выходной сигнал элемента 30 задержки по- 55 ступает на управляющий вход регистра 1 .и разрешает перезапись координат точки А о из регистра 12 в регистр 1, а затем выходной сигнал элемента 26 задержки поступает на управляющий вход регистра 12 и разрешает перезапись координат точки А 1 из регистра 2 в регистр 12.

Очередной сигнал ввода по шине 8 поступает на блок 6, который формирует сигнал на своем первом выходе, поступающий на управляющий вход регистра 2, разрешая запись координат очередной точки А<е, в регистр 2. Кроме того, сигнал (а) первого выхода блока 6 поступает на второй вход регистра 19 сдвига, устанавливая его в исходное состояние, при этом разблокирует элемент И 20.

По сигналу (б) второго выхода блока 6 в блок 14 поступают координаты точки А„;

А, а в блок 3 — точек А„ ; Аоо. Блок 14 определяет разность координат А„ — Ао,, а блок 3 — разность координат А — А (см. фиг. 1 и 2). Так как оба результата отличны от нуля, то на первых и вторых выходах блоков 3 и 14 формируются нулевые сигналы, при этом на выходе элемента ИЛИНЕ 27 формируется единичный сигнал, блокирующий элемент ИЛИ-HE 28, на выходе которого формируется нулевой сигнал и разблокирует элемент И 16, через который на блоки 4 и 5 поступает сигнал (в) третьего выхода блока 6, который разрешает ввод значений ЛХ„и ЛУ„с третьего выхода блока 14 в блок 5 и ЛХ и АУа с третьего выхода блока 3 в блок 4. Частные от делений 4- и поступают на входы блока 1! сравлл Хл лллХ нения, который по сигналу (г) четвертого выхода блока 6 производит сравнение кодовых комбинаций частных.

В данном случае результатом является сигнал равенства на первом выходе блока сравнения, поступающий на третий вход элемента ИЛИ 25 и через элемент 26 задержки на управляющий вход регистра 12, разрешая перезапись координат точки А из регистра 2 в регистр 12, при этом координаты точки А в регистре 12 автоматически стираются

Аналогично описанному производится анализ координат на отрезках (А 0, А ), (A3p A4p) ° (A4p А4 ) .

При поступлении в регистр 2 координат очередной точки А производится, как и ранее, определение разности в блоке 14 А„,-А4О, а в блоке 3 А4@ — Аао. При этом на вторых выходах блоков 3 и 14 формируются сигналы, поступающий на элемент ИЛИНЕ 27, выходной сигнал которого блокирует элемент И 16, запрещая тем самым работу блоков 4 и 5. Кроме того, сигналы со вторых выходов блоков 3 и 14 поступают на вход элемента И 23, выходной сигнал которого через элементы ИЛИ 24 и 25 и элемент 26 задержки поступает на управляющий вход регистра 12, разрешая перезапись координаты точки А4 из регистра 2 в регистр 12, при этом координаты точки А41 автоматичес959129

9, 5 0

30

45

Формула изобретения ки стираются. Аналогично устройство работает до поступления в регистр 2 координат точки Ае . Далее устройство работает, как описывалось выше.

При окончании ввода кривой из устройства съема по шине 21 поступает сигнал окончания съема, представляющий собой два последовательных импульса, причем первый сигнал через элемент ИЛИ 29 поступает на элемент И 20 и открывает группу ключей 9, разрешая вывод координаты точки

Ав1 в ЭВМ или блок обмена, затем с выхода элемента 30 задержки поступает на управляющий вход регистра 1, разрешая перезапись координат точки Аа; из регистра 12 в регистр 1. Второй сигнал окончания съема через элемент ИЛИ 29 поступает на выходную шину 10 и на элемент И 20, разрешая вывод координаты точки А в ЭВМ или в блок обмена.

Быстродействие таких устройств определяется средним временем, затрачиваемым на все операции, выполняемые для реализации критерия выборки, осуществляемого этими устройствами. Расчет этого времени (в тактах) для прототипа и для предложенного устройства, учитывая параллельность выполнения некоторых операций, а также коэффициент, согласно которому время на выполнения операций типа умножения (деления) в 5 раз больше, чем время выполнения операций типа сложения (вычитания), показывает, что предложенное устройство выполняет обработку одной точки за 8 тактов против- 19 у прототипа.

Кроме того, в предложенном устройстве третья операция, т. е. операция определения ахв- лх; . „ =- и <, не выполняется, если хотя бы одна из разностей (ЛХ; „, ЛУ; „,ЬХ;, hY„) равна нулю. В этом случае для обработки координаты одной точки требуется всего две операции, выполняемые за два такта.

Таким образом, быстродействие предложенного устройства в несколько раз выше, чем у прототипа, что позволяет производить сжатие информации непосредственно в реальном масштабе времени, а также использовать более быстродействующие устройства съема данных. Разница в аппаратурных затратах также видна из сопоставительного анализа количества производимых операций и их сложности.! блок синхронизации, соединенный с входными шинами, ключ, первым входом соединенный с выходом первого регистра, а выходом — с выходной шиной, отличающееся тем, что, с целью повышения быстродействия и упрощения устройства, в него введены третий регистр, блок анализа, второй блок вычитания, блок сравнения, триггер, регистр сдвига и элементы И, первый вход первого элемента И соединен с информационным входом устройства, а выход подключен к первым входам первого и третьего регистров, выход второго регистра подключен к второму входу третьего регистра, выход которого соединен с первым входом второго блока вычитания, к второму входу которого пЬдключен выход первого регистра, первый, второй третий и четвертый входы блока анализа соединены с первым и вторым выходами соответственно первого и второго блоков вычитания, третий выход второго блока вычитания подключен к первому входу второго арифметического блока, управляющие входы первого и второго арифметических блоков через второй элемент И подключены к первому выходу блока анализа, выходы первого и второго арифметических блоков соединены с первым и вторым входами блока сравнения, выходы которого соединены с пятым и шестым входами блока анализа, нулевой выход триггера соединен с вторым входом первого элемента И и с информационным входом регистра сдвига, выход которого соединен с первым входом третьего элемента И, выход которого подключен к второму входу ключа, второй, третий и четвертый выходы блока анализа соединены с управляющими входами третьего и первого регистров и с вторым входом третьего элемента И соответственно, седьмой вход блока анализа и R-вход триггера соединены с соответствующими входами устройства, первый выход блока синхронизации соединен с управляющим входом регистра сдвига, второго

40 регистра и с третьим входом первого элемента И, второй выход — с управляющими входами блоков вычитания и с S-входом триггера, третий выход — с вторым входом второго элемента И, четвертый выход с управляющим входом блока сравнения.

2. Устройство по п. 1, отличающееся тем, что блок анализа содержит элементы

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

55 чены к первому и второму входам блока анализа, выходы соединены с входами первого элемента ИЛИ, выход которого подключен к первому входу второго элемента

ИЛИ, выход которого через первый элемент задержки соединен с вторым выходом блока анализа, третий и четвертый входы блока анализа соединены с вторыми входами элементов И с третьим и четвертым входами первого и с,первым и вторым входами второ959129 (риг.!

tPue.2

Составитель В. Кунцевич

Техред И. Верес Корректор,Л. Бокшан

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

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

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

Филиал ППП «Патент», r. Ужгород, ул. Проектная, 4

Редактор М. Петрова

Заказ 6798/68 го элементов ИЛИ-НЕ, третий вход которого подключен к выходу первого элемента ИЛИНЕ и к первому выходу блока анализа, выход подключен к первому входу третьего элемента ИЛИ, второй и третий входы которого соединены соответственно с пятым и седьмым входами блока анализа, выход подключен к четвертому выходу блока анализа, к второму входу второго элемента

ИЛИ и через второго элемент задержки— к третьему выходу блока анализа, третий вход второго элемента ИЛИ соединен с шестым входом блока анализа.

Источники информации, принятые во внимание при экспертизе

1. Патент США № 3501750, кл, 340-172.2, 1962, 2. Авторское свидетельство СССР № 523438, кл. G 08 С 19/28, 1975 (прототип}.