Устройство для обработки массивов чисел

 

Изобретение относится к вычислительной технике и может использоваться при построении систем сбора и обработки информации, представленной массивами чисел, например, в цифровых устройствах обработки изображений. Цель изобретения - расширение функциональных возможностей за счет выполнения операции объединения, пересечения и дополнения над L - множествами. Устройство содержит регистр 8, реверсивный счетчик 9, блок памяти 12, блок логической обработки 13, элементы задержки 10 и 11, элемент И 14, группу элементов И 15. Блок логической обработки содержит информационные регистры, элементы И, элемент ИЛИ, коммутатор, элементы И-НЕ. Работа устройства основана на записи в ЗУ единичных признаков наличия конкретного числа в каждом из вводимых массивов по адресу, задаваемому с выхода счетчика, используемого как регистр. Восстановление чисел производится выделением соответствующих стробовых сигналов, осуществляемым за счет фиксации начала отсчета и исключения из серии тактовых импульсов тех по порядку импульсов, числа которых в массиве при записи не присутствовали. Значение чисел массива восстанавливается из линейно нарастающих или убывающих кодов, выделяемых на выходах счетчика. Блок логической обработки вводит дополнительные ограничения на вывод чисел. 1 з.п.ф-лы, 3 ил.

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

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

РЕСПУБЛИН

„„Я0„„1481739 (51) 4 б 06 F 7/06

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

H А BTOPCKOMY СВИДЕТЕЛЬСТВУ

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

