Устройство для определения положения числа на числовой оси Советский патент 1986 года по МПК G06F7/06 

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

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

На фиг. 1 приведена функциональная схема устройства} на фиг. 2 - временная диаграмма работы элементов устройства.

Устройство содержит входной счетчик 1, управляющий триггер 2, генератор .3 импульсов, элементы И 4-6, формирователи импульсов 7 и 8,группу элементов 2И-ИЛИ 9,,-9(„.,), счетчики 10,-lOnt, диапазонов, триггеры 1 11-1 „, диапазонов, элементы ИС1СЛЮ- ЧАЮЩЕЕ ИЛИ , группу элемен- тов 2И-ИПИ 13,-13„,,, Меньше 14, информационные выходы 15, вьпсод Больше 16, вход запуска устройства 17, входы анализируемого числа устройства 18.

Входной счетчик служит для запси ИСХОДНОГО сортируемого числа и определения конца цикла сортировки числа по диапазонам и выработки сигнала на своих выходах: на своем вых де (заем, б 0) при поступлении импульсов на вычитающий вход счетчика 1, на своем третьем выходе (переполнение, п) при поступлении соответствующего числа импульсов на суммирующий вход счетчика 1.

Управляющий триггер 2 предназнач дпя хранения признака (значения) старшего информационного разряда в поступающем числе а с первого выхода счетчика 1.

Генератор 3 импульсов служит д;ля выработки синхронизирующих импульсов поступающих на первые входы первого 4 и второго 5 элементов И, причем ,5(апуск .генератора 3 осуществляется по заднему фронту (О ) сигнала по входу 17 устройства, а останов генератора - только по заднему фран- ту ()сигнала с выхода третьег.о элемента И 6. Первый 4 и второй 5 элементы И служат для клапанирования синхронизирующих импульсов в зависимости от содержимого старшего раз ряда сортируемого числа

Формирователь импульсов 7 служит WЯ выработки строб-импульса в кон

це сортировки числа по диапазонам в случае, когда старший разряд числа а )j содержит О.

Формирователь импульсов 8 служит для выработки строб-импульса в конце сортировки числа по диапазонам в случае, когда старший разряд числа а содержит Первая группа элементов 2И-И1.(И 9i|-9«-, служат для выработки импульсов счета.

Счетчики lOi -IOnn служат для записи диапазонов X,, ( ,) . , (Х Х;, ),...Хп, где Х Д S |} Xд - границы диапазонов,

Триггеры 11, -П,., диапазонов служат дпя запоминания поступления,сигналов с выхбда счетчиков lOi-lO,,, диапазонов.

Элементы ИСКЛЮЧАЮЩЕЕ ИЛИ и вторая группа элементов 2И-Ш1И сл ужат ддя выработки сигналов сортировки на выходах устройства.

Элементы устройства счетчики, триггеры, элементы И, ИСКЛЮЧАЮЩЕЕ ИЛИ 2И-ИЛИ могут быть исполнены на базе типовых цифровых интегральных серий типа 133, 155, 561 и т.д.

Форжрователи и генератор импульсов могут быть выполнены, например, на базе микросхемы К155 АГЗ, К155АГ1 с соответствз ющими схемами запуска.

Q

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

Исспедуемый диапазон (Х-, ..,Х„) разбит на поддиапазоны, где , . . . ,Хп - границы поддиапаз онов. Триггеры обнуляются. На информационные входы счетчиков 10, - Ю,,.,,, поступают значения Х .(,) , (X,--X,j) 5, t ., (Х, -Х),..., (Ху,-Х„) X,, соотзетственно. По синхроимпульсам на соответствующих сиюсровходах сче тчиков , значения разности границ переписываются в соответствующие счетчики (цепи обнуления и начальной записи не показаны),. Таким образом, перед началом работы в счетчиках 10 будут содержаться значения разности значений соответствующих соседних границ диапазонов, а в счетчик 0„ заносится разность между максимальным значением числа в избранной двоичной разрядной сетке и значением верхнего поддиапазо1 а Х„, т.е. его инверсное значение ,-х,

3

