Codice grigio - Gray code

Il codice binario riflesso ( RBC ), noto anche come codice binario riflesso ( RB ) o codice Gray dopo Frank Gray , è un ordinamento del sistema numerico binario tale che due valori successivi differiscono in un solo bit (cifra binaria).

Ad esempio, la rappresentazione del valore decimale "1" in binario sarebbe normalmente " 001 " e "2" sarebbe " 010 ". In codice Gray, questi valori sono rappresentati come " 001 " e " 011 ". In questo modo, l'incremento di un valore da 1 a 2 richiede la modifica di un solo bit, anziché due.

I codici Gray sono ampiamente utilizzati per prevenire uscite spurie da interruttori elettromeccanici e per facilitare la correzione degli errori nelle comunicazioni digitali come la televisione digitale terrestre e alcuni sistemi di TV via cavo .

Motivazione e nome

Molti dispositivi indicano la posizione chiudendo e aprendo gli interruttori. Se quel dispositivo utilizza codici binari naturali , le posizioni 3 e 4 sono una accanto all'altra ma tutti e tre i bit della rappresentazione binaria differiscono:

Decimale	Binario
...	...
3	011
4	100
...	...

Il problema con i codici binari naturali è che gli interruttori fisici non sono l'ideale: è molto improbabile che gli interruttori fisici cambino stato esattamente in sincronia. Nella transizione tra i due stati mostrati sopra, tutti e tre gli interruttori cambiano stato. Nel breve periodo in cui tutti stanno cambiando, gli interruttori leggeranno alcune posizioni spurie. Anche senza keybounce , la transizione potrebbe apparire come 011 — 001 — 101 — 100 . Quando gli interruttori sembrano essere in posizione 001 , l'osservatore non può dire se quella è la posizione "reale" 1 o uno stato di transizione tra due altre posizioni. Se l'uscita alimenta un sistema sequenziale , possibilmente tramite logica combinatoria , allora il sistema sequenziale può memorizzare un valore falso.

Questo problema può essere risolto cambiando un solo interruttore alla volta, quindi non c'è mai ambiguità di posizione, risultando in codici che assegnano a ciascuno di un insieme contiguo di interi , o a ciascun membro di una lista circolare, una parola di simboli come che non esistono due parole di codice identiche e ciascuna due parole di codice adiacenti differiscono esattamente per un simbolo. Questi codici sono anche noti come codici a distanza unitaria , a distanza singola , a passo singolo , monostrofici o sincopi , in riferimento alla distanza di Hamming di 1 tra codici adiacenti.

Il brevetto di Gray introduce il termine "codice binario riflesso"

In linea di principio, può esserci più di un codice di questo tipo per una data lunghezza di parola, ma il termine codice Gray è stato inizialmente applicato a un particolare codice binario per numeri interi non negativi, il codice Gray riflesso binario o BRGC . Il ricercatore dei Bell Labs George R. Stibitz descrisse tale codice in una domanda di brevetto del 1941, concessa nel 1943. Frank Gray introdusse il termine codice binario riflesso nella sua domanda di brevetto del 1947, osservando che il codice "non aveva ancora un nome riconosciuto". Ha derivato il nome dal fatto che "può essere costruito dal codice binario convenzionale mediante una sorta di processo di riflessione".

Nella codifica standard il bit meno significativo segue uno schema ripetitivo di 2 on, 2 off ( … 11001100 … ); la cifra successiva un modello di 4 on, 4 off; l' n- esimo bit meno significativo un pattern di 2 ⁿ on 2 ⁿ off. La versione a quattro bit di questo è mostrata di seguito:

Visualizzato come un attraversamento di vertici di un tesseract

Decimale	Binario	Grigio	Decimale di Gray
0	0000	0000	0
1	0001	0001	1
2	0010	0011	3
3	0011	0010	2
4	0100	0110	6
5	0101	0111	7
6	0110	0101	5
7	0111	0100	4
8	1000	1100	12
9	1001	1101	13
10	1010	1111	15
11	1011	1110	14
12	1100	1010	10
13	1101	1011	11
14	1110	1001	9
15	1111	1000	8

Per il decimale 15 il codice passa al decimale 0 con una sola modifica dell'interruttore. Questa è chiamata proprietà ciclica o di adiacenza del codice.

Nelle moderne comunicazioni digitali , i codici Gray svolgono un ruolo importante nella correzione degli errori . Ad esempio, in uno schema di modulazione digitale come QAM in cui i dati vengono tipicamente trasmessi in simboli di 4 bit o più, il diagramma della costellazione del segnale è disposto in modo che i modelli di bit trasmessi dai punti della costellazione adiacenti differiscano di un solo bit. Combinando questo con la correzione dell'errore in avanti in grado di correggere gli errori a bit singolo, è possibile per un ricevitore correggere eventuali errori di trasmissione che fanno deviare un punto della costellazione nell'area di un punto adiacente. Ciò rende il sistema di trasmissione meno suscettibile al rumore .

Nonostante il fatto che Stibitz abbia descritto questo codice prima di Gray, il codice binario riflesso è stato successivamente chiamato dopo Gray da altri che lo hanno usato. Due diverse domande di brevetto del 1953 utilizzano "codice grigio" come nome alternativo per il "codice binario riflesso"; uno di questi elenca anche "codice di errore minimo" e "codice di permutazione ciclica" tra i nomi. Una domanda di brevetto del 1954 fa riferimento al "codice grigio del telefono Bell". Altri nomi includono "codice binario ciclico", "codice di progressione ciclica", "binario permutante ciclico" o "binario permutato ciclico" (CPB).

Il codice Gray è stato talvolta attribuito, erroneamente, a Elisha Gray .

