Grå kode - Gray code

Den reflekterte binære koden ( RBC ), også kjent som reflektert binær ( RB ) eller grå kode etter Frank Gray , er en ordning av det binære tallsystemet slik at to påfølgende verdier avviker bare i en bit (binært siffer).

For eksempel vil representasjonen av desimalverdien "1" i binær normalt være " 001 " og "2" ville være " 010 ". I grå kode er disse verdiene representert som " 001 " og " 011 ". På den måten krever økning av en verdi fra 1 til 2 bare en bit å endre, i stedet for to.

Grå koder er mye brukt for å forhindre falsk utgang fra elektromekaniske brytere og for å lette feilretting i digital kommunikasjon som digital bakkenett og noen kabel -TV -systemer.

Motivasjon og navn

Mange enheter indikerer posisjon ved å lukke og åpne brytere. Hvis den enheten bruker naturlige binære koder , er posisjonene 3 og 4 ved siden av hverandre, men alle tre bitene i den binære representasjonen er forskjellige:

Desimal	Binær
...	...
3	011
4	100
...	...

Problemet med naturlige binære koder er at fysiske brytere ikke er ideelle: det er svært lite sannsynlig at fysiske brytere vil endre tilstand nøyaktig synkronisert. I overgangen mellom de to statene vist ovenfor, endrer alle tre bryterne tilstand. I den korte perioden mens alle endrer seg, vil bryterne lese en falsk posisjon. Selv uten tastetrykk kan overgangen se ut som 011 - 001 - 101 - 100 . Når bryterne ser ut til å være i posisjon 001 , kan observatøren ikke fortelle om det er den "virkelige" posisjon 1, eller en overgangstilstand mellom to andre posisjoner. Hvis utgangen mates inn i et sekvensielt system, muligens via kombinasjonslogikk , kan det sekvensielle systemet lagre en falsk verdi.

Dette problemet kan løses ved å endre bare én bryter om gangen, så det er aldri tvetydighet i posisjon, noe som resulterer i koder som tilordner hvert av et sammenhengende sett med heltall , eller til hvert medlem av en sirkulær liste, et ord med symboler som at ingen to kodeord er identiske og at hvert to tilstøtende kodeord skiller seg nøyaktig fra ett symbol. Disse kodene er også kjent som enhet-distanse , single-distanse , enkelttrinns , monostrophic eller syncopic koder , med henvisning til den Hamming-avstand på 1 mellom tilstøtende koder.

Grays patent introduserer begrepet "reflektert binær kode"

I prinsippet kan det være mer enn én slik kode for en gitt ordlengde, men begrepet grå kode ble først brukt på en bestemt binær kode for ikke-negative heltall, den binærreflekterte grå koden eller BRGC . Bell Labs -forsker George R. Stibitz beskrev en slik kode i en patentsøknad fra 1941, gitt i 1943. Frank Gray introduserte begrepet reflektert binær kode i sin patentsøknad fra 1947, og bemerket at koden "ennå ikke hadde et anerkjent navn". Han hentet navnet fra det faktum at det "kan bygges opp fra den konvensjonelle binære koden ved en slags refleksjonsprosess".

I standardkodingen følger den minst signifikante biten et repeterende mønster på 2 på, 2 av (… 11001100 …); neste siffer et mønster på 4 på, 4 av; den n minst minste biten et mønster på 2 ⁿ på 2 ⁿ av. Fire-bits versjonen av dette er vist nedenfor:

Visualisert som en krysning av hjørner av en tesseract

Desimal	Binær	Grå	Desimal av grå
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	1. 3
10	1010	1111	15
11	1011	1110	14
12	1100	1010	10
1. 3	1101	1011	11
14	1110	1001	9
15	1111	1000	8

For desimal 15 ruller koden over til desimal 0 med bare én bytte av bryter. Dette kalles den sykliske eller tilstøtende egenskapen til koden.

I moderne digital kommunikasjon spiller grå koder en viktig rolle i feilretting . For eksempel, i et digitalt modulasjonsskjema som QAM hvor data vanligvis overføres med symboler på 4 biter eller mer, er signalets konstellasjonsdiagram ordnet slik at bitmønstrene som formidles av tilstøtende konstellasjonspunkter, avviker med bare en bit. Ved å kombinere dette med feilkorrigering fremover som er i stand til å korrigere enkeltbitfeil, er det mulig for en mottaker å korrigere eventuelle overføringsfeil som får et konstellasjonspunkt til å avvike til området til et tilstøtende punkt. Dette gjør overføringssystemet mindre utsatt for støy .

Til tross for at Stibitz beskrev denne koden før Gray, ble den reflekterte binære koden senere oppkalt etter Gray av andre som brukte den. To forskjellige 1953 patentsøknader bruker "Grå kode" som et alternativt navn for "reflektert binær kode"; en av dem viser også "minimum feilkode" og "syklisk permutasjonskode" blant navnene. En patentsøknad fra 1954 refererer til "Bell Telephone Gray -koden". Andre navn inkluderer "syklisk binær kode", "syklisk progresjonskode", "syklisk permuterende binær" eller "syklisk permutert binær" (CPB).

Den grå koden ble noen ganger tilskrevet, feilaktig, Elisha Gray .

Historie og praktisk anvendelse

Matematiske gåter

Reflekterte binære koder ble brukt på matematiske gåter før de ble kjent for ingeniører.

Den binærreflekterte Gray-koden representerer den underliggende ordningen for det klassiske kinesiske ringepuslespillet , en sekvensiell mekanisk puslespillmekanisme beskrevet av franskmannen Louis Gros i 1872.

Det kan tjene som en løsningsguide for Towers of Hanoi -problemet, basert på et spill av franske Édouard Lucas i 1883. På samme måte gir de såkalte Towers of Bucharest og Towers of Klagenfurt -spillkonfigurasjonene ternære og pentary grå koder.

Martin Gardner skrev en populær beretning om Gray -koden i sin spalte i Mathematical Games i august 1972 i Scientific American .

Koden danner også en hamiltonsyklus på en hyperkube , hvor hver bit blir sett på som en dimensjon.

Telegrafi koder

Da den franske ingeniøren Émile Baudot endret seg fra å bruke en 6-enheters (6-biters) kode til 5-enhetskoden for sitt utskriftstelegrafsystem , i 1875 eller 1876, bestilte han de alfabetiske tegnene på skrivehjulet ved hjelp av en reflektert binær kode, og tildelte kodene bare tre av bitene til vokaler. Med vokaler og konsonanter sortert i alfabetisk rekkefølge, og andre symboler som er riktig plassert, har 5-bits tegnkoden blitt gjenkjent som en reflektert binær kode. Denne koden ble kjent som Baudot-kode, og ble med små endringer til slutt vedtatt som International Telegraph Alphabet No. 1 (ITA1, CCITT-1) i 1932.

