Программные продукты и системы, 2023, том 36, № 4

Научно-исследовательский институт

«Центрпрограммсистем»

Программные

продукты и системы

НАУЧНЫЙ ЖУРНАЛ

2023, том 36, № 4

(год издания тридцать шестой)

Главный редактор

Г.И. САВИН, академик РАН

SOFTWARE & SYSTEMS

Research Journal

2023, vol. 36, no. 4

Editor-in-Chief 

G.I. SAVIN, Academician of the Russian Academy of Sciences

Research Institute CENTERPROGRAMSYSTEM

 ПРОГРАММНЫЕ ПРОДУКТЫ И СИСТЕМЫ
Научный журнал 

2023. Т. 36. № 4
DOI: 10.15827/0236-235X.142

Главный редактор 

Г.И. САВИН, академик РАН

Научные редакторы номера:

А.П. ЕРЕМЕЕВ, д.т.н., профессор

С.В. УЛЬЯНОВ, д.ф.-м.н., профессор

Издатель НИИ «Центрпрограммсистем»

(г. Тверь, Россия)

Учредитель В.П. Куприянов

Журнал зарегистрирован в Роскомнадзоре

3 марта 2020 г.

Регистрационное свидетельство ПИ № ФС 77-77843

Подписной индекс в каталоге

Урал-Пресс 70799

ISSN 0236-235X (печатн.)
ISSN 2311-2735 (онлайн)

РЕДАКЦИОННАЯ КОЛЛЕГИЯ

Семенов Н.А. – заместитель главного редактора, д.т.н., профессор Тверского государственного технического 
университета (г. Тверь, Россия)
Сотников А.Н. – заместитель главного редактора, д.ф.-м.н., профессор, заместитель директора 
Межведомственного суперкомпьютерного центра РАН (г. Москва, Россия)
Афанасьев А.П. – д.ф.-м.н., профессор Московского физико-технического института (технического университета),
заведующий Центром распределенных вычислений Института проблем передачи информации РАН (г. Москва, Россия)
Баламетов А.Б. – д.т.н., профессор Азербайджанского научно-исследовательского и проектно-изыскательского института 
энергетики (г. Баку, Азербайджан)
Борисов В.В. – д.т.н., профессор филиала Национального исследовательского университета «МЭИ» 
в г. Смоленске (г. Смоленск, Россия)
Голенков В.В. – д.т.н., профессор Белорусского государственного университета информатики и радиоэлектроники 
(г. Минск, Беларусь)
Елизаров А.М. – д.ф.-м.н., профессор Института математики и механики им. Н.И. Лобачевского Казанского федерального 
университета (г. Казань, Россия)
Еремеев А.П. – д.т.н., профессор Национального исследовательского университета «МЭИ» (г. Москва, Россия)
Кузнецов О.П. – д.т.н., профессор Института проблем управления РАН (г. Москва, Россия)
Курейчик В.М. – д.т.н., профессор Инженерно-технологической академии Южного федерального университета (г. Таганрог, Россия)
Мамросенко К.А. – к.т.н., доцент Московского авиационного института (национального исследовательского университета), 
руководитель Центра визуализации и спутниковых информационных технологий НИИСИ РАН (г. Москва, Россия)
Палюх Б.В. – д.т.н., профессор Тверского государственного технического университета (г. Тверь, Россия)
Сулейманов Д.Ш. – академик АН Республики Татарстан, д.т.н., профессор Казанского государственного технического 
университета (г. Казань, Республика Татарстан, Россия)
Татарникова Т.М. – д.т.н., доцент, профессор Санкт-Петербургского государственного 
электротехнического университета «ЛЭТИ» им. В.И. Ульянова (Ленина) (г. Санкт-Петербург, Россия)
Ульянов С.В. – д.ф.-м.н., профессор, ведущий научный сотрудник Объединенного института ядерных исследований 
(г. Дубна, Россия)
Хорошевский В.Ф. – д.т.н., профессор Московского физико-технического института (технического университета) 
(г. Москва, Россия)
Шабанов Б.М. – д.т.н., чл.-корр. РАН, директор Межведомственного суперкомпьютерного центра РАН (г. Москва, Россия)
Язенин А.В. – д.ф.-м.н., профессор Тверского государственного университета (г. Тверь, Россия)

АССОЦИИРОВАННЫЕ ЧЛЕНЫ РЕДАКЦИИ

Национальный исследовательский университет «МЭИ», г. Москва, Россия
Технологический институт Южного федерального университета, г. Таганрог, Россия
Тверской государственный технический университет, г. Тверь, Россия

АДРЕС ИЗДАТЕЛЯ И РЕДАКЦИИ 
Россия, 170024, 
г. Тверь, просп. Николая Корыткова, д. 3а
Телефон (482-2) 39-91-49
Факс (482-2) 39-91-00
E-mail: red@cps.tver.ru
Сайт: www.swsys.ru

