Устройство для сравнения чисел

1СООЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСГЬБЛИК ОПИСАНИЕ ИЗОБРЕТЕНИЯИ АВТОРСКОМУ. СВИДЕТЕЛЬСТВУ(57) Изтике ииэобрет етеиие относится к автом ислительной технике. Цел ния - расаирение области УДАРСТВЕННЫЙ КОМИТЕТ СССРДЕЛАМ .ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетельство СССРВ 037244, кл С Об Р 7(04, 19 Я 2.Авторское свидетельство СССРУ 798813, кл, С 06 Р 7704, 1979.(54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ ЧИС пртщенения за счет возможности сравнения чисел в системе остаточныхклассов, Устройство для сравнениячисел содержит двоичные счетчики 1,2,элементы 3,4 сравнения, элементыИ 5,6и элемент ИЛИ-КЕ 7, две группы модульных счетчиков 15, 16, элемент НЕ 8,деюнфраторы 9-12 и элементы ИЛИ 13,14, В устройстве обеспечивается возможность сравнения чисел, представленных в системе остаточных классов.Работа устройства происходит по мето.ду досчета до опорных чисел и сравнения результатов досчета в модульных и двоичных счетчиках. 1 ил.Изобретение относится к автомати-ке и вычислительной технике и можетбыть использовано в устройствах обработки инФормации, работающих в системе остаточных классов (СОК).Цель из,обретения - расширение области применения эа счет возможностисравнения чисел в системе остаточныхклассов. 10На чертеже приведена Функциональ,ная схема предлагаемого устройства.Устройство для сравнения чиселсодержит первый и второй двоичныесчетчики ",. и 2, первый и второй элементы 3 и 4,сравнения, первый и второй элементы И 5 и 6, элемент БЛИНЕ 7, элемент НЕ 8, кервый - четвертый дешиФраторы 9-12, первый и второй элементы ИЛИ 13 и 14, первую и 20вторую группы модульных счетчиков15 и 16, входы 17 и 18 кодов остатковсравниваемых чисел, вход 19 закуска,тактовый вход 20, выходы 21-23.Каждый из и модульных счетчиков 2515 и 16 предназначен.для записи внего кода остатка сравниваемого числа по соответствующему основанию Р,РИ и последующего подсчета тактовыхимпульсов по этому основанию, Модуль ные счетчики 15 и 16 могут быть реализованы, например, на микросхемахтипа К 155 ИЕ 8, обеспечивающих любойтребуемый коэФФициент пересчета. Кроме того, модульные счетчики 15 и 16могут быть выполнены на колъцевьирегистрах сдвига с дешиФраторами навходе, причем разрядность каждого изэтих регистров соответствует разрядности двоичного .кода соответствующего основания Р , а дешнФраторы обеспечивают запись единицы в тот разрядрегистра сдвига, номер которого соответствует коду остатка Ы.; или ;сравниваемых чисел А и В,45Первый и второй дешифраторы 9 и0 выполнены так, чтобы обнаружитьзаранее заданную комбинацию кодовна выходах К модульных счетчиков 15и 16. Для наглядности на чертежев качестве этих дешиФраторов 9 и 10указаны элементы ИЛИ, к входам которых подключены все прямые выходысоответствующих модульных счетчиков15 и 16. При этом дешиФраторы 9 и 10Формируют сигнал логического нуляв случае, когда на всех прямык выходах всех К модульных счетчиков 15или 16 соответствующей группы появляются логические нули. В случае выполнения модулвных счетчиков 15 и 16на кольцевых регистрах сдвига дешифраторы 9 н 10 могут быть реализованына элементе И-НЕ, каждый вход которого соединен с выходом того разрядарегистра сдвига, который соответствует нулевому коду остатка.Остальные элементы являются стандартными Функциональными узлами, выполняемыми в виде микросхем,В основе работы предлагаемогоустройства лежит следующее.Любое целое число А из диапазонаО,Р может быть представлено в видеостатков М в Мот деленияэтого числа А на основания - взаимнопростые числа Р, РР такие,что их произведение П Р; Рз Р,.Припоследовательном переборе всех чиселдиапазона О,Р 3 соответствующие остатки 1; будут периодически изменяться от О до Р; -1, В случае, когдачисло А кратно сразу нескольким основаниям Р;, Р Р , его остаткиМ;,Ырпребудут равны нулю одновременно.Рассмотрим для примера случайпредставления чисел по следующим основаниям: Р, =3, Рщ 11Рз 5, Р=7(Р=Р Р Р Р =1155). В этом случаечисла, делящиеся без остатка, например, на Р,; Р 33, будут иметь следующие представления в выбранной СОК;О =0,0,0,0333 =(0,0,3,566 = 0,0,1,3а Ф1122 =0,0,2,2Назовем эти числа опорными числами А и перенумеруем их таким образом; А =О, А,=ЗЗ, А = 66 и т.д., оА=з. Р, Р (в общем случае А =дР,феРцаДешиФраторы 11 и 12 подключены к инФормационным входам элемента 3 сравнения таким образом, чтобы при появлении на выходах модульных счетчиков )5(К+1)-15 п или 16(К+1) - 1 бпо ф кодов остатков чисел А, и А . таких,1что 11 (А.А ), сигнал для числаА появляется на разряде информациоонных входов элемента 3 меньшего ве"оса, чем для числа А, (не более млад" шем разряде ,входа). При этом кодоостатков числа А по основаниямР,Рн не обязательно меньше кода числа Ао по тем же основаниям.)Например, в рассматриваемом случаеокод остатков числа А, = 33 по основаниям Р и Р 4 больше соответствующих кодов чисел, А = 66 и А =1122, хотя очевидно А, с А с А54 фУстройство для сравнения чисел работает следующим образом.Остатки М; и , сравниваемьм чисел А и В в двоичном коде записываются в соответствующие модульные счетчики 15.1 и 16.1 с соответствующих входов 17.и 18. Модульные счетчики 15 и 16 и двоичные счетчики 1 и 2 .перед этим предварительно обнулены (цепи обнуления не показаны). При этом в общем случае на выходах дешифраторов 9 и 10 (элементов ИЛИ в рассматриваемом примере) присутствуют сигналы логической единицы. После записи в счетчики 15 и 16 на управляющий вход 19 подается сигнал разрешения (уровень логической единицы), что обеспечивает пропускание через элементы И 5 и 6 тактовых им. пульсов с входа 20 на счетчики 1, 2, 15 и 16. При этом модульные счетчики 15, и 16.д обнуляются с пери. одом Р;Не йозднее, чем через Р,РР (в рассматриваемом примере Р, Р =ЗЗ) на всех выходах счетчиков 15.1 15.К и 16. 1 - 16 К появятся сигналы логического нуля. Причем в общем случае это произойдет неодновременно для обеих групп модульных счетчиков 15 и 16. В момент обнуления всех К счетчиков соответствующей группы на выходе соответствующего дешифратора 9 или 10 (элемента ИЛИ) появится сигнал логического нуля, который закроет соответствующий элемент И 5 или 6. В результате соответствующие счетчики 1, 15 или 2, 16 остановятсяеПосле того, как остановятся все ечетчики 1, 2, 1 5 и 16, на выходе элемента ИЛИ-НЕ 7 появится сигнал логической единицы, разрешающий работу первого элемента 3 сравнения. На его информационныевходы поступают с выходов дешифраторов 11 и 12 коды, определяемые кодами с выходовмодульных счетчиков 15, (К+1)-15.пи 16,(К+1)-16.п. Если число А, кодыостатков которого поданы на входы 17,больше или меньше числа В, коды остатков которого поданы на входы 18,то на соответствующем выходе элемента 3 появляется сигнал логическойединицы, который проходит через соответствующий элемецт ИЛИ 13 нли 14на выход 21 "Больше" ил 22 "Меньше".Например, пусть на входы 17 поданы коды остатков числа А=193= 1,6,1 б 3,4 , на входы 18 - числа В=971==2,3,1,5, тогда на выходе дешиф-:ратора 9 (элементе ИЛИ) через пятьтактов появится сигнал нулевого уровня, так как на выходах модульных20 счетчиков 15.1-15.4 будут коды остатков СО,О,3,2 , соответствующие, числу А = 198. На выходе дешифратора 10 через девятнадцать тактовтакже появится сигнал логического ну 25 ля, так как на выходах модульныхсчетчиков 16.1 - 16.4 будут кодыостатков ( О,О,О,З числа А =990.В результате на выходе элемента ИЛИНЕ 7 появится разрешающий сигнал иЗ 0 с выхода "Меньше" элемента 3 сравнения сигнал логической единицы через элемент ИЛИ 14 поступит на выход 22 устройства.Если же на выходах модульных счетчиков 15,(К+1)-15.п и 16.(К+1)-16,п35будут коды одинаковых опорных чисел,то элемент 3 сравнения выдаст сигнална своем выходе "Равно", по которомуразрешается работа второго элемента4 О 4 сравнения. На информационные входыэтого элемента 4 поступают коды свыходов двоичных счетчиков 1 и 2,после чего сигнал с соответствующеговыхода элемента 4 поступает на один4 В из выходов устроиства вНапример, пусть на входы 17 поданы коды с остатков числа А=620=2,4,0,4, а на входы 18 - числа В==596=(2,2, 1,1, тогда на выходе дешифратора 9 через семь тактов появится сигнал логического нуля, таккак на выходах счетчиков 15.1-154ебудут двоичные коды остатков 0,0,2,4 числа А, = 627. На выходе деИ,шифратора 10 сигнал логического нуляпоявится через тридцать один такт, ана выходах счетчиков 16. 1-16.4 будутдвоичные коды остатков 0,0,2,4 тоого же числа А, =627, При этом первый5 14 элемент 3 сравнения выдаст сигнал на выходе "Равно", разрешающий работу второго элемента 4 сравнения. Послед" ; ний сравнивает коды чисел 7 и 3 1 со счетчиков 1 и 2.и выдаст сигнал на своем выходе "Меньше", который,.про;ходя через элемент ИЛИ 13, поступает ,на выход 21 "Больше" устройства. Остановку счетчиков не обязательно выполнять при равенстве нулю кодов на выходах части модульных счетчиков. Можно взять в качестве опорных чисел ,те, двоичные коды остатков которых,например, содержат единицу тольков младшем разряде или только в старшем, либо какие-нибудь иные. Важно лишь, чтобы опорные числа располагались более или менее равномерно на числовой оси, во всяком случае мак ,симальная разность между соседними , опорными числами не должна превышатьемкость двоичных счетчиков 1 и 2.Предельная частота тактовых импульсов на входе 20 определяется вре, менем распространения сигнала в модульном счетчике 15 или 16, дешифра - , торе 9 или 10 и элементе И 5 или 6.Процесс сравнения чисел в СОК можно ускорить, выбирая в качестве Р 1 1ф у Рц меньшие основания и умень шая их число К. Однако при этом возрастает количество опорных чисел, из-за чего увеличивается сложность дешифраторов 11 и 12 и элемента 3сравнения.Если увеличить вдвое количество счетчиков и элементов сравнения, причем дополнительные двоичные счет чики включить в режим обратного сче" та, то быстродействие устройства возрастет по крайней мере вдвое, так как диапазон между двумя опорными числами будет просчитываться макси.мум до середины.Предлагаемое устройство способно сравнивать и двоичные числа, ес ли их коды подавать на установочные входы модульных счетчиков 15. 1-15.К и 16,1 16.К. При этом сигнал с выхода элемента ИЛИ-НЕ 7 следует подавать на управляющий вход второго элемента 4 сравнении либо отключать счетные входы остальных модульных счетчиков. 39574 6На основе предлагаемого устройства может быть построен преобразователь кода СОК в позиционный код, например в двоичный. Для этого следует заменить (или дополнить) дешифратор 11 (или 12) преобразователем кода опорных чисел н двоичный код с его выходов просуммировать с выходным кодом двоичного счетчика 1 (илн 2), взятым с обратным знаком. формула и з обретенияТаким образом, предлагаемое устройство позволяет сравнивать какСоставитель Е.Иванова Техред А.Кравчук Корректор Э.Лончакова Редактор С.Пекарь Заказ 6077/47 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, %-35, Раушская наб., д, М 5 Производственно-полиграфическое предприятие, г. Ужгород, улПроектная, 4 1439574, 8 ЯК+1) -п-го модульных счетчиковчены к выходам разрядов первого и первой и второй групп подключены к второго двоичных счетчиков, выходы1 11 Ф входам соответственно третьего и чет- Меньше и Больше которого соедивертого дешифраторов, выходы которых нены с первьжи входами соответственсоединены соответственно с инфор- но первого и второго элементов ИЛИ, мационными входами первой и второй вторые входы которых соединены с групп первого элемента сравнения, выходами соответственно "Больше" и выход "Равно" которого соединен с "Меньше" первого элемента сравнения, управляющим входом второго элемента 1 О выхоДы элемента ИЛИ и выход "Равно" сравнения, информационные входы и- второго элемента сравяения являются вой и второй групп которого подклю- выходами устройства.