Ismer valaki olyan tömörítő eljárást, aminek a dekódoló algoritmusához elég 1 Kilobyte (! 1024 byte! ) RAM memória?
Egy mikrokontrolleres programhoz lenne szükségem egy ilyenre, és abban csak 1 Kilobájtnyi (NEM Mega, pláne nem Gigabyte) RAM memória van. A flash memóriába pedig csak felprogramozáshoz lehet írni.
Értelemszerűen a tömörítendő csomag tömörítetlen (nyers) formában mindenképp kisebb lenne 1 KB-nál, vagyis az 500 bájtot nem haladná meg, de a jelenlegi állások szerint ennél is kevesebb, 250 bájt. Ezt kellene betömöríteni, ami normál PC-n történne, de a kitömörítést már a mikrokontroller processzora végzi a programfutás alatt, és ott az egész műveletsor lefutásához durván 1 KB RAM memória áll rendelkezésre, úgy, hogy a kitömörített adatnak a folyamat végén a RAM memóriában egy bájttömben kell majd helyet foglalnia (máshonnét nem is tudnám olvasni, illetve beírni). Tehát nagyjából a teljes folyamat adatmozgató műveleteihez még pluszban az adat kitömörített méretének a 3×-a áll rendelkezésre.
Amit be szeretnék tömöríteni, és majd futásidőben kitömöríteni, az kb. így néz ki hexadecimális értékpárokkal felírva (pillanatnyilag ezt használom a többi program részéhez tesztelésre, de nagy valószínűséggel az első verzióban is ez a 250 bájtos értéksor lesz benne, remélhetőleg a programkódban tömörített formában felírva HA itt a kérdésemre kapok választ) :
2A 1D 34 00 00 00 00 00 CD 3A 00 00 00 00 00 40 A5 06 BA 0B 00 00 00 00 00 00 00 00 00 00 00 F8 05 32 36 F9 7C 08 2F 00 00 00 00 00 00 00 00 AD 8D 10 00 00 00 00 00 0F 1B 05 00 00 00 00 E0 0C 00 00 90 06 F0 07 00 00 00 00 00 00 00 00 94 D5 F6 BB 00 00 00 00 00 00 00 00 00 00 00 80 6C 9C C0 15 00 00 00 40 45 AD 13 06 00 00 00 50 0F 00 00 88 02 00 00 00 00 00 00 00 00 00 00 9E A4 5C 55 00 00 00 00 00 00 00 00 00 00 00 00 D0 17 0F 08 00 00 00 00 00 00 00 00 00 00 00 C8 81 A5 D4 B4 6C AF 85 00 00 00 00 4E 00 00 00 1F 16 00 1E 00 00 00 80 6D 1F 40 00 00 00 00 A0 2E D0 0F 00 00 00 00 D0 2E 00 00 20 03 00 00 44 81 41 B7 00 00 00 00 04 00 00 00 00 00 00 80 DA 6E 18 6C 88 6C 53 0A 00 00 00 E0 00 00 00 38 B7 02 00 D0 FE 01 00 8C 00 A6 00 3A 05 00 10
Szóval megoldható lenne ez? Ismer valaki a megoldáshoz használható már kidolgozott tömörítő algoritmust?
Ha valaki kérdezné, ez az adatsor egy 1 bites dobsáv tárolásához kell. Ehhez majd jön egy monofonikusra lebontott ragtime-szerű daljáték, szinten 1 bites mintákból összeállítva (tehát csakis a két szélső amplitúdóértéket használom), amiket aztán valós időben pontonként összeadogatok, illetve jobban mondva összenyalábolok (valószínűleg nem szó szerinti + jel lesz, de az is lehet, hogy a végső kiküldött értékek nem 1 bitesek (2 állapotúak) lesznek), és kiküldök a hangszóróval összekötött pinre.
Ennyi.
De most a lényeg, hogy ne kelljen annyi nyers értéket tároljak a flash memóriában, ott inkább programkód legyen.
Ha valaki arra gondolna, persze valószínű, hogy ezzel a program méretét illetően nem fogok tudni helyet spórolni, sőt, lehet, a kitömörítés kódja többet elvinne..... viszont én akkor is szívesebben választanám ezt a megoldást, mert számomra jóval igényesebb és elegánsabb módszer. (A flash meg 64 Kbyte-os, úgyhogy ott nem kell praktikussági okokból történő tömörítésen gondolkozni, mert az mindenképp elég lesz a programnak - szerintem.
További próbálkozásaim:
A bemásolt 250 bájtos blokknál maradva, megnéztem, hogy az egész összesen 78 különböző értéket tartalmaz, éspedig a szemléltetéshez, ezek vesszővel elválasztva:
00, 01, 02, 03, 04, 05, 06, 07, 08, 0A, 0B, 0C, 0F, 10, 13, 15, 16, 17, 18, 1B, 1D, 1E, 1F, 20, 2A, 2E, 2F, 32, 34, 36, 38, 3A, 40, 41, 44, 45, 4E, 50, 53, 55, 5C, 6C, 6D, 6E, 7C, 80, 81, 85, 88, 8C, 8D, 90, 94, 9C, 9E, A0, A4, A5, A6, AD, AF, B4, B7, BA, BB, C0, C8, CD, D0, D4,
D5, DA, E0, F0, F6, F8, F9, FE
Nagy-nagy-nagy többségük (>90%) csak egyszer fordul elő, a 00 kívüli leggyakoribbak is 4-szer, a 00-át meg gondolom nem kell mondjam (több, mint száz)
Ez a 78 érték már ugye 7 biten ábrázolható, ami már elvileg adna valami tömöríthetőségre lehetőséget szerintem, csak ott vagyok gondban, hogy ezek eléggé változatos, szerteszóródó értékek, hapedig ilyen kis adatmennyiségen úgy oldanám meg az egészet, hogy szótárszerűen felírnám, hogy mely 7 bites értékek milyen 8 bites értékekkel egyenlőek, akkor már a szótár csak több helyet fog elfoglalni, mint az megspórolt hely, és azzal csak vesztek.
Vagyis még az jutott eszembe, hogy úgymond "kerekítek" a mintavételi részeken, és ami itt páratlan értékű, azt párosra kerekítem, és elosztom kettővel. Igaz, úgy már nem teljesen az a hangminta lesz, de egyrészt a ritmus a lényeg, és a zaj milyensége az már másodrendű.
Bár lehet, ha mondjuk 00011111-ról van szó, ami páratlan, és 00100000 lesz belőle, az már a ritmikán is változtat.
Plusz, számomra az sem triviális, hogy 7 bitbe tömörített adatblokkokat hogyan fűzzek bájtokba, RÁADÁSUL : (250*7)/8 nem egész szám, szóval nem is tudom, hogy lehetne.
Esetleg a hiányzó bitekre beszúrok valamit?!
Mindenesetre MEGKÖSZÖNNÉM, ha erre a kérdésre majd kapnék választ, illetve rajtam kívül még három másik embert is érdekelne, akik szintén benne vannak a projectbe!
Eddig, amit angol fórumokon találtam, az az LZS algoritmus, de az is egy 2 Kilobájtos szótárt használ, nekünk meg csak 1 Kilobájt RAM van, és abban még el kell férnie a kitömörített adatnak is!
Légyszíves, aki tudja, írja le, hogy mit lehet tenni!
válasza:Srapnel, RLE alatt erre gondolsz? : [link]
Mert ezzel az a baj, hogy az igaz, hogy az adatblokkban vannak olyan részek, ahhol több 00 van egymás után, viszont a többi ponton nincsenek ismétlődő részek, sőt, mint írtam, az ott előforduló értékek nagy valószínűséggel csak egyszer fordulnak elő az egész kódban, tehát azoknál meg elveszne az, amit az ismétlődő részeknél spórolni tudnék. (márha jól fogom fel az RLE lényegét)
A Huffmanhoz esetleg van olyan implementációd, amit így tudnék használni?
válasza:A Huffmannal az a gond, hogy nagyon kevés a RAM.
Maradjunk a Run-Length Encodingnál.
Mivel szótárat sem használhatsz, mert az megint csak a RAM jelentős részét elvenné, ezért csinálhatod a következőt:
A kódolt byte sorozat kis blokkokból állna:
[NX X1 X2 ... Xn][N0][NY Y1 Y2 ... Yn][N0]...
Két blokk fajta lenne:
- Az egyik a nem 0 értékeket sorolja fel úgy, hogy az első bájt megmondja, hány nem 0 érték következik, majd az értékek maguk.
- A másik blokk csak a 0-k darabszámát adja meg.
Az előző két blokk felváltva lenne a bájtlistában.
Az alábbi részlet tömörítés nélkül:
"2A 1D 34 00 00 00 00 00 CD 3A 00 00 00 00 00 40 A5 06 BA 0B 00 00 00 00 00 00 00 00 00 00 00"
Tömörítve így nézne ki:
"03 2A 1D 34 05 02 CD 3A 05 05 40 A5 06 BA 0B 0B"
A megadott példádban pl. egyik blokk sem hosszabb 15 elemnél, ezért a 0-k számát a legelső elemszám valamely 4 bitjébe be lehetne kódolni, tehát:
"35 2A 1D 34 25 CD 3A 5B 40 A5 06 BA 0B"
Részleteiben:
A 35 azt mondja, hogy lesz 3 érték és 5 darab 0. Utána a 3 érték jön (2A 1D 34), ez megy a kitömörítettbe, majd 5 darab nulla, aztán jön a következő blokk. A 25 azt jelenti, hogy 2 érték és 5 darab nulla. A két érték a 25 után van (CD 3A). Stb.
Ha esetleg értékekből több van, mint 15, az sem gond, mert több 15 hosszú blokk jöhet egymás után 0 darab nullával. Hasonlóan kezelhető a 15-nél hosszabb nulla sorozat: akkor az értékek száma 0.
válasza:Ja és a kitömörítés nagyon egyszerűen működne.
Ha pl. a tömörített sorozatot egy 0 byte zárná le, akkor kell egy pointer (c) a tömörített elejére, meg egy másik a tömörítés nélküli terület elejére (d).
A kitömörítés C-szerű elemekkel vegyített pszeudokódja ilyesmi lenne:
ciklus:
a = *(c++) // vagyis a c által mutatott érték a-ba és c inkrementálása
if(a == 0) exit
b = a // a értékének másolása b-be
a = a >> 4 // a eltolása jobbra 4 bittel
while(0 < a--) {
*(d++) = *(c++)
}
b = b & 0x0F
while(0 < b--) {
*(d++) = 0
}
goto ciklus
Óóóó, ez nagyon jó! Valami ilyesmire vágytam!
És még értem is!!!
Huh, nagyon-nagyon szépen köszönjük az ötletedet!
Kár hogy ilyesmi egyikünknek sem szokott az eszébe jutni! :(
Ezzel már ha jól látom a példának felhozott adatsort kb. a 3/4-ére össze lehetne húzni!
Bár azóta rájöttünk (rájöttem, mert az én ötletem volt, hehe), hogy célszerűbb, ha a program egyfajta egyszerű bináris notációt használ a dobra is - ha már a dallamra is, gondoltam -, úgy, mint a dobgépek.
Valami ilyesminek az analógiájára gondolok : [link]
Csak ez lenne egyetlen sávon.
A legkisebb elemi egység 125 minta lenne - amit a fent (úgymond veszteséges tömörítéssel) leíró adatnak a hangos megfelelőjéből vettem :D -, 16000 Hz-en, ami ugye kerekítve 8 ezredmásodperc. Ez elég pontos felosztást ad arra, hogy akár trükközni is lehessen érdekes hangzások előállításához (az adott igen szűk körülményekhez képest).
Itt akkor egy pontosan 4 másodperces dobsávot (16 KHz-en ugye) 512 elemi egységre lehetne bontani.
A dobsáv maga úgy lenne felírva, hogy sorfojtonosan a bitek által le van írva, hogy az adott soron levő pozíción egy "elemi egység" idejéig zaj van, vagy csend. Ez is ugyebár két állapot, így egy 4 másodperces dobsávot, 64 byte-on lehetne leírni.
És ott még mindig lenne csomó 0 - legalábbis egy természetesnek ható ritmikával megírt dobsávon -, amin a Te remek tömörítésedet lehetne alkalmazni :D
Ehhez még egyébként - ami hozzátartozik, hogy honnét vehetném a zajmintákat -, észrevettem - kis próbálgatások után audacityben -, hogy nagyon sok hangminta leredukálható úgy 1 bitesre, hogy habár jelentősen torzul a hangzás, nagyon sok minden még felismerhető marad az emberi fül számára. Így akár még zene is, hangszeres játék, sőt, számomra meglepő érthetőséggel emberi (vagy gépi) beszéd is. Így zaj is generálható minden különösebb nehézségek nélkül négyszögjelekből. (tudom, erre már rájöhettem volna akkor, amikor megcsináltam azt az első dobsávot, aminek a kódolt formája a kérdésben is benne van)
Ehhez csak azt kell megnézzem, hogy egy ilyen audacityben megcsinált 1 bites zajban milyen különböző kitöltési tényezők fordulnak elő. Ezt mondjuk könnyedén megnézhetem úgy, hogy C-ben egy bájtsorba beolvasom a hangfájlt, és megnézem, hogy milyen hosszú egybefüggő egyértékű blokkok fordulnak elő a két szélsőértékből.
Ezután már a mikrokontrollerrel megoldható, hogyha a 64 byte-os dobsávon néz egy bitet, és az 1, akkor egy a már fent említett (kitöltési tényezők alapján vett) értékminták szerint "bekalibrált" véletlenszámgenerátorral generál 125 bináris állapotot, és azt kiküldi mondjuk a hangszóróra (ha meg a dallam is rájön, akkor hozzáadja, azt úgy). (ha meg 0-ás értéket lát a sorban, akkor ott 125 mintáig csend van a dobsávban)
válasza:Mi lenne, ha a dobot úgy tárolnád, ahogy azt évszázadok óta szokták: kottával. :)
Úgy értem az egyes ütőfelületekhez megadod, hogy milyen hosszúságú hangjegy tartozik hozzá ("ti-ti-tá" ugye).
Ha csak nem valami bonyolult jazz, vagy progrock darabot szeretnél így kódolni, akkor kb. az alábbiak elegendőek: egész, fél, negyed, nyolcad, tizenhatod, ha emellé a pontozottakat is felveszed, meg esetleg a kistriolát, nagytriolát, akkor kb. minden pop/rock/folk szám lefedhető.
További kottatrükk ugye az ismétlés, ráadásul a dob tipikusan ismétlődő mintákból áll, ezért lehet ott is segíteni a dolgon.
Meg aztán a dallamokat be a flash-be, hangmintákat be a flash-be, aztán semmi mást nem kell csinálni, mint a RAM-ban csak pointerek, meg számlálók legyenek, amik a flash-ben lévő kottán lépkednek és a kotta utasításait elvégzik. Ha a flashből túl lassú az olvasás, vagy kényelmetlen, akkor meg a kottát a ram-ba kell másolni, ennyi.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!