Storia e applicazione pratica

Puzzle matematici

I codici binari riflessi sono stati applicati ai puzzle matematici prima che diventassero noti agli ingegneri.

Il codice Gray riflesso binario rappresenta lo schema sottostante del classico puzzle cinese ad anelli , un meccanismo di puzzle meccanico sequenziale descritto dal francese Louis Gros nel 1872.

Può servire come guida alla soluzione per il problema delle Torri di Hanoi , basato su un gioco del francese Édouard Lucas nel 1883. Allo stesso modo, le cosiddette configurazioni di gioco Torri di Bucarest e Torri di Klagenfurt producono codici Gray ternari e pentari .

Martin Gardner ha scritto un resoconto popolare del codice Gray nella sua rubrica Mathematical Games dell'agosto 1972 su Scientific American .

Il codice forma anche un ciclo hamiltoniano su un ipercubo , dove ogni bit è visto come una dimensione.

Codici telegrafici

Quando l'ingegnere francese Émile Baudot passò dall'usare un codice a 6 unità (6 bit) a un codice a 5 unità per il suo sistema telegrafico di stampa , nel 1875 o 1876, ordinò i caratteri alfabetici sulla sua ruota di stampa utilizzando un codice binario riflesso, e ha assegnato i codici utilizzando solo tre dei bit alle vocali. Con vocali e consonanti ordinate nel loro ordine alfabetico e altri simboli posizionati in modo appropriato, il codice di caratteri a 5 bit è stato riconosciuto come codice binario riflesso. Questo codice divenne noto come codice Baudot e, con piccole modifiche, fu infine adottato come International Telegraph Alphabet No. 1 (ITA1, CCITT-1) nel 1932.

All'incirca nello stesso periodo, l'austriaco-tedesco Otto Schäffler  [ de ] dimostrò un'altra stampa telegrafica a Vienna usando un codice binario riflesso a 5 bit per lo stesso scopo, nel 1874.

Conversione del segnale da analogico a digitale

Frank Gray , che divenne famoso per aver inventato il metodo di segnalazione che venne utilizzato per la televisione a colori compatibile, inventò un metodo per convertire i segnali analogici in gruppi di codici binari riflessi utilizzando un apparato basato su tubi a vuoto . Depositato nel 1947, il metodo e l'apparato furono brevettati nel 1953 e il nome di Gray rimase sui codici. Il " tubo PCM " brevettato da Gray è stato realizzato da Raymond W. Sears dei Bell Labs, in collaborazione con Gray e William M. Goodall, che hanno attribuito a Gray l'idea del codice binario riflesso.

Parte della prima pagina del brevetto di Gray, che mostra il tubo PCM (10) con codice binario riflesso nella piastra (15)

Gray era molto interessato all'utilizzo dei codici per ridurre al minimo gli errori nella conversione dei segnali analogici in digitali; i suoi codici sono ancora oggi utilizzati per questo scopo.

Encoder di posizione

Encoder rotativo per dispositivi di misurazione dell'angolo contrassegnati in codice Gray a riflessione binaria a 3 bit (BRGC)

Encoder rotativo assoluto codice Gray con 13 tracce. L'alloggiamento, il disco dell'interruttore e la sorgente luminosa sono nella parte superiore; l'elemento sensibile e i componenti di supporto sono nella parte inferiore.

I codici Gray sono utilizzati negli encoder di posizione lineari e rotativi ( encoder assoluti e encoder in quadratura ) rispetto alla codifica binaria ponderata. Ciò evita la possibilità che, quando più bit cambiano nella rappresentazione binaria di una posizione, una lettura errata risulterà da alcuni dei bit che cambiano prima di altri.

Ad esempio, alcuni encoder rotativi forniscono un disco che ha un pattern di codice Gray elettricamente conduttivo su anelli concentrici (tracce). Ogni traccia ha un contatto a molla metallica stazionario che fornisce un contatto elettrico al modello di codice conduttivo. Insieme, questi contatti producono segnali di uscita sotto forma di codice Gray. Altri codificatori utilizzano meccanismi senza contatto basati su sensori ottici o magnetici per produrre i segnali di uscita del codice Gray.

Indipendentemente dal meccanismo o dalla precisione di un encoder in movimento, l'errore di misurazione della posizione può verificarsi in posizioni specifiche (ai limiti del codice) perché il codice potrebbe cambiare nel momento esatto in cui viene letto (campionato). Un codice di uscita binario potrebbe causare errori significativi di misurazione della posizione perché è impossibile far cambiare tutti i bit esattamente nello stesso momento. Se, nel momento in cui viene campionata la posizione, alcuni bit sono cambiati e altri no, la posizione campionata sarà errata. Nel caso di encoder assoluti, la posizione indicata può essere lontana dalla posizione effettiva e, nel caso di encoder incrementali, ciò può danneggiare l'inseguimento della posizione.

Al contrario, il codice Gray utilizzato dagli encoder di posizione garantisce che i codici per due posizioni consecutive qualsiasi differiscano di un solo bit e, di conseguenza, solo un bit alla volta possa cambiare. In questo caso, l'errore di posizione massimo sarà piccolo, indicando una posizione adiacente alla posizione effettiva.

Algoritmi genetici

A causa delle proprietà della distanza di Hamming dei codici Gray, a volte vengono utilizzati negli algoritmi genetici . Sono molto utili in questo campo, poiché le mutazioni nel codice consentono modifiche per lo più incrementali, ma occasionalmente un singolo cambio di bit può causare un grande salto e portare a nuove proprietà.

Minimizzazione del circuito booleano

