Проектирование троичных элементов (4) - пробуем CMOS-ключи

[Shaos]

Выложил то что уже есть из кода: http://nedopc.cvs.sourceforge.net/viewv ... c/src/ddt/

Алгоритм заработал! Пока поддерживается только задание таблицы истинности как аргумента для ddtc. Ограничился пока 6 входами и 12 выходами (но в-принципе можно и увеличить).

[Shaos]

Выложил то что уже есть из кода: http://nedopc.cvs.sourceforge.net/viewv ... c/src/ddt/

Алгоритм заработал! Пока поддерживается только задание таблицы истинности как аргумента для ddtc. Ограничился пока 6 входами и 12 выходами (но в-принципе можно и увеличить).

Алгоритм пока не распознаёт оптимизации на уровне второго и далее входов - например таблица истинности NNNOOOPPP будет преобразована в MUX(i2,'N','O','P') вместо i2. Но я над этим ещё буду работать. MIN и MAX также не распознаются (сложновато это).

[Shaos]

Выложил то что уже есть из кода: http://nedopc.cvs.sourceforge.net/viewv ... c/src/ddt/

Алгоритм заработал! Пока поддерживается только задание таблицы истинности как аргумента для ddtc. Ограничился пока 6 входами и 12 выходами (но в-принципе можно и увеличить).

Алгоритм пока не распознаёт оптимизации на уровне второго и далее входов - например таблица истинности NNNOOOPPP будет преобразована в MUX(i2,'N','O','P') вместо i2. Но я над этим ещё буду работать. MIN и MAX также не распознаются (сложновато это).

ОК, научил программу по запросу NNNOOOPPP генерировать вот такую функцию:

Code: Select all

int ddt_(int f, DDT i1, DDT i2, DDT* o1)
{
	if(o1) *o1 = i2;
	return 0;
}

а по вот такому:
./ddtc NNNOOOPPPNNNOOOPPPNOPNOPNOP e21r
./ddtc NNNOOOPPPNOPNOPNOPNOPNOPNOP e12r
программ изобретает E12 и E21 наоборот (входы снизу вверх нумеруются):

Code: Select all

int ddt_e21r(int f, DDT i1, DDT i2, DDT i3, DDT* o1)
{
	DDT r1;
	int e1;
	e1 = ddt_e21(f,i3,i2,i1,&r1);
	if(e1 < 0) return e1;
	if(o1) *o1 = r1;
	return e1;
}

int ddt_e12r(int f, DDT i1, DDT i2, DDT i3, DDT* o1)
{
	DDT r1;
	int e1;
	e1 = ddt_e12(f,i3,i2,i1,&r1);
	if(e1 < 0) return e1;
	if(o1) *o1 = r1;
	return e1;
}

Правда если попытаться сгенерить по таблице истинности, где входы идут в правильном порядке - программа запутается и нагенерит слишком много (хотя и правильного), т.е. для получения оптимального варианта надо попереставлять входы...

[Shaos]

вот сгенерённый MIN (NNNNOONOP):

Code: Select all

int ddt_(int f, DDT i1, DDT i2, DDT* o1)
{
	DDT r1,r2;
	int e1,e2;
	e1 = ddt_blp(f,i1,&r1);
	if(e1 < 0) return e1;
	e2 = ddt_mux(f,i2,'N',r1,i1,&r2);
	if(e2 < 0) return e2;
	if(o1) *o1 = r2;
	return e1+e2;
}

и сгенерённый MAX (NOPOOPPPP):

Code: Select all

int ddt_(int f, DDT i1, DDT i2, DDT* o1)
{
	DDT r1,r2;
	int e1,e2;
	e1 = ddt_bln(f,i1,&r1);
	if(e1 < 0) return e1;
	e2 = ddt_mux(f,i2,i1,r1,'P',&r2);
	if(e2 < 0) return e2;
	if(o1) *o1 = r2;
	return e1+e2;
}

Также поставил максимальное количество входов 7, а максимальное количество выходов - 21:

http://nedopc.cvs.sourceforge.net/viewv ... iew=markup

