Способ организации вычислений суммы n m-разрядных чисел



Способ организации вычислений суммы n m-разрядных чисел
Способ организации вычислений суммы n m-разрядных чисел

 


Владельцы патента RU 2491612:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Вятский государственный университет" ФГБОУ ВПО "ВятГУ" (RU)

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих многооперандных параллельно-конвейерных сумматоров, для обработки массивов целых положительных чисел. Техническим результатом является повышение скорости вычисления. Способ содержит этапы, на которых параллельно подсчитывают количество единиц bi (i=1, m) в m n-разрядных двоичных векторах, сдвигают двоичное число b1 на один разряд вправо, суммируют с числом b2, полученную сумму b s 2 сдвигают на один разряд вправо и суммируют с числом b3. Аналогичным образом осуществляют сдвиг полученных сумм и суммирование их с последующими числами до получения суммы b s m . При этом младший разряд числа b1 является первым разрядом s1 суммы, младший разряд каждой полученной суммы b s i является i-ым разрядом si суммы. Выполняют сдвиг двоичного числа b s m на один разряд вправо, и в случае, если b s m = 0 , вычисление прекращают, иначе младший разряд является sm+1-ым разрядом суммы, если b s m 0 , то выполняют сдвиг двоичного числа b s m и полученное число является значениями старших разрядов искомой суммы, начиная с m+1 разряда. 1 ил.

 

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