На вход 17 запуска устройства поступает импульс запуска (фиг, 2),а на информационный вход 18 поступает исследуемое число an, которое необходимо определить в соответствующих диапазонах. По переднему фронту (1-fcO) сигнала запуска по входу 7 устройства код числа an переписывается во входной счетчик I. В зависимости от величины поступающих чисел an устройство переходит в один из двух режимов работы: в режим 1, если ,на вход поступило число 04 ап

. т.е. в первой половине разрядной сетки, в режим 2 если на вход

поступило число -jSHfL а млкс

т.е. во второй половине разрядной сетки.

Пусть максимальное число двоич- 1х разрядов в исследуемом диапазоне двоичных чисел составляет, например, восемь разрядов, а границы поддиапазонов Х,1, Х,3, ,..., Х,.,249, , Х„ 255-253 2.

Режим 1.

На вход 18 поступило число а,

например . По переднему

фронту () сигнала со входа 17 устройства число переписывается во входной счетчик 1 так, что на его первом выходе (старшем двоичном разряде) установится нулевой потенциал. По заднему фронту () сигнала по входу 17 нулевой потенциал с первого выхода.счетчика 1 переписывается в триггер 2 так, что на его прямом выходе - нулевой потенциал, а на его инверсном - единичный потенциал. Далее, по заднему фронту сигнала по входу 17 устройства запускается генератор 3 импульсов и на его выходе появляются импульсы (фиг. 2). Поскольку триггер 2 установлен в нулевое состояние, то на втором входе элемента И 4 - единич- ньй потенциал, а на втором входе элемента И 5 - нулевой потенциал. На выходе элемента И 4 появляются импульсы, поступающие на вычитающие счетчика 1, счетчика 10, диапазонов и первые входы первой группы элементов 2И-ИЛИ 9 , . Поскольку в исходном состоянии все триггеры 11 -llfm в нулевом состоянии, то ну левые потенциалы с их прямых выхо314974

дов блокируют срабатывание первой группы элементов 2И-ИЛИ по третьим и четвертым входам. Таким образом, импульсы с выхода элемента 5 И 4 вызывают вначале изменение состояния счетчика I и счетчика 10 до тех пор, пока число поступивших импульсов превысит значение границы первого диапазона.. Для случая при 10 Х,1, после первого же импульса на выходе счетчика 10( появляется от-, рицательный импульс, по заднему фронту которого () устанавливается

триггер 1 Г, в единичное состояние,

разрешение с прямого выхода которого поступает на третий вход элемента 2И-ИЛИ 9) первой группы. Второй импульс с выхода первого элемента И 4 поступает на вычитающий вход

