|
nedoPC.orgElectronics hobbyists community established in 2002 |
|
DDT - свободная система разработки троичного железа
Author |
Message |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
Одноразрядный полный сумматор (SUM.ddt) в формате i3,i2,i1=o2,o1: Получившееся описание схемы: | | | | Code: /* Generated by DDTc v0.4 See www.ternary.info */
#include "ddt.h"
int ddt_sum(int f, DDT i1, DDT i2, DDT i3, DDT* o1, DDT* o2) { DDT r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,r11,r12,r13,r14; int f1,f2,f3,f4,f5,f6,f7,f8,f9,f10,f11,f12,f13,f14; f1 = ddt_rou(f,i1,&r1); if(f1 < 0) return f1; f2 = ddt_rod(f,i1,&r2); if(f2 < 0) return f2; f3 = ddt_mux(f,i2,r1,r2,i1,&r3); if(f3 < 0) return f3; f4 = ddt_mux(f,i2,r2,i1,r1,&r4); if(f4 < 0) return f4; f5 = ddt_mux(f,i2,i1,r1,r2,&r5); if(f5 < 0) return f5; f6 = ddt_mux(f,i3,r3,r4,r5,&r6); if(f6 < 0) return f6; f7 = ddt_shd(f,i1,&r7); if(f7 < 0) return f7; f8 = ddt_blp(f,i1,&r8); if(f8 < 0) return f8; f9 = ddt_bln(f,i1,&r9); if(f9 < 0) return f9; f10 = ddt_shu(f,i1,&r10); if(f10 < 0) return f10; f11 = ddt_mux(f,i2,r7,r8,O,&r11); if(f11 < 0) return f11; f12 = ddt_mux(f,i2,r8,O,r9,&r12); if(f12 < 0) return f12; f13 = ddt_mux(f,i2,O,r9,r10,&r13); if(f13 < 0) return f13; f14 = ddt_mux(f,i3,r11,r12,r13,&r14); if(f14 < 0) return f14; if(o1) *o1 = r6; if(o2) *o2 = r14; return f1+f2+f3+f4+f5+f6+f7+f8+f9+f10+f11+f12+f13+f14; }
| | | | |
Результат тестирования: По E12 и E21 подсчитываем количество необходимых корпусов - 12/2+12/2=6+6=12 P.S. Интересно, что моя автоматическая реализация троичного сумматора получилась один в один как вот в этой статье 1996 года: http://www.hindawi.com/journals/vlsi/1996/094696.abs.htmlРазве что я получил небольшую оптимизацию путём замены некоторых полных троичных мультиплексоров на упрощённые - E21 и E12 (странно что индийские авторы сами до этого не додумались - у них для этого уже всё было - а именно сигналы PTI и NTI)
|
16 Jul 2010 19:42 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
Вот второй релиз под винды:
http://www.nedopc.org/ternary/ddt_0_2_win.zip (69K)
Добавил поддержку DDT-файлов (есть примеры SUM.ddt и ALU.ddt) и снял явные ограничения на количество входов и выходов (неявные остались - 99 входов и 999 функций).
Бета-тестеры - где же вы?
|
16 Jul 2010 20:07 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
На сегодняшний день имеется следующие файлы и программы:
ddt.h/ddt.c - библиотечные компоненты для симуляции (в h-файле также содержится номер версии всего пакета)
ddtc.c (DDTc) - исходник программы синтеза троичной схемы по таблице истинности и сохранения результата в исходника на языке Си
Кроме DDTc предполагается создать следующие программы:
DDTp - программа нахождения оптимального расположения входов (путём перебора всех возможных перестановок входов схемы), которое привело бы к оптимальному решению с помощью DDTc
DDTv - программа визуализации полученного решения (сохраняет в GIF)
DDTg - программа генерации гербер-файлов печатной платы по готовому решению
DDTx - программа генерации VHDL-файлов для прошивки в CPLD и FPGA от Xilinx
DDTi - интерактивная среда разработки и симуляции схем
P.S. DDTb - программа трансляции троичного решения в двоичное (c-source, gif-image, gerbers)
|
18 Jul 2010 14:05 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
Вот третий релиз под винды:
http://www.nedopc.org/ternary/ddt_0_3_win.zip (108K)
Кое-что пооптимизил. Кроме того добавилась программа ddtp.exe, которая делая перестановки входов у DDT-файла пытается найти лучший вариант в смысле количества используемых DG403.
|
27 Jul 2010 22:12 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
Добавил несколько новых функций для детектирования (а также переименовал RDN в ROD и RUP в ROU): | | | | Code: all ternary functions of one argument: NNN = N NNO = SHD(x) = E21(x,N,O) NNP = E21(x,N,P) NON = MUX(x,N,O,N) = E12(x,N,E21(x,O,N)) NOO = BLP(x) = E12(x,N,O) // analog of reverse diode NOP = x // or buffer MUX(x,N,O,P) = E12(x,N,E21(x,O,P)) NPN = MUX(x,N,P,N) = E12(x,N,E21(x,P,N)) NPO = MUX(x,N,P,O) = E12(x,N,E21(x,P,O)) NPP = E12(x,N,P) ONN = NHI(x) = E12(x,O,N) ONO = MUX(x,O,N,O) = E12(x,O,E21(x,N,O)) ONP = MUX(x,O,N,P) = E12(x,O,E21(x,N,P)) OON = E21(x,O,N) OOO = O OOP = BLN(x) = E21(x,O,P) // analog of forward diode OPN = ROU(x) = MUX(x,O,P,N) = E12(x,O,E21(x,P,N)) OPO = MUX(x,O,P,O) = E12(x,O,E21(x,P,O)) OPP = SHU(x) = E12(x,O,P) PNN = NTI(x) = E12(x,P,N) PNO = ROD(x) = MUX(x,P,N,O) = E12(x,P,E21(x,N,O)) PNP = MUX(x,P,N,P) = E12(x,P,E21(x,N,P)) PON = INV(x) = MUX(x,P,O,N) = E12(x,P,E21(x,O,N)) POO = E12(x,P,O) POP = MUX(x,P,O,P) = E12(x,P,E21(x,O,P)) PPN = PTI(x) = E21(x,P,N) PPO = PHI(x) = E21(x,P,O) PPP = P
| | | | |
|
01 Aug 2010 19:59 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
Очередная сборка под винды: http://www.nedopc.org/ternary/ddt_0_4_win.zip (109K) - поддержка '0' и '1' как альтернатива 'O' и 'P' (для генерации двоичных схем) - поддержка комментариев после символа # в DDT-файлах - больше информации в сгенерированном утилитой DDTp файле - переименованы RDN и RUP в ROD и ROU - добавлено больше функций для обнаружения (SHU,SHD,PTI,NTI,PHI,NHI) - добавлена опция -e детектирующая только базовые элементы E12, E21 и MUX
|
01 Aug 2010 21:18 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
Вчера начал заново писать визуализацию DDTv: http://nedopc.cvs.sourceforge.net/viewv ... c/src/ddt/За день написал 500 строк сишного кода - полный разбор сгенерированного исходника ddt_*.c и построение упорядоченного списка связей - теперь дело за малым - всё это нарисовать...
|
10 Jul 2011 06:03 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
Нашёл ещё более раннее описание алгоритма синтеза, переизобретённого мной в DDTc: S.Thelliez "Introduction to the study of ternary switching structures (Information and systems theory, Volume 4)", 1975. Это английский перевод французской книжки 1973 года. Правда автор называет троичный мультиплексор именем "T operator" и чаще использует значения 0,1,2 чем -,0,+. Там даже описано переворачивание таблиц истинности для получения лучшего результата - как раз то, что делает DDTp. Также там не только комбинационные схемы рассмотрены, но и автоматы. Даже аппаратная реализация на биполярных транзисторах и диодах имеется. В списке литературы много русских имён, в том числе есть Брусенцов.
|
10 Aug 2011 20:52 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
| | | | Shaos wrote: Нашёл ещё более раннее описание алгоритма синтеза, переизобретённого мной в DDTc: S.Thelliez "Introduction to the study of ternary switching structures (Information and systems theory, Volume 4)", 1975. Это английский перевод французской книжки 1973 года. Правда автор называет троичный мультиплексор именем "T operator" и чаще использует значения 0,1,2 чем -,0,+. Там даже описано переворачивание таблиц истинности для получения лучшего результата - как раз то, что делает DDTp. Также там не только комбинационные схемы рассмотрены, но и автоматы. Даже аппаратная реализация на биполярных транзисторах и диодах имеется. В списке литературы много русских имён, в том числе есть Брусенцов. | | | | |
Интересно, что тоже самое делает и BDD - строит дерево, переставляет входные переменные и т.д. Причём BDD появилось ТОЛЬКО в 1986 году после выхода статьи за авторством некоего господина по имени Randal E. Bryant (причём даже Кнут назвал это самым большим прорывом за последние 25 лет). Википедия пишет, что BDD щас активно используется в компьютерных программах для логического синтеза микросхем и FPGA - так что я был на правильном пути, когда всё это переизобрёл для троичности. P.S. Там же в википедии указывается на самое первое упоминание этого подхода: C. Y. Lee. "Representation of Switching Circuits by Binary-Decision Programs". Bell Systems Technical Journal, 38:985–999, 1959.P.P.S. Цитата: А теперь ещё есть моя DDT - Decision Diagrams for [Balanced] Ternary P.P.P.S. На самом деле когда я придумывал название DDT, я ничего не знал про "Decision Diagrams" - моё DDT просто означало "Double D403 Ternary" или что-то типа того, а теперь оказывается, что "Ternary Decision Diagrams" обмусолены неоднократно во всяких академических статьях конца прошлого и начала этого века, правда в большинстве из них используется несбалансированная троичность (0,1,2)...
|
24 Feb 2015 08:58 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
На самом деле на sourceforge лежит релиз-кандидат v0.5, причём лежит с лета 2011 - ждёт когда я допишу визуализацию DDTv... P.S. DDTv с 2011 года умеет следующее (на примере ALU для 3niti alpha):
|
07 Mar 2015 17:35 |
|
|
JeNNeR
Fanat
Joined: 18 Nov 2014 09:17 Posts: 52 Location: Отсюда
|
Похожий продукт (только для двоичности) - это Logic Friday. http://sontrak.com/downloads.htmlПрограммка генерит из таблички значений либо из уравнения схему логических элементов. Возможно, есть смысл взять оттуда библиотеку визуализации. Пока не умеет переставлять выводы на блоках и оптимизировать расположение, в результате результат выглядит слегка запутанно.
|
17 Mar 2015 01:49 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
| | | | JeNNeR wrote: Похожий продукт (только для двоичности) - это Logic Friday. http://sontrak.com/downloads.htmlПрограммка генерит из таблички значений либо из уравнения схему логических элементов. Возможно, есть смысл взять оттуда библиотеку визуализации. Пока не умеет переставлять выводы на блоках и оптимизировать расположение, в результате результат выглядит слегка запутанно. | | | | |
Там "espresso", который реализует алгоритм SAT - это альтернатива BDD, а вообще про BDD много есть софта, как оказалось: https://github.com/johnyf/tool_lists/blob/master/bdd.mdP.S. По идее SAT-у ненадо переставлять входы для получения оптимального решения - он и так должен найти оптимальное (если оно есть)...
|
17 Mar 2015 08:21 |
|
|
JeNNeR
Fanat
Joined: 18 Nov 2014 09:17 Posts: 52 Location: Отсюда
|
Он при визуализации не умеет их менять местами, поэтому очень часто к элементу снизу включен верхний контакт, а сверху включен нижний, а линии идут крест-накрест.
|
19 Mar 2015 04:32 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22606 Location: Silicon Valley
|
Поисследовал всё, что мною наделано в DDT - есть проблема: хоть там и присутствует элемент с памятью MEM, однако ни одной схемы с MEM я так и не нагородил, т.к. в-целом существующий DDT не рассчитан на генерацию схем с памятью (и по сути на симуляцию тоже). Если расположить два мультиплексора друг за другом и связать обратной связью, то запоминания не произойдёт, т.к. все переменные живут только в пределах одного шага. Чтобы запоминание таки произошло, каждую временную переменную (как собственно все выходы, а может и входы), надо хранить между шагами симуляции - тогда можно будет запоминать значения на обратных связях (и на обрывах, если вход отрывается). Таким образом каждый блок получает память, выделяемую из внешнего массива троичных значений - после этого необходимость в MEM на низком уровне отпадёт, т.к. его можно будет построить на двух мультиплексорах, связанных обратной связью...
|
19 Mar 2015 13:07 |
|
|
JeNNeR
Fanat
Joined: 18 Nov 2014 09:17 Posts: 52 Location: Отсюда
|
Я в SAT это лечил путём изобретения «псевдовыводов». Например, надо было сохранять состояние двух битов (1 трита) - 1. создал две дополнительные выходные и две дополнительные входные (заодно получил грабли в виде того, что нашел жесткое ограничение по количеству входных), 2. описал в километровой табличке состояний все возможные комбинации входных и выходных (соответственно табличка увеличивалась в 2^4=16 раз)... 3. а после создания схемы просто соединил входные и выходные между собой. (в Пайнте)
|
19 Mar 2015 13:18 |
|
|
Who is online |
Users browsing this forum: No registered users and 37 guests |
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum
|
|