Дата выхода в свет 16.12.2023 г.
Отпечатано ИПП «Фактор и К»

Россия, 170100, г. Тверь, ул. Крылова, д. 26

Выпускается один раз в квартал

Год издания тридцать шестой 

Формат 6084 1/8. Объем 200 стр.

Заказ № 16. Тираж 1000 экз. Цена 550,00 руб.

 SOFTWARE & SYSTEMS 
Research journal
2023, vol. 36, no. 4
DOI: 10.15827/0236-235X.142

Editor-in-chief 
G.I. SAVIN, Academician of RAS

Science editors of the issue:

A.P. Eremeev, Dr.Sc. (Engineering), Professor
S.V. Ulyanov, Dr.Sc. (Physics and Mathematics), Professor

Publisher Research Institute 

CENTERPROGRAMSYSTEM (Tver, Russian Federation)

Founder V.P. Kupriyanov

The journal is registered with the Federal Service 

for Supervision of Communications, Information Technology 

and Mass Communications (Roskomnadzor) 

March 3rd, 2020

Registration certificate ПИ № ФС 77-77843

ISSN 0236-235X (print)
ISSN 2311-2735 (online)

EDITORIAL BOARD

Semenov N.A. – Deputy Editor-in-Chief, Dr.Sc. (Engineering), Professor of the Tver State Technical University
(Tver, Russian Federation)
Sotnikov A.N. – Deputy Editor-in-Chief, Dr.Sc. (Physics and Mathematics), Professor, Deputy Director
of the Joint Supercomputer Center of the Russian Academy of Sciences (Moscow, Russian Federation)
Afanasiev A.P. – Dr.Sc. (Physics and Mathematics), Professor of the Moscow Institute of Physics and Technology, 
Head of Centre for Distributed Computing of Institute for Information Transmission Problems 
(Moscow, Russian Federation)
Balametov A.B. – Dr.Sc. (Engineering), Professor of the Azerbaijan Scientific-Research & Design-Prospecting Power Engineering 
Institute (Baku, Azerbaijan)
Borisov V.V. – Dr.Sc. (Engineering), Professor of the MPEI Branch in Smolensk (Smolensk, Russian Federation)
Golenkov V.V. – Dr.Sc. (Engineering), Professor of the Belarusian State University of Informatics and Radioelectronics 
(Minsk, Republic of Belarus)
Elizarov A.M. – Dr.Sc. (Physics and Mathematics), Professor of the N.I. Lobachevsky Institute of Mathematics 
and Mechanics of the Kazan Federal University (Kazan, Russian Federation)
Eremeev A.P. – Dr.Sc. (Engineering), Professor of the National Research University Moscow Power Engineering 
Institute (Moscow, Russian Federation)
Kuznetsov O.P. – Dr.Sc. (Engineering), Professor of the Institute of Control Sciences of the Russian Academy 
of Sciences (Moscow, Russian Federation)
Kureichik V.M. – Dr.Sc. (Engineering), Professor of the Academy of Engineering and Technology of the Southern
Federal University (Taganrog, Russian Federation)
Mamrosenko K.A. – Ph.D. (Engineering), Associate Professor of the Moscow Aviation Institute (National Research
University), Head of the Center of Visualization and Satellite Information Technologies SRISA RAS 
(Moscow, Russian Federation)
Palyukh B.V. – Dr.Sc. (Engineering), Professor of the Tver State Technical University (Tver, Russian Federation)
Suleimanov D.Sh. – Academician of TAS, Dr.Sc. (Engineering), Professor of the Kazan State Technical University
(Kazan, Republic of Tatarstan, Russian Federation)
Tatarnikova T.M. – Dr.Sc. (Engineering), Associate Professor, Professor of the St. Petersburg Electrotechnical 
University LETI (St. Petersburg, Russian Federation)
Ulyanov S.V. – Dr.Sc. (Physics and Mathematics), Professor of the Dubna International University for Nature, 
Society and Man (Dubna, Russian Federation)
Khoroshevsky V.F. – Dr.Sc. (Engineering), Professor of the Moscow Institute of Physics and Technology
(Moscow, Russian Federation)
Shabanov B.M. – Dr.Sc. (Engineering), Corresponding Member of the RAS, Director of the Joint Supercomputer Center 
of the Russian Academy of Sciences (Moscow, Russian Federation)
Yazenin A.V. – Dr.Sc. (Physics and Mathematics), Professor of the Tver State University (Tver, Russian Federation)

ASSOCIATED EDITORIAL BOARD MEMBERS

National Research University Moscow Power Engineering Institute, Moscow, Russian Federation
Technology Institute at Southern Federal University, Taganrog, Russian Federation
Tver State Technical University, Tver, Russian Federation