flO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4210101/24-24 (22) 10.03.87 (46) 23.05.89. Бюл. № 19 (72) В. П. Боюн, А. А. Столяров и А П. Кичаев (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 1429107, кл. G 06 F 7/06, 1986.

Авторское свидетельство СССР № 1183956, кл. G 06 F 7/06, 1985. (54) УСТРОЙСТВО ДЛЯ ОБРАБОТКИ

МАССИВОВ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может использоваться при построении систем сбора и обработки информации, представленной массивами чисел, например, в цифровых устройствах обработки изображений. Цель изобретения — расширение функциональных возможностей за счет выполнения операции объединения, пересечения и дополнения над L-множествами. Устройство содержит регистр 8, реверсивный счетчик 9, блок памяти 12, блок логической обработки 13, элементы задержки 0 и 11, элемент И 14, группу элементов И 15. Блок логической обработки содержит информационные регистры, элементы И, элемент

ИЛИ, коммутатор, элементы И вЂ” НЕ. Работа устройства основана на записи в ЗУ единичных признаков наличия конкретного числа в каждом из вводимых массивов по адресу, задаваемому с выхода счетчика, используемого как регистр. Восстановление чисел производится выделением соответствующих стробовых сигналов, осуществляемым за счет фиксации начала отсчета и исключения из серии тактовых импульсов тех по порядку импульсов, чис.lа которы в массиве при записи не присутствовали.

Значение чисел массива восстанавливаcтcя из линейно нарастающи i или убывающих кодов, выделяемых н а вы ходах счетчика.

Блок логической обработки вводит дополнительные ограничения на вывод чисел. 1 з.ll. ф-лы, 3 ил.

1481739

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

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

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

Устройство для обработки массивов чисел (фиг, 1) содержит входы 1 — 1 — 1 — 3 записи режимов устройства, входы 2 — 1 — 2— (1.+1) задания режимов устройства, обеспечивающие возможность изменения функций, вход 3 записи режима работы блока памяти, позволяющий устанавливать его в режим записи любого из L массивов и его перевод в режим вывода информации, вход 4 записи чисел массива, вход 5 управления режимом вывода в порядке нарастания или убывания чисел, . информационные входы

6 — 1 — 6 — V, тактовый вход 7, регистр 8, реверсивный счетчик 9, элементы 10 и 11 задержки, блок 12 памяти, блок 13 логической обработки, элемент И 14, группу из 1 элементов И 15 — 1 — 15 — L, стробирующий (L+1) -й выход 16, стробирующие выходы 17, с первого по L-й информационные выходы

18 — 1 — 18 — N.

Блок 13 логической обработки содержит входы «Запись» регистров 19 — 1 — 19 — 3, входы 20 — 1 — -20 — (L+1) задания режимов блока, входы 21 — 1 — 21 — L, информационные регистры 22 — 1 — 22 — 3 элементы И 23—

1 — 23 — L и 24 — 1 — 24 — 1., элемент ИЛИ 25, элемент И 26, коммутатор 27, элементы И—

HE 28 — 1, 28 — 2, 28 — 3, выходы 29 — -1, 29 — 2, 29 — 3 соответственно реализации функций

ИЛИ либо ИЛИ вЂ” НЕ, И либо И вЂ” НЕ и выделения одного из записанных в блоке 12 массивов.

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

Регистр 8 служит для задания режима работы блока 12 памяти в соответствии с табл. 2.

Изменение режимов работы процессора производится записью требуемого кода в регистр 8.

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

Элементы 10 и 11 задержки предназначены для согласования во времени внутренних сигналов устройства.

2О

4G

4

Элементы И 14 и 15 — 1 — 15 — L предназначены для получения стробируюших сигналов, с помощью которых осуществляется выборка результатов обработки из нарастающей или убывающей последовательности кодовых сигналов с выходов счетчика 9 в режиме вывода.

Пусть, например, требуется в одно внешнее устройство ввести в порядке возрастания I-й инверсный упорядоченный массив, а в последующие L устройств в порядке возрастания — упорядоченные массивы, начиная с 1-ro no L-ый.

В таком случае реверсивный счетчик 9 устанавливается единичным потенциалом в режим суммирования и нулевое начальное состояние (по цепи сброс) и в соответствии с табл. 1 обеспечивается следующий вариант установки кодов регистров: 22 — 1—

000...0...001, 22 — 2 — 000...0...001, 22 — 3—

000...1...001.

С подачей тактовых импульсов на вход 7 реверсивный счетчик 9 обеспечивает линейное считывание записанных в блок 12 единичных признаков наличия чисел в ранее вводимых массивах. В том случае, если при записи массива число присутствовало на выходе блока 12, устанавливается логическая единица, если же нет — логический нуль.

Таким образом, на выходах 18 — 1 — 18 — N устройства выделяется линейно нарастающая последогательность возможных вариантов N разрядных кодов, а на выходах блока 12 выделяется информация о присутствии каждого числа в ранее вводимом массиве, что позволяет получить из последовательности тактовых импульсов на входе 7 соответствующий стробирующий сигнал на выходах элементов И 15 — 1 — 15 — L, с помощью которого можно осуществить восстановление из кодов на выходе счетчика 9 каждого из чисел. Это реализуется на входных регистрах внешних для процессора устройств, в которые в соответствии со стробирующими сигналами записываются выходные коды счетчика 9.

Так как на выходах блока 13 в соответствии с табл. 1 выделяются следующие значения: 29 — 1 — «1»; 29 — 2 — «1»;

29 — 3 — Хь то на выходе !6 стробирующие сигналы появятся в соответствии с изменением инверсного значения единичных признаков последовательности, записанной ранее в блок памяти.

При подаче выходного 16 стробирующего сигнала на вход «Запись», например, входного регистра внешнего устройства на 0триггерах, информационные входы которого подключены к информационным выходам ! 8 — 1 — 18 — N устройства так же, как и в предыдущем случае, происходит восстановление чисел массива по стробирующим сигналам.

Аналогично можно рассмотреть работу устройства при реализации функций, при1481739

1 а1i Ла2 =

0 при A,,=A =1; при любом другом случае;

1.

У=А 11 А г=

Q13 A< 23= а Лаи=

0 а !Лагг=

Формула изобретения

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

Пусть необходимо найти дополнение к полному множеству В (соответствует всем возможным разрядным числам, а в блоке

12 — всем единицам 111...111 ) выражения А 4Аг, что можно записать g=A, A (фиг. 3).

В соответствии с табл. 1 в регистры блока 13 необходимо записать в RG 22 — 3— (000...001), в RG 28 — 1 — (000...001), (т. е. на выходе 29 — 1 устанавливается логическая единица), в Яб 22 — 2 — (110...001), что соответствует подаче на входы элемента И 26 последовательности единичных признаков из блоков памяти и реализации инверсии результатов выполнения операции И над единичными признаками массивов А и Аг, введенных ранее в блоки памяти.

В результате выполнения операции И—

НЕ над всеми числами массива реализует= ся требуемая операция:

Результаты выполнения операций И вЂ” HE над единичными признаками чиеел первого

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

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

Можно также показать реализацию других операций над множествами А, Аг (фиг. 3), задаваемыми числовыми массивами, а также объединения двух, трех или

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

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

Рассмотрим (фиг. 2) работу блока 13 логической обработки. В табл. 1, № 8 дан перечень операций, которые выполняет блок

13, при подаче на его входы 21---1 — 21- — L входных сигналов Ль Хг; Хз...Л,...Хь В табл. 1, № 5 — 7 представлены состояния выходных сигналов в зависимости от состояния регистров 22 — 1 — 22 — 3 (¹ 2- — 4) . Изменен«е состояний регистров 22 — 1 — 22--3 осу«(есTвляется подачей соответствующего (табл. 1.

¹ 2 — 4) кода на входы 20 — 1 -20 — (L+-1) устройства и импульса «Запись» на вхо,1ы

19 — 1 — 19 — 3. Выходные кодовые с«гналы регистров 22 — 1, 22 — 2 lip 2Bë Rþò и рохо ждением информационных сигналов с входов

21 — 1 — 21 — через элементы И 23- 123 — 1 и 24 — 1 — 24 — 1, а выходные сигналы регистра 22 — 3 — «рохождсн«ем этих же сигналов через мультиплексор 27. Это позволяет выделить нг выходе элемент» ИЛИ 25 любой из выходных сигналов «л«нулевой потенциал (табл. 1, № 1), а также осу цествить операцию ИЛИ над произвольным числом входных сигналов (табл. 1, Ъ 2), «а выходе элемента И 26 — нулевой потепц«ал, любой из входных сигналов (табл. 1, № 51 или операцию И над произвольным ч«слом входных сигналов (табл. 1, № 6), а на выходе элемента И вЂ” НЕ любой из вход«ых с«гна 10В (табл. 1, № 9). Так как выходы элеме«тов ИЛИ 25 и И 26 и мультиплексора 27 соединены с выходами 29 — 1, 29 — 2, 29---3 через управляемые с выходов L+! - — х регистров 22 — 1, 22 — 2, 22 — 3 элементы И вЂ” -11Е

28, на выходах 29 — 1, 29 — 2. 29--3, кроме прямых сигналов с выходов элементов ИЛИ

25 и 26 и мультиплексора 27, могут быть получены их инверсные значения (табл. 1, № 3, 4, 7, 8, 10). В связи с тем, что запись кодов в регистры 22 — 1, 22 — 2, 22 — 3 осуществляется независимо от любых других, кроме описанных факторов, на выходах

29 — 1, 29 — 2, 29 — 3 могут быть получены также возможные комбинации приведенных в табл. 1, № 5 — 7 операций.

1. Устройство для обработки массивов чисел, содержащее реверс и вный счетч и к, 1481739 блок памяти, группу элементов И, причем информационные входы устройства соединены с информационным входом реверсивного счетчика, счетный вход которого соединен с тактовым входом устройства, вход «Запись» устройства соединен с входом управления записью реверсивного счетчика, выходы разрядов которого соединены с адресными входами блока памяти, выходы которого соединены с первыми входами элементов И группы, вторые входы которых соединены между собой, выходы элементов И группы являются выходами устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет выполнения операции объединения, пересечения и дополнения над L-множествами, в него введены регистр, блок логической обработки, два элемента задержки и элемент И, причем входы записи режимов устройства соединены с соответствующими входами записи режимов блока логической обработки, входы QQ задания режимов которого соединены с входами задания режима устройства и с информационными входами регистра, выходы разрядов которого соединены с входами блока памяти, вход записи которого через первый элемент задержки соединен с входом «Запись» устройства, выходы блока памяти подключены к информационным входам блока логической обработки, выходы которого соответственно соединены с первыми тремя входами элемента. И, четвертый вход которого соединен с вторыми входами элементов И группы и через второй элемент задержки соединен с тактовым входом устройства, выходы элементов И группы являются L-стробирующими выходами устройства, выход элемента И является (L+

1) -м стробирующим выходом устройства, выходы реверсивного счетчика являются информационными выходами устройства.

2. Устройство по п. 1, отличающееся тем, что блок логической обработки содержит три (L+1) -разрядных регистра, первую и вторую группу элементов И no L элементов в каждой, L-входовые элементы И и ИЛИ, коммутатор и три элемента И вЂ” НЕ, причем входы записи режимов блока соединены соответственно с входами «Запись» первого, второго и третьего регистров, информационные входы которых поразрядно подключены к соответствующим входам задания режимов блока, информационные входы блока соответственно подключены к. первым входам элементов И первой и второй групп и к информационным входам коммутатора, первые 1 -выходов первого и второго регистров подключены к вторым входам элементов И первой и второй групп соответственно, выходы третьего регистра с первого по L-й соединены с соответствующими управляющими входами коммутатора, (L+1) -е выходы первого, второго и третьего регистров соединены соответственно с первыми входами первого, второго и третьего элементов И вЂ” НЕ, вторые входы которых соответственно подключены к выходам элемента ИЛИ, элемента И и коммутатора, выходы первой и второй групп элементов И соединены соответственно с входами элемента ИЛИ и элемента И, выходы первого, второго и третьего элементов И вЂ” НЕ являются выходами блока логической обработки.

1481739

СЧ

О 1

С 4 х 1

° С 4 х ( о х

С1 о

IQ о о

4О

Я

ccl х х о

Ц,Д О1

ccl I сч х

СЧ и х о о

I л х со

Е С 4"

cd 1

1 о

1 СЧ

СЧ С о

1 л со

С 4

I»

СЧ

СЧ х

Ц

tf о

1 I 1 1 I I

1 1 I 1 1 I 1 1 1 I 1 1 1 I

1 I I I I 1 1 с»

I I

1 м\

»4

1 1 1 I 1 1 1 х

) х

> > 1 х х

I х х охх

I I I 1 1 1 1 I 1 1 1 1 I I

1

СЧ

l 1

1 1 I 1 1 о х о

Y. х

) о

1 „

СС I о 1

E 1 о 1 о

О х

1 с 4 !

1О

> х х

) > х х

1 1 х х

) () Ч >

