Проектирование дискретных устройств. Оценка сложности.


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

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

clip_image002

Представим эту функцию в виде таблицы истинности, предварительно разбив входное данное на clip_image004 частей: clip_image006 и будем рассматривать произвольное входное значение как совокупность clip_image004[1] переменных.

clip_image009

clip_image011

clip_image013

clip_image015

clip_image017

0

0

0

clip_image019

0

0

1

clip_image021

0

0

clip_image023

clip_image025

0

1

0

clip_image027

0

1

1

clip_image029

clip_image031

clip_image033

clip_image035

clip_image037

clip_image039

clip_image041

clip_image023[1]

clip_image043

Т.к. разделение входных данных на части произвольное, будем предполагать, что каждая переменная принимает свой диапазон значений clip_image045, что означает, что произвольная переменная clip_image047 имеет значность clip_image049, где clip_image051.

Установим взаимно однозначное соответствие между значением переменной clip_image053 и значениями переменных clip_image055 на основе представления числа clip_image057 в позиционной системе счисления со смешанным (различным) основанием.

clip_image059

Пример.

Задано число (27)1010. Представим его в системе счисления с основанием clip_image061, clip_image063, clip_image065.

(27)1010 = (411)532 = 1+2+6?4 = 27

clip_image067

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

Необходимо получить выражение f в некоторой функционально полной системе операций. W={fi, gj, hl}, где fi, gj, hl соответственно унарные, бинарные и тернарные операции.

Систему операций W необходимо дополнить операциями разделения входных данных на части.

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

Будем рассматривать частный случай декомпозиции, спектральную декомпозицию вида:

clip_image077