ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничный koi-8r
22 сообщений из 47, страница 2 из 2
  2  все
Тяпничный koi-8r
    #38848748
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
maytonВобщем несколько мыслей по сабж.

Нужен генератор МДНФ (минимальной дизьюнктивной формы). А зачем???
Долго думал, так и не понял что за задачу ты решаешь.

Единственная, на мой взгляд, область в которой подобное может потребоваться это создание микросхем.

maytonИсходными данными при этом являются:

- целевой ЯП в котором будет минимизированная функция (C/C++/Java/C#)Но если ты действительно увлекся железом, то за ЯП надо брать HDL и/или его диалекты с кузенами (VHDL, AHDL, Verilog и тд).
А из практических реализаций можешь посмотреть на продукты Altera. Последние годы они дают свой Quartus за бесплатно (но с регистрацией и ограничениями по эмулятору). Вроде есть и другие подобные продукты (и даже совсем бесплатные), но я с ними не работал вообще и не помню сейчас ни одного названия. Поищи в линуксовых репозиториях по слову vhdl и получишь с дюжину разных вариантов.

И кстати, в Quartus упрощатель таблиц работает как раз на Quine-McCluskey...
...
Рейтинг: 0 / 0
05.01.2015, 23:28
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38849048
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Но если ты действительно увлекся железом
Увы нет.

Но за совет спасибо.
...
Рейтинг: 0 / 0
06.01.2015, 12:38
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38849800
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Здарова челы. Вобщем отойдя от бутербродов и икрой и паштетов и коньяка (ох уж эти
праздники) я вконце-то концов подошёл к тестам. К разработке через TDD мать ево так.

Значит что мне нужно? Тестовые наборы для Квайна. Среди таковых
будут.

1) Тривиальные тесты. Когда Y{i}==X{j}. Один из аргументов полностью повторяет функцию.
Прочие аргументы - сокращаются.

2) Тождесвенные. Когда Y{i}=C{i} где С - это константы. Формула не зависит от аргументов вообще.

3) Тест классического дешифратора 7(8) сегментного цифрового индикатора (типа электронных часов).
На вход поступает 4 сигнала в BCD/Bin коде а на выходе мы имеем 7 сигналов для свечения сегментов цифр.
Данную задачу я решал в техникуме в рамках толи курсовой толи лабы при проектировании какой-то железяки
поэтому остаточные знания остались.

4) Тест справочника мобильных операторов. На вход поступают 2-3 BCD цифры (из телефонного номера)
на выходе - множество предикатов принадлежности телефонного номера к компании/бренду. Из особенностей
данного теста - взаимоисключаемость. Номер не может принадлежать двум операторам следовательно
на всём множестве Y{i} только одно даёт истину для одного набора аргументов. Это легко проверяется.

5) Прочие нагрузочные тесты. Сюда-же можно включить koi8r-unicode decoder. Как бенчмарк.
Его будем тестить только таблично.
...
Рейтинг: 0 / 0
07.01.2015, 17:57
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38849807
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Несколько мыслей по поводу Карно/Вейча.

Начав рисовать вручную тест я кое-что забыл. В некоторых наборах исходных данных
существуют НЕОПРЕДЕЛЁННЫЕ/ЗАПРЕЩЕННЫЕ комбинации (НК).

Смысл и семантика НК полностью возлагается на инженера которые проектировал
устройство. В моём конкретном случае - это цифровые сигналы от 0xA до 0xF
которые подаются на вход дешифратору. Поскольку для них нет десятичной цифры
то и вопрос отображения стоит по другому. Либо мы отображаем нули. Нет свечения.
Либо все единицы. (Горит восьмёрка). Либо проектируем КАК НАМ УДОБНО
с плавающим значением Y{i} выбирая то состояние которое лучше склеится
или поглотится при оптимизации. При этом исходим из предположения
что НК никогда не придёт на вход и следовательно состояние функции
после оптимизации для НК нам безразлично.

