9. Kodowanie -- kontrola błędów

Magiczna sztuczka z parzystością (na powyższym filmie) umożliwia magikowi wykrycie, która z dziesiątek kart została odwrócona, gdy nie patrzył. Magia tej sztuczki to w rzeczywistości informatyka, wykorzystująca tę samą technikę, której używają komputery do wykrywania i korygowania błędów danych. Pokażemy, jak to działa, w następnym podrozdziale.

To samo dzieje się z danymi przechowywanymi na komputerach -- gdy ty (lub komputer) ich nie obserwujesz, niektóre z nich mogą się przypadkowo zmienić z powodu drobnej usterki. Nie chcielibyśmy, żeby komputer tak po prostu użył nieprawidłowych wartości, kiedy już je odczyta. Chcielibyśmy, żeby przynajmniej wykrył, że coś poszło nie tak, a najlepiej by było, gdyby zrobił to, co magik, czyli naprawił.

W tym rozdziale chodzi o ochronę przed błędami w danych w różnych postaciach -- w danych przechowywanych na dysku twardym, na dysku CD, dyskietce, dysku SSD (na przykład w telefonie komórkowym, aparacie lub odtwarzaczu mp3), danych znajdujących się w danej chwili w pamięci RAM (szczególnie na serwerach, w których poprawność danych jest niezwykle ważna), danych przepływających pomiędzy pamięcią RAM i dyskiem twardym lub między zewnętrznym dyskiem twardym a wewnętrznym dyskiem twardym, danych przetwarzanych właśnie w procesorze, czy danych przesyłanych przez sieci przewodowe lub bezprzewodowe, na przykład z twojego komputera na serwer po drugiej stronie świata. Obejmuje takie dane, jak kody kreskowe wydrukowane na produktach czy numery na kartach kredytowych.

Jeśli nie wykryjemy, że dane zostały zmienione przez jakiś problem fizyczny (na przykład małą rysę na płycie CD lub uszkodzony obwód w pamięci flash), niepoprawna informacja zostanie po prostu użyta. Bardzo źle napisany system bankowy może potencjalnie doprowadzić do zmiany salda twojego rachunku, gdyby tylko jeden z bitów w liczbie został zmieniony przez promień kosmiczny, wpływając na wartość w pamięci komputera! Jeśli kod paskowy na paczce czipsów zakupionej w sklepie zostanie zeskanowany nieprawidłowo, może zostać naliczona opłata za szampon. Jeśli prześlesz plik muzyczny z laptopa do odtwarzacza mp3, a kilka bitów zostało przesłanych nieprawidłowo, odtwarzacz mp3 może odtworzyć muzykę z irytującymi usterkami. Kody kontroli błędów chronią przed tym wszystkim, więc (zwykle) wszystko po prostu działa i nie musimy się obawiać takich błędów.

Dane mogą zostać przypadkowo zmienione z wielu powodów. Niektóre sieci mają dużo ,,szumu'' (spowodowanego złą jakością okablowania, zakłóceniami elektrycznymi lub -- w przypadku sieci bezprzewodowych -- zakłóceniami z innych sieci). Bity na dyskach są bardzo małe, a niedoskonałości na powierzchni mogą w końcu spowodować uszkodzenie pamięci. Powierzchnie na dyskach kompaktowych i DVD są odsłonięte i mogą być łatwo uszkodzone podczas przechowywania (na przykład w wysokiej temperaturze lub wilgotności) lub używania (na przykład przez zadrapania albo kurz). Błędy mogą również wystąpić przy wpisywaniu liczb, na przykład przy wprowadzaniu numeru konta bankowego w celu dokonania płatności lub numeru kontenera, który jest ładowany na statek. Kody kreskowe na produktach mogą być lekko zarysowane lub poplamione na czarno, albo opakowanie może być zgięte lub nie można go prawidłowo odczytać, ponieważ zbyt szybko przesunięto nad nim skaner. Zmiana bitów w pamięci trwałej (takiej jak dyski twarde, dyski optyczne i dyski półprzewodnikowe) jest czasami nazywana gniciem danych, a angielska strona Wikipedii o gniciu danych zawiera listę innych sposobów, w jakie mogą wystąpić te błędy.