счетчика и вход счетчика 1рг через элемент 2И-ИПИ 9(. При 1. 3, (Х.-Х,) 2, после двух поступивших на вход счетчика 10 импульсов на его выходе появляется отрицательный импульс,

по заднему фронту которого (О- I) устанавливается триггер I1 в единичное состояние, разрешение с прямого выхода которого поступает на третий вход элемента 2И-ИЛ11 92, ТаКИМ образом, после установления триггеров 11 и l2 в единичное-состояние , сработает элемент ИСКЛЮЧАЮЩЕЕ ИПИ 12, поскольку на его первом входе - единичнь(й потенциал, а на его втором входе - нулевой потенциал. С выхода элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 12 единичньй потенциал поступает на третий вход элемента 2И-ИЛИ I3j второй группы. На выходах остальных элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 12,, 12, ,..,12 - нулевые потенциалы, поскольку на первом и втором входах эл.е- ментов ИСКЛЮЧАЮЩЕЕ ИЛИ 127 - единичные потенциалы, а на входах остальных элементов ИСКЛЮЧАЮЩЕЕ ИЛИ - нулевые потенциалы.

При последующем поступлении импульсов счета через элемент 2И-Ш1И 9{ второй группы на вычитаюш 1й вход

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

по заднему фронту () которого запускается формирователь импульсов 7. На выходе формирователя импульсов 7 появляется строб-импульс и на

первом и третьем входах элемента 2И-ИЛИ 13,- единичные потенциалы. Срабатывает элемент 2И-ИЛИ 13, а на выходе IS - единичный потенциал, что соответствует определению числа а , в границах соответствующего диапазона ,, а на всех остальных выходах 14, 15,, 1 5 ,.. . , 15.,,

16устройства - нулевой потенциал. По заднему фронту сигнала (О-) со второго вьпсода входного счетчика 1 через элемент И 6 блокируется работа генератора 3 импульсов по второму входу последнего. Устройство закончило цикл сортировки числа в заданных границах Х, диапазонов . Перед сортировкой следующего числа а ft триггеры 11, 11,...,Пп+) обнуляются, а в счетчики 0,-IOt,+i записываются разности значений соот- ветствуюп х соседних границ диапазонов .

Режим 2.

На вход 18 устройства поступило.

число -|---- ,, например а

250. По переднему фронту () сигнала с входа 17 устройства это число переписывается во входной счетчик 1 так, что на его первом выходе (старшем двоичном разряде) установится единичный потенциал. По заднему фронту (О 1) сигнала по входу 17 устройства единичный потенциал с первого выхода счетчика 1 переписывается в триггер 2 так, что на его прямом выходе - единичный потенциал, а на его инверсном выходе - нулевой потенциал. Далее, по заднему фронту сигнала по входу

17устройства запускается генератор 3 импульсор и на его выходе появляются импульсы, которые поступают на выход элемента И 5 и далее на суммирующий вход счетчика 1, вычитающий вход счетчика 10(i+, диапазонов и вторые входы группы элементов 2И-РШИ 9(-9„,, . Поскольку в исходном состоянии все триггеры 11, - в нулевом состоянии, то нулевые потенциалы с их прямых выходов блокируют срабатывание группы элементов 2И-И1Ш ),., по третьим и четвертым входам.

Для случая , после второго импульса на выходе счетчика 10,ц появляется отрицательный импульс, по заднему фронту которого (О - 1) устанавливается триггер 11„,, в еди314974

ничное состояние, разрешение с прямого выхода которого поступает на четвертый вход элемента 2И-Ш1И 9„-т первой группы. Третий импульс с. выхо- 5 да элемента И 5 поступает на суммирующий нход счетчика 1 и вычитающий вход счетчика 10 через элемент 2И-ШШ 9h-, При Х„,249, , а (., )4, после поступле10 ния пяти импульсов счета на суммирующий вход счетчики 1 на третьем выходе последнего появляется отрицательный импульс (фиг. 2), по переднему фронту (1 - 0) которого запус -5 кается формирователь импульсов 8. На выходе формирователя импульсов 8 появляется строб-импульс, а на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 12 й-- . единичный потенциал, так как ранее

20 триггер 11,, бьш установлен в единичное состояние. По совпадению единичных уровней на втором и четвертом входах элемента 2И-ИЛИ 13п на его выходе появляется единичный потенци2- ал (выход 5(,,, устройства). Это соответствует определению числа а,250 в границах диапазона „.,, например | 253-249J . На всех остальных выходах 14, 15j, 5, . .. ,5, 16

30 устройства будет нулевой потенциал. По заднему фронту сигнала (О I) с третьего выхода входного счетчика 1 через элемент И 6 блокируется работа генератора 3 импульсов по второму

35 входу последнего. Устройство закончило цикл сортировки числа an в задан-, ных границах Х,,Х,...,Хц диапазонов за пять тактовых импульсов, начиная с верхней границы Х.

40 Таким образом, при сортировке числа, а,, близкого к максимальному значению кода в разрядной сетке счетчиков, сортировка в режиме 2 происходит, начиная с верхних значений

45 границ диапазонов, что увеличивает быстродействие устройства.

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

50 Устройство дпя определения положения числа на числовой оси, содержащее п счетчиков диапазонов, (п-) элементов ИСКЛЮЧАЩЕЕ ИЛИ, где п - число границ диапазонов, элементы И,

55 причем установочные входы каждого счетчика диапазона подключены к шине начальной установки устройства, выход первого элемента И подключен к выч:итающему входу первого счетчи-.7

ка, отличающееся тем, .что, с целью повышения быстродействия, в него введены (п+1)-й счетчик диапазонов, |п-й элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, входной счетчик, управляю- ;ЩИЙ триггер, первый и второй формирователи импульсов, первая группа (п-1) элементов 2И-ИЛИ, (п+1) триггеров диапазонов, вторая группа (п+

+1) элементов 2И-ИЛИ и генератор импульсов, вход запуска которого

соединен с входом запуска устройства и синхровходами входного счетчи Kk и управляющего триггера, а выход подключен к первым входам первого и второго элементов И, установочные входы (п+1)-го счетчика диапазона подключены к шине начальной установки устройства, входы анализируемого числа устройства соединены с информационными входами входного счетчика, выход старшего разряда которого соединен с информационным входом управляющего триггера, инверсный и прямой выходы которого соединены с вторыми входами соЬтветственно первого и второго элементов И, выход первого элемента И соединен с первыми входами элементов 2И-ИЛИ первой группы и вычитающим входом входного счетчика, выход второго элемента И подключен к вторым входам элементов 2И-ИЛИ первой группы, вычитающему входу (п+ +1)-го счетчика и суммирующему входу входного счетчика, выхода заема и переполнения кот::рого подключены соответственно к первому и второму входам третьего элемента И и через первый и второй формирователи импульсов соединены соответственно с первыми и вторыми входами элементов 2И-ШШ второй группы, выход третьего элемента И подключен к входу останова генератора импульсов, выход i-ro элемента 2И-ИЛИ первой группы, где ,2,..,,(п-1), соединен с вычитающим входом (i+l)-ro счетчика.

1231497

выход заема j-ro .счетчика диапязона,

где ,J 1 ,2,..-., (п+1), соединен с

10

15

20

5

0

5

0

синхровходом j-ro триггера диапазона, информационные входы триггеров диапазонов подключены к входу логической единицы устройства, прямой выход i-ro триггера диапазона сое- динеч с первым входом i-ro элемента ИСКЛЮЧАЩЕЕ ИЛИ, прямой и инверс- ньй выходы первого триггера диапазона подключены к т 7етьим входам первых элементов 2И-ИЛИ соответственно пер- ,вой и второй групп,прямой выход второго , триггера диапазона подключен к четвер- тому входу первого элемента 2И-ИЛИ второй группы, второму входу первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и к третье- му входу второго элемента 2И-ШШ первой группы, прямой выход К-го триггера диапазона, где ,4,..,(п-1) соединен с вторым входом (k-l)-ro элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, с четвертым входом (k-2)-ro элемента 2И-ИЛИ первой группы и с третьим входом k-ro элемента 2И-ИЛИ первой группы, прямой выход п-го триггера диапазона соединен с первым входом п-го элемента ИСКЛЮЧАЩЕЕ ИЛИ, вторым входом (п-1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, третьим входом (п+1)-го элемента 2И-1ШИ второй группы и с четвертым входом (п-2)-го элемента 2И-ИЛИ первой группы, прямой выход (п+1)-го триггера диапазона соединен со вторым входом п-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и с четвертым входом (n-l)-ro элемента 2И-ИЛИ первой группы, инверсный выход (п+1)-го триггера диапазона соединен с четвертым входом (п+1)-го элемента 2И-ИЛИ второй группы, выходы первого и (п+1)-го элементов 2И-ИЛИ второй группы являются выходами Меньше и Больше устройства, выходы элементов 2И-ШШ второй группы со второго по п-й являются информационными выходами устройства.

фиг

Устройство относится К вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов. Устройство обеспечивает с высоким быстродействием сортировку чисел в границах заданных диапазонов. Устройство содержит входной счетчик-, управляющий триггер, генератор импульсов, элементы И, формирователи импульсов, счетчи- ;КН диапазонов, элементы ИСКЛЮЧАЮ- ЩЕЕ ИЛИ, группы элементов 2И-ИЛИ. Исследуемый диапазон разбивается на поддиапазоны. Значения разности границ поддиапазонов записываются в счетчики поддиапазонов, Код числа записывается во входной счетчик. В зависимости от его величины, определяемой по старшему разряду, устройство переходит в один из двух режимов работы - счета от нуля, если на вход поступило число 0 , т.е. в первой половине разрядной сетки, или счета от верхнего значения границ диапазонов, если на вход поступило число , т.е. во второй половине разрядной сетки, что увеличивает быстродействие устройства. 2 ил. а «(Л

Составитель Е.Иванова Редактор И.Сегляник Техред И.-Гайдош Корректор М.Максимишинец

Заказ 2652/52 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб.„ д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород,ул..Проектная, 4

г