Я и выбираю последний вариант. Это очень удобно для Карно/Вейча.
На картинке я отмечаю НК крестиками и склеиваю их с ближайшими
единичками максимально-возможным покрытием.

Для Квайна этот аспект игнорируется. Как мне быть с квайном для НК - пока не знаю.

(В скобках замечу что я использую Карно только для самоконтроля и написания теста).

В реализации его не будет. Будет только Квайн.

На картинке внизу две последние формулы отображают мои две попытки написать
формулу методом Карно.

Карно-1 - это функция Y1 для варинта когда запрещённые комбинации я отображал в
нули.

Карно-2 - это та-же функция Y1 для варианта когда НК я заменил на крестики
и соптимизировал лучше.
...
Рейтинг: 0 / 0
07.01.2015, 18:20
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851467
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Несколько мыслей.

Мне понадобился Код Грея. Для рисования толстых карт (512 на 512) элементов.
На бумажке рисовать не буду но пространственная когерентность элементов
открывает некоторые графические возможности которые мне интересны.

Код: plaintext
1.
2.
3.
4.
unsigned int grayencode(unsigned int g) 
{
    return g ^ (g >> 1);
}



Например B&W растровое изображение может быть (теоретически) представлено
композицией булевой функцией множества аргументов. При этом на компактность
и лаконичность формулы влияют прямоугольные группы пикселов кратные 2^N.

Речь не идёт о компрессии. Здесь скорее всего будет фейл но сам по себе
побочный эффект весьма забавен.
...
Рейтинг: 0 / 0
11.01.2015, 01:39
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851503
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНапример B&W растровое изображение может быть (теоретически) представлено
композицией булевой функцией множества аргументов. При этом на компактность
и лаконичность формулы влияют прямоугольные группы пикселов кратные 2^N.

Речь не идёт о компрессии. Здесь скорее всего будет фейл но сам по себе
побочный эффект весьма забавен.
Из практических применений B&W растра видится только хранение сканов документов, с достаточным разрешением чтобы распечатать можно было. Это примерно 200-300 dpi разрешение. Т.е. лист A4 от 1650*2300 точек.

Архиваторы жмут такие BMP очень хорошо (более чем в 10 раз), думаю за счет большого количества одноцветных последовательностей точек.

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

PS Вписывание размеров в 2^N необязательно, достаточно ближайшее большее, а то что выходит за границы считать любым состоянием.
...
Рейтинг: 0 / 0
11.01.2015, 08:27
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851652
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
У меня не стоит задачи делать архивацию. Это скорее творческий эксперимент для
проверки минимизации для больших объёмов.

А для уменьшения размера bi-level лучше всего подходит JBIG.
...
Рейтинг: 0 / 0
11.01.2015, 14:42
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851764
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Продолжаю поток сознания.

Проблема выколотой точки. В некоторых случаях область непрерывных единичек
распознаётся как простой импликант (2-3 аргумента) за исключением 1-2 "выколотых" точек.

См. скрин ниже.

Приведу пример. Квадратная область единичек удоволетворяет формуле



за исключением выколотой точки



Интуитивное (без применения полного метода Карно) я создаю следующую формулу.



Вобщем я утверждаю что она удовлетворяет множеству единичек (на скрине).

Меня привлекает этот подход тем что фильтруя единичные одинокие нулевые точки
я СУЩЕСТВЕННО сокращаю импликант.

Фильтрация таких точек с точки зрения растровых фильтров - тривиальна.

Равно как и их детектирование.
...
Рейтинг: 0 / 0
11.01.2015, 19:52
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851766
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
...
Рейтинг: 0 / 0
11.01.2015, 19:56
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851778
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Далее я воспроизведу flow вычислений согласно методу Карно.
Следующие области (импликанты)















Объединяются в формулу (2):
...
Рейтинг: 0 / 0
11.01.2015, 20:19
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851782
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Чорт. Латекс глюканул. Ладно запишу так.

