Вид РИД
Изобретение
Изобретение относится к вычислительной технике, в частности к устройствам для вычисления квадратного корня из чисел, представленных в двоичной системе в форме с фиксированной запятой.
Известно устройство для вычисления квадратного корня [Оранский A.M. Аппаратные методы в цифровой вычислительной технике, Минск, изд. БГУ им. В.И. Ленина, 1977 г.]. Оно содержит регистры сдвига, входы которых, а также первые входы элементов И первой группы соединены с выходами блока управления, выходы первого и второго регистров сдвига соединены соответственно с одноименными входами первого сумматора, выход третьего регистра - с первым входом второго сумматора, регистр результата, вход и выход которого подключены соответственно к выходу и первому входу второго сумматора, а разрядные выходы - к вторым входам элементов И первой группы, выходы которых подключены к разрядным входам второго регистра сдвига, регистр остатков, вход и выход которого соединены соответственно с выходом первого сумматора и входом блока задания знака, выход которого подключен к управляющим входам первого и второго сумматоров.
Его недостатком является низкое быстродействие.
Наиболее близким по технической сущности к предлагаемому устройству является устройство для извлечения квадратного корня [А.с. 732863 СССР, 1980 г.], содержащее первый и второй сумматоры, первый, второй и третий регистры сдвига, входы первого и второго из которых, а также первые входы элементов И первой группы соединены с выходами блока управления, выходы первого и второго регистров сдвига соединены соответственно с одноименными входами первого сумматора, выход третьего регистра соединен с первым входом второго сумматора, регистр результата, вход и выход которого соединены соответственно с выходом и первым входом второго сумматора, а разрядные выходы со вторыми входами элементов И первой группы, выходы которых подключены к разрядным входам второго регистра сдвига, регистр остатков, вход и выход которого соединены соответственно с выходом первого сумматора и входом блока задания знака, выход которого подключен к управляющим входам первого и второго сумматоров. Кроме того, оно содержит регистр операнда, вторую группу элементов И и блок анализа разности, вход которого соединен с выходом регистра остатков и третьим входом первого сумматора, а выход - со входом блока управления, один из выходов которого подключен к первым входам элементов И второй группы, вторые входы которых через регистр операнда соединены с информационным входом устройства, подключенного также к четвертому входу первого сумматора, установочный вход которого соединен с выходами элементов И второй группы.
Оно также характеризуется недостаточным быстродействием, так как задерживает результат до окончания всех n итераций притом, что результат уже готов раньше.
Задача изобретения - совершенствование устройства для извлечения квадратного корня.
Технический результат - обеспечение максимально возможного быстродействия при получении результата за счет досрочной выдачи результат без снижения точности.
Технический результат достигается тем, что устройство для извлечения квадратного корня содержит первый и второй сумматоры, первый, второй и третий регистры сдвига, входы первого и второго из которых, а также первые входы элементов И первой группы соединены с выходами блока управления, выходы первого и второго регистров сдвига соединены соответственно с одноименными входами первого сумматора, выход третьего регистра сдвига соединен с первым входом второго сумматора, регистр результата, вход и выход которого соединены соответственно с выходом и вторым входом второго сумматора, а разрядные выходы со вторыми входами элементов И первой группы, выходы которых подключены к разрядным входам второго регистра сдвига, регистр остатков, вход и выход которого соединены соответственно с выходом первого сумматора и входом блока задания знака, выход которого подключен к управляющим входам первого и второго сумматоров, а также регистр операнда, вторую группу элементов И и блок анализа разности, вход которого соединен с выходом регистра остатков и третьим входом первого сумматора, а выход - со входом блока управления, один из выходов которого подключен к первым входам элементов И второй группы, вторые входы которых через регистр операнда соединены с информационным входом устройства, подключенного также к четвертому входу первого сумматора, установочный вход которого соединен с выходами элементов И второй группы, дополнительно содержит блок фиксации нулевого состояния, вход которого подключен к второму выходу первого сумматора, а выход - ко второму входу блока управления.
Введение дополнительно блока фиксации нулевого состояния первого сумматора с его связями с этим сумматором и блоком управления позволило исключить задержку выдачи результата и таким образом повысить среднестатистическое быстродействие всего устройства в целом. Это является новым техническим решением в технике цифровых вычислений квадратного корня, поскольку результаты проведенного авторами анализа аналогов и прототипа не позволили выявить признаки, тождественные всем существенным признакам данного изобретения.
Предложенное устройство для вычисления квадратного корня промышленно применимо, поскольку его техническая реализация возможна с использованием типовых элементов микроэлектронной техники (интегральных логических схем).
Устройство реализует операцию извлечения корня посредством формирования алгебраической суммы сходящихся приращений
где qi∈{+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 записано число Xj-1, корень квадратный которого вычислен устройством к j-му моменту времени, хранится в регистре 2 остатков. На вход устройства поступает новое значение подкоренного выражения, которое записывается в регистр 1 операнда и подается через группу элементов И 6 в сумматор 4, где из него вычитается предыдущее Xj-1, т.е. в сумматоре образуется разность
Эта разность (⎥ΔXj⎢≤Xj) из сумматора 4 передается (со знаком) в регистр 2 остатков, где анализируется блоком 11 анализа разности. Смысл анализа состоит в определении номера разряда μ в коде разности ΔXj, в котором записана старшая единица в соответствии с выражением
где r∈{0, 1} - оператор выделения старшей 1 в коде разности ΔXj
αγK - состояния разрядов кода разности; γ=1, 2, 3, …, n - номера разрядов кода разности.
В соответствии со значением μ блок 13 управления обеспечивает формирование сумматором 5 приращений к ранее вычисленному и хранившемуся в регистре 3 результату Y(j-1)n согласно выражению
причем знак первого приращения (i=μ-2) в цикле определяется знаком ΔXj, хранимым в знаковом разряде регистра 2 остатков. При ΔXj=0 (во всех разрядах "0") значение Yjn равно уже вычисленному Y(j-1)n значению, во всех остальных случаях устройство функционирует аналогично прототипу, отличаясь от него усеченным итерационным циклом, зависящим от величины μ, и начальными условиями: Y0=Yj-1; Z0=ΔXj. Итерационный процесс протекает до выполнения условия ⎥Zi⎢≤2-n.
Во время итераций по формулам (2), (3), (4) блок 14 фиксации нулевого состояния тестирует на полный ноль содержимое первого сумматора 4, проводящего вычисления по формуле (4), и, если в этом сумматоре содержится нуль, посылается сигнал в блок 13 управления. Происходит досрочный (до окончания всех n итераций) останов устройства для вычисления квадратного корня. Это обеспечит повышение (в среднестатистическом отношении) быстродействия заявленного устройства.
В таблице отображен пример хода вычисления . Как видно из таблицы, при , то есть имеющем шесть двоичных разрядов, на вычисление потребовалось не шесть, а только три итерации. Это в среднестатистическом отношении повышает быстродействие устройства для извлечения квадратного корня.
Устройство для извлечения квадратного корня, содержащее первый и второй сумматоры, первый, второй и третий регистры сдвига, входы первого и второго из которых, а также первые входы элементов И первой группы соединены с выходами блока управления, выходы первого и второго регистров сдвига соединены соответственно с одноименными входами первого сумматора, выход третьего регистра сдвига соединен с первым входом второго сумматора, регистр результата, вход и выход которого соединены соответственно с выходом и вторым входом второго сумматора, а разрядные выходы со вторыми входами элементов И первой группы, выходы которых подключены к разрядным входам второго регистра сдвига, регистр остатков, вход и выход которого соединены соответственно с выходом первого сумматора и входом блока задания знака, выход которого подключен к управляющим входам первого и второго сумматоров, а также регистр операнда, вторую группу элементов И и блок анализа разности, вход которого соединен с выходом регистра остатков и третьим входом первого сумматора, а выход - со входом блока управления, один из выходов которого подключен к первым входам элементов И второй группы, вторые входы которых через регистр операнда соединены с информационным входом устройства, подключенного также к четвертому входу первого сумматора, установочный вход которого соединен с выходами элементов И второй группы, отличающееся тем, что дополнительно содержит блок фиксации нулевого состояния, вход которого подключен к второму выходу первого сумматора, а выход - к второму входу блока управления.