Грисмер байланған - Griesmer bound

Ішінде математика туралы кодтау теориясы, Грисмер байланған, Джеймс Уго Грисмердің есімімен аталады, ұзындығына байланысты сызықтық екілік кодтар өлшем к және минималды арақашықтық г..Екілік емес кодтар үшін өте ұқсас нұсқа бар.

Шектеу туралы мәлімдеме

Екілік сызықтық код үшін Грисмер байланысы:

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

Дәлел

Келіңіздер ${displaystyle N (k, d)}$ екілік өлшем кодының минималды ұзындығын белгілеңіз к және қашықтық г.. Келіңіздер C осындай код бол. Біз мұны көрсеткіміз келеді

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

Келіңіздер G матрицасының генераторы болыңыз C. Біз әрқашан бірінші қатар деп ойлай аламыз G формада болады р = (1, ..., 1, 0, ..., 0) салмақпен г..

{displaystyle G = {egin {bmatrix} 1 & dots & 1 & 0 & dots & 0 ast & 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) 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}}.}$ Бұл білдіреді