Omtrent samtidig demonstrerte tysk-østerrikske Otto Schäffler  [ de ] en annen utskriftstelegraf i Wien ved hjelp av en 5-bits reflektert binær kode for samme formål, i 1874.

Konvertering av analog til digital signal

Frank Gray , som ble kjent for å finne opp signalmetoden som kom til å bli brukt til kompatibelt fargefjernsyn, oppfant en metode for å konvertere analoge signaler til reflekterte binære kodegrupper ved hjelp av vakuumrørbasert apparat. Metoden og apparatet ble arkivert i 1947 og ble tildelt patent i 1953, og navnet til Gray holdt seg til kodene. " PCM -rør " -apparatet som Gray patenterte ble laget av Raymond W. Sears fra Bell Labs, i samarbeid med Gray og William M. Goodall, som krediterte Gray for ideen om den reflekterte binære koden.

Del av forsiden av Greys patent, som viser PCM -rør (10) med reflektert binær kode i plate (15)

Gray var mest interessert i å bruke kodene for å minimere feil ved konvertering av analoge signaler til digitale; kodene hans brukes fremdeles i dag til dette formålet.

Posisjonskodere

Roterende encoder for vinkelmåler utstyr merket med 3-biters binærreflektert grå kode (BRGC)

En absolutt roterende encoder med grå kode med 13 spor. Hus, avbryterskive og lyskilde er i toppen; følerelement og støttekomponenter er i bunnen.

Grå koder brukes i lineære og roterende posisjonskodere ( absolutte kodere og kvadraturkodere ) fremfor vektet binær koding. Dette unngår muligheten for at når flere biter endres i den binære representasjonen av en posisjon, vil en feillese skyldes at noen av bitene endres før andre.

For eksempel gir noen roterende kodere en disk som har et elektrisk ledende grå kodemønster på konsentriske ringer (spor). Hvert spor har en stasjonær metallfjærkontakt som gir elektrisk kontakt til det ledende kodemønsteret. Sammen produserer disse kontaktene utgangssignaler i form av en grå kode. Andre kodere benytter berøringsfrie mekanismer basert på optiske eller magnetiske sensorer for å produsere grå-kodesignalene.

Uavhengig av mekanismen eller presisjonen til en encoder i bevegelse, kan posisjonsmålefeil oppstå på bestemte posisjoner (ved kodegrenser) fordi koden kan endres i det eksakte øyeblikket den blir lest (samplet). En binær utgangskode kan forårsake betydelige posisjonsmålefeil fordi det er umulig å få alle bitene til å endre nøyaktig samtidig. Hvis for øyeblikket posisjonen blir samplet, har noen biter endret seg og andre ikke, vil den samplede posisjonen være feil. Når det gjelder absolutte kodere, kan den angitte posisjonen være langt borte fra den faktiske posisjonen, og i tilfelle av inkrementelle kodere kan dette ødelegge posisjonssporing.

I kontrast sørger den grå koden som brukes av posisjonskodere for at kodene for to påfølgende posisjoner vil variere med bare en bit, og derfor kan bare en bit endres om gangen. I dette tilfellet vil den maksimale posisjonsfeilen være liten, noe som indikerer en posisjon ved siden av den faktiske posisjonen.

Genetiske algoritmer

På grunn av Hamming -avstandsegenskapene til Gray -koder, brukes de noen ganger i genetiske algoritmer . De er veldig nyttige i dette feltet, siden mutasjoner i koden for det meste gir inkrementelle endringer, men noen ganger kan en enkelt bitendring forårsake et stort sprang og føre til nye egenskaper.

Boolsk kretsminimering

Grå koder brukes også til å merke aksene til Karnaugh -kart siden 1953 så vel som i Händler sirkeldiagrammer siden 1958, begge grafiske metoder for minimering av logiske kretser .

Feilretting

I moderne digital kommunikasjon spiller grå koder en viktig rolle i feilretting . For eksempel, i et digitalt moduleringsskjema som QAM hvor data vanligvis overføres med symboler på 4 biter eller mer, er signalets konstellasjonsdiagram ordnet slik at bitmønstrene som formidles av tilstøtende konstellasjonspunkter, avviker med bare en bit. Ved å kombinere dette med feilkorrigering fremover som er i stand til å korrigere enkeltbitfeil, er det mulig for en mottaker å korrigere eventuelle overføringsfeil som får et konstellasjonspunkt til å avvike til området til et tilstøtende punkt. Dette gjør overføringssystemet mindre utsatt for støy .

Kommunikasjon mellom klokkedomener

Digitale logikkdesignere bruker Grå koder i stor utstrekning for å overføre flertallsinformasjon mellom synkron logikk som opererer ved forskjellige klokkefrekvenser. Logikken anses å fungere i forskjellige "klokkedomener". Det er grunnleggende for utformingen av store chips som opererer med mange forskjellige klokkefrekvenser.

Sykling gjennom stater med minimal innsats

Hvis et system må gå gjennom alle mulige kombinasjoner av på-av-tilstander for et sett med kontroller, og endringene i kontrollene krever ikke-trivielle kostnader (f.eks. Tid, slitasje, menneskelig arbeid), minimerer en grå kode antall innstillinger endres til bare én endring for hver kombinasjon av tilstander. Et eksempel kan være å teste et rørsystem for alle kombinasjoner av innstillinger for sine manuelt betjente ventiler.

En balansert grå kode kan konstrueres, som vender like ofte. Siden bit-flips er jevnt fordelt, er dette optimalt på følgende måte: balanserte grå koder minimerer det maksimale antallet bit-flips for hvert siffer.

Grå kodeteller og regning

George R. Stibitz brukte en reflektert binær kode i en binær pulsteller i 1941 allerede.

En typisk bruk av grå kodetellere er å bygge en FIFO (først inn, først ut) databuffer som har lese- og skriveporter som finnes i forskjellige klokkedomener. Inngangs- og utgangstellerne inne i en slik dobbelports FIFO lagres ofte med grå kode for å forhindre ugyldige forbigående tilstander fra å bli fanget opp når tellingen krysser klokkedomener. De oppdaterte lese- og skrivepekene må sendes mellom klokkedomener når de endres, for å kunne spore FIFO tom og full status på hvert domene. Hver bit av pekene samples ikke-deterministisk for denne klokkedomenoverføringen. Så for hver bit blir enten den gamle verdien eller den nye verdien forplantet. Derfor, hvis mer enn én bit i flerbitspekeren endres ved samplingspunktet, kan en "feil" binær verdi (verken ny eller gammel) forplantes. Ved å garantere at bare en bit kan endres, garanterer grå koder at de eneste mulige samplede verdiene er den nye eller gamle flerbitsverdien. Vanligvis brukes grå koder for power-of-two lengde.