Nikt nie chce komputera, który nie jest wiarygodny i nie robi tego, co powinien robić z powodu zmian bitów! Jak więc poradzić sobie z tymi problemami?

Kodowanie z korekcją błędów służy do wykrywania kiedy te błędy występują, a jeśli jest to możliwe i niezbyt kosztowne, poprawianie danych tak, aby wróciły do pierwotnej postaci.

Niektóre schematy kontroli błędów zawierają wbudowane kody korekcji błędów, takie jak metoda parzystości, o której wspomnieliśmy na początku tego rozdziału. Być może nie zrozumiałeś jeszcze, jak działała sztuczka z parzystością, ale po odwróceniu karty magik wykrył, która karta została przewrócona, i mógł ją poprawić.

Inne schematy kontroli błędów, takie jak te, które działają przy wysyłaniu danych z serwera za granicą do twojego komputera, wysyłają dane w bardzo małych fragmentach zwanych pakietami (mówi o tym rozdział o protokołach sieciowych) i każdy pakiet ma dodane informacje o wykryciu błędu.

Wykrywania błędów używa się również przy numerach kodów kreskowych na zakupionych produktach, numerach ISBN (International Standard Book Number), które mają wszystkie książki, a nawet 16-cyfrowych numerach na kartach kredytowych. Jeśli którykolwiek z tych numerów zostanie wpisany lub zeskanowany niepoprawnie, istnieje duża szansa, że ​​błąd zostanie wykryty, a użytkownik może zostać poproszony o ponowne wprowadzenie danych.

Po przeczytaniu tego rozdziału powinieneś rozumieć: podstawową ideę kodowania kontroli błędów, powody, dla których tego wymagamy, różnice między algorytmami, które mogą wykrywać błędy, a tymi, które mogą zarówno wykrywać, jak i korygować błędy, a także znać niektóre z tych algorytmów, w szczególności parzystość (skupiając się na sztuczce parzystości) i cyfry kontrolne używane do zapewnienia prawidłowego wprowadzania numerów książek, numerów kodów kreskowych i numerów kart kredytowych.

Jeśli nigdy wcześniej nie widziałeś sztuczki z parzystością, obejrzyj wideo, które jest na początku rozdziału. Zakładamy w tym podrozdziale, że wiesz, co to znaczy sztuczka z parzystością, a teraz wyjaśnimy, jak ona działa!

Magik prosi obserwatora, aby ułożył dwustronne karty w kwadracie, a następnie magik mówi, że uczyni zadanie nieco trudniejszym, dodając do kwadratu dodatkową kolumnę i rząd. Magik odwraca się, a obserwator odwraca jedną z kart. Magik znowu się odwraca i mówi obserwatorowi, która karta została odwrócona!

Teraz pytanie brzmi: skąd magik wiedział, która karta została przewrócona, nie oglądając odwróconej karty, ani nie zapamiętując układu?! Krótko mówiąc, odpowiedzią jest korekcja błędów. Przyjrzyjmy się temu bliżej...

W poniższej aplikacji komputer ma kwadrat 7x7 z czarno-białych kart. Musisz wybrać kolor dodatkowej karty dla każdego rzędu (po prawej) i kolumny (na dole), tworząc kwadrat kart 8x8. Każda dodatkowa karta powinna zostać wybrana tak, aby każdy rząd i kolumna zawierały parzystą liczbę białych kart (ponieważ jest 8 kart w linii, liczba czarnych kart będzie również parzysta). Kartę w prawym dolnym rogu zawsze można wybrać tak, by jej wiersz i kolumna też miały parzystą liczbę białych pól.

