Устройство для сокращения избыточности информации Советский патент 1982 года по МПК G08C19/28 

(54) УСТРОЙСТВО ДЛЯ СОКРАЩЕНИЯ ИЗБЫТОЧНОСТИ

ИНФОРМАЦИИ

1

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

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

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

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

Ai-t

б.

гдеД1 -прирашение процесса

на i-OM такте;

1 -текуш,ая ордината процесса; Y - предыдушая ордината процесса; i - текущее число шагов квантования в выборке;

б - допустимое значение линейной аппроксимации;

л - коэффициент, зависящий от точности аппроксимации.

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

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

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

соединен с управляющим входом регистра сдвига, второго регистра и с третьим входом первого элемента И, второй выход - с управляющими входами блоков вычитания и с 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 задержки, элементы ИЛИ-НЕ 27 и 28, элемент ИЛИ 29 и элемент 30 задержки.

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

где Д Y.i Y., - Yo; 1 Yi Yt - YO ;

ДХ., X,.,-Х„;ЛХ1 Х -Х„; a Х„, X ; Xu, , Y;.., ; Xj, Y - координатыначальной (или информативной), (i - 1)-й и i-и точки соответственно.

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

4м 4yi Д/м

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

А. ЛХ, Л X;-i

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

Для анализа формы вводимой кривой в устройстве определяются элементарные приращения координат АХ, AY каждой последующей точки относительно предыдущей, для чего координаты первой точки записываются в регистр 1, второй - в регистр 12, третьей - в регистр 2, при этом на блок 14 вычитания поступают координаты из регист ров 1 и 12, а на блок 3 вычитания - из регистров 1 и 2. Блок 14 определяет разности АХ., и AY,, а блок 3 определяет разности AXj и АУ. Значения АХ и АУ поступаюФ в арифметический блок 5, а значения АХ и АУг поступают в арифметический блок 4, причем на выходе блока 5 получается частное , а на выходе блока 4 частное ..

-, сЛ At,ija

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

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

J м 2, Аоо lAoi Ь I Авч .олинейному участку, однако без использования блоков 4 и 5 и блока 17 сравнения.

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

Перед началом ввода двухмерного процесса по входной шине 7 на R-вход триггера 18 и на один из входов блока 6 синхронизации поступает сигнал установки. Триггер 18 устанавливается в нулевое состояние, причем сигнал с нулевого выхода триггера 18 поступает на элемет И 13 и на первый вход регистра 19 сдвига.

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

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

начальной точки в параллельном двоичном коде из регистра 1, а также на ввод в блок 14 координаты начальной точки из регистра 12 и в блок 3 координаты начальной точки из регистра 2. Блоки 3 и 14 определяют разность координат, поступивших из регистров 1, 2 и 12. В данном начальном случае АХ,, AY О, АХ, - AY. 0. На первых и вторых выходах блоков 3 и 14 формируются сигналы, поступающие на входы элемента ИЛИ-НЕ 27, нулевой выходной сигнал которого блокирует через элемент И 16 прохождение разрешающего работу блоков 4 и 5 сигнала (в) третьего выхода блока 6. Одновременно сигналы ДХ,, 0и AXj, Oc первых выходов блоков 14 и 3 соответственно поступают на входы элемента И 22, а сигналы AY О и AYg О со вторых выходов блоков 14 и 3 соответственно поступают на входы элемента И 23, а сигналы совпадения с выходом элементов И 22 и 23 через элементы ИЛИ 24 и 25 и элемент задержки 26 поступают на управляющий вход регистра 12, разрешая запись координат начальной точки из регистра 2 в регистр 12, при этом предыдущие координаты в регистре 12 автоматически стираются.

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

По сигналу (б) второго выхода блока 6 в блоки 3 и 14 поступают координаты начальной и первой точек, причем блок 14 определяет разность координат , а-блок 3 - АО |-АОО. При этом на первом и втором выходах блока 14 формируются сигналы, соответствующие значениям AX AYy, 0, которые поступают на первый и второй входы элемента ИЛИ-НЕ 27. Нулевой выходной сигнал элемента ИЛИ-НЕ 27 блокирует элемент И 16, запрещая работу блоков 4 и 5, а единичный выходной сигнал элемента ИЛИ-НЕ 28 через элемент ИЛИ 29 поступает на элемент 30 задержки и через элемент ИЛИ 25 на элемент 26 задержки, а также поступает на элемент И 20, однако элемент И 20 заблокирован выходным сигналом регистра 19 сдвига, как уже говорилось выше. Время задержки элемента 26 больше, чем элемента 30 задержки, следовательно, выходной сигнал элемента 30 задержки поступает на управляющий вход регистра 1 .и разрешает перезапись координат точки Аоо из регистра 12 в регистр 1, а затем выходной

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

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

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

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