I codici grigi sono utilizzati anche nell'etichettare gli assi delle mappe di Karnaugh dal 1953 e nei grafici circolari di Händler dal 1958, entrambi metodi grafici per la minimizzazione del circuito logico .

Correzione dell'errore

Nelle moderne comunicazioni digitali , i codici Gray svolgono un ruolo importante nella correzione degli errori . Ad esempio, in uno schema di modulazione digitale come QAM in cui i dati vengono tipicamente trasmessi in simboli di 4 bit o più, il diagramma della costellazione del segnale è disposto in modo che i modelli di bit trasmessi dai punti della costellazione adiacenti differiscano di un solo bit. Combinando questo con la correzione dell'errore in avanti in grado di correggere gli errori a bit singolo, è possibile per un ricevitore correggere eventuali errori di trasmissione che fanno deviare un punto della costellazione nell'area di un punto adiacente. Ciò rende il sistema di trasmissione meno suscettibile al rumore .

Comunicazione tra domini di clock

I progettisti di logica digitale utilizzano ampiamente i codici Gray per passare informazioni di conteggio multi-bit tra la logica sincrona che opera a diverse frequenze di clock. La logica è considerata operante in diversi "domini di clock". È fondamentale per la progettazione di chip di grandi dimensioni che operano con molte frequenze di clock differenti.

Pedalare attraverso gli stati con il minimo sforzo

Se un sistema deve scorrere tutte le possibili combinazioni di stati on-off di alcuni set di controlli e le modifiche ai controlli richiedono spese non banali (ad es. tempo, usura, lavoro umano), un codice Gray riduce al minimo il numero di impostazioni cambia in un solo cambiamento per ogni combinazione di stati. Un esempio potrebbe essere il test di un sistema di tubazioni per tutte le combinazioni di impostazioni delle sue valvole ad azionamento manuale.

È possibile costruire un codice Gray bilanciato , che capovolga ogni bit con la stessa frequenza. Poiché i capovolgimenti di bit sono distribuiti uniformemente, ciò è ottimale nel modo seguente: i codici Gray bilanciati riducono al minimo il numero massimo di capovolgimenti di bit per ciascuna cifra.

Contatori in codice Gray e aritmetica

Già nel 1941 George R. Stibitz utilizzava un codice binario riflesso in un dispositivo di conteggio degli impulsi binario.

Un uso tipico dei contatori di codice Gray consiste nella creazione di un buffer di dati FIFO (first-in, first-out) che dispone di porte di lettura e scrittura che esistono in diversi domini di clock. I contatori di input e output all'interno di tale FIFO a doppia porta sono spesso memorizzati utilizzando il codice Gray per impedire l'acquisizione di stati transitori non validi quando il conteggio attraversa i domini di clock. I puntatori di lettura e scrittura aggiornati devono essere passati tra i domini di clock quando cambiano, per poter tenere traccia dello stato FIFO vuoto e pieno in ciascun dominio. Ogni bit dei puntatori viene campionato in modo non deterministico per questo trasferimento del dominio di clock. Quindi, per ogni bit, viene propagato il vecchio valore o il nuovo valore. Pertanto, se più di un bit nel puntatore multi-bit cambia nel punto di campionamento, è possibile propagare un valore binario "sbagliato" (né nuovo né vecchio). Garantendo che un solo bit possa essere modificato, i codici Gray garantiscono che gli unici possibili valori campionati siano il nuovo o il vecchio valore multi-bit. In genere vengono utilizzati codici Gray di lunghezza potenza di due.

A volte i bus digitali nei sistemi elettronici vengono utilizzati per convogliare quantità che possono solo aumentare o diminuire di uno alla volta, ad esempio l'uscita di un contatore di eventi che viene passato tra domini di clock o un convertitore digitale-analogico. Il vantaggio dei codici Gray in queste applicazioni è che le differenze nei ritardi di propagazione dei molti fili che rappresentano i bit del codice non possono far sì che il valore ricevuto attraversi stati al di fuori della sequenza del codice Gray. Questo è simile al vantaggio dei codici Gray nella costruzione di encoder meccanici, tuttavia la fonte del codice Gray in questo caso è un contatore elettronico. Il contatore stesso deve contare in codice Gray, o se il contatore funziona in binario, il valore di uscita dal contatore deve essere risincronizzato dopo che è stato convertito in codice Gray, perché quando un valore viene convertito da codice binario a codice Gray, è possibile che le differenze nei tempi di arrivo dei bit di dati binari nel circuito di conversione da binario a grigio significheranno che il codice potrebbe passare brevemente attraverso stati che sono selvaggiamente fuori sequenza. L'aggiunta di un registro temporizzato dopo il circuito che converte il valore di conteggio in codice Gray può introdurre un ciclo di latenza di clock, quindi il conteggio diretto in codice Gray può essere vantaggioso.

Per produrre il valore di conteggio successivo in un contatore a codice Gray, è necessario disporre di una logica combinatoria che incrementi il ​​valore di conteggio corrente memorizzato. Un modo per incrementare un numero di codice Gray è convertirlo in un normale codice binario, aggiungerne uno con un sommatore binario standard e quindi riconvertire il risultato in codice Gray. Altri metodi di conteggio in codice Gray sono discussi in un rapporto di Robert W. Doran , incluso prendere l'output dai primi latch delle infradito master-slave in un contatore di ripple binario.

Indirizzamento codice Gray

Poiché l'esecuzione del codice del programma in genere provoca un modello di accesso alla memoria delle istruzioni di indirizzi localmente consecutivi, le codifiche del bus che utilizzano l'indirizzamento del codice Gray invece dell'indirizzamento binario possono ridurre significativamente il numero di cambiamenti di stato dei bit di indirizzo, riducendo così il consumo energetico della CPU in alcuni -progettazioni di potenza.