4 хх х х

) I > I >

Х !Х Х IIХ IIХ х"

) х х

) > 1 х х 1

I I I I 1 1

Ч!

Х I

Ъ

Х 1 Х

Ч х!х 1

С Ф ххх

-!х

1

1 м I

I 1

СЧ

С !

I I I I l I

I 1 I I I I 1 I 1 1 I I

1 1 1 1 I

1 I I I 1 1 I о

Ю о

1 сЧ I

1 I 1

С 4

СЧ

1 1 1 I I I

OOOO 1 О оооо=

ОООО 1 «О

1 I I 1 1 1 1 1 I 1 1 I I I 1 I 1 1 I 1 1 о о

oo= ос

ООО I ОО

oo-o= oo

ООО I ОО о

I а 1

E. а. о о о

Ю с х х о

1 о I 1 о о

Ю о с с

1 I 1 I 1 I 1 1 1 1

° 1

1 оооо

oooo= оооо

1 оооо= ос@о оо

oo= оо

I ооo oo о о

С4

СЧ

ООО!О!О

ОО О= О= О

O-OO I O I O

o I o

o= o

O I O оI о- o

o= о оооо о — o= о-оо с оо1 а

44

Е о х

I

I !

С! ! а

44 I и о

cd I

1 .д С4 х цо о х

