Граница Грисмера - Griesmer bound

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

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

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

${displaystyle ngeqslant sum _{i=0}^{k-1}leftlceil {frac {d}{2^{i}}}ightceil .}$

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

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

${displaystyle N(k,d)geqslant sum _{i=0}^{k-1}leftlceil {frac {d}{2^{i}}}ightceil .}$

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

${displaystyle G={egin{bmatrix}1&dots &1&0&dots &0ast &ast &ast &&G'&end{bmatrix}}}$

Матрица ${displaystyle G'}$ генерирует код ${displaystyle C'}$, который называется остаточным кодом ${displaystyle C.}$ ${displaystyle C'}$ очевидно имеет размер ${displaystyle k'=k-1}$ и длина ${displaystyle n'=N(k,d)-d.}$ ${displaystyle C'}$ находится на расстоянии ${displaystyle d',}$ но мы этого не знаем. Позволять ${displaystyle uin C'}$ быть таким, чтобы ${displaystyle w(u)=d'}$. Существует вектор ${displaystyle vin mathbb {F} _{2}^{d}}$ так что конкатенация ${displaystyle (v|u)in C.}$ потом ${displaystyle w(v)+w(u)=w(v|u)geqslant d.}$ С другой стороны, также ${displaystyle (v|u)+rin C,}$ поскольку ${displaystyle rin C}$ и ${displaystyle C}$ линейно: ${displaystyle w((v|u)+r)geqslant d.}$ Но

${displaystyle w((v|u)+r)=w(((1,cdots ,1)+v)|u)=d-w(v)+w(u),}$

так это становится ${displaystyle d-w(v)+w(u)geqslant d}$. Суммируя это с ${displaystyle w(v)+w(u)geqslant d,}$ мы получаем ${displaystyle d+2w(u)geqslant 2d}$. Но ${displaystyle w(u)=d',}$ так что мы получаем ${displaystyle d'geqslant { frac {d}{2}}.}$ Из этого следует

${displaystyle n'geqslant Nleft(k-1,{ frac {d}{2}}ight),}$

поэтому из-за целостности ${displaystyle n'}$

${displaystyle n'geqslant leftlceil Nleft(k-1,{ frac {d}{2}}ight)ightceil ,}$

так что

${displaystyle N(k,d)geqslant leftlceil Nleft(k-1,{ frac {d}{2}}ight)ightceil +d.}$

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

${displaystyle N(k,d)geqslant sum _{i=0}^{k-1}leftlceil {frac {d}{2^{i}}}ightceil .}$

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

${displaystyle leftlceil {frac {leftlceil a/2^{k-1}ightceil }{2}}ightceil =leftlceil {frac {a}{2^{k}}}ightceil }$

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

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

Для линейного кода над ${displaystyle mathbb {F} _{q}}$, граница Грайсмера принимает вид:

${displaystyle ngeqslant sum _{i=0}^{k-1}leftlceil {frac {d}{q^{i}}}ightceil .}$

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

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

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

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

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