11.pdf

(126 KB) Pobierz
302997667 UNPDF
ALGORYTMEUKLIDESAROZSZERZONY
NWD(a,b)(=gcd(a,b))
Mo»nazało»y¢,»eab.
Inicjacja
r −1 a, r 0 b
s −1 1,s 0 0
t −1 0, t 0 1
Wniosek.r j =s j a+t j b, j=−1,0.
Iteracje:untilr n+1 =0do
q i br i−2 /r i−1 c;
r i r i−2 −q i r i−1 ;
s i s i−2 −q i s i−1 ;
t i t i−2 −q i t i−1 ;
Output:NWD(a,b)=r n [=s n a+t n b,
poniewa»–cołatwoudowodni¢–
Wniosekzachodzidlawszystkichj=−1,0,...]
Uwaga1.NWDjestwi¦costatni¡reszt¡niezerow¡r n .
Strzałki s¡defactorówno±ciami.
Uwaga2.Drugarówno±¢wpowy»szychiteracjach,zapisanajako
r i−2 =q i r i−1 +r i ,gdzier i <r i−1 (zrówno±cipoprzedzaj¡cej),
nazywasi¦reguł¡dzieleniazreszt¡.Oznaczenia
rodremainder(reszta)
qodquotient(iloraz)
s,tparametrydodatkowe
KODYMDS(maximumdistanceseparable)
NiechCb¦dzieliniowymkodem[n,k,d].Wtedyzachodziograniczenie
dn−k+1(Singleton).Namocydefinicji
d=n−k+1,:kodCjestkodemMDS.
1
Twierdzenie(okodachMDS).DlakoduCliniowego[n,k,d]nast¦puj¡ce
warunkis¡paramirównowa»ne.
a)kodCjestMDS(czylid=n−k+1),
b)ka»den−kwierszewmacierzykontroliparzysto±ciH C s¡liniowo
niezale»ne,
c)wmacierzyG C ka»dypodzbiórkkolumnjestliniowoniezale»ny.
Dowód.Równowa»no±¢warunkówa)ib)jestju»znana.Wynikaonaztwier-
dzeniaowyznaczaniudystansunapodstawiemacierzykontroliparzysto±ci.
Udowodnimyrównowa»no±¢a),c).Załó»my,»ezachodzia),tzn.
d=n−k+1,orazprzypu±¢my,»ekkolumnmacierzyG,G=G C ,o
numerachj i ,gdzie1j 1 <···<j k n,jestzbioremliniowozale»nym.
Wtedypodmacierzotychkolumnachwyj¦tazmacierzyGjestkwadratowa
imarz¡dr<k.Zatemistniejezeruj¡casi¦nietrywialnakombinacjaliniowa
wierszytejpodmacierzy.St¡dodpowiadaj¡cakombinacjacałychwierszy
macierzyGjestniezerowymsłowemwCowadzen−k(bosłowoma
0naka»dejpozycjij i ),sk¡ddn−k,sprzeczno±¢.(Słowotojestnieze-
rowe,bosłowozerowejestjednoznaczniekombinacj¡trywialn¡elementów
bazowych).Zatemzachodzic).Naodwrót,je±lizachodzic),tosłowawC
maj¡conajwy»ejk−1zer,azatemdystansdn−(k−1),gdziezachodzi
równo±¢napodstawieograniczeniaSingletona.
2
Twierdzenie.Je»eliC(kodliniowy[n,k,d])jestkodemMDS,tokoddualny
C ? jestte»kodemMDS(zparametrami[n,n−k,k+1]).
Tenwa»nywynikjestwnioskiemzpoprzedzaj¡cegotwierdzenia.Niechd 0
oznaczadystanskodudualnegoC ? .ZatemC ? maparametry[n,n−k,d 0 ],
gdzied 0 k+1[=n−(n−k)+1]namocyograniczeniaSingletona.Z
drugiejstrony,poniewa»H C ? =(G C ) T ,wi¦cnamocypunktuc),d 0 k+1.
Zachodziwi¦crówno±¢wograniczeniuSingletonadlakodudualnego.
2
KODYCYKLICZNE
Przykład.Niechn=7,v=1101000.
Słowuvmo»emyprzyporz¡dkowa¢wielomianv(x):
v$v(x)=1+x+x 3 .
Cykliczneprzesuni¦ciawprawooipozycjimo»nazapisa¢jako
2
x i v(x)mod( 1+x n )
|{z}
=1+x 7
()x 7 =1)
słowowielomianmod(1+x 7 )
v=1101000v(x)=1+x+x 3
0110100xv(x)=x+x 2 +x 4
0011010x 2 v(x)=x 2 +x 3 +x 5
0001101x 3 v(x)=x 3 +x 4 +x 6
1000110x 4 v(x)=1+x 4 +x 5
0100011x 5 v(x)=x+x 5 +x 6
1010001x 6 v(x)=1+x 2 +x 6
Niechoznaczacykliczneprzesuni¦ciesłowawprawoo1pozycj¦.
Wtedy
(v 1 +v 2 )=(v 1 )+(v 2 )zachodziioznaczaaddytywno±¢operatora.
Jednorodno±¢równie»zachodzi.
)jestwi¦coperatoremliniowym.
Wnioski.Je»eliwmacierzygeneruj¡cej,cykliczneprzesuni¦ciawszystkich
wierszytejmacierzydaj¡wierszetejmacierzy,tokodjestcykliczny.
Kodnapewnojestcykliczny,gdyprzesuni¦ciacyklicznewszystkichelemen-
tówbazowychs¡wkodzie.
Definicja.Wielomianemgeneruj¡cymdlakoducyklicznegojestjedyny
wielomianniezerowymonicznyonajmniejszymstopniuwtymkodzie.
Wbinarnymkodziecyklicznymniemadwóchwielomianówniezerowycho
minimalnnymstopniu.
Dowódniewprost.Przypu±¢my,»eró»newielomianyg(x),g 0 (x)maj¡naj-
mniejszystopie«(>−1).Wtedyg(x)+g 0 (x)jestwkodzie(zliniowo±ci),
gdzienajwy»szepot¦gisi¦znosz¡.Zatem
−16=st(g(x)+g 0 (x))<stg(x),sprzeczno±¢.
Lemat.Je»eliCjestkodemcyklicznymdługo±ciniv2C,to
(8a(x))c(x):=a(x)v(x)mod(1+x n )jestsłowemwC.
Dowód.Niecha(x)=(a 0 +a 1 x+...+a m x m ),gdziestopie«m=sta(x)
3
302997667.001.png
mo»eby¢du»y,np.mn.Poniewa»obrotycyklicznemo»nazredukowa¢
wgwzoru
x i v(x)mod(1+x n )=x imodn v(x)mod(1+x n ),
wi¦cc(x)dasi¦zapisa¢jako
c(x)=a (x)v(x)mod(1+x n )=(a 0 +a 1 x+...+a n−1 x n−1 )v(x)mod(1+x n ).
Zatem
c(x)2hv(x),xv(x),...,x n−1 v(x)imod(1+x n ),coko«czydowód.
2
Lemat.Wielomiangeneruj¡cyg(x)dlakoducyklicznegoCjestpodziel-
nikiemka»degosłowac(x)2C.
Dowód.Niechc(x)2Cic(x)6=g(x).
Wtedyn>stc(x)stg(x)(równo±¢jestdopuszczalna,gdyCniejest
binarny).Zatemnapodstawieregułydzieleniazreszt¡
c(x)=q(x)g(x)+r(x),
gdzieresztar(x)mastopie«str(x)<stg(x)orazr(x)=c(x)+q(x)g(x)2C.
St¡dr(x)0,bobyłabysprzeczno±¢,wprzypadkugdyr(x)60.
2
Poni»szetwierdzenieuzasadnianazw¦„wielomiangeneruj¡cy”dlakodu.
Twierdzenie.Je»eliCjestkodemcyklicznymdługo±cin,awielomiange-
neruj¡cyg(x)mastopie«n−k,to
(i)dimC=k,
(ii)słowag(x),xg(x),...,x k−1 g(x)s¡baz¡wC,
(iii)c(x)2C,(9a(x))c(x)=a(x)g(x),gdziesta(x)<k.
Twierdzenie.Wielomiang(x)(stopnian−k)jestwielomianemgeneruj¡-
cymdlakoducyklicznegoCdługo±cin,dokładniegdyg(x)|(1+x n ).
Dowód(dlakodubinarnego).(8a(x))c(x):=a(x)g(x)mod(1+x n )jest
wC.Zatemstc(x)<n.Nadtonapodstawieregułydzieleniazreszt¡
a(x)g(x)mod(1+x n )=a(x)g(x)+q(x)(1+x n )=c(x),
gdzieg(x)|c(x)8a(x).Bior¡ca(x)=x k ,mamyq(x)1.
2
4
Abywi¦cznale¹¢wszystkiekodycyklicznedługo±cin,wystarczyznale¹¢
wszystkiepodzielnikidwumianu1+x n .Ka»dytakipodzielnikjestbowiem
wielomianemgeneruj¡cymdlakoducyklicznego
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin