Eine effiziente ganzzahlige eindimensionale Dithering-Funktion?

Question

Ich habe in letzter Zeit viel mit LEDs gespielt, angetrieben von 8-Bit Mikrocontrollern. Manchmal ist es notwendig, reine Software-Implementierungen der Pulsweitenmodulation zu verwenden, um die LED-Helligkeit zu steuern - das heißt, das Licht ein- und auszuschalten, wobei das Verhältnis der Zeit schnell ein- und ausgeschaltet wird. Das funktioniert gut, bis ich auf etwa 5% Helligkeit komme, wo das Stroboskop unbehaglich ins Auge fällt.

Wenn Sie den PWM als Schleife implementieren, wird jede Zahl von 0-255 durchlaufen, um das Licht für diesen Moment ein- oder auszuschalten. Ein Licht, das auf den Wert 20 eingestellt ist, wird für die ersten 20 Schleifen eingeschaltet und dann ausgeschaltet.

Ich bin auf der Suche nach einer guten Funktion, die um diese Zahlen herum mischen wird, also anstatt 0, 1, 2, 3 zu durchlaufen ... könnte meine Schleife halb zufällig aus dem Pool von Möglichkeiten probieren. Die Gesamthelligkeit im Laufe der Zeit ist die gleiche, aber ein Licht mit 20 Helligkeitswert kann ein Dutzend Mal über 256 Schleifen ein- und ausgeschaltet werden, anstatt nur einmal zu leuchten und dann für den größten Teil der Schleife auszuschalten. Dies reduziert den Flackereffekt, selbst wenn die Schleife etwas langsamer läuft.

Eine gute Dithering-Funktion müsste jede Zahl im 8-Bit-Bereich zurückgeben, wenn sie mit jeder 8-Bit-Zahl aufgerufen wird. Es müsste also auch keine doppelten Zahlen erzeugen - nicht zufällig, nur gemischt. Es ist am besten, wenn es nicht dazu tendiert, ähnliche Zahlen hintereinander zu setzen - der Unterschied zwischen jeder Zahl sollte hoch sein - idealerweise bei 64-127, denke ich.

Die Einschränkungen sind auch interessant - es ist eine zeitkritische Anwendung. Additions-, Subtraktions- und bitweise Operationen kosten 1 willkürliche Zeiteinheit, Multiplikation kostet 2 Einheiten und Teilungskosten 4 Einheiten. Floats sind nicht in Frage, und die Kosten verdoppeln sich für jedes Vielfache von 8 Bits, die in einer Zwischenzahl verwendet werden. Nachschlagetabellen sind möglich, würden aber etwa die Hälfte der gesamten Speicherkapazität des Geräts beanspruchen - schnelle Algorithmen sind für die Wiederverwendbarkeit am besten geeignet, aber auch langsame Algorithmen von guter Qualität sind sehr nützlich, wenn Platz für die Vorberechnung vorhanden ist.

Vielen Dank für Ihre Hilfe mit Ideen oder Überlegungen. :)

Answer 1

Nicht 100% sicher, dass ich richtig verstehe, aber im Grunde denke ich, dass alle Zahlen, die 256 nicht teilt die Gruppe der Zahlen 0..255 generieren, wenn Sie es einfach zu sich selbst Modulo 256 hinzufügen. Einige Flashbacks von der abstrakten Algebra-Klasse ...

wie folgt aus:

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: ersetzt kleinen Generator mit einem größeren der Verteilung mehr „zufällig“ zu machen.

Answer 2

Beispiel: Unter Verwendung einen Phasenakkumulator für 5-Bit-Dither innerhalb eines 8-Bit-Register, in dem Duty = 1 bis 31 [% = duty/(1 < < Bits)].

// 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 
} 

Die Dithermustern wie folgt aussehen:

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 müssen möglicherweise zu einer Zeit in einer Schleife ein Bit berechnet werden, wenn Sie nicht breit genug, um ganze Zahlen (oder in Assembler, wenn es nein multiplizieren oder teilen).

Optional können die Dither-Muster vorberechnet und als Konstanten in einer Nachschlagetabelle codiert werden.

Nur die Muster für Potenzen von zwei haben kein Rauschen; Dies ist nicht wichtig, außer Sie tun Audio-oder RF-Synthese. Ansonsten haben die anderen Muster Birdies. Das Mischen der Reihenfolge der Musterbits nach dem einmaligen Ausgeben eines Musters würde Rauschen hinzufügen, aber die Birdies entfernen. Eine LFSR-Funktion mit einer langen Wiederholungsdauer, die keine Bits hinzufügt oder entfernt (Anzahl von Einsen und Nullen bleibt gleich, nur ihre Reihenfolge ändert sich), könnte dazu verwendet werden.

Beachten Sie, dass zur Ausgabe eines vollständigen Musters bei 60 Hz Bildfrequenz eine Ditherfrequenz von 60 Hz * (1 < < Bits) = 1,92 kHz erforderlich ist. Vermutlich kann man mit wesentlich geringerer Dither-Frequenz für LED ohne Flimmern davonkommen, wie (1 < < Bits) = 32 Hz. Experiment!