Soubor Wozencraft - Wozencraft ensemble

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Wozencraft ensemble"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Květen 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie kódování, Soubor Wozencraft je sada lineární kódy ve kterém většina kódů vyhovuje Gilbert-Varshamov vázán. Je pojmenován po John Wozencraft, který prokázal svou existenci. Soubor popisuje Massey (1963), který jej připisuje Wozencraft. Justesen (1972) použil soubor Wozencraft jako vnitřní kódy při konstrukci silně explicitního asymptoticky dobrého kódu.

Věta o existenci

Teorém: Nechat ${ displaystyle varepsilon> 0.}$ Pro dost velké ${ displaystyle k}$, existuje soubor vnitřních kódů ${ displaystyle C_ {in} ^ {1}, cdots, C_ {in} ^ {N}}$ z hodnotit ${ displaystyle { tfrac {1} {2}}}$, kde ${ displaystyle N = q ^ {k} -1}$, tak, že alespoň ${ displaystyle (1- varepsilon) N}$ hodnoty ${ displaystyle i, C_ {in} ^ {i}}$ má relativní vzdálenost ${ displaystyle geqslant H_ {q} ^ {- 1} left ({ tfrac {1} {2}} - varepsilon right)}$.

Zde relativní vzdálenost je poměr minimální vzdálenosti k délce bloku. A ${ displaystyle H_ {q}}$ je entropická funkce q-ary definovaná takto:

${ displaystyle H_ {q} (x) = x log _ {q} (q-1) -x log _ {q} x- (1-x) log _ {q} (1-x). }$

Ve skutečnosti, abychom ukázali existenci této sady lineárních kódů, specifikujeme tento soubor výslovně takto: pro ${ displaystyle alpha in mathbb {F} _ {q ^ {k}} - {0 }}$, definujte vnitřní kód

${ displaystyle { begin {cases} C_ {in} ^ { alpha}: mathbb {F} _ {q} ^ {k} to mathbb {F} _ {q} ^ {2k} C_ {in} ^ { alpha} (x) = (x, alpha x) end {případy}}}$

Tady si toho můžeme všimnout ${ displaystyle x in mathbb {F} _ {q} ^ {k}}$ a ${ displaystyle alpha in mathbb {F} _ {q ^ {k}}}$. Můžeme udělat násobení ${ displaystyle alpha x}$ od té doby ${ displaystyle mathbb {F} _ {q} ^ {k}}$ je izomorfní s ${ displaystyle mathbb {F} _ {q ^ {k}}}$.

Tento soubor pochází z Wozencraft a nazývá se souborem Wozencraft.

Pro všechny ${ displaystyle x, y in mathbb {F} _ {q} ^ {k}}$, máme následující fakta:

1. ${ displaystyle C_ {in} ^ { alpha} (x) + C_ {in} ^ { alpha} (y) = (x, alpha x) + (y, alpha y) = (x + y, alpha (x + y)) = C_ {in} ^ { alpha} (x + y)}$
2. Pro všechny ${ displaystyle a in mathbb {F} _ {q}, aC_ {in} ^ { alpha} (x) = a (x, alpha x) = (ax, alpha (ax)) = C_ { in} ^ { alpha} (sekera)}$

Tak ${ displaystyle C_ {in} ^ { alpha}}$ je lineární kód pro každého ${ displaystyle alpha in mathbb {F} _ {q ^ {k}} - {0 }}$.

Nyní víme, že soubor Wozencraft obsahuje lineární kódy s rychlostí ${ displaystyle { tfrac {1} {2}}}$. V následujícím důkazu ukážeme, že existují alespoň ${ displaystyle (1- varepsilon) N}$ ty lineární kódy, které mají relativní vzdálenost ${ displaystyle geqslant H_ {q} ^ {- 1} left ({ tfrac {1} {2}} - varepsilon right)}$, tj. setkávají se s Gilbert-Varshamovem.

Důkaz

