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

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

Иллюстрации

Показать все

Реферат

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

Известно устройство для вычисления квадратного корня [Оранский 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 итераций) останов устройства для вычисления квадратного корня. Это обеспечит повышение (в среднестатистическом отношении) быстродействия заявленного устройства.

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

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