2フェーズNAND回路シミュレータ

状態を持つことでフィードバック演算も可能であろうという理屈で実装されています。

まだテスト段階ですが論理ゲートをプログラムシミュレーションしようとしている人たちの為の何らかのヒントになればと思って公開します。

まだ見落としがあるかも知れませんがシミュレーション自体は多分それなりに動いていると思います。（多分）

実際に何かしらに活かすにはまだ考えないといけない部分は多いかも。

今回は手軽だという理由でPythonで実装しましたが、実際のところ言語は何でも構いません。(大切な部分は理屈のみなので)

コードを読むためのいくつかのポイントだけ（Pythonの方言っぽいの）書き出しておきます。

A = B // C
A = int(B / C) と同等

1 ^ (A & B) #ただしA、Bは1bitのみ利用の場合
!(A & B) と同等

A = { hoge: (C, D)}
dict型といってJSONデータとほぼほぼ同等のもので要するに連想配列的な。<br>
(C, D)のようにtuple型が格納されているのは、要するに配列。<br>
tupleは変更不可の配列だと思っておけば大体大丈夫。

ルール

リンクデータは、ゲートのインデックス: (ソースAのインデックス, ソースBのインデックス, ....) となっている。理屈ではいくつでも入力できます。
ゲートは2bitで構成されており、現在、次回の値を持っています。

計算は常に、現在の値を参照し、計算結果は次回の値へ反映します。

二つの状態を持っているので2フェーズ。

一通り計算が終わったらフェーズを入れ替えて計算…を適当なステップ数繰り返すことで論理演算の答えが出ます。

コード

import math

NUMBER_OF_GATES = 12
MEMORY_SIZE = math.ceil(NUMBER_OF_GATES / 2)

class Logic:

    def __init__(self):
        self.gate_array = bytearray([0] * MEMORY_SIZE)
        self.links = {}
        self.phase = 0
        self.counter = 0


    def nextPhase(self):
        """
        Phase transition
        """
        self.phase = (self.phase + 1) % 2


    def getIndex(self, target, phase=0):
        """
        Get the byte index and bit index of target
        """
        return target // 4, (target % 4) * 2 + ((self.phase + phase) % 2)


    def setbit(self, target, value, phase=0):
        """
        Set the target bit
        """
        yi, bi = self.getIndex(target, phase)
        buf = self.gate_array[yi] & (0xff & (0xff ^ (1 << bi)))
        self.gate_array[yi] = buf | ((1 & value) << bi)


    def getbit(self, target, phase=0):
        """
        Get a bit of the target
        """
        yi, bi = self.getIndex(target, phase)
        buf = self.gate_array[yi] & (1 << bi)
        return buf >> bi


    def setValue(self, target, value):
        """
        Set bits in both phases of the target
        """
        for i in range(2):
            self.setbit(target, value, i)


    def process(self):
        """
        Simulate the circuit for one phase
        """
        for target in self.links.keys():
            for idx, src in enumerate(self.links[target]):
                if idx == 0:
                    calc = self.getbit(src)
                else:
                    calc &= self.getbit(src)
                self.setbit(target, (1 ^ calc), 1)


    def monitor(self, bitnum=8):
        """
        Monitor the contents of memory
        Argument: number of bits
        """
        print("%4d : " % self.counter, end="")
        for target in range(bitnum):
            print("%d " % self.getbit(target, 0), end="")
        print(" ", end="")
        for target in range(bitnum):
            print("%d " % self.getbit(target, 1), end="")
        print()
        self.counter += 1


def run(logic, steps=20):
    """
    Execute circuit simulation for the number of steps.
    (*) Reason why the simulation does not end in one step
    This is due to the transmission delay of the logic circuit.
    """
    for i in range(steps):
        l.monitor(NUMBER_OF_GATES)
        logic.process()
        logic.nextPhase()
    l.monitor(NUMBER_OF_GATES)