Costruire un codice Gray a n bit

I primi passi del metodo di riflessione e prefisso.

Permutazione del codice Gray a 4 bit

La lista di codice Gray riflessa in modo binario per n bit può essere generata ricorsivamente dalla lista per n  − 1 bit riflettendo la lista (cioè elencando le voci in ordine inverso), anteponendo le voci nella lista originale con uno 0 binario , anteponendo il voci nell'elenco riflesso con un 1 binario  e quindi concatenando l'elenco originale con l'elenco invertito. Ad esempio, generando la  lista n = 3 dalla lista n  = 2:

Il codice Gray a un bit è G ₁  = ( 0,1 ). Questo può essere pensato come costruito ricorsivamente come sopra da un codice Gray a zero bit G ₀  = (  Λ  ) costituito da una singola voce di lunghezza zero. Questo processo iterativo di generazione di G _{n +1} da G _n rende chiare le seguenti proprietà del codice riflettente standard:

• G _n è una permutazione dei numeri 0, …, 2 ⁿ  − 1. (Ogni numero appare esattamente una volta nell'elenco.)
• G _n è incorporato come la prima metà di G _{n +1} .
• La codifica è quindi stabile , nel senso che un numero binario una volta che compare in G _n compare nella stessa posizione in tutte le liste più lunghe; quindi ha senso parlare del valore del codice Gray riflettente di un numero: G ( m ) = il m- esimo codice Gray riflettente, contando da 0.
• Ogni voce in G _n differisce di un solo bit dalla voce precedente. (La distanza di Hamming è 1.)
• L'ultima voce in G _n differisce solo di un bit dalla prima voce. (Il codice è ciclico.)

Queste caratteristiche suggeriscono un metodo semplice e veloce per tradurre un valore binario nel corrispondente codice Gray. Ogni bit viene invertito se il bit successivo superiore del valore di ingresso è impostato su uno. Questa può essere eseguita in parallelo con un'operazione di bit-shift e di Exclusive-or se disponibili: l' n- esimo codice Gray si ottiene calcolando . Anteponendo un bit 0 si lascia invariato l'ordine delle parole di codice, anteponendo un bit 1 si inverte l'ordine delle parole di codice. Se i bit nella posizione delle parole di codice vengono invertiti, l'ordine dei blocchi adiacenti di parole di codice viene invertito. Ad esempio, se il bit 0 viene invertito in una sequenza di parole di codice a 3 bit, l'ordine di due parole di codice adiacenti viene invertito ${\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,10,101,100,111,110  (inverti bit 0)

Se il bit 1 viene invertito, i blocchi di 2 codeword cambiano ordine:

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

Se il bit 2 è invertito, i blocchi di 4 parole di codice invertono l'ordine:

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

Pertanto, l'esecuzione di un'esclusiva o su un bit in posizione con il bit in posizione lascia intatto l'ordine delle parole di codice if , e inverte l'ordine dei blocchi di parole di codice if . Ora, questa è esattamente la stessa operazione del metodo di riflessione e prefisso per generare il codice Gray. ${\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}}}$

Un metodo simile può essere utilizzato per eseguire la traduzione inversa, ma il calcolo di ciascun bit dipende dal valore calcolato del bit successivo più alto, quindi non può essere eseguito in parallelo. Supponendo che sia il esimo bit codificato in Gray ( essendo il bit più significativo) e sia il esimo bit codificato binario ( essendo il bit più significativo), la traduzione inversa può essere data in modo ricorsivo: , e . In alternativa, la decodifica di un codice Gray in un numero binario può essere descritta come una somma di prefissi dei bit nel codice Gray, in cui ogni singola operazione di somma nella somma dei prefissi viene eseguita modulo due. ${\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}}$

Per costruire il codice Gray riflesso binario in modo iterativo, al passaggio 0 iniziare con , e al passaggio trovare la posizione del bit dell'1 meno significativo nella rappresentazione binaria di e capovolgere il bit in quella posizione nel codice precedente per ottenere il codice successivo . Le posizioni dei bit iniziano con 0, 1, 0, 2, 0, 1, 0, 3, …. Vedi trova il primo set per algoritmi efficienti per calcolare questi valori. ${\displaystyle \mathrm {codice} _{0}={\mathtt {0}}}$${\displaystyle i>0}$${\displaystyle i}$${\displaystyle \mathrm {codice} _{i-1}}$${\displaystyle \mathrm {codice} _{i}}$

Conversione da e verso codice Gray

Le seguenti funzioni in C convertono tra numeri binari e i loro codici Gray associati. Sebbene possa sembrare che la conversione da Gray a binario richieda che ogni bit venga gestito uno alla volta, esistono algoritmi più veloci.

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.

Tipi speciali di codici Gray

In pratica, "codice Gray" si riferisce quasi sempre a un codice Gray riflesso binario (BRGC). Tuttavia, i matematici hanno scoperto altri tipi di codici Gray. Come i BRGC, ognuno è costituito da un elenco di parole, in cui ogni parola differisce dalla successiva solo per una cifra (ogni parola ha una distanza di Hamming di 1 dalla parola successiva).

n -ario codice Gray

Esistono molti tipi specializzati di codici Gray diversi dal codice Gray riflesso binario. Uno di questi tipi di codice Gray è il codice Gray n- ario , noto anche come codice Gray non booleano . Come suggerisce il nome, questo tipo di codice Gray utilizza valori non booleani nelle sue codifiche.

