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

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

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

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

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

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

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

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

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

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

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

Если ,${\displaystyle d=2t+1}$

${\displaystyle 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)}}}}.}$

Если ,${\displaystyle d=2t+2}$

${\displaystyle 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 (граница Джонсона для ):${\displaystyle A_{q}(n,d,w)}$

(я) Если${\displaystyle d>2w,}$

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

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

${\displaystyle A_{q}(n,d,w)\leq \left\lfloor {\frac {nq^{*}}{w}}\left\lfloor {\frac {(n-1)q^{*}}{w-1}}\left\lfloor \cdots \left\lfloor {\frac {(n-w+e)q^{*}}{e}}\right\rfloor \cdots \right\rfloor \right\rfloor \right\rfloor }$

где - функция пола .${\displaystyle \lfloor ~~\rfloor }$

Замечание: Подстановка границы теоремы 2 в границу теоремы 1 дает численную верхнюю границу для .${\displaystyle A_{q}(n,d)}$

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

• Джонсон, Селмер Мартин (апрель 1962 г.). «Новая верхняя граница для кодов с исправлением ошибок». Труды IRE по теории информации : 203–207.
• Хаффман, Уильям Кэри; Плесс, Вера С. (2003). Основы кодов исправления ошибок . Cambridge University Press . ISBN 978-0-521-78280-7.