if __name__ == "__main__":
    l = Logic()

    """
     Normal order
    """
    l.links = {
            3: (0, 1),
            4: (0, 3),
            5: (1, 3),
            6: (4, 5),
            7: (2, 6),
            8: (6, 7),
            9: (2, 7),
            10: (8, 9),
            11: (3, 7),
            }
    ansBit = 10
    ansCarry = 11

    """
     Reverse order
    """
    # l.links = {
    #         3: (5, 6),
    #         4: (7, 11),
    #         5: (8, 7),
    #         6: (7, 2),
    #         7: (2, 8),
    #         8: (9, 10),
    #         9: (0, 11),
    #         10: (11, 1),
    #         11: (0, 1),
    #         }
    # ansBit = 3
    # ansCarry = 4

    """
     3 port input test
    """
    # l.links = {
    #         3: (0, 1, 2),
    #         }
    # ansBit = 3
    # ansCarry = None

    """
    Initial value set
    0: A
    1: B
    2: Carry or C
    """
    l.setValue(0, 1)
    l.setValue(1, 0)
    l.setValue(2, 0)
    run(l, steps=6)
    print("bit   : ", l.getbit(ansBit))
    if ansCarry != None:
        print("carry : ", l.getbit(ansCarry))

一応なんとなく解説

サンプルの回路データとして NANDゲートのみで構成した全加算器(via wikipedia) を二種類、頭から演算するものと答えの出る側から計算するもの。

NANDゲートのテストとして3入力するもの。

以上3つが含まれています。

論理ゲートの回路図を元に、それぞれのNANDゲートに番号を振り、どのゲートはどこのゲートから値を受け取るのか。というデータにしたものがリンクデータです。

Normal order

Reverse order

フェーズを設けることでどんな順番で演算をしても同じ答えになる（場合によってはステップ数は変わるかも）のを確認してみてください。

この手のプログラムらしからぬ部分として伝達遅延がおきます。ある意味リアルです。

適当なステップ数 process を実行して答えが出る感じで動かしてください。（恐らく多段に組んだNANDゲートの深さがステップ数と同等かと思います）

実際の運用としてはハードウェア上で無限ループにて process を実行することを想定しています。

課題

リンクデータの持ち方がリッチすぎる。

というのがとりあえずの課題。少なくともdictで実装するなんていうリッチなものはハードウェアにおいては許されないというかメモリがもったいないのでもっと良い方法を考える。

制限は設けたくないけど柔軟にすると無駄にデータを食いがちというところが悩ましいです。

(制限を設けてもデータを小さくするのはとても難しい)

目標としては32kゲートくらいの回路を作れるようなものになったらいいですねー。とか。

※実行速度、かなり遅いでしょうけどね。

仮に、最大64kゲート作れるようにするという前提のもと64kbyteのメモリを利用したとして、

1つのゲートには2つのゲートからの出力以上は受け付けないという制限を設けるとインデックスと参照2つのゲートのデータで48bitのデータが1つのゲートに付随します。つまり、1ゲートあたり50bit。約7byteを一つのゲートに消費するという計算です。
これで実装した場合メモリ上に約10kゲートしか実装できません。

とても人間的とは思えないリンク情報の記述

作ってる本人すらパット見て分からないデータです、こんなのが良いはずはない。

一応落ち着いて紙に書いてゆけば復元可能ではあるのですが、即席ではとてもデータが作れないので紙の上とかにひたすら数字書いて眺めながら間違えてないか確認しつつリンク情報をつくる感じです。

とてもしんどい。

回路の使いまわしが困難

これは前述の記述の問題にもつながるのですが、たとえば今回の全加算器の桁を8桁にした場合、もう正直やりたくないです。

やりたくないのでテストしてません。

大問題です。

ラダー表とかで記述して小さなブロックごとに解決してゆくような仕組みが必要かもしれません。

このあたりを解決できると嬉しいですね。