Interpolace bez lineární funkce

mhi

  • ***
  • 240
    • Zobrazit profil
Interpolace bez lineární funkce
« kdy: 20. 01. 2020, 12:26:28 »
Resim takovou ulohu, ktera musi fungovat i na lowcost ARMech bez delicky, pripadne na ruznych jinych obskurnich procesorech. Par napadu mam, ale nic svetoborneho, jsou to spis takove "hacky" (bez č).

Mam tabulku o 16 ti sloupcich [0..15] a 2 radcich (prvni bereme jako hlavicku, pricemz v hlavicce jsou hodnoty po celem rozsahu rostouci - nebo klesajici). Dale mam C fci "int interpoluj(int x)" ktera najde mezi kterymi bunkami se moje hodnota x nachazi. Jsou 3 moznosti, bud' je hodnota nizsi nez hlavickatab[0] nebo vetsi nez hlavickatab[15] nebo je mezi nekterymi hodnotami hlavickatab[0..15]. Pro horni a dolni mez se spocita linearni fce pro prvni/posledni 2  prvky, pro hodnoty uvnitr tabulky se vezme linearni fce mezi danymi prvky tabulky a pres hodnotu (2. radek) se interpoluje vysledek. Alternativne u meznich hodnot se vezmou jen ty mezni hodnoty jako "overflow". Snad to je pochopitelne, jde napr. o jednoduchou prevodni tabulku nejakeho nelinearniho senzoru, ktery je po castech linearizovan (treba termistor NTC).

Druha varianta je, kdy je tato tabulka dvojrozmerna, 16x16, tam vznika problem, ze interpoluju ve 2D poli (x-y). Je to vcelku trivialni uloha, mame-li operace mul-div.

A ted prichazi slozitejsi varianta se kterou si moc nevim rady - jak toto realizovat VELICE rychle (klidne se ztratou presnosti, ale obecne pouzitelne pro ruzne varianty) na procesoru ktery mul-div nema, abych pouzival jen  +- or xor shl shr, pripadne maximalne mul ? Rekneme nejaka 8051 ci PIC16 jako etalon hodne hloupeho procesoru. Muj jediny rozumny napad je, kdy si treba urcim rozdil hodnot mezi sousednimi bunkami a pracuji treba jen s N bity na ktere pocitam (vse v mocninach 2), tzn. hlavne tam dochazi k shiftovani.

Presne takove tabulky jsou pouzivane pri rizeni spalovacich motoru, bohuzel vzdy tam je procesor ktery muldev umi, takze jsem se nemohl inspirovat. U starych ridicich jednotek (pred rokem 1996) se vetsinou pouzivala 8051 a tam se interpolace neresi.
« Poslední změna: 20. 01. 2020, 14:00:09 od Petr Krčmář »


Re:Interpolace bez linearni fce
« Odpověď #1 kdy: 20. 01. 2020, 12:59:16 »
Prostorově je to tvrdě omezeno na těch 16 sloupců? Kdyby ne, roztáhnout na např. 64 sloupců, mezipolohy si vypočítat interpolací předem a pak jen dělat nearest-neighbor lookup.

Re:Interpolace bez linearni fce
« Odpověď #2 kdy: 20. 01. 2020, 13:21:11 »
Pokud jsou ty jmenovatele malé a tu tabulku by šlo při kompilaci nějak předžvýkat, tak se dělení známou konstantou dá převést na násobení.
https://gmplib.org/~tege/divcnst-pldi94.pdf

Re:Interpolace bez linearni fce
« Odpověď #3 kdy: 20. 01. 2020, 13:36:18 »
Teda beru zpět to s těmi malými jmenovateli. Stačí pokud půjde ta tabulka při kompilaci doplnit o potřebné hodnoty pro násobení a shift.

mhi

  • ***
  • 240
    • Zobrazit profil
Re:Interpolace bez linearni fce
« Odpověď #4 kdy: 20. 01. 2020, 14:58:33 »
Prostorově je to tvrdě omezeno na těch 16 sloupců? Kdyby ne, roztáhnout na např. 64 sloupců, mezipolohy si vypočítat interpolací předem a pak jen dělat nearest-neighbor lookup.

