Gråkode er et slags binært tallsystem der bare én bit vil endre seg om gangen. I dag er grå kode mye brukt i den digitale verden. Det vil være nyttig for feilretting og signaloverføring. Grey-telleren er også nyttig i design og verifisering i VLSI-domenet.
En grå kode koder heltall som sekvenser av biter med egenskapen at representasjonene av tilstøtende heltall er forskjellige i nøyaktig én binær posisjon.
Det finnes forskjellige typer grå koder, for eksempel Balansert, Binær reflektert, Maksimal Gap og Antipodal Grå kode.
Tellere har en primær funksjon for å produsere en spesifisert utgangssekvens og blir noen ganger referert til som mønstergeneratorer.
Design
I en grå kode endres bare én bit om gangen. Denne designkoden har to innganger, klokke- og tilbakestillingssignaler og en 4-bits utgang som vil generere grå kode.
For det første, hvis rstn signalet er høyt, vil utgangen være null, og så snart rstn går lavt, på den stigende kanten av klk , vil designet generere en fire-bits grå kode og fortsette å generere ved hver stigende kant av klk signal.
Denne designkoden kan oppgraderes og sette inn binære tall som input, og denne designen vil fungere som en binær til grå kodekonverter.
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></=> Balansert grå kode
I balanserte gråkoder er antallet endringer i ulike koordinatposisjoner så nært som mulig.
En grå kode er uniform eller jevnt balansert hvis alle overgangstallene er like.
Grå koder kan også være eksponensielt balansert hvis alle overgangstallene deres er tilstøtende potenser av to, og slike koder eksisterer for hver potens av to.
For eksempel har en balansert 4-bits grå kode 16 overganger, som kan fordeles jevnt mellom alle fire posisjoner (fire overganger per posisjon), noe som gjør den jevnt balansert.
0 1 1 1 1 1 1 0 0 0 0 0 0 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
n-ær grå kode
Det er mange spesialiserte typer Gray-koder andre enn den binærreflekterte Gray-koden. En slik type grå kode er n-ær grå kode, også kjent som en ikke-boolsk Grå kode. Som navnet tilsier, bruker denne typen Gray-kode ikke-boolske verdier i kodingene.
For eksempel vil en 3-ær ternær grå kode bruke verdiene {0, 1 og 2}. (n, k)-Gray-koden er den n-ære Gray-koden med k sifre. Sekvensen av elementer i (3, 2)-Grå-koden er: {00, 01, 02, 12, 11, 10, 20, 21 og 22}.
(n, k)-Gray-koden kan konstrueres rekursivt, som BRGC, eller kan konstrueres iterativt.
Monotone grå koder
Monotoniske koder er nyttige i teori om sammenkoblingsnettverk, spesielt for å minimere utvidelse for lineære arrays av prosessorer.
Hvis vi definerer vekten til en binær streng til å være antallet 1-ere i strengen, så selv om vi tydeligvis ikke kan ha en grå kode med strengt økende vekt, kan det være lurt å tilnærme dette ved å la koden kjøre gjennom to tilstøtende vekter før vi når den neste.
Beckett-Gray-kode
En annen type Gray-kode, Beckett-Gray-koden, er oppkalt etter irsk dramatiker Samuel Beckett , som var interessert i symmetri . Hans skuespill Quad har fire skuespillere og er delt inn i seksten tidsperioder. Hver periode avsluttes med at en av de fire skuespillerne entrer eller forlater scenen.
Stykket begynner med en tom scene, og Beckett ønsket at hver undergruppe av skuespillere skulle dukke opp på scenen nøyaktig én gang. En 4-bits binær Gray-kode kan representere settet med skuespillere på scenen.
Derimot,
Beckett la en ekstra begrensning på manuset: han ønsket at skuespillerne skulle gå inn og ut, slik at den skuespilleren som hadde vært lengst på scenen, alltid ville være den som gikk ut.
Aktørene kan da representeres av en først-inn, først-ut-kø (FIFO), slik at skuespilleren som blir satt ut av køen alltid er den som ble stilt først.
Beckett klarte ikke å finne en Beckett-Gray-kode for skuespillet sitt, og faktisk, en uttømmende liste over alle mulige sekvenser avslører at ingen slik kode eksisterer for n = 4. Det er kjent i dag at slike koder eksisterer for n = 2, 5 , 6, 7 og 8, og eksisterer ikke for n = 3 eller 4.
Slange-i-boksen-koder
Snake-in-the-box-koder, eller slanger, er sekvensene av noder av induserte baner i en n-dimensjonal hyperkube graf, og coil-in-the-box-koder, eller coils, er sekvensene av noder av induserte sykluser i en hyperkube.
Sett på som grå koder, har disse sekvensene egenskapen til å oppdage enhver enkeltbits kodefeil.
Enkeltspors grå kode
En annen type gråkode er enkeltspors gråkode (STGC) utviklet av Norman B. Spedding og foredlet av Hiltgen, Paterson og Brandestini i 'Single-track Grey codes' (1996).
STGC er en syklisk liste over P unike binære kodinger med lengde n slik at to påfølgende ord er forskjellige i nøyaktig én posisjon. Når listen undersøkes som en P × n matrise, er hver kolonne et syklisk skift av den første kolonnen.
algebra av sett
Navnet kommer fra deres bruk med roterende kodere, hvor mange spor blir registrert av kontakter, noe som resulterer i at hver av sporene gir en utgang på 0 eller 1. For å redusere støy på grunn av at forskjellige kontakter ikke skifter samme tidspunkt, setter man fortrinnsvis opp sporer slik at kontaktenes datautgang er i grå kode.
For å få høy vinkelnøyaktighet trenger man mange kontakter; for å oppnå minst 1-grads nøyaktighet, trenger man minst 360 distinkte posisjoner per omdreining, noe som krever minimum 9 databiter og samme antall kontakter.
Hvis alle kontakter er plassert i samme vinkelposisjon, trengs 9 spor for å få en standard BRGC med minst 1-grads nøyaktighet. Imidlertid, hvis produsenten flytter en kontakt til en annen vinkelposisjon, men i samme avstand fra senterakselen, må det tilsvarende 'ringmønsteret' roteres i samme vinkel for å gi samme utgang.
To-dimensjons grå kode
Todimensjonale gråkoder brukes i kommunikasjon for å minimere antall bitfeil i kvadraturamplitudemodulasjon tilstøtende punkter i konstellasjonen.
I en standardkoding avviker de horisontale og vertikale tilstøtende konstellasjonspunktene med en enkelt bit, og tilstøtende diagonale punkter avviker med 2 biter.