Grå kode

Grå kode
støt	Ja
Hamming afstand	1

Den Gray kode er en kontinuerlig kode , hvori tilstødende kodeord kun er forskellige i en enkelt binært ciffer, den Hamming afstanden mellem tilstødende kodeord er 1.Transmission fejl i konstant forandring digitale signaler på multi-core linjer reduceres på denne måde, da der ikke er forskellige transittider kan påvirke. Det fungerer som en kodningsmetode til robust transmission af digitale mængder via analoge signalveje. Koden er opkaldt efter fysikeren Frank Gray , der modtog patent på denne proces i 1953 .

Der kan konstrueres en afbalanceret grå kode, hvor alle cifre (bits) i kodeordene afviger lige så ofte fra nabokodeord. Når alle kodeord gennemgås i den korrekte rækkefølge, ændres hvert ciffer derefter det samme antal gange.

Den grå kode er normalt implementeret som en binær kode , men kan også bruges til transmissionsveje på flere niveauer .

Generering fra binær kode

Logiske operatorer

Følgende punkter viser, hvordan du får et gråkodet binært tal fra en binær kode trin for trin:

X1: binært tal i binær kode
X2: Højre skift af det binære tal med 1 bit
X3: Modulo-2-tilføjelse ( XOR-drift ) af X1 og X2; dette er det ønskede tal i den grå kode.

Det samme som pseudokode:

Binær kode X1 → Grå kode: X3 = (X1 XOR X2)

Og som en formel:

${\ displaystyle x_ {3} = x_ {1} \ oplus (x_ {1} \ gg 1)}$

Generator matrix

Da den grå kode er en lineær kode , kan den genereres med en generatormatrix . Et binært længdeord kan ses som en vektor i et -dimensionelt -vektorrum . Lad os nu være en linjevektor, så kan kodningen af ordet i kodeordet repræsenteres som følger: ${\ displaystyle G}$ ${\ displaystyle w}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle \ mathbb {F} _ {2}}$ ${\ displaystyle \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle w}$ ${\ displaystyle w}$ ${\ displaystyle c}$

${\ displaystyle c = w \ underbrace {\ begin {bmatrix} 1 & 1 && 0 \\ & \ ddots & \ ddots & \\ && \ ddots & 1 \\ 0 &&& 1 \ end {bmatrix}} _ {=: G}}$

Afkodningen udføres ved at multiplicere den inverse af . Dette har følgende form: ${\ displaystyle G ^ {- 1}}$ ${\ displaystyle G}$

${\ displaystyle G ^ {- 1} = {\ begin {bmatrix} 1 & \ cdots & \ cdots & 1 \\ & \ ddots && \ vdots \\ && \ ddots & \ vdots \\ 0 &&& 1 \ end {bmatrix }} \ in \ mathbb {F} _ {2} ^ {n \ gange n}}$

Vektorrummet kan tydeligt repræsenteres med hyperkuber . ${\ displaystyle \ mathbb {F} _ {2} ^ {n}}$

Generation som en grå tæller

Du kan også programmere en grå kodetæller direkte i hardware (f.eks. I HDL ). Til dette er det nyttigt at bruge et hjælpe -register, der skifter med hver urcyklus.

 Q_h [n+1] = !Q_h [n]
 Q_h [0  ] =  0     wenn der Gray-Code-Zähler mit Null startet also Q[0]=0, oder Q[0] eine gerade Anzahl an Einsen hat. Bei anderer Initialisierung würde der Zähler rückwärts laufen.

Dette gør kombinatorikken ganske klar:

 Q₀[n+1] = !(Q₀[n] ^   Q_h[n] )
 Q₁[n+1] =   Q₁[n] ^ ( Q₀[n] &  Q_h[n] )
 Q₂[n+1] =   Q₂[n] ^ ( Q₁[n] & !Q₀[n] &  Q_h [n] )
 Q₃[n+1] =   Q₃[n] ^ ( Q₂[n] & !Q₁[n] & !Q₀ [n] & Q_h [n] )
        …
 Q_k-1[n+1] =   Q_k-1[n] ^ ( Q_k-2[n] & !Q_k-3[n] & …  & !Q₁ [n] & !Q₀ [n] & Q_h [n])
 Q_k[n+1] =   Q_k[n] ^ (!Q_k-2[n] &         …  & !Q₁ [n] & !Q₀ [n] & Q_h [n])