Noen ganger brukes digitale busser i elektroniske systemer til å formidle mengder som bare kan øke eller redusere med en om gangen, for eksempel utgangen fra en hendelsesteller som sendes mellom klokkedomener eller til en digital-til-analog-omformer. Fordelen med grå koder i disse applikasjonene er at forskjeller i forplantningsforsinkelsene til de mange ledningene som representerer bitene i koden, ikke kan få den mottatte verdien til å gå gjennom tilstander som er utenfor den grå kodesekvensen. Dette ligner fordelen med Gray -koder ved konstruksjon av mekaniske kodere, men kilden til Gray -koden er en elektronisk teller i dette tilfellet. Selve telleren må telle i grå kode, eller hvis telleren kjører i binær, må utgangsverdien fra telleren låses igjen etter at den har blitt konvertert til grå kode, for når en verdi er konvertert fra binær til grå kode, er det mulig at forskjeller i ankomsttidene til de binære databitsene inn i den binære til grå konverteringskretsen vil bety at koden kort kan gå gjennom tilstander som er vilt ute av sekvens. Å legge til et registeret klokke etter kretsen som konverterer tellingsverdien til grå kode kan innføre en klocksyklus med latens, så det kan være fordelaktig å telle direkte i grå kode.

For å produsere den neste tellingsverdien i en gråkodeteller, er det nødvendig å ha en kombinasjonslogikk som vil øke den nåværende tellingsverdien som er lagret. En måte å øke et grått kodenummer på er å konvertere det til vanlig binær kode, legge det til med en standard binær adder, og deretter konvertere resultatet tilbake til grå kode. Andre måter å telle i grå kode diskuteres i en rapport av Robert W. Doran , inkludert å ta utgangen fra de første låsene til master-slave flip-flops i en binær kruseteller.

Grå kode adressering

Ettersom utførelsen av programkoden vanligvis forårsaker et instruksjonsminnetilgangsmønster for lokalt påfølgende adresser, kan busskodinger som bruker grå kodeadressering i stedet for binær adressering redusere antall tilstandsendringer av adressebitene betydelig, og derved redusere CPU -strømforbruket i noen lave -kraftdesign.

Konstruere en n -bit grå kode

De første trinnene i reflekter-og-prefiksmetoden.

4-biters grå kode-permutasjon

Den binærreflekterte grå kodelisten for n bits kan genereres rekursivt fra listen for n  -1 bits ved å gjenspeile listen (dvs. oppføringene i omvendt rekkefølge), prefiks oppføringene i den opprinnelige listen med en binær 0 , prefiks den oppføringer i den reflekterte listen med en binær  1 , og deretter sammenkoble den opprinnelige listen med den omvendte listen. For eksempel genererer du n  = 3 -listen fra n  = 2 -listen:

Den en-biters grå koden er G ₁  = ( 0,1 ). Dette kan tenkes som bygget rekursivt som ovenfor fra en null-bits grå kode G ₀  = (  Λ  ) som består av en enkelt oppføring med null lengde. Denne iterative prosessen med å generere G _{n +1} fra G _n gjør følgende egenskaper for standard reflekterende kode klar:

• G _n er en permutasjon av tallene 0,…, 2 ⁿ  - 1. (Hvert tall vises nøyaktig en gang i listen.)
• G _n er innebygd som første halvdel av G _{n +1} .
• Derfor er kodingen stabil , i den forstand at når et binært tall vises i G _n , vises det i samme posisjon i alle lengre lister; så det er fornuftig å snakke om den reflekterende grå koden verdien til et tall: G ( m ) = den m reflekterende grå koden, teller fra 0.
• Hver oppføring i G _n skiller seg bare med en bit fra forrige oppføring. (Hamming -avstanden er 1.)
• Den siste oppføringen i G _n skiller seg bare med en bit fra den første oppføringen. (Koden er syklisk.)

Disse egenskapene antyder en enkel og rask metode for å oversette en binær verdi til den tilsvarende grå koden. Hver bit er invertert hvis den neste høyere biten av inngangsverdien er satt til en. Dette kan utføres parallelt med en bitskift og eksklusiv eller operasjon hvis de er tilgjengelige: den n grå koden oppnås ved å beregne . Ved å forberede en 0 bit forlater rekkefølgen på kodeordene uendret, og en 1 bit i forkant reverserer rekkefølgen på kodeordene. Hvis bitene i posisjonen til kodeord er invertert, blir rekkefølgen på nærliggende blokker av kodeord reversert. For eksempel hvis bit 0 er invertert i en 3 -bits kodeordsekvens, blir rekkefølgen til to nabokodeord reversert ${\ displaystyle n \ oplus \ left \ lfloor {\ tfrac {n} {2}} \ right \ rfloor}$${\ displaystyle i}$${\ displaystyle 2^{i}}$

000,001,010,011,100,101,110,111 → 001,000,011,010,101,100,111,110  (inverter bit 0)

Hvis bit 1 er invertert, endrer blokker med 2 kodeord rekkefølge:

000,001,010,011,100,101,110,111 → 010,011,000,001,110,111,100,101  (inverter bit 1)

Hvis bit 2 er invertert, blokker med 4 kodeord omvendt rekkefølge:

000,001,010,011,100,101,110,111 → 100,101,110,111,000,001,010,011  (inverter bit 2)

Således utfører en eksklusiv eller på en bit i posisjon med borekronen i posisjon etterlater størrelsesorden kodeord intakte hvis , og reverserer rekkefølgen av blokker av kodeord hvis . Nå er dette nøyaktig den samme operasjonen som reflekter-og-prefiks-metoden for å generere den grå koden. ${\ displaystyle b_ {i}}$${\ displaystyle i}$${\ displaystyle b_ {i+1}}$${\ displaystyle i+1}$${\ displaystyle b_ {i+1} = {\ mathtt {0}}}$${\ displaystyle 2^{i+1}}$${\ displaystyle b_ {i+1} = {\ mathtt {1}}}$

