СПОСОБ СУММИРОВАНИЯ ЧИСЕЛ Российский патент 2000 года по МПК G06F7/50 

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

Известен способ сложения двоичных чисел, в котором, с целью ускорения процесса суммирования, формируют два слова: сумму по модулю 2 исходных слагаемых и конъюнкцию исходных слагаемых со сдвигом на один разряд влево, после чего одноименные разряды полученных слов разбивают на группы специальным образом. [Авторское свидетельство СССР N 176724, класс МКИ G 06 F 7/50, 1965].

Недостатком способа является то, что он применим только для двоичных чисел и, ускоряя каждую отдельную операцию сложения, не позволяет уменьшить количество операций сложения при полном переборном P-ичном суммировании n-разрядного числа X с массивом V n-разрядных чисел от 0 до Pⁿ, уменьшить разрядность сумматоров, повысить интегральное быстродействие суммирования чисел, а также перейти от степенной к линейной зависимости общего количества операций сложения от разрядности чисел.

Наиболее близким по технической сущности к изобретению является способ суммирования чисел, при котором суммирование производят параллельно во всех группах разрядов, на которые разделен сумматор, при этом в каждую группу разрядов условно прибавляют "единицу" или "нуль" переноса, а затем осуществляют выбор окончательного результата суммирования. [Авторское свидетельство СССР N 249050, класс МКИ G 06 F 7/50, 1969].

Недостатком способа является то, что он повышает только быстродействие каждой операции сложения, но не позволяет уменьшить количество операций сложения при полном переборном P-ичном суммировании n-разрядного числа X с массивом V n-разрядных чисел от 0 до Pⁿ, уменьшить разрядность сумматоров, повысить интегральное быстродействие суммирования чисел, а также перейти от степенной к линейной зависимости общего количества операций сложения от разрядности чисел.

Решаемая задача - создание способа суммирования чисел, в котором разбиение исходного числа на блоки, новое поблочное суммирование и формирование требуемых чисел позволило уменьшить количество операций сложения при полном переборном P-ичном суммировании n-разрядного числа X с массивом V n-разрядных чисел от 0 до Pⁿ, уменьшить разрядность сумматоров, повысить интегральное быстродействие суммирования чисел, а также перейти от степенной к линейной зависимости общего количества операций сложения от разрядности чисел.

Задача решается предлагаемым изобретением. Сущность изобретения заключается в том, что в способе суммирования чисел исходное n-разрядное P-ичное число X разбивают на k блоков x₁,...,x_i,...,x_k по m разрядов в каждом, производят параллельное на нескольких сумматорах или последовательное на одном сумматоре добавление единицы к каждому числу x₁,...,x_i,...,x_k с формированием в (m+1)-ом разряде "единиц" или "нулей" переноса, полученные числа записывают соответственно в массивы Z₁,...,Z_i,...,Z_k, повторяют эти действия P^m раз и получают (m+1)-разрядные массивы Z₁,...,Z_i,...,Z_k, содержащие в каждом P^m P-ичных чисел, формируют строки требуемого массива Y, причем в качестве текущих значений в каждом массиве Z₁,...,Z_i,...,Z_k выбирают первые числа, записывают их в первую строку и переходят к формированию следующей строки требуемого массива Y, в массиве Z₁ в качестве текущего значения выбирают следующую строку и записывают это число в первые m разрядов, затем переходят к следующему массиву Z_i и проверяют наличие сигнала перехода к новому текущему значению, при этом сигнал перехода получают из предыдущего массива Z_i-1 в том случае, если в предшествующей строке массива Z_i-1 в (m+1)-м разряде был "нуль", а в текущей строке массива Z_i-1 в (m+1)-м разряде "единица", если сигнал перехода есть, то в массиве Z_i в качестве текущего значения выбирают следующую строку и записывают это число в следующие m разрядов формируемой строки массива Y, повторяют указанные действия (k-l) раз до формирования полной строки, а затем повторяют все действия по формированию следующей строки массива Y (Pⁿ-1) раз до полного формирования всех строк массива Y, причем если в любом массиве Z_i текущим значением выбирают последнюю строку, то в качестве следующего текущего значения массива Z_i выбирают его первую строку, осуществляют представление всего полученного массива Y, содержащего Pⁿ n-разрядных P-ичных чисел.

