Der widerspiegelte binäre Code, auch bekannt als Code von Gray nach Frank Gray, sind ein binäres Ziffer-System, wo sich zwei aufeinander folgende Werte in nur einem Bit unterscheiden. Es ist ein nichtbelasteter Code.

Der widerspiegelte binäre Code wurde ursprünglich entworfen, um unechte Produktion an elektromechanischen Schaltern zu verhindern. Heute werden Graue Codes weit verwendet, um Fehlerkorrektur in Digitalkommunikationen wie Digitallandfernsehen und einige Kabelfernsehen-Systeme zu erleichtern.

Name

Glockenlaboratorium-Forscher Frank Gray hat widerspiegelten binären Code des Begriffes in seiner 1947-Patent-Anwendung eingeführt, bemerkend, dass der Code "bis jetzt keinen anerkannten Namen" hatte. Er hat den Namen von der Tatsache abgeleitet, dass er "aus dem herkömmlichen binären Code durch eine Art Nachdenken-Prozess aufgebaut werden kann".

Der Code wurde später nach Gray durch andere genannt, der ihn verwendet hat. Zwei verschiedene 1953-Patent-Anwendungen geben "Code von Gray" als ein alternativer Name für den "widerspiegelten binären Code"; einer von denjenigen verzeichnet auch "minimalen Fehlercode" und "zyklischen Versetzungscode" unter den Namen. Eine 1954-Patent-Anwendung bezieht sich auf "den Code von Bell Telephone Gray".

Motivation

Viele Geräte zeigen Position durch das Schließen und die Öffnung von Schaltern an. Wenn dieses Gerät natürliche binäre Codes verwendet, würden diese zwei Positionen neben einander richtig sein:

...

011

100

...

Das Problem mit natürlichen binären Codes besteht darin, dass, mit echten (mechanischen) Schaltern, es sehr unwahrscheinlich ist, dass Schalter Staaten genau in der Gleichzeitigkeit ändern werden. Im Übergang zwischen den zwei Staaten, die oben gezeigt sind, ändern alle drei Schalter Staat. In der kurzen Periode, während sich alle ändern, werden die Schalter eine unechte Position lesen. Sogar ohne keybounce könnte der Übergang 011 — 001 — 101 — 100 ähnlich sein. Wenn die Schalter scheinen, in der Position 001 zu sein, kann der Beobachter nicht erzählen, ob das die "echte" Position 001, oder ein Übergangsstaat zwischen zwei anderen Positionen ist. Wenn das Produktionsfutter in ein folgendes System (vielleicht über die combinational Logik) dann das folgende System einen falschen Wert versorgen kann.

Der widerspiegelte binäre Code behebt dieses Problem durch das Ändern nur eines Schalters auf einmal, also gibt es nie jede Zweideutigkeit der Position,

Dez grauer binärer

0 000 000

1 001 001

2 011 010

3 010 011

4 110 100

5 111 101

6 101 110

7 100 111

Bemerken Sie, dass sich staatliche 7 herumwälzen können, um 0 mit nur einer Schalter-Änderung festzusetzen. Das wird das "zyklische" Eigentum eines Codes von Gray genannt. Im Standard folgt Gray, der das am wenigsten bedeutende Bit codiert, einem wiederholenden Muster 2 auf, 2 von der folgenden Ziffer ein Muster 4 auf, 4 davon; und so weiter.

Mehr formell ist ein Code von Gray ein Codezuweisen jedem eines aneinander grenzenden Satzes von ganzen Zahlen, oder jedem Mitglied einer kreisförmigen Liste, einem Wort von solchen Symbolen, dass sich jeder zwei angrenzende Code Wörter durch ein Symbol unterscheidet. Diese Codes sind auch bekannt als Codes der einzelnen Entfernung, die Entfernung von Hamming 1 zwischen angrenzenden Codes widerspiegelnd. Es kann mehr als einen Code von Gray für eine gegebene Wortlänge geben, aber der Begriff wurde zuerst auf einen besonderen binären Code für die natürlichen Zahlen, den binär widerspiegelten Code von Gray oder BRGC angewandt, dessen Drei-Bit-Version oben gezeigt wird.

Geschichte und praktische Anwendung

Widerspiegelte binäre Codes wurden auf mathematische Rätsel angewandt, bevor sie bekannt Ingenieuren geworden sind. Der französische Ingenieur Émile Baudot hat Codes von Gray in der Telegrafie 1878 verwendet. Er hat die französische Legion der Ehre-Medaille für seine Arbeit empfangen. Der Code von Gray wird manchmal, falsch, Elisha Gray (in Grundsätzen der Pulscodemodulation, K. W. Cattermoles, zum Beispiel) zugeschrieben.