Ne, toto reseni nechci, problem je ze neni ani moc pameti, resp. tech tabulek je docela dost (delam prave to rizeni spalovaciho motoru a chci ten kod ted' odprasit, aby vse bylo v tabulkach a ne v kodu). Asi bych mohl zvolit ruzne formaty tabulek, ale to udela slozitejsi a pomalejsi kod. Druhy problem je, ze nektere ty senzory maji hodne nelinearni prubehy prave v zajimavych oblastech a je potreba misto vyuzit k ziskani co nejpresnejsich hodnot.

Ad druhe reseni: rozumim tomu (tak nejak intuitivne, dukaz bych asi nenapsal nacisto z hlavy), nicmene nejsem si jist, zda to jde pouzit, protoze to deleni muze nabyvat ruznych hodnot a pak uz je mozna jednodussi mit obrovske tabulky.

Moje reseni je vzit rozdil hodnot right-left (sousedni definovane body), spocitat kde je nejvyssi bit a pak pro N kroku (log2) pricitat k vysledku toto cislo bitove prislusne posunute (cimz ziskam rozdeleni intervalu mezi hodnotami na 2,4,8,16,... dilu, podle toho kolik budu potrebovat - a mam tech 16 subhodnot vyreseno 4 mi operacemi shift if add shift shift. Tim vlastne nepresne nasobim, ale pomerne rychle, rozhodne ne v 300 taktech :) ). Navic si muzu u kazde tabulky urcit presnost se kterou chci pocitat. Vysvetluju to asi nesrozumitelne, kdyztak to prevedu do nejakeho kodu.


gilll

Re:Interpolace bez lineární funkce
« Odpověď #5 kdy: 20. 01. 2020, 15:28:54 »
nestačilo by si ke každému bodu předpočítat směrnici?

mhi

  • ***
  • 240
    • Zobrazit profil
Re:Interpolace bez lineární funkce
« Odpověď #6 kdy: 20. 01. 2020, 16:07:58 »
ad predpocet smernice: U te "3D" 16x16 tabulky to nebude tak uplne jednoduche, nicmene pokud si dovolim pouzit mul, mohlo by to fungovat tak, ze pro danou tabulku by se urcila div konstanta ve tvaru 2^n (==> shr ) a smernice by byla vzdy vypoctena jako val*smernice/2^n, pak by to bylo zrejme pouzitelne.  Tabulku by to zvetsilo jen 2* nebo 3*.

Stale to neresi procesory kde je mul taktove "moc drahy".

Re:Interpolace bez lineární funkce
« Odpověď #7 kdy: 20. 01. 2020, 16:15:54 »
Stale to neresi procesory kde je mul taktove "moc drahy".
Nějaká tabulka předpočítané "násobilky"? ale zase nevím, kolik paměti si můžete dovolit...

gilll

Re:Interpolace bez lineární funkce
« Odpověď #8 kdy: 20. 01. 2020, 16:18:49 »
ad predpocet smernice: U te "3D" 16x16 tabulky to nebude tak uplne jednoduche, nicmene pokud si dovolim pouzit mul, mohlo by to fungovat tak, ze pro danou tabulku by se urcila div konstanta ve tvaru 2^n (==> shr ) a smernice by byla vzdy vypoctena jako val*smernice/2^n, pak by to bylo zrejme pouzitelne.  Tabulku by to zvetsilo jen 2* nebo 3*.

Stale to neresi procesory kde je mul taktove "moc drahy".

v 2d případě stačí 2 předpočítané matice pro x gradient a y gradient. Co znamená moc drahý mul, že nemůžeš násobit vůbec?

Re:Interpolace bez lineární funkce
« Odpověď #9 kdy: 20. 01. 2020, 16:24:30 »
Stale to neresi procesory kde je mul taktove "moc drahy".
Násobení lze udělat jednoduše pomocí bitových posunů a sčítání, např. 131 * X je 128 * X + 2 * X + 1 * X. Tohle funguje jen pro unsigned aritmetiku, ale to nevadí, protože si můžeš vybrat, ze které strany budeš tu interpolaci dělat.

Re:Interpolace bez lineární funkce
« Odpověď #10 kdy: 20. 01. 2020, 17:09:23 »
Resim takovou ulohu, ktera musi fungovat i na lowcost ARMech bez delicky, pripadne na ruznych jinych obskurnich procesorech. Par napadu mam, ale nic svetoborneho, jsou to spis takove "hacky" (bez č).
...
Na tohle narazí každý, kdo se jednočipy zabývá. Zkuste si prohlédnout zdrojáky, je v tom jak lineární aproximace, tak interpolace kubickými splajny, což je o hodně přesnější. Lze to počítat v celých číslech, násobení je potřeba, na druhou stranu pro ty splajny můžete mít tu tabulku docela malou (8 měření) a i tak je to dost přesné, pokud je funkce alespoň trochu monotonní. Dokonce ani ta tabulka nemusí být ekvidistantní. Je to vždy kompromis mezi přesností a náročností na prostředky, takže to chce vyzkoušet a trochu si s tím pohrát.