Автору не известен способ суммирования чисел, совокупность существенных признаков формулы изобретения которого идентична совокупности существенных признаков формулы заявляемого изобретения. Следовательно, заявляемое изобретение удовлетворяет условию новизны.

Автору не известен способ суммирования чисел, совокупность отличительных признаков формулы изобретения которого идентична совокупности отличительных признаков формулы изобретения заявляемого изобретения. Следовательно, заявляемое изобретение соответствует условию уровня техники.

На чертеже показан вариант устройства для осуществления способа суммирования чисел. Устройство содержит блок 1 представления исходного числа X (БПИЧ), k блоков 2, 3, 4, 5, 6 выделения m-разрядных чисел (БВМЧ), блок 7 сумматоров (БСУМ), k блоков 8, 10, 12, 14, 16 фиксации промежуточных массивов Z₁,...,Z_i,...,Z_k (БФПМ), (k-1) блок 9, 11, 13, 15 фиксации единиц переноса (БФЕП), k блоков 17, 19, 21, 23, 25 формирования строки массива Y (БФСМ), (k-1) блок 18, 20, 22, 24 анализа единиц переноса (БАЕП), блок 26 формирования текущей строки массива Y (БФТС) и блок 27 представления всего массива Y (БПИМ). Каждый из k блоков 8, 10, 12, 14, 16 фиксации промежуточных массивов Z₁,...,Z_i,...,Z_k и из (k-1)-го блока 9, 11, 13, 15 фиксации единиц переноса содержит P^m чисел, а блок 27 представления всего массива Y содержит Pⁿ n-разрядных P-ичных чисел.

Блок 1 представления исходного числа X имеет k выходов, которые соответственно своему номеру соединены со входами 2, 3, 4, 5, 6 блоков выделения m-разрядных чисел. Каждый выход блоков 2, 3, 4, 5, 6 выделения m-разрядных чисел соединен соответственно своему номеру со входами блока 7 сумматоров. Нечетные выходы блока 7 сумматоров, начиная с 1 и до 2k-1, соединены с соответствующими входами k блоков 8, 10, 12, 14, 16 фиксации промежуточных массивов Z₁, . ..,Z_i,...,Z_k. Четные выходы блока 7 сумматоров, начиная с 2 и до 2k-2, соединены с соответствующими входами (k-1)-го блока 9, 11, 13, 15 фиксации единиц переноса. Выходы блоков 8, 10, 12, 14, 16 фиксации промежуточных массивов Z₁,...,Z_i,...,Z_k соединены с первыми входами соответствующих k блоков 17, 19, 21, 23, 25 формирования строки массива Y, выходы блоков 9, 11, 13, 15 фиксации единиц переноса соединены соответственно со входами (к-1)-го блока 18, 20, 22, 24 анализа единиц переноса. Выходы блоков 18, 20, 22, 24 анализа единиц переноса соединены соответственно со вторыми входами следующих за ними блоков 17, 19, 21, 23, 25 формирования строки массива Y, причем выход блока 20 анализа единиц переноса ANAL_i-1 соединен со вторым входом блока 21 формирования строки массива Y FORM_i. Выходы k блоков 17, 19, 21, 23, 25 формирования строки массива Y соединены соответственно своим номерам со входами блока 26 формирования текущей строки массива Y. Выход блока 26 формирования текущей строки массива Y соединен со входом блока 27 представления всего массива Y.

