Hallo zusammen
eine PLL mit der man in einem uC den Clock einstellt, besteht ja häufig
aus einem Teiler (DIV) und einem Multiplizierer (MUL) die den Takt des
externen Quarzes (FQ) verarbeiten:
1
clock = (FQ / DIV) * MUL
Ich möchte eine Funktion schreiben, die den gewünschten clock übergeben
bekommt und die PLL bestmöglichst einstellt (geringste Abweichung vom
vorgegebenen Takt).
Mein erster Ansatz wäre einfach alle möglichen DIV und MUL
durchzuprobieren, den resultierenden Takt zu berechnen und am Ende das
MUL und DIV nehmen, welches den Takt mir der geringsten Abweichung vom
gewünschtem Takt erzeugt.
Nur irgendwie ist das aber ziemlich ineffizient. Gibt es ein bessere
Verfahren ?
@ klaus (Gast)
>Mein erster Ansatz wäre einfach alle möglichen DIV und MUL>durchzuprobieren, den resultierenden Takt zu berechnen und am Ende das>MUL und DIV nehmen, welches den Takt mir der geringsten Abweichung vom>gewünschtem Takt erzeugt.
Ist bei einer geringen Anzahl Werte auch die günstigste.
>Nur irgendwie ist das aber ziemlich ineffizient.
Wenn man das als Makro schrieb ist das egal, es wird ja nur vom Compiler
einmal durchgerasselt.
> Gibt es ein bessere Verfahren ?
Primfaktorzerlegung der Zahlen, daraus kann man die beste
Bruchannäherung berechnen.
Oder man geht über die Grundidee der Festkommaarithmetik ran. Könnte
einfacher und schneller sein.
MFG
Falk
1. Ermittle den ggT von FQ und clock (per Euklid) wähle DIV = FQ / ggT
und MUL = freq / ggT für denn Fall, dass die resultierenden DIV und MUL
innerhalb des wählbaren Wertebereichs liegen.
2. Sollte dies nicht möglich sein, wähle die nächste noch nicht
getestete Annäherung an die Zielfrquenz, die ein Vielfaches von FQ /
maxDiv ist und wiederhole 1. Falls MUL noch ausserhalb des Wertebereichs
liegt wiederhole 2.
Hallo Falk
> Primfaktorzerlegung der Zahlen, daraus kann man die beste> Bruchannäherung berechnen.
Das wäre aber wahrscheinlich ähnlich aufwändig, oder ?
So ganz verstehe ich glaube ich die Idee dahinter nicht, haste mal n
kleines Beispiel
> 1. Ermittle den ggT von FQ und clock (per Euklid) wähle DIV = FQ / ggT> und MUL = freq / ggT für denn Fall, dass die resultierenden DIV und MUL> innerhalb des wählbaren Wertebereichs liegen.>> 2. Sollte dies nicht möglich sein, wähle die nächste noch nicht> getestete Annäherung an die Zielfrquenz, die ein Vielfaches von FQ /> maxDiv ist und wiederhole 1. Falls MUL noch ausserhalb des Wertebereichs> liegt wiederhole 2.
Hallo Tim,
wenn ich den Algorithmus richtig verstehe, dann liefert er aber nicht
zwangsläufig das MUL und DIV Paar welches die geringste Abweichung
erzeugt oder doch ?
Die mathematischen Verfahren sind oft nur begrenzt für PLLs anwendbar,
da sie zwar den besten Bruch liefern, es in der Praxis aber meist
Einschränkungen gibt, wie einen bestimmten Bereich in dem der VCO
arbeiten kann, ein bestimmter Wertebereich für MUL und DIV usw.
Ich verwende daher eine verbesserte Version von alle Kombinationen
durchprobieren:
Ich starte mit DIV=1 und MUL=1 (bzw. dem minimalen zulässigen Wert.)
Damit gehe ich in eine Endlosschleife die solange läuft bis entweder die
Frequenz exakt passt, oder MUL bzw. DIV über dem maximalen zulässigen
Wert sind.
In jedem Schleifendurchlauf wird MUL oder DIV erhöht, je nachdem ob die
Ausgangsfrequenz zu niedrig oder zu hoch ist. Wenn die neue Kombination
eine geringere Abweichung hat als die bisherige beste und alle weiteren
Bedingungen der PLL erfüllt sind, wird diese zwischengespeichert.
Damit spart man sich eine Menge Kombinationen und findet relativ schnell
die beste Kombination. Maximal sind max(MUL) + max(DIV) Schritte
notwendig.
Eigentlich schon.
Das aber keine garantiert, das ist ein "Schnellschuss"
Also für den Fall, dass der DIV bzw MUL über den ggT bestimmt werden,
dann ist das Ergebnis vollkommen Exakt.
Für die andern Fälle weiss ich, dass die kleinsten Abstände zwischen
exakten Zielfrequenzen durch DIV-MUL-Kombinationen FQ / maxDIV ist. Wenn
ich die Punkte in der Umgebung des Ziels, die diese Bedingung erfüllen
(Vielfache von FQ / maxDiv), mit aufsteigendem Abstand zur gewünschten
Zielfrequenz prüfe, dann komme ich an die beste Näherung.
(Auch wenn ich die test-Schrittweite an maxDIV orientiere wird DIV nicht
zwangsläufig maxDIV sein, falls dich das beunruhigt, dafür sorgt die
erneute ggT Berechnung)
@ Benedikt K. (benedikt) (Moderator)
>Ich verwende daher eine verbesserte Version von alle Kombinationen>durchprobieren:
Was ist daran so grossartig verbessert?
>Ich starte mit DIV=1 und MUL=1 (bzw. dem minimalen zulässigen Wert.)>Damit gehe ich in eine Endlosschleife die solange läuft bis entweder die>Frequenz exakt passt,
Naja, das ist je nun eher ein KLEINE Verbesserung.
> oder MUL bzw. DIV über dem maximalen zulässigen Wert sind.>In jedem Schleifendurchlauf wird MUL oder DIV erhöht, je nachdem ob die>Ausgangsfrequenz zu niedrig oder zu hoch ist. Wenn die neue Kombination>eine geringere Abweichung hat als die bisherige beste und alle weiteren>Bedingungen der PLL erfüllt sind, wird diese zwischengespeichert.
Logisch, man muss ja schliesslich den bisher besten Wert sich merken,
wie sonst?
>Damit spart man sich eine Menge Kombinationen und findet relativ schnell>die beste Kombination. Maximal sind max(MUL) + max(DIV) Schritte>notwendig.
Lass das mal keinen Mathematiker hören. Die dreschen dann gnadenlos auf
die planlosen Ingenieure ein, hier sogar zu recht!
Dein Suchlauf braucht maximal max(mul)*max(div)/2 Schritte, nämlich
dann, wenn die Maxima von MUL und DIV deine Lösung sind.
Das Ganze ist Brute Force, nix weiter.
@ OP. Die Suche nach dem ggT, dem grössten gemeinsamen Teiler beinhaltet
die Primfaktorzerlegung.
Ein Beispiel hab ich so fix nicht an der Hand.
MFG
Falk
Nein Falk, er hat schon recht. Die Obergrenze ist range(Div) +
range(Mul)
Er erhöht immer nur je um 1. Zu keinem Zeitpunkt wird einer der
Parameter zurückgesetzt. Das funktioniert für die Suche und kann eben
maximal so oft ausgeführt werden ohne den Wertebereich zu verlassen.
Und nein, der ggT benötigt keine Primfaktorzerlegung (Verfahren von
Euklid) ein einfaches Modulo reicht hier aus.
@ Tim Seidel (maxxie)
>Nein Falk, er hat schon recht. Die Obergrenze ist range(Div) +>range(Mul)
Nöö, schreibs doch mal auf
MUL und DIV von 1..4
MUL DIV
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
>Er erhöht immer nur je um 1. Zu keinem Zeitpunkt wird einer der>Parameter zurückgesetzt. Das funktioniert für die Suche
Nöö, damit überspringt man unzulässig einen SEHR grossen Wertebereich!
MFG
Falk
http://de.wikipedia.org/wiki/Euklidischer_Algorithmus#Iterative_Variante
Keine Primfaktoren involviert, auch wenn ein mathematischer Zusammenhang
zwischen den Primfaktoren und dem ggT existiert. Benötigt werden sie
nicht.
---
Und probiers aus. Der Wertebereich der übersprungen wird, ist bereits
ausschließbar als Lösung. Ich habs eben auch erst überprüfen müssen.
Falk Brunner schrieb:
> @ Tim Seidel (maxxie)>>>Nein Falk, er hat schon recht. Die Obergrenze ist range(Div) +>>range(Mul)>> Nöö, schreibs doch mal auf>> MUL und DIV von 1..4>> MUL DIV> 1 1> 1 2> 1 3> 1 4> 2 1> 2 2> 2 3> 2 4> 3 1> 3 2> 3 3> 3 4> 4 1> 4 2> 4 3> 4 4
Nein, es wir nie ein Wert zurückgesetzt. Daher dauert die Schleife max 8
Takte!
>>Er erhöht immer nur je um 1. Zu keinem Zeitpunkt wird einer der>>Parameter zurückgesetzt. Das funktioniert für die Suche>> Nöö, damit überspringt man unzulässig einen SEHR grossen Wertebereich!
Nein. Probiers mal aus:
Du möchtest den Faktor 1,234
Also beginnst du mit
1 1 = 1 -> zu klein, mul erhöhen
2 1 = 2 -> zu groß, div erhöhen
2 2 = 1 -> zu klein, mul erhöhen
3 2 = 1,5 -> zu groß, div erhöhen
3 3 = 2 -> zu klein, mul erhöhen
4 3 = 1,33 -> zu groß, div erhöhen
4 4 = 1 -> zu klein, mul erhöhen
5 4 -> Ende
Ergebnis: 4 3, also 1,33
@ Benedikt K. (benedikt) (Moderator)
>Ergebnis: 4 3, also 1,33
Ok, da hab ich wohl was ziemlich falsch verstanden. Wenn ich so drüber
nachdenke ist das Verfahren recht einfach und clever.
MfG
Falk
Hallo Benedikt
gutes Verfahren!
Man kann es sogar noch etwas weiter optimieren.
Vielleicht hast du es auch so gemacht,
es geht nicht direkt aus deinem Beitrag hervor.
Berechnet man pro Iteration die Abweichung zu
braucht man
(a) im Idealfall Fließkomma und hat
(b) teure divisionen und multiplikation in der Schleife
Man kann sich beides wie folgt sparen.
Zunächst kann man die Gleichung so umformen:
1
clock * DIV = FQ * MUL
2
3
mit
4
5
A = clock * DIV
6
B = FQ * MUL
A und B kann man sich initial berechnen.
Ist der minimal erlaubte Wert für DIV und MUL = 1 ist A=clock und B=FQ.
Der Algorithmus bleibt gleich und hat die gewünschte Frequenz
exakt berechnet wenn A=B ist.
Was man gewinnt ist folgendes:
Die Abweichung bestimmt man in der Schleife nun durch
1
diff = abs(A-B)
Wird in der Schleife DIV um 1 erhöht,
kann man A neuberechnen mit A = A + clock.
Wird in der Schleife MUL um 1 erhöht,
kann man B neuberechnen mit B = B + FQ.
Man hat also keine Multiplikationen und Divisionen mehr.
@ klaus
Gute Idee. Darauf bin ich auch noch nicht gekommen, was wohl daran
liegt, dass mein µC über eine 32bit Hardwaremultiplikation und Division
verfügt, von daher das ganz nicht so schlimm ist.
Ich sehe da aber ein anderes Problem und zwar kann man damit nicht
prüfen kann ob die PLL Frequenz im zulässigen Bereich ist. Oder übersehe
ich da gerade etwas?
Wo wir schon beim Optimieren sind, hier ein weiteres Problem:
Viele PLLs haben nicht nur einen Divider, sondern erst einen Predivider
der den Quarztakt teilt, dann einen Multiplikator und dann noch einen
Postdivider, da eben die PLL meist nur einen begrenzten Arbeitsbereich
hat (oft nur 4:1).
Hier wird es dann deutlich schwerer, da man jetzt noch einen weiteren
Parameter hat an dem man drehen kann.
Bisher sehe ich hier keine andere Möglichkeit außer eine zusätzliche
Schleife einzubauen, die stur die obige Suche für alle Postdivider Werte
durchführt.
> Ich sehe da aber ein anderes Problem und zwar kann man damit nicht> prüfen kann ob die PLL Frequenz im zuDa es aber auch nicht völlig daneben
lässigen Bereich ist. Oder übersehe
> ich da gerade etwas?
Man kann nur prüfen ob MUL und DIV innerhalb des zulässigen
Wertebereichs liegen, meinst du das?
Habe gerade gemerkt, dass die Modifikation so wie ich sie beschrieben
habe leider nicht garantiert den optimalen Wert liefert wenn es keine
exakte Lösung gibt. Ich überlege mir trotzdem das so zu verwenden, da
extrem schnell...
klaus schrieb:
>> Ich sehe da aber ein anderes Problem und zwar kann man damit nicht>> prüfen kann ob die PLL Frequenz im zuDa es aber auch nicht völlig daneben> lässigen Bereich ist. Oder übersehe>> ich da gerade etwas?>> Man kann nur prüfen ob MUL und DIV innerhalb des zulässigen> Wertebereichs liegen, meinst du das?
Nein. Als Beispiel nehme ich mal die PLL der dsPICs:
Die Eingangsfrequenz wird durch 2-33 geteilt. Das Ergebnis muss zwischen
0,8MHz und 8MHz liegen. Das ist die erste Bedingung.
Diese Frequenz wird mit 2-513 multipliziert. Die VCO Frequenz muss
zwischen 100MHz und 200MHz liegen. Das wäre die nächste Bedingung.
Dieser Wert wird anschließend nochmals durch 1, 2, 4...128 geteilt.
Diese vielen Bedingungen machen einerseits mathematische Lösung nutzlos,
da diese sehr wahrscheinlich ein Ergebnis liefern, das gegen eine von
den Bedingungen verstößt. Ebenso sehe ich hier auch bei deiner Lösung
ein Problem, da man keine Zwischenergebnisse bzw. die VCO Frequenz
erhält um die Bedingungen zu prüfen.
Die erste Bedingung kann man den Präprozessor bzw. der Optimierer des
Compilers berechnen lassen, da bei konstanter Eingangsfrequenz die min
und max Werte konstant sind. Aber bei dem Multiplikator funktioniert das
wegen dem (recht engen) VCO Bereich nicht, da diese Werte von dem Teiler
davor abhängig ist.