Возенкрафт вместе

В теории кодирования ансамбль Возенкрафта представляет собой набор линейных кодов , в котором большинство кодов удовлетворяют границе Гилберта-Варшамова . Он назван в честь Джона Возенкрафта , доказавшего его существование. Ансамбль описан Мэсси (1963) , который приписывает его Возенкрафту. Юстесен (1972) использовал ансамбль Возенкрафта в качестве внутренних кодов при построении строго явного асимптотически хорошего кода.

Теорема существования

Теорема: Пусть $\varepsilon >0.$ Для достаточно большого $k$, существует ансамбль внутренних кодов $C_{in}^{1},\cdots ,C_{in}^{N}$ скорости ​ ${\tfrac {1}{2}}$, где $N=q^{k}-1$, такой, что по крайней мере $(1-\varepsilon )N$ значения $i,C_{in}^{i}$ имеет относительное расстояние $\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)$.

Здесь относительное расстояние — это отношение минимального расстояния к длине блока. И $H_{q}$ – q-ичная функция энтропии, определяемая следующим образом:

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

Фактически, чтобы показать существование этого набора линейных кодов, мы укажем этот ансамбль явно следующим образом: для $\alpha \in \mathbb {F} _{q^{k}}-\{0\}$, определите внутренний код

${\begin{cases}C_{in}^{\alpha }:\mathbb {F} _{q}^{k}\to \mathbb {F} _{q}^{2k}\\C_{in}^{\alpha }(x)=(x,\alpha x)\end{cases}}$

Здесь мы можем заметить, что $x\in \mathbb {F} _{q}^{k}$ и $\alpha \in \mathbb {F} _{q^{k}}$. Мы можем сделать умножение $\alpha x$ с $\mathbb {F} _{q}^{k}$ изоморфен $\mathbb {F} _{q^{k}}$.

Этот ансамбль создан благодаря Wozencraft и называется ансамблем Wozencraft.

Для всех $x,y\in \mathbb {F} _{q}^{k}$, мы имеем следующие факты:

1. $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. Для любого $a\in \mathbb {F} _{q},aC_{in}^{\alpha }(x)=a(x,\alpha x)=(ax,\alpha (ax))=C_{in}^{\alpha }(ax)$

Так $C_{in}^{\alpha }$ является линейным кодом для каждого $\alpha \in \mathbb {F} _{q^{k}}-\{0\}$.

Теперь мы знаем, что ансамбль Возенкрафта содержит линейные коды со скоростью ${\tfrac {1}{2}}$. В следующем доказательстве мы покажем, что существуют по крайней мере $(1-\varepsilon )N$ те линейные коды, имеющие относительное расстояние $\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)$, т.е. они достигают границы Гилберта-Варшамова.

Доказательство

Чтобы доказать, что существует хотя бы $(1-\varepsilon )N$ количество линейных кодов в ансамбле Возенкрафта, имеющих относительное расстояние $\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)$, мы докажем, что существует не более $\varepsilon N$ количество линейных кодов, имеющих относительное расстояние $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)$ то есть, имея расстояние $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Обратите внимание, что в линейном коде расстояние равно минимальному весу всех кодовых слов этого кода. Этот факт является свойством линейного кода . Итак, если одно ненулевое кодовое слово имеет вес $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k$, то этот код имеет расстояние $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Позволять $P$ быть набором линейных кодов, имеющих расстояние $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$ Тогда есть $|P|$ линейные коды, имеющие некоторое кодовое слово, имеющее вес $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Лемма. Два линейных кода $C_{in}^{\alpha _{1}}$ и $C_{in}^{\alpha _{2}}$ с $\alpha _{1},\alpha _{2}\in \mathbb {F} _{q^{k}}$ различимы и ненулевые, не имеют общего ненулевого кодового слова.

Доказательство. Предположим, существуют различные ненулевые элементы $\alpha _{1},\alpha _{2}\in \mathbb {F} _{q^{k}}$ такие, что линейные коды $C_{in}^{\alpha _{1}}$ и $C_{in}^{\alpha _{2}}$ содержат одно и то же ненулевое кодовое слово $y.$ Теперь, поскольку $y\in C_{in}^{\alpha _{1}},y=(y_{1},\alpha _{1}y_{1})$ для некоторых $y_{1}\in \mathbb {F} _{q}^{k}$ и аналогично $y=(y_{2},\alpha _{2}y_{2})$ для некоторых $y_{2}\in \mathbb {F} _{q}^{k}.$ Более того, поскольку $y$ не равно нулю, у нас есть $y_{1},y_{2}\neq 0.$ Поэтому $(y_{1},\alpha _{1}y_{1})=(y_{2},\alpha _{2}y_{2})$, затем $y_{1}=y_{2}\neq 0$ и $\alpha _{1}y_{1}=\alpha _{2}y_{2}.$ Это подразумевает $\alpha _{1}=\alpha _{2}$, что является противоречием.

Любой линейный код, имеющий расстояние $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k$ имеет некоторое кодовое слово веса $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$ Теперь из леммы следует, что мы имеем по крайней мере $|P|$ другой $y$ такой, что $wt(y)<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k$ (одно такое кодовое слово $y$ для каждого линейного кода). Здесь $wt(y)$ обозначает вес кодового слова $y$, которое представляет собой количество ненулевых позиций $y$.

Обозначим

$S=\left\{y\ :\ wt(y)<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\right\}$

Затем:

${\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{ is the volume of Hamming ball of radius }}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{ large enough }}\\&=\varepsilon N\end{aligned}}$

Так $|P|<\varepsilon N$, поэтому набор линейных кодов, имеющих относительное расстояние $\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k$ имеет по крайней мере $N-\varepsilon N=(1-\varepsilon )N$ элементы.

См. также

• Хэмминг связан
• Код Юстесена
• Линейный код

Ссылки

• Мэсси, Джеймс Л. (1963), Пороговое декодирование , Tech. Отчет 410, Кембридж, Массачусетс: Массачусетский технологический институт, Исследовательская лаборатория электроники, hdl : 1721.1/4415 , MR   0154763 .
• Юстесен, Йорн (1972), «Класс конструктивных асимптотически хороших алгебраических кодов», Институт инженеров по электротехнике и электронике. Труды по теории информации , IT-18 (5): 652–656, doi : 10.1109/TIT.1972.1054893 , MR   0384313 .

Внешние ссылки

• Лекция 28: Кодекс Юстесена. Курс теории кодирования. Профессор Атри Рудра .
• Лекция 9: Границы объема шара Хэмминга. Курс теории кодирования. Профессор Атри Рудра .
• Дж. Юстесен (1972). «Класс конструктивных асимптотически хороших алгебраических кодов». IEEE Транс. Инф. Теория . 18 (5): 652–656. дои : 10.1109/TIT.1972.1054893 .
• Заметки по теории кодирования: граница Гилберта-Варшамова. Венкатесан Гурусвами