Kiedy uznasz, że wszystko jest dobrze, powinieneś polecić komputerowi odwrócić kartę. Przez kilka sekund będzie pokazywana animacja, a następnie karty pojawią się ponownie, z jedną odwróconą kartą (cała reszta będzie taka sama jak poprzednio). Twoim zadaniem jest zidentyfikowanie odwróconej karty. Powinieneś to zrobić bez zapamiętania układu kart. Pamiętasz wzorzec, według którego dodawałeś dodatkowe karty? To on jest kluczem. Gdy uznasz, że zidentyfikowałeś kartę, kliknij ją, aby sprawdzić, czy masz rację. Aplikacja poprowadzi cię krok po kroku. Jeśli całkowicie utknąłeś podczas identyfikacji odwróconej karty, w aplikacji pojawi się podpowiedź, chociaż powinieneś najpierw spróbować ją znaleźć sam. Upewnij się, że dodajesz dodatkowe karty poprawnie; komputer nie powie ci, jeśli źle je ustawisz i prawdopodobnie nie będziesz w stanie zidentyfikować odwróconej karty, jeśli dodatkowe karty nie zostaną ustawione poprawnie.

Sztuczka z parzystością. Kliknij, by załadować.

Pamiętasz, jak ustawiałeś karty tak, aby każda kolumna miała parzystą liczbę białych kart? Kiedy karta zostaje odwrócona, powoduje to, że w wierszu i kolumnie znajduje się nieparzysta liczba białych kart. Wszystko, co musisz zrobić, to zidentyfikować rząd i kolumnę, które mają nieparzystą liczbę białych kart, a wtedy karta, która znajduje się na ich przecięciu, musi być tą, która została odwrócona!

To, co zobaczyliśmy powyżej, to prosty algorytm korekcji błędów, znany jako 2-wymiarowa kontrola parzystości.

Karty reprezentują bity, przy czym ich dwa stany to czerń i biel (w rozdziale o reprezentacji danych analizowaliśmy, jak bit może być przechowywany przez cokolwiek, co może być w jednym z dwóch stanów: błyszczący / matowy, namagnesowany / nienamagnesowany , wysokie napięcie / niskie napięcie, czerń / biel itp.). Karty w kracie 7x7, które komputer dla ciebie przygotował, mogą być jakimiś danymi, na przykład tekstem reprezentowanym za pomocą bitów, obrazem lub jakimiś liczbami. Chociaż są one rozmieszczone na kracie, na komputerze wiersze bitów będą przechowywane i przesyłane jeden po drugim (jako 8 partii po 8 bitów każda).

Dodatkowe, dodane przez ciebie karty są nazywane bitami parzystości. Parzystość oznacza po prostu, czy liczba jest parzysta czy nieparzysta (słowo pochodzi od tego samego rdzenia co ,,para''). Dodając dodatkowe karty w taki sposób, aby zapewnić parzystą liczbę białych kart w każdym rzędzie i kolumnie, sprawiłeś, że wiersze i kolumny miały tzw. własność parzystości.

Odwrócenie karty symulowało błąd w danych (np. kawałek kurzu lądujący na dysku CD lub promień kosmiczny zmieniający bit na dysku twardym, lub zakłócenia elektryczne zmieniające bit wysyłany przez kabel sieciowy). Ponieważ wiedziałeś, że w każdym wierszu i kolumnie powinna znajdować się parzysta liczba białych kart, byłeś w stanie stwierdzić, że wystąpił błąd, na podstawie faktu, że w kolumnie i wierszu była nieparzysta liczba białych kart. Oznacza to, że algorytm jest w stanie wykryć błędy, czyli była to detekcja błędów. Konkretna karta, która została odwrócona, znajdowała się na przecięciu wiersza i kolumny z nieparzystą liczbą białych kart, a ponieważ byłeś w stanie dokładnie określić, która karta została odwrócona, byłeś w stanie poprawić błąd. Tym samym to też algorytm korekcji błędów.

Gdybyś nie dodał bitów parzystości, nie byłbyś w stanie nawet stwierdzić, że wystąpił błąd, chyba że zapamiętałeś cały układ kart! A co by było, gdyby odwrócono więcej niż jedną kartę? Rozważymy to później.

