Justesen kod

Binära Justesen-koder
Döpt efter	Jørn Justesen
Klassificering
Typ	Linjär blockkod
Blocklängd	$n$
Meddelandets längd	$k$
Betygsätta	= ${\frac {R}{2}}={\frac {k}{2n}}$
Distans	$\delta n$ där $\delta \geq {\Big (} 1-R-\epsilon {\Big )}H_{2}^{-1}{\big (}{\frac {1}{2}}-\epsilon {\big )}\sim 0.11(1-R -\epsilon )$ för liten $\epsilon >0$ .
Alfabetets storlek	2
Notation	$\left[n,k/2,\delta n\right]_{2}$ -kod
Egenskaper
konstant hastighet, konstant relativ avstånd, konstant alfabetsstorlek

I kodningsteorin bildar Justesen-koder en klass av felkorrigerande koder som har en konstant hastighet , konstant relativ avstånd och en konstant alfabetisk storlek.

Innan Justesen-felkorrigeringskoden upptäcktes var ingen felkorrigeringskod känd som hade alla dessa tre parametrar som konstanta.

Därefter har andra ECC-koder med denna egenskap upptäckts, till exempel expanderkoder . Dessa koder har viktiga tillämpningar inom datavetenskap, till exempel vid konstruktionen av provutrymmen med liten bias .

Justesen-koder härleds som kodsammansättningen av en Reed–Solomon-kod och Wozencraft-ensemblen .

Reed–Solomon-koderna som används uppnår konstant hastighet och konstant relativt avstånd på bekostnad av en alfabetisk storlek som är linjär i meddelandelängden.

Wozencraft -ensemblen är en familj av koder som uppnår konstant hastighet och konstant alfabetisk storlek, men det relativa avståndet är bara konstant för de flesta av koderna i familjen.

Sammankopplingen av de två koderna kodar först meddelandet med hjälp av Reed–Solomon-koden, och kodar sedan varje symbol i kodordet vidare med hjälp av en kod från Wozencraft-ensemblen – med en annan kod för ensemblen vid varje position i kodordet.

Detta skiljer sig från vanlig kodsammansättning där de inre koderna är desamma för varje position. Justesen-koden kan konstrueras mycket effektivt med endast logaritmiskt utrymme .

Definition

Justesen-koden är sammanlänkningen av en $(N,K,D)_{q^{k}}$ yttre kod $C_{out}$ och olika $(n,k,d)_{q}$ inre koder $C_{in}^{i}$ , för $1\leq i\leq N$ .

Mer exakt, sammanlänkningen av dessa koder, betecknade med $C_{out}\circ (C_{in}^{1}, ...,C_{in}^{N})$ , definieras enligt följande. Givet ett meddelande $m\in [q^{k}]^{K}$ , beräknar vi kodordet som produceras av en yttre kod $C_{out}$ : $C_{out}(m)=(c_{1},c_{2},..,c_{N })$ .

Sedan applicerar vi varje kod med N linjära inre koder på varje koordinat för det kodordet för att producera det slutliga kodordet; det vill $C_{out}\circ (C_{in}^{1},..,C_{in}^{N})(m)=(C_{in}^{1 }(c_{1}),C_{in}^{2}(c_{2}),..,C_{in}^{N}(c_{N}))$ .

Titta tillbaka på definitionen av den yttre koden och linjära inre koder, denna definition av Justesen-koden är vettig eftersom kodordet för den yttre koden är en vektor med $N$ element, och vi har $N$ linjära inre koder för de $N$ -elementen.

Här för Justesen-koden är den yttre koden $C_{out}$ vald att vara Reed Solomon-kod över ett fält $\mathbb {F} _{q^{k}}$ utvärderad över $\mathbb {F} _{q^{k}}-\{0\}$ av hastigheten $R$ , $0$ < ${\ displaystyle R}$ < $1$ .

