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

Изобретение относится к области приема, передачи и обработки информации и может быть использовано в различных системах обработки больши информационных массивов. Известно устройство для сокращения избыточности информации, содержащее регистр текущей выборки, выхо которого соединен со входом регистра памяти выборки, первым входом блока вычитания и через второй ариф метический блок с первым арифметическИм блоком, выход регистра памяти соединен с вторым входом блока в читания и первым входом электронног ключа, выход блока вычитания соедине через дешифратор и первый арифмети ес1 ий блок с вторым арифметическим блоком, выход которого подключен к второму входу электронного клгча, второму арифметическому блоку и к второму входу счетчика, первый вход которого соединен с входом устройства, а выход подключен ко второму входу дешифратора tl3. Недостатками такого устройства являются сложность его аппаратурной реализации, а также ограниченность его использования для сжатия информации процессов с повышенной динами кой, т.е. .низкое быстродействие. Наиболее близким по технической сущности к изобретению является уст ройство для сокршдения избыточности информации, содержащее первый регистр, второй регистр, вход которого является информационным входом устройства, первый блок вычитания, первым и вторым входами соединенный с выходами первого и второго регист ров, выход первого блока вычитания соединен с первым арифметическим бло ком, второй арифметический блок, (Збло синхронизации, соединенный с входными шинами, ключ, первым входом соеди ненный с выходом первого регистра, а выходом - с выходной шиной, выход первого элемента И подключен к первым входам первого и третьего регист ров, выход второго регистра подключен к второму входу третьего регистра, выход которого соединен с первым входом второго блока вычитания, к второму входу которого подключен выход первого регистра, первый, второй третий и четвертый входы блока анали за соединены с первым и вторым Bjgxoдами соответственно первого и второго блоков вычитания, третий выход второго блока вычитания подключен к первому входу второго арифметического блока, управляющие входы первого и второго арифметических блоков через второй элемент И подключены к первому выходу блока анализа, выходы первого и второго арифметических бло ков соединены с первым и вторым входами блока сравнения, выходы которого соединены с пятым и шестым входами блока анализа, нулевой выход триггера соединен с вторым входом первого элемента И и с информационным входом регистра сдвига, выход которого соединен с первым входом третьего элемента И, выход которого подключен ко второму входу ключа, второй, третий и четвертый выходы блока анализа соединены с управляюгцими входами третьего и первого регистров и со вторым входом третьего элемента И соответственно, седьмой вход блока анализа и R-вход триггера соединены с соотведствующими входами устройства, первый выход блока синхронизации соединен с управляющим входом регистра сдвига, второго регистра и с третьим входом первого элемента И, второй выход - с управляющими входами блоков вычитания и с S-входом триггера, третий выход - с вторым входом второго элемента И, четвертый выход - с управляющим входом блока сравнения Сз.. Недостатком такого устройства является то, что при обработке начальных (трех) точек кривой производятся дополнительные затраты времени на вычисление ЛХ и . и их отношений. Для блокировки - в арифметических блоках вычислений запрещенных комбинаций деления (например, знаменатель дроби равен нулю) требуются дополнительные аппаратурные затраты. Кроме того, структура арифметичёского блока, выполняющего операцию деления в известном устройстве, сложнее структуры арифметического блока, выполняющего операцию умножения. Целью изобретения является упроЩение устройства, Поставленная цель достигается тем, что в устройство, содержащее блок синхронизации, элементы И, триггер, вычитатели, ключ, умножители, блок сравнения, элементы задержки, элементы ИЛИ, регистры, выход первого регистра подключен к первым входам второго регистра и первого вычйтателя, выход второго регистра подключен к первым входам третьего регистра и второго вычйтателя, выход третьего регистра подключен к первому входу ключа и вторым входам первого и второго вычитателей, первый выход ijepBoго вычйтателя подключен к первому входу первого, умножителя, выход которого подключен к первому входу блока сравнения, первый выход второго вычйтателя подключен к первому входу второго умножителя, выход которого подключен к второму входу блока сравнения, первый выход которого подключен к первому входу первого элемента ИЛИ, второй вход которого является первым управляющим входом устройства, вйход первого элементна ИЛИ подключен к второму входу ключа и первому входу второго элемента ИЛИ и через первый элемент задержки пбдключен к второму входу третьего регистра, второй выход блока сравнения подключен к второму входу второго элемента ИЛИ, выход которого через второй элемент задержки подключен к второму входу второго регистра, первый вход блока синхронизации объединен с первым входом триггера и является вторым управляющим входом устройства, второй вход блока синхронизации является третьим управляющим входом устройства, первый, второй и третий выходы блока синхронизации подключены соответственно к синхронизирующим входам первого и второго вычитателей, первого и второго умножителей и блока сравнения, введен распределитель импульсов, пер вый и второй входа которого подключе ны соответственно к второму и третьему управляющим входам устройства, первый выход распределителя импульсов подключен к первому входу первого элемента И, выход которого подклю чен к третьему входу третьего регист ра,- второй выход распределителя импульсов подключен к первому входу второго элемента И, выход которого подключен к третьему входу второго регистра, третий выход распределителя импульсов подключен к второму входу триггера, выход которого подключен к первому входу третьего элемента И и третьему входу блока синхронизации, выход третьего элемента И подключен к первому входу первого регистра, вторые входы первого, второго и третьего элемента И объединены и являются информационным входом устройства, четвертый выход блока синхронизации подключен к третьему входу третьего элемента И, второй выход второго вычитателя подключен к второму входу второго умножителя, второй, выход первого вычитателя подключей к второму входу первого умножителя . На фиг. 1 приведена схема устройства} на фиг.. 2 - кривая для поясне ния принципа сокращения избыточности Устройство содержит регистры 1-3, вычитатели 4 и 5, умножители б и 7, блок 8 сравнения, элементы ИЛИ 9 и 1 элементы 11 и 12 задержки, ключ 13, распределитель 14 импульсов, элементы И 15-17, триггер 18, блок 19 синхронизации информационный вход 20, управляющие входы 21-23, выходную ши ну 24. Суть методаобработки информации, заложенного в предлагаемом устройств состоит в определении лх,- , Л для каждой точки двухмерного информационного массива, определении произведений Дх, лу.., и Ax;.|-dVj И сравнения этих произведений с заданной точностью, где 4 X. X. .X дх. х.-х„ 1-1 1-1 1 1 о Л. : V - у 4V.., 1-1 1-1 о где Хд , -jg , . , v , Xj., , V,-..,- кооринаты начальной (или информативной), i-ой и (1-1)-ой точки соответственно . Иными словами, реализуется с заанной точностью критерий выборки в соответствии с выражением 4x.-d,.,dx.,.d., . При этом точность (или погрешность) сравнения задается оператором длиной разрядной сетки сравниваемых произведений лх. ., , ДХ:-1- У Устранение избыточности вводимой двухмерной информации осуществляется в реальном масштабе времени в процессе анализа текущих координат. При этом выявляются прямолинейные участки кривой. Точки перехода из криволинейного участка в прямолинейный и наоборот считываются характерными точками данной кривой. В про- цессе такой обработки координаты характерных точек поступают на выход устройства для ввода в ЭВМ, а координаты точек, лежащих на прямолинейных участках вводимой кривой, не выход устройства не поступают и в ЭВМ не вводятся. Для анализа формы вводимой кривой в устройстве определяются элементарные приращения координат х и у каждой последующей точки относительно предыдущей, для чего координаты первой точки (А00) записываются в регистр 1, второй точки (А р) в регистр 3, третьей точки (AQJ) - в регистр 2, при этом на вычитатепь 5 поступают координаты из регистров 1 и 3, а на вычитатель 4 из регистров 1 и 2. адчитатель 5 определяет разность Ах х. - Хж н Дз у; - 01 00 - д , а вычитатель 4 определяет разности лх- Хд - А J й 2 floi ЛоО А - л 02 Значения лх., и 4 поступают jB умножитель 7, а значения лх и Ai поступают в умножитель 6, причем на выходе умножителя 7 получается произведение , а на выходе умно- . жителя 6 - произведение &т(-л4 . Сравнивая между собой значения лх., 4Y.j и Xg-J.,, можно определить, лежат точки А Q, А , А э одной прямой или нет. При неравенстве произведений . дается разрешение на вывод координат точки в ЭВМ, а также перезаписи координат точки А,О1 в регистр 1, а точки в регистр 3, при этом координаты точки Ар стирвются. При обнару жении признака прямолинейного участ ка координаты каждой последующей точ иИ на этой кривой сопоставляются с координатами начальной точки участк Лдд, им достигается высокая точност анализа и исключается ошибочное пред ставление криволинейных участков с большим радиусом кривизны прямолине ными. При обнаружении криволинейного участка координаты- каждой последующей точки на этой кривой анализиру ются с координатами каждой предьщущей точки, и при выполнении условия неравенства координаты предыдущей точки передаются в ЭВМ. При этом количество выводимых то чек на единицу длины участка кривой зависит от кривизны участка и величи ны координаты. Устройство работает следующим образом. Перед началом ввода двухмерного массива сигналом, поступающим по шине 21, устанавливается в нулевое состояние триггер 18, блок 19 синхронизации и распределитель 14 импульсо состоящий из последовательно соединенных элемента И, двухразрядного счетчика и дешифратора, причем выходы счетчика через элемент И-НЕподключены к одному из входов элемента И (не указаны). Нулевым сигналом с един1л-т1ного выхода триггера 18 элемен И 17 и блок 19 блокируются. При вводе первой точки по входной шине 22 на вход элемента И распределителя 14 импульсов поступает сигнал ввода, при этом по сигналу с перщого .выхода распределителя 14 через элемент,И 15 в регистр 1 записываются координаты X, У точки AQQ, поступающие одновременно с сигналом ввода по шине 20 из устройства съема данных в цифровом параллельном коде. При вводе следующей точки сигнал на первом выходе распределителя 14 снимается, чем блокируется элемент И 15 а сигналом с второго выхода распределителя 14 разрешается запись координат точки А,д через элемент И 16 в регистр 3. .. Третий сигнал ввода, поступающий по шине 22 на вход распределителя 14 импульсов, формирует сигнал на третьем выходераспределителя 14, который поступает на S-вход триггера 15 и устанавливает его в единич ное состояние. Сигнал с единичного выхода триггера 18 поступает на вход элемента И 17 и блока 19 синхронизации, при этом на выходах блока 19 поочередно формируются тактовые импульсы. По сигналу с первого выхода блЬка 19 синхронизации через элемент И 17 в регистр .2 записываются коорди наты точки АО- поступающие по шине 20. Далее по сигналу я с второго выхода блока 19 синхронизации, поступающему на управляющие входы вычитателей 4 и 5, разрешается ввод координат точек , А j, и , вычитатели 5 и 4 соответственно, при этом вычитатель 5 определяет разность координат Ад;,-Ад(,, а вычитатель 4 . При этом на первом и втором выходах вычитателей 5 и 4 формируются сигналы, соответствующие значениям дх , 4V и дд. , ijj п ал 2 которые поступают на входы умножителей 7 и 6, где по сигналу б с третьего выхода блока 19, синхронизации определяются значения произведений Лх,,ЛУ и 4X2 AV . Результаты вычислений в умножителях- 7 и б- поступают в блок 8 сравнения, где по сигналу 8 с четвертого выхода блока 19 синхронизации они сравниваются. В данном случае результатом является сигнаш неравенства, который через элемент .ИЛИ 9 поступает в ключ 13, тем самым разрешая -задачу координат точки Ад, находящейся в регистре 1, в ЭВМ. Далее этот же сигнал, пройдя элемент 11 задержки, разрешает перезапись координат точки А;, из регистра 3 в регистр 1. Кроме того, сигнал неравенства с элемента ИЛИ 9 поступает через элемент ИЛИ 10 и элемент 12 задержки, время задержки которого больше, чем элемента 11 задержки, в регистр 3, чем разрешает перезапись координат точки A.j из регистра 2 в регистр 3, при этом координаты точки Аoi в регистре 3 автоматически стираются. По очередному сигналу ввода, п6ступающему по шине 22, запускается только блок 19 синхронизации (так как для запуска распределителя 14 импульсов необходимо повторное появление сигнала на шине 21, т.е. сигнала начала кривой), при этом по сигналу с первого выхода блока 19 синхронизации в регистр 2 через элемент И 17 записываются координаты точки поступающей по шине 20. Дальнейшая обработка введенной координаты точки A,(,j производится аналогична вышеописанному. Аналогичные операции производятся до поступления из устройства съема координат точки А . (табл.). в этом случае произведения 4х.( и 4X5 равны. Сигнал равенства с второго выхода блока 8 сравнения через элемент ИЛИ 10 и элемент 12 задержки поступает на управляющий вход регистра 3 и разрешает, таким образом, перезапись координаты точки А,, из регистра 2 в регистр 3. В следующем цикле в регистр 2 вводятся координаты точки А J2, как и ранее производятся определения

разностей в блоке Ь Л,,--Л,,, в блоке 4 А пьоизведеяия

и ах . а

, ,

Далее производится сравнение произведений. В этом случае на выходе блока 8 сравнения появляется сигнал неравенства, который через элемент ИЛИ 9 разрешает вьодачу в ЭВМ координаты точки Аод из регистра, через элемент 11 задержки разрешает перезапись координаты точки А из регистра 3 в регистр 1, и через элемент ИЛИ 10 и элемент 12 задержки разрешает перезапись координаты точки А-,2 из регистра 2 в регистр 3.

Далее устройство работает, как описывалось выше.

При окончании ввода кривой из устройства съема по шине 23 поступает сигнал окончания съема, представля(ощий собой два последовательных импульса, причем первый импульс через элемент ИЛИ 9 поступает на ключ 13, разрешая выход координаты А50 в ЭВМ, затем с выхода элемента 11 задер(ски поступает на управляющий вход регистра 1, разрешая перезапись координат точки А 55 из регистра 3 в регистр 1. Второй импульс окончания cteMa через элемент ИЛИ 9 разрешает

выдачу в ЭВМ через ключ 13 содержимое регистра 1, т.е. координаты точки А jy.

Процесс анализа вводимой кривой (фиг. 2), а также результаты записи,

перезаписи, вычитания и сравнения координат точек приведены в таблице.

д -д

д -д

02 00.

01 ОО

02 03

Д -д

24 2г 25 23

25 2.4

А -А 27 iJ

28 2.Ь 21 Л5 U -Д 28 11

29 27

А29-А

1-.8

-А

30

26

д - д

-А 32

30

Ь2

А

02

00

0-1

02

03

01

10

08

09

А

09

11

08

Ч-1

09

Л24

23

25 2

24

2b 25

27

24 Aj-,

25

28

28

А

27

2Э

30

ге

30

3-(

АЗ,

io

22

А 32

и

33

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

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

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