А.Б. Угольников - Лекции по дискретной математике, страница 6

Ïðè ýòîì àëãîðèòì äåøèôðîâêèñîîáùåíèÿ ñîñòîèò â ñëåäóþùåì: ïóñòü ñîîáùåíèåïðåâðàòèëîñü â ñòðîêóà)β.αïðè ïðîõîæäåíèè ÷åðåç êàíàë ñâÿçèÂîçìîæíû äâå ñèòóàöèèH(β) = 0 ⇔ N (H(β)) = 0.  ýòîì ñëó÷àå â ïðåäïîëîæåíèè, ÷òî â êàíàëå ñâÿçè áîëåå îäíîéα = β.îøèáêè ïðîèçîéòè íå ìîãëî, äåëàåì âûâîä, ÷òîá)H(β) 6= 0 ⇔ N (H(β)) = j 6= 0. ýòîì ñëó÷àå, âñ¼ â òîì æå ïðåäïîëîæåíèè î êîëè-÷åñòâå îøèáîê â êàíàëå, äåëàåì âûâîä, ÷òî îøèáêà âj -îìN (H(β)) = N (H(α + αj )) = N (Í(α) + H(αj )) == N (H(α)) + N (H(αj )) = 0 + N (ek (j)) = j.òèâîïîëîæíûé. Äåéñòâèòåëüíî, îøèáêà âj -ìðàçðÿäå è çàìåíÿåì åãî íà ïðî-α, β ∈ V ρ(α, β) > 3 âûøå ìû ïîëó÷àëè, ÷òî äëÿρ(α, β) > 2t + 1, ïî ïðåäûäóùåìó ñâîéñòâó V ÿâëÿåòñÿ Vn1 .3.

Äëÿ ëþáûõV4.β = α + αj .ðàçðÿäå îçíà÷àåò, ÷òîëþáûõÏîýòîìóα, β ∈ Vntÿâëÿåòñÿ ëèíåéíûì ïðîñòðàíñòâîì, êàê ÿäðî ëèíåéíîãî îïåðàòîðà. Ïîñòðîåííûé êîäVÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì áîëåå îáùèõ ëèíåéíûõ êîäîâ Á×Õ, â ÷¼ì ìû óáåäèìñÿ ïîçæå.5. Ïî ñâîéñòâó 3 äëÿ ëþáîãî6. Åñëèn = 2 k − 1,òîα ∈ V kαk = ρ(0, α) > 3.|V | = 2n−k =2nn+1⇒ 2n = |V | · (n + 1) = |V | · |SHn1 (α)|,ò.å.Vâ ýòîì ñëó÷àåÿâëÿåòñÿ ñîâåðøåííûì.Ëèíåéíûå êîäû.Ïðåäûäóùèå ïîñòðîåíèÿ ìîæíî îáîáùèòü íà ñëó÷àé áîëüøåãî êîëè÷åñòâàïðîâåðî÷íûõ ðàçðÿäîâ.

ÏóñòüH(n − k) × nìàòðèöà íàä(Z)2 ,èìåþùàÿ ñëåäóþùóþ ñòðóêòóðó:H = (A|In−k ),Aãäå íåêîòîðàÿ(n − k) × kìàòðèöà,In−k åäèíè÷íàÿ ìàòðèöà ïîðÿäêàn − k.ÏóñòüV = {x ∈ B n | HxT = 0} ÿäðî îïåðàòîðàH.ßñíî, ÷òî â âèäó ñïåöèàëüíîé ñòðóêòóðû ìàòðèöûHñèñòåìà óðàâíåíèéHxT = 0ðàçðåøèìà îòíîñèòåëüíî ïîñëåäíèõ(n − k)êîîðäèíàò, ò.å.Vìîæíî ïåðåïèñàòü ïî äðóãîìó:V = {x ∈ B n |xT = GT uT , u ∈ B k },ãäåGT =ÌàòðèöàG = Ik |ATIkA.dimV = k. V , êàê ÿäðîd ìèíèìàëüíîå ðàññòîÿíèå êîäà:íàçûâàåòñÿ ïîðîæäàþùåé ìàòðèöåé. ßñíî, ÷òîëèíåéíîãî îïåðàòîðà, ÿâëÿåòñÿ ëèíåéíûì ïðîñòðàíñòâîì. Ââåä¼ìd = min ρ(α, β) = min kαk.α∈Vα6=0α,β∈Vα6=βn, kèdÿâëÿþòñÿ ïàðàìåòðàìè ëèíåéíîãî êîäà, ïîýòîìó ëèíåéíûé êîä, îòâå÷àþùèé ýòèì ïàðà-ìåòðàì îáîçíà÷àþò[n, k, d]-êîä.ßñíî, ÷òî â ñèëó (1)[n, k, d]-êîäèñïðàâëÿåò d−1 2îøèáîê.Ñâÿçü ìåæäó ìèíèìàëüíûì ðàññòîÿíèåì êîäà è ðàíãîì åãî ïðîâåðî÷íîé ìàòðèöû óñòàíàâëèâàåòñëåäóþùååÓòâåðæäåíèå.

