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



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

 


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

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

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих параллельно-конвейерных делителей, обрабатывающих массивы положительных целых чисел. Техническим результатом является повышение скорости вычисления. Способ содержит этапы, на которых происходит параллельная запись делителя в ячейки матрицы на элементах памяти, первый разряд частного становится равным сумме по модулю два младшего разряда первого столбца матрицы и первого разряда делимого, остальные разряды частного становятся равными нулю; подсчитывается количество единиц b2 в векторе, равном поразрядному логическому умножению соответствующих разрядов второго столбца матрицы и разрядов частного, при этом второй разряд частного становится равным сумме по модулю два младшего разряда b2 и второго разряда делимого; аналогично подсчитывается количество единиц bi в векторе, который равен поразрядному логическому умножению соответствующих разрядов i-го столбца матрицы и разрядов частного, после чего вычисляется сумма ci вектора bi и вектора bi-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·(log2m)·m тактов. Таким образом, предлагаемый способ обеспечивает выполнение операции формирования произведения быстрее известного итерационного способа в ((m-1) ·2·m)/((log2m)·2·m)=(m-1)/log2m раз. Например, при m=64 вычисления будут выполняться в 8 раз быстрее.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

затем подсчитывается количество единиц b4=10 в векторе f3=(1101)&(0101)-0101, который равен поразрядному логическому умножению соответствующих разрядов четвертого столбца матрицы и разрядов частного, после чего вычисляется сумма С4=10+0=10 вектора b4=10 и вектора c3=0, сдвинутого на один разряд вправо, при этом четвертый разряд частного d4=0⊕0=0 становится равным сумме по модулю два младшего разряда c4 и четвертого разряда делимого.

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

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

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

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

На фиг.2 представлен вариант структурной схемы матрицы на элементах памяти для трехбитного остатка (m=3), где 1 - логический элемент И, 2 - информационный триггер с одним входом данных, одним входом синхронизации и одним выходом данных, 3 - информационный вход триггера, 4 - вход синхронизации триггера, 5 -информационный выход триггера, x1-x3 - входы схемы, на которые подается остаток множимого по трехбитному основанию, yi-y3 - входы схемы, на которые подается остаток множителя по трехбитному основанию, aij - выходы матрицы на элементах памяти.

Способ деления целых двоичных чисел без остатка, начиная с младших разрядов, заключающийся в том, что в умножающем устройстве:
происходит параллельная запись делителя в ячейки матрицы на элементах памяти, размерность матрицы составляет m столбцов и m строк, где m - разрядность как делителя, так и частного, причем
в ячейки с 1 по m первой строки матрицы записывается m-разрядный делитель,
в ячейки с 2 по m второй строки матрицы записываются m-1 младших разрядов делителя, …, в ячейки с k по m k-й строки матрицы записывается m-k младших разрядов делителя, …, в m-ю ячейку m-й строки матрицы записывается младший разряд делителя, во все остальные ячейки матрицы записываются нули; затем первый разряд частного становится равным сумме по модулю два младшего разряда первого столбца матрицы и первого разряда делимого, остальные разряды частного становятся равными нулю;
затем подсчитывается количество единиц b2 в векторе, равном поразрядному логическому умножению соответствующих разрядов второго столбца матрицы и разрядов частного, при этом второй разряд частного становится равным сумме по модулю два младшего разряда b2 и второго разряда делимого;
затем подсчитывается количество единиц b3 в векторе, который равен поразрядному логическому умножению соответствующих разрядов третьего столбца матрицы и разрядов частного, после чего вычисляется сумма c3 вектора b3 и вектора b2, сдвинутого на один разряд вправо, при этом третий разряд частного становится равным сумме по модулю два младшего разряда с3 и третьего разряда делимого;
и так далее вычисления продолжаются аналогичным образом, подсчитывается количество единиц bk в векторе, который равен поразрядному логическому умножению соответствующих разрядов k-го столбца матрицы и разрядов частного, после чего вычисляется сумма ck вектора bk и вектора ck-1, сдвинутого на один разряд вправо, при этом k-й разряд частного становится равным сумме по модулю два младшего разряда ck и k-го разряда делимого;
затем подсчитывается количество единиц bk+1 в векторе, который равен логическому умножению соответствующих разрядов (k+1)-го столбца матрицы и разрядов частного, после чего вычисляется сумма ck+1 вектора bk+1 и вектора ck, сдвинутого на один разряд вправо, при этом (k+1)-й разряд частного становится равным сумме по модулю два младшего разряда ck+1 и (k+1)-го разряда делимого;
и так далее вычисления продолжаются аналогичным образом, подсчитывается количество единиц bm в векторе, который равен логическому умножению соответствующих разрядов m-го столбца матрицы и разрядов частного, после чего вычисляется сумма cm вектора bm и вектора cm-1, сдвинутого на один разряд вправо, при этом m-й разряд частного становится равным сумме по модулю два младшего разряда cm и m-го разряда делимого;
в итоге будет сформировано m-разрядное частное исходных чисел.



 

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих параллельно-конвейерных умножителей. Техническим результатом является повышение скорости вычисления. Способ содержит этапы: осуществляют параллельную запись остатка по основанию 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 ил.

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

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

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

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

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

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

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

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

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