nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 26 Nov 2020 05:49



Reply to topic  [ 27 posts ]  Go to page 1, 2  Next
DDT - свободная система разработки троичного железа 
Author Message
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
DDT - это пакет программ под свободной лицензией GPL3, предназначенных для генерации схем для троичного железа, построенных на электронных ключах DG403 (ну или вообще на абстрактных троичных селекторах).

Сейчас доступна версия v0.4 под винды:

http://www.nedopc.org/ternary/ddt_0_4_win.zip (109K)

Исходники лежат на SourceForge: nedopc.cvs.sourceforge.net/viewvc/nedopc/src/ddt/
Забрать текущие исходники NedoPC SDK к себе на комп можно так:
cvs -z3 -d:pserver:anonymous@nedopc.cvs.sourceforge.net:/cvsroot/nedopc checkout -P src

С марта 2015 исходники DDT лежат тут: github.com/ternary-info/ddt


С июня 2018 исходники DDT лежат тут: https://gitlab.com/ternary/ddt

P.S. Архивы всех предыдущих версий DDT:
http://ternary.info/ternary/ddt_0_1_win.zip (59K)
http://ternary.info/ternary/ddt_0_2_win.zip (69K)
http://ternary.info/ternary/ddt_0_3_win.zip (108K)
http://ternary.info/ternary/ddt_0_4_win.zip (109K)


Last edited by Shaos on 24 Feb 2015 10:16, edited 2 times in total.



15 Jul 2010 19:27
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
Программа создана по итогам размышлений в топике про троичное железо на основе CMOS-ключей.
Вот пример генерации схемы троичного полусумматора (в виндовом варианте запускаем test_hs.bat):

ddtc PNONOPOPN,NOOOOOOOP

Code:
/* Generated by ddtc v0.1
   See www.ternary.info */

#include "ddt.h"

int ddt_(int f, DDT i1, DDT i2, DDT* o1, DDT* o2)
{
   DDT r1,r2,r3,r4,r5,r6;
   int e1,e2,e3,e4,e5,e6;
   e1 = ddt_rdn(f,i1,&r1);
   if(e1 < 0) return e1;
   e2 = ddt_rup(f,i1,&r2);
   if(e2 < 0) return e2;
   e3 = ddt_mux(f,i2,r1,i1,r2,&r3);
   if(e3 < 0) return e3;
   e4 = ddt_blp(f,i1,&r4);
   if(e4 < 0) return e4;
   e5 = ddt_bln(f,i1,&r5);
   if(e5 < 0) return e5;
   e6 = ddt_mux(f,i2,r4,'O',r5,&r6);
   if(e6 < 0) return e6;
   if(o1) *o1 = r3;
   if(o2) *o2 = r6;
   return e1+e2+e3+e4+e5+e6;
}


тест-программа:

Code:
#include <stdio.h>
#include <stdlib.h>
#include "ddt.h"
#include "ddt_.c"

char ax[] = "NOPNOPNOP";
char ay[] = "NNNOOOPPP";

int main()
{
 int i,t;
 DDT r,rr[9];

 printf("\nE12:%i E21:%i (MUX:%i,NOT:%i,BLP:%i,BLN:%i,RUP:%i,RDN:%i)\n\n",
   ddt_(DDT_E12,0,0,NULL,NULL),ddt_(DDT_E21,0,0,NULL,NULL),
   ddt_(DDT_MUX,0,0,NULL,NULL),ddt_(DDT_NOT,0,0,NULL,NULL),
   ddt_(DDT_BLP,0,0,NULL,NULL),ddt_(DDT_BLN,0,0,NULL,NULL),
   ddt_(DDT_RUP,0,0,NULL,NULL),ddt_(DDT_RDN,0,0,NULL,NULL));

 printf("\| N O P |\n----------\n");
 for(i=0;i<9;i++)
 {
   t = ddt_(DDT_SIM,ax[i],ay[i],&r,&rr[i]);
   if(!(i%3)) printf("%c|",ay[i]);
   printf(" %c",r);
   if((i%3)==2) printf(" |\n");
 } 
 printf("----------\n\n");

 printf("\| N O P |\n----------\n");
 for(i=0;i<9;i++)
 {
   if(!(i%3)) printf("%c|",ay[i]);
   printf(" %c",rr[i]);
   if((i%3)==2) printf(" |\n");
 } 
 printf("----------\n\n");

 printf("dt=%i\n",t);

 return 0;
}