Den yttre koden $C_{out}$ har det relativa avståndet $\delta _{out}=1-R$ och blocklängden på $N=q^{k}-1$ . Uppsättningen av inre koder är Wozencraft-ensemblen $\{C_{in}^{\alpha }\}_{\alpha \in \mathbb {F} _{ q^{k}}^{*}}$ .

Egendom av Justesen kod

Eftersom de linjära koderna i Wonzencraft-ensemblen har hastigheten ${\frac {1}{2}}$ , är Justesen-koden den sammanlänkade koden $C^{*}=C_{out}\circ (C_{in}^{1},C_{in}^{2},..,C_{ in}^{N})$ med hastigheten ${\frac {R}{2}}$ . Vi har följande teorem som uppskattar avståndet för den sammanlänkade koden $C^{*}$ .

Sats

Låt $\varepsilon >0.$ Då har $C^{*}$ ett relativt avstånd på minst $(1-R-\varepsilon )H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right).$

Bevis

För att bevisa en nedre gräns för avståndet för en kod $C^{*}$ bevisar vi att Hamming-avståndet för ett godtyckligt men distinkt kodordspar har en nedre gräns. Så låt $\Delta (c^{1},c^{2})$ vara Hamming-avståndet för två kodord $c^{1}$ och $c^{2}$ . För något givet

$m_{1}\neq m_{2}\in \left(\mathbb {F} _{q^{k}}\right)^{K },$

vi vill ha en nedre gräns för $\Delta (C^{*}(m_{1}),C^{*}(m_{2})).$

Lägg märke till att om $C_{out}(m)=(c_{1},\cdots ,c_{N})$ så $C^{*}(m)=(C_{in}^{1}(c_{1 }),\cdots ,C_{in}^{N}(c_{N}))$ . Så för den nedre gränsen $\Delta (C^{*}(m_{1}),C^{*}(m_{2}) )$ måste vi ta hänsyn till avståndet för $C_{in}^{1},\cdots ,C_{in}^{N}.$

Anta

${\begin{aligned}C_ {out}(m_{1})&=\left(c_{1}^{1},\cdots ,c_{N}^{1}\right)\\C_{out}(m_{2})& =\left(c_{1}^{2},\cdots ,c_{N}^{2}\right)\end{aligned}}$

Kom ihåg att ${\displaystyle \left\{C_{in}^{1},\cdots ,C_{in}^{N}\right\}} är$ en Wozencraft ensemble . På grund av "Wonzencraft ensemble theorem" finns det åtminstone $(1-\varepsilon )N$ linjära koder $C_{in}^{i}$ som har avstånd ${\displaystyle H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.} Så om för$ några $1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}$ och koden $C_{in}^{i }$ har avstånd $\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \ höger)\cdot 2k,$ sedan

