WikiDer > Граница Грисмера

Griesmer bound

в математика из теория кодирования, то Граница Грисмера, названный в честь Джеймса Хьюго Грайсмера, ограничен длиной линейный двоичный коды измерения k и минимальное расстояние d.Есть также очень похожая версия для недвоичных кодов.

Заявление о привязке

Для двоичного линейного кода граница Грайсмера:

Доказательство

Позволять обозначают минимальную длину двоичного кода размерности k и расстояние d. Позволять C быть таким кодом. Мы хотим показать, что

Позволять грамм быть образующей матрицей C. Всегда можно предположить, что первая строка грамм имеет форму р = (1, ..., 1, 0, ..., 0) с весом d.

Матрица генерирует код , который называется остаточным кодом очевидно имеет размер и длина находится на расстоянии но мы этого не знаем. Позволять быть таким, чтобы . Существует вектор так что конкатенация потом С другой стороны, также поскольку и линейно: Но

так это становится . Суммируя это с мы получаем . Но так что мы получаем Из этого следует

поэтому из-за целостности

так что

Индукцией по k мы в конечном итоге получим

Обратите внимание, что на любом этапе размер уменьшается на 1, а расстояние - вдвое, и мы используем тождество

для любого целого числа а и положительное целое число k.

Оценка для общего случая

Для линейного кода над , граница Грайсмера принимает вид:

Доказательство аналогично бинарному случаю и поэтому не приводится.

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

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

  • Дж. Х. Грисмер, "Граница для кодов с исправлением ошибок", IBM Journal of Res. и Dev., т. 4, вып. 5. С. 532-542, 1960.