Frank Gray, der berühmt geworden ist, wegen die Signalmethode zu erfinden, die gekommen ist, um für das vereinbare Farbenfernsehen verwendet zu werden, hat eine Methode erfunden, analoge Signale zu widerspiegelten binären Codegruppen umzuwandeln, die Tube-basierten Vakuumapparat verwenden. Die Methode und der Apparat wurden 1953 patentiert, und der Name von Gray ist bei den Codes geblieben. Der "PCM Tube" Apparat, den Gray patentiert hat, wurde von Raymond W. Sears von Glockenlaboratorien gemacht, mit Gray und William M. Goodall arbeitend, der Gray an der Idee vom widerspiegelten binären Code geglaubt hat.

Der Gebrauch seiner namensgebenden Codes, für die sich Gray am meisten interessiert hat, sollte die Wirkung des Fehlers in der Konvertierung von analogen Signalen zum digitalen minimieren; seine Codes werden noch heute für diesen Zweck, und andere verwendet.

Position encoders

Graue Codes werden in der Position encoders (geradliniger encoders und Drehung encoders) in der Bevorzugung vor der aufrichtigen binären Verschlüsselung verwendet. Das vermeidet die Möglichkeit das, wenn Mehrer-Bit-Änderung in der binären Darstellung eines Winkels, sich ein falsch gelesener aus einigen der Bit ergeben wird, die sich vor anderen ändern. Ursprünglich war das Codemuster elektrisch leitend, (in einer Drehung encoder) durch eine Isolieren-Platte unterstützt. Jede Spur hatte seinen eigenen stationären Metallfrühlingskontakt; ein mehr Kontakt hat die Verbindung zum Muster gemacht. Dieser allgemeine Kontakt wurde durch das Muster damit verbunden, welch auch immer der Spur die Kontakte auf dem leitenden Muster ruhten. Jedoch nutzen sich gleitende Kontakte ab und brauchen Wartung, die optischen encoders bevorzugt.

Unabhängig von der Sorge im Übereinstimmen der Kontakte und Genauigkeit des Musters würde ein natürlich-binärer Code Fehler an spezifischen Plattenpositionen haben, weil es unmöglich ist, die ganze Bit-Änderung in genau derselben Zeit vorzunehmen, wie die Platte rotiert. Dasselbe trifft auf einen optischen encoder zu; Übergänge zwischen undurchsichtigem und durchsichtigem können nicht gemacht werden, gleichzeitig für bestimmte genaue Positionen zu geschehen. Drehung encoders zieht aus der zyklischen Natur von Codes von Gray einen Nutzen, weil sich Konsekutivpositionen der Folge durch nur ein Bit unterscheiden.

Türme Hanois

Der binär widerspiegelte Code von Gray kann auch verwendet werden, um als ein Lösungsführer für die Türme des Hanoier Problems, sowie das klassische chinesische Ringrätsel, ein folgender mechanischer Rätsel-Mechanismus zu dienen. Es bildet auch einen Zyklus von Hamiltonian auf einem Hyperwürfel, wo jedes Bit als eine Dimension gesehen wird.

Genetische Algorithmen

Wegen der Entfernungseigenschaften von Hamming von Codes von Gray werden sie manchmal in genetischen Algorithmen verwendet. Sie sind in diesem Feld sehr nützlich, da Veränderungen im Code größtenteils zusätzliche Änderungen berücksichtigen, aber gelegentlich kann eine einzelne Bit-Änderung einen großen Sprung verursachen und zu neuen Eigenschaften führen.

Karten von Karnaugh

Graue Codes werden auch im Beschriften der Äxte von Karten von Karnaugh verwendet.

Fehlerkorrektur

In modernen Digitalkommunikationen spielen Codes von Gray eine wichtige Rolle in der Fehlerkorrektur. Zum Beispiel in einem Digitalmodulationsschema wie QAM, wo Daten normalerweise in Symbolen von 4 Bit oder mehr übersandt wird, wird das Konstellationsdiagramm des Signals eingeordnet, so dass sich die durch angrenzende Konstellationspunkte beförderten Bit-Muster durch nur ein Bit unterscheiden. Durch das Kombinieren davon mit der Vorwärtsfehlerkorrektur, die dazu fähig ist, Fehler des einzelnen Bit zu korrigieren, ist es für einen Empfänger möglich, irgendwelche Übertragungsfehler zu korrigieren, die einen Konstellationspunkt veranlassen, ins Gebiet eines angrenzenden Punkts abzugehen. Das macht das Übertragungssystem weniger empfindlich gegen das Geräusch.

Kommunikation zwischen Uhr-Gebieten

Digitallogikentwerfer verwenden Codes von Gray umfassend, um Mehrbit-Information der Zählung zwischen der gleichzeitigen Logik zu passieren, die an verschiedenen Uhr-Frequenzen funktioniert. Die Logik wird betrachtet, in verschiedenen "Uhr-Gebieten" funktionierend. Es ist für das Design von großen Chips grundsätzlich, die mit vielen verschiedenen Abstoppen-Frequenzen funktionieren.

Graue Codeschalter und Arithmetik

