Операция извлечения квадратного корня на логическом устройстве

Министерство образования Российской Федерации

Тверской государственный технический университет

Кафедра ЭВМ

ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ (РАБОТУ)

Студент____________________________ код________ группа ___________

фамилия, инициалы

1.Тема __________________________________________________________

________________________________________________________________

2. Срок представления проекта (работы) к защите "____"__________2011   г.

3. Исходные данные для проектирования (научного исследования)

____________________________________________________________________________________________________________________________________ Содержание пояснительной записки курсового проекта (работы)

4.1._____________________________________________________________

4.2._____________________________________________________________

4.3._____________________________________________________________

4.4._____________________________________________________________

4..._____________________________________________________________

5. Перечень графического материала: ________________________________

_________________________________________________________________

Руководитель проекта (работы) ________________       _________________

подпись, дата                           инициалы, фамилия

Задание принял к исполнению ____________      "___"______2011   г.

подпись

Министерство образования Российской Федерации

Тверской государственный технический университет

Кафедра ЭВМ

            СОГЛАСОВАНО                                                     УТВЕРЖДАЮ

Гл. специалист предприятия                                         Зав. кафедрой ЭВМ

(для которого выполнен                                                                                                  В.А. Григорьев

реальный проект (работа)

_____________________                                              ____________________

  подпись, инициалы, фамилия                                                  подпись, инициалы, фамилия

"___"___________2011   г.                                            "___"___________2011 г.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту (работе) по ____________________________________

                                                                                  наименование учебной дисциплины

на тему:_________________________________________________________

________________________________________________________________

Автор проекта (работы)____________________________________________

                                                                                    подпись, дата, инициалы, фамилия

Специальность ___________________________________________________

                                                                                       номер,  наименование

Обозначение курсового проекта (работы) _________Группа______________

Руководитель проекта _________________     __________________________

подпись, дата                                      инициалы, фамилия

Проект (работа) защищен (а) ___________            Оценка________________

Члены комиссии:

______________________         ________________

подпись, дата                                инициалы, фамилия

______________________         ________________

подпись, дата                                инициалы, фамилия

______________________         ________________

подпись, дата                                 инициалы, фамилия

Тверь 2011

Операция извлечения квадратного корня

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

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

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

Имеются два пути решения задачи извлечения корня квадратного.

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

              Bi+1 = 0,5 (Bi + A/Bi ) ,

где Bi+1  есть  (i+1)-е приближение  , i=0, 1, 2, ...

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

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

Вычисление i-й цифры В:

    после получения (i-1)-й цифры  В (bi-1)  в  i - й  разряд В для пробы помещается 1.

    вычисляется  разность (A - Bi)2=Ri.

    если Ri > 0, то сохраняется   bi=1, иначе  bi = 0.

    перейти к вычислению (i+1)-й   цифры.

Определение остатка  Ri = A -   является сложной процедурой, выполнение которой нежелательно. Поэтому используется рекуррентная формула для получения Ri  из Ri-1.  Допустим, что найдены первые (i-1) цифр из  B=0,b1b2b3...bi-1.  Очевидно, что Bi-1  - наибольшее число из    (i-1) разрядов, для которого  т.е.

Следующая i-я цифра       т.е. Bi=0,b1b2...bi-10   или Bi=0,b1b2...1.

При  Ri  0 принимается bi=1, иначе bi=0.

Остаток Ri  при bi=1 можно получить следующим образом:

Следующая цифра bi+1 определяется так же, если  Ri  0. Если Ri < 0,  то прежде чем вычислять следующую цифру, необходимо восстановить предыдущий остаток, т.е. получить

Затем в следующем такте вычислить следующий остаток:

Новая цифра результата равна инверсному значению  знаковой цифры остатка Ri+1.

Таким образом, чтобы получить остаток Ri нужно к Bi-1  приписать справа пару цифр 01, сдвинуть его на   (i-1)  разрядов вправо и вычесть из предыдущего остатка   Ri-1.  Если  Ri  0, то bi=1, если Ri < 0, то  bi = 0.  В последнем случае необходимо восстановить  предыдущий остаток и приступить к вычислению следующей цифры.

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

Как и при делении можно отказаться от восстановления остатка. В этом случае, если  Ri < 0,  то  bi=0, а в следующем цикле  к Bi добавляется не 01, а 11 (дополнительный код) и вычитание заменяется сложением. Для доказательства этого приведем следующие преобразования:

При этом имеется в виду, что Bi-1=0,b1b2...bi-1, a Bi=0,b1b2...bi-10.

Таким образом, если Ri < 0, то в следующем такте вычитание заменяется сложением, в i-й разряд результата записывается 0, и в следующем такте к Bi приписывается справа не 01, а 11.

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

Вычисление корня квадратного подобно вычислению  частного при делении.  Роль делителя, постоянного в процессе деления, выполняет "переменный делитель" Bi, который сдвигается на один разряд вправо в каждом такте.

Как и при делении, вместо сдвига  делителя вправо можно сдвигать остаток влево, предусмотрев использование модифицированного кода остатка из-за возможной потери знака при сдвиге влево.  

Результат вычисления корня квадратного всегда получается с  недостатком, поэтому желательно его округление. Для этого необходимо определить  n+1 разряд корня.

Процесс вычисления корня квадратного состоит из однотипных циклов, в каждом из которых  определяется очередная цифра корня.  Значение очередной цифры определяет инверсия знака текущего остатка. При положительном остатке в результат заносится 1, а новое значение формируется путем приписывания к первым записанным цифрам результата пары 01. Если текущий остаток отрицателен, то в качестве очередной цифры результата выбирается 0, а для формирования очередного значения переменного делителя к текущему значению корня приписывается пара 11. Затем процедура повторяется.

Для извлечения  корня квадратного из числа с плавающей запятой необходимо порядок числа разделить на 2, а из мантиссы извлечь корень по правилам для чисел с фиксированной запятой, приведенным выше.  Если порядок нечетный, то необходимо прибавить к порядку 1, затем сдвинуть порядок и мантиссу на один разряд вправо. Так как мантиссы всегда нормализованы и в первом цикле из мантиссы производится вычитание  числа 0,01, то  первый остаток  всегда будет положительным, т.е. первая цифра результата всегда будет 1. Следовательно, при выполнении извлечения корня квадратного никогда не может произойти нарушение нормализации.    

Перед началом выполнения операции  знак операнда и его величина анализируются на равенство 0. При нулевой мантиссе операция не производится, а результату сразу присваивается значение 0. Если знак операнда  "-", вырабатывается требование прерывания.

Пример: вычислить корень квадратный из числа 598. 5982 = 1001010110, ,     242 =11000. Вычисления проводить на ДСДК, сдвиг переменного делителя без восстановления остатка.

Для выполнения операции потребуются следующие структурные элементы:

    Сумматор модифицированного кода на 12 разрядов (один дополнительный разряд для образования модифицированного кода, второй - для определения младшего разряда результата.

    Регистр А (РгА) для приема операнда из памяти. Сдвиговый регистр (для сдвига мантиссы вправо при нечетном порядке)

    Регистр В (РгВ) для хранения результатов вычисления значения  корня квадратного. Сдвиговый регистр (сдвиг влево после определения очередной цифры результата).

    Регистры  D1, D2 (РгD1, РгD2) - вспомогательные регистры для хранения двух бит, приписываемых в конец переменного делителя в соответствии с приведенными выше формулами. Сдвигаются вправо после очередного подсуммирования переменного делителя к сумматору.

    Регистр С (РгС) для хранения переменного делителя. Регистр С сдвигаем влево, а после подсуммирования регистров D1 или D2 сдвигаем на один разряд вправо.

    Два счетчика для подсчета числа определенных цифр результата (СТ1) и числа сдвигов переменного делителя С (СТ2).

    Инвертор для реализации  сложения  (вычитания) переменного делителя с содержимым сумматора.

При выполнении примера полагаем, что в начале выполнения операции текущий остаток равен содержимому РгА. Пример выполнения операции иллюстрируется Табл. 1.

Таблица 1.

Кодированная граф-схема алгоритма.

Расшифровка вершин ГСА.

Ye:  Пустая вершина. Вводится, чтобы избежать «петель».

Y1:   РгА:=[А]м д , СМ[0-10]:=0, РгС[0-10]:=0,  РгВ[0-10]:=0, СТ1:=0, СТ2:=0;

Y2:   РгD1=00.01, РгD2:=00,11;

Y3:  РгПА[0-20]:=РгА[0-20], РгМА[0-10]:=РгА[21-30], СТ1:=8;

Y4:  ТП:=1;

Y5:  РгПА:=РгПА+1, РгМА=R(1)РгМА;

Y6:  РгПА:=R(1)РгПА;

Y7:  СМ:=СМ+РгМА;

Y8:  РгС:=РгC+РгD1;

Y9:  СМ:=СМ+, РгD1:=R(1)РгD1, РгD2:=R(1) РгD2, СТ1:=СТ1-1;

Y10: РгВ[10]:=0;

Y11: РгВ[10]:=1;

Y12: РгС:=РгВ;

Y13: РгВ:=L(1)РгВ, СТ2:=СТ1;

Y14: РгС:=L(1)РгС, СТ2:=СТ2-1;

Y15: РгС:=РгС+РгD1;

Y16: РгС:=РгС+РгD2;

Y17: ШД:=РгПА|РгВ;

Y18: РгС:=R(1)РгС.

Кодирование состояний, замена переменных, выбор элементов памяти, кодирование микрокоманд, получение МДНФ для функций возбуждения элементов памяти и выходных сигналов.

Закодируем  элементы множества состояний, множества входов и множества выходов двоичными последовательностями, длина которых соответствует мощности соответствующих множеств. Переменные t1, t2, t3, t4, t5, кодирующие состояния автомата, называются внутренними переменными автомата, в переменные x1,…x9, кодирующие входные сигналы – внешними переменными.

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

Используем диаграмму Вейча, размещая в ней имена состояний таким образом, чтобы они склеивались между собой, образуя интервалы наименьшего ранга. В каждой склейке могут участвовать метки состояний, соответствующие переменной xj, в данном столбце табл.3, и метки состояний уравнения P1. Если для кодирования состояний используются не все возможные кодовые комбинации, соответствующие всем наборам значений внутренних переменных, то неиспользуемые коды образуют области неопределенности функции (диаграммы), которые могут участвовать в любых склейках. Необходимо только следить за тем, чтобы в склейку, определяющую конъюнкцию при переменной  xj,  не попадали метки состояний, для которых обозначен переход в другие состояния  под действием других переменных в этом же столбце таблицы. Очевидно, что разным способам размещения меток в диаграмме  будут соответствовать разные выражения, определяющие новые внешние переменные.

По диаграмме Вейча закодируем состояния as(t1,t2,t3,t4,t5) и am(t1,t2,t3,t4,t5), на основе этих значений получим функции возбуждения для элементов памяти (5-ти RS-триггеров).

Триггер предназначен для хранения одного бита, или одного разряда двоичного числа. Для хранения многоразрядных чисел используют линейки триггеров, называемые регистрами. Состояния триггера и соответствующие им выходы обозначаются 0 и 1. Наиболее распространенными являются D- триггер, Т - триггер, имеющие один информационный вход, RS и - JK- триггеры. Имеющие два информационных входа.

Обозначения входов:

R0 – раздельный вход установки в 0;

S1 – раздельный вход установки в 1;

Выходы:  Q - прямой,Q - инверсный.

По характеру реакции на входные воздействия различают синхронные и асинхронные триггеры.

Асинхронный триггер  - входные сигналы управляют состоянием триггера непосредственно с момента подачи их на входы.

Синхронный триггер - входные сигналы действуют на состояние триггера только при подаче синхроимпульса на управляющий вход С.

Матрица переходов RS-триггера

Расширенная таблица переходов-выходов.

Табл.2

Кодирование состояний.