Б sm ai bi si pi илет №13. Аппаратная поддержка операции сложения двоичных чисел.

Pi-1

ai –iая цифра числа а bi – iая цифра числа b SM – одноразрядный сумматор pi-1 – перенос из предыдущего разряда Si – результат суммы рi – перенос из iго разряда Для создания математической модели работы одноразрядного сумматора используется Булева алгебра.

Р

Ai bi pi-1

SM

Si Pi

A

B

D S

T

A+B

ассмотрим два вида одноразрядных сумматоров: 1) Накапливающий реализуется следующей схемой: c A,B,A+B –nразрядные регистры (сдвигающие) регистр – это элемент памяти на n разрядов D-триггер – это элемент памяти на 1 разряд (бит) Принцип работы: Числа а и в загружаются в соответствующие регистры Значение суммы подается на регистр А+В pi подается на D-триггер В результате получается сумма. Время сложения=n*tsm 2) Параллельный сумматор (использует n одноразрядных сумматоров) Время сложения=tsm+n*tпереносов Ускорение операции сложения строится на разделении полученной суммы и переносов.

Билет №14. Схемы деления чисел с восстановлением и без восстановления остатка. В основе выполнения операции деления лежат следующие операции - вычитание - анализ знака промежуточного результата - операция сдвига Если остаток от вычитания больше нуля, то в текущий разряд частного записывается единица, в противном случае ноль. Деление прекращается при заполнении всех разрядов частного. Вычисление производится с некоторой погрешностью. <восстановление остатка>=<текущее значение остатка>+<текущее значение делителя> Существуют два метода деления: -с восстановлением остатка -без восстановления остатка Если на каком то шаге получается отрицательный остаток, то в методах с восстановлением остатка восстанавливается предыдущий остаток. Деление производится по модулю, знак частного определяется сложением знакового разряда по модулю 2. Общее правило: делитель больше делимого, работа производится с модулями чисел.

Деление с восстановлением остатка и сдвигом остатка 1) Делитель вычитается из делимого 2) если остаток меньше 0, то остаток восстанавливается 3) сдвиг остатка на 1разряд влево (), на освободившееся место вдвигается 0

Деление с восстановлением остатка и со сдвигом делителя 1) Делитель вычитается из делимого 2) если остаток меньше 0, то остаток восстанавливается 3) сдвиг делителя на 1разряд вправо (), на освободившееся место вдвигается 1

Деление без восстановления остатка со сдвигом остатка 1) Делитель вычитается из делимого 2) Если остаток отрицательный, то к нему прибавляется делитель в прямом коде Если остаток положительный, то к нему прибавляется делитель в обр/доп. Коде 3) сдвиг остатка на 1разряд влево (), на освободившееся место вдвигается 0

Деление без восстановления остатка со сдвигом делителя 1) Делитель вычитается из делимого 2) Если остаток отрицательный, то к нему прибавляется делитель в прямом коде Если остаток положительный, то к нему прибавляется делитель в обр./доп. Коде 3) сдвиг делителя (в коде, определенном в п.2) на 1разряд вправо ()

Билет №15. Схемы умножения двоичных чисел (сравнительный анализ) Операция умножения двоичных чисел сводится к операциям сложения и сдвига а) умножение, начиная с младшего разряда со сдвигом множимого б) умножение, начиная со старшего разряда со сдвигом множимого в) умножение, начиная с младшего разряда со сдвигом сумматора г) умножение, начиная со старшего разряда со сдвигом сумматора Схемы реализации представлены на рисунках ниже, в соответствующем порядке

n

МНОЖИТЕЛЬ

СУММАТОР

МНОЖИМОЕ

МНОЖИТЕЛЬ

СУММАТОР

МНОЖИМОЕ

1 n 1

МНОЖИТЕЛЬ

СУММАТОР

МНОЖИМОЕ

МНОЖИТЕЛЬ

СУММАТОР

МНОЖИМОЕ

^

^

^

^

2n 1 2n 1 2n 1 2n 1 Рис 15а Рис 15б n 1 n 2n 2n 1 2n 1 2n 1 2n 1 Рис 15в Рис 15г Билет №16. Умножение двоичных чисел в дополнительном коде Произведение дополнительных кодов сомножителей равно дополнительному коду результата только в случае положительного множителя. Особенности операции умножения: -фиксация перед старшим разрядом -сдвиг сумматора -умножение, начиная с младшего разряда -умножение производится по модулю, знак результата определяется как сумма по модулю 2 знаковых разрядов множимого и множителя Произведение чисел в дополнительном коде при отрицательном множителе получается прибавлением дополнения множимого произведению дополнительных кодов. (Добавляется множимое с положительным знаковым разрядом) Умножение чисел в обратном коде подчиняется тем же правилам, что и в дополнительном коде, за исключением того, что при отрицательном множителе произведению обратных кодов прибавляется код, полученный от обращения обратного кода множимого. Правило-аналогия: -изначально на сумматоре ноль -если в множителе единица то прибавляем множимое и сдвигаем на 1 вправо - если в множителе ноль то просто сдвигаем на 1 вправо в освободившиеся разряды добавляем ту цифру, которая стоит в знаковом разряде.