результат её запуска:

Code:
E12:5 E21:5 (MUX:4,NOT:0,BLP:1,BLN:1,RUP:1,RDN:1)

\| N O P |
----------
N| P N O |
O| N O P |
P| O P N |
----------

\| N O P |
----------
N| N O O |
O| O O O |
P| O O P |
----------

dt=10


Как видно программа насчитала 5 блоков E12 и 5 блоков E21, т.е. всего потребуется 6 микросхем DG403 (3 подключены как 2xE12 и 3 подключены как 2xE21).


15 Jul 2010 19:29
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
Одноразрядный полный сумматор (SUM.ddt) в формате i3,i2,i1=o2,o1:

Code:
NNN=NO
NNO=NP
NNP=ON
NON=NP
NOO=ON
NOP=OO
NPN=ON
NPO=OO
NPP=OP
ONN=NP
ONO=ON
ONP=OO
OON=ON
OOO=OO
OOP=OP
OPN=OO
OPO=OP
OPP=PN
PNN=ON
PNO=OO
PNP=OP
PON=OO
POO=OP
POP=PN
PPN=OP
PPO=PN
PPP=PO


Получившееся описание схемы:

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;
}


Результат тестирования:

Code:
Number of MUX in FUN is 10
Number of E12 in FUN is 12
Number of E21 in FUN is 12

NNN|NO
NNO|NP
NNP|ON
NON|NP
NOO|ON
NOP|OO
NPN|ON
NPO|OO
NPP|OP
ONN|NP
ONO|ON
ONP|OO
OON|ON
OOO|OO
OOP|OP
OPN|OO
OPO|OP
OPP|PN
PNN|ON
PNO|OO
PNP|OP
PON|OO
POO|OP
POP|PN
PPN|OP
PPO|PN
PPP|PO

dt=24


По 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 20:42
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
Вот второй релиз под винды:

http://www.nedopc.org/ternary/ddt_0_2_win.zip (69K)

Добавил поддержку DDT-файлов (есть примеры SUM.ddt и ALU.ddt) и снял явные ограничения на количество входов и выходов (неявные остались - 99 входов и 999 функций).

Бета-тестеры - где же вы? ;)


16 Jul 2010 21:07
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
На сегодняшний день имеется следующие файлы и программы:
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 15:05
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
Вот третий релиз под винды:

http://www.nedopc.org/ternary/ddt_0_3_win.zip (108K)

Кое-что пооптимизил. Кроме того добавилась программа ddtp.exe, которая делая перестановки входов у DDT-файла пытается найти лучший вариант в смысле количества используемых DG403.


27 Jul 2010 23:12
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
Добавил несколько новых функций для детектирования (а также переименовал 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 20:59
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
Очередная сборка под винды:

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 22:18
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
Вчера начал заново писать визуализацию DDTv: http://nedopc.cvs.sourceforge.net/viewv ... c/src/ddt/

За день написал 500 строк сишного кода - полный разбор сгенерированного исходника ddt_*.c и построение упорядоченного списка связей - теперь дело за малым - всё это нарисовать...


10 Jul 2011 07:03
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
Shaos wrote:

Интересно, что моя автоматическая реализация троичного сумматора получилась один в один как вот в этой статье 1993 года:

http://www.hindawi.com/journals/vlsi/19 ... 6.abs.html

Разве что я получил небольшую оптимизацию путём замены некоторых полных троичных мультиплексоров на упрощённые - E21 и E12 (странно что индийские авторы сами до этого не додумались - у них для этого уже всё было - а именно сигналы PTI и NTI)


Нашёл ещё более раннее описание алгоритма синтеза, переизобретённого мной в 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 21:52
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
Shaos wrote:
Shaos wrote:

Интересно, что моя автоматическая реализация троичного сумматора получилась один в один как вот в этой статье 1993 года:

http://www.hindawi.com/journals/vlsi/19 ... 6.abs.html

Разве что я получил небольшую оптимизацию путём замены некоторых полных троичных мультиплексоров на упрощённые - E21 и E12 (странно что индийские авторы сами до этого не додумались - у них для этого уже всё было - а именно сигналы PTI и NTI)


Нашёл ещё более раннее описание алгоритма синтеза, переизобретённого мной в 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. Цитата:
Quote:
Researchers have of late suggested refinements on the BDD data structure giving way to a number of related graphs, such as BMD (binary moment diagrams), ZDD (zero-suppressed decision diagram), FDD (free binary decision diagrams), PDD (parity decision diagrams), and MTBDDs (multiple terminal BDDs).
А теперь ещё есть моя DDT - Decision Diagrams for [Balanced] Ternary ;)

