1

私はJavaでプロセッサシミュレータを書いていますが、制御信号は面倒ではありません。以下のようなロジックを生成するツールはありますか？

バイナリロジック：

input[0]: 00001
input[1]: 00000
input[2]: 00010
input[3]: 00011

出力：

if(input.subString(0,3) == "000") 
    //do something;

基本的に、出力は入力の共通部分を見つけます。上記の例では、「000で始まるものはすべて何かを実行します」と言っています。00000, 00001, 00010, 00011

最適化はk-mapに似ていますが、入力が100個あり、手動で最適化するのは実際的ではありません。

上記の私の例とは関係のないk-mapの例を次に示します。

kmapの例

出力はJava構文である必要はありません。単純化された論理ステートメントであれば、

4

1 に答える 1

1

N長さビット (約 100)の文字列の大きなセットがあり、Nこれらの文字列だけに一致する単純な論理式が必要ですか?

Kernaugh マップを作成するプログラムを作成してみてください。面白い練習になるでしょう。Kernaugh マップについてはあまり覚えていませんが、行と列のラベルはグレー コードを使用して配置されていると思います。

または、手作りの Kernaugh マップで問題を扱いやすくすることもできます。各文字列について、それらすべてに共通するビットを見つけます。次に、人間がマップを作成するための残りのビット位置のリストを出力します。

Python コードのビット:

str_len = 5
strs = [
     [0,0,0,0,1],
     [0,0,0,0,0],
     [0,0,0,1,0],
     [0,0,0,1,1],
]
for i in range(str_len):
    if all([x[i] for x in strs]):
        print 'Bit %d is 1' % i
    elif not any([x[i] for x in strs]):
        print 'Bit %d is 0' % i
    else:
        print 'Bit %d is contingent' % i

Bその時点で、残りの偶発ビットをエンコードする方法を考えてみることができます。この例では、たまたますべてのケースがカバーされています (そして、それを特別なケースとして検出できます。たとえばN = 2^B)。

偶発ビットの式を見つけるためのブルート フォース アルゴリズムは次のようになります。

  1. 次の偶発ビットを選択しますi。
  2. S を S0 (ビットi= 0 のサブセット) と S1 (ビットi= 1 のサブセット) に分割します。
  3. S0 と S1 の式 f0 と f1 をそれぞれ再帰的に見つけます。
  4. S の式は です(~b[i] & f0) | (b[i] & f1)。

いくつかの最適化があります。簡単なのは、S0 または S1 が空の場合です。結果の式の分岐を省略します。もう 1 つは、すべての可能な組み合わせがセット内にある場合です (上記の例と同様)。その場合、式はビットを参照する必要はありません。最も難しいのは、入力されたビットを反復するための適切な順序を見つけることです。単純に順序どおりに行うと、最適とは言えない式になる可能性があります。

実際、上記の最初の提案をスキップして、これをすべてのビットで実行できます。常に 1 または 0 であるビットは、S0 または S1 が空の単純なケースを生成します。

このかなり厄介な Python コードは、いくつかの最適化を行ってアルゴリズムを実行します。 注：あまりテストされておらず、必ずしも最適な出力が得られるとは限りません!

def get_formula(S, i=0):
    # Special case where it's an empty set -- return a tautology
    if len(S) == 0:
        return '1'

    remaining_bits = len(S[0]) - i

    # Special case where no bits are left
    if remaining_bits <= 0:
        return '1'

    # Partition the set
    S0 = filter(lambda x: x[i] == 0, S)
    S1 = filter(lambda x: x[i] == 1, S)

    f0 = get_formula(S0, i+1)
    f1 = get_formula(S1, i+1)

    # Special cases where one subset is empty
    # Also special case for subformula being tautology
    if len(S1) == 0:
        if f0 == '1':
            return '~b[%d]' % i
        return '~b[%d] & (%s)' % (i, f0)
    if len(S0) == 0:
        if f1 == '1':
            return 'b[%d]' % i
        return 'b[%d] & (%s)' % (i, f1)

    # Special cases where one or both subformulas was a tautology
    if f0 == '1' and f1 == '1':
        return '1'
    if f0 == '1':
        return '~b[%d] | b[%d] & (%s)' % (i, i, f1)
    if f1 == '1':
        return '~b[%d] & (%s) | b[%d]' % (i, f0, 1)

    # General case
    return '~b[%d] & (%s) | b[%d] & (%s)' % (i, f0, i, f1)


strs = [
     [0,0,0,0,1],
     [0,0,0,0,0],
     [0,0,0,1,0],
     [0,0,0,1,1],
]

print get_formula(strs)

最後に、このコードがより最適な式を見つけられるようにする 1 つの方法Sは、常に 0 または常に 1 であるビットを先にスキャンし、それらを早期に処理することだと思います。各サブセットの残りの偶発ビットは、深くネストされたサブフォーミュラにプッシュされ、処理が早すぎる場合よりも冗長なフォーミュラが形成されなくなります。これは事実上、カーノー マップ スタイルの構築をシミュレートすると思います。各ステップで、常に 0 または常に 1 のビットのセットがマップ上の四角形を定義します。そのセットを見つけて、それらをすべて一度に処理し (たとえば、コンパクトな数式として~b[0] & ~b[1] & ~b[2])、残りのビットを再帰します。を使用して順番に処理するのではなく、どのビット位置が既に処理されているかを追跡する必要がありますi。

(実際、考えてみると、最適な式を得るには、一度に多数の相関ビットを選択してスマートに分割する必要もあります。興味深い問題です...)

于 2012-05-22T22:48:31.500 に答える