Il codice Gray è un tipo di sistema numerico binario in cui cambia solo un bit alla volta. Oggi il codice grigio è ampiamente utilizzato nel mondo digitale. Sarà utile per la correzione degli errori e la trasmissione del segnale. Il contatore Gray è utile anche nella progettazione e nella verifica nel dominio VLSI.
Un codice Gray codifica gli interi come sequenze di bit con la proprietà che le rappresentazioni degli interi adiacenti differiscono esattamente in una posizione binaria.
Esistono diversi tipi di codici grigi, ad esempio bilanciato, riflesso binario, gap massimo e codice grigio antipodale.
I contatori hanno la funzione primaria di produrre una sequenza di output specificata e vengono talvolta definiti generatori di pattern.
Progetto
In un codice grigio cambia solo un bit alla volta. Questo codice di progettazione ha due ingressi, segnali di clock e reset e un'uscita a 4 bit che genererà il codice grigio.
Innanzitutto, se il prima il segnale è alto, l'uscita sarà zero e non appena prima va basso, sul fronte ascendente di clk , il progetto genererà un codice grigio a quattro bit e continuerà a generare ad ogni fronte di salita clk segnale.
Questo codice di progettazione può essere aggiornato e inserire numeri binari come input e questo progetto funzionerà come convertitore di codice da binario a grigio.
module gray_ctr # (parameter N = 4) ( input clk, input rstn, output reg [N-1:0] out); reg [N-1:0] q; always @ (posedge clk) begin if (!rstn) begin q <= 0; out <="0;" end else begin q + 1; `ifdef for_loop for (int i="0;" n-1; out[i] ^ q[i]; out[n-1] `else q[n-1:1] q[n-2:0]}; `endif endmodule pre> <h3>Hardware Schematic</h3> <img src="//techcodeview.com/img/verilog-tutorial/27/verilog-gray-counter-2.webp" alt="Verilog Gray Counter"> <h3>Testbench</h3> <pre> module tb; parameter N = 4; reg clk; reg rstn; wire [N-1:0] out; gray_ctr u0 ( .clk(clk), .rstn(rstn), .out(out)); always #10 clk = ~clk; initial begin {clk, rstn} <= 0; $monitor ('t="%0t" rstn="%0b" out="0x%0h'," $time, rstn, out); repeat(2) @ (posedge clk); <="1;" repeat(20) $finish; end endmodule pre> <p>And it produces the following output, such as:</p> <pre> ncsim> run T=0 rstn=0 out=0xx T=10 rstn=0 out=0x0 T=30 rstn=1 out=0x0 T=50 rstn=1 out=0x1 T=70 rstn=1 out=0x3 T=90 rstn=1 out=0x2 T=110 rstn=1 out=0x6 T=130 rstn=1 out=0x7 T=150 rstn=1 out=0x5 T=170 rstn=1 out=0x4 T=190 rstn=1 out=0xc T=210 rstn=1 out=0xd T=230 rstn=1 out=0xf T=250 rstn=1 out=0xe T=270 rstn=1 out=0xa T=290 rstn=1 out=0xb T=310 rstn=1 out=0x9 T=330 rstn=1 out=0x8 T=350 rstn=1 out=0x0 T=370 rstn=1 out=0x1 T=390 rstn=1 out=0x3 T=410 rstn=1 out=0x2 Simulation complete via $finish(1) at time 430 NS + 0 </pre> <h3>Balanced Gray Code</h3> <p>In balanced Gray codes, the number of changes in different coordinate positions is as close as possible.</p> <p>A Gray code is <strong> <em>uniform</em> </strong> or <strong> <em>uniformly</em> </strong> balanced if its transition counts are all equal.</p> <p>Gray codes can also be <strong> <em>exponentially</em> </strong> balanced if all of their transition counts are adjacent powers of two, and such codes exist for every power of two.</p> <p>For example, a balanced 4-bit Gray code has 16 transitions, which can be evenly distributed among all four positions (four transitions per position), making it uniformly balanced.</p> <pre> 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 </pre> <h3>n-ary Gray Code</h3> <p>There are many specialized types of Gray codes other than the binary-reflected Gray code. One such type of Gray code is the n-ary Gray code, also known as a <strong> <em>non-Boolean</em> </strong> Gray code. As the name implies, this type of Gray code uses non-Boolean values in its encodings.</p> <p>For example, a 3-ary ternary Gray code would use the values {0, 1, and 2}. The (n, k)-Gray code is the n-ary Gray code with k digits. The sequence of elements in the (3, 2)-Gray code is: {00, 01, 02, 12, 11, 10, 20, 21, and 22}.</p> <p>The (n, k)-Gray code may be constructed recursively, as the BRGC, or may be constructed iteratively.</p> <h3>Monotonic Gray Codes</h3> <p>Monotonic codes are useful in interconnection networks theory, especially for minimizing dilation for linear arrays of processors.</p> <p>If we define the weight of a binary string to be the number of 1s in the string, then although we clearly cannot have a Gray code with strictly increasing weight, we may want to approximate this by having the code run through two adjacent weights before reaching the next one.</p> <h3>Beckett-Gray Code</h3> <p>Another type of Gray code, the Beckett-Gray code, is named for Irish playwright <strong> <em>Samuel Beckett</em> </strong> , who was interested in <strong> <em>symmetry</em> </strong> . His play <strong> <em>Quad</em> </strong> features four actors and is divided into sixteen time periods. Each period ends with one of the four actors entering or leaving the stage.</p> <p>The play begins with an empty stage, and Beckett wanted each subset of actors to appear on stage exactly once. A 4-bit binary Gray code can represent the set of actors currently on stage.</p> <p>However,</p> <p>Beckett placed an additional restriction on the script: he wished the actors to enter and exit so that the actor who had been on stage the longest would always be the one to exit.</p> <p>The actors could then be represented by a first-in, first-out (FIFO) queue so that the actor being dequeued is always the one who was enqueued first.</p> <p>Beckett was unable to find a Beckett-Gray code for his play, and indeed, an exhaustive listing of all possible sequences reveals that no such code exists for n = 4. It is known today that such codes do exist for n = 2, 5, 6, 7, and 8, and do not exist for n = 3 or 4.</p> <h3>Snake-in-the-box Codes</h3> <p>Snake-in-the-box codes, or snakes, are the sequences of nodes of induced paths in an n-dimensional <strong> <em>hypercube</em> </strong> graph, and coil-in-the-box codes, or coils, are the sequences of nodes of induced cycles in a hypercube.</p> <p>Viewed as Gray codes, these sequences have the property of detecting any single-bit coding error.</p> <h3>Single-track Gray Code</h3> <p>Another kind of Gray code is the single-track Gray code (STGC) developed by <strong> <em>Norman B. Spedding</em> </strong> and refined by <strong> <em>Hiltgen, Paterson</em> </strong> and <strong> <em>Brandestini</em> </strong> in 'Single-track Gray codes' (1996).</p> <p>The STGC is a cyclical list of P unique binary encodings of length n such that two consecutive words differ in exactly one position. When the list is examined as a P × n matrix, each column is a cyclic shift of the first column.</p> <p>The name comes from their use with rotary encoders, where many tracks are being sensed by contacts, resulting in each in an output of 0 or 1. To reduce noise due to different contacts not switching the same moment in time, one preferably sets up the tracks so that the contacts' data output is in Gray code.</p> <p>To get high angular accuracy, one needs lots of contacts; to achieve at least 1-degree accuracy, one needs at least 360 distinct positions per revolution, which requires a minimum of 9 bits of data and the same number of contacts.</p> <p>If all contacts are placed at the same angular position, then 9 tracks are needed to get a standard BRGC with at least 1-degree accuracy. However, if the manufacturer moves a contact to a different angular position but at the same distance from the center shaft, then the corresponding 'ring pattern' needs to be rotated the same angle to give the same output.</p> <h3>Two-dimensions Gray Code</h3> <p>Two-dimensional Gray codes are used in communication to minimize the number of bit errors in quadrature amplitude modulation adjacent points in the constellation.</p> <p>In a standard encoding, the horizontal and vertical adjacent constellation points differ by a single bit, and adjacent diagonal points differ by 2 bits.</p> <hr></=></pre></=> Codice grigio equilibrato
Nei codici Gray bilanciati, il numero di cambiamenti nelle diverse posizioni delle coordinate è il più vicino possibile.
Un codice Gray è uniforme O uniformemente bilanciato se i conteggi delle sue transizioni sono tutti uguali.
Possono anche esserlo i codici grigi esponenzialmente bilanciati se tutti i conteggi delle loro transizioni sono potenze adiacenti di due, e tali codici esistono per ogni potenza di due.
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
Codice Gray n-ario
Esistono molti tipi specializzati di codici Gray diversi dal codice Gray riflesso in binario. Uno di questi tipi di codice Gray è il codice Gray n-ario, noto anche come a non booleano Codice grigio. Come suggerisce il nome, questo tipo di codice Gray utilizza valori non booleani nelle sue codifiche.
Ad esempio, un codice Gray ternario a 3 arie utilizzerebbe i valori {0, 1 e 2}. Il codice (n, k)-Gray è il codice Gray n-ario con k cifre. La sequenza di elementi nel codice (3, 2)-Gray è: {00, 01, 02, 12, 11, 10, 20, 21 e 22}.
Il codice (n, k)-Gray può essere costruito ricorsivamente, come il BRGC, o può essere costruito iterativamente.
Codici grigi monotoni
I codici monotonici sono utili nella teoria delle reti di interconnessione, in particolare per ridurre al minimo la dilatazione per matrici lineari di processori.
Se definiamo il peso di una stringa binaria come il numero di 1 nella stringa, anche se chiaramente non possiamo avere un codice Gray con peso strettamente crescente, potremmo volerlo approssimare facendo passare il codice attraverso due pesi adiacenti prima di raggiungere il prossimo.
Codice Beckett-Gray
Un altro tipo di codice Gray, il codice Beckett-Gray, prende il nome dal drammaturgo irlandese Samuel Beckett , a chi era interessato simmetria . Il suo gioco Quadruplo presenta quattro attori ed è diviso in sedici periodi di tempo. Ogni periodo termina con l'entrata o l'uscita di scena di uno dei quattro attori.
Lo spettacolo inizia con un palco vuoto e Beckett voleva che ogni sottoinsieme di attori apparisse sul palco esattamente una volta. Un codice Gray binario a 4 bit può rappresentare l'insieme degli attori attualmente sul palco.
Tuttavia,
Beckett pose un'ulteriore restrizione sulla sceneggiatura: voleva che gli attori entrassero e uscissero in modo che ad uscire fosse sempre l'attore che era stato sul palco più a lungo.
Gli attori potrebbero quindi essere rappresentati da una coda FIFO (first-in, first-out) in modo che l'attore rimosso dalla coda sia sempre quello accodato per primo.
Beckett non è riuscito a trovare un codice Beckett-Gray per la sua opera teatrale 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.
Codici Snake-in-the-box
I codici Snake-in-the-box, o serpenti, sono le sequenze di nodi di percorsi indotti in un sistema n-dimensionale ipercubo grafico 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 rilevare qualsiasi errore di codifica a bit singolo.
Codice Gray a binario singolo
Un altro tipo di codice Gray è il codice Gray a traccia singola (STGC) sviluppato da Norman B. Spedding e raffinato da Hiltgen, Paterson E Brandestini in 'Codici Gray a traccia singola' (1996).
L'STGC è un elenco ciclico di P codifiche binarie univoche di lunghezza n tale che due parole consecutive differiscono esattamente in una posizione. Quando l'elenco viene esaminato come una matrice P × n, ciascuna colonna è uno spostamento ciclico della prima colonna.
algoritmo per bfs
Il nome deriva dal loro utilizzo con gli encoder rotativi, dove molte tracce vengono rilevate dai contatti, risultando in ciascuna un'uscita di 0 o 1. Per ridurre il rumore dovuto a contatti diversi che non commutano nello stesso momento nel tempo, è preferibile impostare il tracce in modo che l'output dei dati dei contatti sia in codice Gray.
Per ottenere un'elevata precisione angolare sono necessari molti contatti; per ottenere una precisione di almeno 1 grado, sono necessarie almeno 360 posizioni distinte per giro, il che richiede un minimo di 9 bit di dati e 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 grado. Tuttavia, se il produttore sposta un contatto in una posizione angolare diversa ma alla stessa distanza dall'albero centrale, il corrispondente 'modello di anello' deve essere ruotato dello stesso angolo per fornire lo stesso output.
Codice Grigio Bidimensionale
I codici Gray bidimensionali vengono utilizzati nella comunicazione per ridurre al minimo il numero di errori di bit nella modulazione di ampiezza in quadratura punti adiacenti nella costellazione.
In una codifica standard, i punti adiacenti della costellazione orizzontali e verticali differiscono di un singolo bit, mentre i punti diagonali adiacenti differiscono di 2 bit.