En lignende metode kan brukes til å utføre omvendt oversettelse, men beregningen av hver bit avhenger av den beregnede verdien til den neste høyere biten, slik at den ikke kan utføres parallelt. Forutsatt at den er den gråkodede biten (som er den mest betydningsfulle biten), og den t binærkodede biten (som er den mest signifikante biten), kan omvendt oversettelse gis rekursivt:, og . Alternativt kan dekoding av en grå kode til et binært tall beskrives som en prefiks sum av bitene i grå koden, hvor hver individuell summeringsoperasjon i prefiks sum utføres modulo to. ${\ displaystyle g_ {i}}$${\ displaystyle i}$${\ displaystyle g_ {0}}$${\ displaystyle b_ {i}}$${\ displaystyle i}$${\ displaystyle b_ {0}}$${\ displaystyle b_ {0} = g_ {0}}$${\ displaystyle b_ {i} = g_ {i} \ oplus b_ {i-1}}$

For å konstruere den binærreflekterte grå koden iterativt, start i trinn 0 med , og i trinn finn bitposisjonen til den minst signifikante 1 i den binære representasjonen av og snu biten på den posisjonen i den forrige koden for å få den neste koden . Bitposisjonene starter 0, 1, 0, 2, 0, 1, 0, 3,…. Se finne første sett for effektive algoritmer for å beregne disse verdiene. ${\ displaystyle \ mathrm {code} _ {0} = {\ mathtt {0}}}$${\ displaystyle i> 0}$${\ displaystyle i}$${\ displaystyle \ mathrm {code} _ {i-1}}$${\ displaystyle \ mathrm {code} _ {i}}$

Konvertering til og fra grå kode

Følgende funksjoner i C konverterer mellom binære tall og tilhørende grå koder. Selv om det kan virke som om grå-til-binær konvertering krever at hver bit skal håndteres en om gangen, finnes det raskere algoritmer.

typedef unsigned int uint;

// This function converts an unsigned binary number to reflected binary Gray code.
uint BinaryToGray(uint num)
{
    return num ^ (num >> 1); // The operator >> is shift right. The operator ^ is exclusive or.
}

// This function converts a reflected binary Gray code number to a binary number.
uint GrayToBinary(uint num)
{
    uint mask = num;
    while (mask) {           // Each Gray code bit is exclusive-ored with all more significant bits.
        mask >>= 1;
        num   ^= mask;
    }
    return num;
}

// A more efficient version for Gray codes 32 bits or fewer through the use of SWAR (SIMD within a register) techniques. 
// It implements a parallel prefix XOR function. The assignment statements can be in any order.
// 
// This function can be adapted for longer Gray codes by adding steps.

uint GrayToBinary32(uint num)
{
    num ^= num >> 16;
    num ^= num >>  8;
    num ^= num >>  4;
    num ^= num >>  2;
    num ^= num >>  1;
    return num;
}
// A Four-bit-at-once variant changes a binary number (abcd)2 to (abcd)2 ^ (00ab)2, then to (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2.

Spesielle typer grå koder

I praksis refererer "grå kode" nesten alltid til en binærreflektert grå kode (BRGC). Imidlertid har matematikere oppdaget andre typer grå koder. I likhet med BRGC, består hvert av en liste med ord, hvor hvert ord skiller seg fra det neste med bare ett siffer (hvert ord har en Hamming -avstand på 1 fra det neste ordet).

n -ary Grå kode

Det er mange spesialiserte typer grå koder enn den binærreflekterte grå koden. En slik type grå kode er n -ary Gray -koden , også kjent som en ikke -boolsk grå kode . Som navnet tilsier, bruker denne typen grå kode ikke- boolske verdier i kodingene.

For eksempel vil en 3-ary ( ternær ) grå kode bruke verdiene 0,1,2. Den ( n ,  k ) - Grå koden er den n -ary grå koden med k sifre. Elementsekvensen i (3, 2) -Gray-koden er: 00,01,02,12,11,10,20,21,22. ( N ,  k ) -Gray-koden kan konstrueres rekursivt, som BRGC, eller kan konstrueres iterativt . En algoritme for iterativt å generere ( N ,  k ) -Gray-koden presenteres (i C ):

// inputs: base, digits, value
// output: Gray
// Convert a value to a Gray code with the given base and digits.
// Iterating through a sequence of values would result in a sequence
// of Gray codes in which only one digit changes at a time.
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits])
{ 
	unsigned baseN[digits];	// Stores the ordinary base-N number, one digit per entry
	unsigned i;		// The loop variable
 
	// Put the normal baseN number into the baseN array. For base 10, 109 
	// would be stored as [9,0,1]
	for (i = 0; i < digits; i++) {
		baseN[i] = value % base;
		value    = value / base;
	}
 
	// Convert the normal baseN number into the Gray code equivalent. Note that
	// the loop starts at the most significant digit and goes down.
	unsigned shift = 0;
	while (i--) {
		// The Gray digit gets shifted down by the sum of the higher
		// digits.
		gray[i] = (baseN[i] + shift) % base;
		shift = shift + base - gray[i];	// Subtract from base so shift is positive
	}
}
// EXAMPLES
// input: value = 1899, base = 10, digits = 4
// output: baseN[] = [9,9,8,1], gray[] = [0,1,7,1]
// input: value = 1900, base = 10, digits = 4
// output: baseN[] = [0,0,9,1], gray[] = [0,1,8,1]

Det er andre gråkode- algoritmer for ( n , k ) -Gray-koder. ( N , k ) -Gray-koden produsert av algoritmen ovenfor er alltid syklisk; noen algoritmer, for eksempel den av Guan, mangler denne egenskapen når k er oddetall. På den annen side, mens bare ett siffer om gangen endres med denne metoden, kan det endres ved å pakke (sløyfe fra n  - 1 til 0). I Guans algoritme stiger og faller tellingen vekselvis, slik at den numeriske forskjellen mellom to grå kodesifre alltid er en.

Grå koder er ikke unikt definert, fordi en permutasjon av kolonnene i en slik kode også er en grå kode. Prosedyren ovenfor gir en kode der jo lavere signifikans et siffer er, jo oftere endres det, noe som gjør det likt normale tellemetoder.

Se også Skew binært tallsystem , et variert ternært tallsystem hvor maksimalt to siffer endres på hvert trinn, ettersom hver økning kan gjøres med høyst ett siffer bæreoperasjon .

Balansert grå kode

Selv om den binære reflekterte grå koden er nyttig i mange scenarier, er den ikke optimal i visse tilfeller på grunn av mangel på "ensartethet". I balanserte grå koder er antall endringer i forskjellige koordinatposisjoner så nært som mulig. For å gjøre dette mer presist, la G være en R -ary komplett grå syklus med overgangssekvens ; de overgangs tellinger ( spekter ) av G er samlingen av heltall som er definert av ${\ displaystyle (\ delta _ {k})}$

${\ displaystyle \ lambda _ {k} = | \ {j \ in \ mathbb {Z} _ {R^{n}}: \ delta _ {j} = k \} | \ ,, {\ text {for} } k \ in \ mathbb {Z} _ {n}}$