Forskellen mellem formlen for den største bit Q _k og de mindre bit Q _k-1 er nødvendig, så tælleren er cyklisk, dvs. tælleren springer til den oprindelige værdi Q = 000 ... 00 efter den sidste værdi Q = 100 ... 00. Med en uendelig tæller ville der ikke være nogen forskel.

 ^ := Exklusiv Oder / XOR / Antivalenz

 ! := Inverter / NOT / Negation

 & := Und / AND / Konjunktion

betyder

Motivationen for udviklingen af denne kode er følgende problem: På flere kerner i en elektrisk datalinje skal data transmitteres parallelt, der ændres kontinuerligt (dvs. altid kun med et ciffer). B. Signaler fra en temperatursensor eller en roterende encoder . Overført som et binært tal ændres bitene teoretisk nøjagtigt på samme tid for en ny måleværdi på hver berørt linje, både ved input af linjen og ved output. Faktisk ændres bitene på linjen imidlertid ikke på samme tid. Dette kan have forskellige årsager: komponentspredning, driftstider, asymmetri osv. Dette fører til uønskede mellemliggende tilstande og kort (mellem de røde linjer) forkert modtagne værdier:

2-bit grå kode:

3-bit grå kode:

4-bit grå kode:

5-bit grå kode:

6-bit grå kode:

Problem med dobbelte kodesignaler

Mens det teoretiske signal i rækkefølgen

{0000}, {0001}, {0010}, {0011}, {0100}, {0101}, {0110}, {0111} osv.

sendes, modtages andre signaltilstande kortvarigt ved udgangen:

{0000}, {0001}, {0000} , {0010}, {0011}, {0100}, {0101}, {0111} , {0110}, {0111} osv.

Løsning med grå kode

For at undgå dette sendes kontrolsignaltilstandene ved hjælp af en grå kode, så kun en bit ændres ad gangen:

Sendt sekvens: {0000}, {0001}, {0011}, {0010}, {0110}, {0111}, {0101}, {0100} osv.
Indgående sekvens: {0000}, {0001}, {0011}, {0010}, {0110}, {0111}, {0101}, {0100} osv.

Den samme sekvens ankommer til udgangen som ved indgangen, selvom der opstår betydelige tidsfejl (røde linjer).

Karnaugh-Veitch diagram

I Karnaugh -Veitch -diagrammet kan den grå kode genkendes - flere sekvenser er mulige - fra det faktum, at der kun sker overgange mellem (vandret eller lodret) nabofelter.

Orden af grå kode
	¬X ₀	X ₀	X ₀	¬X ₀
¬X ₂	0	1	3	2	¬X ₃
X ₂	4.	5	7.	6.	¬X ₃
X ₂	12.	13.	15.	14.	X ₃
¬X ₂	8.	9	11	10	X ₃
	¬X ₁	¬X ₁	X ₁	X ₁

Rækkefølge af dobbelt kode
	¬X ₀	X ₀	X ₀	¬X ₀
¬X ₂	0	1	2	3	¬X ₃
X ₂	7.	6.	5	4.	¬X ₃
X ₂	8.	9	10	11	X ₃
¬X ₂	15.	14.	13.	12.	X ₃
	¬X ₁	¬X ₁	X ₁	X ₁

Koden er også velegnet til cykliske applikationer som f.eks. Disken vist nedenfor, da kun et ciffer ændres ved skift fra det højeste tal til nul.

Værdien af en 1 på positionen i det grå kodenummersystem er (hvor n tæller fra 1, så ... 31, 15, 7, 3, 1). I modsætning til det normale binære system tilføjes de enkelte ikke, men trækkes fra højre. Eksempel: 111 _Grå = 7 - (3 - 1) = 5 eller 1111 _Grå = 15- (7 - (3 - 1)) = 10. Cifre, der er 0, udelades, eksempel: 101 _Grå = 7 - 1 = 6. ${\ displaystyle n}$ ${\ displaystyle 2 ^ {n} -1}$

Processen med at generere grå kode er symmetrisk.

Da naboværdier kun adskiller sig med et ciffer, er den grå kode velegnet til at afdække fejl i serielle processer.

Geometrisk og grafteoretisk fremstilling

Foto 1: terning
Billede 2: Terning med koordinatsystem
Fig. 3: De 6 stier til den grå kode i tabellen. Det er en Hamilton -cyklus . Startpunkt: 000 (grøn cirkel øverst til venstre), fortsættelse: grøn → blå → rød → sort linje, slutpunkt: ved startpunktet

