- PVSM.RU - https://www.pvsm.ru -
В очередной раз, при обдумывании самоделки на Atmega, встал вопрос проектирования соединений. В моем случае 12 внешних коннекторов и 21 связь. Расположение, соединение, пересечения, программирование, ошибки, ошибки, ошибки.
При кажущейся простоте задачи поломать
И… лень взяла свое.
Обычный алгоритм в таком случае:
А что если последовательность пинов в коннекторах уже жестко заданы?
Как например у драйвера L298N. Пересечения проводов или дорожек сильно усложнят проектирование, сборку и эксплуатацию.
Попробуем решить задачу с помощью генетического алгоритма. И для начала определимся с моделью.
Получается ген длиной 21 хромосом, которые отображают пины микроконтроллера, а точнее их соединения с коннекторами.
VCC и GND пины коннекторов игнорируем, так как шины мы можем вынести за коннекторы.
Каждая ячейка может иметь значение от 1 до 32 (количество лап у микросхемы). Значения в гене не могут повторяться.
Не допускается пересечений проводников (соединения делаются последовательно, если следующий пин занят — проскакиваем далее)
Количество вариантов соединений:
40 564 819 207 303 340 847 894 502 572 032.
Правда это количество рассчитано для сочетаний с повторениями, но такой способ позволяет быстро оценить сложность.
Для уменьшения пространства поиска используем функции пина коннектора (ADC, INT, PWM, PCINT). Например, если пин может быть только ADC, то вести к нему линию PWM или дискретного входа бессмысленно.
Данный фильтр уменьшает количество вариантов до 8 748 869 014 201 881 088. Разница ощутима. Но миллиарды миллиардов вариантов это тоже много.
Так же ранее использовались «ручные» эмпирические правила:
Но волшебный Collections.shuffle задающий последовательность коннекторов для обработки, решает эту задачу успешно на автомате.
Запускаем алгоритм и получаем решение для Atmega328p TQFP32. У меня на бюджетном ноутбуке находит менее чем за минуту.
1 SONAR1.Echo
2 SONAR1.Trig
9 DRIVE.ENB
10 DRIVE.IN4
11 DRIVE.IN3
12 DRIVE.IN2
13 DRIVE.IN1
14 DRIVE.ENA
15 ENCODER_L.IN
16 VAC_CLEAN.EN
17 CPU.EN
22 PWR.LVL
23 PWR.CUR
24 SENS_R.IN
25 SENS_L.IN
26 ENCODER_R.IN
27 I2C.SDA
28 I2C.SCL
30 UART.RXD
31 UART.TXD
32 BROOM.EN
Алгоритм находит решение за пару тысяч эпох. Иногда не находит и за миллион. В таком случаем просто надо перезапустить программу, потому что инициализация происходит случайно.
Без фильтра по функциям пинов алгоритм так же находит решение. Правда за 74 минуты и 13 перезапусков алгоритма по миллиону эпох на каждый. Перед каждым запуском делаем shuffle последовательности соединений.
Остается только соединить проводами макетку или нарисовать дорожки на плате с микроконтроллером.
Чтобы описать всё, надо будет написать не одну статью. Я постарался комментировать непонятные и самые интересные моменты в java-коде.
Желающие углубиться в тему могут заглянуть в git-проекта [2].
Автор: Максим Завало
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/java/354252
Ссылки в тексте:
[1] мозг: http://www.braintools.ru
[2] git-проекта: https://github.com/maxzawalo/pcb_design
[3] Источник: https://habr.com/ru/post/507484/?utm_source=habrahabr&utm_medium=rss&utm_campaign=507484
Нажмите здесь для печати.