
nedoPC.orgCommunity of electronics hobbyists established in 2002 

...

Page 1 of 1

[ 14 posts ] 

[Ternary] DDT  free software for ternary circuits design
Author 
Message 
Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

http://www.nedopc.org/ternary/ddt_0_4_win.zip (109K)
    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
    
Last edited by Shaos on 20 Sep 2012 21:10, edited 1 time in total.

01 Aug 2010 22:22 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

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 22:24 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

Latest release for Windows:
http://www.nedopc.org/ternary/ddt_0_4_win.zip (109K)
There is no visualization yet...

01 Aug 2010 22:25 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

Example of "reinvented" full ternary adder (SUM.ddt  i3,i2,i1=o2,o1):
ddtc SUM.ddt generates this csource:     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:
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 22:35 


Mac Buster
Retired
Joined: 03 Aug 2003 23:37 Posts: 1483 Location: Moscow

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 opcodes 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 "rewire controller". Crazy idea. I know I am crazy.

03 Aug 2010 05:31 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

No, DDT is for static solutions. Dynamic solution is also possible with DG403s, but it is heavy. 1output ternary LUT (lookup table) based on DG403s requires D(n)=3*D(n1)+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 21:10, edited 1 time in total.

04 Aug 2010 05:52 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

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 3trit digit = 2 x DG403,
Left/Right Shifter of 3trit digit = 4 x DG403 (75% of them),
Universal Unary Function for 3trit argument = 4 x DG403 (75% of them),
Universal Binary Function for 3trit arguments = 12 x DG403,
Converter 1trit to 2bit = 2 x DG403 (75% of them),
Converter 2trit to 4bit = 8 x DG403,
Converter 3trit to 5bit = 18 x DG403,
Converter 4trit to 7bit = 39 x DG403,
Converter 5trit to 8bit = 83 x DG403,
Converter 6trit to 10bit = 162 x DG403,
Converter 2bit to 1trit = 1 x DG403,
Converter 4bit to 2trit = 11 x DG403,
Converter 5bit to 3trit = 32 x DG403,
Converter 7bit to 4trit = 80 x DG403,
Converter 8bit to 5trit = 154 x DG403,
Converter 10bit to 6trit = 309 x DG403 (not optimal),
Increment/Decrement of 1trit digit = 6 x DG403 (83% of them),
Increment/Decrement of 2trit digit = 10 x DG403,
Increment/Decrement of 3trit digit = 16 x DG403,
Increment/Decrement of 4trit digit = 22 x DG403,
Increment/Decrement of 5trit digit = 28 x DG403,
Increment/Decrement of 6trit digit = 34 x DG403,
Increment/Decrement of 7trit digit = 40 x DG403,
Increment/Decrement of 8trit digit = 46 x DG403,
Increment/Decrement of 9trit digit = 52 x DG403 (48 manually),
Comparison 1trit digits = 2 x DG403,
Comparison 2trit digits = 6 x DG403,
Comparison 3trit digits = 8 x DG403,
Comparison 4trit digits = 12 x DG403,
Comparison 5trit digits = 44 x DG403 (not optimal),
Adder for 1trit digits = 12 x DG403 (delay 3)  the same as Full Adder above,
Adder for 2trit digits = 28 x DG403 (delay 5) versus sequential version, created manually  24 x DG403 with delay 6,
Adder for 3trit digits = 50 x DG403 (delay 7) versus sequential version, created manually  36 x DG403 with delay 9,
Adder for 4trit digits = 76 x DG403 (delay 9) versus sequential version, created manually  48 x DG403 with delay 12,
Adder for 5trit digits = 106 x DG403 (delay 11) versus sequential version, created manually  60 x DG403 with delay 15,
1trit Multiplier = 2 x DG403,
2trit Multiplier = 30 x DG403,
3trit Multiplier = 188 x DG403,
4trit Multiplier = 1088 x DG403

07 Dec 2010 06:04 


jay4th

For addition, beyond 3 to 5 trits, you may need to look at higher level architecture such as carrypredict, or (my favorite) carryselect adders. The Select part of carryselect 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 07:14 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

Do you have a picture describing this approach?

07 Dec 2010 18:40 


jay4th

http://en.wikipedia.org/wiki/Carryselect_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 "carryselect" 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 20:05 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

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; }
    
Schematics were created in Logisim  "x2" means "ternary input/output"
P.S. Image creation is not yet automatic...

02 Jan 2011 21:43 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

1trit halfadder (or 1trit 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; }
    
Manually created 3trit increment/decrement scheme (3 halfadders are used):

07 Jan 2011 08:50 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

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 21:48 


Shaos
Admin
Joined: 09 Jan 2003 00:22 Posts: 16355 Location: Colorado

currently working on visualization...

10 Nov 2012 10:04 



Page 1 of 1

[ 14 posts ] 

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

