Грисмер связан

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

Заявление о границах

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

n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .

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

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

N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .

Пусть G — порождающая матрица C . Мы всегда можем предположить, что первая строка G имеет вид r = (1,...,1,0,...,0) с весом d .

G={\begin{bmatrix}1&\dots &1&0&\dots &0\\\ast &\ast &\ast &&G'&\\\end{bmatrix}}

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

w((v|u)+r)=w(((1,\cdots ,1)+v)|u)=d-w(v)+w(u),

так что это становится $d-w(v)+w(u)\geqslant d$ . Суммируя это с $w(v)+w(u)\geqslant d,$ мы получаем $d+2w(u)\geqslant 2d$ . Но $w(u)=d',$ так что мы получаем $2d'\geqslant d.$ Как $d'$ является целым, мы получаем $d'\geqslant \left\lceil {\tfrac {d}{2}}\right\rceil .$ Это подразумевает