Ãëàâíàÿ > Ïîìåõîóñòîé÷èâîå êîäèðîâàíèå > Òåîðèÿ êîäîâ, èñïðàâëÿþùèõ îøèáêè
<< Ïðåäûäóùèé ïàðàãðàô
Ñëåäóþùèé ïàðàãðàô >>
<< Ïðåäûäóùèé ïàðàãðàô Ñëåäóþùèé ïàðàãðàô >>
Ìàêåòû ñòðàíèö

17.5. ÃÐÀÍÈÖÀ ÃÐÀÉÑÌÅÐÀ

Äëÿ ëèíåéíîãî -êîäà ãðàíèöà Ñèíãëòîíà (17.45) óòâåðæäàåò, ÷òî Ãðàíèöà Ãðàéñìåðà, çàäàâàåìàÿ âûðàæåíèåì (17.52), óâåëè÷èâàåò ïðàâóþ ÷àñòü ýòîãî íåðàâåíñòâà. Ëó÷øå âñåãî ïðèâåñòè ýòó ãðàíèöó, èñïîëüçóÿ âåëè÷èíó ìèíèìàëüíî âîçìîæíóþ äëèíó äâîè÷íîãî ëèíåéíîãî êîäà ðàçìåðíîñòè ñ ìèíèìàëüíûì ðàññòîÿíèåì

Òåîðåìà 23.

Äîêàçàòåëüñòâî. Ïóñòü -êîä ñ ïîðîæäàþùåé ìàòðèöåé Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî

ãäå ìàòðèöà èìååò ðàíã â ïðîòèâíîì ñëó÷àå ìû áû îáðàòèëè â íóëü ïåðâóþ ñòðîêó ìàòðèöû è ìèíèìàëüíîå ðàññòîÿíèå êîäà áûëî áû ìåíüøå ÷åì

Ïóñòü ìàòðèöà ïîðîæäàåò -êîä. Ïðåäïîëîæèì, ÷òî âåêòîð ãäå Òàê êàê òî

è, ñêëàäûâàÿ ýòè íåðàâåíñòâà, ïîëó÷àåì, ÷òî èëè . Ñëåäîâàòåëüíî,

Òåîðåìà 24. (Ãðàíèöà Ãðàéñìåðà [562]; ñì. òàêæå ðàáîòó Ñîëîìîíà è Ñòèôôëåðà [1257].)

Äîêàçàòåëüñòâî. Ìíîãîêðàòíî ïðèìåíÿÿ òåîðåìó 23, íàõîäèì, ÷òî

Ïðèìåðû. (1). Íàéäåì ÷èñëî ò. å. ñàìûé êîðîòêèé êîä ðàçìåðíîñòè 5, èñïðàâëÿþùèé òðè îøèáêè. Ñîãëàñíî òåîðåìå 24

 äåéñòâèòåëüíîñòè ñóùåñòâóåò -êîä Á×Õ, è ïîýòîìó

(2). Åñëè òî èç òåîðåìû 24 âûòåêàåò, ÷òî

Íà ñàìîì äåëå ñèìïëåêñíûé (ñì. ãë. 1) ïîêàçûâàåò, ÷òî ýòà ãðàíèöà äîñòèãàåòñÿ.

<< Ïðåäûäóùèé ïàðàãðàô Ñëåäóþùèé ïàðàãðàô >>
Îãëàâëåíèå