Šedý kód

Grayův kód  je binární kód , jinak zrcadlový kód, je to také kód s odrazem, ve kterém se dvě „sousední“ ( v uspořádané, tedy lexikografické množině ) kombinace kódů liší pouze číslicí v jedné binární číslici. . Jinými slovy, Hammingova vzdálenost mezi sousedními kódovými slovy je 1.

V praxi se nejčastěji používá reflexní binární Grayův kód , i když v obecném případě existuje nekonečné množství Grayových kódů s hodnotami číslic v číslicích převzatých z různých abeced. Ve většině případů termín "Grey code" znamená přesně reflexivní binární Gray kód.

Původně byl zamýšlen k ochraně před falešným ovládáním elektromechanických spínačů. Dnes jsou Grayovy kódy široce používány pro zjednodušení detekce a opravy chyb v komunikačních systémech a také při vytváření zpětnovazebních signálů v řídicích systémech.

Název

Grayův kód se nazývá "reflexivní" (odražený) kvůli skutečnosti, že první polovina hodnot po změně pořadí je ekvivalentní druhé polovině, s výjimkou nejvýznamnějšího bitu. Nejvýznamnější bit je jednoduše převrácený. Rozdělením každé nové poloviny na polovinu je tato vlastnost zachována (viz vlastní podobnost ).

Kód je pojmenován po výzkumníkovi Franku Grayovi, který pracoval v Bellových laboratořích . Gray patentoval (patent č. 2632058) a poprvé použil tento kód ve svém impulsním komunikačním systému.

Aplikace

Šedý kód se používá při přenosu měnících se digitálních signálů při absenci hodinového signálu (například v mnoha typech snímačů). Představme si, že kód (normální binární) skočí o 3→4, neboli 011 2 → 100 2 . Pokud kvůli nedokonalosti čtečky načteme první bit od 011 a zbylé dva bity od 100, dostaneme 000 2 = 0 - číslo, které má k reálným hodnotám daleko. V Grayově kódu nebudou žádné nadbytečné hodnoty: skok bude v jednom bitu, 010 G  → 110 G a uvažujeme buď staré 010 G =3, nebo nové 110 G =4.

Pokud je čtečka tak pomalá, že se hodnoty během čtení několikrát změnily, šedý kód zaručuje, že chyba bude malá - menší než skutečná změna signálu. Pokud se například během doby čtení hodnoty změnily 010 G =3 → 110 G  → 111 G =5 , pak kromě těchto tří hodnot můžete získat 011 G =2  - vyjde chyba jedna.

Pokud je snímač kruhový (například rotační kodér ), musí skočit z maxima na nulu. Takový skok (ze 100 G =7 na 000 G =0 ) také změní jeden bit.

Šedé kódy se často používají v snímačích kodéru . Jejich použití je pohodlné, protože dvě sousední hodnoty stupnice signálu se liší pouze v jednom bitu. Používají se také ke kódování čísel stop na pevných discích .

Grayův kód lze také použít k vyřešení problému Hanojských věží .

Šedé kódy jsou také široce používány v teorii genetických algoritmů pro kódování genetických vlastností reprezentovaných celými čísly.

Šedý kód se používá ke generování kombinací pomocí metody otočných dveří [1] .

V některých počítačových hrách (například Duke Nukem 3D ) je pro úspěšné dokončení úrovně potřeba zvolit správnou kombinaci poloh několika přepínačů. Neexistují žádné nápovědy, stačí projít všechny kombinace. Chcete-li minimalizovat počet přepínání při iteraci možností, měli byste použít Gray kód. Pokud jsou například tři přepínače, zkoušíme je v pořadí 000, 001, 011, 010, 110…

Sofistikované senzory, které vyžadují hodinový signál, se odchylují od Grayova kódu a pracují v konvenčním binárním systému [2] .

Konverzní algoritmy

Binární převod do šedé

Šedé kódy lze snadno získat z binárních čísel pomocí bitové operace XOR se stejným číslem posunutým doprava o jeden bit a ve které je nejvýznamnější bit vyplněn nulou. Proto je i -tý bit Grayova kódu Gi vyjádřen v bitech binárního kódu Bj takto :

kde  je operace XOR; bity jsou číslovány zprava doleva, počínaje nejméně významným bitem.

Následuje algoritmus pro převod z binárního kódu na Gray, napsaný v C :

unsigned int grayencode ( unsigned int g ) { návrat g ^ ( g >> 1 ); }

