nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 16:39



Reply to topic  [ 14 posts ] 
DDT - free software for ternary circuits design 
Author Message
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
http://www.nedopc.org/ternary/ddt_0_4_win.zip (109K)

Quote:
DDT (DG403+DG403=Ternary) synthesis and simulation tools
========================================================

Main purpose of this package is automated design of ternary schematics,
based on analog switches DG403. Ternary signal may be connected to positive
voltage (+1 or P), negative voltage (-1 or N) or ground (0 or O). By
connecting logic voltage pins of DG403 (Vl and GND) to upper or lower
part of full range of analog voltage (between V- and V+) we may get two
different types of basic ternary elements - E12 (Vl=Ground, GND=Negative)
and E21 (Vl=Positive, GND=Ground). Each DG403 may have two E12 or two E21
elements. One E12 and one E21 may be connected together to create ternary
multiplexer (MUX) or universal ternary element. Also some special
functions may be constructed from E12 and E21, namely BLN (block
negative), BLP (block positive), RUP (rotate up), RDN (rotated down)
and NOT (ternary negation). Also there is basic element with memory
MEM (sample and hold circuit).

Source code ddt.h and ddt.c are set of functions for simulation of ternary
schematics programmatically in C-language.

DDTc is synthesis utility that may use command line argument as truth
table or as filename of DDT-file with truth table inside. Output of this
program is C-source that may be used for compiling simulation binary.

