Способ умножения чисел в позиционном коде
Владельцы патента RU 2749647:
Федеральное государственное бюджетное учреждение науки Институт космических исследований Российской академии наук (RU)
Изобретение относится к области дискретных вычислений, а именно, к умножению целых чисел, преимущественно чисел в позиционном представлении. Технический результат заключается в обеспечении работы в потоковом режиме при непрерывном изменении входных данных. Такой результат достигается за счет способа умножения чисел в позиционном коде, заключающегося в позиционном представлении дискретных значений множимого и множителя, выполнении логических операций для составляющих сигналов и последующей сортировки полученных результатов, при этом, для каждой из возможных комбинаций пар значений уровней квантования дискретизованных квантованных сигналов множимого и множителя, выполняют логическую операцию И, а затем сортируют полученные результаты этих логических операций и определяют искомое произведение, как общее число единичных значений, получаемое в результате всех логических операций. 1 ил.
Изобретение относится к области дискретных вычислений. А именно, к способам умножения целых чисел, преимущественно чисел в позиционном представлении. В частности, к умножению квантованных значений амплитуд цифровых изображений.
Известны способы умножения, реализуемые в цифровых вычислительных машинах, например, (Карцев М.А. Арифметика цифровых машин - М.: Наука, 1969) Однако, описываемая операция умножения, выполняемая в цифровых вычислительных машинах сложна и не может производится в потоковом режиме, в темпе поступления данных.
Известны различные примеры осуществления операции умножения. В частности, приведенные в патенте РФ 888109 от 07.12.1981, МПК G06F 7/52 или в патенте РФ 1038937 от 17.05.1982, МПК G06F 7/52, например.
Все они имеют достаточно сложную реализацию и не предназначены для работы в потоковом режиме.
Прототипом выбран способ умножения чисел в позиционном коде реализованный в устройстве по патенту РФ 2054709 от 20.02.1996, МПК G06F 7/52. В рассмотренном устройстве предложено техническое решение, выполненное на простых логических элементах, которое может работать в потоковом режиме.
Недостатком прототипа является то, что предложенное решение достигается операцией многократного суммирования, что отмечено и в самом патенте. Это не является эффективным решением. Поэтому автором была представлена схема, которая ограничена только двукратным умножением.
Целью изобретения является выбор наиболее простой технологии умножения для произвольных целых чисел, которая обеспечивает работу в потоковом режиме при непрерывном изменении входных данных.
Сущность изобретения заключается в том, что для каждой из возможных комбинаций позиционных значений дискретного сигнала (на уровнях квантования сигналов изображений, например) множимого и множителя выполняют логическую операция И, а затем полученные результаты сортируют, получая значение произведения также в позиционной форме для дискретного сигнала.
Предложенный способ поясняется чертежом. На фиг. 1 показан пример устройства умножения для чисел, квантованных на четыре уровня. Здесь показаны регистр множимого, регистр множителя, логические элементы И в количестве равном произведению уровней в регистрах множителя и множимого (в нашем случае 4×4=16), а также размещенный на выходе блок сортировки. Выходы уровней регистров множителя и множимого подключены к одному из двух входов одного из логических элементов И во всех возможных комбинациях. А выходы каждого из этих логических элементов И соединены со входами сортирующего блока.
Операция сортировки может выполняться известными способами. Сортировка может быть выполнена, например, широко известным методом пузырька или другим ему подобным. (Методы сортировок и их реализации: методические указания /сост.И.В. Беляева, К.С.Беляев. Ульяновск: УлГТУ, 2006).
Вариант сортирующего блока в частном случае двукратного умножения приведен в прототипе.
Известно также устройство для сортировки двоичных чисел (патент РФ 2264645 от 20.11.2005 МПК G06F 7/06), а также известно устройство сортировки цифровой двоичной информации, которое осуществляет подсчет количества одинаковых чисел и символов (патент РФ №2382396 от 20.02.2010 МПК G06F 17/30, G06F 7/08), например.
Наиболее общее и эффективное решение сортировки, выполненное на логических элементах И и ИЛИ, и функционирующее в потоковом режиме, использовано в способе сложения изображений описанном в патенте РФ №2578799 от 27/03.2016 МПК H04N/225, G06T 5/50.
Предлагаемый способ умножения осуществляется следующим образом. Представим дискретизованные и квантованные по уровням сигналы двух изображений полученные цифровыми фотоприемниками. Необходимо выполнить умножение для сигналов отдельных дискретных элементов (пикселей) выбранных на этих изображениях. Величину этих сигналы можно представить разложением в позиционной форме в зависимости от положения уровня квантования. Тогда величина сигнала будет представлена общим числом единиц, размещенным по уровням квантования. Регистры множимого и множителя для этих сигналов на различных уровнях квантования будут содержать значения 1 или 0, с которыми можно выполнять логические операции. Результатом полученных на выходе логических элементов И, представленных в схеме на фиг. 1, будут 1 или 0 в соответствии с таблицей истинности для этой операции. На выходе блока сортировки будет получено значение сигнала, соответствующее суммарному числу единичных значений на выходе всех логических элементов И.
Проверка правильности функционирования легко осуществляется простым заданием конкретных числовых данных множимого и множителя.
Напомним таблицу истинности для логической операции И.
Выполним по нашей схеме на фиг. 1 умножение двух следующих чисел - 4, что соответствует 1111 в позиционном (по уровням квантования) представлении и - 3, что соответствует 1110. Представим его следующей таблицей, где в первых строке и столбце показаны множимое и множитель, а на пересечении их значений даны результаты выполнения логической операции И.
Подсчет общего числа единиц в полученных результатах таблицы дает число 12, что соответствует искомому результату умножения 3×4=12.
Предлагаемый способ умножения может быть использован в сопроцессорах, в устройствах, требующих оперативного (потокового) выполнения умножения. Например, для обработки видеоинформации в бортовых комплексах, в частности корреляторах.
Поскольку описанное техническое решение выполняется в потоковом режиме, то решающее устройство может функционировать в процессе непрерывного изменения входных данных. В его реализации не требуется сложных схемных решений, используются только дешевые элементы, выполняющие простые логические операции. Для изготовления электронных систем могут быть использованы серийные ПЛМ.
Способ умножения чисел в позиционном коде, заключающийся в позиционном представлении дискретных значений множимого и множителя, выполнении логических операций для составляющих сигналов и последующей сортировки полученных результатов
отличающийся тем, что для каждой из возможных комбинаций пар значений уровней квантования дискретизованных квантованных сигналов множимого и множителя, выполняют логическую операцию И, а затем сортируют полученные результаты этих логических операций и определяют искомое произведение, как общее число единичных значений получаемое в результате всех логических операций.
