Forum: Mikrocontroller und Digitale Elektronik Interpolation in C


von Mark Toellner (Gast)


Lesenswert?

Hallo Kollegen,

ich möchte auf einen 8Bit-µC eine Interpolation verwirklichen.

Ich habe ein SuchFeld[265], und zwei uint Input, Output.


Das SuchFeld sieht etwa so aus:
----------------------------------------------------------
const unsigned int SuchFeld[265] = {
1            // Index 1
2            // Index 2
6            // Index 3
11           // Index 4
15           // Index 5
19           // Index 6
22           // Index 7
28           // Index 8
...
----------------------------------------------------------

Die Variable Input hat einen Wertebereich von 0..1023.

Momentan mache ich folgendes:
Input ist der Index, Output ist die Variable des Suchfeldes. Siehe 
Programmcode:
----------------------------------------------------------
Input /= 4;
Output = SuchFeld[Input];
----------------------------------------------------------

Ist in meinem oben genannten Programmcode z.B. Input = 10 dann
Erhalte ich als Output = 6.

Dieses Ergebnis ist mir allerdings zu ungenau! (Info: Die Tabelle lässt 
sich nicht erweitern!)
Ich muß deshalb Interpolieren.

Allg. Formel: f(x) = f0 + (f1 - f0)/(x1 - x0)*(x - x0)
[wobei x1-x0 immer 1 - Tabelle]

Wende ich diese Formel an müßte ich bei einem Input = 10 ein Output = 4 
erhalten.

Ich habe es auch versucht zu implementieren. Allerdings habe ich mit 
über 13 if verschachtelungen wohl nicht gerade die Laufzeitoptimierteste 
Lösung gefunden. Deshalb wende ich mich hier auch an Profis. ;)

Mein Hauptproblem ist je nach Input Eingangswert das richtige Wertepaar 
(f1,f0) zu finden! (Die Tabellengrenze sollte ja mitbeachtet werden.)

Ich hoffe das ganze versteht irgendjemand ich finde ein helfendes Hirn!

Gruß, Mark Toellner

von Karl H. (kbuchegg)


Lesenswert?

Dein erstes Ziel muss es sein, die beiden
Tabellenindizes zu finden, zwischen denen
der gesuchte Index liegt.

Bei einem Eingabewert von 10, sind für dich
die Tabellenindizes 1 und 2 interessant.

   low  = ( 10 / 4 ) - 1  -> 1
   high = ( 10 / 4 )      -> 2

Etwas Vorsicht musst du am Anfang und am Ende
der Tabelle walten lassen.

D.h. dein gesuchter Wert liegt irgendwo zwischen
Suchfeld[1] und Suchfeld[2].
Nur wo genau.
10 / 4 -> 2.5
Die 2 haben wir schon berücksichtigt. Bleiben noch die
0.5. Dein gesuchter Wert liegt also genau in der Mitte
zwischen Suchfeld[1] und Suchfeld[2]

Mit Kommazahlen wollen wir nicht rechnen, also
holen wir uns mal den Rest der Division:

   t = 10 % 4       -> 2

und interpolieren

  Wert = Suchfeld[low] + ( Suchfeld[high] - Suchfeld[low] ) * t / 4;

in Zahlen

   Suchfeld[1]  -> 2
   Suchfeld[2]  -> 6

   2 + ( 6 - 2 ) * 2 / 4

   2 + 4 * 2 / 4

   2 + 2

   4


Bis auf den Fall, dass die erste Division eine 0 für high
ergibt und es daher keinen low Index gibt, brauchst du kein
einziges if.

von Mark Toellner (Gast)


Lesenswert?

Danke für die schnelle Antwort!

Ich denke ich habe meinen Denkfehler erkannt!
Der Modulooperator war der Schlüssel!

Ich denke es muß so richtig sein:
Da Integer immer Abgerundet werden!?

   low  = ( 10 / 4 )      -> 1
   high = ( 10 / 4 ) +1   -> 2

Gruß,
Mark Toellner

von Kai S. (Firma: ZeuSWarE GmbH) (zeusosc)


Lesenswert?

