Kód s konstantní hmotností - Constant-weight code

v teorie kódování, a kód s konstantní hmotností, nazývané také m-z-n kód, je detekce a oprava chyb kód, kde všechna kódová slova sdílejí stejné Hammingova hmotnost.v jeden horký kód a vyvážený kód jsou dva široce používané druhy kódu s konstantní hmotností.

Tato teorie je úzce spjata s teorií vzory (jako t-dizajny a Steinerovy systémy ). Většina práce na tomto velmi důležitém poli diskrétní matematika je znepokojen binární kódy konstantní hmotnosti.

Binární kódy s konstantní hmotností mají několik aplikací, včetně skákání frekvence v GSM sítí.^[1]Většina čárové kódy použijte binární kód s konstantní hmotností ke zjednodušení automatického nastavení prahové hodnoty řádkové kódy použijte buď kód s konstantní hmotností, nebo téměř konstantní váhu spárovaný kód disparity Kromě použití jako kódy pro opravu chyb lze při navrhování použít i velký prostor mezi kódovými slovy asynchronní obvody jako obvody necitlivé na zpoždění.

Kódy s konstantní hmotností Bergerovy kódy, dokáže detekovat všechny jednosměrné chyby.

A(n, d, w)

Hlavní problém týkající se kódů s konstantní hmotností je následující: jaký je maximální počet kódových slov v binárním kódu s konstantní hmotností s délkou ${displaystyle n}$ , Hammingova vzdálenost ${displaystyle d}$ a hmotnost ${displaystyle w}$ ? Toto číslo se nazývá ${displaystyle A (n, d, w)}$ .

Kromě některých triviálních pozorování je obecně nemožné vypočítat tato čísla přímým způsobem. Horní hranice jsou dány několika důležitými větami, jako je za prvé a druhý Johnson hranice,^[2] a lepší horní hranice lze někdy najít i jinými způsoby. Dolní hranice se nejčastěji vyskytují vystavením konkrétních kódů, a to buď pomocí různých metod od diskrétní matematiky, nebo pomocí těžkého počítačového vyhledávání. Velká tabulka takových rekordních kódů byla zveřejněna v roce 1990,^[3] a rozšíření o delší kódy (ale pouze pro tyto hodnoty ${displaystyle d}$ a ${displaystyle w}$ relevantní pro aplikaci GSM) byla zveřejněna v roce 2006.^[1]

1 zN kódy

Zvláštní případ kódů s konstantní hmotností je jeden zN kódy, které kódují ${displaystyle log _ {2} N}$ bity v kódovém slově ${displaystyle N}$ bity. Jeden ze dvou kódů používá kódovací slova 01 a 10 ke kódování bitů „0“ a „1“. Jeden ze čtyř kódů může použít slova 0001, 0010, 0100, 1000 k zakódování dvou bitů 00, 01, 10 a 11. Příkladem je kódování dual rail a článek řetězu ^[4] používá se v obvodech necitlivých na zpoždění. U těchto kódů ${displaystyle n = N, ~ d = 2, ~ w = 1}$ a ${displaystyle A (n, d, w) = n}$ .

Některá z nejpozoruhodnějších použití jednoho horkého kódu zahrnujíkód dvoufázové značky používá kód 1 ze 2;modulace pulzní polohy používá 1 zn kód;dekodér adres,atd.

Vyvážený kód

v teorie kódování, a vyvážený kód je binární dopředná oprava chyb kód, pro který každé kódové slovo obsahuje stejný počet nula a jeden bit. Vyvážené kódy byly zavedeny Donald Knuth;^[5] jsou podmnožinou takzvaných neuspořádaných kódů, což jsou kódy mající tu vlastnost, že pozice těch v kódovém slovu nikdy nejsou podmnožinou pozic těch v jiném kódovém slově. Stejně jako všechny neuspořádané kódy jsou vyvážené kódy vhodné pro detekci všech jednosměrné chyby v zakódované zprávě. Vyvážené kódy umožňují obzvláště efektivní dekódování, které lze provádět paralelně.^[5]^[6]^[7]

Některá z více pozoruhodných použití vyvážených kódů zahrnujíkód dvoufázové značky používá kód 1 ze 2;Kódování 6b / 8b používá kód 4 z 8; Hadamardův kód je ${displaystyle 2 ^ {k} / 2}$ z ${displaystyle 2 ^ {k}}$ kód (kromě nulového kódového slova), tři ze šesti kód atd.

3vodičové kódování jízdního pruhu používané v MIPI C-PHY lze považovat za zobecnění kódu s konstantní hmotností na ternární - každý vodič přenáší a ternární signál, a v kterémkoli okamžiku jeden ze 3 vodičů vysílá nízký, jeden vysílá střední a jeden vysílá vysoký signál.^[8]