Ad esempio, un codice Gray 3-ario ( ternario ) utilizzerebbe i valori 0,1,2. Il codice Gray ( n ,  k ) è il codice Gray n -ario con k cifre. La sequenza degli elementi nel codice (3, 2)-Gray è: 00,01,02,12,11,10,20,21,22. Il codice ( n ,  k )-Gray può essere costruito in modo ricorsivo, come il BRGC, o può essere costruito in modo iterativo . Viene presentato un algoritmo per generare iterativamente il codice ( N ,  k )-Gray (in 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]

Esistono altri algoritmi di codice Gray per ( n , k )-codici Gray. Il codice ( n , k )-Gray prodotto dal suddetto algoritmo è sempre ciclico; alcuni algoritmi, come quello di Guan, mancano di questa proprietà quando k è dispari. D'altra parte, mentre cambia solo una cifra alla volta con questo metodo, può cambiare avvolgendo (loop da n  − 1 a 0). Nell'algoritmo di Guan, il conteggio aumenta e diminuisce alternativamente, in modo che la differenza numerica tra due cifre del codice Gray sia sempre uno.

I codici Gray non sono definiti in modo univoco, perché anche una permutazione delle colonne di tale codice è un codice Gray. La procedura di cui sopra produce un codice in cui minore è il significato di una cifra, più spesso cambia, rendendola simile ai normali metodi di conteggio.

Vedere anche Skew Binary Number System , una variante del sistema numerico ternario in cui al massimo due cifre cambiano ad ogni incremento, poiché ogni incremento può essere eseguito con al massimo un'operazione di riporto di una cifra .

Codice grigio bilanciato

Sebbene il codice Gray riflesso binario sia utile in molti scenari, non è ottimale in alcuni casi a causa della mancanza di "uniformità". Nei codici Gray bilanciati , il numero di modifiche nelle diverse posizioni delle coordinate è il più vicino possibile. Per rendere questo più preciso, sia G un ciclo di Gray completo R -ario avente sequenza di transizione ; i conteggi delle transizioni ( spettro ) di G sono l'insieme di interi definiti da ${\displaystyle (\delta _{k})}$

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

Un codice Gray è uniforme o uniformemente bilanciato se i suoi conteggi di transizione sono tutti uguali, nel qual caso abbiamo per tutti k . Chiaramente, quando , tali codici esistono solo se n è una potenza di 2. Altrimenti, se n non divide uniformemente, è possibile costruire codici ben bilanciati in cui ogni conteggio delle transizioni è o . I codici grigi possono anche essere bilanciati in modo esponenziale se tutti i loro conteggi di transizione sono potenze di due adiacenti e tali codici esistono per ogni potenza di due. ${\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}$

Ad esempio, un codice Gray bilanciato a 4 bit ha 16 transizioni, che possono essere distribuite uniformemente tra tutte e quattro le posizioni (quattro transizioni per posizione), rendendolo uniformemente bilanciato:

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

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

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

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

mentre un codice Gray bilanciato a 5 bit ha un totale di 32 transizioni, che non possono essere distribuite uniformemente tra le posizioni. In questo esempio, quattro posizioni hanno sei transizioni ciascuna e una ne ha otto:

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

Mostreremo ora una costruzione e implementazione per codici Gray binari ben bilanciati che ci permette di generare un codice Gray bilanciato a n cifre per ogni n . Il principio principale è costruire induttivamente un  codice Gray di ( n + 2) cifre dato un codice Gray G di n cifre in modo tale che la proprietà bilanciata sia preservata. Per fare ciò, consideriamo partizioni di in un numero pari L di blocchi non vuoti della forma ${\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\} ,\sinistra\{g_{-1}\destra\}}$

dove , , e ). Questa partizione induce un codice Gray a -cifre dato da ${\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}}$

Se definiamo le molteplicità di transizione

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

essere il numero di volte in cui la cifra in posizione i cambia tra blocchi consecutivi in ​​una partizione, quindi per il  codice Gray ( n + 2) cifre indotto da questa partizione lo spettro di transizione è ${\displaystyle \lambda '_{i}}$

${\displaystyle \lambda '_{i}={\begin{casi}4\lambda _{i}-2m_{i},&{\text{if }}0\leq i<n\\L,&{ \text{ altrimenti }}\end{casi}}}$

La parte delicata di questa costruzione è trovare un'adeguata partizione di un codice Gray bilanciato di n cifre tale che il codice da esso indotto rimanga equilibrato, ma per questo contano solo le molteplicità di transizione; unire due blocchi consecutivi su una transizione di cifra e dividere un altro blocco su un'altra transizione di cifra produce un codice Gray diverso con esattamente lo stesso spettro di transizione , quindi si può ad esempio designare le prime transizioni a cifra come quelle che cadono tra due blocchi. Si possono trovare codici uniformi quando e , e questa costruzione può essere estesa anche al caso R- ario. ${\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}}}$

Codici grigi di lunga durata

I codici Gray a lungo termine massimizzano la distanza tra modifiche consecutive di cifre nella stessa posizione. Cioè, la lunghezza minima di esecuzione di qualsiasi bit rimane invariata il più a lungo possibile.

Codici grigi monotonici

I codici monotonici sono utili nella teoria delle reti di interconnessione, in particolare per ridurre al minimo la dilatazione per array lineari di processori. Se definiamo il peso di una stringa binaria come il numero di 1 nella stringa, allora anche se chiaramente non possiamo avere un codice Gray con peso strettamente crescente, potremmo voler approssimare questo facendo scorrere il codice attraverso due pesi adiacenti prima di raggiungere il prossimo.

Possiamo formalizzare il concetto di codici Gray monotoni come segue: si consideri la partizione dell'ipercubo in livelli di vertici che hanno uguale peso, cioè ${\displaystyle Q_{n}=(V_{n},E_{n})}$

