|
nedoPC.orgElectronics hobbyists community established in 2002 |
|
|
Page 1 of 1
|
[ 14 posts ] |
|
DDT - free software for ternary circuits design
Author |
Message |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
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
| | | | |
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 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
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 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
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 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
Example of "reinvented" full ternary adder (SUM.ddt - i3,i2,i1=o2,o1):
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:
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 |
|
|
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 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 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 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
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 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
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 |
|
|
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).
|
07 Dec 2010 06:14 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
Do you have a picture describing this approach?
|
07 Dec 2010 17:40 |
|
|
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
|
07 Dec 2010 19:05 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
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 20:43 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
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; }
| | | | |
Manually created 3-trit increment/decrement scheme (3 half-adders are used):
|
07 Jan 2011 07:50 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
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 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22827 Location: Silicon Valley
|
currently working on visualization...
|
10 Nov 2012 09:04 |
|
|
|
Page 1 of 1
|
[ 14 posts ] |
|
Who is online |
Users browsing this forum: No registered users and 1 guest |
|
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
|
|