Способ осуществляется следующим образом. В блок 1 представления исходного n-разрядного P-ичного числа X записывают исходное число X. С выходов этого блока 1 представления исходного числа X сигналы поступают на входы соответствующих k блоков 2, 3, 4, 5, 6 выделения m-разрядных чисел, в которых фиксируют числа x₁,...,x_i,...,x_k. С выходов всех k блоков 2, 3, 4, 5, 6 выделения m-разрядных чисел сигналы одновременно или последовательно поступают на соответствующие входы блока 7 сумматоров. В блоке 7 сумматоров производят параллельное на нескольких сумматорах или последовательное на одном сумматоре добавление единицы к каждому числу x₁,...,x_i,...,x_k с формированием в (m+1)-ом разряде "единиц" или "нулей" переноса, повторяют эти действия P^m раз и получают (m+1)-разрядные массивы чисел. Сигналы с нечетных выходов блока 7 сумматоров, начиная с 1 и до 2k-1, поступают на входы соответствующих k блоков 8, 10, 12, 14, 16 фиксации промежуточных массивов Z₁,...,Z_i,.. .,Z_k. Во всех k блоках 8, 10, 12, 14, 16 фиксации промежуточных массивов Z₁, . . .,Z_i,...,Z_k производят фиксацию промежуточных массивов Z₁,...,Z_i,...,Z_k. Сигналы с четных выходов блока 7 сумматоров, начиная с 1 и до 2k-2, поступают на входы соответствующих (k-1)-гo блоков 9, 11, 13, 15 фиксации единиц переноса. Во всех блоках 9, 11, 13, 15 фиксации единиц переноса производят фиксацию соответственно "единиц" или "нулей" переноса.

Сигналы с выходов k блоков 8, 10, 12, 14, 16 фиксации промежуточных массивов Z₁, . ..,Z_i,...,Z_k поступают на первые входы соответствующих k блоков 17, 19, 21, 23, 25 формирования строки массива Y. Сигналы с выходов (k-1)-го блоков 9, 11, 13, 15 фиксации единиц переноса поступают на входы соответствующих (k-1)-го блока 18, 20, 22, 24 анализа единиц переноса.

Формируют строки требуемого массива Y. Прежде всего, в качестве текущих значений в каждом массиве Z₁,...,Z_i,...,Z_k выбирают первые строки, сформированные сигналы с выходов k блоков 8, 10, 12, 14, 16 фиксации промежуточных массивов Z₁,...,Z_i,...,Z_k поступают на первые входы соответствующих k блоков 17, 19, 21, 23, 25 формирования строки массива Y, в блоках 17, 19, 21, 23, 25 формирования строки массива Y фиксируют текущие значения чисел, затем сигналы с выходов k блоков 17, 19, 21, 23, 25 формирования строки массива Y поступают на соответствующие входы блока 26 формирования текущей строки массива Y, в блоке 26 формирования текущей строки массива Y получают первую строку требуемого массива Y и сигнал с выхода блока 26 формирования текущей строки массива Y поступает на вход блока 27 представления всего массива Y, в котором записывают первую строку требуемого массива Y.

Переходят к формированию следующей строки требуемого массива Y. В блоке 16 фиксации промежуточного массива Z₁ в массиве Z₁ в качестве текущего значения выбирают следующую строку, сформированный сигнал поступает из блока 16 фиксации промежуточного массива Z₁ на вход блока 17 формирования строки массива Y FORM₁, в блоке 17 формирования строки массива Y FORM₁ формируют новое текущее значение числа, а затем сигнал из блока 17 формирования строки массива Y FORM₁ поступает на соответствующий вход блока 26 формирования текущей строки массива Y, в котором записывают это текущее число в первые m разрядов.

Затем переходят к следующему блоку 21 формирования строки массива Y FORM_i, который соединен с блоком 12 фиксации промежуточного массива Z_i и проверяют в предшествующем блоке 20 анализа единиц переноса ANAL_i-1, который соединен с блоком 13 фиксации единиц переноса массива Z_i-1, наличие сигнала перехода к новому текущему значению в блоке 21 формирования строки массива Y FORM_i. При этом, сигнал перехода формируют в предыдущем блоке 20 анализа единиц переноса ANAL_i-1, только в том случае, если в предшествующей строке в блоке 13 фиксации единиц переноса массива Z_i-1 был "нуль", а в текущей строке в блоке 13 фиксации единиц переноса массива Z_i-1 "единица". Если сигнал перехода сформирован в предыдущем блоке 20 анализа единиц переноса ANAL_i-1, то в блоке 21 формирования строки массива Y FORM_i в качестве текущего значения выбирают следующую строку из блока 12 фиксации промежуточного массива Z_i, формируют сигнал из блока 12 фиксации промежуточного массива Z_i, который поступает на вход блока 21 формирования строки массива Y FORM_i, фиксируют текущее значение числа из массива Z_i, затем формируют сигнал с выхода i-го блока 21 формирования строки массива Y FORM_i, который поступает на соответствующий вход блока 26 формирования текущей строки массива Y, в котором записывают это текущее число в следующие m разрядов формируемой строки массива Y. Повторяют указанные действия (k-1) раз до формирования полной строки в блоке 26 формирования текущей строки массива Y. В блоке 26 формирования текущей строки массива Y получают следующую строку требуемого массива Y и посылают сигнал с выхода блока 26 формирования текущей строки массива Y на вход блока 27 представления всего массива Y, в котором записывают следующую строку требуемого массива Y.