Ïóñòü V ëèíåéíûé êîä ñ ïðîâåðî÷íîé ìàòðèöåé H . Òîãäà V èìååò ìèíèìàëüíîå ðàññòîÿíèå d ðàâíîñèëüíî îäíîâðåìåííîìó âûïîëíåíèþ ñëåäóþùèõ äâóõ óñëîâèé:31à) ëþáûå (d − 1) ñòîëáöîâ â H ëèíåéíî íåçàâèñèìû;á) ñóùåñòâóþò d ëèíåéíî çàâèñèìûõ ñòîëáöîâ(óñëîâèÿ à) è á) âìåñòå îçíà÷àþò, ÷òî ðàíã ìàòðèöû H ðàâåí d − 1 ).Äîêàçàòåëüñòâî. Ïóñòü V èìååò ìèíèìàëüíîå êîäîâîå ðàññòîÿíèå d. Òîãäà ñóùåñòâóåò òàêîåx = (x1 , ..., xn ), ÷òî HxT = 0, ïðè÷¼ì x èìååò ðîâíî d íåíóëåâûõ êîìïîíåíò.

Ýòî çíà÷èò, ÷òîñòîëáöû ìàòðèöû H ñ íîìåðàìè ýòèõ íåíóëåâûõ êîìïîíåíò áóäóò ëèíåéíî çàâèñèìû. d − 1 æåëèíåéíî çàâèñèìûõ ñòîëáöîâ íåò, èíà÷å ñóùåñòâîâàë áû x ∈ V ñ ìåíüøåé íîðìîé ïðîòèâîðå÷èåñ ìèíèìàëüíîñòüþ d. Îáðàòíî, åñëè ñóùåñòâóåò d ëèíåéíî çàâèñèìûõ ñòîëáöîâ, òî x = (x1 , ..., xn ),èìåþùèé íà ìåñòàõ ñ ýòèìè íîìåðàìè åäèíèöû, à íà îñòàëüíûõ íóëè, ëåæèò â V.  òî æå âðåìÿ,åñëè áû êîäîâîå ðàññòîÿíèå V áûëî ìåíüøå d, òî ïî äîêàçàííîìó âûøå ñóùåñòâîâàëè áû d − 1ëèíåéíî çàâèñèìûõ ñòîëáöîâ ó H ïðîòèâîðå÷èå ñ à). Äîêàçàòåëüñòâî îêîí÷åíî.32(29.10.03)Ëåêöèÿ 9Êîäû Á×Õ (Áîóç, ×îóäõóðè, Õîêâèíãåì)Ïóñòü ìû õîòèì ïîñòðîèòü ëèíåéíûé êîä èñïðàâëÿþùèéâîãî ðàññòîÿíèÿdtîøèáîê, ò.å.