Билет 17. Возможности ускорения операций умножения и деления двоичных чисел. Ускорение операций умножения По времени выполнения операцию умножения относят к длинным операциям. Рассматривается метод анализа двух разрядов множителя одновременно, начиная с младших разрядов. Используется система для преобразования разрядов множителя чтобы уменьшить количество слагаемых при выполнении операций в сумматоре. Справедливо соотношение: Пример: 101111= Правила преобразования разрядов множителя

Анализируемые Пары разрядов	Преобразование	Действия при анализе во время сложения на сумматоре
00	Не преобразуется	Сдвиг на 2 р. вправо содержимого сумматора:
01	Не преобразуется	Содержимое СМ складывается с множимым в п.к., затем результат сложения сдвигается на 2 р. вправо: СМ=СМ+[X1]п.к. .
10	Не преобразуется	Содержимое СМ складывается с множимым в п.к. сдвинутым на 1 р. влево, затем результат сложения сдвигается на 2 р. вправо: .
11	Заменяется на , на место анализируемой пары записывается , а 1 суммируется со следующей анализируемой парой разрядов	Содержимое СМ складывается с множимым в о.к./д.к. , затем результат сложения сдвигается на 2 р. вправо: .

СМ – сумматор.Т.о. при проведении умножения используются операции арифметического (+) и алгебраического сложения (-) и сдвиги. Ускорение операции деления Подход заключается в следующем: При образовании достаточно малого по модулю остатка очередные цифры частного будут группой цифр «0». Частное можно записать группой из нулей. При большом положительном остатке, к разряда которого содержит единицы в к-1 разряд частного записываются единицы, дальше продолжается деление.

Билет №18. Предмет и задачи теории автоматов. Типизация конечно-автоматных моделей. Любой процесс управления можно представить композицией двух автоматов: композиционного(оперативного) и управляющего. Основные разделы: 1) Теория конечных автоматов 2) Теория бесконечных автоматов (теория алгоритмов) 3) Магазинные автоматы Предмет Теория Конечных Автоматов (ТКА) рассматривает три класса задач: - Построение математической модели управления дискретным объектом -Задача технической диагностики (расшифровка черного ящика) -Основные задачи кибернетики -Синтез относительно несложных дискретных устройств с памятью ТКА: -абстрактная (рассматривает задачи 1-3) -структурная (рассматривает задачу 4) Абстрактный автомат – это математическая модель, которая не отображает многих конкретных особенностей: - структуру автомата - структуру входных и выходных сигналов - природу сигналов На вход подаются входные слова, на выходе получаются выходные слова. Задача АТА состоит в определении внутренних состояний автомата, которые необходимо минимизировать. Структурная теория автоматов определяет: -структуру автомата -структуру входного и выходного канала В структурной ТА изучаются способы построения автоматов из элементарных автоматов и способы кодирования входных и выходных сигналов. Структурный автомат состоит из комбинационно-логической схемы (КЛС) и памяти. Входные сигналы x={x(1), x(2), …, x(n)} – множество разных букв. y={y(1), y(2),…y(m)} – выходные сигналы. Абстрактный автомат функционирует в абстрактном времени. В каждый момент времени t абстрактный автомат находится в одном из состояний s={s1, s2, …, sk}. В каждый момент времени автомат может воспринимать входную букву x(t) и выдавать выходную букву y(t). Выходной сигнал зависит не только от входного сигнала в данный момент времени, но и от некоторой предыстории, т.е. от сигналов которые поступили на вход ранее. Состояния и представляют память о прошлом. В связи с этим абстрактные автоматы называются с памятью.