P.S. На самом деле больше 6 входов делать пока нельзя - позже поправлю...

[Shaos]

Сгенерируем троичный полусумматор:

./ddtc PNONOPOPN,NOOOOOOOP

Code: Select all

/* Generated by ddtc v0.1
   See www.ternary.info */

#include "ddt.h"

int ddt_(int f, DDT i1, DDT i2, DDT* o1, DDT* o2)
{
	DDT r1,r2,r3,r4,r5,r6;
	int e1,e2,e3,e4,e5,e6;
	e1 = ddt_rdn(f,i1,&r1);
	if(e1 < 0) return e1;
	e2 = ddt_rup(f,i1,&r2);
	if(e2 < 0) return e2;
	e3 = ddt_mux(f,i2,r1,i1,r2,&r3);
	if(e3 < 0) return e3;
	e4 = ddt_blp(f,i1,&r4);
	if(e4 < 0) return e4;
	e5 = ddt_bln(f,i1,&r5);
	if(e5 < 0) return e5;
	e6 = ddt_mux(f,i2,r4,'O',r5,&r6);
	if(e6 < 0) return e6;
	if(o1) *o1 = r3;
	if(o2) *o2 = r6;
	return e1+e2+e3+e4+e5+e6;
}

тест-программа:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include "ddt.h"
#include "ddt_.c"

char ax[] = "NOPNOPNOP";
char ay[] = "NNNOOOPPP";

int main()
{
 int i,t;
 DDT r,rr[9];

 printf("\nE12:%i E21:%i (MUX:%i,NOT:%i,BLP:%i,BLN:%i,RUP:%i,RDN:%i)\n\n",
   ddt_(DDT_E12,0,0,NULL,NULL),ddt_(DDT_E21,0,0,NULL,NULL),
   ddt_(DDT_MUX,0,0,NULL,NULL),ddt_(DDT_NOT,0,0,NULL,NULL),
   ddt_(DDT_BLP,0,0,NULL,NULL),ddt_(DDT_BLN,0,0,NULL,NULL),
   ddt_(DDT_RUP,0,0,NULL,NULL),ddt_(DDT_RDN,0,0,NULL,NULL));

 printf("\| N O P |\n----------\n");
 for(i=0;i<9;i++)
 {
   t = ddt_(DDT_SIM,ax[i],ay[i],&r,&rr[i]);
   if(!(i%3)) printf("%c|",ay[i]);
   printf(" %c",r);
   if((i%3)==2) printf(" |\n");
 }  
 printf("----------\n\n");

 printf("\| N O P |\n----------\n");
 for(i=0;i<9;i++)
 {
   if(!(i%3)) printf("%c|",ay[i]);
   printf(" %c",rr[i]);
   if((i%3)==2) printf(" |\n");
 }  
 printf("----------\n\n");

 printf("dt=%i\n",t);

 return 0;
}

результат её запуска:

Code: Select all

E12:5 E21:5 (MUX:4,NOT:0,BLP:1,BLN:1,RUP:1,RDN:1)

\| N O P |
----------
N| P N O |
O| N O P |
P| O P N |
----------

\| N O P |
----------
N| N O O |
O| O O O |
P| O O P |
----------

dt=10

Как видно программа насчитала 5 блоков E12 и 5 блоков E21, т.е. всего потребуется 6 микросхем DG403 (3 подключены как 2xE12 и 3 подключены как 2xE21).

[Shaos]

Вот первый релиз под винды:

http://www.nedopc.org/ternary/ddt_0_1_win.zip (59K)

Бета-тестеры - вперёд!

[Shaos]

Добавил возможность заводить таблицу соответствия через файл с использованием символа X (зарелизю завтра как v0.2), например вот так можно задать логику работы MUX (текстовый файл MUX.ddt):

Code: Select all

NNXX=N
NOXX=O
NPXX=P
OXNX=N
OXOX=O
OXPX=P
PXXN=N
PXXO=O
PXXP=P

Запуск ddtc MUX.ddt сгенерит вот такую функцию:

Code: Select all