Dokázat, že existují alespoň ${ displaystyle (1- varepsilon) N}$ počet lineárních kódů v souboru Wozencraft s relativní vzdáleností ${ displaystyle geqslant H_ {q} ^ {- 1} left ({ tfrac {1} {2}} - varepsilon right)}$, dokážeme, že existují nanejvýš ${ displaystyle varepsilon N}$ počet lineárních kódů s relativní vzdáleností ${ displaystyle$ tj. mít vzdálenost ${ displaystyle$

Všimněte si, že v lineárním kódu je vzdálenost rovna minimální hmotnosti všech kódových slov daného kódu. Tato skutečnost je vlastnost lineárního kódu. Takže pokud má jedno nenulové kódové slovo váhu ${ displaystyle$, pak má tento kód vzdálenost ${ displaystyle$

Nechat ${ displaystyle P}$ být soubor lineárních kódů majících vzdálenost ${ displaystyle$ Pak existují ${ displaystyle | P |}$ lineární kódy s nějakým kódovým slovem, které má váhu ${ displaystyle$

Lemma. Dva lineární kódy ${ displaystyle C_ {in} ^ { alpha _ {1}}}$ a ${ displaystyle C_ {in} ^ { alpha _ {2}}}$ s ${ displaystyle alpha _ {1}, alpha _ {2} in mathbb {F} _ {q ^ {k}}}$ odlišné a nenulové, nesdílejte žádné nenulové kódové slovo.

Důkaz. Předpokládejme, že existují odlišné nenulové prvky ${ displaystyle alpha _ {1}, alpha _ {2} in mathbb {F} _ {q ^ {k}}}$ takové, že lineární kódy ${ displaystyle C_ {in} ^ { alpha _ {1}}}$ a ${ displaystyle C_ {in} ^ { alpha _ {2}}}$ obsahovat stejné nenulové kódové slovo ${ displaystyle y.}$ Nyní od té doby ${ displaystyle y in C_ {in} ^ { alpha _ {1}}, y = (y_ {1}, alpha _ {1} y_ {1})}$ pro některé ${ displaystyle y_ {1} in mathbb {F} _ {q} ^ {k}}$ a podobně ${ displaystyle y = (y_ {2}, alpha _ {2} y_ {2})}$ pro některé ${ displaystyle y_ {2} in mathbb {F} _ {q} ^ {k}.}$ Navíc od ${ displaystyle y}$ je nenulová, co máme ${ displaystyle y_ {1}, y_ {2} neq 0.}$ Proto ${ displaystyle (y_ {1}, alpha _ {1} y_ {1}) = (y_ {2}, alpha _ {2} y_ {2})}$, pak ${ displaystyle y_ {1} = y_ {2} neq 0}$ a ${ displaystyle alpha _ {1} y_ {1} = alpha _ {2} y_ {2}.}$ Z toho vyplývá ${ displaystyle alpha _ {1} = alpha _ {2}}$, což je rozpor.

Libovolný lineární kód mající vzdálenost ${ displaystyle$ má nějaké kódové slovo váhy ${ displaystyle$ Nyní Lemma naznačuje, že máme alespoň ${ displaystyle | P |}$ odlišný ${ displaystyle y}$ takhle ${ displaystyle wt (y)$ (jedno takové kódové slovo ${ displaystyle y}$ pro každý lineární kód). Tady ${ displaystyle wt (y)}$ označuje váhu kódového slova ${ displaystyle y}$, což je počet nenulových pozic ${ displaystyle y}$.

Označit

${ displaystyle S = left {y : wt (y)$

Pak:^[1]

${ displaystyle { begin {aligned} | P | & leqslant | S | & leqslant { text {Vol}} _ {q} left (H_ {q} ^ {- 1} left ({ tfrac {1} {2}} - varepsilon right) cdot 2k, 2k right) && { text {Vol}} _ {q} (r, n) { text {je objem Hammingovy koule poloměru}} r { text {in}} [q] ^ {n} & leqslant q ^ {H_ {q} left (H_ {q} ^ {- 1} left ({ frac { 1} {2}} - varepsilon right) right) cdot 2k} && { text {Vol}} _ {q} (pn, n) leqslant q ^ {H_ {q} (p) n} & = q ^ { left ({ frac {1} {2}} - varepsilon right) cdot 2k} & = q ^ {k (1-2 varepsilon)} & < varepsilon (q ^ {k} -1) && { text {for}} k { text {dostatečně velký}} & = varepsilon N end {zarovnáno}}}$

Tak ${ displaystyle | P | < varepsilon N}$, proto sada lineárních kódů majících relativní vzdálenost ${ displaystyle geqslant H_ {q} ^ {- 1} left ({ tfrac {1} {2}} - varepsilon right) cdot 2k}$ má alespoň ${ displaystyle N- varepsilon N = (1- varepsilon) N}$ elementy.

Viz také

• Justesenův kód
• Lineární kód
• Hamming vázán

Reference

• Massey, James L. (1963), Mezní dekódování, Tech. Zpráva 410, Cambridge, Massachusetts: Massachusetts Institute of Technology, Research Laboratory of Electronics, hdl:1721.1/4415, PAN  0154763.
• Justesen, Jørn (1972), „Třída konstruktivních asymptoticky dobrých algebraických kódů“, Institute of Electrical and Electronics Engineers. Transakce na informační teorii, IT-18: 652–656, doi:10.1109 / TIT.1972.1054893, PAN  0384313.

externí odkazy

• Přednáška 28: Justesenův kód. Kurz teorie kódování. Prof. Atri Rudra.
• Přednáška 9: Hranice objemu Hammingova míče. Kurz teorie kódování. Prof. Atri Rudra.
• J. Justesen (1972). "Třída konstruktivních asymptoticky dobrých algebraických kódů". IEEE Trans. Inf. Teorie. 18: 652–656. doi:10.1109 / TIT.1972.1054893.
• Poznámky k teorii kódování: Gilbert-Varshamov Bound. Venkatesan Guruwami