Figur 1 viser hexahedronen for 3 variabler og figur 2 den samme terning med det tilhørende koordinatsystem. Knudepunkterne (hjørnepunkter eller cirkler) på enhedens terning svarer hver til en linje i grå kode. Overgangene (linjernes nabolag) er symboliseret ved terningens kanter. Når du går på kanten, oprettes en grå kode.

lukket 3-bit grå kode
en)	b)	c)	d)	e)	f)
000	000	000	000	000	000
001	100	010	010	001	100
101	101	110	011	011	110
100	001	100	001	010	010
110	011	101	101	110	011
111	111	111	111	111	111
011	110	011	110	101	101
010	010	001	100	100	001

Præcis 1 bit ændres på hver kant. Den grå kode har lige så mange kvarterer, som terningen har kanter. Fra terningen i figur 1 kan de mulige stier krydses på 6 forskellige måder. Der er således 6 muligheder for at generere en 3-bit grå kode, der opfylder betingelserne for den grå kode (tabel og figur 3). Bortset fra det er Gray -koden cyklisk, og udgangspunktet kan derfor også være på en anden linje. På grund af sin enkle rekursive generationsregel er den binære reflekterede grå kode normalt specificeret (kolonne “e” - næstsidste kolonne i tabellen). Der er en hel klasse af grå koder for en bestemt bitlængde.

Der er nøjagtig lige så mange varianter for en n-bit grå kode, som der er Hamilton-cirkler på en n-dimensionel hyperkube .

lukket 3-bit grå kode
en)	b)	c)	d)	e)	f)
000	000	010	010	000	100
001	100	110	011	001	110
101	101	100	001	011	010
100	001	101	101	010	011
110	011	111	111	110	111
111	111	011	110	111	101
011	110	001	100	101	001
010	010	000	000	100	000

Da den grå kode, der er vist her, er cyklisk, er koden i kolonne c), d) og f) flyttet et sted op i denne tabel (sammenlignet med tabellen ovenfor), så de tre nuller i tabellens sidste linje . Det kan således ses, at den grå kode i kolonne a) kun er en spejlvendt vending af kolonne b). På samme måde er kolonne c) bagsiden af kolonne d), mens kolonne e) er bagsiden af kolonne f). Der er tre uorienterede Hamilton-cirkler på den tredimensionelle terning, som kun er vist her i forskellige retninger (rettet Hamilton-cirkel).

For en bedre illustration vises kodetabellerne for de 6 varianter af den 3-bit grå kode her igen. Hvorved variant e repræsenterer den binære reflekterede grå kode, som normalt menes, når den grå kode er nævnt. De 6 versioner kan også genereres ved at permutere de 3 kolonner i kodetabellen. Det følger, at med n bits n! Versioner der. Så for 3 bit 3! = 6 versioner af den 3-bit grå kode.

3 bit: a

3 bit: b

3 bit: c

3 bit: d

3 bit: e

3 bit: f

Billede 4

... etc. ...

Den 4-bit grå kode kan læses fra hyperkuben i figur 4. Der er 4 for 4 bits! = 24 forskellige grå koder.

Ansøgninger

Skemategning af en disk med grå kodning. De gule prikker repræsenterer lyssensorer.

En grå kode absolut encoder med 13 bits

En mulig anvendelse er bestemmelsen af den absolutte position af en rude eller strimmel, der er markeret med sort -hvide søjler, som er scannet med lysbarrierer eller andre sensorer. Denne position bruges derefter til at måle vinkel eller rotationshastighed.

En anden applikation er randprojektion . Der projiceres en sekvens af mønstre af parallelle striber på et objekt. Antallet af striber er grå-kodet og kan beregnes for hver pixel af et observationskamera.

En anden applikation er asynkron læsning af data. For eksempel bruges den grå kode til at aflæse tælleraflæsninger i korrelatorer uden fejl. Selv i værste fald, når man læser ind under en skiftende bit, er resultatet altid korrekt, fordi en skiftende bit ikke er defineret, og den kun gør en forskel på ± 1. Denne type læsning kræver ingen synkronisering og kun meget lidt CPU -tid.

Andre mulige anvendelser er vindretningsmålere eller vandstandsmålere, kortlægning af bilens position i elevatorer.

