Разработка и программная реализация эффективных дискретных алгоритмов минимизации булевых функций в классе полиномиальных нормальных форм с фиксированной полярностью тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Акинин, Андрей Александрович

• Акинин, Андрей Александрович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Акинин, Андрей Александрович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1 РАЗРАБОТКА МЕТОДИКИ СРАВНИТЕЛЬНОЙ ОЦЕНКИ ЭФФЕКТИВНОСТИ ДИСКРЕТНЫХ АЛГОРИТМОВ ПОЛИНОМИАЛЬНОГО ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ

1.1 Структурные и математические модели тестопригодных

14

полиномиальных логических преобразователей

1.2 Особенности аналитических методов полиномиального

23

преобразования булевых функций

1.3 Методика сравнительной эффективности дискретных алгоритмов полиномиального преобразования на основе метода неопределенных 31 коэффициентов

Цель работы и задачи исследования

2 РАЗРАБОТКА АЛЬТЕРНАТИВНЫХ ДИСКРЕТНЫХ АЛГОРИТМОВ ^ ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ К ПОЛИНОМУ ЖЕГАЛКИНА

2.1 Алгоритмы преобразо вания нл основе метода неопределенных

37

коэффициентов

2.2 Алгоритм п эеобразования на основе частных полиномиальных нормальных форм

2.3. Алгоритм преобразования на основе метода конечных разностей

2.4 Алгоритм фрактального полиномиального разложения булевых функций

2.5 Алгоритм бинарно-векторного разложения булевых функций

Выводы

69

3 РАЗРАБОТКА АЛЬТЕРНАТИВНЫХ ДИСКРЕТНЫХ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ К 72 МИНИМИЗИРОВАННЫМ ПОЛЯРИЗОВАННЫМ ПОЛИНОМАМ РИДА-МАЛЛЕРА

3.1 Общие подходы к преобразованию булевых функций в

72

поляризованные полиномы Рида-Маллера

3.2 Алгоритмы преобразования к поляризованным полиномам на

76

основе предварительной поляризации булевых функций

3.3 Алгоритмы преобразования к поляризованным полиномам на

80

основе поляризации полинома Жегалкина

Выводы

4 РАЗРАБОТКА И ВЕРИФИКАЦИЯ ПРОБЛЕМНО-ОРИЕНТИРОВАННОГО ПРОГРАММОЮ КОМПЛЕКСА

93

МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ПОЛИНОМИАЛЬНЫХ НОРМАЛЬНЫХ ФОРМ С ФИКСИРОВАННОЙ ПОЛЯРНОСТЬЮ

4.1 Разработка структуры и интерфейса программного комплекса

4.2 Разработка программного модуля восстановления дизъюнктивной нормальной формы булевой функции до совершенной формы

4.3 Разработка программного модуля минимизации поляризованных полиномов Рида-Маллера

4.4 Верификация программных модулей преобразования булевых функций к полиному Жегалкина

Выводы

ЗАКЛЮЧЕНИЕ

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

Введение диссертации (часть автореферата) на тему «Разработка и программная реализация эффективных дискретных алгоритмов минимизации булевых функций в классе полиномиальных нормальных форм с фиксированной полярностью»

ВВЕДЕНИЕ

Актуальности темы. Представление булевых функций (БФ) в полиномиальных нормальных формах с фиксированной полярностью в последние двадцать лет получает всё более широкое распространение, так как имеет самые разнообразные приложения: спектральная обработка сигналов [1,2]; по-мехозащищенная передача информации [3]; моделирование обратимых логических структур [4,5] и квантовых процессоров [6]; реверсивная логика [7] многоальтернативное и многоверсионное проектирование [8,9]; декомпозиция булевых функций [10]; тестопригодная реализация логических преобразователей на матричных структурах [11-16] и т.п.

Весьма перспективно применение полиномиальных формы БФ для проектирования комбинационных автоматов, приспособленных к тестопри-годному проектированию (Design For Testability или DFT) и встроенному самотестированию (Built - In - Self - Test или BIST). Широкое практическое использование методов DFT и BIST как на уровне электронной компонентной базы, так и на уровне радиоэлектронных средств и систем позволяет сократить сроки разработки систем, затраты на их верификацию в процессе производства и проверку работоспособности в процессе эксплуатации [1722]. Уникальное свойство тестопригодности полиномиальных логических преобразователей (ГШП), заключается в том, что для их структурного тестирования используются тестовые векторы с унифицированной битовой структурой, не зависящей от реализуемой логической функции. При этом для обнаружения любой одиночной константной неисправности достаточное и необходимое количество тестовых векторов не превосходит величины 2п, где п - количество аргументов булевой функции (БФ). Данное обстоятельство при широком практическом использовании ПЛП существенно упрощает решение задач синтеза и оценки качества контрольных и диагностических тестов для цифровой техники. Отличительным свойством полиномиальных логических преобразователей является так же и в то, что представление булевой функции в виде полинома Жегалкина может быть короче её представ-

ления в виде минимальной дизъюнктивной нормальной формы [23], а среди поляризованных полиномов Рида-Маллера могут быть найдены формы в 1.5 раза короче, чем полином Жегалкина [24].

Полиномиальные логические преобразователи могут быть эффективно реализованы как б специализированных больших интегральных схемах (ASIC - Application Specific Integrated Circuit), так и в программируемых логических интегральных схемах типов CPLD и FPGA.

Большой вклад в теоретические и практические разработки по формированию и использованию полиномиальных нормальных форм БФ внесли Жегалкин И.И., Reed L.S., Muller D.E., Reddy S.M., A.E.A. Almaini, D.H. Green, T. Sasao, B.J. Falkowski, M.J. Davio, M. Perkowski, G. Papakonstantinou, H.A. Перязев, В.П. Супрун, А.Д. Закревский, Н.Р. Торопов, В.Д. Малюгин, B.C. Выхованец и многие другие.

Теоретический интерес к полиномиальным формам булевых функций (БФ) обусловлен тем, что нахождение полиномиальной формы БФ относят к NP-трудным задачам [25], в связи с чем асимптотические вычислительная (О) и объемная (V) сложности алгоритмов полиномиального преобразования БФ имеют оценку порядка 0(2П) и V(2n), где п - количество аргументов преобразуемой БФ. Асимптотические оценки вычислительной и объемной сложности характеризуют весь класс [26] алгоритмов полиномиального преобразования БФ, подчеркивая то, что любой алгоритм из данного класса не может быть реализован быстрее, чем за 2" шагов алгоритма, при этом потребуется более чем 2" бит (слов) памяти. Таким образом, теоретический интерес состоит в отыскании наилучших алгоритмов полиномиального преобразования БФ, ориентированных на практическую реализацию средствами вычислительной техники (программными или аппаратурными). Так как преобразования БФ к полиномиальной форме относится к NP-трудным задачам, то преобразование БФ, зависящих более чем от 5...6 аргументов, возможно только с использованием специализированных объектно-ориентированных

программных комплексов, которые в настоящее время отсутствуют у отечественных инженеров - схемотехников.