Затем повторяют все действия по формированию следующей строки массива Y (Pⁿ-1) раз до полного формирования всех строк массива Y в блоке 27 представления всего массива Y, в котором записывают все строки требуемого массива Y. Причем если в любом массиве Z_i в блоке 12 фиксации промежуточного массива Z_i, текущим значением выбирают последнюю строку, то в качестве следующего текущего значения массива Z_i выбирают его первую строку.

Заявляемое изобретение может быть использовано при построении арифметических устройств ЭВМ для повышения быстродействия решения задач математического моделирования, для значительного сокращения времени обработки целочисленных переборных задач специального назначения, имеющих важное народно-хозяйственное значение, решение которых без внедрения данного изобретения не представляется возможным. Общее количество операций сложения KS при известных способах суммирования определяют как Pⁿ, а в заявляемом изобретении определяют на этапе суммирования как k раз по P^m (m+1)-разрядных операций сложения:

Заявляемое изобретение позволяет решить поставленную задачу, уменьшить количество операций сложения при полном переборном P-ичном суммировании n-разрядного числа X с массивом V n-разрядных чисел от 0 до Pⁿ, уменьшить разрядность сумматоров, повысить интегральное быстродействие суммирования чисел, а также перейти от степенной к линейной зависимости общего количества операций сложения от разрядности чисел. Следовательно, заявляемое техническое решение удовлетворяет условию промышленной применимости.

Изобретение относится к вычислительной технике, в частности к способам суммирования чисел, и может быть использовано при построении арифметических устройств ЭВМ для повышения их быстродействия. Технический результат изобретения заключается в создании способа суммирования n-разрядного числа с массивом чисел от 0 до Pⁿ, который позволит повысить быстродействие и перейти от степенной к линейной зависимости общего количества операций сложения от разрядности чисел. Исходное n-разрядное Р-ичное число Х разбивают на k блоков x₁....х_i...х_k по m разрядов в каждом. Производят параллельное на нескольких сумматорах добавление единицы к каждому числу х₁..., х_i, х_k. Формируют в (m+1)-м разряде "единицы" или "нули" переноса. Получают (m+1)-разрядные массивы Z₁, . ..Z_i,...Z_k. Формируют строки требуемого массива Y. В качестве текущих значений в каждом массиве Z₁,...Z_i,...Z_k выбирают первые числа. 1 з. п. ф-лы, 1 ил.