X 2 их х

cd ccl х х х л х Е 1 о е

С0 С 4 х с6

0 cE I х оD Х С4 х х

=1 х х анэ о

dI Z X

О Cd о х

С4

44 Х Х х е л Ф

С4 О О

5?

Ц cd о

И С 1»

2 С4 Х со х о о о

Ю у

44 с6

Х lll х о а о

Ql 1 х х х Ф о

Ql Ц х х х g

> C4

Ц о х

С 4

С 4 о

Б С 4

C( о а х о

Ш с5 С0 х»

1 х х

Q lD х о а х г х

O E

О lD х я

Ц х а с6 о z и

Е Ш

l2 х

1» х о х

С4 м х х о с. о ох х

lD О4

Я цох х

44 О ххх х Ф л

dl X

u dl

R cd

Ц Х dl

X O cd

С( о с! о

С Х 1

С(ccl I 1 х

СЧ о х х х е (Х с 4

С3 х

D 5 Х

Ql cd а3

И X о хо о х

44 Е С!4 о х х о х х х х оло

lD

Я

Сс4 Ц X

1481739

1г

Е

v

P (!4 ((4 х

С 4

О (Ч и ж

О а (»

О4 2

Е

X л

<и (o и Я

О

QI (0 Х

t(О и

1 1 1 1 а с 4с

О1х1Х!х I!Х I (Х -1х!Х! Х I dd 11Х

1 I I I 1 !

1 1 1 1 1 1 м

О !

С4 ( х ( х х

< х х

1 (Q 1 С 4 о

I Oc

< 1 I 1 1 х ( х х

1 I 1 1! .4 .-Ъ х х " х

<С 1< хх Г!

1 1 (с Z — 1Х,Х;Х I (Х 1,Х

1 o(1 С4

I 1 1 1 1 I 1 I 1 I 1 1 1

1 1 1 I I I I 1

О

О о о о

С \

I 1

С4 1

С 4 1

1 (.3 I

1! о —-ооо ооооО о

I оооо—

ooo-o=

oo-oo оооо

ОООО оооо

1 1 1 I 1 1 1 1

1 I 1 I 1

O I O

o= o

o I O

OOO — I O

oo-o= o=

О О О 1 О 1 о о

Ю о (о о (4

С4 (4

I I I I 1 I 1 1

1 оооо= оооо

О О о о

OOO- I O I O

ОО О= О= О

О О О 1 О I О о

О о

o—-! о— сo—m 1

О

О, (". 1

v 1 х (» 1

Ql 1

О, Ql

Х

ы

М

О

E (4

О о

CV I (4 1

I 1 I 1 I I I 1

1 I 1 1 I I 1 а

Е

l л

=1

X ! (О

Cd

l(4

F4

М

Ч о с

О о.!

l (! (С и I

Cd

0)

l

О !

О СЧ

1( л ((4 1

Ql I

Х 1. х 1 !

О

О 1

О о

О

Я

Ц ((4

О

Е I:1

Х О

О Х а m

Ql

m

О

Ql

Е х х х

> v

Ц

О m (Е л

Х (4

Ос

° С 4 (Cl с(4

С .(о

° I>(C х л (44 с6 х и

Ы

1 Z

Ж

g ж

Й Cd

"1 (с! Х ао с(4 Е

И О

o x х (Qf

О х ((4 (с(сЧ и сЛ О!

Д 1 N

ОЕ(О и

1 л

Й (й

v сч

gm

ОХ (»

О

lO cc

Q x

С: М

I с(4 Ос и Хсч

Ю ((4

d OCQ аqo сс(Х л (1 ((Q о к

О Х ((4

О ц х с6

ы (с\ ссс

V Х О с (»4 (Q ч ((( х е(o o (»

Π— л

lo x m

1481739

Таблица 2

Режим

000 ° ° .001

110...000

111...000

111.. ° 111

20-/

27L f1 г1-1

Фиг. 2

Информация на выходах

000...000

100...000

010.. ° 000

001.. ° 000

Вывод чисел из блока 12

Ввод чисел первого массива

Ввод чисел второго массива

Ввод чисел третьего массива

Ввод чисел L-го массива

Ввод чисел одного массива одновременно в первый и второй узлы блока 12

Ввод чисел одного массива одновременно в первый, второй и третий узлы блока 12

Ввод чисел одного массива одновременно во все узлы блока 12

1481739

А> г

А/ Az l 2

А/ г

Составитель В. Журавлев

Редактор Л. Гратилло Техред И. Верес Корректор С. Черни

Заказ 2690/49 Тираж 669 Поди исное

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

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

Производственно-издательский комбинат «Патент», г. Ужгород, YJI. Гагарина, 10!