Je však třeba pamatovat na to, že tento algoritmus bude fungovat správně, pokud kompilátor implementuje necyklický logický posun (např. standard jazyka C neurčuje typ posunu pro čísla se znaménkem, ale podpora je zaručena pro typy bez znaménka).

Stejný algoritmus napsaný v Pascalu:

function BinToGray ( b : integer ) : integer ; begin BinToGray := b xor ( b shr 1 ) end ;

Příklad: Převeďte binární číslo 10110 na Gray kód.

10110 01011 ----- XOR 11101

Převod Grayova kódu na binární kód

Reverzní algoritmus – převod Grayova kódu na binární kód – lze vyjádřit rekurzivním vzorcem

navíc se převod provádí bit po bitu, počínaje nejvyššími číslicemi, a hodnota použitá ve vzorci se vypočítá v předchozím kroku algoritmu. Pokud do tohoto vzorce dosadíme výše uvedený výraz za i -tý bit Grayova kódu, dostaneme

Výše uvedený algoritmus spojený s manipulací s jednotlivými bity je však pro softwarovou implementaci nepohodlný, proto se v praxi používá upravený algoritmus:

kde N  je počet bitů v Grayově kódu (pro zvýšení rychlosti algoritmu lze N brát jako číslo nejvýznamnějšího nenulového bitu Grayova kódu); znaménko znamená součet pomocí operace "exclusive OR", tj.

Dosazením výrazu za i - tý bit Grayova kódu do vzorce získáme

Zde se předpokládá, že bit, který přesahuje bitovou mřížku ( ), je roven nule.

Níže je funkce C, která implementuje tento algoritmus. Provádí sekvenční posun doprava a sčítání původního binárního čísla, dokud další posun nevynuluje sčítanec.

unsigned int grey decode ( unsigned int grey ) { nepodepsaný int bin ; for ( bin = 0 ; šedá ; šedá >>= 1 ) { přihrádka ^= šedá ; } vratný koš ; }

Stejný algoritmus napsaný v Pascalu:

function GrayToBin ( b : integer ) : integer ; var g : celé číslo ; begin g := 0 ; zatímco b > 0 do begin g := g xor b ; b := b shr 1 ; konec ; GrayToBin := g ; konec ;

Příklad: Převeďte Grayův kód 11101 na binární.

11101 01110 00111 00011 00001 ----- 10110

Rychlý převod 8/16/24/32bitové hodnoty Grayova kódu na binární kód C (Poznámka: Původní Grayův kód je složený. Každá tetráda bitů je samostatné číslo a je kódováno samostatně. Tento kód není úplný Grayův kód A změny pravidla o jeden bit při přechodu na nové číslo jsou uloženy pouze v rámci každé 4. Například při přechodu z 0x0F na 0x10 se změní dva bity současně, protože máme změnu ve dvou tetrádách 0-> 1 a F-> 0):

int gray2bin ( int x ) { return x ^ (( x & 0x88888888 ) >> 3 ) ^ (( x & 0xCCCCCCCC ) >> 2 ) ^ (( x & 0xEEEEEEEE ) >> 1 ); }

Jednoduchý způsob, jak převést binární číslo na Grayův kód, se provádí podle pravidla: nejvýznamnější bit je zapsán beze změny, každý další symbol Grayova kódu musí být invertován, pokud byla dříve přijata "1" v přirozeném kódu, a ponechán beze změny. pokud byla přijata "1" v přirozeném kódu. 0".

Generování šedého kódu

Grayův kód pro n bitů lze rekurzivně zkonstruovat z kódu pro n-1 bitů převrácením seznamu bitů (to znamená zápisem kódů v opačném pořadí), zřetězením původního a obráceného seznamu a přidáním nul na začátek každého z nich. kód v původním seznamu a jedničky na začátek kódů v obráceném seznamu. Chcete-li tedy vygenerovat seznam pro n = 3 bity na základě kódů pro dva bity, je třeba provést následující kroky:

Kódy pro n = 2 bity:	00, 01, 11, 10
Obrácený seznam kódů:		10, 11, 01, 00
Kombinovaný seznam:	00, 01, 11, 10	10, 11, 01, 00
Nuly přidány do původního seznamu:	000, 001, 011, 010	10, 11, 01, 00
Jednotky přidané do obráceného seznamu:	000, 001, 011, 010	110, 111, 101, 100

Níže je uveden jeden z algoritmů pro generování sekvence Grayova kódu dané hloubky, napsaný v jazyce Perl :