Код: plaintext
1.
y = x1x5!x6 + x1x5x7 + x1x5x6!x7!x8 + x1!x2x5 + x1x3x5 + x1x2!x3!x4x5



Попытка вынести за скобки x1x5. Получаем формулу (2):

Код: plaintext
1.
y = x1x5( !x6 + x7 + x6!x7!x8 + !x2 + x3 + x2!x3x4 )



Согласно формуле (1) было:

Код: plaintext
1.
y = x1x5!(x1x2!x3x4x5x6!x7x8)



Явно было меньше операций.
...
Рейтинг: 0 / 0
11.01.2015, 20:39
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851790
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton, ты маньяк

Зачем сам себе грузишь мозг теорией микросхемотехники? В программировании она малопригодна. Это более низкий уровень.

Разве что по итогу изышлений возмешь горсть микросхем и паяльник. Оно тебе надо?
...
Рейтинг: 0 / 0
11.01.2015, 21:07
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851796
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Еще пару дней погружу и перестану.
...
Рейтинг: 0 / 0
11.01.2015, 21:16
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851797
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЕще пару дней погружу и перестану.
И правильно. Я бы до сих пор паял (один полезный девайс спроектировал и спаял), образование паяльное, но с паяльником не дружу, руки не оттуда растут, потому и подался в программисты.
...
Рейтинг: 0 / 0
11.01.2015, 21:21
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851806
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я очень сложный чел. И у меня (на самом деле) в любой задаче стоит гланая постановка (и около
десятка второстепенных). В минимизации булевых функций таковые есть:
- обфускация данных/стеганография
- оптимизация производительности
- овладевание ручными методиками минимизации. Глубокий анализ. Обобщение.
- код Грея
- Ассемблер x86
- Байткод Java
- Персептрон
- Инженерная графика/факсимильные изображения.

Поэтому блуждание и рыскание в стороны - вокруг 1 технологии - это одна из форм моего досуга.
Сочетая приятное тык скыть с полезным.

А в радио-технике у меня еще более огроменный список дел. Я вот галогеновый фонарь
с датчиком уже месяц не могу установить. Камеру-регистратор чинить надо. Эпоксидку
купить. Свой старый комп на DDR2 надо поднять и поставить Пингвина. Фотик Кэнон перепрошить.
Вобщем как-то вот в таком аспекте.

А минимизация это просто так. Чтоб было под каким флагом ходить.
...
Рейтинг: 0 / 0
11.01.2015, 21:41
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851810
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЯ вот галогеновый фонарь
с датчиком уже месяц не могу установить.
И зря. Это важнее. Надо отвлекаться от теории на приземленные вещи. Именно это важно. Всем нужен конечный результат. Теория никому не нужна. На ней выезжают разве что ученые с мировым именем, но их единицы и стремится попасть в их круг бесполезно.
...
Рейтинг: 0 / 0
11.01.2015, 21:57
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851853
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
QMC Logic Minimizer работающий по методу Квайна повис на анализе функции с 18 аргументами и
262144 наборами значений. В качестве исходных данных была взята bi-level картинка с изображением
фотографии Че-Гевары. Разрешение 512 на 512. По вертикали и по горизонтали по 9 булевых аргументов
в порядке кода Грея.

Ответа от него я не дождался. Но для эксперимента были заготовлены копии этой картинки в разрешения
16x16,32x32,64x64,128x128...e.t.c.

Для варианта 16x16 минимизированная функция выглядит так:

Код: plaintext
1.
2.
3.
4.
5.
f1  =  A' B' C' D' F' H  +  A' B' C' D' E G H'  +  A' B' C' E F' H  +  A' B' D F' G'  +  C D' E' F  +  A' C D' F H  +  
A' B C F  +  B E' G H'  +  A B C' D' F  +  A C E' F  +  A D E' F H  +  B' C' D' E' F' G'  +  A' C D' G' H'  +  
A' D E' F' G'  +  A' B D E' G'  +  A' E F' G' H'  +  A' B D' F H  +  C' D' E F' G' H'  +  A B C' F H  +  
A C D F G' H'  +  B C D F H  +  C D' E' G' H'  +  B' D E F' G' H'  +  A B' C' D G' H'  +  A' C E' F' G'  +  
A' B D' F G'  +  A B E' F