Анализ даже ограниченного количества доступных работ (печатных и из Интернет-ресурсов) [27-58] показывает, что существует множество алгоритмов полиномиального преобразования БФ, которые разрабатывались и оптимизировались в течение довольно длительного промежутка времени (около тридцати лет). Зачастую, проводилось сравнение не вычислительной сложности алгоритмов, а временной сложности программ, реализующих альтернативные алгоритмы. В свою очередь время выполнения любой программы зависит и от языка программирования, и от быстродействия средств вычислительной техники, которое за тридцатилетний промежуток времени существенно изменилось. Поэтому в настоящее время не представляется возможным объективно ранжировать известные алгоритмы как по вычислительной, так и по объемной сложности, что существенно затрудняет объективный выбор наиболее эффективных. В то же время, проведенный анализ показывает, что каждый из известных формальных методов преобразования ДНФ к полиномиальной форме ориентирован либо на бинарные преобразования, либо на векторные преобразования исходных данных, объем которых не менее 2" бит. Однако характерной особенностью цифровой вычислительной техники является ограниченная разрядность. Если учитывать данную особенность, то естественно предположить, что для полиномиального преобразования БФ вычислительными средствами наиболее адекватны алгоритмы и программы, рациональным образом сочетающие векторные преобразования над данными, объем которых равен разрядности вычислительных средств, и бинарные преобразования над неделимыми машинными словами.

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

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

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

- разработка методики сравнительной оценки эффективности дискретных алгоритмов полиномиального преобразования булевых функций;

- разработка альтернативных дискретных алгоритмов преобразования БФ к полиному Жегалкина (положительно поляризованный полином Рида-Маллера);

- разработка альтернативных дискретных алгоритмов преобразования БФ к минимизированным поляризованным полиномам Рида - Маллера;

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

Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы численные методы, методы алгебры логики, дискретной математики, математического моделирования, технической диагностики, вычислительной математики, объектно-ориентированного программирования.

Научная новизна работы. В работе получены следующие результаты, характеризующиеся научной новизной:

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

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

- альтернативные алгоритмы преобразования БФ к полиному Жегал-кина, которые базируются на различных аналитических методах преобразования (метод неопределенных коэффициентов; метод частных полиномиальных форм; метод на основе булева дифференциального исчисления; метод фрактального преобразования вектора значений БФ) и которые впервые с единых позиций ранжированы по вычислительной и объемной сложности;

- алгоритм бинарно-векторного полиномиального преобразования БФ к полиному Жегалкина, базирующийся на комбинации аналога метода на основе булева дифференциального исчисления и метода фрактального преобразования вектора значений БФ, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью;

- алгоритм решения комбинаторной задачи формирования всех возможных N - разрядных двоичных кодовых комбинаций, в которых произвольные К - разрядов (К < 14) имеют фиксированные значения, отличающийся от известных переборных алгоритмов целенаправленным последовательным формированием всех возможных N - разрядных комбинаций и обеспечивающий существенное уменьшение вычислительной сложности алгоритмов полиномиального преобразования БФ;

- алгоритм векторно - бинарного последовательного преобразования исходного полинома Жегалкина ко всем возможным поляризованным полиномам Рида-Малера, базирующийся на операции «смена ¡-полярности», которая частично выполняется над векторами из машинных слов, а частично -над машинными словами, как битовыми объектами, отличающийся от из-

вестных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью.

Результаты соответствуют следующим пунктам паспорта специальности:

- п. 2 «Развитие качественных и приближенных аналитических методов исследования математических моделей»;

- п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий».

- п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».

Практическая значимость работы. Разработан проблемно-ориентированный программный комплекс, обеспечивающий автоматическое преобразование Б<1 во все возможные полиномиальные формы Рида-Маллера, поиск минимальной полиномиальной формы и вывод её структурной формулы.

Полиномиальное преобразование БФ, зависящих от 15 или 16 переменных, осуществляется на ПЭВМ клона 1ВМ РС с тактовой частотой процессора 1,5...2 ГГц и объемом оперативной памяти 1 Гб за время, не превышающее 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 таблиц, приложения.

Содержание работы.

В первой главе анализируются структурные и математические модели тестопригодных полиномиальных логических преобразователей, аналитические методы полиномиального преобразования БФ и разработан теоретический подход к оценке вычислительной сложности альтернативных алгоритмов преобразования булевых функций к полиному Жегалкина, базирующий-

ся на геометрической (табличной) модели аналитического метода неопределенных коэффициентов.

Во второй гливе разработаны семь альтернативных дискретных алгоритмов А1 - А7 полиномиального преобразования п-аргументных БФ к полиномам Жегалкина и получены оценки их вычислительной и объёмной сложности. Разработанные алгоритмы базируются на следующих аналитических методах формирования ПНФ БФ: методе неопределенных коэффициентов, методе ЧПНФ, методе конечных разностей, методе фрактальных преобразований. Разработан алгоритм бинарно-векторного полиномиального преобразования БФ к полиному Жегалкина, базирующийся на комбинации аналога метода на основе булева дифференциального исчисления и метода фрактального преобразования вектора значений БФ, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью

В третьей главе разработаны альтернативные дискретные алгоритмы преобразования БФ к минимизированным поляризованным полиномам Рида - Малера. Алгоритмы реализованы на основе следующих методов преобразования БФ: ЧПНФ, фрактального полиномиального разложения БФ, векторного полиномиального разложения БФ, бинарно-векторном полиномиальном разложении БФ.

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

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

Четвертая глава посвящена разработке и верификации проблемно-ориентированного программного комплекса минимизации булевых функций

в классе полиномиальных нормальных форм с фиксированной полярностью, обеспечивающего последовательное решение всех поставленных в работе задач: ввод дизъюнктивной нормальной формы БФ; преобразование её в совершенную нормальную форму; преобразование БФ к полиному Жегалкина или любому поляризованному полиному Рида - Малера; нахождение минимальной полиномиальной формы Рида - Малера; вывод минимизированной структурной формулы поляризованного полинома.

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

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

В заключении сформулированы основные научные и практические результаты диссертационного исследования.

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

Прилагается список используемых литературных источников.

1 РАЗРАБОТКА МЕТОДИКИ СРАВНИТЕЛЬНОЙ ОЦЕНКИ ЭФФЕКТИВНОСТИ ДИСКРЕТНЫХ АЛГОРИТМОВ

ПОЛИНОМИАЛЬНОГО ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ

1.1 Структурные и математические модели тестопри годных полиномиальных логических преобразователей

Постоянно возрастающая сложность программируемых логических интегральных схем (ПЛИС), появление систем на кристалле (system-on-chip SOC) и систем, содержащих встроенные IP-ядра (Intellectual Property-интеллектуальная собственность), обостряют проблему резкого увеличения объёма тестовых данных, необходимых на различных этапах жизненного цикла цифровых элементов, узлов и устройств [17, 18].

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

Эффективность встроенного самотестирования измеряется степенью покрытия неисправностей, аппаратурными затратами и временем выполнения теста. Если степень покрытия неисправностей одинакова, то предпочтительными являются такие средства встроенного самотестирования, которые требуют для своей реализации наименьших аппаратурных затрат, линейную зависимость длины теста от количества входных переменных и унифицированную структуру тестовых векторов не зависимо от реализуемой функции. Такими уникальными свойствами тестопригодности обладают полиномиальные логические преобразователи (ПЛП).