Re:Interpolace bez lineární funkce
« Odpověď #11 kdy: 20. 01. 2020, 18:36:09 »
Taky mne jako nejjednodušší řešení napadlo pomocí hodnot z tabulky vytvořit aproximační polynom.
Lze i pro více rozměrů:

http://kfe.fjfi.cvut.cz/~limpouch/numet/aprox.pdf

Jen mám obavu, že zrovna u jednočipů bude asi nejrychlejší právě ono vyhledání v tabulce a následná lineární interpolace mezi známými body. Záleží jak moc je průběh složitý a jakého stupně by onen polynom byl.

mhi

  • ***
  • 240
    • Zobrazit profil
Re:Interpolace bez lineární funkce
« Odpověď #12 kdy: 20. 01. 2020, 18:40:53 »
Resim takovou ulohu, ktera musi fungovat i na lowcost ARMech bez delicky, pripadne na ruznych jinych obskurnich procesorech. Par napadu mam, ale nic svetoborneho, jsou to spis takove "hacky" (bez č).
...
Na tohle narazí každý, kdo se jednočipy zabývá. Zkuste si prohlédnout zdrojáky, je v tom jak lineární aproximace, tak interpolace kubickými splajny, což je o hodně přesnější. Lze to počítat v celých číslech, násobení je potřeba, na druhou stranu pro ty splajny můžete mít tu tabulku docela malou (8 měření) a i tak je to dost přesné, pokud je funkce alespoň trochu monotonní. Dokonce ani ta tabulka nemusí být ekvidistantní. Je to vždy kompromis mezi přesností a náročností na prostředky, takže to chce vyzkoušet a trochu si s tím pohrát.

Resim trochu jiny typ ulohy nez popisujete.

PS: S jednocipy tak nejak delam rekneme od roku 2000 (driv jsem taky neco bastlil, ale to byla doba kamenna) a nikdy jsem tuto optimalizaci nepotreboval delat :-).

--------------------------------------------------------------------------------------

Stale to neresi procesory kde je mul taktove "moc drahy".
Násobení lze udělat jednoduše pomocí bitových posunů a sčítání, např. 131 * X je 128 * X + 2 * X + 1 * X. Tohle funguje jen pro unsigned aritmetiku, ale to nevadí, protože si můžeš vybrat, ze které strany budeš tu interpolaci dělat.

Ano, toto +- popisuju s tim, ze ani nemusim dopocitat cely integer, ale jen treba 4 bity podle toho jak presne to chci mit.

Ad drahost MULu, jednu z operaci dohledani v tabulce kteoru potrebuju delat je s mezni frekvenci rekneme 10 000 * 48 * 2 Hz, a to volano z interruptu spolu s dalsimi vypocty. Interrupt se bohuzel vola jeste casteji, protoze digitalne filtruje zakmity a ruseni senzoru. Krome toho musi bezet jeste hromada dalsich veci, ale ty jsou uz minimalne 4* pomalejsi a nektere ultra pomale nebo odlozitelne.

A doplnim, ze tech tabulek bude finalne radove > stovka, nektere rucne delane, nektere vychazejici z mereni (tam se pak uplatni jejich sestaveni pocitacem, ale tuto ulohu zde neresim!)
« Poslední změna: 20. 01. 2020, 18:42:28 od mhi »

RDa

  • *****
  • 1 152
    • Zobrazit profil
    • E-mail
Re:Interpolace bez lineární funkce
« Odpověď #13 kdy: 20. 01. 2020, 23:40:00 »
Otazka je, zda i tyto dnesni, jiz omnoho komplexnejsi ukoly, by se meli resit technologii ktera neni pro ne vhodna. Operaci nasobeni ma dnes kazdy normalni mcu.

Podle casovani potrebujes 1M lookupu, takze to nepobezi na zadnem ATtiny s par MHz a par bajty pameti.
Takze co s ~100MHz a 32K+ pameti nema MUL?

mhi

  • ***
  • 240
    • Zobrazit profil
Re:Interpolace bez lineární funkce
« Odpověď #14 kdy: 23. 01. 2020, 12:50:53 »
Otazka je, zda i tyto dnesni, jiz omnoho komplexnejsi ukoly, by se meli resit technologii ktera neni pro ne vhodna. Operaci nasobeni ma dnes kazdy normalni mcu.

Nemely. Muj pozadavek je z duvodu existence "obsolete" hardware, ktery chci pouzit. Ladim to sice na ARMu, ktery ma vykon i mul a vlastne i div a muze mit klidne i FP a hafo RAMky, nicmene chci to mit v zakladu portovatelne na relativne stary MCU (nakreslit desku a nechat ji vyrobit, osadit, to stoji vic casu nez si to udelat portovatelne/kompatibilni a pak to jen hodit na cizi HW, ktery mam stejne reverse engineernuty).