Den reflekterede grå kode har et tæt forhold til at løse problemet med tårne i Hanoi , og den beskriver også løsningen af de kinesiske ringe .

eksempel

Decimaltallet svarer til den grå kode . Afkodningen i decimalrepræsentationen følger derefter reglen . Hvis flere dem vises i en række Gray kode, vil de blive trukket fra hinanden: The Gray kode dekodes som følger: . ${\ displaystyle 4_ {10} = 100_ {2}}$ ${\ displaystyle 6_ {10} = 110_ {2}}$ ${\ displaystyle 1 \ cdot 7_ {10} - (1 \ cdot 3_ {10} -0 \ cdot 1_ {10}) = 4_ {10}}$ ${\ displaystyle 7_ {10} = 111_ {2}}$ ${\ displaystyle 1 \ cdot 7_ {10} - (1 \ cdot 3_ {10} -1 \ cdot 1_ {10}) = 5_ {10}}$

Generel procedure: I en konvertering er den afgørende faktor placeringen af dem. Stillingen påvirker regningen. Hvis vi ser på tallet 100, så er den i position 3 (fra højre til venstre). Faktoren for en opnås ved at overveje det maksimale antal decimaler, der kan lagres i binær form i et 3-bit tal. Der kan maksimalt lagres 7 (111) i 3-bit binær kode. Hvis vi nu tager et større binært tal, fungerer det praktisk talt analogt. Binært nummer: 11010 (1 i position 5.4 og 2). 5-bit binært tal: maks. 31 4-bit binært tal: maks. 15 2-bit binært tal: maks. 3

Beregning: ${\ displaystyle 31_ {10} - (15_ {10} -3_ {10}) = 19}$

Genberegn en grå kode

  for I := NumBits - 1 downto 0 do        // jedes einzelne Bit vom letzten bis zum ersten
    Value := Value or (                   // das Ergebnis jedes errechneten Bits dem Gesamtergebnis hinzufügen
      (((1 shl (I + 1)) and Value) shr 1) // das Bit der Stelle zuvor im Ergebnis
      xor                                 // xor mit
      ((1 shl I) and GrayCode)            // der aktuellen Stelle des Codes
                       );

historie

Selv før begrebet Gray Code blev introduceret, var der allerede matematiske puslespil, hvor princippet blev anvendt. Først senere tiltrak koden ingeniørernes opmærksomhed. Allerede i 1874 brugte Otto Schäffler, der producerede og forbedrede telegrafer og telefoner i Wien, den reflekterede grå kode. Den franske Jean-Maurice-Émile Baudot brugte Grå koder til elektrisk telegrafi i 1874 . Han modtog den franske æreslegion for sit arbejde .

Det blev opkaldt efter Frank Gray , en forsker ved Bell Laboratories , der genopdagede koden beskrevet af George Stibitz i 1941 til hans formål. Et patent på et gråkodende elektronrør blev udstedt den 17. marts 1953 med titlen Pulse Code Communications , U.S. patent nr. 2.632.058 .

Lignende koder

Weblinks

Commons : Grå kode - samling af billeder, videoer og lydfiler

Java -eksempel til konvertering af et decimaltal til grå kodrepræsentation ( Memento fra 30. september 2007 i internetarkivet )
Algoritmer til generering af den reflekterede grå kode på Combinatorial Object Server

Individuelle beviser

↑ patent US2632058 : Pulse code kommunikation. Udgivet 17. marts 1953 , opfinder: Frank Gray. ‌
↑ Girish S. Bhat, Carla D. Savage: Balancerede grå koder . I: The Electronic Journal of Combinatorics . 28. august 1996, ISSN 1077-8926 , s. R25 - R25 , doi : 10.37236 / 1249 ( combinatorics.org [åbnet 22. maj 2021]).
↑ U.S. patentnummer 2.632.058 freepatentsonline.com

[1] tent US2632058 : Pulse code kommunikation. Udgivet 17. marts 1953 , opfinder: Frank Gray. ‌

[2] Girish S. Bhat, Carla D. Savage: Balancerede grå koder . I: The Electronic Journal of Combinatorics . 28. august 1996, ISSN 1077-8926 , s. R25 - R25 , doi : 10.37236 / 1249 ( combinatorics.org [åbnet 22. maj 2021]).

[3] U.S. patentnummer 2.632.058 freepatentsonline.com

Languages