Устройство для сжатия чисел и вычисления полинома

(51)5 0 06 Р 7/54 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ, СССР ОПИСАНИЕ ИЗОБРЕТЕНИК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ М )а стройства - ния, так как раниченная о не позво(21) 4768991/24(56) Авторское свидетельство ССС М 885997, кл. 6 06 Р 7/544, 1979.Авторское свидетельство СССР М 1464156, кл. 6 06 Р 7/544, 1987.(54) УСТРОЙСТВО ДЛЯ СЖАТИЯ ЧИСЕЛ И ВЫЧИСЛЕНИЯ ПОЛИНОМА(57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях, Цель изобретения состоит в расширении области применения за счет дополнительной возможности сжатия чисел. Устройство содерИзобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях,Известно устройство для вычисления полинома и-й степени, содержащее сумматор, линии задержки, регистр.Недостаток устройства - ограниченная область применения, так как оно не позволяет сжимать цифровые данные, поступающие на вход устройства, его сложность.Известно также устройство для вычисления полинома и-й степени, содержащее сумматор, группу элементов задержкирегистр.Недостаток у огобласть примене он жит два регистра, два коммутатора, две группы элементов задержки, сумматор, сумматор произведений, группу умножителей, Сущность изобретения состоит в реализации возможности производить сжатие исходных чисел за счет уменьшения количества значащих двоичных разрядов, требуемых для представления сжатых чисел в сравнении с исходными, при этом устройство осуществляет сжатие на основе соотношения У= а 1(макс(а 3)+ 1) + а 2 (макс(а;)+ + 1)" 2++ ап, где У - сжатое число; а - цифры числа; а = 1,п; сжатое число при необходимости восстанавливается поэлементно в исходное последовательным его делением на макс(а) + 1, остатки от деления справа налево, начиная с последнего частного, и составляет исходное число. 1 ил 1 табл. ляет сжимать цифровые данные, поступающие на вход устройства.Цель изобретения - расширение области применения за счет введения дополнительной возможности сжатия чисел.Поставленная цель достигается тем, что в устройство для сжатия чисел и вычисления полинома, содержащее первый регистр, сумматор и первую группу последовательно соединенных элементов задержки, дополнительно введены блок сравнения, два коммутатора, второй регистр, сумматор произведений, группа умножителей и вторая группа элементов задержки, причем устройство содержит соединенные по входам блок сравнения и через информационные входы первый коммутатор, выход блока5 10 15 20 25 30 35 40 50 сравнения соединен с адресным входом первого коммутатора, первый и второй информационные входы второго коммутатора, адресные входы которого соединены с входом задания режима устройства, вход стробирования устройства соединен с входом стробирования второго коммутатора, выход второго коммутатора соединен с входом второго сомножителя первого умножителя груп и ы умножителей, последовательно соединенных посредством входа первого сомножителя, и входом первого элемента задержки, последовательно соединенной второй группы элементов задержки, вход логической единицы устройства соединен с первым входом второго регистра и входом первого сомножителя первого умножителя группы, выходы элементов задержки второй группы с первого по (и - 2)-й элемент, где и - количество цифр в сжимаемом числе, соединены с входами вторых сомножителей соответствующих умножителей с второго по (и - 1)-й группы, выходы умножителей с первого по(п - 1)-й группы соединены соответственно с входами с второго по и-й второго регистра, вход стробирования второго регистра соединен с входом стробирования сумматора произведений, входы второго операнда которого соединены с выходом второго регистра, выход сумматора произведений, выход основания сжимаемого числа устройства.Первый коммутатор служит для реализации логической функции с целью передачи на вход сумматора числа, соответствующего макс(а), где а - одноразрядная цифра сжимаемого числа,= 1,п, является стандартным элементом и И-ИЛИ.Второй коммутатор служит для реализации логического управления с целью разрешения режима сжатия чисел или вычисления полинома, является стандартным элементом 2 И - ИЛИ, второй вход,первого элемента И которого инверсный.Сумматор произведений служит для вычисления сумм произведений с целью получения сжатого числа или полинома и-й степени, является известным элементом,Блок сравнения служит для реализации логической функции "Больше" с целью сравнить а-числа, поступающие на его вход, и разрешить передачу на выход первого коммутатора числа, равного макс(а), является стандартным элементом.Группа умножителей служит для умножения поступающих на информационные входы данных с целью получения элементов степенного ряда, они являются стандартными последовательно соединенными посредством первого сомножителя элементами.Второй регистр служит для накопления асинхронно поступающих на его информационные входы данных с целью последующей одновременной подачи данных при поступлении стробирующего импульса на входы первого и второго операндов сумматора произведений, является стандартным элементом.Вторая группа элементов задержки служит для задержки прохождения числа на один такт через каждый элемент, они являются стандартными последовательно соединенными элементами.Сущность изобретения состоит в расширении области применения, что достигается путем реализации возможности производить сжатие исходных чисел за счет уменьшения количества значащих двоичных разрядов, требуемых для представления сжатых чисел в сравнении с исходными, при этом сжатое число А получаем из следующего соотношения А = а 1 (макс(а) + 1)"++ а 2(макс(а;)+1)" + , + а,где = 1,п.Сжатое число при необходимостивосстанавливается поэлементно в исходное последовательным его делением намакс(а)+ 1, остатки от деления слева направо и составят исходное число.На чертеже изображена блок-схемапредлагаемого устройства,Устройство содержит вход 1 сжимаемого числа устройства, первый регистр 2, сумматор 3 произведений, второй регистр 4,коммутатор 5, вторую группу 6 элементов задержки, вход 7 задания режима работы устройства, вход 8 основания полинома устройства, выход 9 основания сжимаемого числа устройства, выход 10 сжатого кода числа устройства, блок 11 сравнения, коммутатор 12, сумматор 13, вход 14 логической единицы устройства, вход 15 стробирования устройства, первая группа 16 элементов задержки, группа 17 умножителей, причем вход 1 сжимаемого числа устройства соединен с информационным входом первого регистра 2 блока 11 сравнения и информационным входом первого коммутатора 12, выход блока 11 сравнения соединен с адресным входом первого коммутатора 12, выход которого соединен с входом первого слагаемого сумматора 13, вход второго слагаемого которого соединен входом 14 логической единицы устройства, выход10 15 20 25 30 35. 40 45 50 55 сумматора 13 - с первым информационным входом второго коммутатора 5, второй информационный вход и адресные входы которого соединены соответственно с входом 8 основания полинома устройства и входом 7 задания режима устройства, вход 15 стробирования устройства соединен с входами стробирования сумматора 13, второго коммутатора 5; первого элемента задержки первой последовательно соединенной группы 16 и первого умножителя последовательно соединенной посредством первых суммирующих входов группы 17 умножителей, выход второго коммутатора 5 соединен с входом второго сомножителя первого умножителя группы 17 и входом первого элемента 6 задержки второй последовательно соединенной группы, вход 14 логической единицы устройства соединен с первым входом второго регистра 4 и входом первого сомножителя первого умножителя группы 17, выходы с первого по (п - 2)-й элементов 6 задержки второй группы, где и - количество цифр в сжимаемом числе, соединены.соответственно с входами вторых сомножителей умножителей с второго по (и)-й группы 17, входы стробирования, начиная с второго умножителя группы 17, соединены соответственно с выходами элементов 16 соответственно с первого по (и)-й задержки первой группы, выходы умножителей 17 с первого по(п - 1)-й группы соединены соответственно с входами с второго по и-й второго регистра 4, выход (п)-го элемента 16 задержки первой группы соединен с входом стробирования второго регистра 4, первого регистра 2 и сумматора 3 произведений, входы первого и второго операндов которого соединены с выходами соответственно первого 2 и второго 4 регистров, выход сумматора 3 произведений соединен с выходом 10 сжатого кода числа устройства, выход 9 основания сжимаемого числа устройства соединен с выходом сумматора 13,Устройство работает следующим образом.С началом работы устройства с входа 15 стробирования устройства стробирующий импульс задает напрямую и через первую группу 16 элементов задержки последовательность работы стробируемых элементов (сумматор 13, коммутатор 5, группа 17 умножителей, второй регистр 4, сумматор 13 произведений, первый регистр 2), на вход 7 задания режима устройства подан логический "0", что соответствует выбору режима сжатия числа, при этом второй коммутатор 5 запрещает прохождение аргумента много- члена с входа 8 основания полинома устройства на .свой выход и разрешает прохождение числа, соответствующего выражению макс(а)+ 1 с выхода сумматора 13, сжимаемого число с входа 1 сжимаемого числа устройства подается (каждая в-разрядная цифра числа - с соответствующего входа), на первый регистр 2, где сжимаемое число хранится до поступления стробирующего импульса,Цифры сжимаемого числа с входа 1 сжимаемого числа устройства также поступают на блок 11 сравнения, который, используя признак "Больше", устанавливает логическую единицу по адресному 1-му входу первого 12 коммутатора, через информационный 1-й вход которого на его выход поступила большая цифра, соответствующая макс(а), далее следующая на первый суммирующий вход сумматора 13, с входа 14 логической единицы устройства через второй суммирующий вход сумматора 13 к макс(а) добавляется единица, в результате получаем число, соответствующее выражению макс(а) + 1, следующее на выход 9 основания устройства, которое через первый информационный вход второго коммутатора 5 поступает на первый вход первого умножителя группы 17 и далее через первую группу элементов 16 задержки на первые входы сомножителей остальных (и - 2)-х умножителей группы 17, соединение группы 17 умножителей и подача с входа 14 логической единицы позволяет последовательно, с прохождением стробирующего импульса, возводить цифру, соответствующую макс(а) + 1 в степень от 0 до (и) (так, с входа 14 логической единицы получаем "1", а на соответствующих выходах группы 17 умножителей х 1, х х, ., х" ), и по мере поступления данных накапливаются полученные величины степенного ряда с основанием, соответствующим макс(а) + 1 на втором регистре 4, с появлением стробирующего импульса, по времени совпадающим с окончанием вычисления на (и - 1)-м умно- жителе группы 17.Благодаря наличию второй группы 6 элементов задержки одновременно с второго регистра 4 первого регистра 2 данные поступают на входы первого и второго операндов сумматора 3 произведений, перемножаются соответственно первый операнд с первым, второй с вторым и т.д полученные произведения суммируются и результат выдается через выход сумматора 3 произведений на выход 10 сжатого кода числа устройства, следующий стробирующий импульс с входа 15 стробирования следует через время, равное Ьт(п - 1)+ Т, где Ь т - такт работы одного умножителя 17группы, и - количество коэффициентов (а), Т - время работы сумматора 3 произведений.В режиме вычисления полинома и-й степени с входа 7 задания режима устройства на адресные входы второго 5 коммутатора подается логическая единица, открывающая его второй информационный вход, импульс с входа 15 стробирования через первую 16 группу элементов задержки задает порядок работы элементов устройства, число, задающее основание полинома с входа 8 основания полинома устройства через второй информационный вход второго 5 коммутатора последовательно поступает на вход второго сомножителя первого умножителя 17 группы и через элементы б задержки второй группы на вход второго сомножителя остальных умножителей 17 группы, которые последовательно возводят число х в степень от 1 до (и) и накапливают полученные величины степенного ряда на втором 4 регистре, с входа 14 логической единицы устройства число "1" поступает на вход первого сомножителя первого умножителя 17 группы и первый вход второго 4 регистра, данные с первого 2 регистра и с второго 4 регистра, при подаче на их входы стробирования импульса с выхода последнего элемента 16 задержки группы, поступают на соответственно на первый и второй входы операндов сумматора 3 произведений, который перемножает первый операнд первого входа на первый операнд второго входа, второй на вторым и т.д., здесь же полученные произведения суммируются и результат выдается на выход 10 сжатого кода числа устройства, следующий стробирующий импульс со входа 15 стробирования следуетчерез время равное Лтоп - 1)+Т, где Лс - такт работы одного умножителя группы 17, и - количество коэффициентов (а), Т - время работы сумматора 3 произведений.Оценим технико-экономическую эффективность изобретения. Например, если на вход 1 сжимаемого числа устройства поступило число "130524", на сумматоре 13 получаем число 6, степенной ряд которого после возведения в степень группой 17 умножителей имеет вид 1, 6, б, 6, 6, б,4 3 5сумматор 3 произведений выполняет следующие действия Результат вычислений - число 11860, в двоичном представлении которому выделяется 14 разрядов против 17 разрядов исходного числа, т,е. выигрыш равен трем 55 7776+ 31296+ 0:216+ 5 36+ 2. 6+ 4 5 10 15 20 25 30 35 40 45 50 разрядам, и далее с увеличением количества чисел, поступающих на вход устройства, количество выигранных разрядов будет возрастать, что и подтверждается данными приводимой ниже таблицы оценки эффективности сжатия чисел для возможных вариантов чисел, которые могут поступать на вход устройства, в которой приведены граничные числовые данные до сжатия и после с учетом увеличения количества разрядов и макс(а) + 1 с указанием количества значащих двоичных разрядов для представления каждого граничного варианта, а также граничное выигранное количество двоичных разрядов в результате сжатия. Из таблицы следует, что при работе устройства в режиме сжатия чисел выигрыш в двоичных разрядах подтверждает эффективность изобретения,Таким образом, техническое преимущество заявляемого изобретения по сравнению с известным состоит в расширении области применения путем сжатия исходного числа, что позволяет сократить количество значащих двоичных разрядов, необходимых для его представления,Положительный эффект изобретения состоит в том, что при расширении области применения обеспечивается сжатие в П пак 10 / а (макс(а)+ 1) раз, что к=о к=опозволяет получать на выходе устройства числа, которые требуют меньшего количества значащих двоичных разрядов для своего представления, Устройство может использоваться в специализированных вычислителях. Формула изобретенияУстройство для сжатия чисел и вычисления полинома, содержащее первый регистр, сумматор и первую группу последовательно соединенных элементов задержки, о т л ич а ю щ е е с я тем, что, с целью расширения области применения путем обеспечения дополнительной возможности сжатия чисел, в него введены блок сравнения, два коммута-тора, второй регистр, сумматор произведений, группа умножителей и вторая группа элементов задержки, причем вход сжимаемого числа устройства соединен с информационными входами первого регистра и первого коммутатора и входом блока сравнения, выход которого соединен с адресным входом коммутатора, выход которого соединен с входом первого слагаемого сумматора, вход младшего разряда второго слагаемого которого соединен с входом логической единицы устройства, входом млад10 1725218 йакс 1 а)+ РазРяд 3 еМакс и йинвозможныечисла до ипосле сжатия Кол,двоич.разр.Выигрыш Кол,двоич.разо.Выигрыш Кол. двоич.рдзрею еа Выигрыш Макс и минвозможныечисла ло ипосле сжатия Кол.двоич.разр.Выигрыш Макс и мин Иакс и минвозможныечисла до ипосле сжатия возножные дои после сжатия 5 4 3 3 2-1 4414249 6 4 5 4 1-0 9 7 5 2 6 4 4 3 2-1 4 4 2 1 2-3 7 7 3 2 4"5 зз 3 15 22 12 8 5 11 2 10 3 2шего разряда первого сомножителя первого умножителя группы и входом младшего разряда первой группы входов второго регистра, выход сумматора соединен с первым информационным входом второго коммутатора, второй информационный вход и адресный вход которого соединены соответственно с входом основания устройства и входом задания режима устройства, тактовый вход которого соединен с входами стробирования сумматора, второго коммутатора, первого элемента задержки первой группы и первого умножителя группы, выход второго коммутатора соединен с входом второго сомножителя первого умножителя группы и входом первого элемента задержки второй группы, выходы с первого по (и - 2)-й элементов задержки второй группы, где и - количество цифр в сжи 12 10 7 5 5 15 14 8 7 18 17 10 8 8"9 22 20 12 10 10маемом числе, соединены с входами вторых сомножителей соответственно с второго по (и)-й умножителей группы, входы стробирования которых соединены с выходами со ответственно с первого по(п)-й элементовзадержки первой группы, выходы умножителей с первого по(п)-й группы соединены с входами соответственно с второй по и-ю групп разрядов сумматора произведений, 10 выход (и - 1)-го элемента задержки первойгруппы соединен с входами стробирования второго регистра, первого регистра и сумматора произведений, входы первого и второго операндов которого соединены с 15 выходами соответственно первого и второго регистров, выход сумматора произведений соединен с выходом сжатого кода числа устройства, выход основания которого соединен с выходом сумматора. з1 О1083-2161412104191741252320171462624191772927211725218 Накс (а)+1 Раз"Ряд Кол,Кол,Кол,Накс и минвозможныечисла до ипосле сжатия Колич,двоим,разр.Выигрыж Накс и минвозможныечисла до ипосле сжатия макс и минвозможныечисла до ипосле сжатия Накс и минвозможныечисла до ипосле сжатия двоич,Разр.Выигрыж двоич,разр,двоич,разр,Выигрыш Выигрыж вв 18 80 1 У 66 16 48 13 2 55 15 35 111725218 оставитель Э,Корольхред М.Моргентал Редактор В.Данко Те Корректор оизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 10 аказ 1177 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5