õîòèì, ÷òîáû äëÿ êîäî-áûëî ñïðàâåäëèâî íåðàâåíñòâî:d > 2t + 1.Êàê ñëåäóåò èç óòâåðæäåíèÿ, äîêàçàííîãî â êîíöå ïðåäûäóùåé ëåêöèè, äëÿ ýòîãî äîñòàòî÷íî,÷òîáû ëþáûå2tÏóñòü òåïåðüñòîëáöîâ ïðîâåðî÷íîé ìàòðèöût = 1.Háûëè ëèíåéíî íåçàâèñèìû.Óñëîâèå ëèíåéíîé íåçàâèñèìîñòè ëþáûõ äâóõ ñòîëáöîâ îçíà÷àåò îäíîâðå-ìåííîå âûïîëíåíèå ñëåäóþùèõ 2-õ óñëîâèé:hi 6= 0, i = 1, ..., n;hi 6= hj , ïðè i 6= j, i, j = 1, ..., n,ãäå hi , i = 1, ..., n ñòîëáöû ìàòðèöû H. Åñëè òåïåðü â êà÷åñòâå ñòîëáöîâ ìàòðèöû H âçÿòü hi =en−k (i) â îáîçíà÷åíèÿõ ââåä¼ííûõ íà ïðîøëîé ëåêöèè, òî ïîëó÷èì êîä Õýììèíãà. Ïðàâäà, òàêàÿ1)2)ìàòðèöà íå áóäåò èìåòü êàíîíè÷åñêîé ñòðóêòóðû (7) èç ïðåäûäóùåé ëåêöèè äëÿ ýòîãî íàäîïåðåñòàâèòü å¼ ñòîëáöû.Çàéì¼ìñÿ òåïåðü ïîñòðîåíèåì êîäîâ Á×Õ äëÿ ïðîèçâîëüíîãît,âûáåðåì ïàðàìåòðûnèm,t.Ïóñòü íàì äàíû ïàðàìåòðûkèòàê ÷òîáû âûïîëíÿëèñü ñîîòíîøåíèÿ :n = 2m − 1,k > n − tm.GF (2m ) ôàêòîðπ(x) ñòåïåíè m.

