Джонсон связан

В прикладной математике граница Джонсона (названная в честь Сельмера Мартина Джонсона ) представляет собой ограничение на размер кодов с исправлением ошибок , используемых в теории кодирования для передачи данных или связи.

Определение

Позволять $C$ быть q -ичным кодом длины $n$ , то есть подмножество $\mathbb {F} _{q}^{n}$ . Позволять $d$ быть минимальным расстоянием $C$ , то есть

d=\min _{x,y\in C,x\neq y}d(x,y),

где $d(x,y)$ Хэмминга расстояние между $x$ и $y$ .

Позволять $C_{q}(n,d)$ — множество всех q -ичных кодов длины $n$ и минимальное расстояние $d$ и пусть $C_{q}(n,d,w)$ обозначим набор кодов в $C_{q}(n,d)$ такая, что каждый элемент имеет ровно $w$ ненулевые записи.

Обозначим через $|C|$ количество элементов в $C$ . Затем мы определяем $A_{q}(n,d)$ быть наибольшим размером кода с длиной $n$ и минимальное расстояние $d$ :

A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.

Аналогично определяем $A_{q}(n,d,w)$ быть наибольшим размером кода в $C_{q}(n,d,w)$ :

A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.

Теорема 1 (оценка Джонсона для $A_{q}(n,d)$ ):

Если $d=2t+1$ ,

A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}-{d \choose t}A_{q}(n,d,d)}{A_{q}(n,d,t+1)}}}}.

Если $d=2t+2$ ,

A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}}{A_{q}(n,d,t+1)}}}}.

Теорема 2 (оценка Джонсона для $A_{q}(n,d,w)$ ):

(i) Если $d>2w,$

A_{q}(n,d,w)=1.

(ii) Если $d\leq 2w$ , затем определите переменную $e$ следующее. Если $d$ четно, то определим $e$ через отношение $d=2e$ ; если $d$ нечетно, определите $e$ через отношение $d=2e-1$ . Позволять $q^{*}=q-1$ . Затем,