DDTp is permutating utility that is trying to find better solution
(in terms of DG403 number) by permutating inputs of given DDT-file and
calling DDTc for every combination with calculating of elements.


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 = NOT(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


Currently DDT (Decision Diagrams for Ternary) source code is located on GitLab: https://gitlab.com/ternary/ddt


Last edited by Shaos on 20 Sep 2012 20:10, edited 1 time in total.



01 Aug 2010 21:22
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
It is a free software covered by GPL v3, so source code is available on SourceForge:

http://nedopc.cvs.sourceforge.net/viewv ... c/src/ddt/

To get full sources of all NedoPC SDK do this:

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


01 Aug 2010 21:24
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Latest release for Windows:

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

There is no visualization yet...


01 Aug 2010 21:25
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Example of "reinvented" full ternary adder (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


ddtc SUM.ddt generates this c-source:

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


Testing results:

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


It requires 12 chips DG403

P.S. Interesting thing about this solution is that it's identical to the article from 1993:

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

Actually DDT's automatic design made some improvements by changing 4 multiplexers to simpler devices (E12 and E21) - and because of that we need just 12 chips to implement 14 functions (each DG403 may be connected as two E12s or two E21s).


01 Aug 2010 21:35
Profile WWW
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Quote:
Actually DDT's automatic design made some improvements by changing 4 multiplexers to simpler devices (E12 and E21) - and because of that we need just 12 chips to implement 14 functions (each DG403 may be connected as two E12s or two E21s).


Wow, at first reading I came to strange conclusion that you're talking about scheme that can dynamicaly rewire connections and so the processing device can read op-codes from RAM, decode it, rewire DG403s connections, execute the command and return result. That would be just fantastic - small ammount of executional set of DG403 chips (operational matrix) and large "re-wire controller". Crazy idea. I know I am crazy.


03 Aug 2010 04:31
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Mac Buster wrote:
Wow, at first reading I came to strange conclusion that you're talking about scheme that can dynamicaly rewire connections and so the processing device can read op-codes from RAM, decode it, rewire DG403s connections, execute the command and return result. That would be just fantastic - small ammount of executional set of DG403 chips (operational matrix) and large "re-wire controller". Crazy idea. I know I am crazy.


No, DDT is for static solutions. Dynamic solution is also possible with DG403s, but it is heavy. 1-output ternary LUT (look-up table) based on DG403s requires D(n)=3*D(n-1)+1 chips, where n - number of inputs and D(1)=1, so:
D(1)=1 (looks like ROM for 3 trits)
D(2)=4 (looks like ROM for 9 trits)
D(3)=13 (looks like ROM for 27 trits)
D(4)=40 (looks like ROM for 81 trits)
D(5)=121 (looks like ROM for 243 trits)
D(6)=364 (looks like ROM for 729 trits)
D(7)=1093 (looks like ROM for 2187 trits)
D(8)=3280 (looks like ROM for 6561 trits)
D(9)=9841 (looks like ROM for 19683 trits)
D(10)=29524 (looks like ROM for 59049 trits)
etc.
Also if we have M outputs we need M*D(N) chips where N - number of inputs.


Last edited by Shaos on 20 Sep 2012 20:10, edited 1 time in total.



04 Aug 2010 04:52
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Now DDT generated these schemes:
NOT = 2 x DG403 (50% of them),
MIN or MAX = 2 x DG403 (75% of them),
Half Adder = 6 x DG403 (83% of them),
Full Adder = 12 x DG403,
Sign of 3-trit digit = 2 x DG403,
Left/Right Shifter of 3-trit digit = 4 x DG403 (75% of them),
Universal Unary Function for 3-trit argument = 4 x DG403 (75% of them),
Universal Binary Function for 3-trit arguments = 12 x DG403,
Converter 1-trit to 2-bit = 2 x DG403 (75% of them),
Converter 2-trit to 4-bit = 8 x DG403,
Converter 3-trit to 5-bit = 18 x DG403,
Converter 4-trit to 7-bit = 39 x DG403,
Converter 5-trit to 8-bit = 83 x DG403,
Converter 6-trit to 10-bit = 162 x DG403,
Converter 2-bit to 1-trit = 1 x DG403,
Converter 4-bit to 2-trit = 11 x DG403,
Converter 5-bit to 3-trit = 32 x DG403,
Converter 7-bit to 4-trit = 80 x DG403,
Converter 8-bit to 5-trit = 154 x DG403,
Converter 10-bit to 6-trit = 309 x DG403 (not optimal),
Increment/Decrement of 1-trit digit = 6 x DG403 (83% of them),
Increment/Decrement of 2-trit digit = 10 x DG403,
Increment/Decrement of 3-trit digit = 16 x DG403,
Increment/Decrement of 4-trit digit = 22 x DG403,
Increment/Decrement of 5-trit digit = 28 x DG403,
Increment/Decrement of 6-trit digit = 34 x DG403,
Increment/Decrement of 7-trit digit = 40 x DG403,
Increment/Decrement of 8-trit digit = 46 x DG403,
Increment/Decrement of 9-trit digit = 52 x DG403 (48 manually),
Comparison 1-trit digits = 2 x DG403,
Comparison 2-trit digits = 6 x DG403,
Comparison 3-trit digits = 8 x DG403,
Comparison 4-trit digits = 12 x DG403,
Comparison 5-trit digits = 44 x DG403 (not optimal),
Adder for 1-trit digits = 12 x DG403 (delay 3) - the same as Full Adder above,
Adder for 2-trit digits = 28 x DG403 (delay 5) versus sequential version, created manually - 24 x DG403 with delay 6,
Adder for 3-trit digits = 50 x DG403 (delay 7) versus sequential version, created manually - 36 x DG403 with delay 9,
Adder for 4-trit digits = 76 x DG403 (delay 9) versus sequential version, created manually - 48 x DG403 with delay 12,
Adder for 5-trit digits = 106 x DG403 (delay 11) versus sequential version, created manually - 60 x DG403 with delay 15,
1-trit Multiplier = 2 x DG403,
2-trit Multiplier = 30 x DG403,
3-trit Multiplier = 188 x DG403,
4-trit Multiplier = 1088 x DG403


07 Dec 2010 05:04
Profile WWW
Reply with quote
For addition, beyond 3 to 5 trits, you may need to look at higher level architecture such as carry-predict, or (my favorite) carry-select adders. The Select part of carry-select can be done with about 2/3 chip delays and about #trits/4 chips. (About because you are actually selecting not only the sum, but also the carry out).


07 Dec 2010 06:14
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
jay4th wrote:
For addition, beyond 3 to 5 trits, you may need to look at higher level architecture such as carry-predict, or (my favorite) carry-select adders. The Select part of carry-select can be done with about 2/3 chip delays and about #trits/4 chips. (About because you are actually selecting not only the sum, but also the carry out).


Do you have a picture describing this approach?


07 Dec 2010 17:40
Profile WWW
Reply with quote
http://en.wikipedia.org/wiki/Carry-select_adder has a good presentation for the binary case. For trinary obviously the select stages must choose between three 'speculativly' calculated sums: Ahi + Bhi + -1, Ahi + Bhi + 0, Ahi + Bhi + 1.

The chip count then is 3x(chips for multiply) + chips for 3:1 mux. And additional chips for adding the low part. Obvious extensions for more than two parts.

Right now it is believed that the fastest adders that can be built use a carry predict portion and then a sum select portion. The "carry-select" adder is a hybrid, doing ripple carry between select stages.

That is, if you are adding Alo Amed Ahi to Blo Bmed Bhi, then which of the three computations of Bhi + Ahi + C depends on the result of which of the choices of Bmed + Amed you made.

The pictures make it much clearer I think.

Jay


07 Dec 2010 19:05
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
I just finished some visualization for full adder:

Code:
/* Generated by DDTc v0.5
   Solution is 12 x DG403
   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_mux(f,i1,O,P,N,&r1);
 if(f1 < 0) return f1;
 f2 = ddt_mux(f,i1,P,N,O,&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_e21(f,i1,N,O,&r7);
 if(f7 < 0) return f7;
 f8 = ddt_e12(f,i1,N,O,&r8);
 if(f8 < 0) return f8;
 f9 = ddt_e21(f,i1,O,P,&r9);
 if(f9 < 0) return f9;
 f10 = ddt_e12(f,i1,O,P,&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;
}


Image

Schematics were created in Logisim - "x2" means "ternary input/output"

P.S. Image creation is not yet automatic...


02 Jan 2011 20:43
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
1-trit half-adder (or 1-trit increment/decrement scheme):

Code:
/* Generated by DDTc v0.5
   Solution is 6 x DG403
   See www.ternary.info */

#include "ddt.h"

int ddt_inde1_(int f, DDT i1, DDT i2, DDT* o1, DDT* o2)
{
 DDT r1,r2,r3,r4,r5,r6;
 int f1,f2,f3,f4,f5,f6;
 f1 = ddt_mux(f,i1,P,N,O,&r1);
 if(f1 < 0) return f1;
 f2 = ddt_mux(f,i1,O,P,N,&r2);
 if(f2 < 0) return f2;
 f3 = ddt_mux(f,i2,r1,i1,r2,&r3);
 if(f3 < 0) return f3;
 f4 = ddt_e12(f,i1,N,O,&r4);
 if(f4 < 0) return f4;
 f5 = ddt_e21(f,i1,O,P,&r5);
 if(f5 < 0) return f5;
 f6 = ddt_mux(f,i2,r4,O,r5,&r6);
 if(f6 < 0) return f6;
 if(o1) *o1 = r3;
 if(o2) *o2 = r6;
 return f1+f2+f3+f4+f5+f6;
}


Image

Manually created 3-trit increment/decrement scheme (3 half-adders are used):

Image


07 Jan 2011 07:50
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Interesting, but I just found DDT approach described in the book from 1975: S.Thelliez "Introduction to the study of ternary switching structures (Information and systems theory, Volume 4)". In this book ternary multiplexer named "T operator".


10 Aug 2011 20:48
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Post 
currently working on visualization...

_________________
:dj: https://mastodon.social/@Shaos


10 Nov 2012 09:04
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 14 posts ] 

Who is online

Users browsing this forum: No registered users and 6 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:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.