Поясню по формуле. Аргументы QMC маркирует буквами A...Z. Штрих - операция инверсии.
Символ плюс - оператор логической дизъюнкции.

В данном конкретном случае A..D - биты координаты y, E..H - биты координаты x.

Чуть позже попробую с разрешениями повыше.

Ссылки по теме:
https://sourceforge.net/projects/qmclm/
https://www.google.com/search?q=che guevara ext:png
...
Рейтинг: 0 / 0
12.01.2015, 01:26
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38851885
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
mayton,

Мне становится все любопытнее и любопытнее. ЗАЧЕМ???
...
Рейтинг: 0 / 0
12.01.2015, 07:51
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38852099
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ты опоздал с этим вопросом лет на восемь. Лучше спроси зачем мы модерируем этот форум?
Have fun? Или просто spend time? Или всё всместе?
...
Рейтинг: 0 / 0
12.01.2015, 12:08
| Ответить | Цитировать | Написать  
Тяпничный koi-8r
    #38906547
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly Moskovskymayton,

Таблица будет на порядки быстрее работать чем выражения.
Про читаемость кода я вообще молчу.

Тогда в чем смысл?

Обфускация алгоритма. В IOCCC можно учавствовать :)
Было интересно, но в принципе , учитывая что все кодовые страницы объединяет весовой принцип, понятно что принципиально всё это возможно было сделать.
...
Рейтинг: 0 / 0
17.03.2015, 04:56
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Тяпничный koi-8r
    #39245059
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Up! Не ждали!

Пора вернуться к Че-Геваре.

Долго глядел на этот блок. Думал о расчетах булевых выражений на стеке. Не хватает сноровки...

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
  mainLogicType f16 =  A & NB & D & NE & NF & NH |  
             A & D & NE & F & NG & H |  
             A & NB & C & ND & NE & NF & H |  
             A & NB & C & ND & F & NH |  
             A & C & ND & E & NH |  
             A & B & ND & NF & G & NH |  
             A & B & ND & NE & F & H |  
             A & B & ND & E & NH |  
             A & B & D & NE & NF & H |  
             A & B & E & G & NH |  
             A & NB & D & E & NF & H |  
             A & NB & NC & D & E & F & G |  
             A & NB & C & D & G & H |  
             A & D & NE & NF & NG & NH |  
             A & D & E & NF & NG & H |  
             A & B & D & E & F & NG |  
             A & C & D & E & NG & H ;



Думаю в стековой машине код существенно станет короче.
...
Рейтинг: 0 / 0
27.05.2016, 16:02
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Тяпничный koi-8r
    #39578081
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Апну тему.

Минимизация снова востребована. Но в этот раз условия немного
другие.

Мне надо минимизировать просто размер исходника. Сейчас это выглядит в XML/DSL
примерно так (я скипаю XML-теговую разметку и оставляю суть):

Код: xml
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
rule R1 & R2 &R3 .... RN {
  action1();
  action2();
}

rule ...... {
  action2();
  action3();
}

..



Где R1...RN - некие бизнес-предикаты которые определяют свойства биржевого месседжа.
Логика трансформирует эти рулы в исполняемый код и на ходу компилит в бинарь.
Секций rule - порядка 20 штук. Предикатов среднем от 1 до 8. Есть не только коньюнкции.

У этой модели есть некое хранимое состояние которое появляется в action. Но это нам
не особо важно.

Я по прежнему не автоматизировал расчет методом Квайна-МакКласски. Каюсь. Надо возобновить.
...
Рейтинг: 0 / 0
29.12.2017, 21:19
| Ответить | Цитировать | Написать  
22 сообщений из 47, страница 2 из 2
  2  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничный koi-8r
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]