Dual of BCH är en oberoende källa

En viss familj av BCH-koder har en särskilt användbar egenskap, som är den som behandlas som linjära operatorer , deras dubbla operatorer förvandlar sin indata till en $\ell$ -vis oberoende källa . Det vill säga att uppsättningen av vektorer från inmatningsvektorutrymmet mappas till en $\ell$ -vis oberoende källa. Beviset för detta faktum nedan som följande Lemma och följd är användbart för att avrandomisera algoritmen för en $1-2^{-\ell }$ -approximation till MAXEkSAT .

Lemma

Låt $C\subseteq F_{2}^{n}$ vara en linjär kod så att $C^{\perp }$ har ett avstånd större än $\ ell +1$ . Då $C$ en $\ell$ -vis oberoende källa.

Bevis på lemma

Det är tillräckligt att visa att givet vilken ${\displaystyle k\xl} som helst$ matris M , där k är större än eller lika med l , så att rangordningen för M är l , för alla ${\ displaystyle x\in F_{2}^{k}}$ , $xM$ tar varje värde i $F_{2}^{l}$ samma antal gånger.

Eftersom M har rang l kan vi skriva M som två matriser av samma storlek, $M_{1}$ och $M_{2}$ , där $M_{1}$ har rang lika med l . Detta innebär att $xM$ kan skrivas om till $x_{1}M_{1}+x_{2}M_{2}$ för några ${\ displaystyle x_{1}}$ och $x_{2}$ .

Om vi ​​betraktar M skrivet med avseende på en bas där de första l raderna är identitetsmatrisen, så har $x_{1}$ nollor där $M_{2}$ har rader som inte är noll, och $x_{2}$ har nollor där $M_{1}$ har rader som inte är noll.

Nu kan vilket värde y som helst , där $y=xM$ , skrivas som $x_{1}M_{1}+x_{2}M_{2 }$ för vissa vektorer $x_{1},x_{2}$ .

Vi kan skriva om detta som:

$x_{1}M_{1}=y-x_{2}M_{2}$

Fastställande av värdet för de sista $kl$ koordinaterna för ${\displaystyle x_{2}\in F_{2}^{k}} ($ observera att det finns exakt $2^{kl}$ sådana val), kan vi skriva om denna ekvation igen som:

$x_{1}M_{1}=b$ för vissa b .

Eftersom $M_{1}$ har rang lika med l , finns det exakt en lösning $x_{1}$ , så det totala antalet lösningar är exakt $2^ {kl}$ , bevisar lemmat.

Naturlig följd

Kom ihåg att BCH _{2, m , d} är en $[n=2^{m},n-1-\lceil {d-2}/2\rceil m,d]_{2}$ linjär kod.

Låt $C^{\perp }$ vara BCH _{2,log n , ℓ +1} . Då $C$ en $\ell$ -vis oberoende källa av storlek $O(n^{\lfloor \ell /2\rfloor })$ .

Bevis på följd

Dimensionen d för C är bara $\lceil {(\ell +1-2)/{2}}\rceil \log n+1$ . Så $d=\lceil {(\ell -1)}/2\rceil \log n +1=\lgolv \ell /2\rgolv \log n+1$ .

Så kardinaliteten för $C$ betraktad som en mängd är bara $2^{d}=O(n^{\lfloor \ell /2\rfloor })$ , bevisar följden.

Coding Theory notes vid University at Buffalo

Coding Theory notes vid MIT