DDT - свободная система разработки троичного железа

[Shaos]

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 к себе на комп можно так:

Code: Select all

cvs -z3 -d:pserver:anonymous@nedopc.cvs.sourceforge.net:/cvsroot/nedopc checkout -P src[/color]

В марте 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)

[Shaos]

Программа создана по итогам размышлений в топике про троичное железо на основе CMOS-ключей.
Вот пример генерации схемы троичного полусумматора (в виндовом варианте запускаем test_hs.bat):

ddtc PNONOPOPN,NOOOOOOOP

Code: Select all

/* 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: Select all

#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: Select all

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).

[Shaos]

Одноразрядный полный сумматор (SUM.ddt) в формате i3,i2,i1=o2,o1:

Code: Select all

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: Select all

/* 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: Select all

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)

[Shaos]

Вот второй релиз под винды:

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

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

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

[Shaos]

На сегодняшний день имеется следующие файлы и программы:
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)

[Shaos]

Вот третий релиз под винды:

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

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

[Shaos]

Добавил несколько новых функций для детектирования (а также переименовал RDN в ROD и RUP в ROU):

Code: Select all

 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

[Shaos]

Очередная сборка под винды:

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

[Shaos]

Вчера начал заново писать визуализацию DDTv: http://nedopc.cvs.sourceforge.net/viewv ... c/src/ddt/

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

[Shaos]

Интересно, что моя автоматическая реализация троичного сумматора получилась один в один как вот в этой статье 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. Также там не только комбинационные схемы рассмотрены, но и автоматы. Даже аппаратная реализация на биполярных транзисторах и диодах имеется. В списке литературы много русских имён, в том числе есть Брусенцов.

[Shaos]

Интересно, что моя автоматическая реализация троичного сумматора получилась один в один как вот в этой статье 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. Цитата:

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)...

[Shaos]

На самом деле на sourceforge лежит релиз-кандидат v0.5, причём лежит с лета 2011 - ждёт когда я допишу визуализацию DDTv...

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

Code: Select all

./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...

[JeNNeR]

Похожий продукт (только для двоичности) - это Logic Friday:
https://web.archive.org/web/20150311050100/http://sontrak.com/downloads.html
Программка генерит из таблички значений либо из уравнения схему логических элементов.
Возможно, есть смысл взять оттуда библиотеку визуализации.
Пока не умеет переставлять выводы на блоках и оптимизировать расположение,
в результате результат выглядит слегка запутанно.

[Shaos]

Похожий продукт (только для двоичности) - это Logic Friday...
Программка генерит из таблички значений либо из уравнения схему логических элементов.
Возможно, есть смысл взять оттуда библиотеку визуализации.
Пока не умеет переставлять выводы на блоках и оптимизировать расположение,
в результате результат выглядит слегка запутанно.

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

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

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

[JeNNeR]

Он при визуализации не умеет их менять местами, поэтому очень часто к элементу снизу включен верхний контакт, а сверху включен нижний, а линии идут крест-накрест.