Диссертация (1103424), страница 16
Текст из файла (страница 16)
Äëÿ ñëîâà x ∈ {0, 1}d ÷åðåç xS áóäåì îáîçíài÷àòü ïðîåêöèþ ñëîâà x íà êîîðäèíàòû, âõîäÿùèå â Si . Èíûìè ñëîâàìè,åñëè x = x1 . . . xd , à Si = {j1 , . . . , jl }, ãäå j1 < · · · < jl , òî xS = xj1 . . . xjl .iÂòîðîé êëþ÷åâîé êîìïîíåíò êîíñòðóêöèè äåêîäèðóåìûå ñïèñêîì êîäû, èñïðàâëÿþùèå îøèáêè. Ìû áóäåì ãîâîðèòü î õýììèíãîâñêîì ðàññòîÿíèè ìåæäó ñëîâàìè:Îïðåäåëåíèå 5.4.
Ïóñòü ñëîâà v è v 0 ëåæàò â ìíîæåñòâå {0, 1}n . Òîãäàõýììèíãîâñêèì ðàññòîÿíèåì ìåæäó íèìè íàçûâàåòñÿ äîëÿ íåñîâïàäàþùèõ áèòîâ, ò.å. {i | vi 6= vi0 }/n. Åñëè õýììèíãîâñêîå ðàññòîÿíèå îò v äîv 0 íå áîëüøå (1 − α), òî ìû òàêæå áóäåì ãîâîðèòü, ÷òî êàæäîå èç ñëîâÿâëÿåòñÿ α-àïïðîêñèìàöèåé äðóãîãî.Íàì ïîòðåáóþòñÿ êîäû, ñóùåñòâîâàíèå êîòîðûõ óòâåðæäàåò ñëåäóþùàÿòåîðåìà:Òåîðåìà 5.5 ( [47]). Äëÿ ëþáîãî íàòóðàëüíîãî n > 0 è äåéñòâèòåëüíîãîδ > 0 ñóùåñòâóþò n̄ = poly(n/δ) è ôóíêöèÿ LDCn,δ : {0, 1}n → {0, 1}n̄ ,âû÷èñëèìàÿ çà ïîëèíîìèàëüíàÿ îò n/δ âðåìÿ, äëÿ êîòîðîé ñóùåñòâóåòàëãîðèòì äåêîäèðîâàíèÿ ñïèñêîì.
Ýòîò àëãîðèòì ðàáîòàåò ïîëèíîìèàëüíîå îò n/δ âðåìÿ è ïî ëþáîìó y ∈ {0, 1}n̄ âîçâðàùàåò ñïèñîê âñåõx ∈ {0, 1}n , òàêèõ ÷òî LDCn,δ (x) ÿâëÿåòñÿ 21 + δ -àïïðîêñèìàöèåé y .Èç òåîðåìû, â ÷àñòíîñòè, ìîæíî ñäåëàòü âûâîä, ÷òî äëÿ ëþáîãî y íàéä¼òñÿ íå áîëåå ïîëèíîìà îò n/δ ñëîâ x, òàêèõ ÷òî LDCn,δ (x) ÿâëÿåòñÿ ( 12 +δ)àïïðîêñèìàöèåé y . Çàìåòèì, ÷òî áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü,÷òî n̄ åñòü ñòåïåíü äâîéêè (â ñëó÷àå, åñëè ýòî íå òàê, äîïîëíèì âñå ñëîâàíóëÿìè).  äàëüíåéøåì áóäåì èñïîëüçîâàòü îáîçíà÷åíèå l = l(n) = log n̄.Òàêèì îáðàçîì, äëÿ êàæäîãî u ∈ {0, 1}n ñëîâî LDCn,δ (u) äëèíû 2l ìîæíî èíòåðïðåòèðîâàòü êàê òàáëèöó èñòèííîñòè íåêîòîðîé áóëåâîé ôóíêöèèû : {0, 1}l → {0, 1}.Îïðåäåëåíèå 5.6.
Ïóñòü ôèêñèðîâàíû ñëàáûé äèçàéí (S1 , . . . , Sm ) èêîä LDCn,δ , äåêîäèðóåìûé ñïèñêîì. Îïðåäåëèì ôóíêöèþ ÒðåâèñàíàTRδ : {0, 1}n × {0, 1}d → {0, 1}m ñëåäóþùèì ðàâåíñòâîì:TRδ (u, y) = û(y ) . . . û(y ).S179Sm ðàáîòå [49] ïîêàçàíî, ÷òî ôóíêöèÿ Òðåâèñàíà ÿâëÿåòñÿ ýêñòðàêòîðîì,íî ìû ýòèì ïîëüçîâàòüñÿ íå áóäåì, âìåñòî ýòîãî âîñïîëüçóåìñÿ îïðåäåëåíèåì íàïðÿìóþ.
Íà÷í¼ì ñ îïðåäåëåíèÿ çíà÷åíèé ïàðàìåòðîâ. ×èñëà n è kçàäàíû ôîðìóëèðîâêîé òåîðåìû. Çàòåì, ÷èñëà m, d, l è δ âûáèðàþòñÿ òàê,÷òîáû áûëè îäíîâðåìåííî âûïîëíåíû ñëåäóþùèå óñëîâèÿ:• m = k + d + 1;• δ=18m ;• l = log n̄, ãäå n̄ áåð¼òñÿ èç òåîðåìû 5.5;• d = O(l2 log m) áåð¼òñÿ èç òåîðåìû 5.3.Ìîæíî çàìåòèòü, ÷òî âûáîð d îäíîçíà÷íî çàäà¼ò âñå îñòàëüíûå ïàðàìåòðû:ïî k è d îïðåäåëÿåòñÿ m, çàòåì δ , çàòåì n̄ è l, è äëÿ êîððåêòíîñòè îñòà¼òñÿïðîâåðèòü òîëüêî ñóùåñòâîâàíèå ñëàáîãî äèçàéíà. Ïîñêîëüêó l = O(log n),òî ïðè âûáîðå ïîäõîäÿùåãî d = O(log3 n) â ïîñëåäíåì óðàâíåíèè ëåâàÿ÷àñòü ñòàíåò íå ìåíüøå ïðàâîé, ïîýòîìó ñëàáûé äèçàéí ñóùåñòâîâàòü áóäåò.Èìåííî äëÿ òàêîãî d ìû çàôèêñèðóåì âñå ïàðàìåòðû.×òîáû îïðåäåëèòü, êàê ïî a íàéòè p ñ èñïîëüçîâàíèåì ôóíêöèè TRδ ,íóæíà íåêîòîðàÿ ïîäãîòîâêà.
Îáîçíà÷èì ÷åðåç Lb ìíîæåñòâî âñåõ ñëîâ,èìåþùèõ óñëîâíóþ ñëîæíîñòü ñ îãðàíè÷åíèåì íà âðåìÿ t1 (n) ïðè èçâåñòíîì b ìåíüøå k :noLb = u ∈ {0, 1}n | Ct1 (n) (u|b) < k .Ïî óñëîâèþ a ∈ Lb . Êðîìå òîãî, ðàçìåð Lb ìåíüøå 2k . Çíà÷èò, îáðàç Lb ×{0, 1}d ïîä äåéñòâèåì ôóíêöèè TRδ ñîäåðæèò ìåíåå 2k+d ýëåìåíòîâ, ò.å.
âñèëó âûáîðà m = k + d + 1 çàíèìàåò ìåíåå 50% îáëàñòè çíà÷åíèé {0, 1}m .Âîñïîëüçóåìñÿ ýòèì ñëåäóþùèì îáðàçîì.Ïóñòü B : {0, 1}m → {0, 1} ïðåäèêàò, îçíà÷àþùèé ëåæàòü â îáðàçåLb × {0, 1}d ïîä äåéñòâèåì ôóíêöèè TRδ . Èíûìè ñëîâàìè, B(z) = 1, åñëèè òîëüêî åñëè z = TRδ (u, y) äëÿ íåêîðîãî u, òàêîãî ÷òî Ct1 (n) (u|b) < k ,è íåêîòîðîãî y ∈ {0, 1}d .
Èç âûøåèçëîæåííîãî ñëåäóåò, ÷òî äëÿ ëþáîãîu ∈ Lb âåðíî íåðàâåíñòâî1Pry∈{0,1}d [B(TRδ (u, y)) = 1] − Prr1 ,...,rm ∈{0,1} [B(r1 . . . rm ) − 1] > .280(5.1)Äåéñòâèòåëüíî, ïåðâàÿ âåðîÿòíîñòü ðàâíà 1 ïî îïðåäåëåíèþ B , à âòîðàÿìåíüøå 12 â ñèëó âûáîðà ïàðàìåòðîâ. Ïåðåïèøåì íåðàâåíñòâî (5.1) ÷åðåçîïðåäåëåíèå ôóíêöèè Òðåâèñàíà:h i Pry∈{0,1}d B û y. .
. û y=1 −S1Sm1− Prr1 ,...,rm ∈{0,1} [B(r1 . . . rm ) − 1] > . (5.2)2Äàëåå, ïðèìåíèì èçâåñòíûé ïðè¼ì ãèáðèäèçàöèè: áóäåì ïî î÷åðåäè çà ìåíÿòü âñå û y S íà ri . Òàêèì îáðàçîì, ëåâóþ ÷àñòü íåðàâåíñòâà (5.2)iìîæíî ïðåäñòàâèòü â âèäå ñóììûm Xh Pry∈{0,1}d ,ri+1 ,...,rm ∈{0,1} B û y S . . . û y S1i−1i û y S ri+1 . . . rm = 1 −ii=1h i − Pry∈{0,1}d ,ri ,ri+1 ,...,rm ∈{0,1} B û y S1 . . .
û y Si−1 ri ri+1 . . . rm = 1 .(5.3)Ïîñêîëüêó ýòî âûðàæåíèå ÿâëÿåòñÿ ñóììîé m ñëàãàåìûõ è ïðè ýòîì ïðå1âûøàåò 12 , òî õîòÿ áû îäíî ñëàãàåìîå ïðåâûøàåò 2m. Ïîëó÷àåì, ÷òî äëÿíåêîòîðîãî i ∈ [1, m] âåðíîh i Pry∈{0,1}d ,ri+1 ,...,rm ∈{0,1} B û y S1 . . . û y Si−1 û y Si ri+1 . . . rm = 1 −h i 1− Pry∈{0,1}d ,r ,r ,...,r ∈{0,1} B û y. . . û yri ri+1 . . . rm = 1 >ii+1mS1Si−12m(5.4)Áîëåå òîãî, áèòû y âíå Si ìîæíî ôèêñèðîâàòü íåêîòîðûì îáðàçîì, òàê ÷òîáû íåðàâåíñòâî (5.4) îñòàëîñü âåðíûì. Îáîçíà÷èì ñëîâî y S ÷åðåç x.
Òîãäà iïðè ôèêñèðîâàííûõ áèòàõ âíå x êàæäàÿ ôóíêöèÿ û y S áóäåò çàâèñåòüjòîëüêî îò |Si ∩ Sj | áèòîâ, ëåæàùèõ â x. Îáîçíà÷èì ýòó ôóíêöèþ ÷åðåç fj .Òàêèì îáðàçîì, äëÿ êàæäîãî j ñëîâî u çàäà¼ò áóëåâó ôóíêöèþfj : {0, 1}|Si ∩Sj | → {0, 1}.  äàëüíåéøåì ìû äëÿ ïðîñòîòû áóäåì çàïèñûâàòü û y S êàê fj (x), õîjòÿ ñóùåñòâåííûì îáðàçîì fj çàâèñèò òîëüêî îò |Si ∩ Sj | áèòîâ x. Òàêèì îáðàçîì, òàáëèöà èñòèííîñòè äëÿ òàêîé ôóíêöèè çàíèìàåò 2|Si ∩Sj | áèòîâ, à ñîâîêóïíîñòü òàáëèö èñòèííîñòè äëÿ ôóíêöèé f1 , . . . , fi−1 çàíèìàåò81Pi−1j=1 2|Si ∩Sj |áèòîâ. Ïî îïðåäåëåíèþ ñëàáîãî äèçàéíà ýòî ÷èñëî íå áîëüøåm.Òåïåðü ìîæíî îïðåäåëèòü ñëîâî p äëÿ äàííîãî a.
Ýòî áóäåò ñîâîêóïíîñòü òàáëèö èñòèííîñòè äëÿ ôóíêöèé f1 , . . . , fi−1 , ïîñòðîåííûõ ïî u = a.Íåòðóäíî ïðîâåðèòü äâà èç òð¼õ óñëîâèé òåîðåìû. Âî-ïåðâûõ, äëèíà pìåíüøå m, ò.å. íå áîëüøå k + d, ò.å. íå áîëüøå k + O(log3 n), ÷òî è òðåáîâàëîñü. Âî-âòîðûõ, äëÿ çàäàíèÿ p ïðè èçâåñòíîì a íåîáõîäèìî ñïåöèôèöèðîâàòü k è d (êîòîðûå çàäàäóò âñå îñòàëüíûå ïàðàìåòðû, ïðè ýòîì nóæå èçâåñòíî êàê äëèíà a), èíäåêñ i è áèòû y âíå x, ïðè êîòîðûõ èñòèííîíåðàâåíñòâî 5.4. Ïîñêîëüêó i 6 m, à |y| = d = O(log3 n), âñ¼ ýòî çàéì¼òíå áîëüøå O(log3 n) áèòîâ. Ïðè ýòîì âðåìÿ ïîñòðîåíèÿ p áóäåò ïîëèíîìèàëüíûì.
Äåéñòâèòåëüíî, ïî d, k è n ìîæíî ïîñ÷èòàòü m, δ è l. Çàòåìçà ïîëèíîìèàëüíîå îò n âðåìÿ ñòðîÿòñÿ ñëàáûé äèçàéí {S1 , . . . , Sm } è êîäâ. Íàêîíåö, ñîãëàñíî ïåðåäàííîé èíôîðìàöèè ôèêñèðóþòñÿ áèòû âíå Si .Ïîñëå ýòîãî p ïîëó÷àåòñÿ ïåðåïèñûâàíèåì íåîáõîäèìûõ áèòîâ â. Òàêèìîáðàçîì, óòâåðæäåíèå Cpoly(n) (p|a) < O(log3 n) äîêàçàíî.Çàìåòèì òàêæå, ÷òî ïðè èçâåñòíûõ ïàðàìåòðàõ n, k , d è i ïî ñëîâó p ìîæíî âîññòàíîâèòü âñå òàáëèöû èñòèííîñòè ôóíêöèé f1 , . . . , fi−1 , íåñìîòðÿ íàîòñóòñòâèå ðàçäåëèòåëåé. Äåéñòâèòåëüíî, ïî ïàðàìåòðàì n, k è d ìîæíîâîññòàíîâèòü äèçàéí {S1 , .
. . , Sm }, è ïðè èçâåñòíîì i âû÷èñëèòü ðàçìåðû|Si ∩ Sj | äëÿ âñåõ j = 1, . . . , i − 1. Ïîñëå ýòîãî ñëîâî p ìîæíî ðàçáèòü íàáëîêè äëèíû 2|Si ∩Sj | , êîòîðûå çàäàäóò òàáëèöû ôóíêöèé fj . ñëåäóþùåì ðàçäåëå ìû äîêàæåì, ÷òî ïðè èçâåñòíûõ p è b äîñòàòî÷íîíåáîëüøîé äîïîëíèòåëüíîé èíôîðìàöèè äëÿ âîññòàíîâëåíèÿ a ïîëèíîìèàëüíûì àëãîðèòìîì èç êëàññà AM.5.3Äîêàçàòåëüñòâî êîððåêòíîñòè êîíñòðóêöèè ýòîì ðàçäåëå ìû äîêàæåì, ÷òî äëÿ ñëîâà p, ïîñòðîåíèå êîòîðîãî îïèñàíî â ðàçäåëå 5.2, è íåêîòîðîãî ïîëèíîìà t2 (·) äåéñòâèòåëüíî âûïîëíåíîñîîòíîøåíèå CAMt2 (n) (a|b, p) = O(log3 n).
Íà÷í¼ì ñ ïðåîáðàçîâàíèÿ íåðàâåíñòâà (5.4) ê áîëåå óäîáíîìó âèäó. Âíà÷àëå ïåðåïèøåì åãî â íîâûõ îáî-82çíà÷åíèÿõ.Prx∈{0,1}l ,ri+1 ,...,rm ∈{0,1} [B (f1 (x) . . . fi−1 (x)û(x)ri+1 . . . rm ) = 1] −− Prx∈{0,1}l ,ri ,ri+1 ,...,rm ∈{0,1} [B (f1 (x) . . . fi−1 (x)ri ri+1 . . . rm ) = 1] >1(5.5)2mÇàìåòèì, ÷òî îíî ñîîòâåòñòâóåò íåðàâåíñòâó (2.3) äëÿ z = (x, ri+1 , . . . , rm ),σ = ri , f (z) = f1 (x) . .
. fi−1 (x)ri+1 . . . rm , g(z) = û(x), T (a1 . . . am−1 , r) =B(a1 . . . ai−1 rai . . . am−1 ). Çíà÷èò, òåîðåìà 2.38 âûïîëíåíî äëÿ Gri (z) =T (z, ri ) ⊕ ri ⊕ 1, ò.å. äëÿ(ri ,åñëè B(f1 (x) . . . fi−1 (x)ri ri+1 . . . rm ) = 1;Gri (x, ri+1 . . . rm ) =1 − ri , èíà÷å.Òàêèì îáðàçîì, ïðèìåíÿÿ íåðàâåíñòâî (2.4), âûâîäèìPrx,ri ri+1 ...rm [Gri (x, ri+1 . . . rm ) = û(x)] >11+.2 2m(5.6)Äàëåå, ìîæíî çàôèêñèðîâàòü áèò ri , òàê ÷òîáû íåðàâåíñòâî (5.6) îñòàëîñüâåðíûì. Ñîîòâåòñòâóþùèé áèò âêëþ÷àåòñÿ â îïèñàíèå a ïðè èçâåñòíûõ b èp.  äàëüíåéøåì áåç îãðàíè÷åíèÿ îáùíîñòè ìû áóäåì ñ÷èòàòü, ÷òî ri = 1.Ââåä¼ì îáëåã÷¼ííîå îáîçíà÷åíèå:(1, åñëè B(f1 (x) . .
. fi−1 (x)1ri+1 . . . rm ) = 1;G(x, r) = G(x, ri+1 . . . rm ) =0, èíà÷å.Ïåðåïèøåì íåðàâåíñòâî (5.6):11+.(5.7)2 2mÍà ýòîì ýòàïå íàêîíåö ìîæíî îïèñàòü îñíîâíóþ èäåþ âîññòàíîâëåíèÿa ïî èçâåñòíûì b è p. Çíàÿ b, ìîæíî âû÷èñëÿòü ïðåäèêàò B íà ëþáîì çàäàííîì àðãóìåíòå. Çíàÿ p, ìîæíî âû÷èñëÿòü âñå fi (x), è òàêèì îáðàçîìâû÷èñëÿòü f (z). Íàêîíåö, åñëè ïîìèìî b è p èçâåñòíî ri , òî ìîæíî âû÷èñëÿòü G(x, r). Ïðè óäà÷íîì âûáîðå ri+1 . . . rm ñòðîêà ũ = G(·, ri+1 . . . rm )ñîâïàä¼ò ñ û áîëåå ÷åì íà äîëå 21 +δ îò âñåõ x. Ïîñëå ýòîãî ìû ïðèìåíèì ê ũàëãîðèòì äåêîäèðîâàíèÿ ñïèñêîì è ñðåäè ïðåäëîæåííûõ âàðèàíòîâ íàéä¼ìa. Ê ñîæàëåíèþ, ýòîò ïëàí â ÷èñòîì âèäå íå ñðàáîòàåò èç-çà îãðàíè÷åíèéïî âðåìåíè: äëÿ âû÷èñëåíèÿ ïðåäèêàòà B íóæíî, ïî âñåé âèäèìîñòè, ñâåðõïîëèíîìèàëüíîå âðåìÿ, ïîñêîëüêó òðåáóåòñÿ âû÷èñëèòü ñëîæíîñòü Cpoly , àPrx,ri+1 ...rm [û(x) = G(x, ri+1 . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
