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

Союз СоветскихСоциалистическихРеспублик ОПИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУОпубликовано 15.09.82, Бюллетень 34 нв делам изобретений н еткрмтийДата опубликования описания 15.09.82(72) Авторы изобретения Зенин и В. С. Да С.,Лакерннк. Мамедов,ститут технической кибернетики АН Белорусс аявительойства являетс ложность аппа деЬ 1=,Юу-са ащен у - у;, - прина 1-ом такте;текущая ординпредыдущая отекущее числов выборке; а процесса;дината процесса; агоь квантования Изобретение относится к приему, передаче и обработке нформации и может быть использовано в различных отраслях промышленности, где требуется обрабатывать большие информационные массивы.Известно устройство для обработки и сжатия информации, содержащее регистры текущей выборки и числа, сумматор, блок оперативной памяти, блок буферной памяти, счетчик заполнения, элемент сравнения и элементы И, ИЛИ 1.Недостатком такого устря низкое быстродействие и сратурной реализации.Наиболее близким по тенической сущности к предлагаемому является устройство для сокращения избыточности информации, содержащее первый регистр, второй регистр, вход которого является информационным входом устройства, первый блок вычитания, первым и вторым. входами соединенный с ыходами первого и второго регистров, выход первого блока вычитания соединен с первым арифметическим блоком, второй арифметический блок, блок синхронизации, соединенный с входными шинами, ключ, первым входом соединенный с выходом пер 2вого регистра, выходом - с выходной шиной, выход блока вычитания соединен через дешифратор и первый арифметический блок с вторым арифметическим блоком и выходным арифметическим блоком, выход которого подключен к второму входу ключа, второму арифметическому блоку и к второму входу счетчика, первый вход которого соединен с входом устройства, а выход подключен к второму входу дешифратора 2.Недостатками такого устройства являются сложность его аппаратурной реализции, а также ограниченность его использования для сжатия информации процессов с повышенной динамикой, т. е. низкое быстродействие. Это бъясняется тем, что данное устройство реализует критерий выборки в соответствии с выражением5 1 о б - допустимое значение линеййой аппроксимации;л - коэффициент, зависящий от точности аппроксимации.Реализация указанного критерия требует осуществления операций сложения, вычитания, деления, умножения и возведения в степень. Это приводит к значительным аппаратурным затратам. Обработка одного приращения в устройстве, как показано ниже в технико-экономическом обосновании, происходит за 19 тактов. Цель изобретения - повышение быстродействия и упрощение устройства,Поставленная цель достигается тем, что в устройство, содержащее первый регистр, второй регистр, вход которого является информационным входом устройства, первый блок вычитания, первым и вторым входами соединенный с выходами первого и второго регистров, выход первого блока вычитания соединен с первым арифметическим блоком, второй арифметический блок, блок синхронизации, соединенный с входными шинами, ключ, первым входом соединенный с выходом первого регистра, а выходом - с выходной шиной, дополнительно введены третий регистр, блок анализа, второй блок вычитания, блок сравнения, триггер, регистр сдвига и элементы И, первый вход первого элемента И соединен с информационным входом устройства, а выход подключен к первым входам первого и третьего регистров, выход второго регистра подключен к второму входу третьего регистра, выход которого соединен с первым входом второго блока вычитания, к второму входу которого подключен выход первого регистра, первый, второй, третий и четвертый входы блока анализа соединены с первым и вторым выходами соответственно первого и второго блоков вычитания, третий выход второго блока вычитания подключен к первому входу второго арифметического блока, управляющие входы первого и второго арифметических блоков через второй элемент И подключены к первому выходу блока анализа, выходы первого и второго арифметических блоков соединены с первым и вторым входами блока сравнения, выходы которого соединены с пятым и шестым входами блока анализа, нулевой выход триггера соединен с вторым входом первого элемента И и с информационным входом регистра сдвига, выход которого соединен с первым входом третьего элемента И, выход которого подключен к второму входу ключа, второй, третий и четвертый выходы блока анализа соединены с управляющими входами третьего и первого регистров и с вторым входом третьего элемента И соответственно, седьмой вход блока анализа и К-вход триггера соединены с соответствующими входами устройства, первый выход блока синхронизации 15 20 25 зо 35 40 45 50 55 соединен с управляющим входом регистрасдвига, второго регистра и с третьим входомпервого элемента И, второй выход - с управляющими входами блоков вычитания и сЬ-входом триггера, третий выход. - с вторымвходом второго элемента И, четвертый выход - с управляющим входом блока сравнения.Блок анализа содержит элементы ИЛИ,И, ИЛИ-НЕ и элементы задержки, первыевходы элементов И и первый и второй входыпервого элемента ИЛИ-НЕ подключенык первому и второму входам блока анализа,выходы соединены с входами первого элемента ИЛИ, выход которого подключен кпервому входу второго элемента ИЛИ, выход которого через первый элемент задержкисоединен с вторым выходом блока анализа,третий и четвертый входы блока анализасоединены с вторыми входами элементов Ис третьим и четвертым входами первого ис первым и вторым входами второго элемента ИЛИ-НЕ, третий вход которого подключен к выходу первого элемента ИЛИ-НЕи к первому выходу блока анализа, выходподключен к первому входу третьего элемента ИЛИ, второй и третий входы которогосоединены соответственно с пятым и седьмым входами блока анализа, выход подключен к четвертому выходу блока анализа,к второму входу второго элемента ИЛИи через второй элемент задержки - к третьему выходу блока анализа, третий вход второго элемента ИЛИ соединен с шестым входом блока анализа.На. фиг. 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задержки, элементы ИЛИ-НЕ 27 и 28, элемент ИЛИ 29 и элемент 30 задержки.Суть метода обработки информации,заложенного в предлагаемом устройстве,состоит в определении отношения - длякаждой точки двухмерного информационного массива, сравнения этого отношенияс соответствующим отношением для предыдущей точки с заданной точностью,т.е.для 1-й точки определяется отношение Мах,и сравнивается с отношением-, полученным для (1 - 1)-й точки,хсгде Л У 1 1 = У.1 - Уа , Л У = ; - Ъоа Х; Х; , У;,; Х, У - координатыначальной (или информативной), (1 - 1)-йи 1 - й точки соответственно.Иными словами, реализуется с заданнойточностью критерий выборки в соответствиис выражением При этом точность (или погрешность) сравнения задается оператором длиной разрядной сетки сравниваемых отношенийЯ 1-лДХ Ь Х;-л Устранение избыточности вводимой двухмерной информации осуществляется в реальном масштбе времени в процессе анализа текущих координат. При этом выявляются 15 Для анализа формы вводимой кривойв устройстве определяются элементарные приращения координат ЛХ, ЛУ каждой последующей точки относительно предыдущей, для чего координаты первой точки записываются в регистр 1, второй - в регистр 12, третьей - в регистр 2, при этом на блок 14 вычитания поступают координаты из регистров 1 и 12, а на блок 3 вычитания - из регистров 1 и 2. Блок 14 определяет разности ЛХ, и ЛУл, а блок 3 определяет разности ЛХ, и ЛУ Значения ЛХл и ЛУ, поступают зо 35 в арифметический блок 5, а значения ЛХ, и ЛУ поступают в арифметический блок 4, причем на выходе блока 5 получается частное ф, а на выходе блока 4 частное д 4 л-, 40д л. дал Полученные частные являются тангенсами углов наклона элементарных отрезков прямых или элементарными производными вводимой кривой. Сравнивая между собой значения дф и ддф, можно определить, лежат точки на одйой прямой или нет. При неравенстве частных дл и д" дается разрешениед Х Ыл.на вывод координат точки в ЭВМ, а также перезаписи координат первой точки в регистр 1, а второй точки в регистр 12, а при равенстве двух значений дается разрешение только на перезапись координат второй точки в регистр 12, при этом координаты первой точки стираются. В обоих случаях координаты последующей точки записываются в регистр 12. При обнаружении признака прямолинейного участка координаты каждой 55 последующей точки на этой прямой сопоставляются с координатами начальной точкиучастка, чем достигается высокая точность прямолинейные участки кривой. Точки перехода из криволинейного участка в прямолинейный и наоборот считываются характерными точками данной кривой. В процессе такой, обработки координаты характерных точек поступают на выход устройства для ввода в ЭВМ, а координаты точек, лежащих на прямолинейных участках вводимой кривой, на выход устройства не поступают и в ЭВМ не вводятся. 25 анализа и исключает,я ошибочное представление криволинейных участков с большим радиусом кривизны прямолинейными. При обнаружении криволинейного участка координать 1 каждой последующей точки на этой кривой анализируются с координатами каждой предыдущей точки, и при выполнении условия неравенства координаты предыдущей точки передаются в ЭВМ. При этом количество выводимых точек на единицу длины участка кривой зависит от кривизны участка и величины принятой координаты. При обнаружении участка прямой, параллельной оси координат, т, е. когда ЛХ или л 1 равны нулю, работа блоков 4 и 5 запрещается и формируется сигнал, аналогичный сигналу равенства блока 17 сравнения, который также разрешает только перезапись кос 1 динат из регистра 2 в регистр 12, при это: координаты в регистре 2 стираются, т. с. устройство работает аналогично рассмотренному ранее-Х - ь = ь - Ъд+ д прямлинейному участку, однако без использования блоков 4 и 5 и блока 17 сравнения. Устройство работает следующим образом Перед началом ввода двухмерного процоса по входной шине 7 на К-вход триг-ра 18 и на один из входов блока 6 синхронизации поступает сигнал установки. Триггер 8 устанавливается в нулевое состояние, причем сигнал с нулевого выхода триггера 18 поступает на элемет И 13 и на первый вход регистра 19 сдвига,При вводе первой и последующих точек по входной шине 8 на второй вход блока 6 синхронизации поступает сигнал ввода, при этом на выходах (а, б, в, г) блока 6 поочередно формируются тактовые импульсы. Одновременно с сигналом ввода по входной шине 11 на входы элемента И 13 и регистра 2 из устройства съема данных поступают координаты Х, Ъ начальной точки в цифровом параллельном коде. Сигнал с первого выхода (а) блока 6 синхронизации разрешает запись координат Х, У в регистры 1, 2 и 12 через элемент И 13. Регистры 1, 2 и 12 построены таким образом, что при записи новой информации предыдущая информация стирается (например, на триггерах Р-типа). Сигнал (а) с первого выхода блока 6 про.- изводит запись в первый разряд регистра 19 единицы.Далее при поступлении со второго выхода (б) блока 6 сигнала на 5-вход триггера 18 он устанавливается в единичное состояние и блокирует поступление координат Х, У в регистры 1 и 12 через элемент И 13, а также прекращается поступление единичного сигнала на первый вход регистра 19. Одновременно сигнал (б) со второго выхода блока 6 поступает на управляющие входы блоков 3 и 14, который дает разрешение на вход в, блоки 3 и 14 координат Х, Уначальной точки в параллельном двоичном коде из регистра 1, а также на ввод в блок 14 координаты начальной точки из регистра 12 и в блок 3 координаты начальной точки из регистра 2. Блоки 3 и 14 определяют разность координат, поступивших из регистров 1, 2 и 12. В данном начальном случае ЛХ= ЛУ= О, ЛХ = ЛУ = О, На первых и вторых выходах блоков 3 и 14 формируются сигналы, поступающие на входы элемента ИЛИ-НЕ 27, нулевой выходной сигнал которого блокирует через элемент И 16 прохождение разрешающего работу блоков 4 и 5 сигнала (в) третьего выхода блока 6. Одновременно сигналы ЛХ= О и ЛХ= 0 с первых выходов блоков 14 и 3 соответственно поступают на 15 входы элемента И 22, а сигналы ЛУ= 0 и ЛЪ = 0 со вторых выходов блоков 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 определяет разность координат А, - А Л 0 а-блок 3 - А - А . При этом на первом и втором выходах блока 14 формируются сигналы, соответствующие значениям ЛХ= = ЛУ = О, которые поступают на первый и второй входы элемента ИЛИ-НЕ 27. Нулевой выходной сигнал элемента ИЛИ-НЕ 2745 блокирует элемент И 16, запрещая работу блоков 4 и 5, а единичный выходной сигнал элемента ИЛИ-НЕ 28 через элемент ИЛИ 29 поступает на элемент 30 задержки и через элемент ИЛИ 25 на элемент 26 задержки, а также поступает на элемент И 20, однако элемент И 20 заблокирован выходным сигналом регистра 19 сдвига, как уже говорилось выше. Время задержки элемента 26 больше, чем элемента 30 задержки, следовательно, выходной сигнал элемента 30 задержки по ступает на управляющий вход регистра 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 формируется единичный сигнал, блокирующий элемент ИЛИ-НЕ 28, на выходе которого формируется нулевой сигнал и разблокирует элемент И 16, через который на блоки 4 и 5 поступает сигнал 1 в) третьего выхода блока 6, который разрешает ввод значений ЛХи ЛУс третьего выхода блока 14 в блок 5 и ЛХ и ЛУ с третьего выхода блока 3 в блок 4. Частные от делений л и фф поступают на входы блока 1 сравл хл сЪХнения, который по сигналу (г) четвертого выхода блока 6 производит сравнение кодовых комбинаций частных.В данном случае результатом является сигнал равенства на первом выходе блока сравнения, поступающий на третий вход элемента ИЛИ 25 и через элемент 26 задержки на управляющий вход регистра 12, разрешая перезапись координат точки А из регистра 2 в регистр 12, при этом координаты точки А в регистре 12 автоматически сти- раются Аналогично описанному производится анализ координат на отрезках (Ад 0, А ), (Азо, Ало) (А 40, Ал,),При поступлении в регистр 2 координат очередной точки А производится, как и ранее, определение разности в блоке 14 Ад, А 4, а в блоке 3 Аа - Ало. При этом на вторых выходах блоков 3 и 14 формируются сигналы, поступающий на элемент ИЛИНЕ 27, выходной сигнал которого блокирует элемент И 16, запрещая тем самым работу блоков 4 и 5. Кроме того, сигналы со вторых выходов блоков 3 и 14 поступают на вход элемента И 23, выходной сигнал которого через элементы ИЛИ 24 и 25 и элемент 26 задержки поступает на управляющий вход регистра 12, разрешая перезапись координаты точки Ала из регистра 2 в регистр 12, при этом координаты точки А 4 автоматичес959129 9,5 10 15 20 25 30 Э 5 45 Формула изобретения 50 55 ки стираются. Аналогично устройство работает до поступления в регистр 2 координатточки Аег. Далее устройство работает, какописывалось выше.При окончании ввода кривой из устройства съема по шине 21 поступает сигналокончания съема, представляющий собойдва последовательных импульса, причемпервый сигнал через элемент ИЛИ 29 поступает на элемент И 20 и открывает группуключей 9, разрешая вывод координаты точкиАв 1 в ЭВМ или блок обмена, затем с выходаэлемента 30 задержки поступает на управляющий вход регистра 1, разрешая перезапись координат точки Аа; из регистра 12в регистр 1. Второй сигнал окончания съемачерез элемент ИЛИ 29 поступает на выходную шину 10 и на элемент И 20, разрешаявывод координаты точки А в ЭВМ илив блок обмена,Быстродействие таких устройств определяется средним временем, затрачиваемымна все операции, выполняемые для реализации критерия выборки, осуществляемогоэтими устройствами. Расчет этого времени(в тактах) для прототипа и для предложенного устройства, учитывая параллельностьвыполнения некоторых операций, а такжекоэффициент, согласно которому время навыполнения операций типа умножения (деления) в 5 раз больше, чем время выполненияопераций типа сложения (вычитания), показывает, что предложенное устройство выполняет обработку одной точки за 8 тактовпротив 19 у прототипа.Кроме того, в предложенном устройстветретья операция, т. е. операция определенияйХВ 1 ДХ; .ф и ф, не выполняется, если хотя бы однаиз разностей (ЛХ; , ЛУ; ,Ь)1;, ЬУ) равнанулю. В этом случае для обработки координаты одной точки требуется всего две операции, выполняемые за два такта.Таким образом, быстродействие предложенного устройства в несколько раз выше,чем у прототипа, что позволяет производитьсжатие информации непосредственно в реальном масштабе времени, а также использовать более быстродействующие устройствасъема данных. Разница в аппаратурныхзатратах также видна из сопоставительногоанализа количества производимых операцийи их сложности. 1. Устройство для сокращения избыточности информации, содержащее первый регистр, второй регистр, вход которого является информационным входом устройства, первый блок вычитания, первым и вторым входами соединенный с выходами первого и второго регистров, выход первого блока вычитания соединен с первым арифметическим блоком, второй арифметический блок,блок синхронизации, соединенный с входными шинами, ключ, первым входом соединенный с выходом первого регистра, а выходом - с выходной шиной, отличающееся тем, что, с целью повышения быстродействия и упрощения устройства, в него введены третий регистр, блок анализа, второй блок вычитания, блок сравнения, триггер, регистр сдвига и элементы И, первый вход первого элемента И соединен с информационным входом устройства, а выход подключен к первым входам первого и третьего регистров, выход второго регистра подключен к второму входу третьего регистра, выход которого соединен с первым входом второго блока вычитания, к второму входу которого пЬдключен выход первого регистра, первый, второй третий и четвертый входы блока анализа соединены с первым и вторым выходами соответственно первого и второго блоков вычитания, третий выход второго блока вычитания подключен к первому входу второго арифметического блока, управляющие входы первого и второго арифметических блоков через второй элементИ подключены к первому выходу блока анализа, выходы первого и второго арифметических блоков соединены с первым и вторым входами блока сравнения, выходы которого соединены с пятым и шестым входами блока анализа, нулевой выход триггера соединен с вторым входом первого элемента И и с информационным входом регистра сдвига, выход которого соединен с первым входом третьего элемента И, выход которого подключен к второму входу ключа, второй, третий и четвертый выходы блока анализа соединены с управляющими входами третьего и первого регистров и с вторым входом третьего элемента И соответственно, седьмой вход блока анализа и К-вход триггера соединены с соответствующими входами устройства, первый выход блока синхронизации соединен с управляющим входом регистра сдвига, второго 40регистра и с третьим входом первого элемента И, второй выход - с управляющими входами блоков вычитания и с Я-входом триггера, третий выход - с вторым входом второго элемента И, четвертый выход с управляющим входом блока сравнения. 2. Устройство по п, 1, отличающееся тем, что блок анализа содержит элементы ИЛИ, И, ИЛИ-НЕ и элементы задержки, первые входы элементов И и первый и второй входы первого элемента ИЛИ-НЕ подключены к первому и второму входам блока анализа, выходы соединены с входами первого элемента ИЛИ, выход которого подключен к первому входу второго элемента ИЛИ, выход которого через первый элемент задержки соединен с вторым выходом блока анализа, третий и четвертый входы блока анализа соединены с вторыми входами элементов И с третьим и четвертым входами первого и с,первым и вторым входами второ(Риг. Составитель В.Техред И. Верес Тираж 642 ПИ Государственного к о делам изобретений и Москва, Ж - 36, Раушс ПП Патент, г. Ужгоро едактор М. Петроваказ 6798/68ВНИ р,Л. Бокшаное 113035,филиал П я, 4 го элементов ИЛИ-НЕ, третий вход которого подключен к выходу первого элемента ИЛИНЕ и к первому выходу блока анализа, выход подключен к первому входу третьего элемента ИЛИ, второй и третий входы которого соединены соответственно с пятым и седьмым входами блока анализа, выход подключен к четвертому выходу блока анализа, к второму входу второго элемента ИЛИ и через второго элемент задержки -к третьему выходу блока анализа, третийвход второго элемента ИЛИ соединен с шестым входом блока анализа.Источники информации,принятые во внимание при экспертизе1, Патент США3501750, кл, 340-172.2,1962,2, Авторское свидетельство СССР523438, кл. б 08 С 19/28, 1975 (прототип),КунцевйчКорректо Поднисиомнтета СССРоткрытийкая наб., д. 4 д ул Проектна