Д. Примеры применения преобразований Уолша и Хаара при анализе и синтезе логических функций.

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

(см. скан)

(см. скан)

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

методов, основанных на применении спектров и автокорреляционных характеристик логических функций. С тем чтобы пояснить идеи, положенные в основу этих методов анализа и синтеза, рассмотрим только один вопросов, освещенных в работах [42, 184, 185] и в других работах, на которые будут сделаны ссылки в § 6.

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

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

Обратимся к обобщенной логической функции представленной табл. 4.11. По ранее приведенным формулам определяем для этой функции ее спектр по Уолшу и отвечающую ей автокорреляционную характеристику. Расчет, проводимый по формуле (4.16), дает в данном случае значения указанные для соответствующих в предпоследнем столбце табл. 4.11, а расчет по формуле (4.35) дает значения указанные для соответствующих в последнем столбце этой таблицы.

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

Здесь знак суммирования по модулю 2.

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

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

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

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

Рассмотрим в качестве следующего примера, как определяется принадлежность булевой функции к классу самодвойственных или к классу антисамодвойственных функций. Обозначим чертой над обозначением переменной или функции переменных их отрицания (замену любого из их значений на и любого из значений на Самодвойственными называют такие функции для которых соблюдается условие а антисамодвойственными — такие из них, для которых соблюдается условие Распознавание самодвойственности или антисамодвойственности функции сводится к

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

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

При использовании в рассматриваемой здесь области функций Уолша в качестве базисных в разных случаях оказывается целесообразным разное их упорядочение: по Уолшу [179, 205]; по Пэли [42]; по Адамару [62]. Иногда более целесообразно применение базисных функций Хаара [42].

До сих пор в § 3 говорилось о спектральных методах анализа булевых функций; об аппарате, используемом при спектральном анализе и синтезе функций -ичной логики при к будет упомянуто в § 4.

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