$\Delta \left(C_{i}^{i}\left(c_{i}^{1}\right),C_{in}^{i}\left(c_{i}^{2} \right)\right)\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Vidare, om vi har $T$ nummer $1\leqslant i\leqslant N$ så att $c_{i}^{1}\neq c_{i}^{2}$ och koden $C_{in}^{i}$ har avståndet $\geqslant H_{q}^{-1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,$ sedan

$\Delta \left(C^{*}(m_{1}),C^{*}(m_{2})\right)\geqslant H_{q}^{-1}\left({\ tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot T.$

Så nu är den sista uppgiften att hitta en nedre gräns för $T$ . Definiera:

$S=\left\{i\ :\ 1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}\right\}.$

Då är $T$ antalet linjära koder $C_{in}^{i},i\in S$ med avståndet $H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Nu vill vi uppskatta $|S|.$ Uppenbarligen $|S|=\Delta (C_{out}(m_{1}),C_ {out}(m_{2}))\geqslant (1-R)N$ .

På grund av Wozencraft Ensemble Theorem finns det som mest $\varepsilon N$ linjära koder med avstånd mindre än $H_{q}^{- 1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,$ så

$T\geqslant |S|-\varepsilon N\geqslant (1-R)N-\varepsilon N=(1-R-\varepsilon )N.$

Äntligen har vi

$\Delta (C^{*}(m_{1}),C^{*}(m_{2}))\geqslant H_{q}^{-1}\left({\tfrac {1} {2}}-\varepsilon \right)\cdot 2k\cdot T\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\ cdot (1-R-\varepsilon )\cdot N.$

Detta gäller för alla godtyckliga $m_{1}\neq m_{2}$ . Så $C^{*}$ har det relativa avståndet åtminstone $(1-R-\varepsilon )H_{q }^{-1}\left({\tfrac {1}{2}}-\varepsilon \right),$ vilket kompletterar beviset.

Kommentarer

Vi vill överväga den "starkt explicita koden". Så frågan är vad den "starkt explicita koden" är. Löst sagt, för linjär kod, är den "explicita" egenskapen relaterad till komplexiteten i att konstruera dess generatormatris G.

Det betyder i själva verket att vi kan beräkna matrisen i logaritmiskt utrymme utan att använda brute force-algoritmen för att verifiera att en kod har ett givet tillfredsställt avstånd.

För de andra koder som inte är linjära kan vi överväga komplexiteten hos kodningsalgoritmen.

Så överlägset kan vi se att Wonzencraft-ensemblen och Reed-Solomon-koderna är starkt explicita. Därför har vi följande resultat:

Följd: Den sammanlänkade koden $C^{*}$ är en asymptotiskt bra kod (det vill säga rate $R$ > 0 och det relativa avståndet $\delta$ > 0 för liten q) och har en starkt explicit konstruktion.

Ett exempel på en Justesen-kod

Följande något annorlunda kod hänvisas till som Justesen-koden i MacWilliams/MacWilliams. Det är det speciella fallet med den ovan betraktade Justesen-koden för en mycket speciell Wonzencraft-ensemble:

Låt R vara en Reed-Solomon-kod med längden N = 2 ^m − 1, rang K och minimivikten N − K + 1.

Symbolerna för R är element av F = GF(2 ^m ) och kodorden erhålls genom att ta varje polynom ƒ över F av grad mindre än K och lista värdena för ƒ på icke-nollelementen i F i någon förutbestämd ordning.

Låt α vara ett primitivt element av F . För ett kodord a = ( a ₁ , ..., a _N ) från R , låt b vara vektorn med längden 2 N över F som ges av

$\mathbf {b} =\left(a_{1},a_{1} ,a_{2},\alpha ^{1}a_{2},\ldots ,a_{N},\alpha ^{N-1}a_{N}\right)$

och låt c vara vektorn med längden 2 Nm erhållen från b genom att uttrycka varje element i F som en binär vektor med längden m . Justesen -koden är den linjära koden som innehåller alla sådana c .

Parametrarna för denna kod är längd 2 m N , dimension m K och minsta avstånd

$\sum _{i=1}^{\ell }i{\binom {2m}{i}},$

där $\ell$ är det största heltal som uppfyller $\sum _{i=1}^{\ell }{\binom {2m }{i}}\leq N-K+1$ . (Se MacWilliams/MacWilliams för ett bevis.)

Se även

• Wozencraft ensemble
• Sammanfogad felkorrigeringskod
• Reed-Solomon felkorrigering
• Linjär kod

• Föreläsning 28: Justesen Code. Kodningsteoris kurs. Prof. Atri Rudra .
• Föreläsning 6: Sammanfogade koder. Forney-koder. Justesen koder. Essentiell kodningsteori .
• J. Justesen (1972). "En klass av konstruktiva asymptotiskt bra algebraiska koder". IEEE Trans. Inf. Teori . 18 (5): 652–656. doi : 10.1109/TIT.1972.1054893 .
•   FJ MacWilliams ; NJA Sloane (1977). Teorin om felkorrigerande koder . Nord-Holland. s. 306–316 . ISBN 0-444-85193-3 .