Аналогично описанному производится анализ координат на отрезках ( AJQ), (A(j; A4o)i (А4о; Ад).

При поступлении в регистр 2 координат очередной точки Ai,2, производится, как и ранее, определение разности в блоке 14 Ад, , а в блоке 3 Аад.-Азд. При этом на вторых выходах блоков 3 и 14 формируются сигналы, поступающий на элемент ИЛИНЕ 27, выходной сигнал которого блокирует элемент И 16, запрещая тем самым работу блоков 4 и 5. Кроме того, сигналы со вторых выходов блоков 3 и 14 поступают на вход элемента И 23, выходной сигнал которого через элементы ИЛИ 24 и 25 и элемент 26 задержки поступает на управляющий вход регистра 12, разрешая перезапись координаты точки Ада из регистра 2 в регистр 12, при этом координаты точки A4i автоматически стираются. Аналогично устройство работает до поступления в регистр 2 координат точки Азг- Далее устройство работает, как описывалось выше. При окончании ввода кривой из устройства съема по шине 21 поступает сигнал окончания съема, представляющий собой два последовательных импульса, причем первый сигнал через элемент ИЛИ 29 поступает на элемент И 20 и открывает группу ключей 9, разрешая вывод координаты точки Ав-1 в ЭВМ или блок обмена, затем с выхода элемента 30 задержки поступает на управляющий вход регистра 1, разрешая перезапись координат точки . из регистра 12 в регистр 1. Второй сигнал окончания съема через элемент ИЛИ 29 поступает на выходную шину 10 и на элемент И 20, разрешая вывод координаты точки в ЭВМ или в блок обмена. Быстродействие таких устройств определяется средним временем, затрачиваемым на все операции, выполняемые для реализации критерия выборки, осуществляемого этими устройствами. Расчет этого времени (в тактах) для прототипа и для предложенного устройства, учитывая параллельность выполнения некоторых операций, а также коэффициент, согласно которому время на выполнения операций типа умножения (деления) в 5 раз больше, чем время выполнения операций типа сложения (вычитания), показывает, что предложенное устройство выполняет обработку одной точки за 8 тактов против- 19 у прототипа. Кроме того, в предложенном устройстве третья операция, т. е. операция определения д(м выполняется, если хотя бы одна из разностей (AXi-, AYi--, ,ЛХ;, АУц) равна нулю. В этом случае для обработки координаты одной точки требуется всего две операции, выполняемые за два такта. Таким образом, быстродействие предложенного устройства в несколько раз выше, чем у прототипа, что позволяет производить сжатие информации непосредственно в реальном масштабе времени, а также использовать более быстродействующие устройства съема данных. Разница в аппаратурных затратах также видна из сопоставительного анализа количества производимых операций и нх сложности. Формула изобретения 1. Устройство для сокращения избыточности информации, содержащее первый регистр, второй регистр, вход которого является информационным входом устройства, первый блок вычитания, первым и вторым входами соединенный с выходами первого и второго регистров, выход первого блока вычитания соединен с первым арифметичесКИМ блоком, второй арифметический блок, блок синхронизации, соединенный с входными шинами, ключ, первым входом соеди ненный с выходом первого регистра, а выходом - с выходной шиной, отличающееся тем, что, с целью повышения быстродействия и упрощения устройства, в него введены третий регистр, блок анализа, второй блок вычитания, блок сравнения, триггер, регистр сдвига и элементы И, первый вход первого элемента И соединен с информационным входом устройства, а выход подключен к первым входам первого и третьего регистров, выход второго регистра подключен к второму входу третьего регистра, выход которого соединен с первым входом второго блока вычитания, к второму входу которого пЬдключен выход первого регистра, первый, второй третий и четвертый входы блока анализа соединены с первым и вторым выходами соответственно первого и второго блоков вычитания, третий выход второго блока вычитания подключен к первому входу второго арифметического блока, управляющие входы первого и второго арифметических блоков через второй элемент И подключены к первому выходу блока анализа, выходы первого и второго арифметических блоков соединень с первым и вторым входами блока сравнения, выходы которого соединены с пятым и шестым входами блока анализа, нулевой выход триггера соединен с вторым входом первого элемента И и с информационным входом регистра сдвига, выход которого соединен с первым входом третьего элемента И, выход которого подключен к второму входу ключа, второй, третий и четвертый выходы блока анализа соединены с управляющими входами третьего и первого регистров и с вторым входом третьего элемента И соответственно, седьмой вход блока анализа и R-вход триггера соединены с соответствующими входами устройства, первый выход блока синхронизации соединен с управляющим входом регистра сдвига, второго регистра и с третьим входом первого элемента И, второй выход - с управляющими входами блоков вычитания и с S-входом триггера, третий выход - с вторым входом второго элемента И, четвертый выход - с управляющим входом блока сравнения. 2. Устройство по п. 1, отличающееся тем, что блок анализа содержит элементы ИЛИ, И, ИЛИ-НЕ и элементы задержки, первые входы Элементов И и первый и второй входы первого элемента ИЛИ-НЕ подключены к первому и второму входам блока анализа, выходы соединены с входами первого элемента ИЛИ, выход которого подключен к первому входу второго элемента ИЛИ, выход которого через первый элемент задержки соединен с вторым выходом блока анализа, третий и четвертый входы блока анализа соединены с вторыми входами элементов И с третьим и четвертым входами первого и с первым и вторым входами второ