6.5. Программная реализация логических функций

Представление автомата схемой элементов – это первый вид структурной реализации автомата. Другой ее вид – это реализация автомата программой.

Ограничимся вопросами программной реализации логических функций. Под программой понимаем пронумерованную последовательность команд к₁,…, к_S, взятых из фиксированного набора (система команд). Программа работает над конечным множеством проименованных двоичных ячеек. Имя ячейки (адрес), чаще всего – имя логической переменной, значение которой хранится в этой ячейке.

Система команд содержит команды-операторы вида:

1) Одноадресные

b:=f(a₁,…, a_p) (выполнить операцию f над содержимым ячеек a₁,…, a_p и результат положить в ячейку b)

2) Двухадресные условные переходы двух видов:

1. «если а, то i, иначе j» (если a=1, то выполняем k_i, иначе k_j);

2. «если не а, то i, иначе j».

Операция f(a₁,…, a_p) – это логическая функция р-переменных (в частности она может быть константой 1 или 0).

Если j=i+1, то переход можно считать одноадресным: (если а, то i (иначе перейти к k_i+1)), а если i=j, то безусловным: «перейти к i». Любая из указанных команд может быть заключительной, что указывается словом «конец».

Процессом вычисления программы к₁,…,к₃ называется последовательность шагов k(1), k(2),…,k(t), на каждом шаге которой выполняется одна команда программы. Эта последовательность определяется так:

1. k(1)=k₁ ;

2. если k(i)=k_r-оператор, то k(i+1)=k_r+1;

3. если k(i) – нулевой переход, то номер команды k(i+1) указывается этим переходом;

4. если k(i) - заключительная команда, остановка процесса после ее выполнения.

Программа П вычисляет (или реализует) логическую функцию f(x₁,…, x_n)=y, если для любого двоичного набора =(₁,…, _n) при начальном состоянии памяти х₁=₁,…, х_n=_n, (состояние остальных ячеек несущественно), программа через конечное число шагов остановится и при этом в ячейке у лежит величина f=(₁,…, _n).

Если под сложностью автомата мы понимаем число элементов в его схеме, то сложность программы можно понимать в различных смыслах (по числу команд, по времени реализации и т.д.)

Любой схеме, реализующей функцию f и содержащей N элементов, нетрудно поставить в соответствие программу, реализующую f и состоящую из N команд, следующим образом: занумеруем элементы схемы числами 1,2,…,n так, чтобы на любом пути от входа к выходу номера элементов возрастали; при этом номер 1 получит один из входных элементов, а номер N – выходной элемент. Пусть элемент e_i схемы реализует функцию _i и к его входам присоединены выходы элементов e_j1,…, e_j(некоторые из них могут быть входами схемы). Поставим элементу e_i в соответствие либо ячейку а_i и команду а_i=_i(a_j1,…, a_jp), если iN; либо ячейку у и команду «y:= _N(a_j1,…, a_jp) конец», если i=N. Получим программу без условных переходов (их называют операторными), в которой порядок команд в точности соответствует нумерации элементов в схеме.

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

Другой «крайний» вид программ, вычисляющих логические функции – это программы, состоящие из команд вида y:= (=0 или =1) и условных переходов. Такие программы называют бинарными программами. Всякую булеву формулу F, содержащую N букв, можно реализовать бинарной программой, вычисляющей F за время N и содержащей N команд условного перехода. Для описания метода реализации используем представление программы в виде графа в котором вершины соответствуют командам, а ребра – переходам. Пусть G₁ – граф программы для функции f₁ с начальной вершиной V₁₀ и двумя заключительными вершинами (с командой “y=0”) и (с командой “y=1”); G₁₂ – граф программы f₂ c началом V₂₀ и концами и , тогда:

1) программа, граф G₁ которой получен путем присоединения графа G₂ к «нулю» G₁ (т.е. отождествлением вершин и V₂₀; команда «y=0» при этом отбрасывается), вычислит функцию f=f₁ f₂;

2) программа, граф G₁ которой получен путем присоединения графа G₂ к «единице» G₁ (т.е. отождествлением вершин и V₂₀; команда «y=0» при этом отбрасывается), вычислит функцию f=f₁f₂;

3) программа, граф которой получен из G₁ заменой команд и на инверсные(«y:=0» на «у:=1») вычисляет f_1.

Отметим, что в графе G получаются две единичные, а в графе G’ – две нулевые заключительные вершины. В обоих случаях их надо отождествить.

Пример 5: Формула (x₁x₂) ( x₅) реализуется бинарной программой, граф которой имеет вид:

Описанный метод не гарантирует минимальности полученных программ по времени и числу команд.

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