Полиномиальные логические преобразователи реализуются на матричных структурах [12-14], представленных на рис.1.1, которые базируются на представлении реализуемой логической функции в виде полиномиальных нормальных форм (ПНФ) и в которых используется логический базис Жегал-кина [59]: логические функции «И» (AND), «Исключающее ИЛИ» (EXOR) и «Константа 1».

t X t

1 AND 1 Х2 AND n

къ п 2n : X n

къ С

- F с . F

EXOR EXOR

а) б)

t

в) г)

Рис. 1.1 Структурные модели полиномиальных логических преобразователей

На рис. 1.1а представлена модель матричной структуры ПЛП, которой соответствует следующая математическая модель (1.1):

F(x],x2...xn) = C@K\ ®K2 ©...©£,, (1.1)

где К1 - ортогональные элементарные конъюнкции, в каждую из которых переменные х, х2...хп могут входить как с инверсией, так и без инверсии;

© - знак логической операции «исключающее ИЛИ» (exclusive-or -EXOR), которую часто называют «сумма по модулю 2»;

С ={0,1} - признак не инвертирования (С=0) или инвертирования (С=1) функции F(xl,x2...xn).

В отечественной литературе форму (1.1) часто называют «сумма по модулю два элементарных конъюнкций», а в зарубежной - ESOP (exclusive-or sum-of-products).

На рис. 1.16 представлена модель матричной структуры ПЛП, которой соответствует следующая математическая модель (1.2):

F(xl,x2...xn) = C®K'l" ®...®К;", (1.2)

где К"' - монотонная элементарная конъюнкция, в каждую из которых входят не инвертированными только те переменные х,,х2...х/г, которые на соответствующих входных наборах равны 1.

В отечественной литературе форму (1.2) называют полиномом Жегал-кина или положительно поляризованным полиномом Рида-Маллера, а в зарубежной - PPRM (positive-polarity Reed-Muller expressions).

На рис. 1.1 в представлена модель матричной структуры ПЛП, которой соответствует следующая математическая модель (1.3):