W tym momencie powinieneś umieć wykonać sztuczkę z parzystością na tyle dobrze, że widać, że ją rozumiesz. Pozostała część tego rozdziału skupia się na dalszym badaniu pomysłów dotyczących korekcji błędów, związanych ze sztuczką z parzystością.

Najlepszym rozwiązaniem byłoby posiadanie fizycznych kart parzystości, które można rozmieścić przed sobą i przestawiać w trakcie rozważania postawionych pytań.

Algorytm korekcji błędów często łatwiej wykrywa błędy, niż je poprawia. Błędy na wielu bitach mogą czasami nawet pozostać zupełnie niewykryte. Co się stanie, jeśli komputer (lub twój przyjaciel, jeśli byłeś magikiem z prawdziwymi kartami parzystości), był sprytny i odwrócił dwie karty zamiast jednej? Możesz zacząć od namówienia przyjaciela lub kolegi z klasy, aby to zrobił. Powtórz to kilka razy. Czy zawsze potrafisz poprawić błędy, czy też czasem źle zgadujesz?

Pamiętaj, że aby wykryć błędy za pomocą tego algorytmu, wystarczy zauważyć że jeden lub więcej wierszy i / lub kolumn ma nieparzystą liczbę czerni i bieli -- wtedy musi istnieć co najmniej jeden błąd. Aby poprawić błędy, trzeba wskazać konkretne karty, które zostały odwrócone.

Czy zawsze jesteś w stanie wykryć, kiedy wystąpił błąd, jeśli zostały odwrócone 2 karty? Czemu? Czy zawsze jesteś w stanie poprawić błąd? A co gdyby były to 3 karty?

Okazuje się, że zawsze można wykryć błąd po odwróceniu 2 kart (tj. błąd 2-bitowy), ale system nie może naprawić błędu większego niż 1-bitowy. Kiedy dwie karty są odwrócone, będą co najmniej dwie opcje jak odwrócić dwie karty w celu przywrócenia parzystości, a ty nie będziesz wiedział, która z nich jest właściwa. Przy 3-bitowym błędzie (odwrócone 3 karty) zawsze będzie można wykryć błąd (nieparzystą liczbę białych bitów w co najmniej jednym rzędzie lub kolumnie), ale nie zawsze będzie można dokonać korekty. Przy odwracaniu 4 kart jest możliwe (choć niezbyt prawdopodobne), że błąd może pozostać niewykryty.

Rzeczywiście istnieje sposób na odwrócenie 4 kart tak, by błąd pozostał niewykryty, to znaczy żaden algorytm nie wykryje błędu inaczej niż przez przypadek. Czy potrafisz znaleźć znaleźć ten sposób?

Dzięki większej liczbie kart parzystości możemy wykryć i ewentualnie poprawić więcej błędów. Przyjrzyjmy się bardzo prostemu systemowi z minimalnymi liczbą kart parzystości. Możemy mieć tablicę 7x7 z danymi i tylko jedną kartę parzystości. Ta karta parzystości sprawia, że w całym układzie znajduje się parzysta liczba białych kart (w tym karta parzystości). Jak można tego użyć do wykrywania błędów? Czy jesteś w stanie kiedykolwiek poprawić błędy w tym systemie? W jakich sytuacjach błędy pozostają niezauważone? Rozważ sytuacje z różną liczbą błedów (tzn. odwróconych kart).

Przy użyciu tylko jednej dodatkowej karty do sprawdzania parzystości można wykryć błąd pojedynczego bitu (całkowita liczba czarnych kart stanie się nieparzysta), ale 2-bitowy błąd nie zostanie wykryty, ponieważ liczba białych kart będzie ponownie parzysta. Zostanie wykryty 3-bitowy błąd, ale ogólnie rzecz biorąc, ten system jest dość zawodny.

