Способ деления целых двоичных чисел без остатка начиная с младших разрядов

Авторы патента:

G06F7/535 - Способы и устройства для обработки данных с воздействием на порядок их расположения или на содержание обрабатываемых данных (логические схемы H03K 19/00)

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

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

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих параллельно-конвейерных делителей, обрабатывающих массивы положительных целых чисел. Техническим результатом является повышение скорости вычисления. Способ содержит этапы, на которых происходит параллельная запись делителя в ячейки матрицы на элементах памяти, первый разряд частного становится равным сумме по модулю два младшего разряда первого столбца матрицы и первого разряда делимого, остальные разряды частного становятся равными нулю; подсчитывается количество единиц b₂ в векторе, равном поразрядному логическому умножению соответствующих разрядов второго столбца матрицы и разрядов частного, при этом второй разряд частного становится равным сумме по модулю два младшего разряда b₂ и второго разряда делимого; аналогично подсчитывается количество единиц b_i в векторе, который равен поразрядному логическому умножению соответствующих разрядов i-го столбца матрицы и разрядов частного, после чего вычисляется сумма c_i вектора b_i и вектора b_i-1, сдвинутого на один разряд вправо, при этом i-й разряд частного становится равным сумме по модулю два младшего разряда с_i и i-го разряда делимого, в итоге будет сформировано m-разрядное частное исходных чисел. 2 ил.

