DDT - free software for ternary circuits design

Balanced Ternary Numeral System - forum was moved from http://ternary.info

Moderator: haqreu

User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

DDT - free software for ternary circuits design

Post by Shaos »

http://www.nedopc.org/ternary/ddt_0_4_win.zip (109K)
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: 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 = 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.
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Re: DDT - free software for synthesis and simulation of...

Post by Shaos »

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
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Re: DDT - free software for synthesis and simulation of...

Post by Shaos »

Latest release for Windows:

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

There is no visualization yet...
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Re: DDT - free software for synthesis and simulation of...

Post by Shaos »

Example of "reinvented" full ternary adder (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
ddtc SUM.ddt generates this c-source:

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;
}
Testing results:

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
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).
Mac Buster
Retired
Posts: 1474
Joined: 03 Aug 2003 22:37
Location: Moscow

Re: DDT - free software for synthesis and simulation of...

Post by Mac Buster »

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.
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Re: DDT - free software for synthesis and simulation of...

Post by Shaos »

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.
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Re: DDT - free software for synthesis and simulation of...

Post by Shaos »

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
jay4th

Re: DDT - free software for synthesis and simulation of...

Post by jay4th »

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).
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Re: DDT - free software for synthesis and simulation of...

Post by Shaos »

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?
jay4th

Re: DDT - free software for synthesis and simulation of...

Post by jay4th »

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
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Re: DDT - free software for synthesis and simulation of...

Post by Shaos »

I just finished some visualization for full adder:

Code: Select all

/* 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...
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Re: DDT - free software for synthesis and simulation of...

Post by Shaos »

1-trit half-adder (or 1-trit increment/decrement scheme):

Code: Select all

/* 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
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Re: DDT - free software for synthesis and simulation of...

Post by Shaos »

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".
User avatar
Shaos
Admin
Posts: 23989
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

currently working on visualization...
Я тут за главного - если что шлите мыло на me собака shaos точка net