Ein typischer Gebrauch von Codeschaltern von Gray baut einen FIFO (zuerst - in, zuerst) Datenpuffer, der gelesen hat und Häfen schreibt, die in verschiedenen Uhr-Gebieten bestehen. Der Eingang und die Produktionsschalter innerhalb solch eines Doppelhafens FIFO werden häufig mit dem Code von Gray versorgt, um ungültige vergängliche Staaten davon abzuhalten, gewonnen zu werden, wenn die Zählung Uhr-Gebiete durchquert.

Die aktualisierten gelesen und schreiben, dass Zeigestöcke zwischen Uhr-Gebieten passiert werden müssen, wenn sie sich ändern, um im Stande zu sein, FIFO leeren und vollen Status in jedem Gebiet zu verfolgen. Jedes Bit der Zeigestöcke wird nichtdeterministisch für diese Uhr-Bereichsübertragung probiert. So für jedes Bit werden entweder der alte Wert oder der neue Wert fortgepflanzt. Deshalb, wenn sich das mehr als ein Bit im Mehrbit-Zeigestock an der Stützstelle ändert, kann ein "falscher" binärer Wert (weder neu noch alt) fortgepflanzt werden. Durch das Garantieren von nur einem Bit kann sich ändern, Codes von Gray versichern, dass die einzigen möglichen probierten Werte der neue oder alte Mehrbit-Wert sind. Normalerweise werden Codes von Gray der power-two Länge verwendet.

Manchmal werden Digitalbusse in elektronischen Systemen verwendet, um Mengen zu befördern, die nur zunehmen oder durch einer nach dem anderen, zum Beispiel die Produktion eines Ereignis-Schalters abnehmen können, der zwischen Uhr-Gebieten oder zu einem zum Analogon digitalen Konverter passiert wird. Der Vorteil von Codes von Gray in diesen Anwendungen besteht darin, dass Unterschiede in den Fortpflanzungsverzögerungen der vielen Leitungen, die die Bit des Codes vertreten, den erhaltenen Wert nicht veranlassen können, Staaten durchzugehen, die außer der Codefolge von Gray sind. Das ist zum Vorteil von Codes von Gray im Aufbau von mechanischem encoders ähnlich, jedoch ist die Quelle des Codes von Gray ein elektronischer Schalter in diesem Fall. Der Schalter selbst muss im Code von Gray zählen, oder wenn die Gegenläufe in der Dualzahl dann der Produktionswert vom Schalter wiederabgestoppt werden muss, nachdem es zum Code von Gray umgewandelt worden ist, weil, wenn ein Wert von der Dualzahl bis Code von Gray umgewandelt wird, es möglich ist, dass Unterschiede in der Ankunftszeit der binären Datenbit in den binären-zu-grau Umwandlungsstromkreis bedeuten werden, dass der Code kurz durch Staaten gehen konnte, die wild außer der Folge sind. Wenn er ein abgestopptes Register nachdem hinzufügt, kann der Stromkreis, der den Wert der Zählung zum Code von Gray umwandelt, einen Uhr-Zyklus der Latenz einführen, so kann das Zählen direkt im Code von Gray vorteilhaft sein. Ein Codeschalter von Gray wurde 1962 patentiert, und es hat viele andere seitdem gegeben. In letzter Zeit kann ein Codeschalter von Gray als eine Zustandmaschine in Verilog durchgeführt werden. Um den folgenden Wert der Zählung zu erzeugen, ist es notwendig, etwas combinational Logik zu haben, die den aktuellen Wert der Zählung erhöhen wird, der im Code von Gray versorgt wird. Wahrscheinlich soll die offensichtlichste Weise, eine Kennnummer von Gray zu erhöhen, es in den gewöhnlichen binären Code umwandeln, denjenigen dazu mit einer binären Standardviper hinzuzufügen, und dann das Ergebnis zurück zum Code von Gray umzuwandeln. Diese Annäherung wurde in einer Zeitung 1996 besprochen und dann nachher von jemandem anderem 1998 patentiert. Andere Methoden, im Code von Gray zu zählen, werden in einem Bericht von R. W. Doran, einschließlich der Einnahme der Produktion von den ersten Klinken der Flip-Misserfolge des Masters-Sklaven in einem binären Kräuselungsschalter besprochen.

Vielleicht ist der allgemeinste elektronische Schalter mit den "nur einem Bit Änderungen in einer Zeit" Eigentum der Schalter von Johnson.

Das Konstruieren eines N-Bit Code von Gray

Die binär widerspiegelte Codeliste von Gray für n Bit kann rekursiv von der Liste für n−1 Bit durch das Reflektieren der Liste (d. h. die Auflistung der Einträge in umgekehrter Reihenfolge), das Verketten der ursprünglichen Liste mit der umgekehrten Liste, das Vorbefestigen der Einträge in der ursprünglichen Liste mit binärem 0, und dann das Vorbefestigen der Einträge in der widerspiegelten Liste mit binärem 1 erzeugt werden. Zum Beispiel, den n = 3 Liste vom n = 2 Liste erzeugend:

