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

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

Определение

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

${displaystyle d = min _ {x, yin C, xeq y} d (x, y),}$

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

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

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

${Displaystyle A_ {q} (n, d) = max _ {Cin C_ {q} (n, d)} | C |.}$

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

${displaystyle A_ {q} (n, d, w) = max _ {Cin 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 выбрать t + 1} (q-1) ^ {t + 1} - {d выбрать t} A_ {q} (n, d, d)} {A_ {q} (n, d, t + 1 )}}}}.}$

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

${displaystyle A_ {q} (n, d) leq {frac {q ^ {n}} {sum _ {i = 0} ^ {t} {n choose i} (q-1) ^ {i} + {frac {{n выбрать 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 dleq 2w}$, затем определите переменную ${displaystyle e}$ следующее. Если ${displaystyle d}$ четно, тогда определим ${displaystyle e}$ через отношение ${displaystyle d = 2e}$; если ${displaystyle d}$ нечетно, определите ${displaystyle e}$ через отношение ${displaystyle d = 2e-1}$. Позволять ${displaystyle q ^ {*} = q-1}$. Потом,

${displaystyle A_ {q} (n, d, w) leq leftlfloor {frac {nq ^ {*}} {w}} leftlfloor {frac {(n-1) q ^ {*}} {w-1}} leftlfloor cdots leftlfloor {frac {(n-w + e) ​​q ^ {*}} {e}} ightfloor cdots ightfloor ightfloor ightfloor}$

куда ${displaystyle lfloor ~~ floor}$ это функция пола.

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

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

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

Рекомендации

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