TTL и CMOS логика Цифровая схемотехника на логических микросхемах. Счетчики, сдвиговые регистры, простая логика... |
23.09.2017, 17:04
|
|
Частый гость
Регистрация: 20.09.2014
Сообщений: 24
Сказал спасибо: 0
Сказали Спасибо 0 раз(а) в 0 сообщении(ях)
|
Примеры минимизации булевой функции с большим числом переменных
Доброго времени суток!
Подскажите пожалуйста ресурс с примерами минимизации булевих функций на 8, 9, 10 и более переменных. Необходимо исходное выражение булевой функции и её минимальная форма. Процедура минимизации не обязательна.
|
|
|
|
24.09.2017, 03:15
|
|
Модератор
Регистрация: 04.08.2010
Адрес: Москва СЗАО
Сообщений: 11,257
Сказал спасибо: 11,170
Сказали Спасибо 3,859 раз(а) в 2,929 сообщении(ях)
|
Re: Примеры минимизации булевой функции с большим числом переменных
А поиск? Есть даже онлайн ресурсы. "минимизация булевых функций онлайн"
__________________
rtfm forever должно быть основой для каждого. Альтернатива грустна, поскольку метод слепого щенка успешно работает при весьма малом числе вариантов…
Последний раз редактировалось mike-y-k; 24.09.2017 в 16:44.
|
|
|
|
24.09.2017, 12:20
|
|
Частый гость
Регистрация: 20.09.2014
Сообщений: 24
Сказал спасибо: 0
Сказали Спасибо 0 раз(а) в 0 сообщении(ях)
|
Re: Примеры минимизации булевой функции с большим числом переменных
От 9 переменных поиск результатов не даёт. На 8 переменных есть примеры функций для минимизации, очевидно штучно подобраны, для карти Карно.
Минимизация функций онлайн только до 6 переменных, включительно.
|
|
|
|
26.09.2017, 01:38
|
|
Частый гость
Регистрация: 20.09.2014
Сообщений: 24
Сказал спасибо: 0
Сказали Спасибо 0 раз(а) в 0 сообщении(ях)
|
Re: Примеры минимизации булевой функции с большим числом переменных
По адресу рассмотрена минимизация 8-переменной булевой функции картой Карно. Представлена минимальная форма заданной функции (приложил). В этой минимальной форме в 1-м и 2-м конъюктермах можно ещё провести элементарное поглощение седьмой переменной, 2-й конъюктерм станет меньший на одну переменную. Выходит, что правила контура метода Карно для 8-переменной функции не до конца проводят минимизацию?
|
|
|
|
26.09.2017, 05:14
|
|
Модератор
Регистрация: 04.08.2010
Адрес: Москва СЗАО
Сообщений: 11,257
Сказал спасибо: 11,170
Сказали Спасибо 3,859 раз(а) в 2,929 сообщении(ях)
|
Re: Примеры минимизации булевой функции с большим числом переменных
Mishel 825, тут уже от реализации алгоритма сильно зависит. Встречаемые варианты работали до 6 переменных. Дальше был тихий ужас.
Алгоритмы на методах Куайна и Куайна-МакКласки тут эффективнее.
И алогоритм Espresso в его реализациях кушает до 40 переменных. Кстати вроде на его основе работают оптимизаторы и валидаторы для программируемой логики. И оптимизаторы в системах проектирования микросхем. Хотя чаще там сразу несколько методов задействованы с выбором оптимума из результатов.
PS По ссылкам на статьи внизу есть ссылки на реализации в разных вариантах. Можно их проверить и выбрать оптимальный(е)/лучший(е)/…
PPS Тут сильная зависимость от Ваших задач и критериев оценки результата. В такой ситуации только показать векторы движения получится…
__________________
rtfm forever должно быть основой для каждого. Альтернатива грустна, поскольку метод слепого щенка успешно работает при весьма малом числе вариантов…
Последний раз редактировалось mike-y-k; 26.09.2017 в 17:40.
|
|
|
|
27.09.2017, 00:45
|
|
Прописка
Регистрация: 17.03.2015
Сообщений: 298
Сказал спасибо: 0
Сказали Спасибо 220 раз(а) в 126 сообщении(ях)
|
Re: Примеры минимизации булевой функции с большим числом переменных
Сообщение от Mishel 825
|
Необходимо исходное выражение булевой функции и её минимальная форма.
|
Делал как-то для себя по Квайн+Петрик (см. екзешник во вложении).
Программу ограничил 8 переменными, хотя, как я помню, реализация позволяет и большее число переменных, но сейчас исходники искать надо, да и заново все вспоминать
Програмка, конечно сыровата - нет прогресс-бара (для малого количества переменных, было не нужно), очистка результатов отдельно не выведена (делается через смену количества переменных), может быть еще какие неудобства, сейчас уже и не вспомню.
Главное считает правильно, а когда получил результат, то и забил на всякие рюшечки.
Попробуйте, может пригодиться.
Кстати, делал по книжице: "Шевелев Ю.П. Дискретная математика. Ч.1. Теория множеств. Булева алгебра (2003)".
Если будете тестировать, то отпишитесь - чисто для статистики - не ошибся ли где в реализации алгоритма.
|
|
|
Сказали "Спасибо" ProtAS-13
|
|
|
27.09.2017, 01:23
|
|
Модератор
Регистрация: 04.08.2010
Адрес: Москва СЗАО
Сообщений: 11,257
Сказал спасибо: 11,170
Сказали Спасибо 3,859 раз(а) в 2,929 сообщении(ях)
|
Re: Примеры минимизации булевой функции с большим числом переменных
В процессе воспоминаний понял, что надо бы ещё сайт MIT прошерстить на предмет поиска решений, и посмотреть поглубже в материалах на сайте IBM.
__________________
rtfm forever должно быть основой для каждого. Альтернатива грустна, поскольку метод слепого щенка успешно работает при весьма малом числе вариантов…
|
|
|
|
27.09.2017, 03:21
|
|
Частый гость
Регистрация: 20.09.2014
Сообщений: 24
Сказал спасибо: 0
Сказали Спасибо 0 раз(а) в 0 сообщении(ях)
|
Re: Примеры минимизации булевой функции с большим числом переменных
Спасибо поддерживающим тему.
mike-y-k, хорошая информация, ищу примеры для тестирования.
ProtAS-13, протестировал на 4, 5, 6 и 8 переменных. Програма выдала правильный результат. Приложил функции для тестирования и результаты тестирования. Не везде отображается инверсия, что затрудняет ориентацию.
|
|
|
|
27.09.2017, 19:48
|
|
Гражданин KAZUS.RU
Регистрация: 02.06.2003
Адрес: Челябинск
Сообщений: 545
Сказал спасибо: 10
Сказали Спасибо 341 раз(а) в 202 сообщении(ях)
|
Re: Примеры минимизации булевой функции с большим числом переменных
Сообщение от Mishel 825
|
Доброго времени суток!
Подскажите пожалуйста ресурс с примерами минимизации булевих функций на 8, 9, 10 и более переменных. Необходимо исходное выражение булевой функции и её минимальная форма. Процедура минимизации не обязательна.
|
Цель какая?
|
|
|
|
27.09.2017, 20:03
|
|
Модератор
Регистрация: 04.08.2010
Адрес: Москва СЗАО
Сообщений: 11,257
Сказал спасибо: 11,170
Сказали Спасибо 3,859 раз(а) в 2,929 сообщении(ях)
|
Re: Примеры минимизации булевой функции с большим числом переменных
Bill, а цель из названия и первого топика? Очень востребованно в семействе разнообразных программируемых логических… Оптимизация, однако. Руками написанное/нарисованное не всегда минимально получается и не лезет в имеющееся железо. Собственные средства в пакетах разработки тоже не всегда устраивают или отсутствуют из-за стоимости.
__________________
rtfm forever должно быть основой для каждого. Альтернатива грустна, поскольку метод слепого щенка успешно работает при весьма малом числе вариантов…
|
|
|
|
Ваши права в разделе
|
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения
HTML код Выкл.
|
|
|
Тема |
Автор |
Раздел |
Ответов |
Последнее сообщение |
Ускорить компьютер
|
7Fantomas7 |
Ремонт оргтехники |
111 |
08.08.2018 05:27 |
Часовой пояс GMT +4, время: 19:38.
|
|