Лекция: Метод бинарных программ (разложение в ряд Шеннона)

Метод бинарных программ основан на поочередном анализе каждой переменной. Результатом анализа является бинарное дерево решений. Для проведения анализа используются команды условных переходов. Наиболее удобно применение команд, связанных с анализом переносов, например, RRC – сдвиг вправо через бит переноса. Переменная, которая поступает в бит переноса С, подвергается бинарному анализу — определению значения 0 или 1. В зависимости от результата алгоритм разветвляется в двух направлениях, образуя логику решения.

Рассмотрим пример построения блок-схемы алгоритма анализа булевой функции, которые зависит от четырех переменных – x, y, z, w:

Пусть .

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

Здесь сначала анализируется x, потом y, дальшеw иz.

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

Рисунок 3.1 — Блок-схема алгоритма программной реализации логической функции

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