1. Способ суммирования чисел, заключающийся в том, что исходное n-разрядное Р-ичное число Х записывают в блок представления исходного числа (БПИЧ), с выходов которого осуществляют поступление сигналов на входы соответствующих k блоков выделения m-разрядных чисел (БВМЧ), в которых исходный сигнал в виде числа Х разбивают на k сигналов в виде m-разрядных чисел x₁,.. .,x_i,...,x_k и фиксируют эти сигналы, с выходов всех k блоков БВМЧ осуществляют поступление сигналов одновременно или последовательно на соответствующие входы блока сумматоров (БСУМ) и пересылку m-разрядных чисел x₁,...,x_i,..., x_k на входы соответствующих k блоков фиксации промежуточных массивов (БФПМ) в качестве первых строк промежуточных массивов Z₁,...,Z_i,...,Z_k, при этом в блоке сумматоров формируют отрицательные сигналы переноса, которые передают на входы соответствующих (k-1) блоков фиксации единиц переноса (БФЕП) в качестве их начальных значений, после завершения пересылки в блоке сумматоров осуществляют параллельное на нескольких сумматоров или последовательное на одном сумматоре увеличение от 1 до P^m каждого из m-разрядных чисел x₁,..., x_i, ...,x_k на единицу, формируя в (m+1)-м разряде сигналы переноса, в случае получения при суммировании "единицы" в (m+1)-м разряде, после чего сигналы в виде увеличенных на единицу чисел x₁+1,...,x_i+1,...,x_k+1 подают на входы соответствующих k блоков БФПМ в качестве очередных строк промежуточных массивов Z₁,...,Z_i,...,Z_k, а сигналы переноса передают на входы соответствующих (k-1) блоков БФЕП в качестве их очередных значений, действия, связанные с выполнением упомянутого увеличения на единицу чисел, повторяют до полного формирования сигналов значений блоков БФПМ и БФЕП, в результате чего получают полностью сформированные и зафиксированные сигналы промежуточных массивов Z₁,...,Z_i,...,Z_k, в блоках БФПМ, а также соответствующие им сигналы переноса в блоках БФЕП, в качестве очередных сигналов значений текущих строк блоков БФПМ и БФЕП для последующего использования выбирают текущий сигнал в этих блоках, осуществляют выбор сигналов значений первых строк блоков БФПМ и БФЕП соответственно, сигналы с выходов блоков БФПМ передают на первые входы соответствующих блоков формирования строки массива (БФСМ) Y, а очередные сигналы с выходов блоков БФЕП передают на входы соответствующих блоков анализа единиц переноса (БАЕП), при отсутствии в первых строках блоков БФПМ записанных фрагментов исходного числа и в первых строках БФЕП сигналов переноса осуществляют пересылку сигналов с выходов блоков БФПМ и БФЕП на соответствующие входы блока формирования текущей строки (БФТС) массива Y, в котором формируют сигнал, совпадающий с исходным сигналом заданного числа Х, который фиксируют в блоке БФТС и пересылают в качестве значения сигала первой строки искомого массива Y в блок представления искомого массива (БПИМ), далее повторяют обработку сигналов, зафиксированных в блоках БФПМ и БФЕП, до полного формирования искомого массива Y в блоке БПИМ. 2. Способ по п.1, отличающийся тем, что при формировании текущей строки массива Z₁ в одном из блоков БФПМ выбирают строку, соответствующую текущей строке массива Z₁, формируют сигнал который подают на вход соответствующего блока БФСМ, а затем на соответствующий вход блока БФТС, одновременно с этим на вход соответствующего блока БАЕП подают сигнал переноса из первого блока БФЕП, который анализируют в блоке БАЕП, и в случае обнаружения нулевого сигнала переноса в блоке БФТС фиксируют очередное значение и формируют сигнал, который подают на вход блока БПИМ и записывают в текущую строку искомого массива, при условии обнаружения в блоке БАЕП единичного сигнала переноса на другой вход следующего ближайшего блока БФСМ посылают сигнал выбора следующей строки в качестве очередного значения из соответствующего блока БФПМ, в котором формируют сигнал, передающий на вход блока БФСМ новое очередное значение, которое передают на соответствующий вход блока БФТС и фиксируют в нем в качестве очередного, одновременно с этим из соответствующего блока БФЕП посылают сигнал переноса на вход соответствующего блока БАЕП, который обрабатывают аналогичным образом, т.е. при обнаружении нулевого сигнала переноса сформированное число в блоке БФТС преобразуют в сигнал и передают на вход блока БПИМ в качестве очередной строки и осуществляют переход на следующее значение, при обнаружении единичного сигнала переноса осуществляют действия, аналогичные формированию предыдущего соответствующего фрагмента в блоке БФТС, при наличии единичных сигналов переноса во всех блоках БАЕП во время обработки текущего шага осуществляют полное обновление значений во всех блоках БФСМ и в блоке БФТС соответственно, если в любом блоке БФПМ в качестве очередного значения осуществляют выбор последней строки, то в качестве следующего значения выбирают первую строку из этого блока.