Wracając do powyższej sztuczki z parzystością, w której była tablica 7x7 i 15 kart parzystości rozszerzających tablicę do wymiaru 8x8, warto zauważyć, że potrzebna była tylko jedna dodatkowa karta do wykrycia, że wystąpił błąd, ale aż 15 dodatkowych do poprawienia błędu. Można powiedzieć, że w algorytmie znacznie więcej miejsca kosztuje poprawianie błędów, niż po prostu ich wykrywanie!

Co się dzieje, gdy używamy tablicy o innych rozmiarach? Wiersz czy kolumna nie musi mieć parzystej liczby białych kart i parzystej liczby czarnych kart, po prostu tak akurat jest w przypadku tablicy o parzystym boku (np. o najczęściej w tym podrozdziale używanym rozmiarze 8x8).

Rozszerz tablicę 6x6 za pomocą kart parzystości do tablicy 7x7. Karty parzystości muszą sprawić, że każdy rząd i kolumna ma parzystą liczbę białych kart (w tym przypadku zawsze będzie nieparzysta liczba czarnych kart w każdym rzędzie i kolumnie). Wykrywanie błędów polega na szukaniu wierszy i kolumn zawierających nieparzystą liczbę białych kart (ale parzysta liczbę czarnych). Co ciekawe, tablica nie musi nawet być kwadratowa! Możesz użyć 4x7 i też będzie działać!

Nie ma również ograniczeń rozmiaru. Możesz utworzyć tablicę 10x10 (100 kart) i nadal możesz wykryć, która karta została przewrócona. Większe tablice czynią magiczną sztuczkę jeszcze bardziej imponującą.

Prawdopodobnie nie byłbyś zadowolony, gdybyś kupił książkę przez Internet, wpisując numer ISBN (International Standard Book Number), i wysłano by Ci niewłaściwą książkę, lub jeśli kilka dni po jej zamówieniu otrzymałbyś email z informacją, że podany numer karty kredytowej nie należał do Ciebie, tylko miał jedną zmienioną cyfrę, a inny posiadacz karty kredytowej poskarżył się na bezprawne obciążenie jego karty. Albo gdybyś poszedł do sklepu kupić puszkę napoju, a skaner odczytał ją jako droższy produkt. Czasami skaner nawet nie odczytuje kodu kreskowego, a operator kasy ręcznie musi wprowadzić numer do komputera -- ale jeśli nie wprowadzi go dokładnie tak, jak widnieje na kodzie kreskowym, może się okazać, że zostanie naliczona opłata za niewłaściwy produkt. Wszystko to są przykłady sytuacji, którym korekcja błędów może zapobiec.

Numery kodów kreskowych, numery kart kredytowych, numery kont bankowych, numery ISBN, numery PESEL, etykiety wysyłkowe (kody kontenerów wysyłkowych -- SSCC) i numery podatkowe zawierają kody korekcji błędów, aby zmniejszyć ryzyko ich wystąpienia. Niektóre cyfry w takich numerach to cyfry kontrolne, które uzyskuje się, wykonując specjalne obliczenia na wszystkich pozostałych cyfrach w numerze. Jeśli na przykład wpiszesz numer karty kredytowej w formularzu internetowym, aby coś kupić, zostanie obliczone, jaka powinna być 16. cyfra, przy użyciu pierwszych 15 cyfr i specjalnego sposobu (w numerach kart kredytowych jest 16 cyfr). Jeśli oczekiwana 16. cyfra nie jest cyfrą, którą wprowadziłeś, można stwierdzić, że wystąpił błąd przy wprowadzeniu numeru i zostaniesz powiadomiony, że numer karty kredytowej jest nieprawidłowy.

W następnym podrozdziale najpierw przyjrzymy się jednemu z najczęściej używanych formatów kodów kreskowych, używanych w większości produktów kupowanych w sklepach. Później rozpatrzymy numery kart kredytowych. Nie musisz rozumieć dlaczego obliczenia działają tak dobrze (jest to zaawansowana matematyka i nie jest to ważne dla zrozumienia ogólnej idei) i chociaż dobrze jest wiedzieć, jakie są obliczenia, nie jest to niezbędne. Więc jeśli matematyka jest dla ciebie wyzwaniem i cię niepokoi, nie panikuj za bardzo, ponieważ to, co oglądamy w tym podrozdziale, nie jest wcale tak trudne, jak mogłoby się początkowo wydawać!

