Dane naprawcze- jak działają?

0

Witam
Moje poszukiwania nie przyniosły zadowalających rezultatów, więc zdecydowałem się zapytać:

Czy mógłby ktoś wytłumaczyć, we w miarę nie skomplikowany sposób jak działają dane naprawcze w archiwach np. rar? W jaki sposób z 10% objętości archiwum jesteśmy w stanie odtworzyć dowolny brakujący fragment?

Z góry dzięki;)

1

Przeczytaj jak działa RAID

Przykład: wyobraź sobie że do każdej sekwencji 7 bitów danych wejściowych dodajesz jeden bit określający parzystość pozostałych 7 (tzn. np. jeśli wśród tych 7 bitów była parzysta liczba jedynek to nasz dodatkowy bit wynosi 1 a jeśli liczba jedynek była nieparzysta to 0). Jeśli teraz którykolwiek z tych 8 bitów ulegnie uszkodzeniu to możemy go "odzyskać". Jeśli uszkodził się nasz dodatkowy, ósmy bit, to po prostu obliczamy na nowo parzystość. Jeśli uszkodził się inny to znów obliczamy parzystość a następnie sprawdzamy z naszym dodatkowym bitem czy brakuje nam 0 czy 1.
Dzięki temu uzyskaliśmy możliwość odzyskiwania uszkodzonych danych, o ile uszkodzone jest nie więcej niż 1 bit w bajcie, a kosztowało nas to 1 bit na każde 7 bitów danych, czyli narzut to niecałe 15%.

1

Dane naprawcze są implementacją kodowania Reeda-Solomona: http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

Zamiast R-S można by zastosować dużo prostszą metodę z dużo gorszymi, ale nadal pozytywnymi rezultatami.
Schemat:

  • dzielimy dane na N bloków,
  • dodajemy (N+1)-szy blok, o rozmiarze największego bloku, który zawiera XORa wszystkich poprzednich bloków (jeśli któryś blok jest krótszy to się do wyrównuje przy XORowaniu),
  • do każdego z tych (N+1) bloków dodajemy sumę kontrolną by sprawdzić integralność danych,
  • po odebraniu danych sprawdzamy sumy kontrolne,
  • jeżeli wszystko jest OK to nic nie robimy,
  • jeżeli więcej niż jedna suma kontrolna wskazuje na błędne dane w bloku to jesteśmy w lesie,
  • jeśli tylko jeden blok jest uwalony, to odtwarzamy go XORując wszystkie pozostałe (wraz z (N+1)-szym blokiem),
1

Do tego nie trzeba nawet Reedów-Salomonów. Prosta zasada. Załóżmy że mamy dwie liczby dane:

a = 42
b = 666

tworzymy trzecią, według jakiegoś schematu. Może być nawet prosta suma:

a = 42
b = 666
c = 708

pod warunkiem że wiemy która jest daną a która liczbą kontrolną, i jak ta liczba kontrolna powstała, można odtworzyć dowolną jedną z nich na podstawie dwóch pozostałych:

a = c - b
b = c - a
c = a + b

Rzeczywiste algorytmy są bardziej skomplikowane, ale wszystkie opierają się na tej zasadzie: wyliczenie brakującej danej na podstawie pozostałych.

0

Dziekuję, już mniej więcej rozumiem o co chodzi:)

1 użytkowników online, w tym zalogowanych: 0, gości: 1