Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Efikasna korekcija gresaka

[es] :: Art of Programming :: Efikasna korekcija gresaka

[ Pregleda: 3142 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

blaza
n/a

Član broj: 961
Poruke: 743
*.yu1.net.



+3 Profil

icon Efikasna korekcija gresaka19.12.2004. u 09:57 - pre 234 meseci
Problem je sledeci:
*Vise CD-ROM image fajlova (tipa .iso, .nrg) (velicine 100-1000mb) snima se na DVD (velicine 4483mb).
*Zajedno sa image fajlovima na DVD se snima text fajl sa spiskom MD5 cheksum-a za svaki od image fajlova. U svakom trenutku je moguce brzo utvrditi da li je integritet odredjenog image fajla narusen poredjenjem izracunate MD5 ckeksum vrednosti sa podatkom iz text fajla.
*Potrebno je obezbediti mehanizam za korekciju jednog broja potencijalnih gresaka koje mogu nastati pri eksploataciji DVD-a. Posmatramo greske tipa:
- proizvoljan bit u fajlu je invertovan
- proizvoljan blok bajtova u fajlu je pogresan
*Navedene greske mogu biti visestruke.
*Mehanizam za korekciju gresaka bi na osnovu zdravog fajla kreirao podatke za korekciju. Ovi podaci bi se cuvali na posebnom DVD-u (nerelevantno). Pretpostavka je da integritet podataka za korekciju nece biti narusen. Ukoliko broj i pozicije pogresnih bitova, i broj, pozicije i velicina pogresnih blokova bajtova zadovoljavaju odredjene uslove, na osnovu podataka za korekciju i na osnovu ostecenog fajla bilo bi moguce rekonstruisati zdrav fajl sa zadovoljavajucom tacnoscu.
*Interesuje me, koji algoritam (ili kombinacija algoritama) za korekciju gresaka ce obezbediti najvecu otpornost na greske, pod uslovom da velicina bloka podataka za korekciju bude sto manja.

Na pamet su mi pala najprostija, neodgovarajuca resenja, koja se baziraju na zapisu fajla u kvadratnu matricu i nalazenju XOR vrednosti svih elemenata za svaku kolonu i vrstu (brzo otklanjanje jednostrukih gresaka od jednog bita i mnogo sporije otklanjanje visestrukih gresaka od jednog bita do odredjene granice koju diktira vreme izracunavanja) i podela fajlova na blokove, pronalazenje CRC32(16) za svaki od blokova, i XOR-ovanje svih blokova (otklanjanje svih gresaka koje ne prelaze granice bloka, pod uslovom da su svi ostali blokovi ispravni - Recovery Record mehanizam koji koristi RAR).
Jos nisam konsultovao literaturu; u medjuvremenu svaki komentar je dobrodosao.
Thanks for your input.
O_o
 
Odgovor na temu

zvrba
The Lord of Chaos

Član broj: 31716
Poruke: 105
*.cmu.carnet.hr.



Profil

icon Re: Efikasna korekcija gresaka19.12.2004. u 15:15 - pre 234 meseci
Potrazi na netu Error Correcting Codes (ECC). MD5 _nije_ dobar za tako sto. Pogledaj kako radi RAID. Mislim da RAID5 koristi Reed-Solomon ECC.

BTW:
1. je li ovo neka domaca zadaca ili projekt za fax?
2. u slucaju da je odgovor pod 1. NE: nije li lakse isprziti iste podatke na dva, tri ili vise DVD-ova (broj ovisi koliko vec imas povjerenja u medij)?
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.yu1.net.



+3 Profil

icon Re: Efikasna korekcija gresaka19.12.2004. u 16:58 - pre 234 meseci
MD5 je nezvanicni standard za proveru integriteta fajla, a ne postupak za korekciju gresaka.
Odgovor je NE.
Ako npr. imam 200 DVD-ova sa .iso fajlovima, zeleo bih da imam jedan DVD sa podacima za korekciju, pomocu kojih bi mogao da popravim bilo koji .iso fajl sa bilo kog od tih 200 DVD-ova; ne bih zeleo da imam 200 rezervnih kopija.

O_o
 
Odgovor na temu

masetrt
Marko Djurovic
Programer, Omni-Explorer
Beograd

Član broj: 3129
Poruke: 228
*.nat-pool.bgd.sbb.co.yu.

Sajt: www.vast.com


+2 Profil

icon Re: Efikasna korekcija gresaka20.12.2004. u 09:21 - pre 234 meseci
Evo jedna ideja. Postupak bi bio slican kao provera i uklanjanje gresaka pri zapisu i citanju na magnetne trake (ako ih se neko jos seca). Naime traka je imala 9 traka po sirini. U osam bi se upisivao bajt , a u devetu parnost setovanih bitova. E slicno po duzini, na kraju bi se zapisala parnost setovanih bitova u jednoj traci. Tako je moguce tacno utvrditi na kojoj traci i u kom bajtu se greska javila. Sto se tice brzine pa i nije nesto brzo ali je prosto za realizaciju.
His majesty Grand Duke of Shumadija and Western Pomoravlje
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.yu1.net.



+3 Profil

icon Re: Efikasna korekcija gresaka20.12.2004. u 17:11 - pre 234 meseci
Resenje koje si predlozio moze se koristiti za korekciju jedne jednobitne greske, i za detekciju ostalih tipova gresaka. Ako je fajl duzine X bajtova, podaci za korekciju bi zauzimali 1+X/8 bajtova, znaci jednu osminu fajla.
Kada bi fajl smestio u priblizno kvadratnu dvodimenzionalnu matricu, tako da svaki bit bude element matrice, tada bi podaci za korekciju zauzimali sqrt(X/2) bajtova, sto je manje od 1+X/8 za dovoljno veliko X.
Ako bi postojao postupak na osnovu koga bi mogli da ustanovimo da li je fajl ispravan ili ne, (npr. provera MD5 ili CRC32 checksum-a), opisanim postupkom bi se mogle otkloniti visestruke jednobitne greske. Ako npr. imam dva neslaganja po horizontali i tri po vertikali, 6 bitova su problematicni. Kako postoji 2^6 = 64 razlicite kombinacije, izracunavanjem MD5 ili CRC32 checksum-a za fajl korigovan sa novim bitovima za svaku od 64 kombinacija mogli bi da utvrdimo koja je kombinacija dobitna, tj. mogli bi da rekonstruisemo originalni fajl. Posto provera MD5 ili CRC32 checksum-a fajla traje, a u slucaju da postoji veci broj neslaganja po vertikali i horizontali, duzina izracunavanja bi diktirala broj visestrukih jednobitnih gresaka koje je moguce otkloniti.
Pri kopiranju proizvoljnog fajla sa optickog medijuma na HDD, primetio sam da dolazi do 4 karakteristicne greske:
1.-Fajl se bez problema prekopira na HDD, s time sto je par bitova invertovano.
2.-Kopiranje 'puca', i sistem prijavljuje gresku tipa "CRC32 error - file corrupted".
3.-Kopiranje 'puca', i sistem prijavljuje gresku tipa "Error. Cannot access sector xyz".
4.-Kopiranje 'puca' uz gresku tipa "File not accessible".
Postoje alati (BadCopy i dr.) pomocu kojih je moguce spasiti veci deo fajla u slucaju da dodje do greske pri citanju. Za gresku pod 4 nisam siguran. Prilikom spasavanja u idealnom slucaju problematican deo fajla se gubi - sadrzaj se zamenjuje, ali se duzina fajla ne menja.
Mehanizam za korekciju bi trebao da obezbedi nacin da se fajl rekonstruise nakon spasavanja. Ako npr. fajl podelim na jednake blokove, tako da svaki CDFS sektor sadrzi podatke iz samo jednog bloka, i ako XOR-ujem sve te blokove, i dobijeni podatak sacuvam, ako nadjem CRC32 za svaki od tih blokova, kasnije, u slucaju da se nekom klasteru ne moze pristupiti, nakon spasavanja fajla, ja sam u stanju da na osnovu raspolozivih podataka rekonstruisem tacan sadrzaj problematicnog bloka.
Posto trenutno nemam vremena da se bavim ovim stvarcicama, 'projekat' sam prebacio u 'waiting queue'. Uskoro nastavljam; u medjuvremenu, sve ideje su dobrodosle.
O_o
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.yu1.net.



+3 Profil

icon Re: Efikasna korekcija gresaka26.12.2004. u 19:27 - pre 234 meseci
Na osnovu procitanih tekstova dosao sam do zakljucaka:
1.Korekciju gresaka ne treba implementirati na nivou fajla, vec na nivou fizickog zapisa. Znaci, ako dodje do izmene sadrzaja/ostecenja jednog ili vise fajlova, pomocu bilo kog DVD imidz jutilitijia bi se skidao DVD imidz .iso fajl, a zatim bi se taj fajl "popravljao". Ako postojeci ECC lejeri nisu u stanju da poprave ostecenja, sadrzaj odgovarajucih lokacija u .iso fajlu bio bi pogresan. Nas program bi na osnovu "podataka za korekciju" vrsio popravku imidz fajla. Nakon uspesne popravke sve fajlove bilo bi moguce spasiti.
2.Mehanizam za korekciju bi radio po principu:
2.1. Nakon rezanja DVD-a skidao bi se DVD imidz .iso fajl.
2.2. Na osnovu imidz fajla, kreirali bi se podaci za korekciju, na sledeci nacin:
2.2.1. Uspostavlia bi se bijekcija izmedju bitova imidz fajla i bitova priveremenog fajla iste velicine
2.2.2. Svaki bit iz imidz fajla bi se preslikao u neki bit privremenog fajla tako da 2 "bliska" bita iz imidz fajla ne budu "bliski" u privemenom fajlu
2.2.3. Tako dobijeni privremeni fajl bi se podelio na blokove
2.2.4. Na svaki od blokova bi se primenio neki od algoritama za korekciju gresaka unutar bloka u cilju nalazenja "podataka za korekciju" za svaki blok
2.2.5. dobijeni "podaci za korekciju" za svaki od blokova bi se sacuvali
2.2.6. U cilju ustede resursa ceo postupak bi se optimizovao tako da se privremeni fajl zapravo ne bi kreirao, itd...
2.2.7. Cilj svega ovoga je da se greske sekvencijalnog niza bitova (hint: burst errors) rasprse, tako da nisu skoncentrisane na jednom mestu. Ako se pogresni bitovi dobro rasprse, svaki blok za koji postoje "podaci za koreciju" u idealnom slucaju sadrzace najvise par pogresnih bitova, tako da ce gresku biti moguce lako otkloniti.
2.3. Osteceni imidz fajlovi bi se popravljali tako sto bi se istom bijekcijom kreirao privremeni fajl, a zatim bi se pogresni blokovi popravili primenom algoritma za korekciju gresaka unutar bloka na osnovu "podataka za korekciju", nakon cega bi se primenom inverzne bijekcije rekonstuisao "zdrav" imidz fajl. Ceo postupak bi se optimizovao tako da se privremeni fajl nikada ne bi kreirao.

Ako neko misli da je sve ovo nepotrebno, neka slobodno pomocu nekog CD/DVD jutilitija proveri par diskova koje poseduje neko vreme. (hint: Surface scan + File Scan).
O_o
 
Odgovor na temu

[es] :: Art of Programming :: Efikasna korekcija gresaka

[ Pregleda: 3142 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.