P.P.P.S. На самом деле когда я придумывал название DDT, я ничего не знал про "Decision Diagrams" - моё DDT просто означало "Double D403 Ternary" или что-то типа того, а теперь оказывается, что "Ternary Decision Diagrams" обмусолены неоднократно во всяких академических статьях конца прошлого и начала этого века, правда в большинстве из них используется несбалансированная троичность (0,1,2)...

_________________
:eugeek: https://twitter.com/Shaos1973


24 Feb 2015 09:58
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
На самом деле на sourceforge лежит релиз-кандидат v0.5, причём лежит с лета 2011 - ждёт когда я допишу визуализацию DDTv...

P.S. DDTv с 2011 года умеет следующее (на примере ALU для 3niti alpha):
Code:
./ddtv ddt_ALU.c

DDT v0.5 (c) 2010-2011, Alexander A. Shabarshin <me@shaos.net>
DDTv converts C-source of DDT-scheme to GIF image

Reading 'ddt_ALU.c'...
65 functions found
8 input variables found
65 temporary variables found
4 output variables found
Tracing links...
313 links traced
Detecting levels...
9 levels detected (8 internal)
Level 0: 8 external inputs
Level 1: 10 functions with 36 inputs (u=3 c=26) and 10 outputs
Level 2: 12 functions with 48 inputs (u=16 c=3) and 12 outputs
Level 3: 13 functions with 40 inputs (u=15 c=0) and 13 outputs
Level 4: 10 functions with 40 inputs (u=21 c=0) and 10 outputs
Level 5: 9 functions with 28 inputs (u=11 c=0) and 9 outputs
Level 6: 7 functions with 28 inputs (u=15 c=0) and 7 outputs
Level 7: 2 functions with 8 inputs (u=7 c=0) and 2 outputs
Level 8: 2 functions with 8 inputs (u=7 c=0) and 2 outputs
Level 9: 4 external outputs
Longest function name is 3 characters
Longest input name is 2 characters
Longest output name is 2 characters
Longest temporary name is 3 characters
Initial size of the image 2032 x 760 (254 x 95 cells)
Sorting by level...

_________________
:eugeek: https://twitter.com/Shaos1973


07 Mar 2015 18:35
Profile WWW
Fanat
User avatar

Joined: 18 Nov 2014 10:17
Posts: 53
Location: Отсюда
Reply with quote
Похожий продукт (только для двоичности) - это Logic Friday. http://sontrak.com/downloads.html
Программка генерит из таблички значений либо из уравнения схему логических элементов.
Возможно, есть смысл взять оттуда библиотеку визуализации.
Пока не умеет переставлять выводы на блоках и оптимизировать расположение,
в результате результат выглядит слегка запутанно.


17 Mar 2015 02:49
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18968
Location: Silicon Valley
Reply with quote
JeNNeR wrote:
Похожий продукт (только для двоичности) - это Logic Friday. http://sontrak.com/downloads.html
Программка генерит из таблички значений либо из уравнения схему логических элементов.
Возможно, есть смысл взять оттуда библиотеку визуализации.
Пока не умеет переставлять выводы на блоках и оптимизировать расположение,
в результате результат выглядит слегка запутанно.

Там "espresso", который реализует алгоритм SAT - это альтернатива BDD, а вообще про BDD много есть софта, как оказалось:

https://github.com/johnyf/tool_lists/blob/master/bdd.md

P.S. По идее SAT-у ненадо переставлять входы для получения оптимального решения - он и так должен найти оптимальное (если оно есть)...

_________________
:eugeek: https://twitter.com/Shaos1973


17 Mar 2015 09:21
Profile WWW
Fanat
User avatar

Joined: 18 Nov 2014 10:17
Posts: 53
Location: Отсюда
Reply with quote
Он при визуализации не умеет их менять местами, поэтому очень часто к элементу снизу включен верхний контакт, а сверху включен нижний, а линии идут крест-накрест.


Attachments:
Безымянный.png
Безымянный.png [ 14.66 KiB | Viewed 9397 times ]
19 Mar 2015 05:32
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 27 posts ]  Go to page 1, 2  Next

Who is online

Users browsing this forum: No registered users and 2 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

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.