EDITORIAL BOARD AND PUBLISHER OFFICE ADDRESS 
Nikolay Korytkov Ave, 3а, Tver, 170024, Russian Federation
Phone: (482-2) 39-91-49  Fax: (482-2) 39-91-00
E-mail: red@cps.tver.ru
Website: www.swsys.ru

Release date 16.12.2023

Printed in printing-office Faktor i K

Krylova St. 26, Tver, 170100, Russian Federation

Published quarterly. 36th year of publication

Format 6084 1/8. Circulation 1000 copies

Prod. order № 16. Wordage 200 pages. Price 550,00 rub. 

Вниманию авторов

Журнал «Программные продукты и системы» публикует материалы научного и научно-практического 

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

Журнал «Программные продукты и системы» внесен в Перечень ведущих рецензируемых научных жур-

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

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

РИНЦ, в CrossRef и в другие базы и электронные библиотеки.

Журнал «Программные продукты и системы» включен в ядро коллекции РИНЦ, размещенное на плат-

форме Web of Science в виде базы данных RSCI.

Автор статьи отвечает за подбор, оригинальность и точность приводимого фактического материала. 

При перепечатке ссылка на журнал обязательна. Статьи публикуются бесплатно.

Условия публикации

К рассмотрению принимаются оригинальные материалы, отвечающие редакционным требованиям и со-

ответствующие тематике журнала. Группы научных специальностей: 

1.2. Компьютерные науки и информатика 
1.2.1. Искусственный интеллект и машинное обучение (физико-математические науки). 
1.2.2. Математическое моделирование, численные методы и комплексы программ (физико-математиче-

ские науки, технические науки)

2.3. Информационные технологии и телекоммуникации
2.3.1. Системный анализ, управление и обработка информации, статистика (технические науки, физико-

математические науки). 

2.3.2. Вычислительные системы и их элементы (технические науки).
2.3.3. Автоматизация и управление технологическими процессами и производствами (технические 

науки). 

2.3.5. Математическое и программное обеспечение вычислительных систем, комплексов и компьютер-

ных сетей (технические науки, физико-математические науки).

2.3.6. Методы и системы защиты информации (технические науки, физико-математические науки).
2.3.7. Компьютерное моделирование и автоматизация (технические науки, физико-математические науки).
2.3.8. Информатика и информационные процессы (технические науки).
Работа представляется в электронном виде в формате Word. Объем статьи вместе с иллюстрациями – не 

менее 10 000 знаков. Диаграммы, схемы, графики должны быть доступными для редактирования (Word, 
Visio, Excel). Заголовок должен быть информативным; сокращения, а также терминологию узкой тематики 
желательно в нем не использовать. Количество авторов на одну статью – не более 4, количество статей одного 
автора в номере, включая соавторство, – не более 2. Список литературы, наличие которого обязательно, 
должен включать не менее 10 пунктов.

Необходимы также содержательная структурированная аннотация (не менее 250 слов), ключевые слова 

(7–10) и индекс УДК. Название статьи, аннотация и ключевые слова должны быть переведены на английский 
язык (машинный перевод недопустим), а фамилии авторов, названия и юридические адреса организаций 
(если нет официального перевода) – транслитерированы по стандарту BGN/PCGN. 

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

материала и авторскую справку. Обзательно соблюдение автором договора (публичной оферты).

Порядок рецензирования