Известен итерационный способ деления целых чисел с плавающей запятой. В этом способе деление сводится к последовательности вычитаний с восстановлением остатка либо без восстановления остатка, которые выполняются последовательно (http.//wwvv.distedu.ru/mirror/_inform/dmivic.chat.ru/inform/div.html) со старших разрядов делимого. Недостаток состоит в том, что, во-первых, при итерационном способе умножения чисел выполняется m-1 операций вычитания, а с учетом последовательного способа переносов в старшие разряды - количество тактов суммирования равно (m-1)·2·m. Во-вторых, процесс формирования суммы является последовательным процессом.

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

Описание работы устройства: делитель можно представить в виде последовательности бит A(a_m, a_m-1, …, a₂, a₁), где m - разрядность делителя.

Происходит параллельная запись делителя в ячейки матрицы на элементах памяти, размерность матрицы составляет m столбцов и m строк, где m - разрядность как делителя, так и частного, причем в ячейки с 1 по m первой строки матрицы записывается m-разрядный делитель, в ячейки с 2 по m второй строки матрицы записываются m-1 младших разрядов делителя, …, в ячейки с k по m k-й строки матрицы записывается m-k младших разрядов делителя, …, в m-ю ячейку m-й строки матрицы записывается младший разряд делителя.

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

После чего первый разряд частного становится равным сумме по модулю два младшего разряда первого столбца матрицы и первого разряда делимого, остальные разряды частного становятся равными нулю;

затем подсчитывается количество единиц b₂ в векторе, равном поразрядному логическому умножению соответствующих разрядов второго столбца матрицы и разрядов частного, при этом второй разряд частного становится равным сумме по модулю два младшего разряда b₂ и второго разряда делимого;

затем подсчитывается количество единиц b₃ в векторе, который равен поразрядному логическому умножению соответствующих разрядов третьего столбца матрицы и разрядов частного, после чего вычисляется сумма c₃ вектора b₃ и вектора b₂, сдвинутого на один разряд вправо, при этом третий разряд частного становится равным сумме по модулю два младшего разряда c₃ и третьего разряда делимого;

и так далее вычисления продолжаются аналогичным образом, подсчитывается количество единиц b_k в векторе, который равен поразрядному логическому умножению соответствующих разрядов k-го столбца матрицы и разрядов частного, после чего вычисляется сумма c_k вектора b_k и вектора c_k-1, сдвинутого на один разряд вправо, при этом k-й разряд частного становится равным сумме по модулю два младшего разряда c_k и k-го разряда делимого;

затем подсчитывается количество единиц b_k+1 в векторе, который равен логическому умножению соответствующих разрядов (k+1)-го столбца матрицы и разрядов частного, после чего вычисляется сумма C_k+1 вектора b_k+1 и вектора c_k, сдвинутого на один разряд вправо, при этом (k+1)-й разряд частного становится равным сумме по модулю два младшего разряда c_k+1 и (k+1)-го разряда делимого;

и так далее вычисления продолжаются аналогичным образом, подсчитывается количество единиц b_m в векторе, который равен логическому умножению соответствующих разрядов m-го столбца матрицы и разрядов частного, после чего вычисляется сумма c_m вектора b_m и вектора c_m-1, сдвинутого на один разряд вправо, при этом m-й разряд частного становится равным сумме по модулю два младшего разряда c_mи m-го разряда делимого;

в итоге будет сформировано m-разрядное частное исходных чисел.

Пример: необходимо разделить делимое a₁=110111 на делитель a₂=1011 (m=4). Запишем делитель в виде матрицы размерностью m=4 строк и m=4 столбцов, в ячейки с 1 по m=4 первой строки записывается делитель. В ячейки с 2 по m=4 второй строки записывается m-1=3 младших разрядов делителя. В ячейки с 3 по m-1=4 третьей строки записывается m-2=2 младших разрядов делителя. В четвертую ячейку четвертой строки записывается младший разряд делителя. Во все остальные ячейки матрицы записываются нули:

Первый разряд частного d₁=l становится равным инверсии суммы по модулю два младшего разряда первого столбца матрицы и первого разряда делимого, остальные разряды частного становятся равными нулю;

затем подсчитывается количество единиц b₂=1 в векторе f₂=(0011)&(0001)=0001, равном поразрядному логическому умножению соответствующих разрядов второго столбца матрицы и разрядов частного, при этом второй разряд частного d₂=l⊕l=0 становится равным сумме по модулю два младшего разряда b₂ и второго разряда делимого;

затем подсчитывается количество единиц b₃=0 в векторе f₃=(0110)&(0001)-0000, который равен поразрядному логическому умножению соответствующих разрядов третьего столбца матрицы и разрядов частного, после чего вычисляется сумма c₃=0+0=0 вектора b₃=0 и вектора b₂=0, сдвинутого на один разряд вправо, при этом третий разряд частного d₃=0⊕l=l становится равным сумме по модулю два младшего разряда c₃ и третьего разряда делимого;

затем подсчитывается количество единиц b₄=10 в векторе f₃=(1101)&(0101)-0101, который равен поразрядному логическому умножению соответствующих разрядов четвертого столбца матрицы и разрядов частного, после чего вычисляется сумма С₄=10+0=10 вектора b₄=10 и вектора c₃=0, сдвинутого на один разряд вправо, при этом четвертый разряд частного d₄=0⊕0=0 становится равным сумме по модулю два младшего разряда c₄ и четвертого разряда делимого.

Таким образом, сформировано частное d=0101.

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

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

На фиг.1 представлен вариант структурной схемы устройства, реализующего операцию вычисления произведения остатков по основанию в общем виде, где 1 - счетчик единичных бит в двоичных векторах, 2 - p-разрядный двухплечевой сумматор, где p=log₂n, 3 - сдвиговый p-разрядный регистр, a₁-a_n - m-разрядные информационные входы схемы, s₁-S_m - одноразрядные информационные выходы схемы, b₁-b_m - p-разрядные выходы счетчиков 1, - (р+1)-разрядные выходы сумматоров 2.

На фиг.2 представлен вариант структурной схемы матрицы на элементах памяти для трехбитного остатка (m=3), где 1 - логический элемент И, 2 - информационный триггер с одним входом данных, одним входом синхронизации и одним выходом данных, 3 - информационный вход триггера, 4 - вход синхронизации триггера, 5 -информационный выход триггера, x₁-x₃ - входы схемы, на которые подается остаток множимого по трехбитному основанию, y_i-y₃ - входы схемы, на которые подается остаток множителя по трехбитному основанию, a_ij - выходы матрицы на элементах памяти.

Способ деления целых двоичных чисел без остатка, начиная с младших разрядов, заключающийся в том, что в умножающем устройстве:
происходит параллельная запись делителя в ячейки матрицы на элементах памяти, размерность матрицы составляет m столбцов и m строк, где m - разрядность как делителя, так и частного, причем
в ячейки с 1 по m первой строки матрицы записывается m-разрядный делитель,
в ячейки с 2 по m второй строки матрицы записываются m-1 младших разрядов делителя, …, в ячейки с k по m k-й строки матрицы записывается m-k младших разрядов делителя, …, в m-ю ячейку m-й строки матрицы записывается младший разряд делителя, во все остальные ячейки матрицы записываются нули; затем первый разряд частного становится равным сумме по модулю два младшего разряда первого столбца матрицы и первого разряда делимого, остальные разряды частного становятся равными нулю;
затем подсчитывается количество единиц b₂ в векторе, равном поразрядному логическому умножению соответствующих разрядов второго столбца матрицы и разрядов частного, при этом второй разряд частного становится равным сумме по модулю два младшего разряда b₂ и второго разряда делимого;
затем подсчитывается количество единиц b₃ в векторе, который равен поразрядному логическому умножению соответствующих разрядов третьего столбца матрицы и разрядов частного, после чего вычисляется сумма c₃ вектора b₃ и вектора b₂, сдвинутого на один разряд вправо, при этом третий разряд частного становится равным сумме по модулю два младшего разряда с₃ и третьего разряда делимого;
и так далее вычисления продолжаются аналогичным образом, подсчитывается количество единиц b_k в векторе, который равен поразрядному логическому умножению соответствующих разрядов k-го столбца матрицы и разрядов частного, после чего вычисляется сумма c_k вектора b_k и вектора c_k-1, сдвинутого на один разряд вправо, при этом k-й разряд частного становится равным сумме по модулю два младшего разряда c_k и k-го разряда делимого;
затем подсчитывается количество единиц b_k+1 в векторе, который равен логическому умножению соответствующих разрядов (k+1)-го столбца матрицы и разрядов частного, после чего вычисляется сумма c_k+1 вектора b_k+1 и вектора c_k, сдвинутого на один разряд вправо, при этом (k+1)-й разряд частного становится равным сумме по модулю два младшего разряда c_k+1 и (k+1)-го разряда делимого;
и так далее вычисления продолжаются аналогичным образом, подсчитывается количество единиц b_m в векторе, который равен логическому умножению соответствующих разрядов m-го столбца матрицы и разрядов частного, после чего вычисляется сумма c_m вектора b_m и вектора c_m-1, сдвинутого на один разряд вправо, при этом m-й разряд частного становится равным сумме по модулю два младшего разряда c_m и m-го разряда делимого;
в итоге будет сформировано m-разрядное частное исходных чисел.

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

Логический модуль // 2497181

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

Устройство совместного кодирования границ при интервальных вычислениях // 2497180

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

Устройство декодирования совместно хранимых границ при интервальных вычислениях // 2497179

Способ обработки информации и вычисления кувыркова (варианты) и устройство "генерализатор" для осуществления способа // 2494445

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

Логический процессор // 2491613

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

Система и способ адаптивной приоритизации объектов антивирусной проверки // 2491611

Изобретение относится к системам и способам расчета и назначения приоритета антивирусной проверки различных объектов. .

Способы и системы для реализации приближенного сравнения строк в базе данных // 2487394

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

Самопроверяемый специализированный вычислитель систем булевых функций // 2485575

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

Способ формирования аргументов аналоговых сигналов частичных произведений [ni]&[mj]f(h) cd аргументов множимого ±[mj]f(2n) и аргументов множителя ±[ni]f(2n) - "дополнительный код" в пирамидальном умножителе f ( cd ) для последующего логического дешифрирования f1(cd ) и формирования результирующей суммы ±[s ]f(2n) - "дополнительный код" (варианты русской логики) // 2481614

Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств для выполнения арифметической операции умножения аргументов множимого ±[mj]f(2n) и аргументов множителя ±[ni]f(2n) - «Дополнительный код».

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

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

Программируемое логическое устройство // 2503993

Изобретение относится к вычислительной технике и может быть использовано для вычисления логических функций в отказоустойчивой аппаратуре. Техническим результатом является сокращение аппаратных затрат при реализации систем логических функций большого количества переменных. Устройство содержит группы D-триггеров, блоки вычисления функций, счетчик, дешифратор, блоки конъюнкций, блоки значений конъюнкций, при этом блоки вычисления функций, блоки конъюнкций, блоки значений конъюнкций реализованы на базе логических элементов 2·2НЕ-И-ИЛИ, реализующих функцию . 4 ил., 8 табл.

Логический вычислитель // 2504826

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

Способы выполнения элементарных вычислительных операций (эво) и устройство для его осуществления // 2505850

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

Устройство деления и извлечения квадратного корня // 2510072

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

Комбинационный сумматор // 2514785

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

Функциональная структура сумматора f3 (сигмаcd) условно "g" разряда реализующая процедуру "дешифрирования" агрументов слагаемых [1,2sgh1]f(2a) и [1,2sgh2]f(2n) позиционного формата "дополнительный код ru" посредством арифметических аксиом троичной системы счисления f(+1,0,-1) и двойного логического дифференцирования d1,2/dn-f1,2(+-)d/dn активных аргументов "уровня 2" и удаления активных логических нулей "+1""-1"-"0" в "уровне 1" (варианты русской логики) // 2517245

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

Способ формирования квазиструктурированных моделей фактографического информационного наполнения документов // 2517428

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

Логический преобразователь // 2517720

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

Логический преобразователь // 2518669

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