Większość produktów, które można kupić w sklepie, ma kod kreskowy z 13-cyfrowym ,,globalnym numerem handlowym'' (zwanym GTIN-13). Pierwsze 12 cyfr to rzeczywisty numer identyfikacyjny produktu, 13. to cyfra kontrolna wyliczana z pozostałych 12. Nie wszystkie kody kreskowe to GTIN-13, istnieje kilka innych typów. Jeśli jednak kod kreskowy zawiera 13 liczb, to prawie na pewno jest to GTIN-13.

Ostatnia cyfra tych liczb jest wyliczana z pierwszych 12. Jest to bardzo ściśle związane z bitem parzystości, który rozważaliśmy powyżej, gdzie ostatni bit rzędu jest ,,wyliczany'' z wcześniejszych bitów. Kod GTIN-13 pozwala nam wykryć, czy jedna z cyfr nie została wprowadzona niepoprawnie.

Następująca aplikacja sprawdza kody kreskowe GTIN-13. Wprowadź pierwsze 12 cyfr kodu kreskowego, a aplikacja powie ci, jaka powinna być ostatnia cyfra! Możesz zacząć używając numeru kodu kreskowego 9 300675 036009.

Co się stanie, jeśli popełnisz błąd podczas wpisywania 12 cyfr (spróbuj zmienić jedną cyfrę)? Czy można wykryć, że popełniono błąd?

Znajdź inny produkt z kodem kreskowym, np. artykuł spożywczy lub przedmiot papierniczy. Zauważ, że niektóre kody kreskowe są trochę inne -- upewnij się, że kody kreskowe, których używasz, mają 13 cyfr (chociaż możesz też dowiedzieć się, jak działa cyfra kontrolna na innych kodach). Czy aplikacja zawsze jest w stanie określić, czy poprawnie wpisałeś kod kreskowy?

Jeden z następujących numerów produktów zawiera jedną niepoprawną cyfrę. Czy możesz stwierdzić, przy pomocy aplikacji, który z produktów miał nieprawidłowo wpisany numer?

• 9 400550 619775
• 9 400559 001014
• 9 300617 013199

Gdybyś skanował powyższe kody kreskowe w sklepie, niepoprawny musiałby zostać ponownie przeskanowany, a system może stwierdzić, że jest to zła liczba, bez konieczności wyszukiwania w spisie. Zwykle błędy są spowodowane uszkodzeniem samego kodu kreskowego (np. trochę lodu na zamrożonym produkcie, powodujące nieprawidłowy odczyt). Jeśli zostanie wykryty błąd, skaner zwykle wydaje dźwięk ostrzegawczy, aby ostrzec kasjera.

Możesz spróbować wymienić się numerami kodów kreskowych z kolegami z klasy, ale przed podaniem numeru rzuć monetą i jeśli wyjdzie orzeł, zmień jedną z cyfr kodu kreskowego, zanim go podasz. Czy uda im się ustalić, że dostali błędny kod kreskowy?

Jeśli jedna cyfra jest niepoprawna, to wyliczona cyfra kontrolna da inną wartość niż ma cyfra w kodzie, co zasygnalizuje błąd. Tak więc błędy jednocyfrowe zawsze zostaną wykryte, ale co jeśli dwie cyfry ulegną zmianie -- czy zawsze błąd zostanie wykryty?

Co jeśli błąd występuje w samej sumie kontrolnej, ale nie w innych cyfrach -- czy zostanie wykryty?