${\displaystyle V_{n}(i)=\{v\in V_{n}:v{\text{ ha un peso }}i\}}$

per . Questi livelli soddisfano . Sia il sottografo di indotto da , e siano gli archi in . Un codice Gray monotono è quindi un percorso hamiltoniano in modo tale che ogni volta che viene prima nel percorso, allora . ${\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}\in E_{n}(i)}$${\displaystyle \delta _{2}\in E_{n}(j)}$${\displaystyle i\leq j}$

Un'elegante costruzione di codici Gray monotoni di n cifre per qualsiasi n si basa sull'idea di costruire ricorsivamente sottopercorsi di lunghezza aventi bordi in . Definiamo , quando o , e ${\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} }$

altrimenti. Qui è una permutazione opportunamente definita e si riferisce al cammino P con le sue coordinate permutate da . Questi cammini danno origine a due codici Gray monotoni di n cifre e dati da ${\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 {\ testo{ e }}G_{n}^{(2)}=P_{n,0}^{R}P_{n,1}P_{n,2}^{R}P_{n,3}\cdots }$

La cui scelta garantisce che questi codici siano effettivamente codici Gray risulta essere . I primi valori di sono mostrati nella tabella sottostante. ${\displaystyle \pi _{n}}$${\displaystyle \pi _{n}=E^{-1}\left(\pi _{n-1}^{2}\right)}$${\displaystyle P_{n,j}}$

Sottopercorsi nell'algoritmo Savage-Winkler

