ich weiss dass die folgende Frage hier nicht ganz on-Topic ist, aber ich gehe davon aus dass es hier einige helle Köpfe gibt die etwas Sinnvolles dazu sagen können.
In einer Mikrocontroller-Schaltung kommt eine Berechnung vor, wo eine Grösse y in Abhängigkeit von drei Grössen a, b und c berechnet werden soll. Also y = f(a,b,c)
Das Problem ist, dass ich jetzt noch nicht weiss wie diese Funktion aussieht. Erst später, wenn sich die Schaltung bereits beim Kunden befindet, wird die Funktion bekannt sein. Das Programm muss aber jetzt geschriebnen werden und soll später nicht mehr verändert werden.
Ich sehe im Moment zwei Lösungsansätze:
In das Programm muss ein kompletter Formel-Interpreter mit rein, die Funktion wird später im NV-Ram abgelegt und dann abgearbeitet. Relativ hoher Programmieraufwand.
Die Funktion wird so dargestellt, dass sie durch eine Reihe von Konstanten an alle denkbaren Fälle angepasst werden kann. Die Konstanten können im NV-Ram abgelegt werden. Zum Beispiel:
Dabei sind c1...c35 die Konstanten, und h1...h4 sind Hilfgrössen.
Mit den ersten 3 Formeln werden die Eingangsgrössen linearisiert, die vierte Formel beschreibt wie stark welche Eingangsgrössen in das Ergebnis eingehen, und die letzte Formel ist nochmal eine universelle Reihenentwicklung.
Die Frage ist nun, wie man so eine universelle Funktion am besten gestaltet. Einerseits sollte sie alle denkbaren Funktionen möglichst gut nachbilden können, andererseits sollte die Anzahl der Konstanten und die Anzahl der Fliesskomma-Operationen nicht zu gross werden. Das oben gezeigte Beispiel ist in dieser Hinsicht sicherlich noch weit vom Optimum entfernt.
Wie die Funktion später aussehen wird, ist noch nicht bekannt. Zum jetzigen Zeitpunkt kann ich aber schon einiges ausschliessen: Es werden keine periodischen Funktionen (sin, cos) benötigt, und nichtstetige Funktionen (sgn) oder Fallunterscheidungen wird es ebenfalls nicht geben.
Nun meine Frage: Ich bin doch bestimmt nicht der Erste, der vor dem Problem steht so eine universelle Funktion zu entwerfen. Gibt es dazu schon irgendwelche Beispiele?
Am Fri, 28 Nov 2008 09:51:43 +0100 schrieb Michael Koch:
Kann man nicht Teile später verändern, indem man diese im NV-RAM hinterlegt und vor der Abarbeitung z.B. in den RAM kopiert?
Das ist natürlich von der Architektur des Controllers abhängig.
Ich habe einen sehr guten Formelparser als DLL für eigene Projekte erworben;
formatting link
Allzu gross ist der auch nicht (18kB), das liesse sich bestimmt auch mit einem geeigneten MC implementieren. Allerdings wird der auch wieder auf Bibliotheken aufsetzen, die leicht den Rahmen sprengen könnten.
Lutz
--
Mit unseren Sensoren ist der Administrator informiert, bevor es Probleme im
Serverraum gibt: preiswerte Monitoring Hard- und Software-kostenloses Plugin
auch für Nagios - Nachricht per e-mail,SMS und SNMP: http://www.messpc.de
Neu: Ethernetbox jetzt auch im 19 Zoll Gehäuse mit 12 Ports für Sensoren
In dem Fall werden für ein Programmiergerät für Freescale HC08-Controller die oberste Schicht der Befehle in Bytecode nochmal definiert und in einem externen 24C02 EEPROM abgelegt. Das sind
20 - 30 Bytecode-Befehle. Sowohl der Compiler der das per V24 reinkommende ASCII-File ins EEPROM compiliert als auch der Interpreter der die Befehle dann ausführt sind simpel, jeweils
1-2 Seiten Sourcecode. Setzt allerdings auf FORTH ( d.h. etwas das ohnehin interpretieren kann ) auf das sich bereits in dem Controller befindet.
Das würde ich empfehlen, da es am universellsten ist und gegenüber dem Ansatz mit einer möglichst universellen, aber feste Formel, auch bedeutend schneller.
Wenn dein Controller C++ kann, dann kannst du diesen von mir entwickelten Formel-Parser nehmen:
formatting link
Könnte allerdings schon ein wenig mehr Speicher brauchen und war auch nur ein proof-of-concept, ob ich sowas "zu Fuß" schreiben kann. Mit flex und bison (oder yacc) ist das eine Sache von 2 Stunden, schön kompakt und in Standard C. Die yacc-Grammatik und Lexer-Beschreibung für einen Formelparser gibt es zudem haufenweise im Web. sodaß man das noch nicht mal selber entwickeln braucht.
--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Mir fehlt die Sicht darauf, warum man das so machen muß. Ganz schnoddrig würde ich erst mal sagen, daß bei hinreichend kleiner Schrittweite alles linear ist.
Wenn die Funktion nur von einer Variablen abhängig wäre, dann könnte man sie als abschnittweise linear betrachten und durch eine Tabelle darstellen. Aber im vorliegenden Fall habe ich 3 Variablen, und das würde dann eine
3-dimensionale Tabelle erfordern. Das sprengt den verfügbaren Speicherplatz.
Aber aus den bisherigen Antworten wird klar, dass ein Formel-Interpreter wohl die bessere Lösung ist.
Wie ja verschiedene Leute hier schon angesprochen haben, wird ein Formel-Interpreter schnell recht aufwändig. Eine reine Parametrisierung könnte sich dagegen als zu unflexibel erweisen. Ich würde daher eine Mischlösung bevorzugen, die etwa so aussehen könnte: Du baust einen kleinen "Bytecode-Interpreter", der intern ein paar Register simuliert und folgende Befehle ausführen kann:
- Lade Festwert in Register
- Lade Wert aus RAM in Register (z.B. kannst Du Deinen Variablen Nummern geben)
- Speichere Register in RAM Eventuell, falls erforderlich, noch weitere arithmetische Funktionen. Compares und bedingte Sprünge etc. wirst Du wahrscheinlich gar nicht brauchen. Dann brauchst Du nur Deine Formel "vorkompiliert" im EEPROM abzulegen und Dein Interpreter arbeitet sie dann ab. Hat den Vorteil, dass es relativ leicht zu coden ist und der Bytecode wenig Platz braucht. Recht performant ist's außerdem.
Viele Grüße, Leo
--
Warning: This posting may contain traces of ISO 8859-1.
Die automotive Kennfeld-Steuergeräte von anno 1979 hatten 2 Variablen:
formatting link
Wie angegeben 16x16 Stützstellen und dann 16 Stellen interpolieren und schon hat man das Alpenpanorama aus Bild 3. Die CPU wurde als RCA 87085A angegeben, wird aber wohl eine 1802 gewesen sein. Program/Daten waren in ROMs.
In ein serielles EEPROM a la 24C512 kriegt man eine Menge Stützwerte rein. Problem bei meinem Programmiergerät ist, daß das Laden eines S19 oder Intel-Hex-Files dieser Grösse über 9600 Baud V24 Geduld verlangt.
Splines sind nicht schlecht. Das sind mehrere Polynome dritter Ordnung (in der Computergrafik nennt sich das auch Bezier), die aneinandergekettet werden von x1 bis x2: h1 = a1 + b1*x + c1*x^2 + d1*x^3 von x2 bis x3: h2 = a2 + b2*x + c2*x^2 + d2*x^3 usw. Du nimmst die Messwerte und fittest die nach der kleinsten Fehlerquadratemethode an die Spline und legst dann a1,b1,c1,d1 x1,x2 pro Abschnitt ab. Matlab (bzw Octave) sollte da fertige Funktionen dafür haben. Ist wohl einer der optimalsten Ansätze (sozusagen die Verbesserung der einfach stückweise Approximation durch Geraden). Hast Du wenigstens ne kleine Ahnung wie die Kurve später mal aussehen soll? Eher wie ein Tagestemperaturgang oder mehr Richtung zackige Börsenkurse?
Ansonsten gibt es auch einige Formelparser mit Quellcode im Web (hatte da mal ne Delphikomponente gefunden), sogar komplette Basic-Interpreter. Nachteil: du brauchst viel mehr Speicher (RAM und ROM), und wenn das Ding Bugs hat, darfst Du da im Parser nach Fehlern suchen. Aber wenn es in Deinen Controller reinpasst, warum nicht.
Kriegst Du das schriftlich? Dann kommt die Funktion (su. FORTH) rein und jede Anpassung lässt sich vergolden :-)
FORTH kann das ganz easy! Da kannst Du beliebig Programmteile (als Source!) in ein EEPROM etc. packen und dann beim Booten einbinden.
Sh. OpenBoot der PowerPC und Sun Workstations, da wird sowas noch extremer gemacht.
[...]
Das glaube ich auch.
FORTH rulez :-)
Ansonsten denke ich mal, dass da jemand (Dein Kunde) sich von hinten in die Knie schiessen will, so dass das Messer aus der Brust guckt wenn ihm das Seil um den Hals zugeht... oder so!
Programm fertigstellen, bevor die komplette HW fertig ist hat noch nie wirklich geklappt. Jedenfalls nicht ohne FORTH. Ansonsten google mal nach Mitch Bradley und FORTH bei Sun...
formatting link
firmware-olpc/
Die Anfänge bei Sun sind in dem Interview aber nur knapp beschrieben. Musst Du mal weitersuchen.
Mitch hat seinerzeit den Plattencontroller programmiert bevor die CPU- Platine funktionierte. Er hat immer in den meetings erklärt, dass er im Plan liegt und er war fertig, bevor der ganze Computer fertig war.
Alle haben geglaubt, er hätte Halluzinationen von zuviel Lötdämpfen... Als dann die CPU funzte und auf Anhieb der Plattencontroller perfekt lief, gabs ein grosses Fragen: wie hat der Kerl das hingekriegt?
Mitch dazu: wenn sich keiner für Deine Arbeit interessiert, ist das übel, aber noch schlimmer ist es, wenn alle (incl. management) dauernd in Dein Labor gestürzt kommen und wissen wollen, wie das mit FORTH ging.
Die kleinsten Controller, die ich mit FORTH programmiert habe, waren cygnal/silabs F300. IIRC 8kB ROM und 256B internal RAM. Da ist dann aber nur noch ein sehr rudimentärer Interpreter drin. FORTH zuckt ab 2kB :-) Ab 16kB gehts gut, ab 32kB + 8kB RAM (+ zus. 1kB ser EEPROM) hast Du allen Luxus, von dem man für embedded Controller träumen kann.
Ich hab das mal zweigeteilt aufgebaut: Einen flex/yacc basierter Parser der aus kleinen Logikformeln eine Art Assembler erzeugt, der zu binärcode übersetzt im Mikrocontroller von einer Stackmaschiene interpretiert wird. Der Interpreter im Controller bestand dabei aus ca.
20 Zeilen C Code. Vorteilhaft ist hierbei das der komplexe Teil der Datenverarbeitung auf den PC begrenzt bleibt.
Das ganze klingt viel schlimmer als es letztendlich ist. bye Rudi
Ja, ist recht einfach. Ich habe es eben quasi nach Kochbuch-Rezept aus "Compilers: Principles, Techniques, & Tools" (die Neuauflage vom Drachenbuch) zusammengehackt, diesmal als rekursiv absteigenden Parser, was in schön kompakten und übersichtlichen Code resultiert, mit dem Nachteil, daß die Parsing-Routine nicht die schnellste ist. Aber muß je nur einmal geparst werden, dann werden nur noch die Opcodes abgearbeitet. Beispielanwendung:
infix syntax: 2.000000 67.875000 * a log * b 1.000000 c / a * + exp + c /
(log und exp sind die Standard C funktionen, also zur Basis e)
Läuft unter Linux per "cc -o formel -lm formel.c" compiliert, problemlos, aber auch unter Windows mit Visual Studio. Die Chancen stehen also hoch, daß es unter vielen anderen Standard C Compilern auch läuft :-)
Man kann es leicht noch beliebig erweitern, z.B. um wissenschaftliche Schreibweise bei den Zahlen, oder weitere Funktionen und Variablen einbauen. Auf ein wenig größeren Microcontrollern sollte es inklusiv Parser problemlos draufpassen, einfach mal ausprobieren. Sonst die Konstantentabelle und die Opcodeliste auf dem PC generieren lassen und nur die evaluate-Funktion auf dem Microcontroller implementieren. Die sollte auch in kleine PICs noch reinpassen (dann aber ohne Floating-Point Support, wenn's wirklich kleine PICs sind).
// one token struct Token { enum TokenType type; union { float floatValue; char charValue; } value; };
// next character for lexer function scan char g_peek;
// next token for parse function struct Token g_lookahead;
// formula to parse char* g_formula;
// bytecode program: contains TokenType elements // bytecode with one argument: // TOKEN_NUMBER: index in g_constants // TOKEN_VARIABLE: 'a', 'b' or 'c' // not used: TOKEN_LEFT_PAREN and TOKEN_RIGHT_PAREN int g_program[MAX_BYTECODE_PROGRAM_SIZE]; int g_programIndex;
// constant table float g_constants[MAX_CONSTANTS]; int g_constantsIndex;
// stack, used while evaluating float g_stack[STACK_DEPTH]; int g_stackIndex;
// forward declaration void expr();
// read next character from formula and return it // return 0, if at end char nextChar() { char c = *g_formula; if (c) g_formula++; return c; }
// lexer struct Token scan() { struct Token token; while (1) { if (!g_peek) { token.type = TOKEN_EOF; return token; } while (1) { if (!(g_peek == ' ' || g_peek == '\t')) break; g_peek = nextChar(); } if (!g_peek) { token.type = TOKEN_EOF; return token; } if (isdigit(g_peek) || g_peek == '.') { float v = 0; if (isdigit(g_peek)) { while (1) { v = v * 10.0f + (float) (g_peek - '0'); g_peek = nextChar(); if (!isdigit(g_peek)) break; } } if (g_peek == '.') { float fraction = 0; float div = 10; g_peek = nextChar(); if (isdigit(g_peek)) { while (1) { fraction += (float) (g_peek - '0') / div; div *= 10.0f; g_peek = nextChar(); if (!isdigit(g_peek)) break; } } v += fraction; } token.type = TOKEN_NUMBER; token.value.floatValue = v; return token; } if (isalpha(g_peek)) { int i = 0; char buf[10]; while (1) { buf[i++] = g_peek; g_peek = nextChar(); if (!isalpha(g_peek)) break; if (i == 10) { printf("identifier too long"); exit(-1); } } buf[i] = 0; if (strcmp(buf, "a") == 0) { token.type = TOKEN_VARIABLE; token.value.charValue = 'a'; } else if (strcmp(buf, "b") == 0) { token.type = TOKEN_VARIABLE; token.value.charValue = 'b'; } else if (strcmp(buf, "c") == 0) { token.type = TOKEN_VARIABLE; token.value.charValue = 'c'; } else if (strcmp(buf, "log") == 0) { token.type = TOKEN_LOG; } else if (strcmp(buf, "exp") == 0) { token.type = TOKEN_EXP; } else { printf("unknown identifier"); exit(-1); } return token; } switch (g_peek) { case '+': token.type = TOKEN_ADD; break; case '-': token.type = TOKEN_SUB; break; case '*': token.type = TOKEN_MUL; break; case '/': token.type = TOKEN_DIV; break; case '(': token.type = TOKEN_LEFT_PAREN; break; case ')': token.type = TOKEN_RIGHT_PAREN; break; default: printf("syntax error"); exit(-1); break; } g_peek = ' '; return token; } }
// match a token and scan the next token void match(enum TokenType t) { if (g_lookahead.type == t) { g_lookahead = scan(); } else { printf("\nsyntax error"); exit(-1); } }
// add one bytecode to the program void addBytecode(int code) { g_program[g_programIndex++] = code; if (g_programIndex == MAX_BYTECODE_PROGRAM_SIZE) { printf("\nprogram too long"); exit(-1); } }
// add a constant to the constant table and the constant load instruction to bytecode void addConstant(float value) { addBytecode(TOKEN_NUMBER); addBytecode(g_constantsIndex); g_constants[g_constantsIndex++] = value; if (g_constantsIndex == MAX_CONSTANTS) { printf("\ntoo many constants"); exit(-1); } }
// pop a value from stack float pop() { if (g_stackIndex == 0) { printf("stack underflow"); exit(-1); } return g_stack[--g_stackIndex]; }
// push a value to stack void push(float value) { g_stack[g_stackIndex++] = value; if (g_stackIndex == STACK_DEPTH) { printf("stack underflow"); exit(-1); } }
// evaluate the parsed formula float evaluate(float a, float b, float c) { int* program = g_program; float arg; g_stackIndex = 0; while (1) { int bytecode = *program++; switch (bytecode) { case TOKEN_EOF: return pop(); case TOKEN_NUMBER: push(g_constants[*program++]); break; case TOKEN_ADD: push(pop() + pop()); break; case TOKEN_SUB: arg = pop(); push(pop() - arg); break; case TOKEN_MUL: push(pop() * pop()); break; case TOKEN_DIV: arg = pop(); push(pop() / arg); break; case TOKEN_VARIABLE: switch (*program++) { case 'a': push(a); break; case 'b': push(b); break; case 'c': push(c); break; default: printf("unknown variable"); exit(-1); } break; case TOKEN_LOG: push(logf(pop())); break; case TOKEN_EXP: push(expf(pop())); break; } } }
// debug function for dumping the bytecode program void dump() { int* program = g_program; g_stackIndex = 0; while (1) { int bytecode = *program++; switch (bytecode) { case TOKEN_EOF: return; case TOKEN_NUMBER: printf("%f ", g_constants[*program++]); break; case TOKEN_ADD: printf("+ "); break; case TOKEN_SUB: printf("- "); break; case TOKEN_MUL: printf("* "); break; case TOKEN_DIV: printf("/ "); break; case TOKEN_VARIABLE: printf("%c ", *program++); break; case TOKEN_LOG: printf("log "); break; case TOKEN_EXP: printf("exp "); break; } } }
// main entry point int main(int argc, char** argv) { float a, b, c, y; if (argc != 5) { printf("usage: formula a b c\n"); exit(-1); } parse(argv[1]); a = (float) atof(argv[2]); b = (float) atof(argv[3]); c = (float) atof(argv[4]); y = evaluate(a, b, c); printf("formula: %s\n", argv[1]); printf("\na: %f\n", a); printf("b: %f\n", b); printf("c: %f\n", c); printf("\ny: %f\n", y); printf("\ninfix syntax: "); dump(); printf("\n"); return 0; }
--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Du solltest die mehr oder weniger zarten Hinweise auf FORTH mal beachten. Noch ein bischen Honig ums Mauls schmieren:
FORTH wurde in den 60er und 70er Jahren entwickelt, von Chuck Moore, der damit (besonders interaktiv) als freelancer die Positionen von (Radio)- Teleskopen steuerte und programmierte. FORTH ist besonders in den Kreisen und bei der NASA stark im Einsatz. Die (3 von 4) Teleskope seinerzeit in dem Space-Shuttle Experiment sind alle in FORTH (übrigens wussten die verschiedenen Unis nix davon, dass andere auch in FORTH schrieben) geschrieben, der Greifarm ebenfalls.
IIRC ist auch OSCAR-1 per Forth programmiert. Damals auf einem RCA 1802.
FORTH braucht extrem wenig Resourcen, ist sehr schnell und arbeitet interaktiv.
FORTH schaltet (typisch selbsständig aber auch auf Wunsch) zwischen Compiler und Interpreter Modus um. Aber das ist für einen Neuling nur verwirrend und irgendwann kapiert man dann, warum das alles so einfach und genial ist.
Ich habe bis heute nicht rausbekommen, ob es ein Interpiler oder ein Compreter ist :-)
Mit FORTH erstellt man das Programm (in FORTH heisst das Worte) in der natürlichen Sprache und Kontext des Anwenders. Du rufst alle Worte (Funktionen) per Name auf. Wenn Du willst, kannst Du sowas schreiben
: AZIMUT ( nWinkel -- ) ( ein Kommentar steht immer in Klammern ) Z Achse freigeben Stell-Winkel ermitteln Position ansteuern Z Achse blockieren ;
Obiges Wort (Progrämmchen) braucht nur ca. 40 byte im Speicher! Mit : schaltest Du den Compiler ein, das nächste Wort ist der neue Name, danach die Liste der abzuarbeitenden Dinge (andere Worte) ; schaltet den Compiler ab und den Interpreter wieder ein. Nun kennt das System das Wort AZIMUT und kann die jederzeit unter diesem Namen aufrufen.
und dann tippst du:
67.5 Grad AZIMUT
und die Z-Achse zeigt anschliessend auf 67,5°
Bei C haben die Programmierer den Compiler im Kopf. Bei FORTH haben die Programmierer den Compiler im Target :-)
Wenn Du hp Taschenrechner magst, dann ist FORTH das Einfachste was es gibt! Du wirst nach einiger Zeit nicht mehr begreifen, warum alles andere so kompliziert ist/war.
Das klingt eigentlich mehr nach einer Anwendung für einen Bootloader.
Was spricht dagegen, das Programm zu gegebenem Zeitpunkt mit der entsprechenden Funktion zu kompilieren und dem Kunden zu mailen? Ein Bootloader ist sowieso ganz praktisch, wenn dem Kunden noch was einfällt, das er gern hätte.
Es hängt insbesondere davon ab, wo du "komplett" ansetzt. Alle bisherigen Vorschläge liefen ja mehr oder weniger auf die Grund- rechenarten hinaus. Eine wirklich *universelle* Funktion dreier Variablen könnte aber auch Wurzeln, Logarithmen, Winkelfunktionen oder richtig eklige Sachen wie Besselfunktionen etc. enthalten. Das wirst du wahrscheinlich nicht auf einem Mikrocontroller parsen und rechnen wollen, auch wenn der Begriff heutzutage gern mal 32-Bit Cores mit Floatingpoint-Einheit umfaßt.
Es wäre also sinnvoll, wenn du deine Funktion erst mal einschränkst. Vermutlich geht es ohnehin um ein "Fitting" Problem. D.h. die Funktion muß ein paar vorgegebene Werte treffen. Dann wäre eine Polynom-Inter- polation oder (evtl. besser) Spline-Interpolation denkbar.
Das läuft auf ein Polynom hinaus:
y = sum c_ijk a^i b^j d^k i,j,k
i,j,k laufen dabei von 0...M, wobei M die höchste Potenz der unabhängigen Variablen ist. Insgesamt gibt es (M+1)^3 Koeffizienten, für M=3 also z.B. 64 Stück. Als einfachgenaue FLOATS sind das 256 Byte. Für größere M würde man wohl darauf hoffen, daß viele Koeffizienten
0 sind und nur die von 0 verschiedenen als Liste von Tupeln (c_ijk, i, j, k) speichern. Für Splines gilt ähnliches, allerdings sind es potentiell mehr Koeffizienten.
Falls das reicht, wäre die direkte Speicherung der Koeffizienten wohl die erste Wahl.
Das hilft nicht unbedingt weiter. Reihenentwicklungen sind ja üblicher- weise nur auf kleinen Intervallen der Eingangsgrößen brauchbar.
Die klassische Anwendung ist ein interaktiver Funktionsplotter. Da läuft es meistens darauf hinaus, eine möglichst universelle Library an Grundfunktionen und einen Arithmetik-Parser zu haben. Insbesondere ersteres harmoniert nicht mit "Mikrocontroller". Es sei denn, du kannst die Grundfunktionen einschränken.
Den Parser würde man vermutlich am besten außerhalb des Controllers unterbringen und im EEPROM dann Bytecode oder direkt Maschinencode speichern.
Und was steckt hinter "Z Achse freigeben"? Das versteht der Controller ja auch noch nicht.
Ich habe Deine Beispiele schon immer mit Interesse gelesen, sieht schön einfach aus ;-). Aber letztendlich muss ich auf einem Microcontroller irgendwann ja Timer, Ports, Interrupts, also den ganzen echt hardware- nahen Kram mit Parametern versorgen oder Werte abfragen.
Gibt es da irgendwo eine Adresse im Netz "Forth for Dummies and microcontroller" wo man sich mal einlesen kann?
73 de Tom
--
Thomas 'Tom' Malkus, DL7BJ
Locator JO43GC * DL-QRP-AG #1186 * AGCW-DL #2737 * DARC OV I19
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.