int ddt_MUX(int f, DDT i1, DDT i2, DDT i3, DDT i4, DDT* o1)
{
	DDT r1;
	int e1;
	e1 = ddt_mux(f,i4,i3,i2,i1,&r1);
	if(e1 < 0) return e1;
	if(o1) *o1 = r1;
	return e1;
}

т.е. тот же MUX, но у которого аргументы идут в обратном порядке, значит в таблице истинности самый левый трит является самым нижним на схеме (т.е. младшие триты идут первыми в смысле нумерации).

[Shaos]

Для того чтобы представлять для чего сколько нужно корпусов при таком подходе, привожу конкретные числа:
- NOT требует 2 микросхемы (точнее 50% от 2 микросхем - см. нижнюю часть второй схемы),
- MIN или MAX требуют по 2 микросхемы (точнее 75% от них),
- полусумматор требует 6 микросхем (точнее 83% от них),
- полный сумматор - ориентировочно 12 микросхем,
- троично-двоичный преобразователь 2t4b - ориентировочно 8 микросхем,
- троично-двоичный преобразователь 3t5b - ориентировочно 21 микросхема (что говорит о том, что троично-двоичные преобразователи экономичнее делать на основе двоичных ROM или PAL).

Подтвердил тестом однотритный полный сумматор 1+1+1=1+1 - вышло ровно 12 корпусов DG403:

Code: Select all

// Number of E12 in FUN is 12
// Number of E21 in FUN is 12
// Number of MUX in FUN is 10
// Number of NOT in FUN is 0
// Number of BLP in FUN is 1
// Number of BLN in FUN is 1
// Number of RDN in FUN is 1
// Number of RUP in FUN is 1

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 e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12,e13,e14;
	e1 = ddt_rup(f,i1,&r1);
	if(e1 < 0) return e1;
	e2 = ddt_rdn(f,i1,&r2);
	if(e2 < 0) return e2;
	e3 = ddt_mux(f,i2,r1,r2,i1,&r3);
	if(e3 < 0) return e3;
	e4 = ddt_mux(f,i2,r2,i1,r1,&r4);
	if(e4 < 0) return e4;
	e5 = ddt_mux(f,i2,i1,r1,r2,&r5);
	if(e5 < 0) return e5;
	e6 = ddt_mux(f,i3,r3,r4,r5,&r6);
	if(e6 < 0) return e6;
	e7 = ddt_e21(f,i1,'N','O',&r7);
	if(e7 < 0) return e7;
	e8 = ddt_blp(f,i1,&r8);
	if(e8 < 0) return e8;
	e9 = ddt_bln(f,i1,&r9);
	if(e9 < 0) return e9;
	e10 = ddt_e12(f,i1,'O','P',&r10);
	if(e10 < 0) return e10;
	e11 = ddt_mux(f,i2,r7,r8,'O',&r11);
	if(e11 < 0) return e11;
	e12 = ddt_mux(f,i2,r8,'O',r9,&r12);
	if(e12 < 0) return e12;
	e13 = ddt_mux(f,i2,'O',r9,r10,&r13);
	if(e13 < 0) return e13;
	e14 = ddt_mux(f,i3,r11,r12,r13,&r14);
	if(e14 < 0) return e14;
	if(o1) *o1 = r6;
	if(o2) *o2 = r14;
	return e1+e2+e3+e4+e5+e6+e7+e8+e9+e10+e11+e12+e13+e14;
}

