Grėjaus koduotė

   Šį straipsnį ar jo skyrių reikėtų peržiūrėti.
Būtina ištaisyti gramatines klaidas, patikrinti rašybą, skyrybą, stilių ir pan.
Ištaisę pastebėtas klaidas, ištrinkite šį pranešimą.

Grėjaus koduotė, pavadinta pagal Franką Grėjų – tai dvejetainių skaičių sistemos kodavimo būdas, kai dvi viena po kitos esančios reikšmės skiriasi tik vienu bitu (dvejetainiu skaitmeniu). Grėjaus koduotė dar yra vadinama atspindėta dvejetainė koduotė, nes esami skaitmenys atspindi prieš tai buvusius skaitmenis.

Pavyzdžiui, dešimtainė reikšmė „1“ dvejetainiu formatu paprastai būtų „001“, o „2“ – „010“. Grėjaus koduotėje, šios reikšmės yra vaizduojamos kaip „001“ ir „011“. Tokiu būdu, norint padidinti reikšmę nuo 1 iki 2, reikia pakeisti tik vieną bitą, o ne du.

Grėjaus koduotė yra plačiai naudojama siekiant išvengti klaidingos išvesties iš elektromechaninių jungiklių ir palengvinti klaidų taisymą skaitmeniniuose ryšiuose, pvz., skaitmeninėje antžeminėje televizijoje ir kai kuriose kabelinės televizijos sistemose. Grėjaus koduotės naudojimas šiuose įrenginiuose padeda supaprastinti logines operacijas ir sumažinti praktines klaidas.[1]

Veikimas

Daugelis prietaisų nurodo padėtį uždarydami ir atidarydami jungiklius. Jei toks prietaisas naudoja natūraliuosius dvejetainius kodus, 3 ir 4 pozicijos yra viena šalia kitos, tačiau visi trys dvejetainio atvaizdo bitai skiriasi:

Dešimtainė Dvejetainė
… …
3 011
4 100
… …

Natūraliųjų dvejetainių kodų problema yra ta, kad fiziniai jungikliai nėra idealūs: mažai tikėtina, kad fiziniai jungikliai pakeis būsenas tiksliai sinchroniškai. Pereinant tarp dviejų aukščiau parodytų būsenų, visi trys jungikliai keičia būseną. Per trumpą laiką, kol viskas keičiasi, jungikliai gali parodyti kokią nors klaidingą padėtį. Net ir nesant klavišų atšokimo, perėjimas gali atrodyti kaip 011–001–101–100. Kai atrodo, kad jungikliai yra 001 padėtyje, stebėtojas negali pasakyti, ar tai yra „tikroji“ 1 padėtis, ar pereinamoji būsena tarp dviejų kitų padėčių. Jei išvestis yra įvedama į nuoseklią sistemą, pvz., per kombinuotą logiką, nuoseklioji sistema gali saugoti klaidingą reikšmę.

Šią problemą galima išspręsti vienu metu pakeičiant tik vieną jungiklį, todėl nėra nesusipratimų dėl padėties, dėl to kodai yra priskiriami kiekvienam gretimam sveikųjų skaičių rinkiniui arba kiekvienam nariui iš apskrito sąrašo taip, kad nėra dviejų identiškų koduotės reikšmių ir kiekvienos dvi gretimos koduotės reikšmės skiriasi tiksliai vienu simboliu.

Grėjaus koduotė dar yra vadinama vieno atstumo arba vieno žingsnio,[2] koduote.

Išradimas

Iš principo, gali būti daugiau nei viena koduotė tam tikram žodžio ilgiui, tačiau terminas Grėjaus koduotė pirmiausia buvo pritaikyta tam tikrai ne neigiamų sveikųjų skaičių dvejetainei koduotei, dvejetainei atspindėtai Grėjaus koduotei. „Bell Labs“ tyrėjas Džordžas Stibicas aprašė tokią koduotę 1941 m. patento paraiškoje, kuri buvo suteikta 1943 m.[3][4][5] Frankas Grėjus savo 1947 m. patento paraiškoje įvedė terminą atspindėta dvejetainė koduotė, pažymėdamas, kad koduotė dar neturi pripažinto pavadinimo.[6] Pavadinimą jis sukūrė iš to, kad kodas gali būti sudarytas iš įprasto dvejetainio kodo tam tikro refleksijos proceso būdu.

Standartinėje koduotėje mažiausiai reikšmingas bitas kartojasi pagal šabloną 2 įjungta, 2 išjungta ( … 11001100 … ); sekantis skaitmuo turi šabloną šabloną 4 įjungta, 4 išjungta; i-tasis mažiausiai svarbus bitas turi šabloną 2i įjungta 2i išjungta. Reikšmingiausias skaitmuo yra išimtis. n bitų Grėjaus koduotės atveju reikšmingiausias skaitmuo yra 2n-1 įjungta 2n-1 išjungta, toks pat kaip ir antrasis pagal reikšmingumą skaitmuo, bet prasidedantis kitu sekos tašku. Keturių bitų versija parodyta žemiau:

Vizualizuojama kaip teserakto viršūnių pokyčiai
Grėjaus koduotė išilgai skaičių linijos
Dešimtainė Dvejetainė Grėjaus Grėjaus
dešimtainė
0 0000 0000 0
1 0001 0001 1
2 0010 0011 3
3 0011 0010 2
4 0100 0110 6
5 0101 0111 7
6 0110 0101 5
7 0111 0100 4
8 1000 1100 12
9 1001 1101 13
10 1010 1111 15
11 1011 1110 14
12 1100 1010 10
13 1101 1011 11
14 1110 1001 9
15 1111 1000 8

Pasiekus 15 dešimtainį skaičių, kodas yra perkeliamas į dešimtainį 0 pakeitus tik vieną bitą. Tai vadinama cikline arba gretima kodo savybe.

Išnašos

  1. ↑ Gray, Joel (March 2020). „Understanding Gray Code: A Reliable Encoding System“. graycode.ie (anglų). Section: Conclusion. Nuoroda tikrinta 2023-06-30.
  2. ↑ Spaulding, Carl P. (1965-01-12) [1954-03-09]. „Digital coding and translating system“ (PDF). Monrovia, California, USA: Datex Corporation. U.S. patent 3165731A. Serial No. 415058. Suarchyvuota (PDF) iš originalo 2020-08-05. Nuoroda tikrinta 2018-01-21. (28 pages)
  3. ↑ Stibitz, George Robert (1943-01-12) [1941-11-26]. „Binary counter“. New York, USA: Bell Telephone Laboratories, Incorporated. U.S. patent 2307868. Serial No. 420537. [1]
  4. ↑ Winder, C. Farrell (October 1959). „Shaft Angle Encoders Afford High Accuracy“ (PDF). Electronic Industries. Chilton Company. 18 (10): 76–80.
  5. ↑ Knuth, Donald Ervin (2014-09-12). „Enumeration and Backtracking / Generating all n-tuples“. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. 4A (1 leid.). Addison-Wesley Professional. pp. 442–443. ISBN 978-0-13348885-2.
  6. ↑ Gray, Frank (1953-03-17) [1947-11-13]. Pulse Code Communication (PDF). New York, USA: Bell Telephone Laboratories, Incorporated. U.S. patent 2632058. Serial No. 785697. Suarchyvuota (PDF) iš originalo 2020-08-05. Nuoroda tikrinta 2020-08-05.