Konstantviktskod

I kodningsteorin är en konstantviktskod , även kallad m -of- n -kod , en feldetekterings- och korrigeringskod där alla kodord delar samma Hamming-vikt . One -hot- koden och den balanserade koden är två ofta använda typer av konstantviktskoder.

Teorin är nära kopplad till den för design (som t -designs och Steiner-system) . Det mesta av arbetet på detta område av diskret matematik handlar om binära konstantviktskoder.

Binära konstantviktskoder har flera tillämpningar, inklusive frekvenshopp i GSM -nät. De flesta streckkoder använder en binär kod med konstant vikt för att förenkla automatisk inställning av ljusstyrketröskeln som skiljer svarta och vita ränder. De flesta radkoder använder antingen en kod med konstant vikt eller en parad disparitetskod med nästan konstant vikt . Förutom att användas som felkorrigeringskoder kan det stora utrymmet mellan kodorden också användas vid konstruktionen av asynkrona kretsar såsom fördröjningsokänsliga kretsar .

Koder med konstant vikt, som Berger-koder , kan upptäcka alla enkelriktade fel.

A ( n , d , w )

Det centrala problemet med konstantviktskoder är följande: vad är det maximala antalet kodord i en binär konstantviktskod med längden ${\displaystyle n} ,$ Hamming distans $d$ och vikt $w$ ? Detta nummer kallas $A(n,d,w)$ .

Bortsett från några triviala observationer är det i allmänhet omöjligt att beräkna dessa siffror på ett enkelt sätt. Övre gränser ges av flera viktiga satser såsom första och andra Johnson gränser , och bättre övre gränser kan ibland hittas på andra sätt. Nedre gränser hittas oftast genom att uppvisa specifika koder, antingen med användning av en mängd olika metoder från diskret matematik, eller genom tung datorsökning. En stor tabell över sådana rekordslagande koder publicerades 1990, och en tillägg till längre koder (men bara för de värden på $d$ och $w$ som är relevanta för GSM-applikationen) publicerades under 2006.

1-av- N -koder

Ett specialfall av konstantviktskoder är en av N - koder, som kodar $\log _{2}N$ bitar i ett kodord med $N$ bitar. En-av-två-koden använder kodorden 01 och 10 för att koda bitarna "0" och "1". En kod av en av fyra kan använda orden 0001, 0010, 0100, 1000 för att koda två bitar 00, 01, 10 och 11. Ett exempel är kodning med dubbla spår och kedjelänk som används i fördröjningsokänsliga kretsar. För dessa koder, $n=N,~d=2,~w=1$ och $A(n, d,w)=n$ .

Några av de mer anmärkningsvärda användningarna av en-heta koder inkluderar bifasmärke kod använder en 1-av-2-kod; pulspositionsmodulering använder en 1-av- n -kod; adressavkodare osv.

Balanserad kod

I kodningsteorin är en balanserad kod en binär framåtriktad felkorrigeringskod för vilken varje kodord innehåller lika många noll och en bitar. Balanserade koder har introducerats av Donald Knuth ; de är en delmängd av så kallade oordnade koder, som är koder som har egenskapen att positionerna för ettor i ett kodord aldrig är en delmängd av positionerna för de i ett annat kodord. Liksom alla oordnade koder är balanserade koder lämpliga för att upptäcka alla enkelriktade fel i ett kodat meddelande. Balanserade koder möjliggör särskilt effektiv avkodning, som kan utföras parallellt.

Några av de mer anmärkningsvärda användningsområdena för koder med balanserad vikt inkluderar bifasmärkeskod som använder en 1 av 2-kod; 6b/8b-kodning använder en 4 av 8-kod; Hadamard- koden är en $2^{k-1}$ av ${\displaystyle 2^{k}}-$ kod (förutom nollkodordet), tre-av-sex- koden; etc.

Den 3-tråds körfältskodning som används i MIPI C-PHY kan betraktas som en generalisering av konstantviktskod till ternär -- varje tråd sänder en ternär signal , och i vilket ögonblick som helst en av de 3 ledningarna sänder en låg, är en sänder en mitt, och en sänder en hög signal.

m -av- n koder

En m -av- n -kod är en separerbar feldetekteringskod med en kodordslängd på n bitar, där varje kodord innehåller exakt m instanser av en "ett". Ett enstaka bitfel gör att kodordet har antingen m + 1 eller m − 1 "ettor". Ett exempel på m -of- n -koden är 2-av-5-koden som används av United States Postal Service .

Den enklaste implementeringen är att lägga till en sträng med ettor till originaldata tills den innehåller m ettor, sedan lägga till nollor för att skapa en kod med längden n .

Exempel:

3-av-6-kod
Original 3 databitar	Bifogade bitar
000	111
001	110
010	110
011	100
100	110
101	100
110	100
111	000

Några av de mer anmärkningsvärda användningarna av koder med konstant vikt, förutom de en-heta och balanserade viktkoderna som redan nämnts ovan, inkluderar kod 39 använder en 3-av-9-kod; bi-kinärkodad decimalkod använder en 2-av-7-kod, 2-av-5-koden osv.

externa länkar

Tabell över nedre gränser på $A(n,d,w)$ upprätthålls av Andries Brouwer (uppdatering av den tidigare tabellen av Neil Sloane och EM Rains)
Tabell över övre gränser på $A(n,d,w)$ upprätthålls av Erik Agrell