nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 27 Apr 2024 17:17



Reply to topic  [ 26 posts ]  Go to page 1, 2  Next
DDT - свободная система разработки троичного железа 
Author Message
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
Одноразрядный полный сумматор (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


Получившееся описание схемы:

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


Результат тестирования:

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


По 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)


16 Jul 2010 19:42
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
Вот второй релиз под винды:

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

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

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


16 Jul 2010 20:07
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
На сегодняшний день имеется следующие файлы и программы:
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)


18 Jul 2010 14:05
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
Вот третий релиз под винды:

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

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


27 Jul 2010 22:12
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
Добавил несколько новых функций для детектирования (а также переименовал RDN в ROD и RUP в ROU):

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


01 Aug 2010 19:59
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
Очередная сборка под винды:

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


01 Aug 2010 21:18
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
Вчера начал заново писать визуализацию DDTv: http://nedopc.cvs.sourceforge.net/viewv ... c/src/ddt/

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


10 Jul 2011 06:03
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
Shaos wrote:

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


10 Aug 2011 20:52
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
Shaos wrote:
Shaos wrote:

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

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


24 Feb 2015 08:58
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
На самом деле на sourceforge лежит релиз-кандидат v0.5, причём лежит с лета 2011 - ждёт когда я допишу визуализацию DDTv...

P.S. DDTv с 2011 года умеет следующее (на примере ALU для 3niti alpha):
Code:
./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...

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


07 Mar 2015 17:35
Profile WWW
Fanat
User avatar

Joined: 18 Nov 2014 09:17
Posts: 52
Location: Отсюда
Reply with quote
Похожий продукт (только для двоичности) - это Logic Friday. http://sontrak.com/downloads.html
Программка генерит из таблички значений либо из уравнения схему логических элементов.
Возможно, есть смысл взять оттуда библиотеку визуализации.
Пока не умеет переставлять выводы на блоках и оптимизировать расположение,
в результате результат выглядит слегка запутанно.


17 Mar 2015 01:49
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
JeNNeR wrote:
Похожий продукт (только для двоичности) - это Logic Friday. http://sontrak.com/downloads.html
Программка генерит из таблички значений либо из уравнения схему логических элементов.
Возможно, есть смысл взять оттуда библиотеку визуализации.
Пока не умеет переставлять выводы на блоках и оптимизировать расположение,
в результате результат выглядит слегка запутанно.

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

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

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

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


17 Mar 2015 08:21
Profile WWW
Fanat
User avatar

Joined: 18 Nov 2014 09:17
Posts: 52
Location: Отсюда
Reply with quote
Он при визуализации не умеет их менять местами, поэтому очень часто к элементу снизу включен верхний контакт, а сверху включен нижний, а линии идут крест-накрест.


Attachments:
Безымянный.png
Безымянный.png [ 14.66 KiB | Viewed 19030 times ]
19 Mar 2015 04:32
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22606
Location: Silicon Valley
Reply with quote
Поисследовал всё, что мною наделано в DDT - есть проблема: хоть там и присутствует элемент с памятью MEM, однако ни одной схемы с MEM я так и не нагородил, т.к. в-целом существующий DDT не рассчитан на генерацию схем с памятью (и по сути на симуляцию тоже). Если расположить два мультиплексора друг за другом и связать обратной связью, то запоминания не произойдёт, т.к. все переменные живут только в пределах одного шага. Чтобы запоминание таки произошло, каждую временную переменную (как собственно все выходы, а может и входы), надо хранить между шагами симуляции - тогда можно будет запоминать значения на обратных связях (и на обрывах, если вход отрывается). Таким образом каждый блок получает память, выделяемую из внешнего массива троичных значений - после этого необходимость в MEM на низком уровне отпадёт, т.к. его можно будет построить на двух мультиплексорах, связанных обратной связью...

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


19 Mar 2015 13:07
Profile WWW
Fanat
User avatar

Joined: 18 Nov 2014 09:17
Posts: 52
Location: Отсюда
Reply with quote
Я в SAT это лечил путём изобретения «псевдовыводов».
Например, надо было сохранять состояние двух битов (1 трита) -
1. создал две дополнительные выходные и две дополнительные входные (заодно получил грабли в виде того, что нашел жесткое ограничение по количеству входных),
2. описал в километровой табличке состояний все возможные комбинации входных и выходных (соответственно табличка увеличивалась в 2^4=16 раз)...
3. а после создания схемы просто соединил входные и выходные между собой. (в Пайнте) :)


Attachments:
RS_2BTriLATCH.png
RS_2BTriLATCH.png [ 9.83 KiB | Viewed 13918 times ]
19 Mar 2015 13:18
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 26 posts ]  Go to page 1, 2  Next

Who is online

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