トランジスタ回路設計プログラム

Algorithm Electronics

集積回路ができる前はトランジスタが演算素子だったんだってね。その前は真空管、もっと前は歯車か。
ということで、Nビット入力 -> Mビット出力 の対応表が与えられたとき、その回路をトランジスタだけで実装する回路を設計するプログラムを作ってみた。
ここでは、トランジスタは次の2つの演算のみできるものとする。

  1. NOT演算。入力Aの逆論理を出力。（NPNトランジスタのエミッタをGNDに、コレクタを抵抗付きVCCと出力に、ベースを入力につなぐとできる）
  2. 2つの入力A,Bが与えられたとき、A and (not B)を出力。（NPNトランジスタのエミッタをGNDに、コレクタをAと出力に、ベースをBにつなぐとできる）

トランジスタをこの使い方でやると、電圧降下がなくて済むはず（ダイオードでORを実装したりすると、順方向電圧降下のせいでたくさんつないだ時におかしいことになる）。

設計プログラムは以下の通り。

#include <cstdio>
#include <cstdlib>

int N, M, tmp;
unsigned int rsl[10], mask;
unsigned int val[30]; int op1[30], op2[30];
int q1[500], q2[500];

bool find(int vID, int vMax, int qPos)
{
	if(vID==vMax){
		for(int i=0;i<M;i++){
			for(int j=0;j<vID;j++){
				if(rsl[i] == val[j]) goto nex;
			}
			return false;
nex:
			continue;
		}
		return true;
	}

	for(int i=qPos;i<vID*vID;i++){
		op1[vID] = q1[i];
		op2[vID] = q2[i];
		if(q1[i] == q2[i]){
			val[vID] = mask & (~val[q1[i]]);
		}else{
			val[vID] = val[q1[i]] & ~val[q2[i]];
		}

		for(int j=0;j<vID;j++) if(val[j] == val[vID]) goto nex2;

		if(find(vID+1, vMax, i+1)) return true;
nex2:
		continue;
	}
	return false;
}

bool test(int nVal)
{
	int ps = 0;
	for(int i=0;i<nVal;i++){
		for(int j=0;j<i;j++){
			for(int k=0;k<i;k++){
				if(j==i-1||k==i-1){
					q1[ps] = j;
					q2[ps++] = k;
				}
			}
		}
	}
	return find(N, nVal, 0);
}

int main(int argc, char** argv)
{
	int beg = 1;
	if(argc >= 2){
		beg = atoi(argv[1]);
	}
	scanf("%d%d",&N,&M);
	for(int i=0;i<M;i++) rsl[i] = 0;
	for(int i=0;i<(1<<N);i++){
		int t = 0;
		for(int j=0;j<N;j++){
			scanf("%d",&tmp);
			t |= tmp << j;
		}
		for(int k=0;k<M;k++){
			scanf("%d",&tmp);
			rsl[k] |= (unsigned int)tmp << (unsigned int)t;
		}
	}
	
	mask = ((unsigned int)1 << (unsigned int)(1<<N)) - 1;
	for(int i=0;i<N;i++){
		val[i] = 0;
		for(int j=0;j<(1<<N);j++){
			if(j & (1<<i)) val[i] |= (unsigned int)1 << (unsigned int)j;
		}
	}

	for(int i=N+beg;;i++){
		fprintf(stderr, "Testing: %d transistors\n", i-N);
		if(test(i)){
			for(int j=0;j<i;j++){
				if(j<N){
					printf("V[%d] : input\n", j);
				}else{
					if(op1[j]==op2[j]){
						printf("V[%d] : !V[%d]\n", j, op1[j]);
					}else{
						printf("V[%d] : V[%d] && !V[%d]\n", j, op1[j], op2[j]);
					}
				}
			}
			break;
		}
	}
}

2 2
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

こんな感じで対応表を与えると（上は半加算器）、トランジスタ演算だけで対応表を満たすような回路を設計する。といってもただの反復深化の全探査。
元々全加算器をできるだけ少ないトランジスタで作るために作ったプログラムだけど、全加算器の回路を求めようとすると非常に時間かかる（一晩かかった）。全加算器の計算結果は以下のような感じ。トランジスタが１１個必要（半加算器は５個）。

V[0] : input
V[1] : input
V[2] : input
V[3] : !V[0]
V[4] : V[1] && !V[3]
V[5] : V[3] && !V[1]
V[6] : !V[4]
V[7] : V[6] && !V[5]
V[8] : V[2] && !V[7]
V[9] : V[7] && !V[2]
V[10] : !V[9]
V[11] : V[10] && !V[5]
V[12] : V[10] && !V[8]
V[13] : !V[12]

これを見て手計算したら、V[11]が繰り上げ出力、V[13]がその桁の出力らしい。