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

    Przeczytaj także...
    Kod Johnsona - kod dwójkowy bezwagowy i niepozycyjny stosowany w elektronice, w którym słowa kodowe są postaci 0 k 1 n − k {displaystyle 0^{k}1^{n-k}} lub 1 k 0 n − k {displaystyle 1^{k}0^{n-k}} .Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.
    MathWorld – encyklopedia matematyczna online, sponsorowana przez Wolfram Research, twórcę i producenta programu Mathematica; współsponsorem jest National Science Foundation (National Science Digital Library).

    Kod Graya, zwany również kodem refleksyjnymdwójkowy kod bezwagowy niepozycyjny, który charakteryzuje się tym, że dwa kolejne słowa kodowe różnią się tylko stanem jednego bitu. Jest również kodem cyklicznym, bowiem ostatni i pierwszy wyraz tego kodu także spełniają wyżej wymienioną zasadę.

    Ciąg – w matematyce pojęcie oddające intuicję ponumerowania, czy też uporządkowania elementów zbioru. W zależności od rodzaju elementów zbioru stosuje się różne nazwy: w przypadku liczb mówi się o ciągach liczbowych, bądź bardziej precyzyjnie, np. w przypadku zbioru liczb całkowitych, rzeczywistych czy zespolonych, ciąg nazywa się wtedy odpowiednio ciągiem całkowitoliczbowym, rzeczywistym i zespolonym. Jeśli elementami zbioru są funkcje, to ciąg nazywa się ciągiem funkcyjnym. Ciąg powstały poprzez wybranie elementów innego ciągu nazywa się podciągiem.Czujnik (sensor) – fizyczne bądź biologiczne narzędzie będące najczęściej elementem składowym większego układu, którego zadaniem jest wychwytywanie sygnałów z otaczającego środowiska, rozpoznawanie i rejestrowanie ich.

    Kodem Graya długości n jest ciąg wszystkich różnych ciągów n cyfr {0,1}, ustawionych tak, że dwa kolejne ciągi cyfr różnią się dokładnie jedną z nich.

    Używa się go w przetwornikach analogowo-cyfrowych, szczególnie w systemach gdzie występują po sobie kolejne wartości np. czujniki położenia/obrotu. Kodów Graya można używać do etykietowania pojedynczych procesorów w sieci będącej hiperkostką.

    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.Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu przechodzony jest tylko jeden raz (oprócz pierwszego wierzchołka) . Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest równoważne rozwiązaniu problemu komiwojażera. Grafy zawierające cykl Hamiltona nazywamy hamiltonowskimi.

    Rozszerzanie kodu Graya[]

    Rozszerzanie kodu Graya o 1 bit przeprowadza się według następującego algorytmu:

    Procesor (ang. processor), także CPU (ang. Central Processing Unit) – urządzenie cyfrowe sekwencyjne, które pobiera dane z pamięci, interpretuje je i wykonuje jako rozkazy. Wykonuje on ciąg prostych operacji (rozkazów) wybranych ze zbioru operacji podstawowych określonych zazwyczaj przez producenta procesora jako lista rozkazów procesora.Kod 1 z n - stosowany głównie w elektronice sposób kodowania, w którym słowa binarne o długości n bitów zawierają zawsze tylko jeden bit o wartości 1. Pozycja jedynki determinuje zakodowaną wartość; jest to więc kod pozycyjny, bezwagowy.
    1. Dopisz te same słowa kodowe, ale w odwrotnej kolejności (odbicie lustrzane)
    2. Do początkowych wyrazów dopisz bit o wartości zero, natomiast do odbitych lustrzanie bit o wartości 1.

    Kod Graya jako zagadnienie grafowe[]

    Niech G będzie grafem. Jeżeli będzie zbiorem wszystkich ciągów cyfr binarnych długości n i połączymy dwa ciągi (wierzchołki) krawędzią tylko wtedy, gdy różnią się one na jednej pozycji, to cykl Hamiltona w G wyznacza jednoznacznie kod Graya długości n.

    Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.C – imperatywny, strukturalny język programowania wysokiego poziomu stworzony na początku lat siedemdziesiątych XX w. przez Dennisa Ritchiego do programowania systemów operacyjnych i innych zadań niskiego poziomu.

    Przykład konstruowania kodu 4-bitowego[]

    Prosta konwersja z ]

    Zamiast konstruowania tablicy kodu Graya dla liczby zapisanej w kodzie dwójkowym można znaleźć odpowiednik w kodzie Graya w następujący sposób:

    1. przesunąć liczbę w postaci binarnej o jeden bit w prawo (podzielić przez 2)
    2. wykonać operację XOR na odpowiednich bitach liczby i wyniku dzielenia liczby przez 2.

    W języku C tę operację można zapisać następującym wyrażeniem: gray = liczba ^ (liczba / 2) lub gray = liczba ^ (liczba >> 1).

    Przetwornik analogowo-cyfrowy A/C (ang. A/D – analog to digital; ADC – analog to digital converter), to układ służący do zamiany sygnału analogowego (ciągłego) na reprezentację cyfrową (sygnał cyfrowy). Dzięki temu możliwe jest przetwarzanie ich w urządzeniach elektronicznych opartych o architekturę zero-jedynkową oraz gromadzenie na dostosowanych do tej architektury nośnikach danych. Proces ten polega na uproszczeniu sygnału analogowego do postaci skwantowanej (dyskretnej), czyli zastąpieniu wartości zmieniających się płynnie do wartości zmieniających się skokowo w odpowiedniej skali (dokładności) odwzorowania. Przetwarzanie A/C tworzą 3 etapy: próbkowanie, kwantyzacja i kodowanie. Działanie przeciwne do wyżej wymienionego wykonuje przetwornik cyfrowo-analogowy C/A.Kod (łac. codex – spis) – ciąg składników sygnału (kombinacji sygnałów elementarnych, np. kropek i kresek, impulsów prądu, symboli) oraz reguła ich przyporządkowania składnikom wiadomości (np. znakom pisma). W niektórych zastosowaniach, głównie przy przesyłaniu informacji podlegających utajnieniu, zwany jest szyfrem. Kody są stosowane m.in. w telegrafii, w technice cyfrowej.

    Konwersja z kodu Graya na naturalny kod binarny[]

    Kolejne cyfry naturalnego kodu binarnego wyznacza się iteracyjnie, od najbardziej znaczącej, w oparciu o odpowiednią cyfrę kodu Graya i poprzednio wyznaczoną cyfrę kodu naturalnego:

    1. przyjmij pierwszą (najbardziej znaczącą) cyfrę kodu naturalnego równą pierwszej cyfrze kodu Graya
    2. każdą kolejną cyfrę oblicz jako różnicę symetryczną (XOR) odpowiedniej cyfry kodu Graya i poprzednio wyznaczonej cyfry kodu naturalnego.

    Przykład przeliczenia:

    Wynik: słowu 1010 w kodzie Graya odpowiada ciąg 1100 w kodzie naturalnym, czyli liczba 12. Rzeczywiście, jak pokazuje przedstawiona wyżej konstrukcja, 1010 jest trzynastym słowem kodowym 4-bitowego kodu, a więc (przy numeracji rozpoczynającej się od zera) odpowiada mu liczba 12.

    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.

    Zobacz też[]

  • dwójkowy system liczbowy
  • kod 1 z n
  • kod Johnsona
  • metoda Karnaugh
  • Linki zewnętrzne[]

  • Kod Graya w MathWorld



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

    Reklama

    Czas generowania strony: 0.026 sek.