m-z-n kódy

An m-z-n kód je oddělitelný detekce chyb kód s délkou kódového slova n bity, kde každé kódové slovo obsahuje přesně m instance „jednoho“. Jedna bitová chyba způsobí, že kódové slovo bude mít buď m + 1 nebo m − 1 "ones". Příklad m-z-n kód je Kód 2 z 5 používá Poštovní služba Spojených států.

Nejjednodušší implementací je přidání řetězce jedniček k původním datům, dokud tato data neobsahují m ty, pak připojte nuly a vytvořte kód délky n.

Příklad:

Kód 3 ze 6
Původní 3 datové bity	Připojené bity
000	111
001	110
010	110
011	100
100	110
101	100
110	100
111	000

Některá z více pozoruhodných použití kódů s konstantní hmotností, kromě výše zmíněných kódů s jednou horkou a vyváženou hmotností, zahrnujíKód 39 používá kód 3 z 9;binární kódované desetinné číslo kód používá kód 2 ze 7, Kód 2 z 5,atd.

Reference

^ ^A ^b D. H. Smith, L. A. Hughes a S. Perkins (2006). "Nová tabulka kódů konstantní hmotnosti o délce větší než 28 ". Electronic Journal of Combinatorics 13.
^ Viz str. 526–527 F. J. MacWilliamse a N. J. A. Sloana (1979). Teorie kódů pro opravu chyb. Amsterdam: Severní Holandsko.
^ A. E. Brouwer, James B. Shearer, N. J. A. Sloane a Warren D. Smith (1990). "Nová tabulka kódů konstantní hmotnosti". IEEE Transakce informační teorie 36.
^ W. J. Bainbridge; A. Bardsley; R.W. McGuffin. „Návrh systému na čipu s využitím časovaných sítí na čipu“.
^ ^A ^b D.E. Knuth (leden 1986). "Efektivní vyvážené kódy" (PDF). Transakce IEEE na teorii informací. 32 (1): 51–53. doi:10.1109 / TIT.1986.1057136.^{[trvalý mrtvý odkaz ]}
^ Sulaiman Al-Bassam; Bella Bose (březen 1990). "Na vyvážených kódech". Transakce IEEE na teorii informací. 36 (2): 406–408. doi:10.1109/18.52490.
^ K. Schouhamer Immink a J. Weber (2010). "Velmi efektivní vyvážené kódy". IEEE Journal on Selected Areas in Communications. 28: 188–192. doi:10.1109 / jsac.2010.100207. Citováno 2018-02-12.
^ „Demystifikace subsystému MIPI C-PHY / DPHY - kompromisy, výzvy a přijetí“ (zrcadlo )

externí odkazy

Tabulka dolních mezí na ${displaystyle A (n, d, w)}$ udržuje Andries Brouwer (aktualizace dřívější tabulka podle Neil Sloane a E. M. Rains )
Tabulka horních mezí na ${displaystyle A (n, d, w)}$ udržuje Erik Souhlas

[smith-1] A ^b D. H. Smith, L. A. Hughes a S. Perkins (2006). "Nová tabulka kódů konstantní hmotnosti o délce větší než 28 ". Electronic Journal of Combinatorics 13.

[2] Viz str. 526–527 F. J. MacWilliamse a N. J. A. Sloana (1979). Teorie kódů pro opravu chyb. Amsterdam: Severní Holandsko.

[brouwer-3] A. E. Brouwer, James B. Shearer, N. J. A. Sloane a Warren D. Smith (1990). "Nová tabulka kódů konstantní hmotnosti". IEEE Transakce informační teorie 36.

[4] W. J. Bainbridge; A. Bardsley; R.W. McGuffin. „Návrh systému na čipu s využitím časovaných sítí na čipu“.

[knuth-5] A ^b D.E. Knuth (leden 1986). "Efektivní vyvážené kódy" (PDF). Transakce IEEE na teorii informací. 32 (1): 51–53. doi:10.1109 / TIT.1986.1057136.^{[trvalý mrtvý odkaz ]}

[optimal-6] Sulaiman Al-Bassam; Bella Bose (březen 1990). "Na vyvážených kódech". Transakce IEEE na teorii informací. 36 (2): 406–408. doi:10.1109/18.52490.

[7] K. Schouhamer Immink a J. Weber (2010). "Velmi efektivní vyvážené kódy". IEEE Journal on Selected Areas in Communications. 28: 188–192. doi:10.1109 / jsac.2010.100207. Citováno 2018-02-12.

[8] „Demystifikace subsystému MIPI C-PHY / DPHY - kompromisy, výzvy a přijetí“ (zrcadlo )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]