Билет №19. Исходные понятия и способы задания конечных автоматов. Определение. Абстрактным автоматом называется конструкция вида , или по-другому можно назвать пятеркой. x-входной алфавит у-выходной алфавит s-множество состояний - функции, или автоматные операторы -оператор переходов - оператор выходов(вообще обозначается буквой «пси») Определение. Автомат называется конечным, если конечны множества X,Y,S. Определение. Автомат, не имеющий входа, называется автоматом без входа, или генератором , «четверка» Определение. Автоматным отображением А называется отображение входных слов длины р в выходные слова q. Y=A*x IpI=IqI Определение. Автоматным оператором называется абстрактная конструкция, определяющая автоматное отображение. Определение. Абстрактный автомат называется детерминированным, если для него выполняется условие однозначности для функции переходов. //недетерминированный автомат В недетерминированном автомате возможен переход в несколько состояний. Определение. Если для недетерминированного автомата переходы взвешены вероятностями, то такой автомат называется вероятностным. Автомат первого рода определяется системой следующих соотношений: или по-другому – автомат Милли. Автомат второго порядка, называется автомат, определенный системой следующих соотношений: Автоматным оператором Мура называется система рекуррентных соотношений, которая равна: Определение. Автомат называется частичным, если для функций определены не все значения пар S и X. Полярным называется автомат, который полностью определен. Определение. Автомат называется инициальным, если для него начальное состояние Способы задания автоматов. 1) Аналитический A= 2) Табличный а) Модель Милли задается двумя таблицами: -таблица переходов -таблица выходов Столбцы помечены состояниями, строки буквами входного алфавита. На пересечении Si и Xi записывается: -в таблице переходов состояние Sk в которое автомат переходит из состояния Si под воздействием входной буквы xi -в таблице выходов записывается выходная буква yt, которая появляется на выходе автомата при переходе в состояние Sk из Si под воздействием входной буквы xi Можно составить совмещенную таблицу переходов-выходов. б) Автомат Мура в виде отмеченной таблицы переходов: столбцы – состояния строки – входные буквы По определению столбцы помечены выходной буквой. Начальное состояние автомата Мура выходной буквы не имеет. На пересечении qi-го столбца и xi строки записывается состояние qk в которое автомат Мура переходит из состояния qi под воздействием буквы xi. 3) Графический Для графического представления используются ориентированные графы. Вершины графа – состояния, ребра – выходные сигналы. Для автоматов Милли выходная буква приписывается ребрам, для автомата Мура – вершинам. Стрелки ориентированного графа показывают направление перехода. Из табличного представления легко перейти к графу. 4) Матричный. - Автомат Милли можно представить с помощью квадратной матрицы, в которой значение строк и столбцов подразумевают состояния. Для Si строки и Sk столбца записывается входная буква, которая вызывает переход и выходная буква, которая выдается на выходе автомата. -Автомат Мура можно представить матрицей на пересечении qi строк и qk столбцов ставится входная буква, вызывающая этот переход.

Билет №20. Эквивалентность автоматных операторов Милли и Мура. Теорема В.М. Глушкова. Определение. Два абстрактных автомата с одинаковыми входными и выходными алфавитами называются эквивалентными, если они индуцируют одно и то же отображение множества входных слов в множество выходных слов. Теорема В.М. Глушкова. Для любого автомата Милли существует эквивалентный ему автомат Мура с числом состояний , где m – количество входных букв, n – количество состояний. 1) Тривиальный переход от автомата Милли к автомату Мура возможен, если для всех состояний: входные стрелки Si исходного автомата помечены одинаковыми входными буква. 2) Общий переход Переход от автомата Мура к автомату Мили решается чрезвычайно просто. Пусть дан автомат Мура S_b ={A_b, X_b, Y_b, d_b, l_b}. Необходимо построить эквивалентный ему автомат Мили S_a = {A_a, X_a, Y_a, d_a, l_a}.

По определению эквивалентности имеем X_a = X_b; Y_a = Y_b. Кроме того, A_a = A_b, d_a= d_b. Остается только построить функцию выходов. Если в автомате Мура d_b(a_i, x_j) = a_s, а l_b(a_s) = y_g, то в автомате Мили l_a(a_i, x_j) = y_g. Другими словами: l(a_i, x_j) = l_b(d_b(a_i, x_j)). Таким

образом, таблица переходов автоматов Мили и Мура совпадают. А таблица выходов эквивалентного автомата Мили строится так, что в каждую клетку таблицы записывается выходной сигнал, которым отмечено состояние, расположенное в данной клетке. Пример. Задан автомат A₅ Мили в виде графа. Постороить совмещенную таблицу переходов/выходов. Найти эквивалентный ему автомат Мура, построить граф и отмеченную таблицу переходов.

Решение.

Совмещенная таблица переходов/выходов.

	S0	S1	S2	S3
X1	S1 Y1	S0 Y2	S1 Y1	S0 Y1
X2	S2 Y2	S2 Y2	S3 Y1	S1 Y2

Нахождение эквивалентного автомата Мура.