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

Номер патента: 1756887

Авторы: Ахременко, Коляда, Селянинов, Чернявский

Есть еще 3 страницы.

Смотреть все страницы или скачать ZIP архив

Текст

(5)5 6 06 Р 7/72 ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ институт лем им. А.ф;Чер(21) 4880868/24(56) АвТорское свидетельство СССРМ 579614, кл. 6 06 Г 7/38, 1977,Авторское свидетельство СССРМ 1287152, кл, 6 06 Р 7/72, 1987,(54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ЧИСЕЛВ МОДУЛЯРНОЙ СИСТЕМЕСЧИСЛЕНИЯ(57) Изобретение относится к вычислительной технике и предназначено для использования в . быстродействующихнепозиционных арифметических устройст-.вах конвЕйерного типа для выполнения опе-рации деления чисел. представленных вминимально избыточной модулярной системе счисления. Цель изобретения - повышение быстродействия за счет увелиЧенйяпропускной способности устройства., По-ставленная цель достигается за счет приме 2нения конвейерного принципа обработки модулярных кодов делимого и делителя и обеспечения возможности совмещения во времени процессов выполненияТ+ 6 операций деления (Т = о 92 К 1, К - число оснований модулярной системы счиСления; через )х 1 обозначается наименьшее целое число, не меньшее х). Для формирования приближения делителя и вычисления зйака делителя используется не блок масштабирования, а отдельный блок параллельйо-конвейерного тийа для формирования интегральных характеристик модулярного кода, обращение к которому можно производить ежетактно, т.е. с частотой К = 1./(м,т м.т. - длительность модульного такта). Устройство содержит коммутаторы 5, 6, блокуправления 7, узлы 8, 9 задержки, формирователь 10 интегральных характеристик модулярного кода, блок модульного вычитания 11, блок модульного умножения 12, мультйплексор 13, узлы задержки, регистр, блок:присвое- .ния знака, коммутатор, блок модульного д сложения, блок масштабирования и узлы задержки, 3 ил.щ е е с я тем, что, с целью повышения быстродействия, устройство содержит третий коммутатор, мультиплексор, с второго по шестой узлы задержки, блок формирования интегральных характеристик модуляр ного кода, блок присвоения знака, в блок управления дополнительно введены первый и второй регистры сдвига, первый и второй кольцевые сдвиговые регистры, второй и третий элементы И, причем входы делимого и делителя устройства соедийены с первым информационным входом соответ-ственно первого и второго коммутаторов, выходы которых соединены с входами первого и второго узлов задержки соответст венно, вторые информационные входы первого и второго коммутаторов соединены с первыми выходами второго и третьего узлов задержки соответственно, выход первого узла задержки соединен с входом 2 О уменьшаемого блока модульного вычитания, выход которого соединен с входом третьего узла задержки, второй выход кото- рого соединен с первым входом блока присвоения знака, второй вход которого 25 соединен с первым выходом четвертого узла задержки, второй выход которого соединен с первым информационным. входом мультиплексора, выход которого соединен с входом четвертого узла задержки, второй ЗО информационный вход мультиплексора соединен с первым выходом блока формирования интегральных характеристик модулярного кода, второй выход которого соединен с первым информационным вхо дом третьего коммутатора, второй информационный вход которого соединен с выходом пятого узла задержки, вход которого соединен с выходом третьего коммутатора и первым входом блока масштабирования, 4 О второй вход которого соединен с выходом блока присвоения знака, выход блока модульного сложения соединен с входом шестого узла задержки, выход которого соединен с выходом частного устройства и входом второго слагаемого блока модульного сложения, второй выход второго узла задержки соединен с входом второго сомножителя блока модульного умножения, вход делителя устройства соединен с входом блока формирования интегральных характеристик модулярного кода, вход запуска устройства соединен с входом сброса шестого узла задержки и с установочными входами первого и второго регистров сдвига и входами сброса первого и второго кольцевых сдвиговых регистров, входы управления сдвигом которых соединены с одноименными входами первого и второго регистров сдвига и тактовым входом устройства, выход старшего разряда первого регистра сдвига соединен с входом младшего разряда первого кольцевого сдвигового регистра, выход которого соединен с первым входом второго элемента И, второй вход которого соединен с выходом третьего элемента И, входы которого соединены с выходами разрядов второго кольцевого сдвигового регистра, вход младшего разряда которого соединен с выходом первого элемента И, первый выход второго регистра сдвига соединен с управляющими входами первого и второго коммутаторов, второй выход второго регистра сдвига соединен с первымвходом элемента ИЛИ, второй вход которого соединен с выходом старшего разряда второго кольцевого сдвигового регистра, выход элемента ИЛИ соединен с входом блокировки блока масштабирования, третий выход второго регистра сдвига соединен с вторым входом первого элемента И, четвертый и пятый выходы второго регистра сдвига соединены с управляющими входами третьего коммутатора и мультиплексора соответственно, выход второго элемента И соединен с выходом признака окончания деления устройства.1756 ВВ 7Составитель М,Селянинов Редактор И.Дербак Техред ММоргентал Корректор М.Петрова аз 3089 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 4/5оизводственно-издательский комбинат "Патент", г. Ужгород, ул,Гасарина, 101Изобретение относится к вычислительной технике ипредназначено для использования в быстродействующих непозиционных арифметических устройствах конвейерного типа для выполнения операции деления чисел, представленных в модулярной системе счисления.Известно устройство для деления, содержащее ре истр делителя, регистр деливычисления итерации, причем выход регистра делимого подключен к первому входу блока вычисления итерации, второй вход которого подключен к шине позиционого признака делимого, выход регистра делителя подключен к входу блока выбора элементар 20 ного делителя, третьему входу блока вычисления итерации и первому входу блока умножения, выход блока выбора элементарного делителя подключен к четвертому входу блока вычисления итерации, пятый вход которого подключен к шине позиционного признака делителя и второму входу блока умножения, третий вход которого подключен к первому входу сумматора, первому входу блока вычитания, первому входу бло 30 ка конца деления, выходу блока вычисленияитерации и входу блока конца итерации,выход которого подключен к второму входублока конца деления и шестому входу блокавычисления итерации, выход блока конца Э 5деления подключен к четвертому входу блока умножения, первому входу блока анализапроизведения, второму входу блока вычитания и второму входу сумматора, выход блока умножения подключен к второму входу 40блокаанализа произведения, выход которого подключен через блок режима работысумматора к третьему входу сумматора итретьему входу блока вычитания, выход которого подключен к седьмому входу блокавычисления итерации, выход сумматора соединен с выходом устройства,. Недостатками данного устройства являются невысокое быстродействие, обусловленное низкой эффективностьюприменяемого способа выполнения базовой операции -деления делителя и невязок.на степени числа 2 или первого модуля системы, а также большая погрешность приближения делителя,55Наиболее близким по технической сущности к предлагаемому является устройстводля деления чисел в системе остаточныхклассов, содержащее регистры делимого,делителя и частного, блок вычитания, блок мого, сумматор, блок выбора 10 элементарного делителя, блок умножения, блок вычитания, блок анализа произведения, блок конца итерации, блок конца деления, блок режима работы сумматора, блок сложения, четыре регистра, два преобразователя прямого кода в дополнительный, счетчик, узел задержки, блок масштабирования, два коммутатора и блок управления, в состав которого входят счетчик, два триггера, дешифратор, три элемента ИЛИ, элемент задержки, элемент НЕ и элемент И,причем первые информационные входы регистров делимого и делителя являются входами делимого и делителя устройства соответственно, выход регистра частного является выходом частного устройства и соединен с первым информационным входом блока сложения, выход которого соединен с информационным входом регистра частного, вход запуска устройства является входом элемента задержки блока управления и соединен с входом элемента НЕ, первыми входами первого и второго элементов ИЛИ, входом разрешения сброса счетчика и входом установки в единицу триггера блока управления, входом разрешения записи регистра делителя, тактовым входом узла задержки и входом сброса счетчика устройства, выход регистра делимого соединен с входом уменьшаемого блока вычитания, выход которого соединен с информационным входом первого регистра, выход которого соединен с входом первого преобразователя прямого кода в дополнительный, первой группой информационных входов первого коммутатора и вторьм информационным входом регистра делимого, выход регистра делителя соединен с первым информационным входом блока умножения, выход которого соединен с информационным входом второго регистра, выход которого соединен с входом вычитаемого блка вычитания, вход делителя устройства соединен с первыми информационными входами третьего и четвертого регистров, выход третьего регистра является выходом остатка устройства и соединен с входом остаточного кода блока масштабирования, первь 1 й и второй входы номера масштаба которого соединены с первым выходом узла задержки и информационным выходом счетчика, второй выход узла задержки соединен с входом младших информационных разрядов счетчика, выход которого соединен с входом узла задержки, выход первого преобразователя прямого кода в дополнительный соединен с вторым информационйым входом второго регистра, выход блока масштабирования соединен с вторым информационным входом четвертого регистра, выход которого соединен с вто-. рыми информационными входами блоков умножения и сложения, с первой группой информационных входов второго коммутатора, входом второго преобразователя прямого кода в дополнительный и входом де- тнойструктуройалгоритмаделения, Примешифратора блока управления, выход второ- нение общего блока масштабирования наго преобразователя прямого кода в этапах аппроксимации делителя и реализадополнительный соединен с вторым инфор- ции схемы Ферма не позволяет организомационным входом второго коммутатора, 5 вать в известном устройстве совмещение вовыход которого соединен с входом старших времени процесса выполенния несколькихинформационных разрядов счетчика;-выход операций деления. Это не дает воэможноэлемента НЕ блока управления соединен с сти использования данного устройства ввходом разрешения записи первого регйст- сверхбыстрых вычислительных устройстра и входом синхронизации блока масшта вах,бирования, выход второо элемента. ИЛИ Цельизобретения - повышениебыстроблока управления соединен с входом разре-действия устройства.шения записи регистра делимого и третьего Поставленная цель достигается путемрегистра, выход (Т+ 4)-го разряда счетчика применения конвейерного принципа обраблока управления, где Т = 3 оц 2 КГ, где К - 15 боткимодулярныхкодовделимогоиделитечисло оснований системы счисления; Ц - ля и обеспечения возможности совмещенияцелая часть, соединен с входом разрешенйя во времени процессов выполнения Т+б опезаписи регистра частного, выход первого раций деления (Т = )оц 2 К, где К - числоэлемента ИЛИ блока управления. соединен оснований модулярной ситемы счисления;с входом разрешения записи четвертого ре х - наименьшее целое число, не меньше х),гистра, прямой выход первого триггера бло- в соответствии с чем в устройство для делека управления соединен с первым входом ния чисел в модулярной системе счисления,элемента И блока управления и счетным содержащее блок модульного вычитания,входом счетчика устройства. вход разреше- блок модульного умножения, регистр, блокния записи которого соединен с входами 25 модульного сложения, блок масштабировасброса второго и четвертого регистров и ния, первый узел задержки. первый и втовыходом элемента И блока управления, вы- рой коммутаторы и блок управления, вход второго триггера которого соединен с:состав которого входят дешифратор, элевходом управления первого коммутатора, мент ИЛИ, первый элемент И, первый входвыход элемента задержки блока управле- З 0 которого соединен с выходом дешифратора,ния соединен с информационным входом вход которого соединен с входом первогосчетчика блока управления, счетный вход слагаемогоблокамодульногосложения, выкоторого соединен с выходом третьего эле- ходом блока масштабирования, с входоммента ИЛИ блока управления, первый и вто- первого сомножителя блока модульного умрой входы которого соединены З 5 ножения, выходкоторогоСоединейсвходомсоответственно с первым выходом дешиф- регистра, выход которого соединен с вхоратора и инверсным выходом первого триг- дом вычитаемого блока модульного вычитагера блока управления, выходы нулевого и ния, введены третий. коммутатор,(Т+3)-го разрядов счетчика блока управле-, мультиплексор, с второго по шестой узлыния соединены с вторыми входами соответ задержки, блок формирования интеграль-ственно второго и первого элементов ИЛИ ных характеристик модулярного кода; блокблока управления, второй выход дешифра- присвоения знака, в блок управления дотора блока управления соединен с входом полнительно введены первый и второй региразрешения сброса первого триггера и вто- . стры сдвига, первый и второй кольцевыерым входом элемента И блока управления, 4 сдвиговые регистры, второй и третий элевторой выход дешифратора блока управле- менты И, причем входы делимого и делителяния соединен с информационным входом устройства соединены с первыми информавторого триггера блока управления и вхо- ционными входами соответственно первогодом управления второго коммутатора, тре- . и второго коммутаторов, выходы которыхтий выход дешифратора блока управления соединены с входами первого и второго уэявляется выходом окончания деления уст- лов задержки соответственно, вторые ин 50ройства. формационные входы первого и второгоИзвестное устройство реализует итера- коммутаторов соединены с первыми выхотивную процедуру деления по методу спу- дами второго и третьего узлов задержки соска Ферма с применением ответственно, выход переогоузлазадержкипараллельно-конвейерного блока масшта- . соединен с входом уменьшаемого блока мо 55бирования чисел, ориентированного на не- дульного вычитания, выход которого соедикоторый набор масштабов. Однако нен с входом третьего узла задержки.,пропускная способность устройства недо- второй выход которого соединен с первымстаточновысока,чтообусловленорекуррен- . входом блока присвоения знака, второйвход которого соединен с первым выходом четвертого узла задержки, второй выход которого соединен с первым информационным входом мультиплексора, выход которого соединен с входом четвертого узла задержки, второй информационный вход мультиплексора соединен с первь 1 м выходом блока формирования интегральных характеристйк модулярного кода, второй выход которого соединен с первым информаионным входом третьего коммутатора, второй информационный вход которого соединен с выходом пятого узла задержки, вход которого соединен с выходом третьего коммутатора и первым входом блока масштабирования, второй вход которого соединен с выходом блока присвоения знака, выход блока модульного сложения соединен с входом шестого узла задержки, выходкоторого соединен с выходом частного устройства и входом второго слагаемого блока модульного сложения, второй выход второго узла задержки соединен с входом второго сомножителя блока модульного умножения, вход делителя устройства соединен с входом блока формирования интегральных ха рактеристик модулярного кода, вход запуска устройства соединен с входом сброса шестого узла задержки и с установочными входами первого и второго регистров сдвига и входами сброса первого и второго кольцевых сдвиговых регистров, входы упрэвления сдвигом которых соединены с одноименными входами первого и второго регистров сдвига и с тактовым входом устройства, выход старшего разряда первого регистра сдвига соединен с входом младшего разряда первого кольцевого сдвигового регистра, выход которого соединен с первым входом второго элемента И, второй вход которОго соединен с выходом третьего элемента И, входы которого соединень 1 с выходами разрядов второго кольцевого сдвигового регистра, вход младшего разряда которого соединен с выходом первого элемента И, первый выход второго регистра сдвига соединен с управляющими входами первОго и второго коммутаторов, второй выход второго регистра сдвига соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом старшего разрядавторого кольцевого сдвитового регистра, выход элемента ИЛИ соединен с входом блокировки блока масштабирования, третий выход второго регистра сдвига соединенс вторым входом первого элемента И, четвертый и пятый выходы второго регистра сдвига соедйнены с управляющими входами третьегЬ коммутатора и мультиплексора соответственно, выход второго элемента И10 20 соединен с выходом признака окончания деления устройства.Таким образом, существенное отличие предлагаемого устройства длл деления чисел в модулярной системе счисления заключается в том, что для формирования приближения делителл и вычисления знакаделителя используется не блок масштабирования, а отдельный блок параллельноконвейерного типа для формированияинтегральных характеристик модулярного кода, обращение к которому можно производить ежетактно, т.е, с частотой т = 1/тм,т, где тм,т, - длительность модульного такта. Это позволяет организовать совмещение во времени выполнения в устройстве до Т+6 операций деления, базирующихся на итеративной процедуре по методу спуска Ферма.Нэ фиг,1 и 2 представлена структурналсхема устройства для деления чисел в модуллрной системе счисленил; нэ фиг,З - структурная схема блока управления,Устройство содержит вход 1 делимого, вход 2 делителя, вход 3 запуска и тактовый вход 4 устройства, первый 5 и второй 6 коммутаторы, блок 7 управления, первый 8 ивторой 9 узлы задержки, формирователь 10 интегральных характеристик модуллрного кода, блок 11 модульного вычитанил, блок 12 модульного умножения, мультиплексор 13, третий узел 14 задержки, регистр 15, четверытй узел 16 задержки, блок 17 присвоенил знака, третий коммутатор 18, блок 19 модульного сложения, блок 20 масштабирования, пятый 21 и шестой 22 узлы задержки, выход 23 частного и выход 24 признакаокончания деления устройства,Входы делимого 1 и делителя 2 устройства подключены к первым информационным входам соответственно первого 5 ивторого б коммутаторов, которые содержат по А=Ь мультиплексоров, гдеЬ = 11092 гп = 1, 2 к), где ю 1, гп 2пм -45 основания модулярной системы счисления,являющиеся попарно простыми целымичислами, т.е. гль щ) = 1; , ) = 1, 21; Ф ).В состав блока 7 управленяи входлтпервый 25 и второй 26 регистры сдвига,50 дешифратор 27, первый 28 и второй 29кольцевые сдвиговые регистры, первый30, второй 31 и третий 32 элементы И иэлемент ИЛИ 33,Разрядность первого 25 и второго 2655 регистров сдвига составляет соответственно Т+ 1 и 2 Т+ 8 бит,Инверсный выход (Т+4)-го разряда, п рямой и инверсный выаоды 2 Т+5)-го разряда,прямой выход 2 Т+б)-го и инверсный выходход старшего разряда первого кольцевогосдвигового регистра 28 и выход третьегоэлемента И 32 соединены с первым и вторым входами второго элемента И 31.5 Выходы первого 5 и второго 6 коммутаторов соединены соответственно с входамипервого 8 и второго 9 узлов задержки, вторые информационные входы первого 5 ивторого 6 коммутаторов подключены к пер 10 вым выходам соответственно третьего 14 ивторого 9 узлов задержки,Первый узел 8 задержки представляетсобой цепочку из Т+2 последовательно соединенных регистров разрядностью Лбит,15 вход первого и выход последнего иэ которых являются соответственно входом и выходом узла задержки,Второй узел 9 задержки представляетсобой цепочку из Т+6 последовательносое 20 диненных регистров разрядностью Лбит;вход первого регистра является входом узлазадержки, выходы (Т+6)-го.и Т+1)-го регистров являются соответственно первым и вторым выходами узла Задержки.Управляющие входы первого 5 и второго 6 коммутаторов объединены и подключены к первому выходу второго регистра 26сдвига блока 7 управления, Выход первогоузла 8 задержки подключен к входу умень 0 шаемого блока 11 модульного вычитания,вход вычитаемого которого Соединен с выходом регистра 15. Второй выход второгоузла 9 задержки соединен с входом второгосомножителя блока 12 модульного.умноже 5 ния, выход которого подключен к входу регистра 15.Формирователь 10 интегральных характеристик модулярного кода является известным устройством, представляющим собой0 усеченный вариант параллельно-конвейер-ного устройства для формирования интегральных характеристик модулярйого кода,быстродействие которого составляет Т+ 3такта при пропускной способности одна5 операция в один такт. Формирователь 10 повходному модулярному оду (х 1, Х 2,х) числа Х из диапазона О модулярной системысчисления осуществялет Формированиелишь двух характеристик: знака 3(Х)Е(0,1)числа Х и номера 1 масштаба 31, аппроксимирующего абсолютную величину Хчисла Х: е(Х) = х =Хщ; (3 = 1, 2,с); пцс 2 п 1 о+ 1 - 2; кМи = Г 7 в; 2цУп обозначается наименьший неотрицательный вычет, сравнимый с величиной Упо модулю е, Дешифратор 27 реализуется,как в известном устройстве.Разрядность первого 28 и второго 29кольцевых сдвиговых регистров составляетТ+ 6 бит,Установочные входы первого 25 и второго 26 регистров сдвига и входы сброса 3первого 28 и второго 29 кольцевых сдвиговых регистров объединены и подключены квходу 3 запуска устройства, входы управления сдвигом первого 25 и второго 26. регистров сдвига, первого 28 и второго 29 4кольцевых сдвиговых регистров объединены и подключены к тактовому входу 4 устройства, выход старшего разряда первогорегистра 25 сдвига соединен с входом млад-.шего разряда первого кольцевого сдвигового регистра.28, выход дешифратора 27 итретий выход второго регистра 26 сдвигаподключены соответственно к первому ивторому входам первого элемента И 30, выход которого соединен с входом младшего 50разряда второго кольцевого сдоигового регистра 29. Второй выход второго регистра26 сдвига и выход старшего разряда второгокольцевого сдвигового регистра 29 соединены соответственно с первым и вторым входами элемента ИЛИ 33, Выходы всехразрядов (с нулевого по (Т+ 5)-й) второгокольцевого сдвиговаго регистра 29 подключены к входам третьего элемента И 32, выО,еслиХ О,(2 Т+7)-го разрядов второго регистра 26 сдвига (разряды номеруются начиная с 0) являются его выходами с первого по пятый,Дешифратор 27 предназначен для формирования сигнала е (Х), задаваемого соот- ношением 1, если Х Е(-1, О, 1),(1)0 в остальных случаях где Х - входная переменная, заданнаясвоим модулярным кодом (х 1, х 2 х) и принадлежащая диапазону 0 =(-що М.1,.гпо х хМ+ 1,.,Во М.1 - 1) модулярной системы счисления; тп - вспомогательный модуль, выбираемый из условий а1 - 1; Номер масштаба Я определяется по правилуи - номер старшей ненулевой цифры симметрического полиадического представления х 1+ х 2 М 1+ , +х 1; Укчисла ХеО;х, е т.и-и"+ З. 11 0 = 1. 2,я); Гу 3 - целая часть действительного числа у;У 1= Г 1 в 1;=зе, - номер старшего ненулевого разряда в двоичном представлении числа Х=1 х -1+ х вУ; Л - количество старших двоичных разря- дов числа ХЗ, используемых для определения масштаба Яь который имеет вид В применяемой модификаации формирователя 10 в отличие от известного устройства для формирования интегральных " характеристик модулярного кода в память соответствующего ( ю - 1)-го ( ю = 2, ЗК) формирователя номера номирующего множителя по адресу хс+ 2 хзаписывается величина 1 х .,+ хазп 1 вт т Мат-гт2" г х 1, если х 0,где х =х 1 + п 1;, если х0 .Величины Я(Х) и 1 снимаются с первого и второго выходов формирователя 10 интечгртаЛьнызях характеристик модулярного кодаз собтвечтственно на (Т+ 2)-м и (Т+ 3)-м тактах.- Ьход ч 10 формирователя интеральных характеристик модулярного кода подключен к входу делителя 2 устройства, первый и второй выходы формирователя 10 соединены с первыми информационными входами мультиплексора 13 и третьего коммутатора 18 соответственно.Блоки модульного вычитания 11, модульного умножения 12 и модульного сложения 19 состоят соответственно из 35 40 45 50 55 наборов вычитателей, умножителей и сумматоров по модулям а 1, а 2,щ и служат для выполнения соответствующих операций над модулярными кодами целых чисел из диапазона О модулярной системы счисления.Выход блока 11 модульного вычитания соединен с входом третьего узла 14 задержки, второй выход которого подключен к первому входу блока 17 присвоения знака, Первый информационный вход и выход мультиплексора 13 соединены соответственно с вторым выходом и входом четвертого узла 16 задержки. Управляющие входы мультиплексора 13 и третьего коммутатора 18 подключены соответственно к четвертому и пятому выходом второго регистра 26 сдвига блока 7 управления. Первый выход четвертого узла 16 задеркки соединен с вторым входом блока 17 присвоения знака,Третий узел 14 зодеркки представляет собой цепочку из четырех последовательно соединенных регистров разрядностью Лбит; вход первого регистра является входом узла задержки, выходы четвертого и первого регистров являются соответственно первым и вторым вь 1 ходами узла задержки.Четвертый узел 16 задержки представляет собой цепочку из Т+6 последовательно соединенных одноразрядных регистров, вход первого регистра является входом узла задержки, выходы первого и последнего регистров являются соответственно первым и вторым выходами узла задержки.Блок 17 присвоения знака осуществляет преобразование модулярного кода числа Х е О в модулярный код числа Х = Х (-1)), где Я(У)я(0,1) - знак числа Уа О, Уодулярный код (х, х 2 х) числа Х и величина 8(У) поступают на первый и второй входы блока 17 соответственно, Блок 17 присвоения знака реализуется с помощью К долговременных зопомйна 1 оьцих устройств,Ьс+11-е из которых обладает емкостью 2слов разрядностью Ь бит и в память которого ПО адресу й ч 2 " ЯУ) записывается вычетхаев 1 Х Ь;=- хг(-1) 1 п 1;( - 1, 2," 3)( )Третий коммутатор 18 содержит 7 О 02 Ц мультиплексоров, где 1. - число масштабов, на которые рассчитан блок 20 масштабирования.Блок 20 масштабирования представляет собой известное устройство для масштабирования параллельно-конвейерного тило, быстродействие которого составляет Т+3 такта при пропускной способности одна операция масштабирования в один такт. Блок 20 масштабирования осуществляет деление входного числа Х е О на некоторыйположительный масштаб 5О, причем ичный код чилса -1, На первом выходе втоэто число ограничено и равно 1. Номер рого регистра 26 сдвига вырабатывается1 е(0, 11-1) масштаба Я и модулярнцй код сигнал О; 0 (где о - содержимое-го разчисла Х подаются соответственно на пер- ряда второго регистра 26 сдвига, / = О,вый и второй входы блока 20. Результатом 5 1,2 Т;- отрицание булевой величиныоперации масштабирования является оцен- о 1), который поступает на управляющие вхока (ближайшее целое число) дроби Х/Я 1, В ды первого 5 и второго б коммутаторов; Вблоке 20 функция блокировки выдачи нену- результате модулярный кдулярный кодлевой информации реализуется стандарт- (а 1, а, а)делимогоА, пОступающийным образом путем подключения к вцходу 10 на вход 1 делимого устройства, ерезна вход делимого устройства, через первыходного регистра блока группы элемен- вый коммутатор 5 передается в етов запрета, управляемой посредством вхо-8 задержки а модул рзадержки, а модулярный кодда блокировки.динен с вторым входом блока 20 масштаби коммутатор б пере а с9на вход делителя уст ойства, через второйкоммутатор передается во второй узел 9рования, первый вход которого объединен с задержки (а; = 1 Я 1 ,Д =1 В 1 П 1= 1, 2,.,К; А,входом пятого узла 21 задержки и подклю- . Вв Ь,ВО), О р ду р), дновременно с этим модулярчен к выходу третьего коммутатора 18; входдешифратора 27 блока 7 управления:, вход роУ Рд ный код делителя В с входа 2 делителя устройства поступает на вход формирователяпервого сомножителя блока 12 модульного 20 р р р ду р о 10 интегральных характеристик модулярноумножения и вход первого слагаемого блока го кода. После этого йачинается выполнение19 модульного сложения обьедиенц и под- опершиоперации деления числа Я на В,ключены к выходу блока 20 масштабирова- В б у рВвиду обеспечения в устройстве конния, вход блокировки которого соединен с вейерного режима выполнения не одной, авыходом элемента ИЛИ 33 блока 7 управлеУ Р 25 целой последовательности бпераций деления, второй информационный входтретьего ния, начиная с и-го такта рассматриваемойкоммутатора 18 соединен с выходом пятогоузла 21 задержки,операции, в устройстве может быть инициировано (и+ 1) операций деления (и = О,Пятый 21 и шестой 22 узлы задеРжки 1 Т+5)тметим, что на каждом такте работыосуществляют задержку информации на Т+ 306 тактов. Разрядность регистров, входящихв состав пятого 21 и шестого 22 узлов задерустройства по сигналу Гт = 1, подаваемому, на тактовый вход 4 устройства, содержижки, состаляет соответственно )1 о 92 Ц и мое пер о 25 р о 26 р с Ровмое первого 25 и второго 26 регистровЛ бит. Входы сброса регистров шестого сдвига, первого 28 и второго 29 кольцевыхузла 22 задеРжки в совокупности состав сдвиговь ре с р б 7 у рсдвиговых регистров блока 7.управленияляют вход сброса узла задержки.д Р сдвигается на один бит в сторону старшихВход сброса шестого узла 22 задержкиразрядов.подключен к входу 3 запуска устройства; На первом такте реализуемой процедувход второго слагаемого и выход блока 19 ры деления формирователь 10 интегральмодульногосложениясоединенысоответст 40 ных харак ери40 ных характеристик модулярного кода"венно с выходом и входом шестого зла 22задержки, выходы шестого узла 22 задерж- мас а б с; Вки и второго элемента И 31 блока 7 управлемасшат а= В, аппроксимирующего абсолютную величинуВ делителя В,ния являются выходом 23 частного и лю Н(Т+1).чр у:1 ра ( + 1)-м такте содержимое 7 = 1 старвыходом 24 признака окончания деления 45 шего разряда первого регистра 25 сдвигаустройства соответственно,Вблока 7 управления передается в младшийРассмотрим, как работает предлагаеразряд первого кольцевого сдвигового регимое устройство для деления чисел в моду- стра лока 7 управления.лярной систЕме счисления, Начиная с (Т+1)-го такта реализуемаяНа начальном (нулевом) такте по.сигналу Гупр = 1, подаваемому на вход 3 запуска50 процедура деления носит итеративный хад У - рактер, Все итерации имеют одинаковуюшестого Узла 22 задеРжки, а также пеРвый Н р р р цдлительность, а именно Т+ тактов,На первом такте первой итерации моду 28 и второй 29 кольцевые сдвиговые регист- лярный код делителя В с второго йцходары блока 7 управления обнуляются; в первом регистре 25 сдвига блока 7 управлениявторого узла 9 задержки поступает на входвторого сомножителя блока 12 модульногоустанавливается (Т+ 1)-разрядный двоичумножения, на вход первого сомножителяный код числа 1, во втором регист е 26д Р Р с Ре 26 которого с выхода блока 20 масыабировасдвига блока 7 управления устанавливается (2 Т+ 8)-разрядный дополнительный двония подается модулярнцй код числа Оо = 0-го разряда ( =- О, 1Т+5) второго кольцевого сдвигового регистра 29 блока 7 управления. В результате блок 12 модульного умножения получает произведение В О = О, код которого передается в регистр 15. Кроме этого,модулярный код числа Оо = 0 с выхода блока 20 масштабирования подается на вход первого слагаемого блока 19 модульного сложения, на вход второго слагаемого которого с выхода шестого узла 22 задержки поступает модулярный код числа 0-1 = О. Блок 19 модульного сложения формирует модулярный код суммы 0+ 0-1= О, который записывается в первый регистр шестого узла 22 задержки. Одновременно с этим модупярный код числа Оо= 0 поступает на вход дешифратора 27 блока 7 управления. В соответствии с соотношением (1) на выходе дешифратора 27 генерируется сигнал е(00) = 1, поступающий на первый вход первого элемента ИЛИ 30 блока 7 управления, на второй вход которого с третьего выхода второго регистра 26 сдвига подается нулевой сигнал о 2 т+б = О. В результате в младший разряд второго кольцевого сдвигового регистра 29 блока 7 управления с выхода первого элемента И 30 поступает сигнал Г 1= е (Оо )д,.= 0 и, таким образом, на данной итерации процедуры деления не происходит изменения содержимого второго кольцевого сдвигового регистра 29, .На втором такте первой итерации модулярный код делимого А =- Ао с выхода первого узла 8 задержки и содержимое регистра 15(код числа 0) подаются соответственно на входы уменьшаемого и вычитаемого блока,11 модульного вычитания, Блок 11 формирует разность А 1 = А 0 - 0 = А, которая передается в третий узел 14 задержки; Одновременно с этим формирователь 10 интегральных характеристик модулярного кода завевешает вычисление знака 3(В) делителя В, Двухзначная величины Я(В) спервого выхода формирователя 10 через мультиплексор 13, на управляющий вход которого подается сигнал сгг;-1, поступает в четвертый узел 16 задержки.На третьем такте первой итерации модулярный код числа А 1 с второго выхода третьего узла 14 задержки и знак 3(В) делителя В с первого выхода четвертого узла 16 задержки подаются нэ первый и второй входы блока 17 присвоения знака. Полученный блуком 17 модулярный код числа Й 1 = А (-1) ) поступает в блок 20 масштабирования через еторой его вход, Кроме этого, нэ данном такте формирователь 10 интегральных характеристик модулярного кода завериает вычисление номерамасштаба Я = В. Величинас второго выхода формирователя 10, проходя через третий коммутатор 18. на управляющий вход которого подается сигнал (т= О, поступает в блок 20 масштзбирования через первый его вход, з также записывается в пятый узел 21 задержки.На четвертом такте первой итерации блок 20 масштабирования начинает вычисление модулярного кода оценки О дроби иА.На шестом такте первой итерации модулярный код числа А 1 с первого выхода третьего узла 14 зэдеркки поступает на второй информационный вход первого коммутатора 5, на управляющий вход которого подается сигнал п= 1, в результате код числа А передается в первый узел 8 задержки. Одновременно с этим модулярный кодделителя В с первого выхода второго узла 9 задержки через второй коммутатор 6 (от,= 1) передается во второй узел 9 задержки.На последнем (Т+6)-м такте первой итерации блок 20 масштабирования завершает вычисление модулярного кода оценки О дроби Р 1/В.На первом такте /-й итерации 0 - 2, 3.,) модуля рный код числа О.1 с выхода блока 20Р.)МаСШтабИрОВаНИя (Гбл= 02 т.Ь ЧОГАН = 0) ПОдается на вход первого сомножителя блока 12 модулярного умножения и вход первого слагаемого блока 19 модульного сложения, на входы второго сомножителя и второго слагаемого которых поступают соответственно модулярный код делителя В с второго выхода второго узла 9 задержки и модулярный- 2- 2код суммы , О = Х О (0-1= 00= О) с1= - 1 1=1выхода шестого узла 22 задержки. В результате блок 12 модульного умножения получает произведение ОВ, модулярный код которого записывается в регистр 15, а на выходе блока 19 модульного сложения фор - 1мируется код суммыО, который пере=1дается в шестой узел 22 задержки,Нз втором такте )-й итерации модупярный код числа Ас выхода первого узла 8 задержки и содержимое регистра 15 (код числа ОВ) подаются соответственно на входы уменьшаемого и вычитаемого блока 11 модульного вычитания, в результате чего на выходе блока 11 формируется разность А = А- 01-В, модулярный код которой передается е третий узел 14 задержки. Одновременно с этим знак Я(В) делителя В с 5 10 15 20 25 30 35второго выхода четвертого узла 16 задержки поступает на первый информационный вход мультиплексора 13, на управляющий вход которого подаеся сигнал О,"= О, поэтому величина Я(В) передается на вход четвертого узла 16 задержки.На третьем такте )-й итерации модулярный код числа А 1 с второго выхода третьего элемента 14 задержки и знак Я(В) с первого выхода четвертого узла 16 задержки подаются на первый и второй входы блока 17 присвоения знака, Получаемый блоком 17 модулярный код числа В 1 = А 1(-1)поступает в блок 20 масштабирования через второй его вход, Кроме этого, номер 1 масштаба Ь= В с выхода пятого узла 21 задержки поступает на второй информационный вход третьего коммутатора 18, на управляющий вход которого подается сигнал (т,+= 1, В результате величина 1 поступает в пятый узел 21 задержки, а также в блок 20 масштабирования, который со следующего такта итерации начнет вычисление модулярного кода оценки О дроби ЯуИ,На шестом такте )-й итерации модуляркые коды числа А 1 с первого выхода третьего узла 14 задержки и делителя В с первого , выхода второго узла 9 задержки через первый 5 и второй 6 коммутаторы, на управляющие входы которых поступает сигнал о= 1, пеоедаются на входы первого 8 и второго 9 узлов задержки соответственно.На заключительном, Т+ 6-м, такте )-й итерации блок 20 масштабирования получа. ет модулярный код оценки 01 дроби В 1/В.Описанная последовательность действий повторяется до тех пор, пока по окончан ии н е кото рой г-й итера ци и (г1) н а выходе блока 20 масштабирования не будетполучен модулярныи код числа Огб("1, О, 1), В этом случае на первом такте (г+1)-й итерации ь соответствии с соотношением (1) на выходе дешифратора 27 блока 7 управления генерируется сигнал я (СЬ) = 1, поступающий на первый вход первого элемента ИЛИ 30, на второй вход которого с третьего выхода второго регистоа 26 сдвига подается единичный сигнал Оа.= 1, В результате младший разряд второго кольцевого сдвигового регистра 29 установится в единичное состояние, так как в него с выхода первого элемента И 30 поступает сигнал Г 1= Е(0 г) с=1, Одновременно с этим блок 19 модульного сложения получает модулярный код искомого частного 0= Я О;, который передается в шестой узел 22 задержки,Процесс выполнения инициированнойгруппы из Т+6 операций деления продолжается до тех пор, пока все они не завершатся,В момент получения блоком 19 модульного5 сложения соответствующего чаСт кого вовтором кольцевом сдвиговом регистре 29блока 7 управления все разряды будутустановлены в единичное состояние. Предположим, что последняя завершенная операция10 деления инициировалась на и-м такте работы устройства (и = О, 1Т+5). Тогда в целяхполучения результатов реализованных операций деления в порядке их инициации работа устройства продолжается еще Т - п+ 515 тактов, т,е. до момента появления на выходе23 признака окончания деления устройстваединичного сигнала. В течение очередныхТ+6 тактов полученные частные последовательно снимаются с выхода 24 устройства и20 на этом процесс выполненйя группы операций деления заканчивается, В такте сьемапоследнего частного в устройстве можетбыть начата инициация новой группы операций,Из прйведенного описания видно, чтовключение в состав предлагаемого устройства отдельного блока для аппроксимацииделителя (параллельно-конвейерногоформирователя интегральных характери 30 стик модулярного кода с частотой обращения 1= 1 йм.т) дает возможностьсовмещать во времени процессы выполнения Т+6 операций деления, Таким образом,предлагаемое решение йозволяет увели 35 чить быстродействие предлагаемого устройства в сравнении с известным в Т+6 раз.Если, например, используется модулярнаясистема счисления с числом оснований К= 8,то достигается девятикратное увеличение40 быстродействия.Ф о р мул а изобретен ия Устройство для деления чисел в моду лярной системе счисления, содержащееблок модульного вычитания, блок модульного умножения, регистр, блок модульного сложекия, блок масштабирования, первый узел задержки, первый и второй коммутаторы и блок управлекия, в состав которого входят дешифратор, элемент ИЛИ и первый элемент И, первый вход которого соединен с выходом дешифратора,. вход которого соединен с входом первого слагаемого блока модульного сложения, выходом блока масштабирования, входом первого сомножителя блока модульного умножения, выход которого соединен с входом регистра, выход которого соединен с входом вычитаемого блока модульного вычитания, о т л и ч а ю

Смотреть

Заявка

4880868, 02.11.1990

НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ПРИКЛАДНЫХ ФИЗИЧЕСКИХ ПРОБЛЕМ ИМ. А. Н. СЕВЧЕНКО

КОЛЯДА АНДРЕЙ АЛЕКСЕЕВИЧ, СЕЛЯНИНОВ МИХАИЛ ЮРЬЕВИЧ, ЧЕРНЯВСКИЙ АЛЕКСАНДР ФЕДОРОВИЧ, АХРЕМЕНКО ВАЛЕРИЙ НИКОЛАЕВИЧ

МПК / Метки

МПК: G06F 7/72

Метки: деления, модулярной, системе, счисления, чисел

Опубликовано: 23.08.1992

Код ссылки

<a href="https://patents.su/11-1756887-ustrojjstvo-dlya-deleniya-chisel-v-modulyarnojj-sisteme-schisleniya.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для деления чисел в модулярной системе счисления</a>

Похожие патенты