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

Johnson bound

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

Определение

Позволять быть q-ари код длины , т.е. подмножество . Позволять быть минимальным расстоянием , т.е.

куда это Расстояние Хэмминга между и .

Позволять быть набором всех q-арные коды с длиной и минимальное расстояние и разреши обозначим набор кодов в так что каждый элемент имеет ровно ненулевые записи.

Обозначим через количество элементов в . Затем определим быть наибольшим размером кода с длиной и минимальное расстояние :

Аналогично определяем быть самым большим размером кода в :

Теорема 1 (оценка Джонсона для ):

Если ,

Если ,

Теорема 2 (оценка Джонсона для ):

(я) Если

(ii) Если , затем определите переменную следующее. Если четно, тогда определим через отношение ; если нечетно, определите через отношение . Позволять . Потом,

куда это функция пола.

Замечание: Подстановка оценки теоремы 2 в оценку теоремы 1 дает числовую оценку сверху на .

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

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

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