Ludzie mogą popełniać błędy, przy wprowadzaniu liczb do komputerów i nawet skanery kodów kreskowych mogą błędnie odczytać jakąś cyfrę. Cyfry kontrolne starają się wykryć, że wystąpił błąd i powiadamiają o tym komputer i / lub osobę. Załóżmy, że podajesz numer telefonu komórkowego znajomemu, aby mógł się z tobą później skontaktować. Aby upewnić się, że prawidłowo podałeś numer, możesz poprosić go o natychmiastowe wysłanie SMSa, żeby to potwierdzić (i żebyś też zaraz miał jego numer). Jeśli nie dostaniesz tego SMSa, prawdopodobnie ponownie sprawdzisz numer i odkryjesz, że twój znajomy popełnił błąd, na przykład źle wpisał cyfrę lub odwrócił dwie cyfry leżące obok siebie. Błędy się zdarzają, a dobre systemy zapobiegają irytującym lub nawet poważnym konsekwencjom tych błędów. Jeśli używana jest cyfra kontrolna, istnieje duża szansa, że błąd zostanie wykryty, gdy cyfra kontrolna nie jest zgodna z oczekiwaniami komputera.

Niektóre z ludzkich, typowych błędów to:

• nieprawidłowa jedna cyfra (podstawienie),
• zamiana miejscami dwóch sąsiadujących cyfr (transpozycja),
• brakująca cyfra,
• dodana cyfra.

Dwa ostatnie zostaną zauważone przez niezgodność z oczekiwaną długością liczby; na przykład GTIN-13 ma 13 cyfr, więc jeśli wprowadzono 12 lub 14, komputer natychmiast wie, że coś jest nie w porządku. Wykrycie pierwszych dwóch polega na cyfrze kontrolnej. Co ciekawe, wszystkie jednocyfrowe błędy zostaną wykryte przez popularne systemy sum kontrolnych, a większość transpozycji też zostanie wykryta (czy możesz znaleźć przykłady transpozycji, które nie zostały wykryte, korzystając z powyższej aplikacji?).

Istnieją również mniej powszechne błędy, popełniane przez ludzi:

• nieprawidłowa cyfra w dwóch lub więcej miejscach,
• podwojenie błędnej cyfry, np. umieszczenie 3481120 zamiast 3481220,
• pomieszanie 3 cyfr, np. 14829 zamiast 12489,
• błędy fonetyczne są możliwe, gdy numer został odczytany i wpisany przez kogoś słuchającego (lub czytającego sobie głośno ten numer podczas wpisywania); na przykład ,,trzydzieści'' (30) może być usłyszane jako ,,trzynaście'' (13).

Eksperymentuj dalej. Jakie błędy zostały wykryte? Jakie znajdziesz błędy, które nie zostaną wykryte? Czy typowe błędy prawie zawsze zostają wykryte? Czy potrafisz znaleźć sytuacje, w których nie zostają? Spróbuj znaleźć przykłady tylu różnych rodzajów wykrywalnych i niewykrywalnych błędów, ile tylko możesz.

Pierwsze 12 cyfr kodu kreskowego przedstawia informacje takie jak kraj pochodzenia, producent i identyfikator produktu. 13. cyfra to cyfra kontrolna, wyliczana z pierwszych 12 cyfr. Jest obliczana przy użyciu następującego algorytmu (zobacz także przykład poniżej).

• Pomnóż co drugą cyfrę (począwszy od drugiej) przez 3, a resztę przez 1 (czyli pozostają bez zmian).
• Dodaj wszystkie pomnożone liczby, otrzymując sumę.
• Cyfra kontrolna to ta liczba, którą należałoby dodać do sumy żeby uczynić ją wielokrotnością 10 (tj. ostatnia cyfra sumy powinna wynosić 0). Albo, bardziej formalnie, weź ostatnią cyfrę sumy i jeśli jest 0, to cyfra kontrolna wynosi 0. W przeciwnym razie odejmij ostatnią cyfrę od 10, aby uzyskać cyfrę kontrolną.