En grå kode er ensartet eller jevnt balansert hvis overgangstallene alle er like, i så fall har vi for alle k . Det er klart at når slike koder bare eksisterer hvis n er en effekt på 2. Ellers, hvis n ikke deler seg jevnt, er det mulig å konstruere velbalanserte koder der hvert overgangstall er enten eller . Grå koder kan også være eksponensielt balansert hvis alle overgangstallene er tilstøtende to, og slike koder eksisterer for hver effekt på to. ${\ displaystyle \ lambda _ {k} = {\ tfrac {R^{n}} {n}}}$${\ displaystyle R = 2}$${\ displaystyle R^{n}}$${\ displaystyle \ left \ lfloor {\ tfrac {R^{n}} {n}} \ right \ rfloor}$${\ displaystyle \ left \ lceil {\ tfrac {R^{n}} {n}} \ right \ rceil}$

For eksempel har en balansert 4-biters grå kode 16 overganger, som kan fordeles jevnt mellom alle fire posisjoner (fire overganger per posisjon), noe som gjør den jevnt balansert:

0 1 1 1 1 1 1 0 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 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 1

mens en balansert 5-bits grå kode har totalt 32 overganger, som ikke kan fordeles jevnt mellom posisjonene. I dette eksemplet har fire posisjoner seks overganger hver, og en har åtte:

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

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

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

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

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

Vi vil nå vise en konstruksjon og implementering for velbalanserte binære grå koder som lar oss generere en n -sifret balansert grå kode for hver n . Hovedprinsippet er å induktivt konstruere en ( n  + 2) -sifret grå kode gitt en n -sifret grå kode G på en slik måte at den balanserte egenskapen bevares. For å gjøre dette, vurderer vi partisjoner i et partall L i ikke-tomme blokker av skjemaet ${\ displaystyle G '}$${\ displaystyle G = g_ {0}, \ ldots, g_ {2^{n} -1}}$

${\ displaystyle \ left \ {g_ {0} \ right \}, \ left \ {g_ {1}, \ ldots, g_ {k_ {2}} \ right \}, \ left \ {g_ {k_ {2} +1}, \ ldots, g_ {k_ {3}} \ right \}, \ ldots, \ left \ {g_ {k_ {L-2} +1}, \ ldots, g _ {-2} \ right \} , \ venstre \ {g _ {-1} \ høyre \}}$

der , og ). Denne partisjonen induserer en -sifret grå kode gitt av ${\ displaystyle k_ {1} = 0}$${\ displaystyle k_ {L-1} =-2}$${\ displaystyle k_ {L} \ equiv -1 {\ pmod {2^{n}}}}$${\ displaystyle (n+2)}$

${\ displaystyle {\ mathtt {00}} g_ {0},}$

${\ displaystyle {\ mathtt {00}} g_ {1}, \ ldots, {\ mathtt {00}} g_ {k_ {2}}, {\ mathtt {01}} g_ {k_ {2}}, \ ldots , {\ mathtt {01}} g_ {1}, {\ mathtt {11}} g_ {1}, \ ldots, {\ mathtt {11}} g_ {k_ {2}},}$

${\ displaystyle {\ mathtt {11}} g_ {k_ {2} +1}, \ ldots, {\ mathtt {11}} g_ {k_ {3}}, {\ mathtt {01}} g_ {k_ {3 }}, \ ldots, {\ mathtt {01}} g_ {k_ {2} +1}, {\ mathtt {00}} g_ {k_ {2} +1}, \ ldots, {\ mathtt {00}} g_ {k_ {3}}, \ ldots,}$

${\ displaystyle {\ mathtt {00}} g _ {-2}, {\ mathtt {00}} g _ {-1}, {\ mathtt {10}} g _ {-1}, {\ mathtt {10}} g_ {-2}, \ ldots, {\ mathtt {10}} g_ {0}, {\ mathtt {11}} g_ {0}, {\ mathtt {11}} g _ {-1}, {\ mathtt {01 }} g _ {-1}, {\ mathtt {01}} g_ {0}}$

Hvis vi definerer overgangsmultiplikasjonene

${\ displaystyle m_ {i} = \ venstre | \ venstre \ {j: \ delta _ {k_ {j}} = i, 1 \ leq j \ leq L \ right \} \ right |}$

