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

 

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

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

ГЕСПУБЛИН

„„SU„„10752

ЗАД G 08 С 19/28

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3527858/18-24 (22) 27.12.82 (46) 23.02.84. Бюл. Р 7 (72) A. Г. Мамедов, А.С. Лакерник и И. П. Кудерко (71) Институт технической кибернеФ3ц<и AH Белорусской ССР (53) 621.398(088.8) (56) 1. Авторское свидетельство СССР

М 523438, кл. G 08 С 19/28, 1975.

2. Авторское свидетельство СССР

Р 959129, кл. G 08 С 19/28, 1980 (прототип). (54)(57) УСТРОИСТВО ДЛЯ СОКРАЩЕНИЯ

ИЗБЫТОЧНОСТИ ИНФОРМАЦИИ, содержащее блок синхронизации, элементы И, триггер, вычитатели, ключ, умножители, блок сравнения, элементы задержки, элементы ИЛИ, регистры, выход первого регистра подключен к первым входам второго регистра и первого вычитателя, выход второго регистра подключен к первым входам третьего регистра и второго Вычитателя, выход третьего регистра подключен к первому вхо; ду ключа и вторым входам первого и второго вычитателей, первый выход первого вычитателя подключен к первому входу первого умножителя, выход которого подключен к первому входу блока сравнения, первый выход второго вычитателя подключен к первому входу второго умножителя, выход которого подключен к второму входу блока сравнения, первый выход которого подключен к первому входу первого элемента ИЛИ, второй вход которого является первым управляющим входом устройства, выход первого элемента

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

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

1075289

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

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

6JlOKOM BbIXOQ KOTOPOI"O BO+KJIIOMPII к второму входу электронного клгча, второму арифметическому блоку и к второму входу счетчика, первый вход которого соединен с входом устройства, а выход подключен ко второму входу дешифратора (,1 3.

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

Наиболее близким по технической сущности к изобретению является устройство для сокращения избыточности информации, содержащее первый регистр, второй регистр, вход которого является информационным входом 35 устройства, первый блок вычитания, первым и вторым входами соединенный с выходами первого и второго регистров,i выход первого блока Вычитания соединен с первым арифметическим бло-40 ком, второй арифметический блок, блок синхронизации, соединенный с входными шинами, ключ, первым входом соединенный с выходом первого регистра, а ВыхОдОм с ВыхОднОЙ шинОЙ ВыхОд 45 первого элемента И подключен к первым входам первого и третьего регистров, выход второго регистра подключен к второму входу третьего регистра, выход которого соединен с первым входом второго блока вычитания, к второму входу которого подключен выход первого регистра, первый, второй, третий и четвертый входы блока анализа соединены с первым и вторым в@ходами соответственно первого и второго блоков вычитания, третий выход второго блока вычитания подключен к первому Входу второго арифметического блока, управляЮщие входы первого и второго арифметических блоков че- 60 рез второй элемент И подключены к первому выходу блока анализа, выходы первого и второго арифметических блоков соединены с первым и вторым входами блока сравнения, выходы которо- 65 го соединены с пятым и шестым входами блока анализа, нулевой выход триггера соединен с вторым входом первого элемента И и с информационным входом регистра сдвига, выход которого соединен с первым входом третьего элемента И, выход которого подключен ко второму входу ключа, второй, третий и четвертый выходы блока анализа соединены с управляющими входами третьего и первого регистров и со вторым входометретьего элемента И соответственно, седьмой вход блока анализа и R-вход триггера соединены с соответствующими входами устройства, первый выход блока синхронизации соединен с управляющим входом регистра сдвига, второго регистра и с третьим входом первого элемента И, второй выход — с управляющими входами блоков вычитания и с $-входом триггера, третий выход - с вторым входом второго элемента И, четвертый выход — с управляющим входом блока сравнения 23..

Недостатком такого устройства является то, что при обработке начальных (трех) точек кривой производятся дополнительные затраты времени на вычисление 5X и 5g. и их от1 1 ношений. Для блокировки в арифметических блоках вычислений запрещенных комбинаций деления (например, знаменатель дроби равен нулю) требуются дополнительные аппаратурные затраты.

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

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