Все статьи, поступающие в редакцию (соответствующие тематике и оформленные согласно требованиям 

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

В редакции сформирован устоявшийся коллектив рецензентов, среди которых члены редколлегии жур-

нала, эксперты из числа крупных специалистов в области информатики и вычислительной техники ведущих 
вузов страны, а также ученые и специалисты НИИСИ РАН, МСЦ РАН (г. Москва) и НИИ «Центрпрограмм-
систем» (г. Тверь).

Редакция журнала «Программные продукты и системы» в своей работе руководствуется сводом правил 

Кодекса этики научных публикаций, разработанным и утвержденным Комитетом по этике научных публикаций (
Committee on Publication Ethics – COPE).

Программные продукты и системы / Software & Systems
36(4), 2023

509

УДК 519.714.5
doi: 10.15827/0236-235X.142.509-522
2023. Т. 36. № 4. С. 509–522

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

подсистем для совместной логической минимизации

П.Н. Бибило

Н.А. Кириенко

В.И. Романов

Ссылка для цитирования
Бибило П.Н., Кириенко Н.А., Романов В.И. Выделение из многоуровневого представления системы булевых функций 
подсистем для совместной логической минимизации // Программные продукты и системы. 2023. Т. 36. № 4. 
С. 509–522. doi: 10.15827/0236-235X.142.509-522
Информация о статье
Поступила в редакцию: 31.05.2023
После доработки: 04.07.2023
Принята к публикации: 10.07.2023

Аннотация. В статье приводятся результаты экспериментальных исследований эффективности программ минимизации 
многоуровневых алгебраических представлений систем булевых функций, выполняемых при синтезе 
комбинационных схем. Результирующие минимизированные логические описания представлены в виде формул 
разложений Шеннона или формул, задающих булевы сети. Исследуются три подхода: совместная минимизация 
многоуровневых представлений систем булевых функций, раздельная минимизация и выделение из исходной системы 
связанных подсистем. При этом каждая из этих подсистем минимизируется отдельно, а функции, составляющие 
их, совместно. После получения минимизированных описаний схем, заданных в виде совокупности взаимосвязанных 
формул разложения Шеннона либо двухоперандных логических уравнений, соответствующих булевым 
сетям, осуществляется синтез логических схем в одной и той же библиотеке проектирования заказных цифровых 
сверхбольших интегральных схем, выполненных по КМОП СБИС (комплементарной метал-оксид-полупроводник 
технологии). Полученные логические схемы сравниваются по площади кристалла и по быстродействию (временной 
задержке). Были проведены эксперименты на 39 промышленных примерах схем. Pезультаты показали конкурентоспособность 
и целесообразность использования на практике всех трех рассмотренных подходов. Улучшение 
параметров схем (площадь, временная задержка) при выделении из исходной системы связанных подсистем достигается 
за счет того, что каждая выделенная подсистема минимизируется на основе разложений Шеннона по 
своей (для каждой подсистемы) перестановке переменных разложения. При этом для одной половины схем более 
эффективным является минимизация многоуровневых представлений на основе разложений Шеннона для исходных 
матричных описаний систем функций, а для другой – на основе разложений Шеннона систем функций, представленных 
в виде логических уравнений. Практическая значимость проведенного исследования заключается в 
том, что использование разработанной программы, реализующей предложенный алгоритм выделения подсистем 
булевых функций, позволяет во многих случаях сокращать площадь и увеличивать быстродействие функциональных 
блоков заказных КМОП СБИС.
Ключевые слова: система булевых функций, многоуровневое представление, дизъюнктивная нормальная форма, 
BDD, булева сеть, синтез логической схемы, VHDL, СБИС, КМОП-технология

Введение.
Минимизация двухуровневых 

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

описаниях 
различного 
вида. 

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

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

При минимизации многоуровневых скобоч-

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

Программные продукты и системы / Software & Systems
36(4), 2023

510

ным для уменьшения площади схем заказных 
СБИС. В качестве структур данных при решении 
задач факторизации использованы булевы 
сети, представленные ориентированными бес-
контурными графами DAG (Directed-Acyclic-
Graph). При декомпозиции систем функций 
были разработаны различные методы совместной 
декомпозиции, при которой одна и та же 
промежуточная функция может использоваться 
совместно – участвовать в разложениях 
(суперпозициях) нескольких функций исходной 
системы. 

Несколько последних десятилетий в каче-

стве основных методов технологически независимой 
оптимизации многоуровневых представлений 
систем булевых функций применяются 
методы минимизации графовых BDD
(Binary Decision Diagram)-представлений [1]
и их модификаций, при этом внимание чаще 
уделяется совместной минимизации [1, 2] и декомпозиции [
3, 4] BDD-представлений систем 
функций. Следует заметить, что структуры 
данных в виде BDD-представлений широко используются 
также при верификации логических 
схем, построении тестов и решении сложных 
задач в различных областях информатики. 
Размерность задач проектирования СБИС возрастает 
в связи с совершенствованием технологических 
процессов производства СБИС и 
уменьшением технологических норм [1]. Решение 
задач логической оптимизации начинается 
совместно с задачами топологического и физического 
проектирования СБИС с широким использованием 
программ проверки выполнимости 
конъюнктивной нормальной формы (КНФ) 
булевых функций, называемых SAT-solvers
(Boolean Satisfiability problem – задача выполнимости 
булевой формулы, представленной в 
виде КНФ) [5–7]. 

После BDD для задания систем булевых 

функций появились новые структуры данных, 
которые используются при решении задач технологически 
независимой логической оптимизации [
5–7]. Это AIG (AND-Inverter-Graph), 
XMG (XOR-Majority-Graph) [8], MIG (Majority-
Inverter-Graph) [9–11], XAIG (XOR-AND-
Inverter-Graph) [12]. Структуры AIG положены 
в основу системы ABC
(http://www.eecs.

berkeley.edu/˜alanmi/abc) – известной академической 
системы оптимизации представлений 
систем булевых функций и синтеза логических 
схем. Характерной особенностью решаемых с 
помощью этих структур оптимизационных задач 
является то, что они используются для совместной 
реализации систем булевых функций. 

Раздельная 
минимизация 
многоуровневых 

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

Одинаковость частей в таблицах истинно-

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

В данной работе предложены новая мера 

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

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

булевых функций на основе 

разложения Шеннона

BDDI-представления системы булевых

функций. Под BDDI (Binary Decision Diagram

Программные продукты и системы / Software & Systems
36(4), 2023

511

with Inverse cofactors) понимается ориентированный 
бесконтурный граф, задающий последовательные 
разложения Шеннона булевой 
функции f(x) либо системы F = {f1(x), …, f m(x)} 
булевых функций по всем переменным x1, …, xn
при заданном порядке (перестановке) переменных, 
по которым проводятся разложения, при 
условии нахождения пар взаимно инверсных 
кофакторов. Разложением Шеннона булевой 
функции f(x) = f(x1, …, xn) по переменной xi является 
представление f(x) в виде

0
1
( )
.
i
i
f x
x f
x f
=


Каждый из кофакторов (cofactors) f0 = f(x1,

…, xi-1, 0, xi+1, …, xn), f1 = f(x1,… xi-1, 1, xi+1,…, xn) 
может быть разложен по одной из переменных 
из множества x1, …, xi-1, xi+1, …, xn. Процесс разложения 
кофакторов заканчивается, когда все n
переменных будут использованы для разложения. 
Если не ищутся взаимно инверсные кофакторы, 
то в результате последовательных разложений 

Шеннона 
строятся 
ROBDD-пред-

ставления (Reduced Ordered Binary Decision 
Diagram – сокращенная упорядоченная бинарная 
диаграмма решений). В ROBDD функциональная 
вершина реализует один кофактор, в 
то время как в BDDI взаимно инверсные кофакторы 
представляются парой взаимосвязанных 
вершин. Таким образом, под BDDI будут пониматься 
совместные ROBDD, в которых на каждом 
уровне найдены пары взаимно инверсных 
кофакторов. Алгоритм построения ROBDD 
описан в [2], он был модифицирован для минимизации 
BDDI-представлений. 

Булевы сети – Bool-представления си-

стемы булевых функций. В статье рассматриваются 
булевы сети [2], функциями вершин которых 
могут быть бинарные логические операции 
И (конъюнкция), ИЛИ (дизъюнкция), а 
также унарная операция НЕ (инверсия). Логическая 
минимизация булевых сетей на основе 
разложения Шеннона описана в [2] и заключается 
в поиске такой перестановки участвующих 
в разложении переменных, при которой 
число литералов в булевой сети является 
наименьшим. Литерал – это булева переменная 
либо ее инверсия. Таким образом, после разложения 
Шеннона по очередной переменной минимизация 
булевой сети сводится к следующему: 
ищутся вершины булевой сети, опирающиеся 
на одинаковые подсети, после чего 
проводится редукция (сокращение) сети и 
находятся уравнения, соответствующие редуцированной 
сети. 

Раздельная BDDI и Bool-минимизация за-

ключаются в нахождении своей перестановки 

<

1 ,...,

n
i
i
x
x > переменных разложения для каж-

дой из функций f1(x), …, f m(x), в то время как 
при совместной BDDI- и Bool-минимизации 
используется одна и та же перестановка переменных 
разложения для всех функций системы. 


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

Пусть система F = {f 1(x), …, f m(x)} булевых 

функций задана на общем множестве Z взаимосвязанных 
уравнений (формул) в булевом базисе 
И, ИЛИ, НЕ – это наборы формул разложений 
Шеннона либо наборы формул, соответствующих 
булевым сетям. Каждая формула из 
Z задает одну промежуточную (внутреннюю) 
булеву переменную либо функцию, которая является 
выходной. Обозначим через R(f j) множество 
всех формул, задающих промежуточные 
переменные, связанные с формульным заданием 
только одной функции f j(x), j = 1, …, m, 
R(f j)  Z. Заметим, что собственно формула 
для выходной функции f j в R(f j) не включается. 
Для многоуровневого формульного представления 
системы F = {f 1(x) , …, f m(x)} булевых 
функций через R(F) = R(f 1, …, f m) = 

1

(
)

m

i

i

R f

=

=
обозначим множество внутренних 

формул для всех функций системы. 

Рассмотрим далее понятие связанности 

представлений функций, которую будем понимать 
как общность формул в заданиях функций 
в виде множеств взаимосвязанных алгебраических 
логических уравнений. Прежде всего следует 
отметить, что характеристика связанности 
трактуется как отношение между парой объектов – 
компонент системы, в роли которых выступает 
одна или несколько функций, задаваемых 
уравнениями рассматриваемой системы. 
Для определения количественных оценок связанности 
введем ряд обозначений. Пусть Fg,
Fh – подсистемы системы F: Fg  F, Fh  F. 
Назовем весом связаности подсистем Fg, Fh

число

(
,
)
(
)
(
)

(
(
))
(
(
)) ,

i
g
j
h

g
h
g
h

i
j

f
F
f
F

S F
F
R F
R F

R f
R f




=

=

=


(1)

где через |A| обозначена мощность множества A. 

В целях нормирования количественных 

оценок связанности наряду с весом (1) введем 
понятие меры M(Fg, Fh) связанности подсистем 
Fg , Fh, вычисляемой по формуле

Программные продукты и системы / Software & Systems
36(4), 2023

512

(
,
)
(
,
)
.

max(
(
) ,
(
) )

g
h

g
h

g
h

S F
F
M F
F

R F
R F

=
(2)

Когда каждая из подсистем представляет 

единственную функцию системы F, формулу (2)
можно записать в виде  

(
,
)
(
,
)

max(
(
) ,
(
) )

(
)
(
)
.

max(
(
) ,
(
) )

i
j

i
j

i
j

i
j

i
j

S f
f
M f
f

R f
R f

R f
R f

R f
R f

=
=


=

(3)

Под M( f i,  f j) понимается мера связанности 

многоуровневых представлений пары функций
f i, f j. 

Предлагаемый далее алгоритм выделения 

связанных подсистем основан на последовательном 
пополнении уже выделенной подсистемы 
Fm = {f 1, …, f m}, m  2, новой функцией 
f m+1. Под мерой связанности системы функций 
Fm  f m+1 будем понимать величину 

1
1

1

1
1

(
,...,
)
(
)

(
{
})
.

max(
(
,...,
) ,
(
) )

m
m

m
m

m
m

R f
f
R f

M F
f

R f
f
R f

+

+

+




=
(4)

В дальнейшем, оценивая меру связанности 

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

Величина меры связанности всегда нахо-

дится в пределах отрезка [0,1]: от полного различия 
множеств формул исходного представления 
функций (либо подсистем функций) до 
их полного совпадения. Это свойство меры 
связанности дает возможность определять границы 
выделяемых для совместной минимизации 
подсистем, причем при проведении экспериментальных 
исследований эту меру удобно 
выражать в процентах.

Примем, что рассматриваемая мера связан-

ности обладает уровнем q, если справедливо 
q ≤ M(f i, f j) для связанности пары функций f i, f j

или q ≤ M(F m  {f m+1}) для компонентной связанности 
при пополнении системы новой функцией. 
Далее, когда речь пойдет о связанности 
систем или подсистем функций, будет подразумеваться 
связанность их многоуровневых представлений 
с оценкой по мере связанности последнего 
проведенного пополнения. 

Рассмотрим пример системы булевых функ-

ций, заданной в таблице 1. 

Таблица 1 

Таблица истинности системы полностью 

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

Table 1

Truth table of a system of fully defined 

Boolean functions

x1 x2 x3 x4
f 1 f 2 f 3 f 4

0 0  0  0
0  0  0  1
0  0  1  0
0  0  1  1
0  1  0  0
0  1  0  1
0  1  1  0
0  1  1  1
1  0  0  0
1  0  0  1
1  0  1  0
1  0  1  1
1  1  0  0
1  1  0  1
1  1  1  0
1  1  1  1

0  0  1  1
1  1  0  0
1  0  0  0
1  1  0  0
0  0  1  1
1  1  0  0
0  1  1  1
1  1 1  0
0  0  1  1
1  0  0  0
1  1  0  0
1  1  0  0
0  0  1  1
1  0  1  1
0  0  0  1
1  0  1  0

Для данной системы функций BDDI-

представление состоит из 12 формул:

1

3
4
3 1
f
x x
x s
=

; 
2

3 2
3 3
f
x s
x s
=

; 

3

3 4
3 5
f
x s
x s
=

; 
4

3 4
3
1
f
x s
x s
=

;

1
4
2
4
s
x x
x
=

; 
2
4
1
s
x x
=
; 
3
4 8
4
6
s
x s
x s
=

;
(5)

4
4
4 6
s
x
x s
=

; 
5
4
7
4
2
s
x s
x x
=

;

6
1
2
s
x x
=
; 
7
1
2
s
x x
=
; 
8
1
2
1
2.
s
x x
x x
=


Множество R(f 1, f 2, f 3, f 4) формул, задаю-

щих функции системы F={f 1, f 2, f 3, f 4}, состоит 
из восьми формул, так как первые четыре 
формулы из (5) не включаются в множество 
R(f 1, f 2, f 3, f 4). Отдельные функции системы заданы 
следующими множествами: R(f 1) = {s1}, 
R(f 2) = {s2, s3, s6, s8}, R(f 3) = {s4, s5, s6, s7}, R(f 4) =
= {s1, s4, s6}. Здесь и далее будем задавать множества 
формул, перечисляя только их левые 
части. Подсистема {f 3, f 4} функций имеет вес 
связанности S(f 3, f 4) = 2 (в задании функций 
имеются две общие формулы – s4, s6. По формуле (
3) мера связанности M(f 3, f 4) = 2/4 = 0,5, 
так как |R(f 3)| = 4, |R(f 4)| = 3 и поэтому 
max(|R(f 3)|, |R(f 4)|) = max(4,3) = 4. Легко заметить, 
что пара f 2, f 3 имеет меру связанности, 
равную 1/4. Мера компонентной связанности (4)
подсистемы {f 2, f 3}  f 4 равна 2/7, так как 
R(f 2, f 3) = {s2, s3, s4, s5, s6, s7, s8}, R(f 4) = {s1, s4,
s6}, R(f 2, f 3)  R(f 4) = {s4, s6}, |{s4, s6}| = 2, 
max(|R(f 2, f 3)|, |R(f 4)|) = 7. Если же к подсистеме 
{f 2, f 3, f 4} добавить функцию f 1, то мера ком-

Программные продукты и системы / Software & Systems
36(4), 2023

513

понентной связанности (4) системы {f 2, f 3,
f 4}  f 1 будет равна 1/7, так как подсистема 
{f 2, f 3, f 4} имеет одно общее уравнение s1 с 
функцией f 1. 

Рассмотрим другое множество формул, за-

дающих те же функции: 

1

12
f
t
=
;  

2

1
2
f
t
t
=

; 

3

3
4
f
t
t
=

; 

4

5
6
f
t
t
=

; 1
1 17
t
x t
=
; 
2
1 13
t
x t
=
; 

3
1 7
t
x t
=
; 
4
1 18
t
x t
=
; 5
1 10
t
x t
=
; 

6
1 12
t
x t
=
; 7
8
9
t
t
t
=

; 8
4
2
t
x x
=
; 

9
4
3
t
x x
=
; 10
11
12
t
t
t
=

; 11
4 16
t
x t
=
; 

12
4 17
t
x t
=
; 13
4
15
t
x
t
=

; 14
4 15
t
x t
=
;

15
2
3
t
x x
=
; 16
2
3
t
x x
=
; 17
2
3
t
x x
=
; 

18
14
12.
t
t
t
=


(6)

Как видим, каждая формула в (6) состоит 

только из одного булева оператора и является 
менее сложной (содержащей меньшее число 
логических операторов) по сравнению с формулами (
5), задающими разложения Шеннона. 
Формулы (6) описывают булеву сеть, реализующую 
систему функций из таблицы 1. 

Множества уравнений, задающие отдель-

ные функции системы: R(f 1) = {t12, t17}; R(f 2) = 
= {t1, t2, t13, t15, t17}; R(f 3) = {t3, t4, t7, t8, t9, t12, t14, 
t15, t17, t18}; R(f 4) = {t5, t6, t10, t11, t12, t16, t17}. 

Подсистема {f 3, f 4} функций имеет вес свя-

занности S(f 3, f 4) = 2 (в задании функций имеются 
две общие формулы t12 и t17) и меру связанности 
M(f 3, f 4) = 2/10 = 0,2, так как |R(f 3)| = 10, 
|R(f 4)| = 7 и max(|R(f 3)|, |R(f 4)|) = max(10,7) = 10. 
Примеры показывают, что различные представления (
множества формул) одних и тех же 
функций могут иметь различные меры связанности. 


Выделение подсистем с заданной 

мерой связанности

Предлагаемый эвристический алгоритм яв-

ляется модификацией предложенного в [13] алгоритма 
и состоит в последовательном формировании (
на каждой итерации i) по текущей 
(остаточной) системе функций очередной подсистемы 
Pi функций (подсистема Pi характеризуется 
мерой компонентной связанности, не 
меньшей q). На первой итерации (i = 1) текущую 
систему функций образуют функции исходной 
системы. 

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

шаги 1–3.

Шаг 1. Рассмотреть 

2
(
1) / 2
m
C
m m
=
−
неупо-

рядоченных пар функций {f i, f j}, i, j = 1, ..., m, 

i j, текущей системы и найти такую пару 
функций L, которая имеет максимальное значение 
меры связанности, вычисляемое по формуле (
3) и не меньшее параметра q. Если таких 
пар функций несколько, то выбирается первая 
из них. Если указанной пары функций нет, то 
переход на шаг 4. 

Шаг 2. Составить из функций найденной на 

первом шаге пары L формируемую подсистему 
Pi, исключив выбранную пару функций L из текущей 
системы, и добавлять в формируемую 
подсистему поочередно те функции f r, которые 
находятся с помощью следующей эвристики: 
из множества функций текущей системы 
выбирается та функция f r, которая обеспечивает 
наибольшее возможное значение 
меры компонентной связанности (4) для подсистемы 
Pi  {f r}. Если таких функций несколько, 
то выбирается и добавляется в формируемую 
подсистему Pi первая из них.

Шаг 3. Если нет ни одной такой функции f r, 

что подсистема P i  {f r} имеет меру компонентной 
связанности, не меньшую q, то закончить 
формирование подсистемы P i и объявить 
не входящие в нее функции текущей подсистемой. 
Переход на шаг 1 для формирования подсистемы 
на итерации i + 1. 

Шаг 4. Закончить формирование подси-

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

Достоинствами данного алгоритма явля-

ются его высокое быстродействие и возможность 
обобщения на формулы AIG, MIG, XMG, 
XAIG, а недостатком – зависимость от последовательности 
формирования результирующих 
выделенных подсистем. Чтобы подсчитать 
меру связанности результирующей выделенной 
подсистемы, надо знать последнюю 
добавляемую в подсистему функцию и, очевидно, 
ту подсистему, в которую она добавляется. 


Приведем пример работы алгоритма на 

формулах (6) при значении допустимого уровня 
связанности q = 0,2 (20 %). 

Шаг 1. Рассмотрим все неупорядоченные па-

ры функций из формул (6) исходной системы и 
найдем для каждой из пар меру связанности (3): 
M(f 1, f 2) = 1/5; M(f 1, f 3) = 2/10; M(f 1, f 4) = 
= 2/7; M(f 2, f 3) = 2/10; M(f 2, f 4) = 1/7; M(f 3, f 4) =
= 2/10. 

Программные продукты и системы / Software & Systems
36(4), 2023

514

Исходя из полученных оценок мер связанно-

сти пар функций при уровне связанности q = 0,2, 
результатом выполнения шага 1 является пара 
{f 1, f 4}, имеющая наибольшую меру связанности 
M(f 1, f 4) = 2/7. 

Шаг 2. К подмножеству {f 1, f 4} функций 

будем добавлять поочередно функции f 2, f 3 и 
находить меры компонентной связанности: 
M({f 1, f 4}  {f 2}) = 1/7, M({f 1, f 4}  {f 3}) = 2/10. 
Для подсистемы ({f 1, f 4}, f 2): R(f 1, f 4) = {t5, t6,
t10, t11, t12, t16, t17}, R(f 2) = {t1, t2, t13, t15, t17}, R(f 1,
f 4)  R(f 2) = {t17}, |{t17}| = 1, max(|R(f 1, f 4)|,
|R(f 2)|) = max(7,5) = 7, откуда M({f 1, f 4}  {f 2}) = 
= 1/7, что меньше 0,2. 

Шаг 3. Для подсистемы ({f 1, f 4}, f 3) значе-

ние M({f 1, f 4}  {f 3}) = 0,2, поэтому на шаге 3 
выделенной подсистемой объявляется {f 1, f 4,
f 3}. Добавить к этой подсистеме функцию f 2 не 
удается, так как полученное значение меры 
компонентной связанности будет меньше 0,2. 
Текущей подсистемой объявляется {f 2}, и выполняется 
переход на шаг 1. 

Шаг 4. В текущей подсистеме остается одна 

функция, поэтому алгоритм прекращает работу. 
Результатом являются одна выделенная 
подсистема {f 1, f 4, f 3} и остаток – подсистема {
f 2}.

Если провести синтез схемы непосред-

ственно по формулам (6) (Bool-представлению), 
то будет получена схема с площадью 
4 336 условных единиц, состоящая из 12 элементов, 
задержка схемы составит 2,78 нс. Если 
же провести совместную минимизацию в 
классе булевых сетей подсистемы {f 1, f 4, f 3} и 
совместную минимизацию подсистемы {f 2} 

(для этой подсистемы совместная минимизация 
вырождается в раздельную одной функции), 
то в результате синтеза получим схему 
(см. рисунок) с площадью 4 262 условные единицы, 
состоящую из 12 элементов, задержка 
схемы составит 3,21 нс. Функции логических 
элементов схемы и их площади приведены в 
таблице 2. Таким образом, параметры схемы изменились – 
площадь схемы уменьшилась, задержка 
увеличилась.

Таблица 2

Функции и площади элементов КМОП

логической схемы

Table 2

Functions and areas of CMOS 

logic circuit elements

Элемент
Функция
Площадь

N
y
A
=
223

NOA
(
)
y
AB
C
=

363

NAO3
(
)
y
A
B
C D
=


491

XOR2
y
A
B
=

692

NOAA
y
AB
CD
=

485

NOA3
(
)
y
ABC
D
=

530

Если же реализовать схему по уравнениям (5) 

(BDDI-представлению), то получим схему с площадью 
4 659 условных единиц, состоящую из 
14 элементов, задержка схемы составит 1,72 нс.
Данный пример показывает, что различные 
способы минимизации многоуровневых представлений 
позволяют получать схемы различной 
площади и задержки. Проведенные про-

Логическая схема в базисе элементов КМОП

Logic circuit in CMOS element basis