• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Kod Hamminga



    Podstrony: [1] 2 [3] [4]
    Przeczytaj także...
    Transmisja – proces przesyłania dowolnej wiadomości lub ogólnie danych między nadawcą (nadajnikiem) a odbiorcą (odbiornikiem) zapisanej określonym, zrozumiałym dla obu stron kodem i po określonej drodze. Do transmisji mogą być wykorzystane media transmisyjne przewodowe lub bezprzewodowe.3blue1brown – kanał na YouTube poświęcony matematyce, prowadzony przez Granta Sandersona, którego celem jest przedstawienie pojęć matematycznych w sposób wizualny.
    Historia[ | edytuj kod]

    Richard Hamming pracował dla Bell Labs na komputerze Bell Model V. Dane wejściowe do tego urządzenia były umieszczane na kartach dziurkowanych, które często posiadały błędy. Specjalny kod znajdował te błędy i zapalał lampki ostrzegawcze, aby operatorzy mogli naprawić problem. Jednak po godzinach pracy, kiedy operatorów nie było maszyna sama nie potrafiła skorygować błędów i po prostu zaczynała nowe zadanie.

    Niezawodność (ang. reliability) − własność obiektu mówiąca o tym, czy pracuje on poprawnie (spełnia wszystkie powierzone mu funkcje i czynności) przez wymagany czas i w określonych warunkach eksploatacji (w danym zespole czynników wymuszających).Liczby całkowite – liczby naturalne dodatnie N + = { 1 , 2 , 3 , … } {displaystyle mathbb {N} _{+}={1,2,3,dots }} oraz liczby przeciwne do nich { − 1 , − 2 , − 3 , … } {displaystyle {-1,-2,-3,dots }} , a także liczba zero. Uogólnieniem liczb całkowitych są liczby wymierne i tym samym liczby rzeczywiste, szczególnym przypadkiem liczb całkowitych są: liczby naturalne.

    Hamming pracował w weekendy i był bardzo sfrustrowany koniecznością ciągłego restartowania programów z powodu zawodności czytnika kart. Przez kolejne kilka lat pracował nad problemem korekcji błędów. W roku 1950 opublikował efekt swojej pracy, znany dzisiaj jako kod Hamminga.

    Kody poprzedzające kod Hamminga[ | edytuj kod]

    Kilka prostych detekcyjnych kodów było używanych wcześniej, ale żaden nie był tak efektywny jak kod Hamminga. Były to między innymi kod parzystości, kod 2z5, powtarzanie.

    Richard Wesley Hamming (ur. 11 lutego 1915 w Chicago, zm. 7 stycznia 1998 w Monterey, Kalifornia) – matematyk amerykański, którego prace wywarły istotny wpływ na nauki komputerowe i telekomunikację.Karta dziurkowana, karta perforowana - nośnik danych stosowany do zapisu informacji w maszynach z automatycznym przetwarzaniem danych. Używana do programowania komputera począwszy od ich konstrukcji aż do lat 80. XX wieku, stosowana współcześnie z papierową taśmą dziurkowaną.

    Kody Hamminga[ | edytuj kod]

    Jeśli w wiadomości jest więcej bitów korygujących i jeśli te bity dla różnej kombinacji bitów przekłamanych dają różne rezultaty, wtedy możemy zidentyfikować nieprawidłowe bity. W 7-bitowej wiadomości jest 7 prawdopodobnych błędów pojedynczych, więc trzy bity korygujące wystarczą by potencjalnie wskazać nie tylko że błąd wystąpił, lecz także na której pozycji.

    Dwójkowy system liczbowy, system binarny, bin – pozycyjny system liczbowy, w którym podstawą jest liczba 2. Do zapisu liczb potrzebne są tylko dwie cyfry: 0 i 1.Bell Telephone Laboratories lub w skrócie Bell Labs – oddział badawczy i wdrożeniowy telekomunikacyjnej korporacji amerykańsko-francuskiej Alcatel-Lucent.

    Hamming zauważył problem przy przekłamaniu dwóch lub więcej bitów i wprowadził pojęcie odległości (teraz nazywanej odległością Hamminga). Kod z kontrolą parzystości ma odległość równą 2 (przekłamanie dwóch bitów jest niewidoczne – kod nie zgłasza błędów, ale słowo jest inne niż przesłane).

    Hamming skupił się na dwóch problemach: zwiększeniu odległości między słowami jak to tylko możliwe, i jednocześnie jak największym stosunku liczby bitów informacyjnych do długości słowa. Główną ideą zastosowanych przez niego schematów kodowania jest nakładanie się bitów parzystości, tak, aby mogły sprawdzać siebie nawzajem.

    YouTube – serwis internetowy, stworzony w lutym roku 2005, który umożliwia bezpłatne umieszczanie, oglądanie filmów oraz live streaming. Używa technologii FLV do wyświetlania szerokiego wyboru filmów zamieszczonych przez użytkowników (tzw. user-generated content), takich jak zwiastuny filmowe lub telewizyjne, teledyski, jak i dzieła amatorskie: wideoblogi i krótkie własne filmy. Większość materiałów została załadowana na YouTube przez prywatne osoby, ale wiele firm (na przykład Columbia Broadcasting System, BBC, Universal Music Group, w Polsce Polska Agencja Prasowa, Grupa TVN, CD Projekt), różne instytucje i organizacje oferują część swoich materiałów przez YouTube jako część programu partnerskiego.Kontrola parzystości – metoda wykrywania przekłamań w transmitowanych wiadomościach. Polega na dodawaniu do wysyłanej wiadomości bitu kontrolnego. W zależności od przyjętej konwencji bit ten nazywany jest bitem parzystości lub bitem nieparzystości. Kontrola parzystości opiera się na parzystości sumy bitów wiadomości, której nie należy mylić z parzystością wiadomości potraktowanej jako liczba dwójkowa. Tę drugą parzystość można odczytać wprost z najmłodszego bitu wiadomości.

    Główny algorytm[ | edytuj kod]

    Przyjmijmy, że bity parzystości znajdują się na pozycjach będących potęgami 2. Algorytm jest następujący:

    1. wszystkie pozycje będące potęgami 2 (1, 2, 4, 8, 16,...) są bitami parzystości,
    2. wszystkie pozycje niebędące potęgami 2 (3, 5, 6, 7, 9, 10,...) to bity informacyjne,
    3. każdy bit parzystości wskazuje parzystość pewnej grupy bitów w słowie, a jego pozycja określa, które bity ma sprawdzać, a które opuszczać:
  • pozycja 1: opuszcza 0 bitów, sprawdza 1 bit, opuszcza 1 bit, sprawdza 1 bit, opuszcza 1 bit itd. (1, 3, 5, 7, 9,...),
  • pozycja 2: opuszcza 1 bit, sprawdza 2 bity, opuszcza 2 bity sprawdza 2 bity, opuszcza 2 bity itd. (2, 3, 6, 7, 10, 11,...),
  • pozycja 4: opuszcza 3 bity, sprawdza 4 bity, opuszcza 4 bity sprawdza 4 bity, opuszcza 4 bity itd. (4, 5, 6, 7, 12, 13, 14, 15,...)
  • pozycja 8: opuszcza 7 bitów, sprawdza 8 bitów, opuszcza 8 bitów sprawdza 8 bitów, opuszcza 8 bitów itd.,
  • ...
  • pozycja n: opuszcza n-1 bitów, sprawdza n bitów, opuszcza n bitów, sprawdza n bitów itd.
  • W tabeli przedstawiono zasadę kodowania dla słowa o długości 20 (15 bitów danych, 5 bitów parzystości).

    Kodowanie korekcyjne lub kodowanie korygujące (ang. ECC - error correction coding, FEC - forward error correction) – technika dodawania nadmiarowości do transmitowanych cyfrowo informacji. Umożliwia całkowitą lub częściową detekcję i korekcję błędów powstałych w wyniku zakłóceń. Dzięki temu nie ma potrzeby wykorzystywania kanału zwrotnego, do poinformowania nadawcy o błędzie i konieczności ponownego przesłania informacji. Kodowanie korekcyjne jest więc wykorzystywane wtedy, gdy retransmisja jest kosztowna, kłopotliwa lub niemożliwa, np. ze względu na ograniczenia czasowe.RAM (ang. Random Access Memory – pamięć o dostępie swobodnym) – podstawowy rodzaj pamięci cyfrowej. Choć nazwa sugeruje, że oznacza to każdą pamięć o bezpośrednim dostępie do dowolnej komórki pamięci (w przeciwieństwie do pamięci o dostępie sekwencyjnym, np. rejestrów przesuwnych), ze względów historycznych określa ona tylko te rodzaje pamięci o bezpośrednim dostępie, w których możliwy jest wielokrotny i łatwy zapis, a wyklucza pamięci ROM (tylko do odczytu) i EEPROM których zapis trwa znacznie dłużej niż odczyt, pomimo iż w ich przypadku również występuje swobodny dostęp do zawartości.

    Kluczowe dla kodów Hamminga jest to, że każdy bit ma unikalną kombinację sprawdzających go bitów parzystości, np. tylko bit 12 jest sprawdzany przez parę p4 i p8. Ta unikalność pozwala korygować błędy pojedyncze. Tłumaczy to też, dlaczego błędy podwójne mogą być wykrywane, ale nie korygowane.

    Bit (w ang. kawałek, skrót od binary digit, czyli cyfra dwójkowa) – najmniejsza ilość informacji potrzebna do określenia, który z dwóch równie prawdopodobnych stanów przyjął układ. Jednostka logiczna.


    Podstrony: [1] 2 [3] [4]



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.012 sek.