Elias Bassalygo Bound

Связь Elias Bassalygo - это математический предел, используемый в теории кодирования для коррекции ошибок во время передачи данных или связи.

Определение

Позволять $C$ быть $q$-ремящий код длины $n$, т.е. подмножество $[q]^{n}$. Позволять $R$ быть скоростью ​ $C$, $\delta$ относительное расстояние и

$B_{q}(y,\rho n)=\left\{x\in [q]^{n}\ :\ \Delta (x,y)\leqslant \rho n\right\}$

быть шаром радиуса $\rho n$ сосредоточен на $y$Полем Позволять ${\text{Vol}}_{q}(y,\rho n)=|B_{q}(y,\rho n)|$ быть объемом хаммингового шарика радиуса $\rho n$Полем Очевидно, что объем шарика хэмминга является инвариантом перевода, то есть безразлично к $y.$ В частности, $|B_{q}(y,\rho n)|=|B_{q}(0,\rho n)|.$

С достаточно большим $n$, скорость $R$ и относительное расстояние $\delta$ Удовлетворить границу Elias-Bassalygo:

$R\leqslant 1-H_{q}(J_{q}(\delta ))+o(1),$

где

$H_{q}(x)\equiv _{\text{def}}-x\log _{q}\left({x \over {q-1}}\right)-(1-x)\log _{q}{(1-x)}$

это Q функция энтропии и

$J_{q}(\delta )\equiv _{\text{def}}\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)$

это функция, связанная с Джонсоном .

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

Чтобы доказать связанную Элиас -Бассалиго, начните со следующей леммы:

Лемма. Для $C\subseteq [q]^{n}$ и $0\leqslant e\leqslant n$, существует радиус хэмминга $e$ по крайней мере

${\frac {|C|{\text{Vol}}_{q}(0,e)}{q^{n}}}$

Кодовые слова в нем.

Доказательство леммы. Случайно выберите полученное слово $y\in [q]^{n}$ и пусть $B_{q}(y,0)$ Будьте мячом, сосредоточенным на $y$ с радиусом $e$Полем С $y$ (равномерный) случайным образом выбран ожидаемый размер перекрывающейся области $|B_{q}(y,e)\cap C|$ является

${\frac {|C|{\text{Vol}}_{q}(y,e)}{q^{n}}}$

Поскольку это ожидаемое значение размера, должен существовать как минимум один $y$ так что

$|B_{q}(y,e)\cap C|\geqslant {{|C|{\text{Vol}}_{q}(y,e)} \over {q^{n}}}={{|C|{\text{Vol}}_{q}(0,e)} \over {q^{n}}},$

В противном случае ожидание должно быть меньше этого значения.

Теперь мы доказываем, что Элиас -Бассалиго связано. Определять $e=nJ_{q}(\delta )-1.$ Леммой, существует мяч с хэммингом с $B$ Кодовые организации такие, что:

$B\geqslant {{|C|{\text{Vol}}(0,e)} \over {q^{n}}}$

По границе Джонсона у нас есть $B\leqslant qdn$Полем Таким образом,

$|C|\leqslant qnd\cdot {{q^{n}} \over {{\text{Vol}}_{q}(0,e)}}\leqslant q^{n(1-H_{q}(J_{q}(\delta ))+o(1))}$

Второе неравенство следует из нижней границы на объеме шарика Хамминга:

${\text{Vol}}_{q}\left(0,\left\lfloor {\frac {d-1}{2}}\right\rfloor \right)\geqslant q^{H_{q}\left({\frac {\delta }{2}}\right)n-o(n)}.$

Внедряя $d=2e+1$ и $\delta ={\tfrac {d}{n}}$ дает второе неравенство.

Поэтому у нас есть

$R={\log _{q}{|C|} \over n}\leqslant 1-H_{q}(J_{q}(\delta ))+o(1)$

Смотрите также

• Гилберт - Варшамов связан
• Хаминг связан
• Джонсон связан
• Плоткин связан
• Синглтон связан

Ссылки

Bassalygo, LA (1965), «Новые верхние границы для коррекции ошибок», проблемы передачи информации , 1 (1): 32–35

Клод Э. Шеннон, Роберт Дж. Галлагер; Berlekamp, ​​Elwyn R. (1967), «Нижние границы с вероятностью ошибок для кодирования на дискретных каналах без памяти. Часть I.», Информация и управление , 10 : 65–103, doi : 10.1016/s0019-9958 (67) 90052-6

Клод Э. Шеннон, Роберт Дж. Галлагер; Berlekamp, ​​Elwyn R. (1967), «Нижние границы с вероятностью ошибок для кодирования на дискретных каналах без памяти. Часть II.», Информация и управление , 10 : 522–552, doi : 10.1016/s0019-9958 (67) 91200-4