Устройство для вычисления квадратного корня Российский патент 2017 года по МПК G06G7/20 G06F7/38 

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

Известно устройство для вычисления квадратного корня [Оранский A.M. Аппаратные методы в цифровой вычислительной технике, Минск, изд. БГУ им. В.И. Ленина, 1977 г.]. Оно содержит регистры сдвига, входы которых, а также первые входы элементов И первой группы соединены с выходами блока управления, выходы первого и второго регистров сдвига соединены соответственно с одноименными входами первого сумматора, выход третьего регистра - с первым входом второго сумматора, регистр результата, вход и выход которого подключены соответственно к выходу и первому входу второго сумматора, а разрядные выходы - к вторым входам элементов И первой группы, выходы которых подключены к разрядным входам второго регистра сдвига, регистр остатков, вход и выход которого соединены соответственно с выходом первого сумматора и входом блока задания знака, выход которого подключен к управляющим входам первого и второго сумматоров.

Его недостатком является низкое быстродействие.

Наиболее близким по технической сущности к предлагаемому устройству является устройство для извлечения квадратного корня [А.с. 732863 СССР, 1980 г.], содержащее первый и второй сумматоры, первый, второй и третий регистры сдвига, входы первого и второго из которых, а также первые входы элементов И первой группы соединены с выходами блока управления, выходы первого и второго регистров сдвига соединены соответственно с одноименными входами первого сумматора, выход третьего регистра соединен с первым входом второго сумматора, регистр результата, вход и выход которого соединены соответственно с выходом и первым входом второго сумматора, а разрядные выходы со вторыми входами элементов И первой группы, выходы которых подключены к разрядным входам второго регистра сдвига, регистр остатков, вход и выход которого соединены соответственно с выходом первого сумматора и входом блока задания знака, выход которого подключен к управляющим входам первого и второго сумматоров. Кроме того, оно содержит регистр операнда, вторую группу элементов И и блок анализа разности, вход которого соединен с выходом регистра остатков и третьим входом первого сумматора, а выход - со входом блока управления, один из выходов которого подключен к первым входам элементов И второй группы, вторые входы которых через регистр операнда соединены с информационным входом устройства, подключенного также к четвертому входу первого сумматора, установочный вход которого соединен с выходами элементов И второй группы.

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

Задача изобретения - совершенствование устройства для извлечения квадратного корня.

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

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

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

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

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

где q_i∈{+1, -1} соответствующим образом подобранные операторы;

i=0, 1, 2, …, n-1.

На каждой итерации оценивается разность .

Устройство функционирует по следующему алгоритму

где i=0, 1, 2, …, n-1; n - разрядность чисел.

На фиг. представлена структурная схема устройства для извлечения квадратного корня, содержащая: регистр 1 операнда, регистр 2 остатков, регистр 3 результата, сумматоры 4, 5, группы элементов И 6, 7, регистры 8, 9, 10 сдвига, блок 11 анализа разности, блок 12 задания знака, блок 13 управления, блок 14 фиксации нулевого состояния.

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

Эта разность (⎥ΔX_j⎢≤X_j) из сумматора 4 передается (со знаком) в регистр 2 остатков, где анализируется блоком 11 анализа разности. Смысл анализа состоит в определении номера разряда μ в коде разности ΔX_j, в котором записана старшая единица в соответствии с выражением

где r∈{0, 1} - оператор выделения старшей 1 в коде разности ΔX_j

α_γK - состояния разрядов кода разности; γ=1, 2, 3, …, n - номера разрядов кода разности.

В соответствии со значением μ блок 13 управления обеспечивает формирование сумматором 5 приращений к ранее вычисленному и хранившемуся в регистре 3 результату Y_(j-1)n согласно выражению

причем знак первого приращения (i=μ-2) в цикле определяется знаком ΔX_j, хранимым в знаковом разряде регистра 2 остатков. При ΔX_j=0 (во всех разрядах "0") значение Y_jn равно уже вычисленному Y_(j-1)n значению, во всех остальных случаях устройство функционирует аналогично прототипу, отличаясь от него усеченным итерационным циклом, зависящим от величины μ, и начальными условиями: Y₀=Y_j-1; Z₀=ΔX_j. Итерационный процесс протекает до выполнения условия ⎥Z_i⎢≤2^-n.

Во время итераций по формулам (2), (3), (4) блок 14 фиксации нулевого состояния тестирует на полный ноль содержимое первого сумматора 4, проводящего вычисления по формуле (4), и, если в этом сумматоре содержится нуль, посылается сигнал в блок 13 управления. Происходит досрочный (до окончания всех n итераций) останов устройства для вычисления квадратного корня. Это обеспечит повышение (в среднестатистическом отношении) быстродействия заявленного устройства.

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

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

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