КОМБИНАЦИОННАЯ СХЕМА
— правильная схема, построенная из элементов, являющихся автоматами без памяти. Правильной наз. схему без обратных связей, соединение элементов в которой выполнено по правилам, которые соответствуют (в функциональном отношении) операции суперпозиции функций. В соответствии с этим оператор, реализуемый К. с.. также является некоторой функцией алгебры логики. Осн. задачами теории К. с. являются задачи анализа и синтеза этих схем. Задача анализа состоит в нахождении общего конструктивного приема (алгоритма), позволяющего по любой К. с. построить выходные ф-ции этой схемы и по ним определить зависимость сигнала на каждом из ее выходов от сигналов на входах. Решение этой задачи состоит в выписывании суперпозиций, определяемых соединением элементов схемы. Задача синтеза сводится к представлению ф-ций, реализуемых К. с., в виде суперпозиции ф-ций, реализуемых некоторым заранее заданным набором логических элементов ЦВМ. Такая задача имеет решение только в том случае, если задаваемое мн-во логич. элементов образует функционально полную систему. Для решения задачи применяют аппарат алгебры логики, получивший развитие в рамках логики математической. В этом случае требование функциональной полноты системы логич. элементов выполняется, если ф-ции, реализуемые этими элементами, образуют функционально полный набор.
К. с. с несколькими выходами всегда можно представить в виде некоторой композиции схем, каждая из которых обладает лишь одним выходом. Это позволяет свести решение задачи синтеза схем с произвольным числом выходов к решению задачи синтеза К. с. с одним выходом, которая, в свою очередь, сводится к задаче построения формулы алгебры логики, представляющей выходную ф-цию схемы. Тесно связанная с ней задача построения оптимальных с точки зрения тех или иных критериев К. с. приводит к задаче минимизации соответствующих аналитических представлений. Хотя на практике очень часто ограничиваются построением аналитического представления выходной ф-ции К. с. и его оптимизацией, выполнение этих задач представляет только частичное решение общей задачи синтеза К. с. и в общем случае может возникнуть необходимость решать следующие задачи: выражать аналитические представления ф-ций, реализуемых К. с., в некоторой заданной системе операторов, обеспечивать требуемое качество физ. характеристик схем, сравнивать различные варианты схем.
Необходимость представлять выходную ф-цию К. с. с помощью некоторой заданной системы операторов возникает в том случае, когда система ф-ций, реализуемая применяемой при построении К. с. системой элементов, не совпадает с базисной системой ф-ций, используемой при построении аналитического представления (напр., в качестве полной используется система элементов, реализующая функцию штрих Шеффера, а в качестве базиса — система, состоящая из функций дизъюнкция, конъюнкция и инверсия). Решение этой задачи состоит в записи ф-ции, реализуемой К. с., в виде суперпозиции ф-ций, реализуемых логич. элементами. В силу полноты системы логич. ф-ций эта задача имеет решение всегда, однако перевод в операторную запись аналитического представления, оптимального с точки зрения к.-л. критерия, в общем случае не приводит к получению записи, оптимальной с точки зрения этого же критерия.
Требуемое качество физ. характеристик К. с. обеспечивается представлением схемы в виде структуры, состоящей из операторов, реализуемых отдельными логич. элементами используемой системы, проверкой того, удовлетворяет ли схема условиям правильности отображения значений логич. переменных в соответствующие им области физ. значений, а также подсчетом временных ф-ций схемы. Представление схемы в виде структуры связано с тем, что операторная запись ф-ции выхода К. с. не учитывает нагрузочных характеристик логич. элементов, а также необходимости их взаимной синхронизации и, следовательно, не дает полного представления о реальной схеме. Указанное представление основывается на нумерации операторов с учетом нагрузочных характеристик соответствующих логич. элементов. При нумерации каждому оператору сопоставляется пара чисел: номер каскада, в котором стоит элемент, и номер элемента в каскаде. Разработаны общие принципы построения К. с. с произвольной значностью структурного
алфавита. Наибольшее практическое значение имеет теория К. с. с двузначным структурным алфавитом.
Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469]; Рабинович 3. Л., Капитонова Ю. В. Общие принципы синтеза комбинационных схем. «Журнал вычислительной математики и математической физики», 1963, т. 3, № 4. Ю. Л. Иваськив.