Das ein Bit Code von Gray ist G = (0, 1). Davon kann so gebaut rekursiv gedacht werden wie oben von einem Nullbit Code G von Gray = {Λ}, aus einem einzelnen Zugang der Nulllänge bestehend. Dieser wiederholende Prozess, G von G zu erzeugen, macht die folgenden Eigenschaften des nachdenkenden Standardcodes klar:

• G ist eine Versetzung der Zahlen 0..., 2−1. (Jede Zahl erscheint genau einmal in der Liste.)
• G wird als die erste Hälfte von G eingebettet.
• Deshalb ist das Codieren im Sinn stabil, dass sobald eine Binärzahl in G erscheint, erscheint es in derselben Position in allen längeren Listen; so hat es Sinn, über den reflektierenden Codewert von Gray einer Zahl zu sprechen: G (m) = die M th nachdenkender Code von Gray, von 0 zählend.
• Jeder Zugang in G unterscheidet sich durch nur ein Bit vom vorherigen Zugang. (Die Hamming Entfernung ist 1.)
• Der letzte Zugang in G unterscheidet sich durch nur ein Bit vom ersten Zugang. (Der Code ist zyklisch.)

Diese Eigenschaften deuten eine einfache und schnelle Methode an, einen binären Wert in den entsprechenden Code von Gray zu übersetzen. Jedes Bit wird umgekehrt, wenn das folgende höhere Bit des Eingangswerts auf einen gesetzt wird. Das kann in der Parallele durch eine Bit-Verschiebung durchgeführt und - oder Operation exklusiv werden, wenn sie verfügbar sind: Der n-te Code von Gray wird durch die Computerwissenschaft erhalten

Eine ähnliche Methode kann verwendet werden, um die Rückübersetzung durchzuführen, aber die Berechnung jedes Bit hängt vom geschätzten Wert des folgenden höheren Bit ab, so kann es nicht in der Parallele durchgeführt werden. Das Annehmen ist der th grau codiertes Bit (das bedeutendste Bit seiend), und ist der th binär codiertes Bit (die meisten - bedeutendes Bit seiend), die Rückübersetzung kann rekursiv gegeben werden: und. Wechselweise kann die Entzifferung eines Codes von Gray in eine Binärzahl als eine Präfix-Summe der Bit im Code von Gray beschrieben werden, wo jede individuelle Summierungsoperation in der Präfix-Summe modulo zwei durchgeführt wird.

Um den binär widerspiegelten Code von Gray wiederholend zu bauen, fangen Sie mit dem Code 0 an, und am Schritt finde ich die Bit-Position des am wenigsten bedeutenden '1' in der binären Darstellung davon mir - schnipse das Bit an dieser Position im vorherigen Code, um den folgenden Code zu bekommen. Die Bit-Positionen fangen 0, 1, 0, 2, 0, 1, 0, 3 an.... Sieh finden, dass der erste Satz für effiziente Algorithmen diese Werte schätzt.

Das Umwandeln zu und aus dem Code von Gray

/ *

Der Zweck dieser Funktion ist, einen nicht unterzeichneten umzuwandeln

Binärzahl zum widerspiegelten binären Code von Gray.

• /

nicht unterzeichnete interne Nummer binaryToGray (nicht unterzeichnete interne Nummer num)

{\

kehren Sie zurück (num>> 1) ^ num;

}\/ *

Der Zweck dieser Funktion ist, einen widerspiegelten binären umzuwandeln

Graue Kennnummer zu einer Binärzahl.

/

nicht unterzeichnete interne Nummer grayToBinary (nicht unterzeichnete interne Nummer num)

{\

nicht unterzeichnete interne Nummer numBits = 8 * sizeof (num);

nicht unterzeichnete int Verschiebung;

dafür (bewegen sich = 1; Verschiebung

}\

geben Sie num zurück;

}\

</Quelle>

Spezielle Typen von Codes von Gray

In der Praxis bezieht sich ein "Code von Gray" fast immer auf einen binär widerspiegelten Code von Gray (BRGC).

Jedoch haben Mathematiker andere Arten von Codes von Gray entdeckt.

Wie BRGCs besteht jeder aus Listen von Wörtern, wo sich jedes Wort vom folgenden in nur einer Ziffer unterscheidet (jedes Wort hat eine Entfernung von Hamming 1 vom folgenden Wort).

n-stufiger Code von Gray

| }\

Es gibt viele Spezialtypen von Codes von Gray außer dem binär widerspiegelten Code von Gray. Ein solcher Typ des Codes von Gray ist der n-stufige Code von Gray', auch bekannt als ein non-Boolean Code von Gray.

Da der Name einbezieht, verwendet dieser Typ des Codes von Gray Non-Boolean-Werte in seinem encodings.