moje $hloubka = 16 ; # vygenerovat 16 šedých kódů, každý o šířce 4 bity my @gray_codes = ( '0' , '1' ); while ( skalární ( @gray_codes ) < $depth ) { my @forward_half = mapa { '0' . $_ } @gray_codes ; moje @reverse_half = mapa { '1' . $_ } obráceně ( @gray_codes ); @gray_codes = ( @forward_half , @reverse_half ); }

Rekurzivní funkce pro konstrukci Grayova kódu v jazyce C :

//n -- požadovaná délka kódu, //m -- ukazatel na pole schopné uložit // všechny Grayovy kódy, dlouhé až n // (musí být přiděleno před voláním funkce) //depth -- parametr rekurze int šedá ( int n , int * m , int hloubka ) { int i , t = ( 1 << ( hloubka - 1 )); if ( hloubka == 0 ) m [ 0 ] = 0 ; jinak { //pole ukládá desítkový zápis binárních slov pro ( i = 0 ; i < t ; i ++ ) m [ t + i ] = m [ t - i - 1 ] + ( 1 << ( hloubka -1 ) ); } if ( hloubka != n ) šedá ( n , m , hloubka + 1 ); návrat 0 ; }

Rychlý převod 8/16/24/32bitového binárního kódu na Grayův kód v jazyce C. (Poznámka: Výsledný kód není úplný Grayův kód. Tento kód se převádí na Grayův kód každé 4 bity samostatně a považuje je za samostatná čísla Výsledkem je, že výsledný kód sestává ze sady 4bitových Grayových kódů. A pravidlo pro změnu jednoho bitu při přechodu na nové číslo je uloženo pouze v každém 4. Například při přechodu z 0x0F na 0x10 jsou dva bity změna současně, protože máme změnu ve dvou tetrádách 0-> 1 a F->0):

int bin2gray ( int x ) { return x ^ (( x & 0xEEEEEEEE ) >> 1 ); }

Neobvyklé variace Grayova kódu

Vyvážený šedý kód

Pokud mají senzory omezené zdroje co do počtu sepnutí, chtěl bych, aby se opotřebovávaly rovnoměrně. Ve vyváženém Grayově kódu v různých bitech je počet přepínačů co nejblíže.

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

Zde se ve 4bitovém kódu každý bit přepíná čtyřikrát. V 5bitovém kódu je to nemožné, jeden bit musíte přepnout 8krát, zbytek - 6krát.

Jednostopý šedý kód

Grayův kód je jednostopý, pokud jsou všechny sloupce matice navzájem kruhové posuny. To vám umožní vyrobit úhlový snímač s jednou stopou.

Dvoubitový Gray kód je jednostopý, jak lze vidět u počítačové myši  , a to jak v kuličkovém mechanismu starších myší, tak v rolovacím kolečku u novějších. Dva senzory jsou na různých místech na stejné dráze. Pokud tento systém dovedete do extrému - polovina disku je "černá", polovina "bílá" a senzory jsou vůči sobě 90 ° - pak můžete zjistit absolutní polohu disku s rozlišením 90 °.

U kódů Gray s vyšší bitovou hloubkou tomu tak není, je nutné zvýšit počet stop, což činí snímač objemným a drahým. Pokud je to možné, odpadají dvě stopy - jedna pro dvoubitový Gray kód a jedna pro nulovou pozici. Existují však kódy, kde je právě jedna stopa, nelze však tímto způsobem zakódovat všech 2 n pozic. Pro 5 bitů je záznam 30 pozic, pro 9 - 360.

2D šedý kód

Používá se při kvadraturní modulaci signálů. Sousední konstelační body se liší o jeden bit, diagonální o dva.

Viz také

• Hammingův kód
• Johnsonův kodex
• Reed-Solomonův kodex

Poznámky

1. ↑ Knuth, Donald E. 1 // Umění programování, svazek 4A. Kombinatorické algoritmy / generování všech kombinací (část 7.2.1.3). - M . : LLC "I. D. Williams", 2016. - T. 4. - S. 416. - 960 s. - ISBN 978-5-8459-1980-9 .
2. ↑ Specifikace magnetického kodéru Megatron MAB-25 . Archivováno 13. července 2015 na Wayback Machine 

Literatura

• Black, Paul E. Grey kód . 25. února 2004. NIST. [1  ]

Odkazy

• NIST Slovník algoritmů a datových struktur: Gray  kód
• Šedé kódy  (ruština)