(Опубликовано в журнале «NB: Кибернетика и программирование» № 3, 2014)

10/07/2014

Введение

Современная элементная база позволяет выполнить аппаратную реализацию операций и функций достаточно большой сложности в виде СБИС. При этом возникает вопрос наиболее эффективной реализации функций и операций, по каким либо критериям или их совокупностям.

Наиболее часто используется критерий времени реализации и схемной сложности (аппаратных затрат). Для оценки целесообразности выбора того или иного способа представления функций и операций и эффективности его реализации на СБИС требуется какой-то объективный критерий или показатель связанный только с фундаментальными свойствами операций. В качестве такого показателя можно было бы по аналогии с алгоритмами использовать показатель сложности операций. Известно, что на практике алгоритмы оцениваются временной и емкостной сложностью [1]. Непосредственное применение этих показателей малоинформативно, поскольку они скорее оценивают сложность метода выполнения операции или функции и существенно зависят от выбора базиса элементарных операций.

На наш взгляд сложность операции, так или иначе, связана со способом её реализации. Наиболее широко применяются следующие способы реализации: табличный, программный и микропрограммный (алгоритмический). Возможна также реализация операций непосредственно на основе построения схем, вычисляющих значения системы булевых функций (СБФ), описывающих эти операции или функции.

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

Операция – это закон, по которому некоторым упорядоченным группам данного множества М ставятся в соответствие элементы из М, один или несколько.

Операция должна быть определена для любой группы элементов и должна быть однозначной.

Функцией называется функциональное соответствие. Функция fустанавливает соответствие между множествами А и В (функция fимеет вид f:А®В). Каждому элементу а из своей области определения функция fставит в соответствие единственный элемент b из обласи значений. Элемент а называется аргументом функции, b – значением функции на а.

n-местная (n-арная) операция w на множестве М (при n>0) есть однозначная функция из Мn в М; при этом не предполагается, что функция w определена для всякого элемента множества Мn. Если операция w не всюду определена на Мn, то она называется n-местной частичной операцией. Под нуль-местной операцией на М понимают выделение элемента из М.

Читатью статью полностью