å være det antall ganger det siffer i stilling i veksler mellom fortløpende blokker i en skillevegg, og deretter for den ( n  + 2) -digit Gray-kode indusert av denne skillevegg overgangen spekteret er ${\ displaystyle \ lambda '_ {i}}$

${\ displaystyle \ lambda '_ {i} = {\ start {cases} 4 \ lambda _ {i} -2m_ {i}, og {\ text {if}} 0 \ leq i <n \\ L, & { \ text {ellers}} \ ende {saker}}}$

Den delikate delen av denne konstruksjonen er å finne en tilstrekkelig partisjonering av en balansert n -sifret grå kode slik at koden indusert av den forblir balansert, men for dette er det bare overgangsmultiplikatene som betyr noe; å koble sammen to påfølgende blokker over en sifferovergang og dele en annen blokk med en annen sifferovergang, gir en annen grå kode med nøyaktig samme overgangsspekter , så man kan for eksempel angi de første overgangene på siffer som de som faller mellom to blokker. Uniforme koder kan bli funnet når og , og denne konstruksjonen kan også utvides til R -ary -saken. ${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle \ lambda '_ {i}}$${\ displaystyle m_ {i}}$${\ displaystyle i}$${\ displaystyle R \ equiv 0 {\ pmod {4}}}$${\ displaystyle R^{n} \ equiv 0 {\ pmod {n}}}$

Langsiktige grå koder

Langsiktige grå koder maksimerer avstanden mellom påfølgende endringer av sifre i samme posisjon. Det vil si at minimum kjørelengde for en hvilken som helst bit forblir uendret så lenge som mulig.

Monoton grå koder

Monotoniske koder er nyttige i teorien om samtrafikknettverk, spesielt for å minimere utvidelse for lineære matriser av prosessorer. Hvis vi definerer vekten til en binær streng som tallet 1s i strengen, så selv om vi tydeligvis ikke kan ha en grå kode med streng økende vekt, vil vi kanskje tilnærme dette ved å la koden kjøre gjennom to tilstøtende vekter før vi når den neste.

Vi kan formalisere konseptet med monotone grå koder som følger: vurdere hyperkubens inndeling i nivåer av hjørner som har lik vekt, dvs. ${\ displaystyle Q_ {n} = (V_ {n}, E_ {n})}$

${\ displaystyle V_ {n} (i) = \ {v \ i V_ {n}: v {\ text {har vekt}} i \}}$

for . Disse nivåene tilfredsstiller . La være subgrafen til indusert av , og la være kantene inn . En monoton grå kode er da en Hamiltonsk bane på en slik måte at når som helst kommer før i banen, da . ${\ displaystyle 0 \ leq i \ leq n}$${\ displaystyle | V_ {n} (i) | = \ textstyle {\ binom {n} {i}}}$${\ displaystyle Q_ {n} (i)}$${\ displaystyle Q_ {n}}$${\ displaystyle V_ {n} (i) \ cup V_ {n} (i+1)}$${\ displaystyle E_ {n} (i)}$${\ displaystyle Q_ {n} (i)}$${\ displaystyle Q_ {n}}$${\ displaystyle \ delta _ {1} \ i E_ {n} (i)}$${\ displaystyle \ delta _ {2} \ i E_ {n} (j)}$${\ displaystyle i \ leq j}$

En elegant konstruksjon av monoton n -sifret grå koder for alle n er basert på ideen om rekursivt å bygge stier med lengde som har kanter inn . Vi definerer , når eller , og ${\ displaystyle P_ {n, j}}$${\ displaystyle 2 \ textstyle {\ binom {n} {j}}}$${\ displaystyle E_ {n} (j)}$${\ displaystyle P_ {1,0} = ({\ mathtt {0}}, {\ mathtt {1}})}$${\ displaystyle P_ {n, j} = \ emptyset}$${\ displaystyle j <0}$${\ displaystyle j \ geq n}$

${\ displaystyle P_ {n+1, j} = {\ mathtt {1}} P_ {n, j-1}^{\ pi _ {n}}, {\ mathtt {0}} P_ {n, j} }$

ellers. Her er en passende definert permutasjon og refererer til banen P med koordinatene permutert av . Disse banene gir opphav til to monotone n -sifrede grå koder og gitt av ${\ displaystyle \ pi _ {n}}$${\ displaystyle P^{\ pi}}$${\ displaystyle \ pi}$${\ displaystyle G_ {n}^{(1)}}$${\ displaystyle G_ {n}^{(2)}}$

${\ displaystyle G_ {n}^{(1)} = P_ {n, 0} P_ {n, 1}^{R} P_ {n, 2} P_ {n, 3}^{R} \ cdots {\ tekst {og}} G_ {n}^{(2)} = P_ {n, 0}^{R} P_ {n, 1} P_ {n, 2}^{R} P_ {n, 3} \ cdots }$

Valget av hvilke som sikrer at disse kodene faktisk er grå koder viser seg å være . De første verdiene av er vist i tabellen nedenfor. ${\ displaystyle \ pi _ {n}}$${\ displaystyle \ pi _ {n} = E^{-1} \ venstre (\ pi _ {n-1}^{2} \ høyre)}$${\ displaystyle P_ {n, j}}$

Delstier i Savage - Winkler -algoritmen

${\ displaystyle P_ {n, j}}$	j = 0	j = 1	j = 2	j = 3
n = 1	0, 1
n = 2	00, 01	10, 11
n = 3	000, 001	100, 110, 010, 011	101, 111
n = 4	0000, 0001	1000, 1100, 0100, 0110, 0010, 0011	1010, 1011, 1001, 1101, 0101, 0111	1110, 1111

Disse monoton grå kodene kan effektivt implementeres på en slik måte at hvert påfølgende element kan genereres i O ( n ) tid. Algoritmen er lettest beskrevet ved hjelp av coroutines .

Monotoniske koder har en interessant forbindelse til Lovász-formodningen , som sier at hver tilkoblet toppunkt-transitiv graf inneholder en Hamiltonian-sti. Subgrafen på "mellomnivå" er toppunkt-transitive (det vil si at dens automorfismegruppe er transitive, slik at hvert toppunkt har det samme "lokale miljøet" "og ikke kan differensieres fra de andre, siden vi kan merke om koordinatene så vel som de binære sifrene for å oppnå en automorfisme ) og problemet med å finne en hamiltiansk bane i denne undergrafen kalles "mellomnivåproblemet", som kan gi innsikt i den mer generelle formodningen. Spørsmålet er besvart bekreftende for , og det foregående konstruksjon for monoton koder sikrer en Hamiltonian-bane med lengde på minst 0,839 N hvor N er antall hjørner i undergrafen på mellomnivå. ${\ displaystyle Q_ {2n+1} (n)}$${\ displaystyle n \ leq 15}$

Beckett - grå kode

En annen type Gray -kode, Beckett - Gray -koden , er oppkalt etter den irske dramatikeren Samuel Beckett , som var interessert i symmetri . Hans skuespill " Quad " inneholder fire skuespillere og er delt inn i seksten tidsperioder. Hver periode ender med at en av de fire skuespillerne går inn på eller forlater scenen. Stykket begynner med en tom scene, og Beckett ønsket at hvert delsett av skuespillere skulle vises på scenen nøyaktig én gang. Det er tydelig at settet med skuespillere som nå er på scenen kan representeres av en 4-biters binær grå kode. Beckett satte imidlertid en ytterligere begrensning på manuset: han ønsket at skuespillerne skulle gå inn og ut, slik at skuespilleren som hadde stått lengst på scenen, alltid ville være den som forlot. Skuespillerne kan deretter bli representert med en først inn, først ut -kø , slik at (av skuespillerne på scenen) skuespilleren som blir utelukket, alltid er den som ble ført først. Beckett klarte ikke å finne en Beckett - Gray -kode for skuespillet sitt, og faktisk viser en uttømmende liste over alle mulige sekvenser at ingen slik kode eksisterer for n = 4. Det er kjent i dag at slike koder eksisterer for n = 2, 5 , 6, 7, og 8, og er ikke til for n = 3 eller 4. et eksempel på en 8-bits Beckett-Gray-koden finner i Donald Knuth 's Art of Computer Programming . I følge Sawada og Wong kan søkeområdet for n = 6 utforskes på 15 timer, og mer enn 9 500 løsninger for saken n = 7 er funnet.

Snake-in-the-box koder

Maksimal lengde på slanger ( L _s ) og spoler ( L _c ) i slanger-i-esken-problemet for dimensjoner n fra 1 til 4

Snake-in-the-box- koder, eller slanger , er sekvensene av noder på induserte stier i en n- dimensjonal hyperkubegraf , og coil-in-the-box koder, eller spoler , er sekvensene av noder av induserte sykluser i en hyperkube. Sett som grå koder, har disse sekvensene egenskapen til å være i stand til å oppdage en enkeltbits kodingsfeil. Koder av denne typen ble først beskrevet av William H. Kautz på slutten av 1950 -tallet; siden den gang har det vært mye forskning på å finne koden med størst mulig antall kodeord for en gitt hyperkubedimensjon.

Enkelsporet grå kode

Nok en slags grå kode er enkeltsporet grå kode (STGC) utviklet av Norman B. Spedding og foredlet av Hiltgen, Paterson og Brandestini i "Single-track Grey codes" (1996). STGC er en syklisk liste over P unike binære kodninger med lengde n slik at to påfølgende ord er forskjellige i nøyaktig en posisjon, og når listen blir undersøkt som en P  ×  n -matrise , er hver kolonne et syklisk skift i den første kolonnen.

Enkelsporet grå kode med 5 sensorer.

Animert og fargekodet versjon av STGC-rotoren.

Navnet kommer fra deres bruk med roterende kodere , der et antall spor blir registrert av kontakter, noe som resulterer i hver en utgang på 0 eller 1 . For å redusere støy på grunn av at forskjellige kontakter ikke bytter på nøyaktig samme tidspunkt, setter man fortrinnsvis sporene slik at dataene som sendes ut av kontaktene er i grå kode. For å få høy vinkelsnøyaktighet trenger man mange kontakter; for å oppnå minst 1 ° nøyaktighet, trenger man minst 360 distinkte posisjoner per omdreining, noe som krever minst 9 biter data, og dermed samme antall kontakter.

Hvis alle kontakter er plassert i samme vinkelposisjon, er det nødvendig med 9 spor for å få en standard BRGC med minst 1 ° nøyaktighet. Men hvis produsenten flytter en kontakt til en annen vinkelposisjon (men i samme avstand fra midtakselen), må det tilsvarende "ringemønsteret" roteres i samme vinkel for å gi samme utgang. Hvis den mest betydningsfulle biten (den indre ringen i figur 1) er rotert nok, samsvarer den nøyaktig med den neste ringen. Siden begge ringene da er identiske, kan den indre ringen kuttes ut, og sensoren for den ringen flyttes til den gjenværende, identiske ringen (men forskjøvet i den vinkelen fra den andre sensoren på den ringen). De to sensorene på en enkelt ring lager en kvadraturkoder. Det reduserer antall spor for en "1 ° oppløsning" vinkelgiver til 8 spor. Å redusere antallet spor ytterligere kan ikke gjøres med BRGC.

I mange år trodde Torsten Sillke og andre matematikere at det var umulig å kode posisjon på et enkelt spor slik at påfølgende posisjoner bare var forskjellige med en enkelt sensor, bortsett fra 2-sensor, 1-spors kvadraturkoder. Så for applikasjoner der 8 spor var for omfangsrike, brukte folk enkelsporede inkrementelle kodere (kvadraturkodere) eller 2-spors "kvadraturkoder + referansehakk" -kodere.

Norman B. Spedding registrerte imidlertid et patent i 1994 med flere eksempler som viste at det var mulig. Selv om det ikke er mulig å skjelne 2 ⁿ posisjoner med n sensorer på et enkelt spor, det er mulig å skjelne nær så mange. Etzion og Paterson antar at når n i seg selv er en effekt på 2, kan n sensorer maksimalt skille 2 ⁿ  - 2 n posisjoner og at for prime n er grensen 2 ⁿ  - 2 posisjoner. Forfatterne fortsatte med å generere en 504-posisjon enkeltsporskode med lengde 9 som de mener er optimal. Siden dette tallet er større enn ²⁸ = 256, kreves mer enn 8 sensorer av hvilken som helst kode, selv om en BRGC kan skille 512 posisjoner med 9 sensorer.

En STGC for P  = 30 og n  = 5 er gjengitt her:

Enkelsporet grå kode for 30 stillinger

Vinkel	Kode		Vinkel	Kode		Vinkel	Kode		Vinkel	Kode		Vinkel	Kode
0 °	10000		72 °	01000		144 °	00100		216 °	00010		288 °	00001
12 °	10100		84 °	01010		156 °	00101		228 °	10010		300 °	01001
24 °	11100		96 °	01110		168 °	00111		240 °	10011		312 °	11001
36 °	11110		108 °	01111		180 °	10111		252 °	11011		324 °	11101
48 °	11010		120 °	01101		192 °	10110		264 °	01011		336 °	10101
60 °	11000		132 °	01100		204 °	00110		276 °	00011		348 °	10001

Hver kolonne er et syklisk skift i den første kolonnen, og fra en hvilken som helst rad til den neste raden endres bare en bit. Enkelsporet (som en kodekjede) er nyttig ved fremstilling av disse hjulene (sammenlignet med BRGC), ettersom bare ett spor er nødvendig, og dermed reduseres kostnadene og størrelsen. Gråkodens natur er nyttig (sammenlignet med kjedekoder , også kalt De Bruijn -sekvenser ), ettersom bare én sensor vil endres til enhver tid, så usikkerheten under en overgang mellom to diskrete tilstander vil bare være pluss eller minus én enhet vinkel måling enheten kan løse.

To-dimensjonal grå kode

Et gråkodet konstellasjonsdiagram for rektangulære 16- QAM

To-dimensjonale grå koder brukes i kommunikasjon for å minimere antall bitfeil i kvadraturamplitude modulasjon (QAM) tilstøtende punkter i stjernebildet . I en typisk koding skiller de horisontale og vertikale tilstøtende konstellasjonspunktene seg med en enkelt bit, og diagonale tilstøtende punkter avviker med 2 bits.

To-dimensjonale Gray-koder har også anvendelser i steds identifikasjoner ordninger, hvor koden ville bli brukt til området kart som en Mercator projeksjon av jordens overflate og et passende syklisk to-dimensjonale avstand funksjon som for eksempel de Mannheim beregning benyttes for å beregne avstand mellom to kodede steder, og kombinerer derved egenskapene til Hamming -avstanden med den sykliske fortsettelsen av en Mercator -projeksjon.

Grå isometri

Den bijektive kartleggingen {0 ↔ 00 , 1 ↔ 01 , 2 ↔ 11 , 3 ↔ 10 } etablerer en isometri mellom det metriske rommet over det endelige feltet med metrikken gitt av Hamming -avstanden og det metriske rommet over den endelige ringen (den vanlige modulær aritmetikk ) med metrikken gitt av Lee -avstanden . Kartleggingen er passende utvidet til en isometri av Hamming -rommene og . Dens betydning ligger i å etablere en korrespondanse mellom forskjellige "gode", men ikke nødvendigvis lineære koder som grå-kart-bilder av ring-lineære koder fra . ${\ displaystyle \ mathbb {Z} _ {2}^{2}}$ ${\ displaystyle \ mathbb {Z} _ {4}}$ ${\ displaystyle \ mathbb {Z} _ {2}^{2m}}$${\ displaystyle \ mathbb {Z} _ {4}^{m}}$${\ displaystyle \ mathbb {Z} _ {2}^{2}}$${\ displaystyle \ mathbb {Z} _ {4}}$

Relaterte koder

Det er en rekke binære koder som ligner på Grey -koder, inkludert:

• Datex -koder alias Giannini -koder (1954), som beskrevet av Carl P. Spaulding, bruker en variant av O'Brien -kode II .
• Koder som brukes av Varec (ca. 1954), bruker en variant av O'Brien-kode I samt base-12 og base-16 Gray-kodevarianter.
• Lucal code (1959) aka modifisert reflektert binær kode (MRB)
• Gillham -kode (1961/1962), bruker en variant av Datex -kode og O'Brien -kode II .
• Leslie and Russell code (1964)
• Royal Radar Etableringskode
• Hoklas -kode (1988)

Følgende binærkodede desimalkoder (BCD) er også gråkodevarianter:

• Petherick -kode (1953), også kjent som Royal Aircraft Establishment (RAE) -kode.
• O'Brien-koder I og II (1955) (En O'Brien-type I-kode ble allerede beskrevet av Frederic A. Foss fra IBM og brukt av Varec i 1954. Senere ble den også kjent som Watts-kode eller Watts reflektert desimal ( WRD) -kode og blir noen ganger tvetydig referert til som reflektert binær modifisert grå kode. En O'Brien type-II kode ble allerede brukt av Datex i 1954.)
• Overskudd-3 Grå kode (1956) (aka Grå overskudd-3- kode, Grå 3-overskuddskode, refleksoverskudd-3-kode, overskytende Grå kode, Grå overskuddskode, 10-overskudd-3 Grå kode eller Grå – Stibitz-kode), beskrevet av Frank P. Turvey Jr. fra ITT .
• Tompkins koder I og II (1956)
• Glixon -kode (1957), noen ganger tvetydig også kalt modifisert grå kode

Se også

• Lineært tilbakemeldingsskiftregister
• De Bruijn -sekvens - en grå kode på et større alfabet enn 0,1.
• Steinhaus - Johnson - Trotter -algoritme - en algoritme som genererer grå koder for faktorsystemet
• Minste avstandskode
• Prouhet – Thue – Morse -sekvens - relatert til invers grå kode
• Ryser -formel
• Hilbert kurve

Merknader

Referanser

Videre lesning

• Richards, Richard Kohler (1955). Aritmetic Operations in Digital Computers (5 utg.). New York, USA: D. Van Nostrand Co., Inc.
• Richards, Richard Kohler (1967). Elektroniske digitale komponenter og kretser . D. Van Nostrand Co., Inc. s. 490, 500–504, 510–511.
• Black, Paul E. (2004-02-25). "Grå kode" . NIST .
• Press, William H .; Teukolsky, Saul A .; Vetterling, William T .; Flannery, Brian P. (2007). "Del 22.3. Grå koder" . Numeriske oppskrifter: The Art of Scientific Computing (3. utg.). New York, USA: Cambridge University Press . ISBN 978-0-521-88068-8.
• Savage, Carla Diane (1997). "En undersøkelse av kombinatoriske grå koder" . SIAM gjennomgang . Society for Industrial and Applied Mathematics (SIAM). 39 (4): 605–629. Bibcode : 1997SIAMR..39..605S . CiteSeerX  10.1.1.39.1924 . doi : 10.1137/S0036144595295272 . JSTOR  2132693 .
• Wilf, Herbert Saul (1989). "Kapittel 1–3". Kombinatoriske algoritmer: En oppdatering . Society for Industrial and Applied Mathematics (SIAM). ISBN 0-89871-231-9.
• Dewar, Megan; Stevens, Brett (2012-08-29). Bestille blokkdesign - Grå koder, universelle sykluser og konfigurasjon . CMS Books in Mathematics (1 utg.). New York, USA: Springer Science+Business Media . doi : 10.1007/978-1-4614-4325-4 . ISBN 978-1-46144324-7. ISSN  1613-5237 .
• Maxfield, Clive "Max" (2012-10-01) [2011-05-28]. "Grå kodeks grunnleggende" . Design hvordan . EETimes . Del 1. Arkivert fra originalen 2017-10-30 . Hentet 2017-10-30 . Del 2 Del 3
• Warren, Jr., Henry S. (2013). "Kapittel 13: Grå kode". Hacker's Delight (2 utg.). Addison Wesley - Pearson Education, Inc. s. 311–317. ISBN 978-0-321-84268-8. (7 sider)
• Zinovik, Igor; Kroening, Daniel; Chebiryak, Yury (2008-03-21). "Beregning av binære kombinatoriske grå koder via uttømmende søk med SAT -løsere" . IEEE -transaksjoner om informasjonsteori . IEEE . 54 (4): 1819–1823. doi : 10.1109/TIT.2008.917695 . hdl : 20.500.11850/11304 . S2CID  2854180 . (5 sider)
• O'Brien, Joseph A. (juni 1957). "Enhetsavstand binære desimaloversettere" . IRE -transaksjoner på elektroniske datamaskiner . EC-6 (2): 122–123. doi : 10.1109/TEC.1957.5221585 . ISSN  0367-9950 . Hentet 2020-05-25 . (2 sider)
• Barr, KG (mars 1981). "En desimalgrå kode - Enkelt konvertert for akselposisjonskoding" (PDF) . Trådløs verden . Vol. 87 nr. 1542. Fakultet for naturvitenskap, Universitetet i Vestindia . s. 86–87. Arkivert (PDF) fra originalen 2020-07-28 . Hentet 28.07.2020 .

Eksterne linker

• "Gray Code" -demonstrasjon av Michael Schreiber, Wolfram Demonstrations Project (med implementering av Mathematica). 2007.
• NIST Dictionary of Algorithms and Data Structures: Grå kode .
• Hitch Hiker's Guide to Evolutionary Computation, Q21: Hva er grå koder, og hvorfor brukes de? , inkludert C -kode for å konvertere mellom binær og BRGC.
• Dragos A. Harabor bruker grå koder i en 3D digitizer .
• Enspors grå koder, binære kjedekoder ( Lancaster 1994 ) og lineære tilbakemeldingsskiftregistre er alle nyttige for å finne sin absolutte posisjon på en enkelsporet roterende encoder (eller annen posisjonssensor).
• AMS -kolonne: Grå koder
• Optisk Encoder Wheel Generator
• ProtoTalk.net - Understanding Quadrature Encoding - Dekker kvadraturkoding mer detaljert med fokus på robotapplikasjoner