Также сгенерировал таблицу значений для ALU на подобие 3niti alpha - для трёхтритных аргументов, причём покрыл только 3 операции - RLA (сдвиг влево через перенос), ADD (сложение с переносом), RRA (сдвиг вправо через перенос). Получилось 8 трит на входе (1 трит операции, 1 трит переноса и два 3-тритных аргумента) и 4 трита на выходе (1 трит переноса и один 3-тритный результат. Сдвиги сами по себе сгенерировались в 4 мукса, а вот добавление сложения 3+3+1=1+4 увеличило размер сгенерированной схемы до 174 корпусов!

Code: Select all

E12:174 E21:174 (MUX:153,NOT:0,BLP:1,BLN:1,RUP:1,RDN:1)

Можно попробовать попереставлять входы (всего то 40000 вариантов ; ) - может как-то удасться добиться более компактной реализации...

[Shaos]

Также сгенерировал таблицу значений для ALU на подобие 3niti alpha - для трёхтритных аргументов, причём покрыл только 3 операции - RLA (сдвиг влево через перенос), ADD (сложение с переносом), RRA (сдвиг вправо через перенос). Получилось 8 трит на входе (1 трит операции, 1 трит переноса и два 3-тритных аргумента) и 4 трита на выходе (1 трит переноса и один 3-тритный результат. Сдвиги сами по себе сгенерировались в 4 мукса, а вот добавление сложения 3+3+1=1+4 увеличило размер сгенерированной схемы до 174 корпусов!

Code: Select all

E12:174 E21:174 (MUX:153,NOT:0,BLP:1,BLN:1,RUP:1,RDN:1)

Можно попробовать попереставлять входы (всего то 40000 вариантов ; ) - может как-то удасться добиться более компактной реализации...

Попереставлял - выявил несколько оптимальных комбинаций входов, при которых получаем вот что:

Code: Select all

E12:53 E21:53 (MUX:41,NOT:0,BLP:1,BLN:1,RUP:1,RDN:1)

т.е. 54 корпуса DG403 (округляем до ближайшего чётного числа), что уже вобщем-то неплохо!

Первоначальное расположение (неудачное):

i1 = B0
i2 = B1
i3 = B2
i4 = A0
i5 = A1
i6 = A2
i7 = C
i8 = O

Удачное расположение:

i1 = B2
i2 = A2
i3 = B1
i4 = A1
i5 = B0
i6 = A0
i7 = C
i8 = O

А также несколько других, но где также соответствующие разряды A и B находятся рядом. Также удалось обнаружить наихудший вариант расположения - аж 606 корпусов получалось!

Также перебор выявил, что некоторые вариации приводят к ошибке программы - буду разбираться...

[Shaos]

Также перебор выявил, что некоторые вариации приводят к ошибке программы - буду разбираться...

Это исправил! Также щас работаю над убиранием ограничений на количество входов и выходов - всё будет динамическим. Из ограничений, связанных с внутренним форматом представления, пока только остаётся 999 как максимальный номер подключаемого нода в первом уровне (количество функций теоретически может быть больше 999, но не в первом уровне сразу после входов) и 99 как максимальный номер входа (и то, и другое сохраняется в трёх символах, но второе ещё и с минусом).

[Shaos]

Вот второй релиз под винды:

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

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

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

[Shaos]

Попереставлял - выявил несколько оптимальных комбинаций входов, при которых получаем вот что:

Code: Select all

E12:53 E21:53 (MUX:41,NOT:0,BLP:1,BLN:1,RUP:1,RDN:1)

т.е. 54 корпуса DG403 (округляем до ближайшего чётного числа), что уже вобщем-то неплохо!

Первоначальное расположение (неудачное):

i1 = B0
i2 = B1
i3 = B2
i4 = A0
i5 = A1
i6 = A2
i7 = C
i8 = O

Удачное расположение:

i1 = B2
i2 = A2
i3 = B1
i4 = A1
i5 = B0
i6 = A0
i7 = C
i8 = O

А также несколько других, но где также соответствующие разряды A и B находятся рядом. Также удалось обнаружить наихудший вариант расположения - аж 606 корпусов получалось!

Также перебор выявил, что некоторые вариации приводят к ошибке программы - буду разбираться...

Заметил, что усложнение задания путём добавления новых функций в схему (например создание ALU которое может делать много вещей в зависимости от кода операции) ведёт к неоптимальному результату - оно и понятно - разные функции могут требовать разного расположения входов для лучшего результата. Поэтому генерировать с помощью DDT надо достаточно мелкие задачи (как например 3-х разрядный сумматор), а более сложные надо составлять вручную из уже сгенерённых блоков...

[Shaos]

Заметил, что усложнение задания путём добавления новых функций в схему (например создание ALU которое может делать много вещей в зависимости от кода операции) ведёт к неоптимальному результату - оно и понятно - разные функции могут требовать разного расположения входов для лучшего результата. Поэтому генерировать с помощью DDT надо достаточно мелкие задачи (как например 3-х разрядный сумматор), а более сложные надо составлять вручную из уже сгенерённых блоков...

Неа - трёхразрядный сумматор, вручную собранный из одноразрядных полных троичных сумматоров, сгенерённых в DDT, получился компактнее:

Code: Select all

int ddt_sum3m(int f, DDT i1, DDT i2, DDT i3, DDT i4, DDT i5, DDT i6, DDT i7, DDT* o1, DDT* o2, DDT* o3, DDT* o4)
{
 int f1,f2,f3;
 DDT r1,r2,r3,r4,r5,r6;
 f1 = ddt_sum(f,i7,i6,i5,&r1,&r2);
 if(f1<0) return f1;
 f2 = ddt_sum(f,r2,i4,i3,&r3,&r4);
 if(f2<0) return f2;
 f3 = ddt_sum(f,r4,i2,i1,&r5,&r6);
 if(f3<0) return f3;
 if(o1) *o1 = r1;
 if(o2) *o2 = r3;
 if(o3) *o3 = r5;
 if(o4) *o4 = r6;
 return f1+f2+f3;
}

1) E12:49 E21:49 (MUX:37,NOT:0,BLP:1,BLN:1,RUP:3,RDN:3)

2) E12:36 E21:36 (MUX:30,NOT:0,BLP:3,BLN:3,RUP:3,RDN:3)