F(x(*, х? ...хр'> ) = С © К[пР © Kf ©... © Kf, (1.3)

где К"'р - поляризованная элементарная конъюнкция, в которую входят только те переменные xl,x2...x/î, которые на соответствующих входных наборах равны 1, при этом инверсными входят те переменные, для которых соответствующий бит поляризации р} = \\

P(P\i Pii—Pn) - двоичный вектор поляризации, в котором каждый компонент характеризует полярность соответствующей переменной.

В отечественной литературе форму (1.3) называют поляризованным полиномом Рида-Маллера с фиксированной полярностью, а в зарубежной -FPRM (fixed-polarity Reed-Muller expressions).

На рис. 1.1 г ппедставлена модель матричной структуры ПЛП, которой соответствует следующая математическая модель (1.4):

f(x,a ,) = с е v;nP © vf е... е v;nP , (i.4)

где V™p - электронно-перестраиваемые логические функции, реализуемые элементами VAR (variable).

Авторы работы [13] предлагают матричную структуру, представленную на рис. 1.1 г, называть VAR- EXOR. Сигнал управления г обеспечивает электронную перестройку логических элементов VAR. При г — 1 реализуется рабочий режим функционирования ПЛП и уравнение (1.4) эквивалентно уравнению (1.3). При г = 0 реализуется режим тестирования ПЛП, при котором входные переменные заменяются на псевдослучайные последовательности максимальной длины (М-последовательности) [13]. При этом последовательные двухоперандные операции логического умножения в перестраиваемых логических элементах VAR заменяются на последовательные двухоперандные операции равнозначности (NEXOR), которые инверсны операциям EXOR. На рис. 1.2 представлена функциональная схема двухоперандного элемента VAR, которая соответствует логическому уравнению (1.5):

У, = (*,-■ &*,)v(x,_, vx, vr), (1.5)

где & - знак логического умножения;

v - знак логического сложения.

Рис. 1.2 Функциональная схема двухоперандного элемента VAR

Уникальной особенностью VAR-EXOR полиномиальных логических преобразователей является то, что в режиме периодического тестирования (off lain testing) одним и тем же генератором на максимальной рабочей частоте логического преобразователя одновременно формируются как тестовые М-последовательности, так и эталонная М-последовательность. При этом и тестовые, и эталонная последовательности принадлежат одному и тому же замкнутому классу, а их различие состоит лишь в фазовом сдвиге относительно друг друга. Фазовый сдвиг эталонной М-последовательности зависит от реализуемой логической функции и должен быть предварительно определен. На рис. 1.3 представлена, предложенная в [14], функциональная схема полного дешифратора «3 —> 8», выполненная на матричной структуре VAR-EXOR.

На рис. 1.3 xq, X|, X2 — входы дешифратора для рабочего режима (г — 1) и для режима тестирования. Вход х3 - дополнительный вход для организации тестирования. Элементы © - сумма по модулю 2.

Подобным образом на языке VHDL был смоделирован и исследован тестопригодный дешифратор «8—>256» с возможностью автоматического введения константных неисправностей на входах и выходах логических элементов. Было введено более 6000 константных неисправностей, а в качестве тестовых использовались девять М-последовательностей, генерируемых 9-ти разрядным регистром сдвига с линейной обратной связью (LFSR - Linear

Feedback Shift Register). Все смоделированные неисправности обнаруживались не более чем за 10 тактов тестирования.

Рис. 1.3 Функциональная схема полного дешифратора «3 —► 8» на основе матрицы VAR-EXOR

Недостатком матричной структуры VAR- ЕХ(Ж, предложенной в [13], является возможность реализации только периодического самотестирования, которое требует вывода логического преобразователя из рабочего режима функционирования. Для устранения данного недостатка в [16] предложена следующая модификация матричной структуры УАЯ- ЕХСЖ.

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

Р(хь х2,....хп) = Со © С1 х| © С2х2 ©...© Сп хп © С(п+,)х, х2 ® С(п+2) х, х3©...

...Ф С(т.1) х, х2...хп, (1.6)

где х, - 1-ая входная логическая переменная;

С, - ]-ый коэффициент, указывающий на необходимость реализации соответствующей конъюнкции при С, = 1;

х, х|...хё - некоторая к-аргументная конъюнкция логических переменных;

ш = 2п; С, = {0,1}, ] = 0,(2п-1); х,= {0,1}, ¡=1,п. Сочетание переменных в правой части (1.6), например, С(т.|) Х| х2...хп, следует понимать как их логическое произведение (конъюнкцию), т. е.

С(т-1) x, х2.. .хп = С(т_1) & х| & х2 &. . .& хп Запишем выражение (1.6) несколько иначе:

Р(х,,х2,....хп) = с0к0 ее, к, е с2к2 е...© с(т.пк^.,) , (1.7)

где конъюнкция К0 = 1 представляет единичную конъюнкцию. Широко известно, что в выражении (1.7) все коэффициенты С, будут равны 1 только в том случае, если реализуется логическая функция п-аргументной конъюнкции инверсий входных аргументов, то есть

х', х'2 ... х'п = К0 © К, © К2 ©...© К(т.|), (1.8)

где х', следует понимать как инверсию х, .

Тогда, в соответствии с законами алгебры логики относительно операции неравнозначности выражение (1.8) можно преобразовать к виду

К0 © К, © К2 ©...© К(п>1) © х', х'2 ... х'п = 0 (1.9)

В зависимости от того, какую именно логическую функцию должен реализовывать п-входовый логический преобразователь, предварительно определяют значения соответствующих коэффициентов С, для логической функции (Рр), реализуемой в рабочем режиме. Тогда, как следует из выражения (1.9), если г конъюнкций, обеспечивающих реализацию рабочей функции Рр оставить в левой части выражения (1.9), а оставшиеся (б+1) конъюнкций перенести в правую часть этого выражения, то они будут равны при любых значениях входных аргументов. Это обеспечивает самопроверяемость логических преобразователей в рабочем режиме функционирования путем ис-

Список литературы диссертационного исследования кандидат наук Акинин, Андрей Александрович, 2013 год

Список литературы

1. Falkowski B.J. Spectral Testing of Digital Circuits // VLSI Design, 2002. Vol. 14(1), pp. 83-105

2. Чернов А. В. Модели и методы дискретного анализа и синтеза в задачах технической диагностики информационных систем / Ростов-на-Дону: ЮФУ, 2009. 170 с.

3. Иванова И.В. Классификация и синтез полиномиальных кодеков в системах автоматизированной обработки данных // Технология и конструирование в электронной аппаратуре. 2005. № 4. С. 19-23.

4. Nayeem N. М., Rice J. Е. Ordering Techniques for ESOP-Based Toffoli Cascade Generation // in the Proceedings of the 2011 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), August, 2011, Victoria, B.C., Canada, pages 274-279.

5. Sanaee Y., Dueck G. W. Generating Toffoli networks from ESOP expressions // Proceedings of IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), Victoria, ВС, Canada, 13-18 June 2009. pp. 715-719.

6. Матвеева И. В. Лингвистическое и программное обеспечение автоматизированного проектирования устройств, функционирующих на волновых и квантовых принципах : диссертация ... кандидата технических наук : 05.13.12 / [Место защиты: С.-Петерб. гос. электротехн. ун-т (ЛЭТИ)].-Санкт-Петербург, 2011.- 262 е.: ил. РГБ ОД, 61 12-5/921

7. R. Drechsler, A. Finder, and R. Wille, Improving ESOP-based synthesis of reversible logic using evolutionary algorithms," inApplications of Evolutionary Computation, Apr. 2011, pp. 151-161.

8. Куланов В.А. Об оценки диверсности реализации минимальных форм функций в различных базисах // Радюелекронш i комп'ютерш системи. 2008. № 59 (32). С. 67-71.

9. Подвальный С. JI. Многоальтернативные системы: обзор и классификация // Системы управления и информационные технологии. 2012. №2. С. 3-14

10. Авгуль Л.Б., Трухан O.K. Декомпозиция частично симметрических булевых функций на основе полиномиального разложения // Доклады БГУИР. 2004. №4. С. 59-63.

11. Акинина Ю.С., Тюрин C.B. Альтернативный подход к обеспечению легкодиагностируемости двухуровневых программируемых пользователем логических матриц // Вестник Воронеж, гос. техн. ун-та. Сер. Вычислительные и информационно-телекоммуникационные системы. Вып. 8.3. 2003. С. 32-35.

12. Hirayama T., Nagasawa К., Nishitani Y., Shimizu К. Double Fixed-Polarity Reed-Muller Expressions: A New Class of AND-EXOR Expressions for Compact and Testable Realization // IPSJ Journal, Apr. 2001, Vol. 42, № 4. - P. 983-991.

13. Акинина Ю.С., Подвальный С.Л., Тюрин C.B. Способ тестопригодной реализации логических преобразователей // Патент на изобретение RUS 2413282 от 22.12.2008; опубл. 27.02.2011 ; Бюл. № 6.

14. C.B. Тюрин, С.Л. Подвальный, Ю.С. Акинина. Способ тестопригодного проектирования логических преобразователей // Сб. науч. трудов IV Всероссийской Научно-технической конференции «Проблемы разработки перспективных микро- и наноэлектронных систем 2010». - М.: ИППМ РАН. - 2010. - С. 36-41.

15. V. Geetha, N. Devarajan and P.N. Neelakantan OR-Bridging Fault Identification and Diagnosis for Exclusive-OR Sum of Products Reed-Muller Canonical Circuits // Journal of Computer Science, USA, 2011, Issue 7(5). pp. 744-748.

16. Акинин A.A., Акинина Ю.С., Подвальный С.Л., Тюрин C.B. Способ тестопригодной реализации логических преобразователей // Заявка

на изобретение RUS 2011123026/08 от 07.06.2011; опубл. 20.12.2012, Бюл. №35. Решение о выдаче патента от 24.04.2013.

17. Аксёнова Г.П. Самотестирование «системы на кристалле», реализованной в ПЛИС // Труды конференции «Технические и программные средства систем управления, контроля и измерения. М: 2010. С. 23-30.

18. Аксёнова Г.П., Халчев В.Ф. Метод параллельно последовательного самотестирования в интегральных схемах типа FPGA // Автоматика и телемеханика. - 2007. - № 1. - С. 163 - 174.

19. Мосин С.Г. Структурные решения тестопригодного проектирования заказных интегральных схем // Информационные технологии. 2008. № 11. С. 2-10.

20. Золоторевич Л.А Верификация проектов и построение тестов контроля СБИС на уровне RTL // Материалы Международной научной конференции «ИТС 2011». Минск: 2011. С. 8-13.

21. Inoue, М. Test synthesis for datapath using datapath-controller functions / M. Inoue, K. Suzuki, H. Okamoto, H. Fujiwara // Proceeding of the 12 th Asian Test Symposium (ATS'03). 2003. P. 294-299.

22. Акинина Ю.С. Разработка моделей и алгоритмов инженерного синтеза самотестирующихся логических преобразователей с перестраиваемым элементным базисом: диссертация...кандидата технических наук: 05.13.18, 05.13.15 /' [Место защиты: Воронежский гос. техн. ун-т (ВГТУ)] - Воронеж, 2006. - 160 е.: РГБ ОД, 61:06-5/1992

23. Papakonstantinou G. Minimization of modulo-2 sum of products // IEEE Trans. Comput. 1979. - №2. - P. 163-167.

24. Перязев H.A. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика. 1995. № 34. Вып. 3-С. 323-326.

25. Закревский A.A., Торопов Н.Р. Полиномиальная реализация частичных булевых функций и систем. - М.: Едиториал УРСС, 2003. - 200 с.

26. Карпов Ю.Г., Трифонов Ю.Г. Сложность алгоритмов и программ // Компьютерные инструменты в образовании. 2007. № 6. С.3-10.

27. Т. Sasao and Ph. W. Besslich. On the complexity of Mod-2 sum PLA's // IEEE Trans, on Сотр., Vol. C-29, No. 2, Feb. 1990. pp. 262-266.

28. I. Schafer and M. A. Perkowski. Multiple-valued input generalized Reed-Muller for // Proc. of the Inter. Symp. on Multiple-Valued Logic, May 1991. pp. 40-48. URL :http://web.cecs.pdx.edu/%7Emperkows/=PUBLICATIONS/PER/G 1992/001 80011.pdf (дата обращения: 24.05.2009).

29. Т. Hirayama, Y. Nishitani, T. Sato. A Faster Algorithm of Minimizing AND-EXOR Expressions // IEICE Trans, on Fund., Vol E85-A, No. 12, 2002. pp. 2708-2714. URL:http://www.kono.cis.iwate-u.ac.jp/%7Ehirayama/research/reprint/ HirNisSat02d.pdf (дата обращения: 07.11.2011).

30. S. Stergiou, K. Daskalakis, G. Papakonstantinou. A Fast and Efficient Heuristic ESOP Minimization Algorithm. URL: http://people.csail.mit.edu/ costi s/papers/esop.pdf (дата обращения: 16.11.2011).

31. L. Csanky, M.A. Perkowski, I. Schafer. Canonical restricted mixed-polarity exclusive-OR sums of products and the efficient algorithm for their minimization.

URL :http://web.cecs.pdx.edu/%7Emperkows/=PUBLICATIONS/PER/G 1993/001 93779.pdf (дата обращения: 21.11.2011).

32. M. Sampson, D. Voudouris, M. Kalathas, G. Papakonstantinou. A Quantum algorithm for Finding Minimum Exclusive-Or Expressions for Incompletely Specified Boolean Functions. URL:

http ://w ww. aueb. gr/py mpe/hercma/_proceedings2007/H07-FULL-PAPERS-

1/SAMPSON-VOUDOURIS-KALATHAS-PAPAKONSTANTINOU-1 .pdf (дата обращения: 09.08.2010).

33. S. Stergiou, K. Daskalakis, G. Papakonstantinou. A Fast and Efficient Heuristic ESOP Minimization Algorithm // GLSVLSI'04, April 26-28, 2004,

Boston, Massachusetts, USA. URL:

http://people.csail.mit.edu/costis/papers/esop.pdf (дата обращения: 09.08.2010).

34. Alan Mishchenko and Marek Perkowski. Fast Heuristic Minimization of Exclusive Sums-of-Products // Proc. RM'2001 Workshop, August 2001. URL :http://web.cecs.pdx.edu/%7Ealanmi/publications/rm01-heu.pdf (дата обращения: 09.08.2010).

35. Debatosh Debnath and Tsutomu Sasao. The Eigenfunction of the Reed-Muller Transformation. URL: http: //www, lsi-cad.com/sasao/Papers/Files/RM1999 debnath.pdf (дата обращения: 12.07.2009).

36. Т. Sasao J. Т. Butler. The Eigenfunction of the Reed-Muller Transformation. URL:http://www.Isi - cad.com/sasao/Papers/files/RJVI2007_ sasao.pdf (дата обращения: 12.07.2009).

37. Shinobu Nagayama, Tsutomu Sasao, Jon T. Butler. Design Method for Numerical Function Generators Based on Polynomial Approximation for FPGA Implementation. URL:http://www.lsi-cad.com/sasao/Papers/files/ DSD2007_nagayama.pdf (дата обращения: 12.07.2009).

38. Geetha V., Devarajan N., Neelakantan P. N. OR-Bridging Fault Analysis and Diagnosis for Exclusive-OR Sum of Products Reed-Muller Canonical Circuits // Journal of Computer Science 7 (5). 2011. pp. 744-748.

39. Tsutomu Sasao. Easily Testable Realizations for Generalized Reed-Muller Expressions // IEEE TRANSACTIONS ON COMPUTERS, VOL. 46, NO. 6, JUNE 1997. pp.709-716.

40. Porwik P. Efficient calculation of the Reed-Muller form by means of the Walsh transform //Int. J. Appl. Math. Comput. Sci., 2002, Vol.12, No.4, 571579. URL:http://matwbn.icm.edu.pl/ksiazki/amc/amc 12/amc 12412.pdf (дата обращения: 12.07.2009).

41. Kalay U, Hall D.V. and Petrowski M.A. A Minimal Universal Test Set for Self-Test of EXOR-Sum-of-Products Circuits // IEEE Trans. Computers, vol.49, no.3, Mar.2000. pp. 267-276.

42. Супрун В.П. Метод преобразования д.н.ф. булевых функций в канонический полином Жегалкина // Автоматика и вычислительная техника. 1984. N2. С. 78-81.

43. Супрун В.П. Табличный метод полиномиального разложения булевых функций // Кибернетика. 1987. N 1. С. 116 - 117.

44. Авгуль Л.Б., Супрун В.П. Декомпозиция булевых функций на основе полиномиального разложения // Известия АН СССР. Техническая кибернетика. 1989. N3.C. 187-191.

45. Супрун В.П. Сложность булевых функций в классе канонических поляризованных полиномов // Дискретная математика. 1993. Т.5. вып. 2. С. 111-115.

46. Закревский А. Д. Минимальная реализация частичных булевых функций полиномами Жегалкина // Автоматика и телемеханика. 1996. № 5. С.134-140.

47. Закревский А. Д. Алгоритмы синтеза полиномов, реализующих слабо определенные булевы функции и системы // Автоматика и телемеханика. 2004. №6. С. 158-176.

48. Малюгин В. Д. Реализация кортежей булевых функций посредством линейных арифметических полиномов // АиТ. 1984. № 2. С. 114-121.

49. Малюгин В.Д. Реализация булевых функций арифметическими полиномами // АиТ. 1982. № 4. С. 84-93.

50. Выхованец B.C. Полиномиальная факторизация спектральных базисов // Автоматика и телемеханика. 2004. № 12. С.3-14

51. Выхованец B.C. Алгебраическая декомпозиция дискретных функции // Автоматика и телемеханика. 2006. № 3. С. 20—53

52. Перязев H.A. Основы теории булевых функций. - М.: Физматлит. 2000. 109 с.

53. Винокуров С. Ф. , Перязев Н. А. Полиномиальная декомпозиция булевых функций // Матем. заметки, Т.53. №2. 1993. С.25-29.

54. Винокуров С. Ф. , Перязев Н. А. Полиномиальная декомпозиция булевых функций по образам однородных операторов от невырожденных функций // Изв. вузов. Математика. 1996, № 1(404). С. 17-21.

55. Попель Д.В. Теоретико-информационный метод минимизации булевых функций в классе полиномов Рида-Малера. URL:http://vmw.dslib.netyeconom-teoria/teoretiko-metodologicheskie-aspekty-formirovaniia-informacionnoi-iekonomiki.html (дата обращения: 10.08.2010).

56. Зайцева Е., Попель Д. Разложение неполностью определенной логической функции по переменным в логике Рида-Маллера. URL:www.bakeru.edu/faculty/ dpopel/.../pdf/CadDD'97.pdf (дата обращения: 12.07.2009).

57. Романкевич A.M., Гроль В.В., Мирошникова O.A. Построение легкотестируемых цифровых устройств с использованием форм Рида-Маллера // Радюелекронш i комп'ютерш системи. 2007. № 7 (26). С. 153— 157.

URL:http://www.khai.edu/csp/nauchportal/Arhiv/R£KS/2007/REKS707/pdf/Rom anGro.pdf (дата обращения: 02.10.2012).

58. Романкевич A.M., Гроль В.В., Мирошникова O.A. Тестопри годные цифровые схемы с разветвлениями // Вюник Хмельницького нащонального ушверситету. 2005. 4.1. Т.2. № 4. С. 155-163. URL:http://www.khai.edu/csp/nauchportal/Arhiv/REKS/2007/REKS707/pdf/Rom anGro.pdf (дата обращения: 02.10.2012).

59. Жегалкин И.И. Арифметизация символической логики / И.И. Жегалкин // Математический сборник Московского математического общества, 1927. - Т. 354. - С. 9-28.

60. Карпов Ю. Г. Теория автоматов. - СПб.: Питер, 2002. - 224 с.

61. Гаврилов Г.П., Сапоженко A.A. Задачи и упражнения по дискретной математике: Учеб. пособие. - 3-е изд., перераб. - М.: ФИЗМАТЛИТ, 2005. - 416 с.

62. Алиев Ф.К., Юров И.А. Курс лекций по математической логике и теории алгоритмов: Учебное пособие . - M.: МИФИ, 2003. — 200 с.

63. Горбатов В.А., Горбатов A.B., Горбатова М.В. Теория автоматов: учеб. для студентов втузов. - М.: АСТ:Астрель, 2008. 559 с.

64. Бохманн Д. Двоичные динамические системы / Д. Бохманн, X. Постхоф. М.: Энергоатомиздат, 1986. 400 с.

65. Mozammei H.A. Khan. An ASIC Architecture for Generation Optimum Mixed Polarity Reed - Muller Expression // Engineering Letters, 13:3, EL1332 (Advance online pulication: 4 November 2006). - 8c.

66. Самарский A.A., Гулин A.B. Численные методы. - M.: Наука, 1989.-432 с.

67. Математическая энциклопедия: Гл. ред. И.М. Виноградов, Т. 1 А-Г. М.: «Советская энциклопедия», 1977. 1152 с.

68. Криницкий H.A. Равносильные преобразования алгоритмов и программирование. - М.: Советское радио, 1970. 304 с.

69. Казимиров А. С. Операторные преобразования и минимизация полиномиальных представлений булевых функций: диссертация...кандидата физико-математичесикх наук: 01.01.09 / [Место защиты: Сиб. федер. ун-т].-Иркутск, 2007,- 90 е.: ил. РГБ ОД, 61 07-1/1604.

70. Bakoev V. and Manev К., Fast computing of the positive polarity Reed-Muller transform over GF(2) and GF(3) // Proc. of the XI Intern. Workshop on Algebraic and Combinatorial Coding Theory (ACCT), 16-22 June, 2008, Pamporovo, Bulgaria, pp. 13-21.

71. Акинин A.A., Акинина Ю.С., Подвальный С.Л., Тюрин C.B. Автоматизация полиномиального разложения булевых функций на основе метода неопределенных коэффициентов // Системы управления и информационные технологии. № 2 (44). 2011. С. 4-8.

72. Акинин A.A., Тюрин C.B. Асинхронный двоичный счётчик // Патент на изобретение RUS. 2452084 от 24.12.2009; опубл. 27.05.2012; Бюл. № 15.

73. Акинин A.A., Подвальный C.JL Программный модуль преобразования дизъюнктивных нормальных форм булевой функции в полином Жегалкина // Вестник Воронежского государственного технического университета. Т. 7. №4. Воронеж, ВГТУ, 2011. - с. 183-186.

74. Математическая энциклопедия: Гл. ред. И.М. Виноградов, т. 2 Д-К. М.: Советская энциклопедия, 1979. 1104 с.

75. Ахметова H.A., Усманова З.М. Дискретная математика. Функции алгебры логики: Учебное пособие. - Уфа: Уфимский государственный авиационный технический университет. 1998. 109 с.

76. Бережная М.А., Рыжикова М.Г., Татаренко Д.А. Синтез комбинационных схем в базисе полиномиальных форм // Радиоэлектроника и информатика: научно-технический журнал. Харьков: ХНУР, 2005. №3. С. 103-109.

77. Акинин А. А., Акинина Ю.С., Тюрин C.B. Автоматизация полиномиального разложения булевых функций на основе метода конечных разностей // Системы управления и информационные технологии. 2011. № 4. С. 69 - 73

78. Акинин A.A. Алгоритм фрактального полиномиального разложения булевых функций // Вестник Воронежского государственного технического университета. 2011. Т. 7 . №11. 1. С. 85-88

79. Акинин A.A. Автоматизация полиномиального разложения булевых функций методом фрактальных преобразований // Интеллектуальный потенциал молодых ученых России и зарубежья: Материалы V Международной научно-практической конференции. М.: Издательство «Спутник+», 2012. С. 9-18.

80. Акинин А. А., Акинина Ю.С., Тюрин C.B. Метод бинарно-векторного полиномиального разложения булевых функций // Сборник

трудов V Всероссийской научно-технической конференции «Проблемы разработки перспективных микро- и наноэлектронных систем 2012». Москва, ИППМ РАН, 2012 г. С. 55-60.

81. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. М.: Радио и связь, 1990. 304 с.

82. Хортон A. Visual С ++ 2005: базовый курс. - М.: ООО «И. Д. Вильяме», 2007. 1152 с.

83. Страуструп Б. Язык программирования С++. Специальное издание. М.: ООО «Бином-Пресс», 2008. 1104 с.

84. Александреску А. Современное проектирование на С++ (серия С++ in Depth). M.: Издательский дом "Вильяме", 2008. 336с

85. Мейерс С. Эффективное использование С++. 55 верных способов улучшить структуру и код ваших программ. 3-е издание. М.: ДМК Пресс, 2006. 300с

86. Акинин A.A., Акинина Ю.С. О программной реализации алгоритма восстановления совершенной дизъюнктивной нормальной формы // Информационные технологии моделирования и управления. 2010, №6(65). С. 726-731.

87. Рихтер Дж. Windows для профессионалов: создание эффективных Win32 приложений с учетом специфики 64-разрядной версии Windows. 4-е изд. М.: Издательско-торговый дом "Русская Редакция", 2004. 752 с.

88. Иртегов Д. В. Введение в операционные системы. СПб.: БХВ -Петербург, 2002. 624 с.

89. Акинина Ю.С. Оптимистическая оценка сложности алгоритма восстановления совершенной дизъюнктивной нормальной формы // Техника машиностроения. М.: ООО НТП "Вираж-Центр", 2002. № 5 (39). С. 74-75

90. Акинин А. А., Акинина Ю.С., Тюрин C.B. Программа "Преобразователь булевых функций" // Свидетельство о государственной регистрации программы для ЭВМ № 2012614544 от 21 мая 2012 г.

91. Акинин A.A. Вычислительная сложность оптимизированных алгоритмов полиномиального преобразования булевых функций // Теория и численные методы решения обратных и некорректных задач: материалы Международной молодежной научной школы. Воронеж: ИПЦ «Научная книга», 2012. С. 58-62.

92. Акинин A.A., Подвальный C.J1. Сравнительная оценка вычислительных алгоритмов полиномиального преобразования булевых функций // "Вестник Воронежского государственного технического университета". Т. 9. №1. Воронеж, ВГТУ, 2013. С. 31-35.

93. Акинин A.A. Оптимизация алгоритма полиномиального преобразования булевых функций // Современные проблемы информатизации в анализе и синтезе программных и телекоммуникационных систем: Сборник трудов, вып. 17. Воронеж, 2012. С. 256 - 257.

94. Акинин А. А., Акинина Ю.С., Тюрин C.B. Программа "Статистическая оценка быстродействия программ полиномиального преобразования булевых функций " // Свидетельство о государственной регистрации программы для ЭВМ № 2012614544 от 21 мая 2012г.

95. Акинин A.A., Акинина Ю.С., Подвальный C.JI. Общие подходы к преобразованию булевых функций в поляризованные полиномы Рида-Маллера // Новые технологии в научных исследованиях, проектировании, управлении, производстве: труды Всероссийской конференции. Воронеж, ВГТУ, 2013 г. С. 48-49.

РО С ОШЖ^А Я ФДД.УРАШ И И

ш ш ш ®

ж

ш ш

т ш ш ш т

ш

ш щ

ж

-ш-ж

НА ИЗОБРЕТЕНИЕ

№ 2452084.

АСИНХРОННЫЙ ДВОИЧНЫЙ: СЧЁТЧИК

11 а те нтообл адате.!! ь (ли): Государст венн ое образовател ь но е учрелсдение высшего профессионального образования 'Воронежский государственный технический университет' (Ш)

Автор(ы): елг, на обороте

х-" г.,

У-*- Д-

г" V» * А

Заявка № 2009148255

Приоритет изобретения 24 декабря 2009 Г. Зарегистрировано в Государственном реестре изобретений Российской Федерации 27мая 2012 г. Срок действия патента истекает 24 декабри 2029 г.

Руководитель Федеральной службы по импе.чхектуалыюй собственности.

/>.//. Сгшонов

' Кг ^ -

штттшшштштттшшшшшш»«т ш т~тштттмш

РОССИЙСКАЯ ФЬДЬРАЦИЯ

(19|

сч

О

Tf

со о <м

ю

Tt

сч|

RU

(in

С2

f5|, мпк

1103К 2V58 ( 2006 011

ФКДЫ'ЛЛЬНЛЯ СЛУЖБА НО ИНIЬЛЛЬКЛ Ч'АЛЬНОЙ СОБСТВЬННОСI И

''-> ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ

(21 1(221 киянка 2009148255/08 24 12 2004

04) Дата начала окчспа срока действия пакта 24 12 2009

Приоршеиы)

02| Дай но ычи ыявки 2И2 2009

1-4 Ъ Даы пубчикации мявки 27 06 2011 Бюд Мг

(15) 011)6 жмтано 27 05 2012 Бкт > 15

(5(1) С иисок доку мен юв цинцадвлпныч ц емче 1с о поиске IIЧ 4012722 А 15 03 1977 Б и 1750056 А1, 2107 1992 Яи 1555856 А1, 07 04 1990 .1Г 63164616 А, 08 07 1988 ИР 0746108 А2 04 12 1996

\ (рсс „ни ис])С111кки

394026, г Воронеж Московский нр-м 14 ЮУВ1Ю ВПУ пленгный опел

(5 П ЛСИ11ХРОННЫИ ДВОИЧНЫМ СЧЕТЧИК

I °) I \'фс ра 1

11 кюрек-ние 1ЧИОС1ПСЯ к цифровой нычис кт'мыюП ихнаке Техническим |хм> 1Ы.1ИШ является обеспечение решения комбинатрноП (адачн формирования нссх ВОЛЮЖНЫХ \-ра ¡рядных двоичных кодовых комбинаций в ьоп>рм\ ирсччве ¡\

ра ¡рядов (1ч НМСЮ1 фиксированные

шачсиия УечроПсшо ^одержи!

нос 1едова1е паю нодк'ноченные идешичные (.чешые секции каждая и< которых содержит счешый (ринер <-хем\ управления д 1Я сю нараипе 1ыюП ки ручки и схему \npau гения \кжра¡ря (ним переносом ичпоящ^ю п< немспм И ПИ (рех немец юв И немец и ИГ 2и1

(72» Лнгор( ы)

Акинин Андрей Л 1ександрович (RU) Тюрин Cepiefi В 1адимирович (Rl'j

(7 i) Па ten I ообчадаie 1ы и)

Государс i венное обра юва (счьнос учреждение высшею профессиональною образования Воронежский государивсиный (ехнический унивсрсигег (RU)

СчТ

73

м ■г», ся ю о 00

о

го

тт

_.Д-4____

4 &

СхУЗ

СхУП

5 &

ъ

1 &

ю

п.

Фиг

Стр

российская федерация

(О СЧ|

СО

см

о см

=э к

„,, RU

ни мпк

G06F II/(X) (2006 01)

'Ah

ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ПН ГЕЛЛЕКТУАЛЫЮЙ СОБСТВЕН НОС ГИ

> iЗАЯВКА IIA ИЗОБРЕТЕНИЕ

uliC2¡ киянка 20! 1123026/08, 07.06 2011 Ирнориюк'ьп

' 221 Да и поллчи ияики 07.06 2011

i-i íi Дли пчСпикации ¡аявки 20 12.2012 Ьюи .4!? 35

Адрес дли переписки

394026. г Воронеж, Московский iip-Ki. 14, ГОХ ВПО "ВП У", патентный oí дел

(71) Ъяшмелыю

Гос\даро1 венное обра юва(ельное учреждение высшею профессиональною образования "Воронежский юсударс!венный 1ехнический универсиге!

(ии)

172) Лнюр(ы)

Акинин Андрей Александрович (К и) Лкинина Юлия Серюевна (КУ). Подвальный Семен Леонидович (Ш,!). Тюрин Сергей Владимирович (Ии)

(5 0 СПОСОБ ТЕСТОПРИГОДНОСТИ РЕАЛИЗАЦИИ ЛОГИЧЕСКИХ ПРЕОБРАЗОВАТЕЛЕЙ

(57) Формула изобре!ения Способ iccionpiii одной реали мции логических преобразователей, включающий первоначальное получение исходною мачематчсскою описания рабочею икона (функционирования n-входовых логических преобра юва i елей в lecionpni одном ло! нческом базисе Жс1алкина. т гем ра ¡рабо i к> и реализацию сгруki> рпой схемы иотческою преобра юва 1еля пулемета lenepaiop ио1ической 1. г последоваюмьных цепочек и ! (к-1) двухвходовых ;ioi ических пементв с злекфонпо перестраиваемой uoi и ческой функцией, реал и íyioijiuv k-аргумепшые функции И в рабочем режиме мчи (функции равно »пачноеш в режиме легирования и !юслед0ва:ел1л!0й цепочки и> íi-i> дв\хвходовых зиемепгов неравно шачносл и. реали ¡ующих рабочую (функцию Н нулем сверили по модулю два всех к-аргумешныч коныопкций. определение в последующем n reciobi.ix М-последовазелыюсгей и i одного тою же шмкпч юю класса и налонной М-последовак'лыюеги. коюрую а;п ори кмически формиру ioi ih n гесювых М-последова 1елыюс1ей. причем в режиме ¡еаировапия i ее юные и малоиную М-пос ледова i ел ы юс i и одновременно leiiepnpyioi внешним п-ра ¡ря.шым peiMcipo.m сдвша с линейной обратной связью на предельно вошожной рабочей часине логическою преобрачова ген я oí ничакнцийся 1ем. мю на )iane pa¡pa6oiKii и реализации ci ру кгурпой схемы лог ическо! о преобрачова юля дополнительно вводя i (s+1) носледова!ельпых цепочек м ¡ (k-1) двухвходовых ло1 ических племен юв с ) к'кгронно перестраиваемой jioi ической функцией и иоследовашльную цепочку из (-.+ I) двухвходовых элементов неравнозначной и. коюрая па выходе (формируе! при «сак ошибки нулем реализации сверчки по модулю два значения функции Fp. всех s дополни 1ельных k-api ументых коныопкций и дополншелыюй n-api умен i ной коныонкции инверсий входных api уменюв. причем сумма s+r=2". ю eeib равна количеепп всех ра>личимых k-api умен i пых коныонкцмП в полиноме Же! алкина

Стр 1

73 С

го

о

го

CJ

о го

СП

»

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2012614545

Программа «Преобразователь булевых функций»

Правооблада!ель(ли): Лкинина Юлия Сергеевна (НИ), Акинин Андрей Александрович (Ш), Тюрин Сергей Владимирович (ЯП)

Автор(ы): Акинина Юлия Сергеевна,

н Андрей Александрович, Тюрин Сергей Владимирович (Ж])

Заявка № 2012612388

Дата поступления 2 апреля 2012 г.

Зарегистрировано в Реестре программ для ЭВМ 21 мая 2012 г.

Руководитель Федеральной службы по интеллектуальной собственности

Б. П. Симонов

ж ^^^ЖЖЖЖЖЖжЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖшЖйП

кзшкшй

ш ш ш

ш

ВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2012614544

Программа «Статистическая оценка быстродействия программ полиномиального преобразования булевых фу нкций»

11равооб.лада 1 ель(ди) Акипина Юлия Сергеевна (ЯП), Акипии Андрей Александрович (НИ), Тюрин Сергей Владимирович (ЯП)

Авюр(ы) Акипина Юлия Сергеетт,

Акинин Андрей Александрович, Тюрин Сергей Владимирович (Я11)

Заявка № 2012612387

Да га поступления 2 апреля 2012 Г. Зарегистрировало и Реестре про! рамм шля ЭВМ 21 мая 2012 г.

Руководитель Федеральной службы по интеллектуальной собственности

Л II Симонов

ш

ш

ш

ш

ш

Й

а

й

ш ш

а «

Я

ЗАО нииэт-смс

" II ЧУЧНО-ИС СЛЕДОВЛТЕЛЬС К И Й ИНС Г И ГУ I *ЛЕКIРОННОИ ГЕХНИКИ-СИГНЛЛЬНЫЕ МИКРОСИС1 ЬМЫ*\ ЧАКРЫ IOL АКЦИОНЕРНОЕ ОБЩЕСТВО

___________оГП^Сг^пис sms vm ru

l'Oiiiiftc-uU К iquiffl i MJ42 r BoptHeA iij i .IfHlittitCiiH i íftí íi фл«. •''(¡7 j.'.'iWM »71)216^74 ИНН ШП jfllj'^iH l>X)í

U[PH Т>ЗД%Ч136С P ^ 'CSl'Kibií--'* i <1 1 в Ific^iT о 1<ци<Л'МОК ihm ( V¡> jte. РФ i

У ГВЕРЖДАК) енеральный директор ЗАО ПИИТГ-СМС

АКТ

В

ri уЩа^-Ьиреля

Кириллов 2013 г.

об использовании результатов кандидатской диссертации Акинина Андрея Александровича «Разработка и программная реализация эффективных дискретных алтригмов минимизации булевых функций в классе полиномиальных форм

с фиксированной полярное 1ыо»

Настоящим актом иодтверждаек'я, чю рафабошшый в коде диссертационного исследования проблемно-ориеншрованный программный комплекс минимизации булевых функций в классе полиномиальных нормальных форм с фиксированной полярностью находи1ся в опытной экыыуакщии и предпола! ается к практическому использованию при разработке специализированных БИС с повышенной радиационной стойкое гыо

Главный конструктор

НИИТ1-СМС

" """С."3'

, '«¿З^ _в II. Крюков

У гверждаю

л

Л к г

о внедрении результатов диссертации » учебный процесс Воронежского государственного технического университета

Разработка и программная реализация эффективных дискретных алгоритмов минимизации булевых функций в .классе полиномиальных форм с фиксированной полярностью_

I ил именование работы. .V? темы. № госрсгистрации!

Автор Акимин Андрей Александрович

Научный руководитель Подвальный Семен Леонидович_______

Выполненной в Воронежском государственном техническом университете_

на кафедре автоматизированных и вычислительных систем

(кафедра, фл культе!. лаборатория. центр и гд.1

а рамках основного научного направления: «Вычислительные комплексы и

проблемно-ориентированные системы управления» ___

в период с Ш .09 .2012 г, по 30 06 . 2013 г. ""*"....."""

внедрены и учебный процесс на основании решения кафедры

автоматизированных и вычислительных систем от 03.09 20/Зг, протокол № /

1 Вид результатов внедренных в учебный процесс: зарегистрированная про-

(комплекс. машина, система, прибор, инструмент, технология, методика.гарегагтырдванные прпгрзи-мы

грамма для ЭВМ «Преобразователь булевых функций»___

лл* ЭВМ. балы .таиных, я т л I

2. Область применения: лабораторный практикум и лекционные курсы но дисциплине «Теория автоматов»; специальность «Вычислительные машины, комплексы, системы и сети» _

(специальность. дисциплина. вид учебной нагручю«)

3. Форма внедрения, описание лабораторной работы, материалы лекционного курса ___

< учебник, учебное пособие, курс лекции, мл, н т.д. с ущплнисм выходных данных >

4 Технический уровень: свидетельство о государственной регистрации про-

( псианы иывки ма 061-2ггы промышленной собственности, получены положительные решения, патенты России.

граммы для ЭВМ Кз 2012614545 от 21 мая 2012 г.________________

дипломы, медали и др м* М> и лат а)

5. Основные публикации по теме диссертации: 15 публикаций, из них 6 в изданиях из списка ВАК_

(количество, где опубликованы)

6. Эффект от внедрения (ожидаемый, фактический):

а) повышение качества образования: изучение алгоритмов и оценок вьтчис-

(информаиия о новыч знаниях, умениях, навыках, приобретаемым студентами или аспирантами.

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

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

б) социальный

{улучшение условий труда. о'!доровлснис окружающей среды и др )

в) экономический

Руководитель основного научного Начальник управления образователь-направления ных программ

_ti^ci-j___СЛ. Подвальный______A.B. Халявина

(надпись Ф И (подпись. Ф.И О )

«<)>г» „ <-.- 2013 г. « ^ » /с 2013 г.

Научный руководитель Декан факультета^ _^ Сс-'у СЛ. Подвальный ■„..,... " С.М. Пасмурное

(подпись, Ф И CjV ' (подпись, фйа Г* .

__20!3 г. « ? >, /О 2013 г.

Автор - Заведующий кафедрой __________ A.A. Акинин___t i / С.Л. Подвальный

(должность. уч. сгснень. подпись. Ф И.О ) (подпись. Ф И О ) {/

« 09 » о/'7у5})Л 2013 г. »__/ о........ _ ___2013 г.