Поставленная цель достигается тем, что в устройство, содержащее блок синхронизации, элементы И, триггер, вычитатели, ключ, умножители, блок сравнения, элементы задержки, элементы ИЛИ, регистры, выход первого регистра подключен к первым входам второго регистра и первого вычитателя, выход второго регистра подключен к первым входам третьего регистра и второго вычитателя, выход третьего регистра подключен к первому входу ключа и вторым входам первого и второго вычитателей, первый выход первого вычитателя подключен к первому входу первого, умножителя, выход которого подключен к первому входу блока сравнения, первый выход второго вычитателя поДключен к первому входу второго умножителя, выход которого подключен к второму входу блока сравнения, первый выход которого подключен к первому входу первого элемента ИЛИ, второй вход которого является первым управляющим входом устройства, выход первого элемен а ИЛИ подключен к вто1075289 рому входу ключа и первому входу второго элемента ИЛИ и через первый элемент задержки пОдключен к второму входу третьего регистра, второй выход блока сравнения подключен к второму входу второго элемента ИЛИ, выход ко- 5 торого через второй элемент задержки подключен к второму входу второго регистра, первый вход блока синхронизации объединен с первым входом триггера и является вторым управляющим вхо- 10 дом устройства, второй вход блока синхронизации является третьим управляющим входом устройства, первый, второй и третий выходы блока синхронизации подключены соответственно к синхронизирующим входам первого и второго вычитателей, первого и второго умножителей и блока сравнения, введен распределитель импульсов, первый и второй входы которого подключены соответственно к второму и третьему управляющим входам устройства, первый выход распределителя импульСОВ ПОДКЛЮЧЕН К ПЕРВОМУ ВХОДУ ПЕРВОго элемента И, выход которого подключен к третьему входу третьего регистра; второй выход распределителя импульсов подключен к первому входу второго элемента И, выход которого подключен к третьему входу второго регистра, третий выход распределителя импульсов подключен к второму входу триггера, выход которого подключен к первому входу третьего элемента И и третьему входу блока синхронизации, выход третьего элемента 35

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

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

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

Суть метода обработки информации, 60 заложенного в предлагаемом устройстве, состоит в определении пх;, 4у; для каждой точки двухмерного информаци- онного массива, определении произведений nx>. nv;, и nx;„ ny. и срав- 65 нения этих произведений с заданной точностью, где

dx, =x.

1 1 — 1

ОХ. = Х.-Х

Р 3

nv = у.-у

4у =у. -v о

"о о, динаты начальной (или информативной), i-ой и (1-1)-ой точки соответственно.

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

4х.- nv . =ох..оу..

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

4Х 1™У;устранение избыточности вводимой двухмерной информации осуществляется в реальном масштабе времени в процессе анализа текущих координат.

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

ЭВМ не вводятся.

Для анализа формы вводимОй кривой в устройстве определяются элементарные приращения координат х и у каждой последующей точки относительно предыдущей, для чего координаты первой точки (А р ) записываются в регистр 1, второй точки (A „) в регистр 3, третьей точки (Ао ) — в регистр 2, при этом на вычитатель 5 поступают координаты из регистров 1 и 3, а на вычитатель 4 из регистров

1 и 2. Вычитатель 5 определяет разНОСТЬ ЬХ = Хл Х И 4Ъ = У4

"оо 1 01 — уело„, а вычитатель 4 определяет

Разности 4Х = X> — Хл, ЬУ

02 M 2

У

"og "оо

Значения 4 Х1 и nV поступают в умножитель 7, а значения пХ и 4У. поступа:от в умножитель 6, причем на выходе умножителя 7 получается произведение ДХ1- ду, а на выходе умножителя 6 — произведение 4х 4 1

Сравнивая между собой значения хну и Д Х -4 У1 мОжнО Определить лежат точки ео Ао„, A О> на одной прямой или нет. При неравенстве произведений ..4х1 nv< и л хя hv дается разрешение на вывод координат точки

A в ЭВМ, а также перезаписи координат точки А, 1 в регистр 1, а точки

1075289

АД вЂ” в регистр 3, при этом координаты точки Ао стиреются. При обнаруО1 женин признака грямолинейного участка координаты каждой последующей точ,и на этой кривой сопоставляются с координатами начальной точки участка

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

При этом количество выводимых точек на единицу длины участка кривой зависит от кривизны участка и величины координаты.

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

Перед началом ввода двухмерного массива сигналом, поступающим по шине 21, устанавливается в нулевое состояние триггер 18, блок 19 синхро25 низации и распределитель 14 импульсов, состоящий из последовательно соединенных элемента И, двухразрядного счетчика и дешифратора, причем выходы счетчика через элемент И-НЕ под- ЗО ключены к одному из входов элемента

И (не указаны). Нулевым сигналом с

I един ного выхода триггера 18 элемент

И 17 и блок 19 блокируются.

При вводе первой точки по входной 35 шине 22 на вход элемента И распределителя 14 импульсов поступает сигнал ввода, при этом по сигналу с первого выхода распределителя 14 через элемент И 15 в регистр 1 записывают- 4р ся координаты Х, у точки А, поступающие одновременйо с сигналом ввода по шине 20 из устройства съема данных в цифровом параллельном коде.

При вводе следующей точки сигнал íà 45 первом выходе распределителя 14 сни-о мается, чем блокируется элемент И 15, а сигналом с второго выхода распределителя 14 разрешается запись координат точки A, „ через элемент И 16 в регистр 3.

Третий сигнал ввода, поступающий по шине 22 на вход распределителя