Zum Beispiel würde ein 3-ary (dreifältiger) Code von Gray die Werte {0, 1, 2} verwenden.

(n k) - ist Grauer Code der n-stufige Code von Gray mit k Ziffern.

Die Folge von Elementen in (3, 2) - Grauer Code ist: {00, 01, 02, 12, 10, 11, 21, 22, 20}.

(n k) - kann Grauer Code rekursiv als der BRGC gebaut werden, oder kann wiederholend gebaut werden.

Ein Algorithmus, um (N k) wiederholend zu erzeugen - wird Grauer Code (in C) präsentiert:

//Eingänge: Basis, Ziffern, schätzt

//Produktion: grauer

//Wandeln Sie einen Wert zu einem graycode mit der gegebenen Basis und den Ziffern um.

//Das Wiederholen durch eine Folge von Werten würde auf eine Folge hinauslaufen

//Codes von Gray, in die sich nur eine Ziffer auf einmal ändert.

Leere to_gray (nicht unterzeichnete Basis, nicht unterzeichnete Ziffern, nicht unterzeichneter Wert, nicht unterzeichnetes Grau [Ziffern])

{

nicht unterzeichneter baseN [Ziffern]; //Läden die gewöhnliche Grund-N-Zahl, eine Ziffer pro Zugang

nicht unterzeichnet ich; //Die Schleife-Variable

//Stellen Sie die normale baseN Zahl in die BaseN-Reihe. Für die Basis 10, 109

//würde als [9,0,1] versorgt

für (ich = 0; ich

Es gibt andere graycode Algorithmen für (n, k) - Graue Codes. Es ist wichtig zu bemerken, dass (n k) - Graue durch den obengenannten Algorithmus erzeugte Codes immer zyklisch sind; einige Algorithmen, wie das durch Guan, haben an diesem Eigentum Mangel, wenn k seltsam ist. Andererseits, während sich nur eine Ziffer in einer Zeit mit dieser Methode ändert, kann sie sich durch die Verpackung ändern (sich von n-1 bis 0 schlingend). Im Algorithmus von Guan erhebt sich die Zählung abwechselnd und fällt, so dass der numerische Unterschied zwischen zwei graycode Ziffern immer ein ist.

Codes von Gray werden nicht einzigartig definiert, weil eine Versetzung der Säulen solch eines Codes ein Code von Gray auch ist. Das obengenannte Verfahren erzeugt einen Code, in den je tiefer die Bedeutung einer Ziffer desto öfter es sich ändert, es ähnlich normalen zählenden Methoden machend.

Erwogener Grauer Code

Obwohl die Dualzahl widerspiegelt hat, dass Code von Gray in vielen Drehbüchern nützlich ist, ist es nicht

optimal in bestimmten Fällen wegen eines Mangels an "der Gleichförmigkeit". In erwogenen Codes von Gray bemühen wir uns, den zu machen

Zahl von Änderungen in jeder Koordinatenposition so nahe wie möglich. Diesen zu machen

genauer, lassen Sie G abgeschlossener Zyklus von Gray eines R-ary sein, der Übergang hat

Folge; die Übergang-Zählungen (Spektrum) dessen sind der

die Sammlung von ganzen Zahlen durch definiert

\lambda_k = | \{j \in \mathbb {Z} _ {R^n}: \delta_j = k \} | \, \text {für} k \in \mathbb {Z} _R

</Mathematik>

Wir sagen, dass ein Code von Gray gleichförmig oder wenn gleichförmig erwogen

ist

seine Übergang-Zählungen sind alle gleich, in welchem Fall wir haben

für den ganzen k. Klar, wenn, solche Codes nur bestehen, wenn n eine Macht von ist

2. Sonst, wenn sich n gleichmäßig nicht teilt, ist das Bestes, das wir tun können, zu

bauen Sie ausgeglichene Codes, wo jede Übergang-Zählung irgendein ist

oder. Graue Codes können auch sein

exponential erwogen, wenn alle ihre Übergang-Zählungen angrenzender sind

Mächte zwei, und solche Codes bestehen für jede Macht zwei.

Wir werden jetzt einen Aufbau für ausgeglichene binäre Codes von Gray zeigen, der uns erlaubt

einen n-digit zu erzeugen, hat Code von Gray für jeden n erwogen. Der Hauptgrundsatz ist

einen stelligen Code von Gray gegeben ein n-digit Gray induktiv zu bauen

Code G auf solche Art und Weise, dass das erwogene Eigentum bewahrt wird. Das, wir zu tun

denken Sie Teilungen in eine gerade Zahl L von

nichtleere Blöcke der Form

\{G_0\}, \{g_1, \cdots, g_ {k_2 }\\}, \{g_ {k_2+1}, \cdots, g_ {k_3 }\\}, \cdots, \{g_ {k_ {l-2} +1}, \cdots, g_ {-2 }\\}, \{g_ {-1 }\\}\

</Mathematik>

wo, und (mod). Diese Teilung

veranlasst einen stelligen durch gegebenen Code von Gray

Wenn wir die Übergang-Vielfältigkeit definieren

ich, 1 \leq j \leq L \} </Mathematik>, um die Zahl von Zeiten die Ziffer in der Position i zu sein

Änderungen zwischen Konsekutivblöcken in einer Teilung, dann für den stelligen

Grauer Code, der durch diese Teilung das Übergang-Spektrum veranlasst ist, ist

\lambda' _k = \begin {Fälle }\

4 \lambda_k - 2 m_k, \, \text {wenn} 0 \leq k

Der feine Teil dieses Aufbaus soll ein entsprechendes Verteilen eines finden

erwogener n-digit Gray codiert solch, dass der dadurch veranlasste Code erwogen bleibt.

Gleichförmige Codes können wenn und, gefunden werden

und dieser Aufbau kann zum R-ary Fall ebenso erweitert werden.

Monotonische Graue Codes

Monotonische Codes sind in der Theorie von Verbindungsnetzen besonders für nützlich

die Minderung der Ausdehnung für die geradlinige Reihe von Verarbeitern.

Wenn wir das Gewicht einer binären Schnur definieren, um die Zahl 1's in zu sein

die Schnur, dann obwohl wir klar keinen Gray mit ausschließlich können codieren

lassen

Gewicht vergrößernd, können wir dem näher kommen wollen, indem wir den Code

führen

durch zwei angrenzende Gewichte vor dem Erreichen des folgenden.

Wir können das Konzept der Eintönigkeit Codes von Gray wie folgt formalisieren: Denken Sie den

Teilung des Hyperwürfels in Niveaus von Scheitelpunkten

das hat gleiches Gewicht, d. h.

dafür. Diese Niveaus befriedigen. Lassen Sie

seien Sie der Subgraph von veranlassten durch, und lassen Sie

seien Sie die Ränder darin. Ein Monostärkungsmittel Code von Gray ist dann Hamiltonian

der Pfad im solchem das, wann auch immer vorher kommt

im Pfad, dann.

Ein eleganter Aufbau des Monostärkungsmittels n-digit Codes von Gray für jeden n basiert auf der Idee davon, rekursiv Subpfade zu bauen

der Länge, die Ränder darin hat. Wir definieren

, wann auch immer

P_ {n+1, j} = 1P^ {\\pi_n} _ {n, j-1}, 0P_ {n, j }\

</Mathematik>

sonst. Hier, ist eine angemessen definierte Versetzung und verweist

zum Pfad P mit seinen Koordinaten, die dadurch permutiert sind. Diese Pfade verursachen

zwei Monostärkungsmittel n-digit Gray codiert und gegeben durch

G_n^ {(1)} = P_ {n, 0} P_ {n, 1} ^R P_ {n, 2} P_ {n, 3} ^R \cdots \text {und} G_n^ {(2)} = P_ {n, 0} ^R P_ {n, 1} P_ {n, 2} ^R P_ {n, 3} \cdots

</Mathematik>

Dessen Wahl sicherstellt, dass diese Codes tatsächlich Codes Umdrehungen von Gray sind

zu sein. Die ersten paar Werte dessen sind

gezeigt im Tisch unten.

Diese Monostärkungsmittel können Codes von Gray auf solche Art und Weise das effizient durchgeführt werden

jedes nachfolgende Element kann in O (n) Zeit erzeugt werden. Der Algorithmus ist

am leichtesten beschriebene Verwenden-Koroutinen.

Monotonische Codes haben eine interessante Verbindung zur Vermutung von Lovász,

der feststellt, dass jeder verbundene mit dem Scheitelpunkt transitive Graph Hamiltonian enthält

Pfad. Der Subgraph "des mittleren Niveaus" ist mit dem Scheitelpunkt transitiv (der, ist

seine automorphism Gruppe ist transitiv, so dass jeder Scheitelpunkt denselben "lokalen hat

Umgebung"" und kann von anderen nicht unterschieden werden, da wir wiederetikettieren können

die Koordinaten sowie die binären Ziffern, um einen automorphism zu erhalten), und der

Problem, einen Pfad von Hamiltonian in diesem Subgraphen zu finden, wird den genannt

"Problem der mittleren Niveaus", das Einblicke in den allgemeineren gewähren kann

Vermutung. Für die Frage ist bejahend, und geantwortet worden

der vorhergehende Aufbau für monotonische Codes sichert einen Pfad von Hamiltonian der Länge

mindestens 0.839N, wo N die Zahl von Scheitelpunkten im mittleren Niveau ist

Subgraph.

Beckett-grauer Code

Ein anderer Typ des Codes von Gray, des Beckett-grauen Codes, wird für den irischen Dramatiker Samuel Beckett genannt, der sich für die Symmetrie interessiert hat. Sein Spiel "Viererkabel" zeigt vier Schauspieler und wird in sechzehn Zeitabschnitte geteilt. Jede Periode endet mit einem der vier Schauspieler, die hereingehen oder die Bühne verlassen. Das Spiel beginnt mit einer leeren Bühne, und Beckett hat gewollt, dass jede Teilmenge von Schauspielern auf der Bühne genau einmal erschienen ist. Klar kann der Satz von Schauspielern zurzeit auf der Bühne durch einen binären 4-Bit-Code von Gray vertreten werden. Beckett hat jedoch eine zusätzliche Beschränkung der Schrift gelegt: Er hat gewollt, dass die Schauspieler hereingegangen und abgegangen sind, so dass der Schauspieler, der auf der Bühne das längste gewesen war, immer derjenige sein würde, um abzugehen. Die Schauspieler konnten dann durch einen ersten in, zuerst Warteschlange vertreten werden, so dass (der Schauspieler auf der Bühne) der Schauspieler, der wird entfernt, immer derjenige ist, der zuerst eingereiht wurde. Beckett war unfähig, einen Beckett-grauen Code für sein Spiel, und tatsächlich zu finden, eine erschöpfende Auflistung aller möglichen Folgen offenbart, dass kein solcher Code für n = 4 besteht. Es ist heute bekannt, dass solche Codes wirklich für n = 2, 5, 6, 7, und 8 bestehen, und für n = 3 oder 4 nicht bestehen. Ein Beispiel eines Beckett-grauen 8-Bit-Codes kann in der Kunst von Knuth der Computerprogrammierung gefunden werden. Gemäß Sawada und Wong kann der Suchraum für n = 6 in 15 Stunden erforscht werden, und mehr als 9,500 Lösungen für den Fall n = 7 sind gefunden worden.

Schlange in den Kasten-Codes

Schlange in den Kasten-Codes oder Schlangen, ist die Folgen von Knoten von veranlassten Pfaden in einem n-dimensional Hyperwürfel-Graphen, und Rolle in den Kasten-Codes oder Rollen, ist die Folgen von Knoten von veranlassten Zyklen in einem Hyperwürfel. Angesehen als Codes von Gray haben diese Folgen das Eigentum des im Stande Seins, jeden Codierfehler des einzelnen Bit zu entdecken. Codes dieses Typs wurden zuerst von W. H. Kautz gegen Ende der 1950er Jahre beschrieben; seitdem hat es viel Forschung über die Entdeckung des Codes mit der größtmöglichen Zahl von Kennwörtern für eine gegebene Hyperwürfel-Dimension gegeben.

Eingleisiger Grauer Code

Und doch ist eine andere Art des Codes von Gray der eingleisige Code von Gray (STGC), der von N. B. Spedding (NZ Patent 264738 - am 28. Oktober 1994) entwickelt ist

und raffiniert von Hiltgen, Paterson und Brandestini in "Eingleisigen Grauen Codes" (1996). Der STGC ist eine zyklische Liste von P einzigartigem binärem encodings der Länge n solch, dass sich zwei Konsekutivwörter in genau einer Position unterscheiden, und wenn die Liste als ein P x n Matrix untersucht wird, ist jede Säule eine zyklische Verschiebung der ersten Säule.

Der Name kommt aus ihrem Gebrauch mit der Drehung encoders, wo mehrere Spuren durch Kontakte gefühlt werden, für jeden in einer Produktion 0 oder 1 resultierend. Um Geräusch wegen verschiedener Kontakte zu reduzieren, die nicht in genau demselben Moment rechtzeitig umschalten, stellt man vorzugsweise die Spuren auf, so dass die Datenproduktion durch die Kontakte im Code von Gray ist. Um hohe winkelige Genauigkeit zu bekommen, braucht man viele Kontakte; um mindestens 1 Grad-Genauigkeit zu erreichen, braucht man mindestens 360 verschiedene Positionen pro Revolution, die ein Minimum von 9 Bit von Daten, und so dieselbe Zahl von Kontakten verlangt.

Wenn alle Kontakte an derselben winkeligen Position gelegt werden, dann sind 9 Spuren erforderlich, um einen normalen BRGC mit mindestens 1 Grad-Genauigkeit zu bekommen. Jedoch, wenn der Hersteller einen Kontakt zu einer verschiedenen winkeligen Position bewegt (aber in derselben Entfernung von der Zentrum-Welle), dann muss das entsprechende "Ringmuster" derselbe Winkel rotieren gelassen werden, um dieselbe Produktion zu geben. Wenn das bedeutendste Bit (der innere Ring in der Abbildung 1) genug rotieren gelassen wird, vergleicht es genau den folgenden Ring. Da beide Ringe dann identisch sind, kann der innere Ring, und der Sensor für diesen Ring ausgeschnitten werden, der zum restlichen, identischen Ring bewegt ist (aber gleichen Sie in diesem Winkel vom anderen Sensor auf diesem Ring aus).

Jene 2 Sensoren auf einem einzelnen Ring machen eine Quadratur encoder.

Das vermindert die Anzahl von Spuren für eine "1 Grad-Entschlossenheit" winkeliger encoder zu 8 Spuren.

Das Vermindern der Anzahl von Spuren kann noch weiter mit BRGC nicht getan werden.

Viele Jahre lang haben Torsten Sillke und andere Mathematiker geglaubt, dass es unmöglich war, Position auf einer solcher Einspur zu verschlüsseln, dass sich Konsekutivpositionen an nur einem einzelnen Sensor, abgesehen von der 1-spurigen 2-Sensoren-Quadratur encoder unterschieden haben.

So für Anwendungen, wo 8 Spuren zu umfangreich waren, haben Leute eingleisigen zusätzlichen encoders (Quadratur encoders) oder 2-spurige "Quadratur encoder + Bezugskerbe" encoders verwendet.

N. B. Spedding hat jedoch ein Patent 1994 mit mehreren Beispielen eingeschrieben zeigend, dass es möglich war. Obwohl es nicht möglich ist, 2 Positionen mit n Sensoren auf einer Einspur zu unterscheiden, ist es möglich, in der Nähe davon viele zu unterscheiden. Zum Beispiel, wenn n selbst eine Macht 2 ist, n Sensoren kann 22n Positionen unterscheiden. Hiltgen und Paterson haben eine Zeitung veröffentlicht, 2001 einen eingleisigen grauen Code mit genau 360 winkeligen Positionen ausstellend, hat das Verwenden von 9 Sensoren gebaut. Da diese Zahl größer ist als 2 = 256, sind mehr als 8 Sensoren durch jeden Code erforderlich, obwohl ein BRGC 512 Positionen mit 9 Sensoren unterscheiden konnte.

Ein STGC für P = 30 und n = 5 wird hier wieder hervorgebracht:

10000

10100

11100

11110

11010

11000

01000

01010

01110

01111

01101

01100

00100

00101

00111

10111

10110

00110

00010

10010

10011

11011

01011

00011

00001

01001

11001

11101

10101

10001

Bemerken Sie, dass jede Säule eine zyklische Verschiebung der ersten Säule, und von jeder Reihe bis die folgenden Reihe-Änderungen von nur einem Bit ist.

Die eingleisige Natur (wie eine Codekette) ist in der Herstellung dieser Räder (im Vergleich zu BRGC) nützlich, weil nur eine Spur erforderlich ist, so ihre Kosten und Größe reduzierend.

Die Graue Codenatur ist (im Vergleich zu Kettencodes, auch genannt Folgen von De Bruijn) nützlich, weil sich nur ein Sensor zu irgendeiner Zeit ändern wird, so wird die Unklarheit während eines Übergangs zwischen zwei getrennten Staaten nur plus sein oder minus eine Einheit des winkeligen Maßes das Gerät zur Auflösung fähig ist.

Siehe auch

• Geradlinige Feed-Back-Verschiebung schreibt ein
• Folge von De Bruijn
• Gillham codieren
• Steinhaus-Johnson-Trotter Algorithmus, ein Algorithmus, der Codes von Gray für das factorial Zahl-System erzeugt

Zeichen

• Schwarz, Code von Paul E. Gray. Am 25. Februar 2004. NIST.

Außenverbindungen

• "Grauer Code" Demonstration durch Michael Schreiber, Wolfram-Demonstrationsprojekt (mit der Durchführung von Mathematica). 2007.
• NIST Wörterbuch von Algorithmen und Datenstrukturen: Grauer Code
• Machen Sie das Handbuch des Wanderers zur Entwicklungsberechnung, Q21 fest: Was sind Codes von Gray, und warum werden sie verwendet?, einschließlich C codieren, um sich zwischen binärem und BRGC umzuwandeln
• Teilmengen oder Kombinationen Können BRGC-Schnuren erzeugen
• "Die Struktur von eingleisigen grauen Codes" von Moshe Schwartz, Tuvi Etzion
• Eingleisige Stromkreis-Codes durch Hiltgen, Alain P.; Paterson, Kenneth G.
• Dragos A. Harabor verwendet Codes von Gray in einem 3D-Digitalisierer.
• eingleisige graue Codes, binäre Kettencodes (Lancaster 1994), und geradlinige Feed-Back-Verschiebungsregister sind alle in der Entdeckung jemandes absoluter Position auf einer eingleisigen Drehung encoder (oder anderer Positionssensor) nützlich.
• Binäre kombinatorische graue Codes über die erschöpfende Suche mit GESESSENEM Solvers durch Zinovik, I. schätzend; Kroening, D.; Chebiryak, Y.
• AMS Säule: Graue Codes
• Optischer Encoder Radgenerator
• ProtoTalk.net - das Verstehen der Quadratur-Verschlüsselung - Deckel-Quadratur, die ausführlicher mit einem Fokus auf robotic Anwendungen verschlüsselt