Bei der Interpoleration ist die gewichtung ziemlich wichtig, daher 
sollte man mit kommazahlen arbeiten,..
pseudo:
double i2= (double) input
double ret= i2/N (N anzahl der tabelleneinträge
double i3=floor(ret)

fkt void* d2i(int i) return i
int i4 =d2i(i3)

lineare gewichtung:
double m=(table[i4]-table[i4+1])/(i3-(i3+1))
double n=table[i4]-m*i3
return (m*ret+n)

>edit:
>grüüße

von Karl H. (kbuchegg)


Lesenswert?

Mark Toellner wrote:
> Danke für die schnelle Antwort!
>
> Ich denke ich habe meinen Denkfehler erkannt!
> Der Modulooperator war der Schlüssel!
>
> Ich denke es muß so richtig sein:
> Da Integer immer Abgerundet werden!?
>
>    low  = ( 10 / 4 )      -> 1
>    high = ( 10 / 4 ) +1   -> 2
>

Hätte ich auch gedacht.
Aber dann stimmen deine in der Fragestellung
genannten Zahlen nicht mehr:

const unsigned int SuchFeld[265] = {
1            // Index 1
2            // Index 2
6            // Index 3

Und du sagst dass der Wert für 10 bisher bei dir 6
war.

Was jetzt richtig ist, kannst nur du sagen.

Wenn ich, für mich einfach mal die Ausgangswerte zu den
Arrayelementen dazuschreibe

const unsigned int SuchFeld[265] = {
1,   // 0, 1, 2, 3
2,   // 4, 5, 6, 7
6,   // 8, 9, 10, 11
11,  // 12, 13, 14, 15

dann ist der korrekte Wert für 10 irgendwo zwischen
6 und 11, nämlich ( 6 + 11 ) / 2 = 8. Du sagtest aber in deiner 
Fragestellung, dass 4 richtig wäre


:-)

von Karl H. (kbuchegg)


Lesenswert?

Kai Scheddin wrote:
> Bei der Interpoleration ist die gewichtung ziemlich wichtig, daher
> sollte man mit kommazahlen arbeiten,..

Nicht wenn man es richtig macht und das Ergebnis wieder
im Ganzzahl-Bereich liegen soll/muss.

von Karl H. (kbuchegg)


Lesenswert?

Mark Toellner wrote:
> Da Integer immer Abgerundet werden!?

Da muss ich noch nachhaken.

Sie werden nicht abgerundet. Die Nachkommastellen
werden abgeschnitten.

Bei positiven Zahlen macht das keinen Unterschied.
Bei negativen schon.

-3.6   abgerundet         -4
       kommastellen weg   -3

von Dirk (Gast)


Lesenswert?

Auf einem 8Bit Controller so eine Lappalie mit double rechnen...
Verrückte Welt heutzutage, tzzzz

von Karl H. (kbuchegg)


Lesenswert?

Dirk wrote:
> Auf einem 8Bit Controller so eine Lappalie mit double rechnen...
> Verrückte Welt heutzutage, tzzzz

:-)

Noch dazu beinhart alles in double.
Wenn er wenigstens nur die letzte Division in double
gemacht hätte, hätte ich ja noch Verständnis dafür.

von Anfänger (Gast)


Lesenswert?

Ist es denn gar nicht möglich auf einem 8 bit Controller mit double zu 
rechnern?

von Karl H. (kbuchegg)


Lesenswert?

Möglich ist es schon.
Nur vermeidet man das wenn es nicht absolut notwendig ist.

Über den Daumen gepeilt würde ich mal sagen, dass floating
point auf einem 8 Bit Mikro mindestens um einen Faktor 10
langsamer ist.

von Kai S. (Firma: ZeuSWarE GmbH) (zeusosc)


Lesenswert?

Karl heinz Buchegger wrote:
>Nicht wenn man es richtig macht und das Ergebnis wieder
>im Ganzzahl-Bereich liegen soll/muss.
ja gut, je nach aufgabenstellung, und aus welchen Körper die werte 
sind,..

zu dem double, habe ja extra pseudo darüber geschrieben,
man kann ja auch mit 8bit fließkomma arbeiten
entweder rund 0.00->255.99 oder rund +-128.99 (oder so ähnlich)

grüüße

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.