Элиас Бассалиго связан

Граница Элиаса Бассалиго — это математический предел, используемый в теории кодирования для исправления ошибок во время передачи данных или связи.

Определение

Позволять $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$ удовлетворить границу Элиаса-Бассалиго:

$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)$

См. также

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

Ссылки

Бассалиго, Л. А. (1965), «Новые верхние границы для кодов, исправляющих ошибки», Проблемы передачи информации , 1 (1): 32–35.

Клод Э. Шеннон, Роберт Г. Галлагер; Берлекамп, Элвин Р. (1967), «Нижние границы вероятности ошибки для кодирования по дискретным каналам без памяти. Часть I.», Information and Control , 10 : 65–103, doi : 10.1016/s0019-9958(67)90052-6

Клод Э. Шеннон, Роберт Г. Галлагер; Берлекамп, Элвин Р. (1967), «Нижние границы вероятности ошибки для кодирования по дискретным каналам без памяти. Часть II.», Information and Control , 10 : 522–552, doi : 10.1016/s0019-9958(67)91200-4