Korekcja błędów Reeda-Solomona

Inne nazwy: kod Reeda-Solomona, kod RS, Reed–Solomon

Definicja

Korekcja błędów Reeda-Solomona to matematyka, dzięki której uszkodzony kod QR nadal się skanuje. Dodaje do danych słowa kontrolne, żeby czytnik mógł odtworzyć brakujące lub błędne bajty, do ustalonej granicy.

Sprawdzone przez zespół AriaQR ·

Obejrzyj odcinek · 2:06Why Damaged QR Codes Still Scan: Error Correction Levels Explained
Korekcja błędów Reeda-Solomona

Pochodzenie i szersze zastosowanie

Kody Reeda-Solomona opisali Irving S. Reed i Gustave Solomon w 1960 roku. Działają na całych symbolach, zwykle bajtach, a nie na pojedynczych bitach, przez co dobrze radzą sobie z seriami uszkodzeń, jak zarysowanie czy smuga.

Ta sama rodzina kodów chroni dane na płytach CD, DVD i Blu-ray, w niektórych łączach telewizji cyfrowej i satelitarnych oraz w innych kodach 2D, w tym Data Matrix ECC 200, kodzie Aztec i PDF417.

Jak używają go kody QR

Kod QR traktuje każde 8-bitowe słowo kodowe jako element ciała skończonego GF(256), zbudowanego za pomocą wielomianu pierwotnego x^8 + x^4 + x^3 + x^2 + 1 (szesnastkowo 0x11D). Słowa kodowe danych dzieli się przez wielomian generujący, a reszta staje się słowami kodowymi korekcji błędów dołączanymi do nich.

Większe kody dzielą dane na kilka bloków, każdy z własnymi słowami kodowymi korekcji błędów. Bloki są następnie przeplatane przy układaniu słów kodowych w siatce, żeby pojedyncza plama uszkodzenia rozłożyła się na wiele bloków, zamiast przytłoczyć jeden.

Ile potrafi naprawić

Przy n słowach kodowych korekcji błędów w bloku dekoder może poprawić do n/2 słów kodowych o nieznanym położeniu albo do n słów kodowych o znanym położeniu, zwanych wymazaniami. Przypadki mieszane podlegają regule, że każdy błąd liczy się podwójnie, a każde wymazanie raz.

Dlatego kod z czystym, płaskim obszarem zasłoniętym logiem może się nadal skanować: inteligentny czytnik może potraktować zasłonięty obszar jako wymazania, natomiast losowe uszkodzenia są trudniejsze do naprawy, bo dekoder musi je najpierw znaleźć.

  • Błędy o nieznanym położeniu: do połowy liczby słów kodowych EC
  • Wymazania (znane położenia): do liczby słów kodowych EC
  • Ciało: GF(256), wielomian 0x11D
  • Bloki są przeplatane, żeby rozłożyć seryjne uszkodzenia

Najczęstsze pytania

Czym jest Reed-Solomon w kodzie QR?

To metoda korekcji błędów, która dodaje do danych dodatkowe słowa kodowe. Skaner używa ich do odtworzenia słów kodowych, które są uszkodzone lub nieczytelne.

Kto wynalazł kody Reeda-Solomona?

Irving S. Reed i Gustave Solomon, którzy opublikowali je w 1960 roku. Kody są dziś używane na płytach optycznych, w łączności i w większości kodów 2D.

Dlaczego kod QR z logo pośrodku nadal może działać?

Logo zasłania moduły, które korekcja błędów Reeda-Solomona potrafi odtworzyć. Działa to, dopóki zasłonięty obszar mieści się w możliwościach korekcji błędów, a wzorce wyszukiwania są wolne.

Źródła i normy

Wszystkie hasła