Известен итерационный способ суммирования массива целых положительных чисел, при котором первое m-разрядное слагаемое суммируется со вторым m-разрядным слагаемым, затем полученная сумма суммируется с третьим m-разрядным слагаемым и так далее, пока не будет получена (m-поразрядная искомая сумма. Недостаток состоит в том, что, во-первых, при итерационном способе суммирования чисел выполняется n-1 операций суммирования, а с учетом последовательного способа последовательного способа переносов в старшие разряды - количество тактов суммирования равно (m-1)·n. Во-вторых, процесс формирования суммы является последовательным процессом.

Техническим результатом от использования способа организации вычислений суммы n m-разрядных чисел является повышение скорости вычисления за счет замены серии из n арифметических операций сложения m параллельно исполняемыми операциями подсчета количества единичных бит в разрядных срезах, формируемых из разрядов суммируемых чисел. На основании анализа и модификации полученных значений сумм количества единиц во всех разрядных срезах выполняется формирование значения двоичного числа, являющегося значением искомой суммы. В результате количество тактов необходимых для формирования значения суммы массива целых двоичных чисел будет равно (log2n)·m тактов. Таким образом, предлагаемый способ обеспечивает выполнение операции формирования суммы массива n m-разрядных чисел быстрее известного итерационного способа в ((m-1)·n)/((log2n)·m) раз, например, при m=100, n=64 вычисления будут выполняться в 8 раз быстрее.

Описание работы устройства: каждое i-oe двоичное позиционное слагаемое можно представить в виде последовательности бит Ai(am, am-1, …, a2, a1), где m-разрядность числа, i∈[1, n]. Тогда n слагаемых можно представить в виде матрицы:

( a 1, m , a 1, m 1 , , a 1,1 a 2, m , a 2, m 1 , , a 2,1 a n , m , a n , m 1 , , a n ,1 )

Способ организации конвейерных вычислений суммы n m-разрядных чисел заключается в параллельном подсчете количества единиц в m двоичных векторах, являющихся столбцами приведенной выше матрицы. В результате формируется m двоичных чисел bi - значений количества единиц в соответствующих n-разрядных векторах, где i∈[1, m].

Младший разряд числа b1 является первым разрядом s1 искомой суммы, затем выполняется сдвиг первого двоичного числа b1 на один разряд вправо, после чего полученный результат суммируется с числом b2, младший разряд полученной суммы b 2 s является вторым разрядом s2 суммы n m-разрядных исходных чисел.

Затем выполняется сдвиг двоичного числа b 2 s на один разряд вправо, после чего полученный результат суммируется с числом b3, младший разряд полученной суммы b 3 s является третьим разрядом s3 суммы n m-разрядных исходных чисел. И так далее вычисления продолжаются аналогичным образом до вычисления суммы b k s , младший разряд которой является k-м разрядом sk суммы n m-разрядных исходных чисел.

Затем выполняется сдвиг двоичного числа b k s на один разряд вправо, после чего полученный результат суммируется с числом bk+1, младший разряд полученной суммы b k + 1 s является (k+1)-м разрядом sk+1 суммы n m-разрядных исходных чисел. И так далее вычисления продолжаются аналогичным образом до вычисления суммы b m 1 s , младший разряд которой является (m-1)-м разрядом Sm-1 суммы n m-разрядных исходных чисел.

Затем выполняется сдвиг двоичного числа b m 1 s на один разряд вправо, после чего полученный результат суммируется с числом bm, младший разряд полученной суммы b m s является m-м разрядом sm суммы n m-разрядных исходных чисел.

Затем выполняется сдвиг двоичного числа b m s на один разряд вправо, и в случае, если b m s = 0 , то вычисление прекращается, иначе младший разряд является sm+1-м разрядом суммы n m-разрядных исходных чисел.

если b m s 0 , то выполняется сдвиг двоичного числа b m s и полученное число является значениями старших разрядов искомой суммы, начиная с m+1 разряда искомой суммы. В итоге через m тактов сдвига будет сформирована сумма n m-разрядных исходных чисел - число s1, s2, …, sk, …, sm.

Пример: необходимо сложить четыре (m=4) трехбитных (n=3) операнда: a1=111, а2=101, а3=001, а4=111. Запишем их в виде матрицы с элементами ai,j

( 111 101 001 111 )

Параллельно подсчитывается число единиц в столбцах матрицы: b1=100, b2=010, b3=011. Так как младший бит b1 равен нулю, то бит результата s1=0.

Число b1 сдвигается на один разряд вправо и результат сдвига b 1 ' = 010 суммируется с числом b2=010. Сумма b 2 s = 100 , ее младший разряд является вторым битом результата s2=0.

Число b 2 s сдвигается на один разряд вправо и результат сдвига b 2 s ' = 010 суммируется с числом b3=011. Сумма b 3 s = 101 , ее младший разряд является третьим битом результата s3=1.

Число b 3 s сдвигается на один разряд вправо и младший разряд результата сдвига b 3 s ' = 010 является четвертым битом результата s4=0. Так как b 3 s ' не равно нулю, то сдвиг повторяется: b 3 s ' ' = 001 , младший бит является пятым битом результата s5=1. Так как b 3 s ' ' не равно нулю, то сдвиг повторяется: b 3 s ' ' ' = 000 , после чего операция прекращается, так как b 3 s ' ' ' равно нулю. В итоге получена искомая сумма (s3,3, s3,2, s3,1, s2,1, s1,1)=10100.

Если принять за время суммирования пары n-разрядных чисел n тактов работы устройства, то время вычисления суммы в устройстве на базе описанного способа равно p-m тактов, где p=log2n, в то время как время суммирования итерационным способом равно m·n тактов. Таким образом, быстродействие устройства на базе описанного способа в n/(log2n) раз выше по сравнению с быстродействием устройства на базе известного итерационного способа суммирования.

Примером построения устройства на базе способа организации вычислений суммы n m-разрядных чисел может служить ее программирование на программируемых логических интегральных схемах (ПЛИС).

На фигуре представлен вариант структурной схемы устройства, реализующего способ организации вычислений суммы n m-разрядных чисел в общем виде, где 1 - счетчик единичный бит в двоичных векторах, 2 - p-разрядный двухплечевой сумматор, где p=log2n, 3 - сдвиговый p-разрядный регистр, a1-an - m-разрядные информационные входы схемы, s1-Sm - одноразрядные информационные выходы схемы, b1-bm - р-разрядные выходы счетчиков 1, b 1 s b m s ( p + 1 ) - разрядные выходы сумматоров 2.

Способ суммирования n m-разрядных целых положительных двоичных чисел в позиционной системе счисления в суммирующем устройстве, заключающийся в том, что в суммирующем устройстве параллельно выполняется подсчет количества единиц в m n-разрядных двоичных векторах, составленных из первых разрядов n чисел, вторых разрядов n чисел, …, k-х разрядов n чисел, …, m-х разрядов n чисел; в результате параллельного подсчета количества единиц в m двоичных векторах формируется m двоичных чисел - значений количества единиц в соответствующих n-разрядных векторах, причем первое двоичное число b1 - значение количества единиц в первом n-разрядном векторе, второе двоичное число b2 - значение количества единиц во втором n-разрядном векторе, …, k-e двоичное число bk - значение количества единиц в k-м n-разрядном векторе, …, m-е двоичное число bm - значение количества единиц в m-м n-разрядном векторе; младший разряд числа b1 является первым разрядом s1 суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа b1 на один разряд вправо, после чего полученный результат суммируется с числом b2, где младший разряд полученной суммы b 2 s является вторым разрядом s2 суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа b 2 s на один разряд вправо, после чего полученный результат суммируется с числом b3, младший разряд полученной суммы b 3 s является третьим разрядом s3 суммы n m-разрядных исходных чисел и так далее вычисления продолжаются аналогичным образом до вычисления суммы b k s , где младший разряд которой является k-м разрядом sk суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа b k s на один разряд вправо, после чего полученный результат суммируется с числом bk+1, младший разряд полученной суммы b k + 1 s является (k+1)-м разрядом sk+1, суммы n m-разрядных исходных чисел и так далее вычисления продолжаются аналогичным образом до вычисления суммы b m 1 s , где младший разряд которой является (m-1)-м разрядом sm-1 суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа b m 1 s на один разряд вправо, после чего полученный результат суммируется с числом bm, младший разряд полученной суммы b m s является m-м разрядом sm суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа b m s на один разряд вправо, и в случае, если b m s = 0 , то вычисление прекращается, иначе младший разряд является sm+1-м разрядом суммы n m-разрядных исходных чисел; если b m s 0 , то выполняется сдвиг двоичного числа b m s и полученное число является значениями старших разрядов искомой суммы, начиная с m+1 разряда искомой суммы; в итоге через m тактов сдвига будет сформирована сумма n m-разрядных исходных чисел - число s1, s2, …, sk, …, sm.



 

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

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих многооперандных параллельно-конвейерных сумматоров для обработки массивов целых положительных чисел.

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

Функциональная структура сумматора f2( cd) условно "k" разряда параллельно-последовательного умножителя f ( cd), реализующая процедуру "дешифрирования" входных структур аргументов слагаемых [1,2sj h1]f(2n) и [1,2sj h2]f(2n) позиционного формата "дополнительный код ru" посредством применения арифметических аксиом троичной системы счисления f(+1,0,-1) и логического дифференцирования d1/dn f1(+ -)d/dn аргументов в объединенной их структуре (вариант русской логики) // 2480817
Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств и выполнении арифметических процедур суммирования позиционных аргументов аналоговых сигналов слагаемых [ni]f(2n) и [mi ]f(2n) с применением арифметических аксиом троичной системы счисления f(+1,0,-1).

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

Изобретение относится к вычислительной технике и может быть использовано при построении многоразрядных быстродействующих сумматоров и АЛУ. .

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

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

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах цифровой обработки сигналов и в криптографических приложениях. Техническим результатом является расширение функциональных возможностей за счет введения операции суммирования по модулю. Устройство содержит n-разрядный и (n+1)-разрядный сумматоры, мультиплексор и регистр. 1 ил.

Изобретение относится к области вычислительной техники, автоматики и может использоваться в различных цифровых структурах и системах автоматического управления, передачи информации. Технический результат: создание устройства, в котором внутреннее преобразование информации производится в многозначной токовой форме сигналов, определяемое состоянием входных потенциальных двоичных сигналов, что в конечном итоге позволяет повысить быстродействие и создать элементную базу вычислительных устройств, работающих на принципах многозначной линейной алгебры. Для этого предложен одноразрядный полный сумматор с многозначным внутренним представлением сигналов, который содержит первый, второй и третий входные коммутаторы квантов тока I0 с первым, вторым и третьим токовыми выходами, первый, второй и третий источники входных логических сигналов, управляющие состоянием соответствующих коммутаторов квантов тока I0, первый и второй вспомогательные источники опорного тока, при этом в схему введены первое, второе и третье токовые зеркала, каждое из которых имеет по два инвертирующих идентичных токовых выхода, три дополнительных токовых зеркала. 1 з.п. ф-лы, 13 ил.

Изобретение относится к области цифровой вычислительной техники и устройствам цифровой автоматики. Техническим результатом является повышение быстродействия выполнения ЭВО при минимальных затратах оборудования. Устройство содержит в каждом двоичном разряде один RS-триггер, семь логических элементов И, пять элементов ИЛИ, четыре элемента НЕ, информационный вход, первый и второй информационные выходы, шесть входов управления. Способ и устройство для его реализации обеспечивают выполнение таких логических операций, как прием кода в триггеры регистра, инвертирование кода всех триггеров регистра, операция сдвига принятого кода влево, операция сложения по модулю два, логическое сложение двух двоичных кодов, логическое умножение 7. н.п. ф-лы, 1 ил.

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой вычислительной техники как средство арифметической обработки дискретной информации. Техническим результатом является обеспечение формирования двоичного кода суммы двух трехразрядных чисел, задаваемых двоичными сигналами. Устройство содержит восемь элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и шесть элементов И. 1 ил., 1 табл.

Группа изобретений относится к вычислительной технике и может быть использована при построении арифметических устройств и выполнения арифметических процедур суммирования позиционных аргументов аналоговых сигналов слагаемых с применением арифметических аксиом троичной системы счисления f(+1,0,-1). Техническим результатом является повышение быстродействия. В одном из вариантов функциональная структура выполнена с использованием логических элементов И, ИЛИ, НЕ. 4 н.п. ф-лы.

Способ формирования логико-динамического процесса преобразования условно минимизированных структур аргументов аналоговых сигналов слагаемых ±[ni]f(+/-)min и ±[mi]f(+/-)min в функциональной структуре сумматора ±f1(σru)min без сквозного переноса f1(±←←) и технологическим циклом ∆tσ → 5∙f(&)-и пять условных логических функций f(&)-и, реализованный с применением процедуры одновременного преобразования аргументов слагаемых посредством арифметических аксиом троичной системы счисления fru(+1,0,-1) и функциональные структуры для его реализации (вариант русской логики) // 2523876
Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств для выполнения арифметических процедур суммирования и умножения условно минимизированных аргументов аналоговых сигналов слагаемых. Техническим результатом является повышение быстродействия. В одном из вариантов функциональная структура реализована на логических элементах И, ИЛИ, ИЛИ-НЕ, И-НЕ. 5 н.п. ф-лы.

Изобретение относится к средствам информатики и вычислительной техники и может быть использовано для синтеза арифметико-логических устройств, для создания быстродействующих и производительных цифровых устройств суммирования и вычитания чисел в двоичной системе счисления в прямых кодах. Техническим результатом является повышение быстродействия устройства, снижение аппаратных затрат. Устройство содержит блок ввода чисел, блок компарации, блок регистра большего числа, блок суммирования-вычитания, блок регистра меньшего числа, блок регистра результата, блок управления. 12 ил.

Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств и выполнения арифметических процедур суммирования позиционных аргументов слагаемых ±[1,2 n j]f(2n) и ±[1,2 m j]f(2n). Техническим результатом является уменьшение аппаратурных затрат. В одном из вариантов сумматор реализован с использованием логических элементов, реализующих логические функции НЕ, И-НЕ. 5 н.п. ф-лы.

Изобретение относится к области вычислительной техники и может быть использовано в КМДП интегральных схемах для реализации арифметических устройств. Техническим результатом является повышение надежности. Устройство содержит логические транзисторы n-типа, предзарядовые транзисторы р-типа, инвертирующие элементы, каждый из которых содержит тактовый транзистор р-типа, логический транзистор р-типа и тактовый транзистор n-типа, шину питания, шину земли, логические выводы, логические входы, прямой и инверсный выходы. 1 ил.

Изобретение предназначено для сложения двух четырехразрядных двоичных чисел, задаваемых двоичными сигналами и может быть использовано в системах цифровой вычислительной техники как средство арифметической обработки дискретной информации. Техническим результатом является повышение однородности аппаратурного состава и увеличение быстродействия. Устройство содержит тринадцать элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (11,…,113) и десять элементов И (21,…,210). 1 ил., 1 табл.
Наверх