${\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

Questi codici Gray monotonici possono essere implementati in modo efficiente in modo tale che ogni elemento successivo possa essere generato in tempo O ( n ). L'algoritmo è più facilmente descritto usando le coroutine .

I codici monotonici hanno un'interessante connessione con la congettura di Lovász , la quale afferma che ogni grafo transitivo vertice connesso contiene un cammino hamiltoniano. Il sottografo "livello medio" è vertex-transitive (cioè, il suo gruppo di automorfismi è transitivo, così che ogni vertice ha lo stesso "ambiente locale"" e non può essere differenziato dagli altri, poiché possiamo rietichettare le coordinate così come le cifre binarie per ottenere un automorfismo ) e il problema di trovare un cammino hamiltoniano in questo sottografo è chiamato "problema dei livelli medi", che può fornire intuizioni nella congettura più generale. Alla domanda è stata data risposta affermativa per , e la precedente la costruzione per codici monotonici assicura un cammino hamiltoniano di lunghezza almeno 0.839 N dove N è il numero di vertici nel sottografo di livello medio. ${\displaystyle Q_{2n+1}(n)}$${\displaystyle n\leq 15}$

Beckett–Codice Gray

Un altro tipo di codice Gray, il codice Beckett-Gray , prende il nome dal drammaturgo irlandese Samuel Beckett , che era interessato alla simmetria . Il suo gioco " Quad " presenta quattro attori ed è diviso in sedici periodi di tempo. Ogni periodo si conclude con uno dei quattro attori che entra o esce dal palco. La commedia inizia con un palcoscenico vuoto e Beckett voleva che ogni sottoinsieme di attori apparisse sul palco esattamente una volta. Chiaramente l'insieme degli attori attualmente in scena può essere rappresentato da un codice Gray binario a 4 bit. Beckett, tuttavia, ha posto un'ulteriore restrizione alla sceneggiatura: desiderava che gli attori entrassero e uscissero in modo che l'attore che era stato sul palco più a lungo fosse sempre quello che usciva. Gli attori potrebbero quindi essere rappresentati da un first in, first out queue , in modo che (degli attori in scena) l'attore che viene rimosso dalla coda sia sempre quello che è stato messo in coda per primo. Beckett non è stato in grado di trovare un codice Beckett-Gray per il suo gioco, e in effetti, un elenco esaustivo di tutte le possibili sequenze rivela che tale codice non esiste per n = 4. Oggi è noto che tali codici esistono per n = 2, 5 , 6, 7, e 8, e non esistono per n = 3 o 4. un esempio di un codice di Beckett-grigio a 8 bit possono essere trovati in Donald Knuth 's Art of Computer Programming . Secondo Sawada e Wong, lo spazio di ricerca per n = 6 può essere esplorato in 15 ore e sono state trovate più di 9.500 soluzioni per il caso n = 7.

Codici Snake-in-the-box

Lunghezze massime dei serpenti ( L _s ) e delle spire ( L _c ) nel problema degli snakes-in-the-box per le dimensioni n da 1 a 4

I codici Snake-in-the-box , o serpenti , sono le sequenze di nodi di percorsi indotti in un grafo ipercubo n- dimensionale , e i codici coil-in-the-box, o bobine , sono le sequenze di nodi di cicli indotti in un ipercubo. Viste come codici Gray, queste sequenze hanno la proprietà di poter rilevare qualsiasi errore di codifica a bit singolo. Codici di questo tipo furono descritti per la prima volta da William H. Kautz alla fine degli anni '50; da allora, ci sono state molte ricerche per trovare il codice con il maggior numero possibile di parole in codice per una data dimensione dell'ipercubo.

Codice Gray a traccia singola

Ancora un altro tipo di codice Gray è il codice Gray a traccia singola (STGC) sviluppato da Norman B. Spedding e perfezionato da Hiltgen, Paterson e Brandestini in "Codici Gray a traccia singola" (1996). L'STGC è un elenco ciclico di P codifiche binarie uniche di lunghezza n tale che due parole consecutive differiscono esattamente in una posizione, e quando l'elenco viene esaminato come una matrice P  ×  n , ogni colonna è uno spostamento ciclico della prima colonna.

Codice Gray a singola pista con 5 sensori.

Versione animata e codificata a colori del rotore STGC.

Il nome deriva dal loro utilizzo con encoder rotativi , in cui un numero di tracce viene rilevato dai contatti, risultando per ciascuna in un'uscita di 0 o 1 . Per ridurre il rumore dovuto a contatti diversi che non commutano esattamente nello stesso momento, si predispongono preferibilmente le tracce in modo che i dati in uscita dai contatti siano in codice Gray. Per ottenere un'elevata precisione angolare, sono necessari molti contatti; per ottenere una precisione di almeno 1° sono necessarie almeno 360 posizioni distinte per giro, il che richiede un minimo di 9 bit di dati, e quindi lo stesso numero di contatti.

Se tutti i contatti sono posizionati nella stessa posizione angolare, sono necessarie 9 tracce per ottenere un BRGC standard con una precisione di almeno 1°. Tuttavia, se il produttore sposta un contatto in una posizione angolare diversa (ma alla stessa distanza dall'albero centrale), il corrispondente "schema ad anello" deve essere ruotato dello stesso angolo per fornire la stessa uscita. Se il bit più significativo (l'anello interno in Figura 1) viene ruotato a sufficienza, corrisponde esattamente all'anello successivo. Poiché entrambi gli anelli sono identici, l'anello interno può essere tagliato e il sensore per quell'anello spostato sull'anello rimanente identico (ma spostato a quell'angolo dall'altro sensore su quell'anello). Questi due sensori su un singolo anello formano un encoder in quadratura. Ciò riduce il numero di tracce per un encoder angolare "risoluzione 1°" a 8 tracce. Con BRGC non è possibile ridurre ulteriormente il numero di tracce.

Per molti anni, Torsten Sillke e altri matematici hanno creduto che fosse impossibile codificare la posizione su una singola traccia in modo tale che posizioni consecutive differissero per un solo sensore, ad eccezione dell'encoder in quadratura a 2 sensori e 1 traccia. Quindi, per le applicazioni in cui 8 tracce erano troppo ingombranti, le persone hanno utilizzato encoder incrementali a traccia singola (encoder in quadratura) o encoder "encoder in quadratura + tacca di riferimento" a 2 tracce.

Norman B. Spedding, tuttavia, ha registrato un brevetto nel 1994 con diversi esempi che dimostrano che era possibile. Sebbene non sia possibile distinguere 2 ⁿ posizioni con n sensori su una singola traccia, è possibile distinguerne così tante. Etzion e Paterson congetturano che quando n è esso stesso una potenza di 2, n sensori possono distinguere al massimo 2 ⁿ  - 2 n posizioni e che per il primo n il limite è 2 ⁿ  - 2 posizioni. Gli autori hanno continuato a generare un codice a traccia singola di 504 posizioni di lunghezza 9 che ritengono ottimale. Poiché questo numero è maggiore di 2 ⁸ = 256, ogni codice richiede più di 8 sensori, sebbene un BRGC possa distinguere 512 posizioni con 9 sensori.

Un STGC per P  = 30 e n  = 5 è riprodotto qui:

Codice Gray a binario singolo per 30 posizioni

Angolo	Codice		Angolo	Codice		Angolo	Codice		Angolo	Codice		Angolo	Codice
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

Ogni colonna è uno spostamento ciclico della prima colonna e da qualsiasi riga alla riga successiva cambia solo un bit. La natura a binario singolo (come una catena di codici) è utile nella fabbricazione di queste ruote (rispetto a BRGC), poiché è necessaria una sola pista, riducendo così il loro costo e le dimensioni. La natura del codice Gray è utile (rispetto ai codici a catena , detti anche sequenze di De Bruijn ), poiché cambierà solo un sensore alla volta, quindi l'incertezza durante una transizione tra due stati discreti sarà solo più o meno un'unità di angolo misurazione che il dispositivo è in grado di risolvere.

Codice Gray bidimensionale

Un diagramma di costellazione in codice Gray per rettangolare 16- QAM

I codici Gray bidimensionali vengono utilizzati nella comunicazione per ridurre al minimo il numero di errori di bit nei punti adiacenti della costellazione con modulazione di ampiezza in quadratura (QAM) . In una codifica tipica i punti della costellazione adiacenti orizzontali e verticali differiscono di un singolo bit e i punti adiacenti diagonali differiscono di 2 bit.

I codici Gray bidimensionali hanno anche usi negli schemi di identificazione della posizione , in cui il codice verrebbe applicato a mappe di area come una proiezione di Mercatore della superficie terrestre e un'appropriata funzione di distanza bidimensionale ciclica come la metrica di Mannheim da utilizzare per calcolare il distanza tra due posizioni codificate, combinando così le caratteristiche della distanza di Hamming con la continuazione ciclica di una proiezione di Mercatore.

isometria grigia

La mappatura biunivoca { 0 ↔ 00 , 1 ↔ 01 , 2 ↔ 11 , 3 ↔ 10 } stabilisce un'isometria tra lo spazio metrico sul campo finito con la metrica data dalla distanza di Hamming e lo spazio metrico sull'anello finito (il solito aritmetica modulare ) con la metrica data dalla distanza di Lee . La mappatura è opportunamente estesa ad un'isometria degli spazi di Hamming e . Le sue menzogne importanza per stabilire una corrispondenza tra vari "buona", ma non necessariamente codici lineari come grigio-map immagini in di codici anello lineare da . ${\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}}$

Codici correlati

Esistono numerosi codici binari simili ai codici Gray, tra cui:

• I codici Datex alias codici Giannini (1954), come descritto da Carl P. Spaulding, utilizzano una variante del codice O'Brien II .
• I codici usati da Varec (ca. 1954), usano una variante del codice I di O'Brien così come le varianti del codice Gray in base 12 e in base 16.
• Codice Lucal (1959) alias codice binario riflesso modificato (MRB)
• Codice Gillham (1961/1962), utilizza una variante del codice Datex e il codice O'Brien II .
• Codice di Leslie e Russell (1964)
• Codice di stabilimento del radar reale
• Codice Hoklas (1988)

Anche i seguenti codici decimali in codice binario (BCD) sono varianti del codice Gray:

• Codice Petherick (1953), noto anche come codice RAE ( Royal Aircraft Establishment ).
• Codici O'Brien I e II (1955) (Un codice O'Brien di tipo I era già stato descritto da Frederic A. Foss dell'IBM e utilizzato da Varec nel 1954. Più tardi, era noto anche come codice Watts o Watt riflesso decimale ( WRD) ed è talvolta ambiguamente indicato come codice Gray modificato binario riflesso. Un codice O'Brien di tipo II era già utilizzato da Datex nel 1954.)
• Eccesso-3 codice Gray (1956) (alias Grey eccesso-3 codice Gray Code 3-eccesso, riflesso codice eccesso-3, codice Gray eccesso, codice eccesso grigio, 10-eccesso-3 codice Gray o codice Gray-Stibitz), descritto da Frank P. Turvey Jr. di ITT .
• Codici Tompkins I e II (1956)
• Codice Glixon (1957), talvolta ambiguamente chiamato anche codice Gray modificato

Guarda anche

• Registro a scorrimento a retroazione lineare
• Sequenza di De Bruijn - un codice Gray su un alfabeto più grande di 0,1.
• Algoritmo di Steinhaus-Johnson-Trotter - un algoritmo che genera codici Gray per il sistema numerico fattoriale
• Codice distanza minima
• Sequenza Prouhet-Gio-Morse - relativa al codice Gray inverso
• formula Ryser
• curva di Hilbert

Appunti

Riferimenti

Ulteriori letture

• Richards, Richard Kohler (1955). Operazioni aritmetiche nei computer digitali (5 ed.). New York, USA: D. Van Nostrand Co., Inc.
• Richards, Richard Kohler (1967). Componenti e circuiti elettronici digitali . D. Van Nostrand Co., Inc. pp. 490, 500-504, 510-511.
• Nero, Paul E. (2004-02-25). "Codice grigio" . NIST .
• Stampa, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). "Sezione 22.3. Codici grigi" . Ricette numeriche: L'arte del calcolo scientifico (3a ed.). New York, USA: Cambridge University Press . ISBN 978-0-521-88068-8.
• Selvaggio, Carla Diane (1997). "Un'indagine sui codici grigi combinatori" . Recensione SIAM . Società di Matematica Industriale e Applicata (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). "Capitoli 1-3". Algoritmi combinatori: un aggiornamento . Società di Matematica Industriale e Applicata (SIAM). ISBN 0-89871-231-9.
• Dewar, Megan; Stevens, Brett (2012-08-29). Ordinazione di modelli di blocchi – Codici Gray, cicli universali e configurazione . CMS Libri in Matematica (1 ed.). 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]. "Fondamenti del codice grigio" . Progettare come fare . EETimes . Parte 1. Archiviato dall'originale il 30-10-2017 . Estratto 30-10-2017 . Parte 2 Parte 3
• Warren, Jr., Henry S. (2013). "Capitolo 13: Codice grigio". Delizia dell'hacker (2 ed.). Addison Wesley - Pearson Education, Inc. pp. 311-317. ISBN 978-0-321-84268-8. (7 pagine)
• Zinovik, Igor; Kroening, Daniel; Chebiryak, Yury (2008-03-21). "Calcolo di codici Gray combinatori binari tramite ricerca esaustiva con risolutori SAT" . Transazioni IEEE sulla teoria dell'informazione . IEEE . 54 (4): 1819-1823. doi : 10.1109/TIT.2008.917695 . hdl : 20.500.11850/11304 . S2CID  2854180 . (5 pagine)
• O'Brien, Joseph A. (giugno 1957). "Traduttori di codice binario-decimale unità-distanza" . Transazioni IRE su computer elettronici . EC-6 (2): 122-123. doi : 10.1109/TEC.1957.5221585 . ISSN  0367-9950 . Estratto il 25/05/2020 . (2 pagine)
• Barr, KG (marzo 1981). "Un codice Gray decimale – Facilmente convertibile per la codifica della posizione dell'albero" (PDF) . Mondo senza fili . vol. 87 n. 1542. Facoltà di Scienze Naturali, Università delle Indie Occidentali . pp. 86-87. Archiviato (PDF) dall'originale il 28-07-2020 . Estratto il 28-07-2020 .

link esterno

• Dimostrazione "Gray Code" di Michael Schreiber, Wolfram Demonstrations Project (con implementazione di Mathematica). 2007.
• Dizionario NIST di algoritmi e strutture dati: codice Gray .
• Guida per gli autostoppisti al calcolo evolutivo, Q21: Cosa sono i codici Gray e perché vengono utilizzati? , incluso il codice C per convertire tra binario e BRGC.
• Dragos A. Harabor utilizza i codici Gray in un digitalizzatore 3D .
• I codici gray a traccia singola, i codici a catena binaria ( Lancaster 1994 ) e i registri a scorrimento a retroazione lineare sono tutti utili per trovare la propria posizione assoluta su un encoder rotativo a traccia singola (o altro sensore di posizione).
• Colonna AMS: codici grigi
• Generatore di ruote con encoder ottico
• ProtoTalk.net – Comprensione della codifica in quadratura – Copre la codifica in quadratura in modo più dettagliato con un focus sulle applicazioni robotiche