12

私はいくつかの出力ラインに N から M のデコーダーを持つ小さな 8 ビット プロセッサを持っています。出力への唯一のインターフェイスは状態変更であり、リードバックはありません。

デバイスは、発生するイベントを迅速に (ただしランダムに) カウントし、このカウントを「単一ビット変更」コードとして別のデバイスに提供する必要があります。出力ピンは別のデバイスによって並行して読み取られ、他のデバイスが決定するのと同じくらい速くまたは控えめに読み取られる可能性があるため、カウントが必要です。

標準の Binary Reflective Gray コードを使用する必要はありません。単一ビット変更コードを使用できます。

ただし、次のビットを追跡して効率的に変更できるようにしたいと考えています。

私は「LowestBitSet」命令を持っていません.4つの8ビットレジスタに設定された最下位ビットを見つけるのはサイクルを消費するので、この「一般的な」アプローチを使用することはできません: 

  Keep binary counter A
  Find B as A XOR (A+1)
  Bit to change is LowestBitSet in B

できるだけ少ないメモリとレジスタでこれを計算したいのですが、大きなルックアップ テーブルにはメモリが制限されすぎています。サイクル タイムは、より重要な要素です。

アルゴリズムに関する提案はありますか?

4

8 に答える 8

1

Knuth、DonaldEの10ページの「AlgorithmL」 。「すべてのnタプルの生成」。The Art of Computer Programming、Volume 4A：Enumeration and Backtracking、pre-fascicle 2a、October 15、2004は理想的なようです。ステップL4は、デバイスの「change_state（j）」になります。

于 2011-01-10T19:19:43.770 に答える
1

LowestBitSet(A ^ (A+1))IBM で働いていない限り、常に 0 です。HighestBitSet()とほぼ同じ意味だと思いますlog_2()。

AShelly によってリンクされたハックの直前にあるビットいじりハックは、8 ビット マイクロでははるかに実現可能です。

これにより、元のアルゴリズムがかなり実用的になり、{ 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, ... }.

グレーコードを生成する別のシーケンスに変更する可能性については、計算を簡単にするために、非常に興味深いですが、私は何も思いつきませんでした.

于 2013-06-29T00:23:19.293 に答える
1

グレイ コードを計算して xor する必要はありません。カウンター自体を使用するだけで、256 要素のルックアップ テーブルを使用して末尾のゼロの数をカウントできます。このような：

unsigned char bit_change(unsigned char counter[4]) {
  static const unsigned char ones[] = {
    0,0,0,1,0,1,1,2,0,1,1,2,1,2,2,3,0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,    
  };

  unsigned char i;
  for (i = 0; i < 4; i++) {
    unsigned char x = counter[i];
    if (x) {
      x ^= x - 1;
      return 8 * i + ones[x];
    }
  }
}

ループを展開すると、これは最大で 2 回の追加、1 回の xor、および 5 回のロードになります (ただし、ほとんどの場合はそれより少なくなります)。テーブルに 256 バイトがない場合は、ニブルに対して同じ戦略を使用できます。

于 2011-01-11T12:42:06.703 に答える
0

Binary Reflective Gray Codeの場合、コード N を計算する効率的な方法については、この回答
を参照してください 。変更するビットのみが設定されている値を取得するには、前のコードと XOR します。
次に、この Bit Twiddling Hack (「v が 2 のべき乗」の場合) を使用して、3 つの操作と 32 エントリのテーブルだけでビット インデックスを見つけることができます。

擬似コードは次のようなものです。

  n = lastCode = 0
  increment:
     n+=1
     newCode = GrayCode(n)
     delta = newCode XOR oldCode
     bitToToggle = BitIndex(delta)
     old code = new code
     GOTO increment;
于 2011-01-10T19:34:51.897 に答える