Ýëåìåíòàìè âÍà îäíîé èç ïðîøëûõ ëåêöèé ìû ïîñòðîèëè ïîëåêîëüöà äâîè÷íûõ ìíîãî-÷ëåíîâ ïî íåïðèâîäèìîìó ìíîãî÷ëåíóí¼ì ÿâëÿþòñÿ ìíîãî÷ëå-0, α1 , α2 , ..., α2m −1 , è óìíîæåíèå ïðîèçâîäèòñÿαi = aim−1 xm−1 + ... + ai0 . Îáîçíà÷èìíûγi =  ñòîëáåö êîýôôèöèåíòîâαi .ïî ìîäóëþ òîãî ñàìîãî ìíîãî÷ëåíàai0...aim−1Äëÿ ñòîëáöîâ âûñîòûmπ(x).Ïóñòüîïðåäåëèì ïðîèçâåäåíèå, êàê ñòîëáåö, ñîîò-GF (2m ). Ââåmâûøå, n = 2 − 1):âåòñòâóþùèé ìíîãî÷ëåíó, ðàâíîìó ïðîèçâåäåíèþ ñîîòâåòñòâóþùèõ ìíîãî÷ëåíîâ èçä¼ì â ðàññìîòðåíèå ìàòðèöóAGF (2 ) (êàê. . . αn. . .

αn3t.... . . αn2t−1ñ êîýôôèöèåíòàìè èçα1 α13A=  . ..α12t−1è ñîîòâåòñòâóþùóþ åé ìàòðèöóHmîòìå÷àëîñüñ êîýôôèöèåíòàìè èçγ1 γ13H= . ..γ12t−1Z2 :. . . γn. . . γn3tm.... . . γn2t−1Ïåðåä äîêàçàòåëüñòâîì ñëåäóþùåãî óòâåðæäåíèÿ îòìåòèì, ÷òî2 (î÷åâèäíî). Îòñþäà ñëåäóåò, ÷òî äëÿ ëþáûõmx1 , .., xs ∈ GF (2 )(x1 + ... + xs )2 = x21 + ... + x2s .33GF (2m ) ïîëå õàðàêòåðèñòèêèñïðàâåäëèâî ðàâåíñòâî:Ïî èíäóêöèè ëåãêî ïîêàçàòü ñïðàâåäëèâîñòü ñëåäóþùåãî ðàâåíñòâà:uuu(x1 + ... + xs )2 = x21 + ...

+ x2s .(1)Óòâåðæäåíèå.  ìàòðèöå H ëþáûå 2t ñòîëáöîâ ëèíåéíî íåçàâèñèìû.Äîêàçàòåëüñòâî. Äîïóñòèì ïðîòèâíîå. Ò.å. íàéäóòñÿ l 6 2t ñòîëáöîâ ñêèå ÷òîhi1 + ... + hil = 0,ãäåhi , i = 1, ..., n ñòîëáöû ìàòðèöûH.íîìåðàìèi1 , ..., il ,òà-Ýòî îçíà÷àåò îäíîâðåìåííîåâûïîëíåíèå ñëåäóþùèõ ðàâåíñòâ:γi1 γi31+ . . . + γil+ . .

. + γi3l=0=0+ . . . + γi2t−1l=0αi1 αi31+ . . . + αil+ . . . + αi3l=0=0+ . . . + αi2t−1l=0......γi2t−11÷òî â ñâîþ î÷åðåäü îçíà÷àåòÏîêàæåì, ÷òî äëÿ ëþáîãî ÷¼òíîãî...(2)...αi2t−112 6 q 6 2tñïðàâåäëèâî:αiq1 + ... + αiql = 0.Äåéñòâèòåëüíî,qìîæíî ïðåäñòàâèòü â âèäå:2u (2v−1)αiq1 + ... + αiql = αi1ò.ê.(3)q = 2u (2v − 1), v 6 t.Ïîýòîìó:2 u(2v−1)(2v−1)= αi1+ ... + αil= 0,2u (2v−1) (1)+ ... + αil(2v−1)αi1(2v−1)+ ... + αilÒàêèì îáðàçîì, èç (2) è (3) ïîëó÷àåì äëÿ ëþáîãî= 0.1 6 q 6 2tαiq1 + ...

+ αiql = 0.(4)Ðàññìîòðèì îïðåäåëèòåëü αi1 2 αi 1W = .. . i αli1......αilαi2l......αiill 1 αi1 = αi1 · . . . · αil .. . i −1 αli1êàê îïðåäåëèòåëü Âàíäåðìîíäà, ó÷èòûâàÿ, ÷òîαi 6= αj ,ïðè... 1. . . αil......i 6= j,αiill −1è 6= 0,αi 6= 0äëÿ ëþáîãî1 6 i 6 n.Ïîëó÷àåì ïðîòèâîðå÷èå ñ (4). Óòâåðæäåíèå äîêàçàíî.Èç Óòâåðæäåíèÿ ñëåäóåò, ÷òî ìàòðèöàHçàäà¼ò ëèíåéíûé[n, k, d]- êîä, ñî ñëåäóþùèìè ïàðà-ìåòðàìèn = 2m − 1,k > n − tm,d > 2t + 1.Àëãîðèòì ðàñïîçíàâàíèÿ îøèáîê â îáùåì ñëó÷àå î÷åíü íå ïðîñòîé. Ìû ðàññìîòðèì åãî äëÿt = 2.34 ýòîì àëãîðèòìå àïðèîðè ïðåäïîëàãàåòñÿ, ÷òî â ðåçóëüòàòå ïåðåäà÷è ñîîáùåíèÿ íå ìîæåò ïðî-x ∈ KerA (âàæíî ïîíèìàòü, ÷òî õîòÿ â òåîðèèH ) ïîñëå ïðîõîæäåíèÿïî êàíàëó ñâÿçè ïåðåõîäèò â ñîîáùåíèå y.

Âû÷èñëèì ñèíäðîì: z1S = Ay =, z1 , z2 ∈ GF (4)z20ßñíî, ÷òî ïî ïðåäïîëîæåíèþ íà êîëè÷åñòâî îøèáîê x = y ðàâíîñèëüíî S =0 . Ïóñòü òåïåðünïðîèçîøëà îäíà îøèáêà â ðàçðÿäå i, ò.å. y = x + ei (ei áàçèñíûé âåêòîð Z2 ñ åäèíèöåé òîëüêî íài-ì ìåñòå). ÒîãäàS = A(x + ei ) = Aei = αi αi3 .èçîéòè áîëåå äâóõ îøèáîê. Ïóñòü èñõîäíîå ñîîáùåíèåìû îïåðèðóåì ñ ìàòðèöåéÒ.å.z1 = αi , z2 = αi3A,íà äåëå âñå âû÷èñëåíèÿ âåäóòñÿ ñ ìàòðèöåé ïî èçâåñòíîìóz1iíàõîäèì íîìåð ðàçðÿäà è äåëàåì âûâîä, ÷òî îøèáêà âí¼ì. Ïóñòü òåïåðü ïðîèçîøëî 2 îøèáêè: â ðàçðÿäàõiS = A(x + ei + ej ) =Äëÿ îïðåäåëåíèÿαièαjGF (4).j:αi + αjαi3 + αj3!òðåáóåòñÿ ðåøèòü ñèñòåìó àëãåáðàè÷åñêèõ óðàâíåíèéâèαi + αjαi3 + αj3= z1= z2(5)Ðåøåíèå àëãåáðàè÷åñêèõ óðàâíåíèé â êîíå÷íûõ ïîëÿõ íåïðîñòàÿ íàóêà.

 ñâÿçè ñ ýòèìâîçíèêàþò òðóäíîñòè ïðè ðàñïîçíàâàíèè îøèáîê ïðè áîëüøèõt. ñëó÷àå ñèñòåìû (5) ïîñòóïàåìñëåäóþùèì îáðàçîì:z2 = αi3 + αj3 = (αi + αj )(αi2 + αi αj + αj2 ) = z1 (z12 + αi αj ) ïðè ïåðåõîäàõ âîñïîëüçîâàëèñü òåì, ÷òîÒ.å.αi , αjGF (4)αi + αjαi αj ïîëå õàðàêòåðèñòèêè 2. Èìååì:= z1= z12 + z2 /z1(6) äâà ðàçëè÷íûõ êîðíÿ óðàâíåíèÿx2 + z1 x + (z12 + z2 /z1 ) = 0íàäGF (4).(7)Óðàâíåíèå (7) ðåøàåòñÿ ñòàíäàðòíûì ñïîñîáîì.Âûïèøåì îêîí÷àòåëüíûéàëãîðèòì:1. Âû÷èñëÿåì ñèíäðîìS = Ay =2. Åñëèz1 = z2 = 03. Åñëèz1 6= 0, z2 = z13 ⇒4. Åñëèz1 6= 0, z2 6= z13 ⇒z1.z2 äåëàåì âûâîä îá îòñóòñòâèè îøèáîê.ïðîèçîøëà îäíà îøèáêà â ðàçðÿäåíàõîäèìαi , αji,ãäåi : αi = z1 .

ðàçëè÷íûå êîðíè óðàâíåíèÿ (7), äåëàåì âûâîä, ÷òîîøèáêè ïðîèçîøëè â ðàçðÿäàõ ñ íîìåðàìèièj. ïðåäïîëîæåíèè, ÷òî áîëåå 2-õ îøèáîê ïðîèçîéòè íå ìîæåò, àëãîðèòì âñåãäà ñðàáàòûâàåò. Åñëèæå, äîïóñòèòü, ÷òî ïðîèçîøëî áîëüøåå êîëè÷åñòâî îøèáîê, òî äåéñòâóÿ ïî ýòîìó àëãîðèòìó, ìûëèáî íå ïîïàä¼ì íè â îäèí ïóíêò, ëèáî óáåäèìñÿ â îòñóòñòâèè êîðíåé óðàâíåíèÿ (7), ëèáî îáðàáîòàåì îäèí èç âàðèàíòîâ 2 4, íî ðåçóëüòàò íå áóäåò èìåòü íèêàêîãî îòíîøåíèÿ ê äåéñòâèòåëüíîïðîèçîøåäøèì îøèáêàì.35Ïðèâåä¼ì àëãîðèòì ïîñòðîåíèÿ ìàòðèöûHr×n òàêîéh1 6= 0.÷òî ëþáûå å¼íåçàâèñèìû. Äëÿ ýòîãî âûáåðåì ïåðâûé ñòîëáåöâèñèìûõ ñòîëáöîâ{h1 , ..., hi }Íài + 1-ì(d − 1)ñòîëáöîâ ëèíåéíîøàãå èìååìè âûáèðàåì ïðîèçâîëüíûé íåíóëåâîé ñòîëáåöhi+1iëèíåéíî íåçà-îòëè÷àþùèéñÿ îòëþáîé ëèíåéíîé êîìáèíàöèè (ïî ìîäóëþ 2) ðàíåå âûáðàííûõ ñòîëáöîâ.

ßñíî, ÷òî ââèäó ëèíåéíîéíåçàâèñèìîñòè{h1 , ..., hi }âñå ëèíåéíûå êîìáèíàöèè âèäàÏîýòîìó ìû ìîæåì âûáðàòühi+1hi1 + ...hip , p = 1, ..., d − 2ðàçëè÷íû.åñëè, è òîëüêî åñëèCi1 + ... + Cid−2 < 2r − 1Èç ýòèõ ðàññóæäåíèé ñëåäóåò ñëåäóþùàÿÒåîðåìà(Ãðàíèöà Âàðøàìîâà-Ãèëüáåðòà)Åñëè âûïîëíÿåòñÿ íåðàâåíñòâî0d −2121 + Cn−1+ Cn−1+ ... + Cn−1< 2r ,òî ñóùåñòâóåò V ëèíåéíûé [n, k, d]-êîä, äëÿ ïàðàìåòðîâ êîòîðîãî ñïðàâåäëèâî:k > n − r, d(V ) > d0 .ÏóñòüVnt êîä ñî ñëîâàìè äëèíûn, óñòîé÷èâûé ê t îøèáêàì (ñì. ïðåäûäóùóþ ëåêöèþ).

ÏóñòüM (n, t) = max|Vnt |tVnÐàíåå íàìè áûëà âûâåäåíà îöåíêà, íàçûâàåìàÿ ãðàíèöåé Õýìèíãà, êîòîðàÿ äà¼òlog2 M (n, t) 6 n − t log2 n + c.Åñëè æåV Á×Õ êîä ñ ïàðàìåòðàìè[n, k, d],òîlog2 |V | = k > n − tm = n − t log2 n + c0 .Ò.å. àññèìïòîòè÷åñêè ïînêîäû Á×Õ ÿâëÿþòñÿ ìàêñèìàëüíûìè ïî ìîùíîñòè.36×àñòü IIIÁóëåâû ôóíêöèè.Ëåêöèÿ 10.Ââåäåì íåñêîëüêî îïðåäåëåíèé. Ïóñòün. Xíóëåé è åäèíèö äëèííûf (x1 , . . . , xn ) ∈ B ôóíêöèÿ îòîáðàæàþùàÿÎïðåäåëåíèå.α2 , .

. . , αn ∈ BB = {0, 1}, B n ìíîæåñòâî âñåâîçìîæíûõ íàáîðîâ èç àëôàâèò ïåðåìåííûõ. Áóäåì ñ÷èòàòü åãî ñ÷åòíûì ìíîæåñòâîì.Ïåðåìåííàÿx1BnâB.íàçûâàåòñÿ ñóùåñòâåííîé äëÿ ôóíêöèèf,åñëè ñóùåñòâóþòòàêèå, ÷òîf (0, α2 , . . . , αn ) 6= f (1, α2 , . . . , αn ). ïðîòèâíîì ñëó÷àå ïåðåìåííàÿx1íàçûâàåòñÿ íåñóùåñòâåííîé.Ìû áóäåì ñ÷èòàòü ðàâíûìè äâå ôóíêöèè, åñëè îíè îòëè÷àþòñÿ òîëüêî íåñóùåñòâåííûìè ïå-f çàâèñèò îò ïåðåìåííûõ x1 , .