Введение к работе
Актуальность темы. Представление булевых функций (БФ) в полиномиальных нормальных формах с фиксированной полярностью в последние двадцать лет получает всё более широкое распространение, так как имеют самые разнообразные приложения: функциональная декомпозиция БФ, сжатие данных, корректирующие коды, спектральный анализ, проектирование устройств волновых вычислений, многоверсионное проектирование и т.п. Особенно широко полиномиальные формы БФ применяются для проектирования комбинационных автоматов, приспособленных к тестопригодному проектированию (Design For Testability или DFT) и встроенному самотестированию (Built - In -Self- Test или BIST). Уникальное свойство тестопригодности полиномиальных логических преобразователей (ПЛП), заключается в том, что для их структурного тестирования используются тестовые векторы с унифицированной битовой структурой, не зависящей от реализуемой логической функции. При этом для обнаружения любой одиночной константной неисправности достаточное и необходимое количество тестовых векторов не превосходит величины 2п, где п - количество аргументов булевой функции (БФ). Данное обстоятельство при широком практическом использовании ПЛП существенно упрощает решение задач синтеза и оценки качества контрольных и диагностических тестов для цифровой техники.
Большой вклад в теоретические и практические разработки по формированию и использованию полиномиальных нормальных форм БФ внесли Же-галкин И.И., Reed L.S., Muller D.E., Reddy S.M., А.Е.А. Almaini, D.H. Green, Т. Sasao, B.J. Falkowski, M.J. Davio, M. Perkowski, G. Papakonstantinou, H.A. Перя-зев, В.П. Супрун, А.Д. Закревский, Н.Р. Торопов, В.Д. Малюгин, B.C. Выхова-нец и многие другие.
Анализ доступных работ, касающихся вопросов преобразования БФ к полиномиальной форме показывает, что такое преобразование относится к NP-трудным задачам, и в этой связи для п более 5...6 преобразование возможно только с использованием специализированных объектно-ориентированных программных комплексов, которые в настоящее время отсутствуют у отечественных инженеров - схемотехников. Следует так же отметить, что из-за обилия различных алгоритмов полиномиального преобразования БФ и отсутствия единого подхода к оценке их вычислительной сложности, не представляется возможным объективно ранжировать известные алгоритмы, как по вычислительной, так и по объемной сложности, что существенно затрудняет объективный выбор наиболее эффективных алгоритмов как по вычислительной, так и по объёмной их сложности. В то же время, каждый из известных формальных методов преобразования ДНФ к полиномиальной форме ориентирован либо на бинарные преобразования, либо на векторные преобразования исходных данных, объем которых не менее 2П бит. Однако характерной особенностью цифровой вычислительной техники является ограниченная разрядность. Если учитывать данную особенность, то можно предположить, что для полиномиального преобразования БФ вычислительными средствами наиболее адекватны алго-
ритмы и программы, рациональным образом сочетающие векторные преобразования над данными, объем которых равен разрядности вычислительных средств, и бинарные преобразования над неделимыми машинными словами.
Из сказанного выше следует, что разработка и программная реализация эффективных дискретных алгоритмов минимизации булевых функций в классе полиномиальных форм с фиксированной полярностью является весьма актуальной, современной и важной задачей.
Тематика диссертационной работы соответствует одному из научных направлений Воронежского государственного технического университета «Вычислительные комплексы и проблемно-ориентированные системы управления».
Цель и задачи исследования. Целью диссертационной работы является разработка и программная реализация эффективных дискретных алгоритмов минимизации булевых функций в классе полиномиальных форм с фиксированной полярностью. Для достижения поставленной цели были определены следующие задачи диссертационного исследования:
разработка методики сравнительной оценки эффективности дискретных алгоритмов полиномиального преобразования булевых функций;
разработка альтернативных дискретных алгоритмов преобразования БФ к полиному Жегалкина (положительно поляризованный полином Рида-Маллера);
разработка альтернативных дискретных алгоритмов преобразования БФ к минимизированным поляризованным полиномам Рида - Маллера;
разработка и верификация проблемно-ориентированного программного комплекса минимизации булевых функций в классе полиномиальных нормальных форм с фиксированной полярностью.
Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы численные методы, методы алгебры логики, дискретной математики, математического моделирования, технической диагностики, вычислительной математики, объектно-ориентированного программирования.
Научная новизна работы. В работе получены следующие результаты, характеризующиеся научной новизной:
- теоретический подход к оценке вычислительной сложности альтерна
тивных алгоритмов преобразования булевых функций к полиному Жегалкина
(положительно поляризованному полиному Рида-Маллера), базирующийся на
геометрической (табличной) модели аналитического метода неопределенных
коэффициентов и определении аналитического соотношения, определяющего
количество целенаправленных обходов значащих клеток таблицы, достаточных
для определения логических значений всех коэффициентов полиномиальной
формы, позволяющий ранжировать алгоритмы по вычислительной сложности;
- альтернативные алгоритмы преобразования БФ к полиному Жегалки
на, которые базируются на различных аналитических методах преобразования
(метод неопределенных коэффициентов; метод частных полиномиальных
форм; метод на основе булева дифференциального исчисления; метод фрак-
тального преобразования вектора значений БФ) и которые впервые с единых позиций ранжированы по вычислительной и объемной сложности;
алгоритм бинарно-векторного полиномиального преобразования БФ к полиному Жегалкина, базирующийся на комбинации аналога метода на основе булева дифференциального исчисления и метода фрактального преобразования вектора значений БФ, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью;
алгоритм решения комбинаторной задачи формирования всех возможных N - разрядных двоичных кодовых комбинаций, в которых произвольные К - разрядов (К < N) имеют фиксированные значения, отличающийся от известных переборных алгоритмов целенаправленным последовательным формированием всех возможных N - разрядных комбинаций и обеспечивающий существенное уменьшение вычислительной сложности алгоритмов полиномиального преобразования БФ;
алгоритм векторно - бинарного последовательного преобразования исходного полинома Жегалкина ко всем возможным поляризованным полиномам Рида-Малера, базирующийся на операции «смена і-полярности», которая частично выполняется над векторами из машинных слов, а частично - над машинными словами, как битовыми объектами, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью.
Результаты соответствуют следующим пунктам паспорта специальности:
п. 2 «Развитие качественных и приближенных аналитических методов исследования математических моделей»;
п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий».
п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».
Практическая значимость работы. Разработан проблемно-ориентированный программный комплекс, обеспечивающий автоматическое преобразование БФ во все возможные полиномиальные формы Рида-Маллера, поиск минимальной полиномиальной формы и вывод её структурной формулы.
Полиномиальное преобразование БФ, зависящих от 15 или 16 переменных, осуществляется на ПЭВМ клона IBM PC с тактовой частотой процессора 1,5...2 ГГц и объемом оперативной памяти 1 Гб за время, не превышающее Ічаса и 5 часов, соответственно.
Реализация и внедрение результатов работы. Результаты, полученные в диссертации, используются в Научно-исследовательском институте электронной техники (г. Воронеж), в ходе выполнения хоздоговорных НИР и в учебном процессе Воронежского Государственного Технического университета.
Апробация работы. Основные положения диссертационной работы докладывались на Шестнадцатой Международной открытой научной конференции "Современные проблемы информатизации" (Воронеж, 2011 г.) , V Междуна-
родной научно-практической конференции «Интеллектуальный потенциал молодых ученых России и зарубежья» (Москва, изд-во «Спутник+», 2012 г.), V Всероссийской научно-технической конференции МЭС-2012 "Проблемы разработки перспективных микро- и наноэлектронных систем" (Москва, ИППМ РАН, 2012) и в Международной молодежной научной школе «Теория и численные методы решения обратных и некорректных задач» (Воронеж, ВИВТ, 2012 г.).
Публикации. Основные результаты диссертации опубликованы в 15 печатных работах, в том числе 6 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателем предложены: в [7] основные принципы программной реализации алгоритма восстановления совершенной дизъюнктивныой нормальной формы; в [2] - подходы к программной реализации алгоритма преобразования дизъюнктивных нормальных форм БФ в полином Жегалкина; в [1, 3] - алгоритмизация аналитических методов полиномиального преобразования БФ; в [5] - алгоритм бинарно-векторного разложения БФ и его обоснование; в [6] - формализация алгоритмов и расчетных соотношений; в [8] - анализ подходов к преобразованию булевых функций; [11, 12] - разработка программных модулей; в [14] - разработка программного аналога асинхронного двоичного счетчика и экспериментальная диагностика изобретения; в [15] - оптимизация структуры логического преобразователя.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, изложенных на 135 страницах, списка литературы из 95 наименований, содержит 17 рисунков, 27 таблиц, приложения.
