А.Б. Угольников - Лекции по дискретной математике (1083729), страница 4
Текст из файла (страница 4)
(Ôåðìà äëÿ êîíå÷íûõ ïîëåé) ∀m > 1 ∃P = P (m) òàêîå, ÷òî äëÿ ëþáîãî ïðîñòîãîp > P ñóùåñòâóåò ðåøåíèå óðàâíåíèÿ xm + y m = z m (mod p).19Äîêàçàòåëüñòâî.p, Zp = {0, . . . , p − 1}.  ãðóïïå{1, . . . , p − 1} = {g 1 , g 2 , . . . , g p−1 }. Ò.å. åñëè x ∈ Zp \{0},ßñíî, ÷òî lx ìîæíî ïðåäñòàâèòü â âèäå lx = ix + mjx åäèíñòâåííûìðàñêðàñêó ÷èñåë èç Zp \{0}.Ðàññìîòðèì êîëüöî âû÷åòîâ ïî ìîäóëþZp \{0} åñòü ïåðâîîáðàçíûélòî x = g x , 1 6 lx 6 p − 1.îáðàçîì. Óñòðàèâàåìêîðåíüg,ò.å.φ : Zp \{0} −→ {c1 , . . .
, cm }φ(x) = ci ⇐⇒ ix = i − 1Ïî òåîðåìå Øóðà äëÿ ëþáîãîm ñóùåñòâóåò òàêîå R = R(m), ÷òî äëÿ âñåõ p > R + 1x + y = z, ò.å. ñóùåñòâóþò òàêèå ix , jx , iy , jy , iz , jz , ÷òîîäíîöâåòíîå ðåøåíèå óðàâíåíèÿg ix +mjx + g iy +mjy = g iz +mjz .Íî ïîñêîëüêó ðåøåíèå îäíîöâåòíîå, òîix = iy = iz ,è âûïîëíåíî ðàâåíñòâîg i+mjx + g i+mjy = g i+mjz .Óìíîæàÿ íàg −iïîëó÷àåì(g jx )m + (g jy )m = (g jz )m .×òî è òðåáîâàëîñü äîêàçàòü.20ñóùåñòâóåò×àñòü IIÊîäèðîâàíèå.Ëåêöèÿ 6Òåîðèÿ êîäèðîâàíèÿÏóñòüA êîíå÷íûé àëôàâèò:ïðîèçâîëüíîãî àëôàâèòàKA = {a1 , ..., am }, m > 2. B äâîè÷íûé àëôàâèò:B = {0, 1}.Äëÿîïðåäåëèì ìíîæåñòâî ñëîâ êîíå÷íîé äëèíû:K∗ =[Kn ∪ {Λ}, ãäån>1Kn = {α|α = ki1 ...kin , kij ∈ K},ΛÏîëîæèìλ(α)ïóñòîå ñëîâî, îáëàäàþùåå ñâîéñòâîì: äëèíà ñëîâàα,òàê äëÿ ëþáîãîΛα = αΛ = α ∀α.α ∈ Kn λ(α) = n. òåîðèè êîäèðîâàíèÿ ðàññìàòðèâàåòñÿ çàäà÷à ïîñòðîåíèÿ îòîáðàæåíèÿF : A∗ → B ∗îáëàäàþùåãî îïðåäåë¼ííûìè ñâîéñòâàìè.
Îñíîâíîé ïðàêòè÷åñêèé èíòåðåñ ïðåäñòàâëÿþò ñëåäóþùèå ñâîéñòâà îòîáðàæåíèÿF:1. Âçàèìíîîäíîçíà÷íîñòü ñîîáùåíèå æåëàòåëüíî óìåòü íå òîëüêî çàêîäèðîâàòü, íîè ðàñêîäèðîâàòü.2. Ñæàòèå äëèíà ñîîáùåíèÿ â àëôàâèòåBäîëæíà áûòü ïî âîçìîæíîñòè êîðîòêîé.3. Óñòîé÷èâîñòü ê ïîìåõàì ýòî òàê íàçûâàåìûåêîäû èñïðàâëÿþùèå îøèáêè,î íèõïîéä¼ò ðå÷ü â ñëåäóþùèõ ëåêöèÿõ.4. Øèôðîâàíèå â öåëÿõ êîíôèäåíöèàëüíîñòè ïåðåäà÷è èíôîðìàöèè èñïîëüçóþòñÿñïåöèàëüíûå êðèïòîãðàôè÷åñêèå êîäû.  ýòîì êóðñå ëåêöèé ìû íå áóäåì èõ ðàññìàòðèâàòü.Ðàññìîòðèì ïðîñòåéøåå ïîáóêâåííîå êîäèðîâàíèå.
Îíî ñòðîèòñÿ ñëåäóþùèì îáðàçîì: ñíà÷àëàîïðåäåëÿåòñÿ îòîáðàæåíèåψ : A → B∗ψai → vi ∈ B ∗çàòåì äëÿ ïðîèçâîëüíîãî ñëîâàα = ai1 ...aik ∈ A∗ïîëàãàþò:F (α) = β = ψ(ai1 )...ψ(aik ) = vi1 ...vik ∈ B ∗ .Ïóñòîå ñëîâî èç ðàññìîòðåíèÿ èñêëþ÷àåòñÿ. ÌíîæåñòâîîòîáðàæåíèåìFíàçûâàåòñÿ êîäîì.{v1 , ..., vm }îáîçíà÷àåòñÿVè íàðàâíå ñÊîä íàçûâàåòñÿ ðàçäåëèìûì, åñëè èç ðàâåíñòâà vi1 vi2 ...vik = vj1 vj2 ...vjl ñëåäóåò k = l è i1 =j1 , i2 = j2 , ..., ik = jk . ßñíî, ÷òî åñëè êîä ðàçäåëèìûé, òî êîäèðîâàíèå âçàèìíîîäíîçíà÷íî.∗Ââåä¼ì åù¼ îäíî âàæíîå îïðåäåëåíèå.
Äëÿ äâóõ ñëîâ α, β ∈ B α íàçûâàåòñÿ ïðåôèêñîì β , åñëè00∗β = αα äëÿ íåêîòîðîãî α ∈ B . Êîä íàçûâàåòñÿ ïðåôèêñíûì, åñëè äëÿ ëþáûõ i, j : i 6= j vi íåÿâëÿåòñÿ ïðåôèêñîì vj . Íåòðóäíî ïîíÿòü, ÷òî åñëè êîä ïðåôèêñíûé, òî îí ðàçäåëèìûé.Òåîðåìà (Íåðàâåíñòâî Êðàôòà-Ìàêíèëëàíà). Ïóñòü V = {v1 , .., vm }, m > 2 ðàçäåëèìûé êîä.ÒîãäàmX2−λ(vi ) 6 1.(1)i=121Äîêàçàòåëüñòâî.Äëÿ ïðîèçâîëüíîãîn∈NîïðåäåëèìW = F (Ak ) = {w ∈ B ∗ |w = vi1 ...vin , 1 6 i1 , ..., in 6 m}Wk = {w ∈ W |λ(w) = k}Ïóñòüλmax = max λ(vi ).vi ∈V1)W=nλFmaxWk ,Ðàññìîòðèì íåêîòîðûå î÷åâèäíûå ñâîéñòâà ýòèõ ìíîæåñòâ:ãäå îáúåäèíåíèå ÿâëÿåòñÿ îáúåäèíåíèåì íåïåðåñåêàþùèõñÿ ìíîæåñòâ (äèçú-k=1þíêòíûì).3)vi1 ...vin 6= vj1 ...vjn ïðè (i1 , ..., in ) 6= (j1 , .., jn )nλPmax|W | =W k = mn .4)|Wk | 6 2k .2) â ñèëó ðàçäåëèìîñòè êîäàV.k=1Ââåä¼ì â ðàññìîòðåíèå äâå ôóíêöèè ïîëîæèòåëüíîãî àðãóìåíòàhv (x) =mXx:x−λ(vi ) ,i=1hw (x) =Xx−λ(w) .w∈WÇàìåòèì, ÷òî â ñèëó ñâîéñòâà 2)XXx−λ(w) =w∈Wx−λ(vi1 ...vin ) ,(i1 ,...,in )ãäå ñóììèðîâàíèå âåä¼òñÿ ïî âñåì âîçìîæíûì èíäåêñàìX(i1 ,...,in )Xx−λ(vi1 ...vin ) =(i1 , ..., in ).Äàëååx−(λ(vi1 )+...λ(vin )) = x−λ(v1 ) + ...
+ x−λ(vm )n= (hv (x))n .(i1 ,...,in )Îòêóäàhv (x) = (hw (x))1/n . ñèëó ñâîéñòâ 1) è 4) èìååì:hw (x) =nλmaxX−k|Wk |x6hv (2) 6 (nλmax )1/n .2k x−k .k=1k=1ÏîýòîìónλmaxXÏîñòðîåíèÿ âåðíû äëÿ ëþáîãîâåðíûì, åñëè ïåðåéòè ê ïðåäåëó ïðèn → ∞.n,ïîýòîìó íåðàâåíñòâî îñòàíåòñÿÏîëó÷èì:hv (2) 6 1.×òî è òðåáîâàëîñü äîêàçàòü.Âîçìîæíî ëè äëÿ äàííîãî íàáîðà äëèíλ(vi ),óäîâëåòâîðÿþùèõ íåðàâåíñòâó (1), ïîñòðîèòüðàçäåëèìûé êîä? Îòâåò äà¼ò ñëåäóþùååÓòâåðæäåíèå.
Äëÿ äàííîãî íàáîðà ÷èñåë l1 , ..., lm ∈ N, m > 2, óäîâëåòâîðÿþùèõ íåðàâåíñòâó:mX2−li 6 1,i=122(2)âñåãäà ñóùåñòâóåò ïðåôèêñíûé êîä V = {v1 , ..., vm }, òàêîé ÷òî λ(vi ) = li ,i = 1, ..., m.sÄîêàçàòåëüñòâî. Ïóñòü ñðåäè íàáîðà ÷èñåë {li }mi=1 èìååòñÿ ðîâíî s ðàçëè÷íûõ: {tj }j=1 , ïðè÷¼ì1 6 t1 6 ... 6 ts .Ïóñòüvjtj êîëè÷åñòâî ÷èñåë ðàâíûõñðåäè ÷èñåësX{li }mi=1 .Íåðàâåíñòâî (2) ïåðåïèøåòñÿ â âèäå:vj 2−tj 6 1.(3)j=1Îòêóäà, â ÷àñòíîñòè, ñëåäóåò, ÷òîv1 6 2t1 .Ïîýòîìó íàéä¼òñÿv1ðàçëè÷íûõ ñëîâ äëèíût1 .Èç (3) òàêæå ñëåäóåò, ÷òîv1 2−t1 + v2 2−t2 6 1 ⇒v2 6 2t2 − v1 2(t2 −t1 ) .Ýòî îçíà÷àåò, ÷òî íàéä¼òñÿv2t2 ,ñëîâ äëèíût1 íåv1 ñëîâ äëèíû t1 ,âûáðàòü vr+1 ñëîâ äëèíûòàêèõ ÷òî âûáðàííûå äî ýòîãîv1ñëîâ äëèíûáóäóò ÿâëÿòüñÿ èõ ïðåôèêñàìè. Ðàññóæäàåì àíàëîãè÷íî.
Ïóñòü ìû óæå âûáðàëèv2 äëèíû t2 è òàê äàëåå vr äëèíû tr (r < s). Ïîêàæåì, ÷òî ìû ìîæåìtr+1 òàê, ÷òî íèêàêèå èç ðàíåå âûáðàííûõ íå áóäóò ÿâëÿòüñÿ ïðåôèêñàìèíîâûõ. Äåéñòâèòåëüíîèç (3) ñëåäóåò, ÷òîr+1Xvj 2−tj 6 1. ⇒j=1tr+1vr+1 6 2− v1 2tr+1 −t1 − ... − vr 2tr+1 −tr ,à ýòî è îçíà÷àåò òðåáóåìîå óñëîâèå. Òàêèì îáðàçîì ìû è ïîñòðîèì âåñü èñêîìûé ïðåôèêñíûé êîä.Óòâåðæäåíèå äîêàçàíî.Äëÿ ïðîèçâîëüíîãî êîäàV = {v1 , ..., vm }ââåä¼ì äâå õàðàêòåðèñòèêè:L=mXλ(vi )i=1èM ìàêñèìàëüíîå ÷èñëî êîäîâûõ ñëîâ, êîòîðîå ìîæíî ïîäðÿä ïîìåñòèòü âíóòðè äðóãèõ êîäîâûõvj îïðåäåëÿåòñÿ kjvj = αvi1 ...vik β, M = max kj .ñëîâ: äëÿ ïðîèçâîëüíîãî÷òî íàèáîëüøååk, òàêîå ÷òî ñóùåñòâóþò vi1 , ..., vik , òàêèåjÓòâåðæäåíèå. Ïóñòü V êîä, íå ÿâëÿþùèéñÿ ðàçäåëèìûì. α ñëîâî ìèíèìàëüíîé äëèíûèç B ∗ , äîïóñêàþùåå äâîÿêîå òîëêîâàíèå.
Òîãäàλ(α) 6 λmaxÄîêàçàòåëüñòâî.Ñëîâîα(L − m + 1)(M + 1).2ðàçáèâàåòñÿ äâóìÿ ñïîñîáàìè íà ýëåìåíòàðíûå ñëîâà êîäàâ¼ì èõ âåðõíåå è íèæíåå ðàçáèåíèÿ. Íàíåñ¼ì èõ îäíîâðåìåííî íà ñëîâîíåêîòîðîå ñóìàðíîå ðàçáèåíèå íà ñëîâàβi .α.V.Íàçî- ðåçóëüòàòå ïîëó÷èìÏðè÷¼ì, â ñèëó ìèíèìàëüíîñòè ñëîâàα,ïåðâàÿ òî÷êàñóìàðíîãî ðàçáèåíèÿ ïðèíàäëåæàùàÿ ñðàçó äâóì ðàçáèåíèÿì (âåðõíåìó è íèæíåìó) áóäåò êîíöîìñëîâàα.  ñóìàðíîì ðàçáèåíèè âñå ñëîâà äåëÿòñÿ íà äâà êëàññà òå, êîòîðûå ÿâëÿþòñÿ ýëåìåíòàð-íûìè êîäàìè, è îñòàëüíûå. Ïîêàæåì, ÷òî âñå ñëîâà èç âòîðîãî êëàññà ðàçëè÷íû. Åñëè ñóùåñòâóþòβ1 = β2 = β ñëîâà èç âòîðîãî êëàññà òàêèå, ÷òîα = β 0 β1 β 00 β2 β 000 ,23äëÿ íåêîòîðûõβ 0 , β 00 , β 000 ,òî ðàññìîòðèì ñëîâîβ 0 ββ 000 .Óòâåðæäàåòñÿ, ÷òî îíî èìååò ïî êðàéíåé ìåðå 2 ðàçëè÷íûõ ðàñøèôðîâêè. Äåéñòâèòåëüíî, âîçìîæ-α):β â îáîèõ ïîçèöèÿõ ÿâëÿåòñÿ êîíöîì ýëåìåíòàðíîãî ñëîâà ïðè ïåðâîé ðàñøèôðîâêå è íà÷àëîì0000ýëåìåíòàðíîãî ñëîâà ïðè âòîðîé.
Òîãäà ñëîâî β ββïî ïåðâîìó ñïîñîáó ðàñøèôðîâûâàåòñÿ êàê00000β β + β (îòäåëüíî ðàñøèôðîâûâàåòñÿ β β , îòäåëüíî β 000 , à ïîòîì ïðèïèñûâàþòñÿ äðóã ê äðóãó),0000ïî âòîðîìó β + ββ . ßñíî, ÷òî ýòè ñïîñîáû ðàçíûå.2) β â ïåðâîì ñëó÷àå ÿâëÿåòñÿ êîíöîì ñëîâà ïðè ïåðâîé ðàñøèôðîâêå è íà÷àëîì ïðè âòîðîé, à0000âî âòîðîì ÿâëÿåòñÿ íà÷àëîì ñëîâà ïðè ïåðâîì ñïîñîáå è êîíöîì ïðè âòîðîì.  ýòîì ñëó÷àå β ββ00000ðàñøèôðîâûâàåòñÿ êàê β β ïî ïåðâîìó ñïîñîáó "+" βïî âòîðîìó, à òàêæå β ïî âòîðîìó "+"ββ 000 ïî ïåðâîìó ñíîâà äâå ðàçëè÷íûå ðàñøèôðîâêè.0000Íî äëèíà ñëîâà β ββñòðîãî ìåíüøå äëèíû ñëîâà α ïðèõîäèì ê ïðîòèâîðå÷èþ ñ âûáîðîì α.Ïóñòü g ÷èñëî êîëè÷åñòâî ñëîâ âòîðîãî ðîäà. ßñíî, ÷òî g íå ïðåâîñõîäèò ÷èñëî âñåâîçìîæíûõïðåôèêñîâ ýëåìåíòàðíûõ ñëîâ èç V, ò.å.íû äâå ñèòóàöèè (äðóãèå ñèòóàöèè íåâîçìîæíû, â ñèëó ìèíèìàëüíîñòè äëèíû1)g 6 (λ(v1 ) − 1) + (λ(v2 ) − 1) + ...
+ (λ(vm ) − 1) = L − m.Ìåæäó äâóìÿ ïîñëåäîâàòåëüíûìè ñëîâàìè âòîðîãî ðîäà íå ìîæåò áûòü áîëüøåMñëîâ ïåðâîãîðîäà, ðîâíî êàê è îò íà÷àëà ñëîâà äî ïåðâîãî ñëîâà âòîðîãî ðîäà è îò êîíöà ïîñëåäíåãî ñëîâàâòîðîãî ðîäà äî êîíöà ñëîâàα âñå ýòè ó÷àñòêè (íàçîâ¼ì èõ îñíîâíûìè) ÿâëÿþòñÿ âëîæåííûìèäëÿ êàêîãî ëèáî êîäîâîãî ñëîâà, ëèáî ïî ïåðâîìó ðàçáèåíèþ, ëèáî ïî âòîðîìó. Òàêèõ ó÷àñòêîâ âñåãîíå áîëåå ÷åìL − m + 1.Êàæäîìó îñíîâíîìó ó÷àñòêó ñîîòâåòñòâóåò íå áîëåå ÷åìðàçáèåíèÿ è ðîâíî 1 èç äðóãîãî.
Ïîýòîìó ñóìàðíî â äâóõ ðàçáèåíèÿõ íå áîëåå ÷åìM ñëîâ èç îäíîãî(L−m+1)(M +1)ñëîâ. Ò.å.2λ(α) 6 λmax (L − m + 1)(M + 1) ⇒λ(α) 6 λmax(L − m + 1)(M + 1)2Òåîðåìà äîêàçàíà.Èç ýòîãî âàæíîãî óòâåðæäåíèÿ ñëåäóåò ñïîñîá ïðîâåðêè êîäà íà ðàçäåëèìîñòü: äîñòàòî÷íî ïðîâåðèòü íà îäíîçíà÷íóþ ðàñøèôðîâêó âñå ñëîâà äëèíîé íå âûøå24λmax(L − m + 1)(M + 1).2Ëåêöèÿ 7.C ⊆ B∗.−→Cìíîæåñòâî ïðåôèêñîâ ñëîâ èç C .
Ðàçäåëèìûé êîä V íàçû−−→(V ∗ ) = B ∗ .Óòâåðæäåíèå.Ðàçäåëèìûé êîä V ÿâëÿåòñÿ ïîëíûì òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãîβ ∈ B ∗ , òàêîãî ÷òî λ(β) > λmax , ñóùåñòâóåò vi ∈ V òàêîå, ÷òî β = vi γ, äëÿ íåêîòîðîãî γ ∈ B ∗ ,ãäå λmax = max λ(v).ÏóñòüÁóäåì îáîçíà÷àòüâàåòñÿ ïîëíûì, åñëèv∈VÄîêàçàòåëüñòâî.
Íåîáõîäèìîñòü.áîëüøå äëèíû ëþáîãî ñëîâà èçvi1 vi2 ...vik .V.Âîçüì¼ì ïðîèçâîëüíîå ñëîâîβ,äëèíà êîòîðîãî ñòðîãîÏî îïðåäåëåíèþ îíî ÿâëÿåòñÿ ïðåôèêñîì íåêîòîðîãî ñëîâàÍî åãî äëèíà áîëüøå ÷åì äëèíàvi1 ,çíà÷èò íåîáõîäèìîå ïðåäñòàâëåíèå èìååò ìåñòî.−−→β ∈ B∗, β ∈/ (V ∗ ). Âûáåðåì β òàê, ÷òîáû0λ(β) áûëî íàèìåíüøèì. Ïóñòü v ∈ V òàêîå, ÷òî λ(v) = λmax . Ïóñòü β = βv, òîãäà β 0 ∈ B ∗ , λ(β 0 ) >−−→λmax , çíà÷èò, ïî óñëîâèþ ∃vi ∈ V òàêîå, ÷òî β 0 = vi γ èëè βv = vi γ . Ïî ïðåäïîëîæåíèþ β ∈/ (V ∗ ),−−→∗ñëåäîâàòåëüíî, β íå ÿâëÿåòñÿ ïðåôèêñîì vi . Çíà÷èò, vi ïðåôèêñ β : β = vi γ .
Åñëè γ ∈ (V ), òî,−−→−−→∗∗î÷åâèäíî, è β ∈ (V ), çíà÷èò γ 6∈ (V ), íî λ(γ) < λ(β) ïðîòèâîðå÷èå ñ ìèíèìàëüíîñòüþ äëèíû β .Òåîðåìà. (Êðèòåðèé ïîëíîòû ðàçäåëèìîãî êîäà) Ðàçäåëèìûé êîä V = {v1 , . . . , vm } ÿâëÿåòñÿïîëíûì òîãäà è òîëüêî òîãäà, êîãäà êîä V ÿâëÿåòñÿ ïðåôèêñíûì è âûïîëíåíî ðàâåíñòâîÄîñòàòî÷íîñòü. Ïóñòü êîä Víåïîëíûé, ò.å. ñóùåñòâóåòmX2−λ(vi ) = 1.(1)i=1Äîêàçàòåëüñòâî.Ïóñòü V ðàçäåëèìûé ïîëíûé êîä. Âûáåðåì ïðîèçâîëüíîå n > λmax . ÐàñB n = {β1 , ..., β2n } ìíîæåñòâî âñåõ ñëîâ èç B ∗ äëèíû n, à òàêæå ìíîæåñòâàVi = {β ∈ B ∗ |λ(β) = n, β = vi γ}, i = 1, ..., m.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
