効率的な整数1次元ディザリング関数？

Question

私は8ビットのマイクロコントローラを搭載したLEDを最近多く使用しています。時には、LEDの明るさを制御するために、パルス幅変調の純粋なソフトウェア実装を使用する必要があります。これは、時間の比率を素早く変化させながら光をオン/オフすることです。これは、私がストロボが目に不快なちらつきを見始めて約5％の明るさにまで落ちるまで素晴らしいです。

PWMをループとして実装すると、0-255の各番号がステップごとに点灯または消灯します。 20の値に設定されたライトは、最初の20回のループでオンになり、次にオフになります。

私はこれらの数字の周りをシャッフルする良い関数を探していますので、0,1,2,3のループを繰り返す代わりに、私のループは可能性のプールから半無作為にサンプリングすることができます。時間の経過に伴う集光度は同じですが、明るさの値が20の光は、一度点灯するのではなく、大部分のループで消灯するのではなく、256回にわたって広がっています。これにより、ループがわずかに遅くなってもちらつき効果が減少します。

8ビットの数値ごとに呼び出されたときに、良好なディザリング機能を使用すると、8ビットの範囲内のすべての数値を返す必要があります。したがって、重複した数字を生成する必要もありません。ランダムではなく、シャッフルしただけです。似たような数字を順番に並べることができない場合は、最善です。各数字の差は、理想的には64〜127桁です。

この制限も興味深いものです。タイムクリティカルなアプリケーションです。加算、減算、ビット単位の演算には任意の1単位時間、乗算コストは​​2単位、除算コストは​​4単位です。フロートは質問から外れており、中間の数で使用される8ビットの倍数ごとにおよそ2倍のコストがかかります。ルックアップテーブルは可能ですが、デバイスの総メモリ容量のおよそ半分を使用します - 高速アルゴリズムは再利用性に最適ですが、良質の低速アルゴリズムも事前計算のスペースがある場合に非常に便利です。

アイデアやミューズグルで私を助けてくれてありがとう。 :)

Answer 1

私は正しく理解していますが、基本的には256を除算しない数値は、それをモジュロ256に加算し続けると数値0..255を生成します。抽象代数のクラスからフラッシュバック...このような

：

s = {} 

n = 157 
for i in range(0, 256): 
    s[n] = True 
    print n 
    n += 157 
    n %= 256 

print "check: has to be 256: ", len(s) 

EDITは：分布がより「ランダム」にするために1より大きいと小型発電機を取り替えました。

Answer 2

例：31 = 1デューティ[％=デューティ/（1 < <ビット）] 8ビットレジスタ内に5ビットディザため位相アキュムレータを使用します。

// Easier to do in assembly, where there is access to the carry flag 
unsigned bits = 5; // states = 1 << bits 
unsigned carry = 7; // keep carry bit within an 8 bit register, limits bits 
unsigned frq = ((1 << carry) * duty)/(1 << bits); // More than 8 bit intermediate value 
unsigned phs = 0; 
for (i = 0; i < (1 << bits); i++) { 
    phs += frq; // Carry is high bit 
    output((phs >> carry) & 1); // Output carry 
    phs &= (1 << carry) - 1; // Discard carry 
} 

ディザパターンは次のようになります。あなたは十分に広い整数を持っていない場合

00: 00000000000000000000000000000000 
01: 00000000000000000000000000000001 
02: 00000000000000010000000000000001 
03: 00000000001000000000010000000001 
04: 00000001000000010000000100000001 
05: 00000010000010000001000001000001 
06: 00000100001000010000010000100001 
07: 00001000010001000010001000010001 
08: 00010001000100010001000100010001 
09: 00010001001000100100010010001001 
10: 00010010010010010001001001001001 
11: 00100100100100100100100100100101 
12: 00100101001001010010010100100101 
13: 00101001010010100101001010010101 
14: 00101010010101010010101001010101 
15: 00101010101010100101010101010101 
16: 01010101010101010101010101010101 
17: 01010101010101011010101010101011 
18: 01010101101010110101010110101011 
19: 01010110101101011010110101101011 
20: 01011011010110110101101101011011 
21: 01011011011011011011011011011011 
22: 01101101101101110110110110110111 
23: 01101110110111011011101101110111 
24: 01110111011101110111011101110111 
25: 01110111101110111101110111101111 
26: 01111011110111110111101111011111 
27: 01111101111101111110111110111111 
28: 01111111011111110111111101111111 
29: 01111111110111111111101111111111 
30: 01111111111111110111111111111111 
31: 01111111111111111111111111111111 

FRQが一度にループ1ビットで計算する必要があるかもしれない（またはアセンブラであった場合に乗算も除算もなし）。

オプションで、ディザパターンをルックアップテーブルの定数として事前に計算してコード化することができます。

2のべき乗のパターンのみノイズがありません。オーディオやRF合成をしない限り、これは重要ではありません。そうでなければ、他のパターンはバーディを持つ。一旦パターンを出力した後、パターンビットの順序をスクランブルすると、ノイズが追加されますが、バーディを削除します。ビットを追加したり削除したりしない長い繰り返し期間を持つLFSR関数（これは1と0の数が同じで、順序変更のみ）はこれを行うために使用できます。

60Hzフレームレートで完全なパターンを出力するには、60Hz *（1 < <ビット）= 1.92kHzのディザ周波数が必要であることに注意してください。おそらく、（1 < <ビット）= 32Hzのように、ちらつきのないLEDのディザ周波数をはるかに低くすることができます。実験！