Spójrzmy na przykład ilustrujący ten algorytm. Chcemy potwierdzić, że cyfra kontrolna umieszczona na kodzie kreskowym butelki soku była poprawna. Numer kodu kreskowego to 9300675032247. Ostatnia cyfra, 7, to cyfra kontrolna. Bierzemy więc pierwsze 12 cyfr i mnożymy je przez 1 lub 3, w zależności od ich pozycji (9x1+3x3+0x1+0x3+6x1+7x3+5x1+0x3+3x1+2x3+2x1+4x3). Następnie sumujemy wszystkie pomnożone liczby, otrzymując sumę 73. Chcemy dodać taką cyfrę kontrolną, która doprowadzi sumę do najbliższej wielokrotności 10, która wynosi 80. Ta liczba to 7, która jest rzeczywiście cyfrą kontrolną na kodzie kreskowym butelki soku.

Poniższa aplikacja może być używana do wykonywania za ciebie obliczeń. Aby upewnić się, że rozumiesz proces, sam musisz wykonać niektóre czynności; aplikacji możesz użyć do szerokiej gamy systemów z cyfrą kontrolną. Aby sprawdzić numer GTIN-13, wprowadź pierwsze 12 cyfr w miejsce przy którym jest napisane ,,Enter the number here''. Mnożniki dla GTIN-13 można wprowadzić jako 131313131313 (co druga cyfra pomnożona przez 3). To da iloczyny każdej z 12 cyfr pomnożonych przez odpowiednią liczbę. Powinieneś samodzielnie obliczyć sumę iloczynów (liczb w okienkach) i ją wpisać. Następnie otrzymasz resztę z dzielenia przez 10. Aby obliczyć cyfrę kontrolną, należy obliczyć cyfrę potrzebną do dopełnienia tej liczby do 10 (na przykład, jeśli reszta to 8, cyfra kontrolna to 2). Jeśli reszta to 0, to cyfra kontrolna również wynosi 0.

Spróbuj z innymi kodami kreskowymi. Teraz popatrz, co dzieje się w obliczeniach, gdy zmieni się cyfrę, lub dwie cyfry zamieni się miejscami.

Algorytm sprawdzania, czy numer kodu kreskowego został poprawnie wprowadzony, jest bardzo podobny. Można obliczyć cyfrę kontrolną i porównać ją z 13. cyfrą, ale prościej jest liczyć na wszystkich 13 cyfrach.

Pomnóż co drugą cyfrę (począwszy od drugiej) przez 3, a pozostałe przez 1. Łącznie z 13. cyfrą, która jest mnożona przez 1. Dodaj wszystkie pomnożone liczby, aby otrzymać sumę. Jeśli ostatnia cyfra sumy wynosi 0, numer został wprowadzony poprawnie. (To oznacza, że reszta z dzielenia przez 10 wynosi 0).

Kody omówione w tym rozdziale są szeroko stosowane, ale kody najczęściej używane do przechowywania danych są bardziej wyrafinowane, ponieważ muszą radzić sobie z bardziej złożonymi błędami niż zmiana pojedynczego bitu. Na przykład, jeśli płyta CD jest porysowana, albo dysk twardy ma małe uszkodzenie, prawdopodobnie wpłynie to na wiele sąsiednich bitów. Systemy te wykorzystują kody oparte na bardziej zaawansowanej matematyce. Najczęściej używanymi kodami do przechowywania i przesyłania danych są kody Reeda-Solomona i cykliczny kod nadmiarowy (CRC). W przypadku numerów czytelnych dla człowieka, takich jak kody kreskowe, numery bankowe, numery podatkowe, numery PESEL itd., najpowszechniejsze są sumy kontrolne, a algorytm Luhna jest jednym z najczęściej używanych. Większe sumy kontrolne są również używane do sprawdzania, czy pliki zostały pobrane poprawnie. Metoda parzystości jest rodzajem kodu Hamminga.

Wszystkie poniższe materiały są w języku angielskim.

• materiały multimedialne na temat sztuczki z parzystością na stronie CS Unplugged;
• CS4FN udostępnia darmową książkę ze sztuczką z parzystością i kilkoma innymi sztuczkami związanymi z informatyką.
• Techradar zawiera sporo informacji na temat wykrywania i korekcji błędów.
• o kodach korekcji błędów;
• kalkulator wyliczający cyfry kontrolne w popularnych kodach kreskowych.