Лекция 8. Схемные реализации ФАЛ

Лекция 8

Схемные реализации ФАЛ

Напоминание: 1) ИСА (информационная структура алгоритма,) суть граф подстановок композицию функции из базовых функций; 2) ПРФ (примитивно-рекурсивная функция) имеет бесконечный граф подстановок, построенный из повторяющихся фрагментов; 3) процессорная реализация – функции ИСА реализуются либо на единственном универсальном процессоре 1П (однопроцессорное разложение), либо на п процессорах (специализированных или универсальных) – пП-разложение (универсальное), nПс-разложение (специализированное); 4) процессорная реализация имеет т хранящих регистров, где временно хранятся значения рекурсивной функции; 5) количество т регистров может быть минимизировано по теореме .

1.  Схемная реализация комбинационного двоичного сумматора.

Пара чисел «а» и «b» представляются двоичными кодами. Двоичные коды имеют п разрядов и упорядочены слева направо. , .

1)  Примитивно-рекурсивная функция сумматора на наборе из элементарных функций {Å, &, Ú}. !Заметим!, что набор не является полным (см. таблицу Поста), в данном случае требование полноты не выдвигается.

Сумматор определяется следующими функциями:

Все операции задаются соответствующими таблицами Si, Ci и Pi.

Таблицы операций поразрядной суммы переноса и сложения задаются исходя из понимания (или необходимости) получения нужных функций. (Fc – функция суммы, Fp – переноса).

Пример построения таблицы и функции Fp переноса Pi.

	Pi-1	ai	bi	Pi
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

СДНФ Pi =

2)  Примитивно-рекурсивная функция сумматора (S).

Обозначим . , где параметр рекурсии i = 0, 1, 2, …, п – количество разрядов сумматора

a) ;

б) ;

в) .

3) Комбинационный сумматор.

ИС i-го разряда в виде ЯПФ.

Комбинационная схема сумматора (1-разрядного)

Комбинационная схема n-разрядного сумматора вычисляет сумму в каждом разряде мгновенно «со скоростью света», если одновременно поданы все входные значения <a, b>.

Затраты на оборудование комбинационных схем весьма велики. Для комбинационного п-разрядного сумматора с набором элементарных функций {Å, &, Ú} число функциональных элементов – 5п, число соединительных проводов – 14п. Но, выполняется суммирование п-разрядных чисел мгновенно, с точностью до физического запаздывания в элементах схемы.

2.  Микропроцессорная реализация сумматора

на трех специальных процессорах.

В данном случае в роли процессоров выступают функциональные элементы ПÅ, ПÚ, П&, работающие на общее поле памяти.

3П-разложение ИС сумматора представлено на рисунке

К концу 3-го такта регистр r0 хранит значение Ci, полученное во втором такте, r3 хранит значение Pi, r1 и r2 свободны и могут быть использованы для приема ai+1, bi+1 при вычислении следующих Pi+1 и Ci+1.

Таким образом строится микропроцессор из 3-х функциональных элементов и 4-х регистров, работающий за 4 такта. Заметим, что по теореме Ершова min число регистров для реализации алгоритма – три, а r0 (четвертый регистр – внешний) используется для выдачи суммы Ci во вне.

Схема микропроцессора пред-

ставляет собой последователь-

ностную машину, где внешний

регистр используется для задерж-

ки Pi на один машинный такт

равный 4 микропроцессорным

тактам).