14 импульсов, формирует сигнал на третьем выходе распределителя 14, который поступает на $ -вход тригге- 55 ра 18 и устанавливает его в единичное состояние. Сигнал с единичного выхода триггера 18 поступает на входы элемента И 17 и блока 19 синхронизации, при этом на выходах блока 19 60 поочередно формируются тактовые импульсы. По сигналу с первого выхода блЬка 19 синхронизации через элемент

И 17 в регистр 2 записываются координаты точки А. „-, поступающие по шине 65

20. Далее по сигналу "а " с второго выхода блока 19 синхронизации, поступающему на управляющие входы вычитателей 4 и 5, разрешается ввод координат точек A „ A и A«, A < в вычитатели 5 и 4 соответственно, при этом вычитатель 5 определяет разность координат A „-Ao, а вычитатель 4

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

dxg ЬiJ

Результаты вычислений в умножителях 7 и б поступают в блок 8 сравнения, где по сигналу "8" с четвертого выхода блока 19 синхронизации они сравниваются.

В данном случае результатом является сигнал неравенства, который через элемент .ИЛИ 9 поступает в ключ 13, тем самым разрешая .задачу координат точки А о, находящейся в регистре 1, в ЭВМ. Далее этот же сигнал, пройдя элемент 11 задержки, разрешает перезапись координат точки А д,„из регистра 3 в регистр 1.

Кроме того, сигнал неравенства с элемента ИЛИ 9 поступает через элемент ИЛИ 10 и элемент 12 задержки, время задержки которого больше, чем элемента 11 задержки, в регистр 3, чем разрешает перезапись координат точки A.z> из регистра 2 в регистр 3, при этом координаты точки А о„ в регистре 3 автоматически стираются.

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

И 17 записываются координаты точки

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

Аналогичные операции производятся до поступления из устройства съема координат точки А,„„ (табл.).

В этом случаЕ произведенйя дХ,, ду и дх . д равны. Сигнал равенсРва

1 с второго выхода блока 8 сравнения через элемент ИЛИ 10 и элемент 12 задержки поступает на управляющий вход регистра 3 и разрешает, таким образом, перезапись координаты точки А„,„= из регистра 2 в регистр 3.

В следующем цикле в регистр 2 вводятся координаты точки А <>, как и ранее производятся определения

1075289

Результат вычитания в блоке 4 вычитания

Перезапись иэ регистра

3 в регистр 1

Перезапись из регистра 2 в регистр

Вывод в ЭВМ

Результат сравнения в блоке 8 сравнения

Результат вычитания в блоке 5 вычитания

Запись координат в регистр

02 Оо

А -А„

А о

Ао1 Аоо

02 о<

ЕА02

01 о2 оз

А09 -Ао

09

А1о

A -А

10 09

10 09

Н1 09

12 09 11 09

24 23

A .-А

А26 -A25

21 25

28 27

29 28

А23

27

А27

А27

29

А29

28

АЭо

A3о А28

АФО

А34

31

А 2-А

А

ЗЭ

33 разностей в блоке 5 А „.-1 „, в блоке

4 А 2-Ао определяют< я П.оизведения

Ьхо 612 и дк ДУ

1 где

ЙХ =Х -Х ЙХ =Х вЂ” Х

4,4,4, 11 09 12 09

ЙЧ Ч4 -Ч ЬJ = J1 -У

11 09 12 09

Далее производится сравнение произведений. В этом случае на выходе блока 8 сравнения появляется сигнал неравенства, который через элемент

ИЛИ 9 разрешает выдачу н ЭВМ координаты точки А09 из регистра 1, через элемент 11 задержки разрешает перезапись координаты точки А „ из регистра 3 в регистр 1, и через элемент ИЛИ 10 и элемент 12 задержки разрешает перезапись координаты точки A 2 из регистра 2 в регистр 3.

25 23

26 24

27 25

28 26

29 27

А3о А28

31 28

32 j0

ЭЭ 31

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

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

ЭВМ, затем с выхода элемента 11 эа10 держки поступает на управляющий вход регистра 1, разрешая перезапись координат точки А 5 из регистра 3 в регистр 1. Второй импульс окончания съема через элемент ИЛИ 9 разрешает

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

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

1О

1078289

1 2 3 4 5 6 7

« Лев

А., АЗ2

АЗ5

36

37

32

38

39

А4о

А З

АЛЗ Аэ

44 37

+2 31

37

А44

А43

44 43

А

Aso А43

51 43

32 5о 49 43

А5 А43

54 50

АЗо

А5о

ASo

52

A So

35 53

54 53

А5о

Конец

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

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

А -А 32

35 32.

АЗ6 "ЗФ

З М

АЗЕ

34 32

35 32

36 32

АЗМ А 32

38 32

39 3

А4о -37

Продолжение таблицы

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

1075289

Фиг.Г

BH HHIIH 3 акаэ Го 6/ич Тирам Е6 9 Подписное

Филиал ППП "Патент" r. Уигород ул Проектная 4