Search academic texts

Information × Registration Number 0424U000180, Candidate dissertation Status Кандидат технічних наук Date 14-06-2024 popup.evolution . Title Development and research of optimal algorithms for minimizing Boolean functions in an arbitrary logical basis for the design of digital combinational devices. Author Vadym V. Minziuk, popup.head Bohdan Y. Rytsar popup.opponent Valerii V. Kozlovskyi popup.opponent Volodymyr H. Saiko Description Мінзюк В. В. Розроблення та дослідження оптимальних алгоритмів мінімізації булових функцій у довільному логіковому базисі для проектування цифрових комбінаційних пристроїв. — Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.12.13 – «Радіотехнічні пристрої та засоби телекомунікацій» (172 – Телекомунікації та радіотехніка). — Національний університет «Львівська політехніка» МОН України, Львів, 2024. У дисертації розв’язано актуальне науково-практичне завдання, яке полягає в удосконаленні та розробленні алгоритмів та методів мінімізації булових функцій для проектування цифрових комбінаційних схем радіотехнічних пристроїв та засобів телекомунікацій. Запропоновано числове подання кон'юнктермів довільного рангу у вигляді пари чисел: двійкового зображення та двійкової маски літералів. Двійкове зображення отримуємо шляхом заміни символів поглинання на нулі в псевдотрійковому зображенні. Щоб отримати маску літералів, спочатку замінюємо в трійковому зображенні нулі одиницями, а потім символи поглинання нулями. Оскільки склеювання можливі лише між кон'юнктермами з однаковою маскою літералів, об'єднуємо такі кон'юнктерми у множини. Тепер можна позначати кожен кон'юнктерм лише одним числом, а маску літералів вказати єдину для всієї множини. Це дає змогу використати в алгоритмах мінімізації булових функцій двійкові операції замість операцій над символами. Такий підхід полегшує комп'ютерну реалізацію методів мінімізації. Розвинуто метод розчеплення кон'юнктермів. Запропоновано модифікацію процедури розчеплення кон'юнктермів на основі числового подання, що дозволяє зменшити витрати обчислювальних ресурсів, а використання додатково шістнадцяткової системи числення дає змогу розширити коло завдань, які можна розв’язати без застосування комп’ютера. Розвинуто метод порозрядного вирощування простих кон'юнктермів. Використана розроблене числове подання замість псевдотрійкового, що дає змогу оперувати числами замість символів у підмножинах кон'юнктермів з однаковою маскою літералів. Уведено поняття коду помітки множини кон'юнктермів, для усічення трійкового дерева вирощування простих кон'юнктермів. Уведено процедуру виявлення підмножини, елементи якої склеюються в один кон'юнктерм, шляхом підрахунку кількості елементів одразу на етапі сортування за заданим бітом. Розширено сферу застосування методу для недовизначених функцій. Запропоновані зміни дають змогу розширити коло розв'язуваних завдань за рахунок зменшення обчислювальних витрат та розширення сфери застосування методу. Удосконалено метод мінімаксного покриття в теоретико-множинній формі. Запропоновано впорядковувати символьні диз’юнктерми щодо наростання їх потужностей, тобто починаючи з мінімальної. Це прискорює процедуру спрощення сформованої множини за рахунок скорочення шляху пошуку диз’юнктермів, що спрощуються. Запропоновано процедуру ланцюгового покриття таблиці простих кон’юнктермів, яка враховує взаємне розташування кон’юнктермів у двійковому просторі, що дає змогу спростити циклічну частину таблиці простих кон’юнктермів. Це призводить до зменшення витрат машинних ресурсів. Для зниження обчислювальної складності завдання можна розрахувати коефіцієнт складності в околі розгалуження ланцюгів та прийняти рішення про розрив ланцюга у цьому місці. Процедура ланцюгового покриття множини простих кон’юнктермів дає змогу розбивати завдання покриття на кілька обчислювальних потоків. Запропонований підхід є евристичним. Удосконалено метод побітового сортування множини цілих чисел, яка не містить тавтології. У процесі розбиття за заданим бітом з номером n виконують підрахунок елементів підмножини, що дає змогу виявити склеювання отриманої підмножини в кон'юнктерм і тоді замінити процедуру сортування по інших бітах простим перерахунком від 0 до (2^n-1). Крім того, оскільки певні методи мінімізації потребують попереднього сортування множини вихідних кон’юнктермів, запропонована модифікація дає змогу отримати частину імплікантів вже на етапі сортування. Уперше запропоновано метод мінімізації булових функцій побітовим розбиттям множини кон’юнктермів на основі розробленої модифікації побітового сортування зі склеюванням, що дає змогу знаходити прості кон’юнктерми низького рангу без проміжних склеювань. Цей метод позбавлений тавтології. Для прикладної задачі виконано синтез перетворювача кодів запропонованими у роботі методами, серед яких метод мінімізації булових функцій побітовим розбиттям зі склеюванням показав найкращий результат. Ключові слова: кон’юнктерм, мінімізація булових функцій, пошук простих кон’юнктермів, покриття таблиці простих кон’юнктермів, проектування цифрових комбінаційних схем. Registration Date 2024-07-03 popup.nrat_date 2024-07-03 Close