В. Спектральное представление логических функций.

Логические функции по самому смыслу своему являются дискретными. Рассматриваемые здесь функции булевых переменных, как и сами булевы переменные, принимают лишь одно из двух значений: 0 или 1. Часто приходится иметь дело не с отдельными логическими функциями, а с рядом их — с системами таких функций. Для спектрального представления логических функций делают следующее. Получают решетчатые функции, косвенно, определенным образом, отражающие свойства заданных логических функций или системы таких функций. Используя решетчатые функции, переходят от них к непрерывным кусочно-постоянным характеристикам, также косвенно отражающим свойства исходных логических функций. Используя в качестве базисных функций Уолша или функции Хаара, находят спектры, отвечающие указанным кусочно-постоянным характеристикам. Для этого производят разложение полученной

Таблица 4.4 (см. скан)

кусочно-постоянной характеристики в ряд по выбранным базисным функциям [42,184,185].

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

Пусть имеются всего три входные переменные величины и две их функции указанные в табл. 4.4. В правой части таблицы указаны х и у, значения которых определяются следующим образом. Каждое из значений х представляет собой десятичное число, эквивалентом которого является двоичное число Так же и каждое из значений у представляет собой десятичное число, эквивалентом которого является двоичное число Полученными парными значениями х и у определяется положение задающих решетчатую функцию точек, изображенных на рис. 4.10, а. Затем точки соединяются так, как показано на рис. 4.10, б. Это и есть кусочно-постоянная характеристика, соответствующая заданной системе логических функций. Считается, что

Рис. 4.10

начальная точка каждого горизонтального участка данной характеристики принадлежит этому участку, а конечная точка к нему не относится.

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

Таблица 4.5 (см. скан)

Для выполнения описанных действий при любом числе входных переменных и любом количестве их функций могут использоваться указываемые ниже формулы Введем обозначение для количества входных переменных (для наших примеров и обозначение для количества функций от этих переменных (у нас ). Введем, кроме этого, обозначение для номера входной переменной величины, указанного в индексе (в наших примерах для имеем соответственно значение равные 0, 1, 2), и обозначение для номера функции, тоже указанного в индексе (в рассмотренных примерах для имеем соответственно равные и 1). В табл. 4.5 внизу под чертой приведены значения а ниже приведены значения следующих функций от (для наших примеров (для рассматриваемых примеров . С учетом значений этих величин решетчатая функция определяется в общем случае следующим образом. Число точек, в которых она определена, равно т.е. оно равно числу строк таблицы. Для рассматриваемых примеров это восемь точек. Координаты точек находятся с помощью формул

При данных наших примеров имеем

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

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

Разложение в ряд по функциям Уолша производят следующим образом. Находят спектр функции

после чего представляют в виде ряда

Рис. 4.11

Для рассматриваемых нами примеров Соответственно с этим

и

Найдем значения имея в виду данные первого из рассматриваемых примеров согласно табл. 4.4 и рис. 4.10,б). Используемые характеристики представлены на рис. 4.11. Первоначально примем Так как при всех рассматриваемых значениях х, то сумма в правой части формулы (4.16) определяется как сумма величин при Она равна 10, и, следовательно, Находим далее при Так как при при то указанная сумма равна разности между суммами значений при и при Первая из них равна 3, вторая равна 7, и, следовательно, Аналогичным образом для следующих значений со получаем

Расчет значений указан в табл. 4.6.

С подстановкой найденных значений в формулу (4.15) приходим к следующему выражению разложения рассматриваемой нами кусочно-постоянной функции в ряд Уолша:

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

Можно проверить, что действительно расчеты, проведенные по формуле (4.18), дают исходные значения Например,

В табл. 4.7 представлены данные такого проверочного расчета. В правой части таблицы указаны подсчитанные значения Это те же значения что и исходные приведенные в табл. 4.4.

Так же, имея в виду данные второго из рассматриваемых примеров, находим

Разложение в ряд Уолша представляется здесь в следующем виде:

(см. скан)

(см. скан)

(см. скан)

Ряды Уолша (4.18) и (4.19) содержат всего соответственно семь и шесть членов. При входных переменных ряд содержит в общем случае не более членов. Применительно к данным рассматриваемых примеров

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

Если иметь в виду данные ранее рассмотренных примеров, для которых было принято то получим

Для рекуррентного по вычисления коэффициентов используются указываемые ниже формулы:

Для данных первого из ранее рассмотренных нами примеров весь ход определения этим способом отражен в табл. 4.8. Во втором столбце указаны соответствующие различным со заданные значения (в табл. 4.4 эти же численные величины указаны как Для выполняемых операций отведены три средних столбца таблицы со значениями . В последнем столбце приведены значения

Таблица 4.8 (см. скан)

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

Сравнивая табл. 4.8 и 4.6, видим, что описанный здесь алгоритм вычислений экономнее ранее рассмотренного. Вычисления производятся значительно быстрее. Данный алгоритм является алгоритмом быстрого преобразования Уолша (БПУ). Здесь первоначально производится прореживание: множество исходных данных разделяется на два подмножества и раздельно обрабатываются принадлежащие к каждому из них данные. Это делается раз за разом, пока не будут получены искомые значения . В данном случае по существу процедура вычислений такая же, как описанная нами ранее в гл. III при рассмотрении БПФ и при рассмотрении в этой главе алгоритма БПУ.

Выполнение БПУ было рассмотрено на примере, для которого было принято . В общем случае, когда значение может быть любым, находят таким же образом

С учетом зависимости (4.20) расчеты по последним формулам проводятся последовательно при и получаются в конце значения По ним определяются

Разложение в ряд по функциям Хаара производят следующим образом. Находят спектр функции

и затем представляют в виде ряда

В этих формулах имеет ранее указанное значение;

Таблица 4.9 (см. скан)

Рис. 4.12

Возвращаясь снова к условию первого из рассмотренных нами примеров, имеем Соответственно с этим должны быть учтены следующие значения

Используемые характеристики показаны на рис. 4.12. При формулы (4.29) и (4.30) записываются так:

Будучи развернутой, формула (4.32) принимает следующий вид:

Для рассматриваемого примера значения были указаны раньше в табл. 4.4. Они повторены еще раз в табл. 4.10, в которой также указаны значения и всех и приведены данные расчета коэффициентов спектрального разложения всех Коэффициент

здесь равен нулю. Согласно формуле (4.33) разложение заданной функции в ряд по базисным функциям Хаара дает

Подстановкой для соответствующих х в формулу (4.34) значений и убеждаемся в правильности полученного результата: и т.д.

Разложение функции в ряд по базисным функциям Хаара может быть ускорено путем рекуррентного определения коэффициентов разложения, аналогично тому, как это было указано выше для разложения в ряд Уолша. В книге [42] подробно рассмотрено использование разложений в базисах Уолша и Хаара для анализа и синтеза логических функций. Рассмотрено также применение с этой целью корреляционных характеристик логических функций. Краткие сведения по перечисленным вопросам приводятся в следующем разделе.