Forum: Mikrocontroller und Digitale Elektronik Taktberechnung für PLL (allgemein)


von klaus (Gast)


Lesenswert?

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 ?

von Falk B. (falk)


Lesenswert?

@  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

von Tim S. (maxxie)


Lesenswert?

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.

von klaus (Gast)


Lesenswert?

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

von klaus (Gast)


Lesenswert?

> 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 ?

von Benedikt K. (benedikt)


Lesenswert?

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.

von Tim S. (maxxie)


Lesenswert?

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)

von Falk B. (falk)


Lesenswert?

@  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

von Tim S. (maxxie)


Lesenswert?

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.

von Falk B. (falk)


Lesenswert?

@  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

von Tim S. (maxxie)


Lesenswert?

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.

von Benedikt K. (benedikt)


Lesenswert?

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

von Falk B. (falk)


Lesenswert?

@  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

von klaus (Gast)


Lesenswert?

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
1
diff = fabs(clock - (FQ / current_MUL) * current_DIV)

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.

von Benedikt K. (benedikt)


Lesenswert?

@ 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.

von klaus (Gast)


Lesenswert?

> 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...

von klaus (Gast)


Lesenswert?

Kann sich jeder selbst mal anschauen, ob das Verfahren interessant ist:


1
#define OSC_FREQ      18432
2
3
#define DIV_MIN_VALUE    1
4
#define DIV_MAX_VALUE    255
5
#define MUL_MIN_VALUE    1
6
#define MUL_MAX_VALUE    2047
7
8
typedef unsigned int int32u;
9
10
int32u setSpeed(int32u arg_Speed)
11
{
12
  int32u my_Div = DIV_MIN_VALUE;
13
  int32u my_BestDiv = DIV_MIN_VALUE;
14
  int32u my_Mul = MUL_MIN_VALUE;
15
  int32u my_BestMul = MUL_MIN_VALUE;
16
  int32u my_A = arg_Speed * DIV_MIN_VALUE;
17
  int32u my_B = OSC_FREQ * MUL_MIN_VALUE;
18
  int32u my_Diff;
19
  int32u my_BestDiff = ~(int32u)0;
20
21
  if (0 != arg_Speed)
22
  {
23
    while(my_A != my_B)
24
    {
25
      if (my_A > my_B)
26
      {
27
        ++my_Mul;
28
        my_B += OSC_FREQ;
29
        if (my_Mul > MUL_MAX_VALUE)
30
        {
31
          break;
32
        }
33
      } else
34
        {
35
          if (my_A < my_B)
36
          {
37
            ++my_Div;
38
            my_A += arg_Speed;
39
            if (my_Div > DIV_MAX_VALUE)
40
            {
41
              break;
42
            }
43
          }
44
        }
45
46
      my_Diff = abs(my_A - my_B);
47
48
      if (my_Diff < my_BestDiff)
49
      {
50
        my_BestDiv = my_Div;
51
        my_BestMul = my_Mul;
52
        my_BestDiff = my_Diff;
53
      }
54
55
      printf("mul=%d, div=%d, my_A=%d, my_B=%d, f=%f\n",
56
        my_Mul, my_Div, my_A, my_B, (OSC_FREQ / (float)my_Div)*my_Mul);
57
    }
58
  } else
59
    {
60
      // the speed should be 0... this makes no sense
61
      // so we use the minimum frequency available
62
      my_BestDiv = DIV_MAX_VALUE;
63
      my_BestMul = MUL_MIN_VALUE;
64
    }
65
66
  printf("best_div=%d, best_mul=%d, f=%f\n",
67
          my_BestDiv, my_BestMul, (OSC_FREQ / (float)my_BestDiv) * my_BestMul);
68
69
  return (OSC_FREQ / my_BestDiv) * my_BestMul;
70
}

von Benedikt K. (benedikt)


Lesenswert?

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.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.