36 корпусов против 50 (сэкономили 28%)

P.S. с другой стороны, автоматически сгенерённая схема должна работать быстрее, т.к. задержка там не должна превышать кол-ва входов (т.е. не более 7), а в ручной схеме - как минимум 9 (три сумматора с задержкой 3 подключены последовательно). т.е. потеряли по быстродействию те же 28% процентов!

P.P.S. надо завизуализировать схему и посмотреть на неё внимательно - может быть DDT изобрёл троичный параллельный перенос?...

[Shaos]

Прикинул на бумаге, что вторая схема подключения DG403 позволяет таким образом покрыть любые троичные функции с любым количеством аргументов, причём это дело можно автоматизировать - вплоть до автоматической разводки платы по таблицам истинности реализуемых функций!

Для того чтобы представлять для чего сколько нужно корпусов при таком подходе, привожу конкретные числа:
- NOT требует 2 микросхемы (точнее 50% от 2 микросхем - см. нижнюю часть второй схемы),
- MIN или MAX требуют по 2 микросхемы (точнее 75% от них),
- полусумматор требует 6 микросхем (точнее 83% от них),
- полный сумматор - ориентировочно 12 микросхем,
- троично-двоичный преобразователь 2t4b - ориентировочно 8 микросхем,
- троично-двоичный преобразователь 3t5b - ориентировочно 21 микросхема (что говорит о том, что троично-двоичные преобразователи экономичнее делать на основе двоичных ROM или PAL).

- схема определения знака трёхразрядного троичного числа - 2 микросхемы
- схема сдвига влево (RLA) и вправо (RRA) - 4 микросхемы (75% от них)
- унарный трёхразрядный универсальный троичный элемент (OPA) - 4 микросхемы (75% от них)
- бинарный трёхразрядный универсальный троичный элемент (OPB) - 12 микросхем

Теперь всё готово, чтобы собирать из отдельных операций АЛУ 3niti alpha

[Mac Buster]

- схема определения знака трёхразрядного троичного числа - 2 микросхемы
- схема сдвига влево (RLA) и вправо (RRA) - 4 микросхемы (75% от них)
- унарный трёхразрядный универсальный троичный элемент (OPA) - 4 микросхемы (75% от них)
- бинарный трёхразрядный универсальный троичный элемент (OPB) - 12 микросхем

А вот эти остатки (по 25%) не получится использовать для других целей?