Bevezet\303\251s a matematik\303\241baJ\303\241rai AntalEzek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak.
<Text-field style="Heading 1" layout="Heading 1">1. Halmazok</Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">2. Term\303\251szetes sz\303\241mok</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">3. A sz\303\241mfogalom b\305\221v\303\255t\303\251se</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">4. V\303\251ges halmazok</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">5. V\303\251gtelen halmazok</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">6. Sz\303\241melm\303\251let</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">7. Gr\303\241felm\303\251let</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1">8. Algebra</Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">9. K\303\263dol\303\241s</Font></Text-field>
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">9.1. Kommunik\303\241ci\303\263 \303\251s k\303\263dol\303\241s</Font></Text-field>restart;
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.1.1. Inform\303\241ci\303\263, bit, entr\303\263pia.</Font></Text-field>H:=proc(F::list(positive),r::positive) local i,s,h; s:=0; h:=0;
for i to nops(F) do s:=s+F[i]; od;
for i to nops(F) do h:=h-log[r](F[i]/s)*F[i]/s; od;
h; end;
H([1,1],2); H([1,3],2); evalf(%);
with(StringTools);Entropy("ab"); Entropy("aaab");LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.1.2. Seg\303\251dt\303\251tel.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.1.3. T\303\251tel.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3">->9.1.4. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.1.5. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.1.6. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.1.7. K\303\263dol\303\241s.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">9.2. Gazdas\303\241gos k\303\263dol\303\241s</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.1. Bet\305\261nk\303\251nti k\303\263dol\303\241s.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.2. P\303\251lda.</Font></Text-field>M:=table():
M["a"]:="10111": M["b"]:="111010101": M["c"]:="11101011101":
M["d"]:="1110101": M["e"]:="1": M["f"]:="101011101":
M["g"]:="111011101": M["h"]:="1010101": M["i"]:="101":
M["j"]:="1011101110111": M["k"]:="111010111": M["l"]:="101110101":
M["m"]:="1110111": M["n"]:="11101": M["o"]:="11101110111":
M["p"]:="10111011101": M["q"]:="1110111010111": M["r"]:="1011101":
M["s"]:="10101": M["t"]:="111": M["u"]:="1010111":
M["v"]:="101010111": M["w"]:="101110111": M["x"]:="11101010111":
M["y"]:="1110101110111": M["z"]:="11101110101": M[" "]:="":
M["0"]:="1110111011101110111": M["1"]:="10111011101110111":
M["2"]:="101011101110111": M["3"]:="1010101110111":
M["4"]:="10101010111": M["5"]:="101010101": M["6"]:="11101010101":
M["7"]:="1110111010101": M["8"]:="111011101110101":
M["9"]:="11101110111011101": M["."]:="10111010111010111":
M[","]:="1110111010101110111": M["?"]:="101011101110101":
M[":"]:="11101110111010101": M["-"]:="111010101010111":
ASCII2Morse:=proc(s::string) local i,m; m:="";
for i to length(s) do m:=cat(m,M[s[i]],"000") od; m; end;
ASCII2Morse("ad "); ASCII2Morse("emi ");
addcomma:=proc(A,M,Ct,p) local i;
for i to length(A) do Ct[A[i]]:=cat(M[A[i]],p) od; end;Ct:=table(): A:="abcdefghijklmnopqrstuvwxyz 0123456789.,?:-";
addcomma(A,M,Ct,"000"):Ct["m"];code:=proc(m,Ct) local i,c; c:="";
for i to length(m) do c:=cat(c,Ct[m[i]]) od; end;c:=code("ad emi",Ct);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3">9.2.3. Prefix, szuffix, infix.</Text-field>IsPrefix("a","abc"); IsPrefix("","abc"); IsPrefix("abc","abc");IsSuffix("c","abc"); IsSuffix("b","abc");HammingSearch("xy","axybcxyde",0); HammingSearch("xyz","axybcxyzde",0);
HammingSearch("xyz","axybcxyzde",1);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.4. K\303\263dfa.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.5. Prefix k\303\263d, egyenletes k\303\263d, vessz\305\221s k\303\263d.
</Font></Text-field>isprefixcode:=proc(A,Ct) local f,i,j; f:=true;
for i to length(A) do for j from i+1 to length(A) do
if IsPrefix(Ct[A[i]],Ct[A[j]]) or IsPrefix(Ct[A[j]],Ct[A[i]])
then f:=false fi;
od; od; f; end;isprefixcode(A,Ct);decodewithcodetable:=proc(c,A,Ct) local i,j,a,m,cc; m:=""; cc:="";
for i while i<=length(c) do cc:=cat(cc,c[i]);
for j to length(A) do a:=A[j];
if Ct[a]=cc then m:=cat(m,a); cc:=""; break fi; od;
od; if length(cc)>0 then FAIL else m fi; end;decodewithcodetable(c,A,Ct);makedecodetable:=proc(A,Ct,Dt) local i;
for i to length(A) do Dt[Ct[A[i]]]:=A[i] od; end;Dt:=table(): makedecodetable(A,Ct,Dt): print(Dt);decode:=proc(c::string,Dt::table) local i,m,cc; m:=""; cc:="";
for i while i<=length(c) do cc:=cat(cc,c[i]);
if type(Dt[cc],string) then m:=cat(m,Dt[cc]); cc:=""; fi;
od; if length(cc)>0 then FAIL else m fi; end;decode(c,Dt);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.6. P\303\251ld\303\241k.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.2.7. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.2.8. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.2.9. <Font encoding="UTF-8">T\303\251tel: McMillan-egyenl\305\221tlens\303\251g.</Font></Text-field>mcmillan:=proc(L::list(posint),r::posint)
convert(map(x->r^(-x),L),`+`) end;
mcmillan([6,7,5],2);shannoncode:=proc(B::string,L::list(posint)) local i,s,c,r,C,LL;
r:=length(B); s:=0; C:=[];
LL:=[[L[i],i]$i=1..nops(L)]; LL:=sort(%,(x,y)->x[1]<y[1]);
for i to nops(LL) do
c:=convert(s*r^LL[i][1],base,r); c:=map(x->B[x+1],c); c:=cat("",op(c));
c:=Reverse(c); c:=cat(Fill(B[1],LL[i][1]-length(c)),c);
C:=[op(C),[c,LL[i][2]]]; s:=s+1/r^LL[i][1];
od; C:=sort(C,(x,y)->x[2]<y[2]); map(x->x[1],C); end;
L:=[6,7,5]; B:="ab"; shannoncode(B,L);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3">->9.2.10. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.2.11. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.2.12. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.2.13. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.14. \303\201tlagos sz\303\263hossz\303\272s\303\241g, optim\303\241lis k\303\263d.</Font></Text-field>meanlength:=proc(F::list(nonnegative),L::list(posint))
local i,s,m; if nops(F)<>nops(L) then return FAIL fi; s:=0; m:=0;
for i to nops(F) do s:=s+F[i] od; if s=0 then return FAIL fi;
for i to nops(F) do m:=m+L[i]*F[i] od; m/s; end;meanlength([1,1,2],[6,7,5]);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.15. Shannon t\303\251tele zajmentes csatorn\303\241ra.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.16. T\303\251tel: Shannon-k\303\263d l\303\251tez\303\251se.</Font></Text-field>shannonlength:=proc(F::list(positive),r::posint)
local i,j,s,L; s:=0; L:=[]; if r<=1 then return FAIL fi;
for i to nops(F) do s:=s+F[i] od;
for i to nops(F) do for j while r^j<s/F[i] do od; L:=[op(L),j];
od; L; end;F:=[1,1,2,2]; L:=shannonlength([1,1,2,2],4); shannoncode("0123",%);H(F,4); evalf(%); meanlength(F,L); evalf(%);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.17. T\303\251tel: optim\303\241lis k\303\263d konstrukci\303\263ja.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.18. Huffmann-k\303\263d.</Font></Text-field>huffmannlength:=proc(F::list(nonnegative),r::posint)
local i,l,h,rr,s,L,HH; if r<=1 then return FAIL fi;
if nops(F)<=r then return [1$i=1..nops(F)] fi;
L:=[[F[i],0,i]$i=1..nops(F)]; HH:=heap[new]((x,y)->x[1]>=y[1],op(L));
rr:=2+((nops(L)-2) mod (r-1));
do
h:=heap[extract](HH);
if heap[empty](HH) then break fi;
s:=h[1]; L:=[h];
for i from 2 to rr do h:=heap[extract](HH); L:=[op(L),h]; s:=s+h[1]; od;
heap[insert]([s,1,L],HH); rr:=r;
od;
HH:=heap[new]((x,y)->x[1]<=y[1],[h[2],0,h[3]]);
do
h:=heap[extract](HH); if h[1]=0 then heap[insert](h,HH); break fi;
L:=h[3]; l:=h[2]+1;
for i to nops(L) do heap[insert]([L[i][2],l,L[i][3]],HH); od;
od; L:=[];
while not heap[empty](HH) do
h:=heap[extract](HH); L:=[op(L),[h[2],h[3]]];
od; sort(L,(x,y)->x[2]<y[2]); map(x->x[1],%); end;
F:=[1,1,2,2,3]; L:=huffmannlength(F,2);
evalf(H(F,2)); evalf(meanlength(F,L));huffmanncode:=proc(B::string,L::list(posint)) local i,j,l,ll,b,c,LL,C;
LL:=[[L[i],i]$i=1..nops(L)]; LL:=sort(LL,(x,y)->x[1]<y[1]);
ll:=1; b[ll]:=0; C:=[];
for i to nops(LL) do
l:=ll; b[l]:=b[l]+1;
while b[l]>length(B) do b[l]:=1; l:=l-1; b[l]:=b[l]+1; od;
l:=LL[i][1]; while ll<l do ll:=ll+1; b[ll]:=1; od;
c:=""; for j to l do c:=cat(c,B[b[j]]) od; C:=[op(C),[c,LL[i][2]]];
od; sort(C,(x,y)->x[2]<y[2]); map(x->x[1],%); end;huffmanncode("ab",L);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.19. P\303\251lda.</Font></Text-field>F:=[17,2,13,2,1,31,2,17,6,9]; L:=huffmannlength(F,3);
evalf(H(F,3)); evalf(meanlength(F,L)); huffmanncode("012",L);
L:=shannonlength(F,3); shannoncode("012",L); evalf(meanlength(F,L));F:=[1247,190,65,197,1407,78,326,165,444,105,541,605,352,638,683,96,0,367,600,761,226,199,9,1,261,437]; L:=huffmannlength(F,2);
huffmanncode("01",L); evalf(meanlength(F,L));F:=map(x->x+1,F); L:=shannonlength(F,2); shannoncode("01",L);
evalf(meanlength(F,L)); evalf(H(F,2));LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3">9.2.20. Adapt<Font encoding="UTF-8">\303\255v Huffmann-k\303\263d.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.2.21. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.2.22. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.2.23. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.24. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.2.25. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.26. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.2.27. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.28. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.2.29. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.30. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.31. A k\303\263doland\303\263 \303\241b\303\251c\303\251 kiterjeszt\303\251se.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3">->9.2.32. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.33. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.2.34. Sz\303\263t\303\241rk\303\263dok.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.35. Futamk\303\263dol\303\241s.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.36. LZ77.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.37. A gzip parancs.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.38. LZW-k\303\263dok.</Font></Text-field>LZW:=proc(m,T,N) local i,n,alpha,beta,gamma,L; n:=128; L:=[];
for i from 0 to n-1 do
T[convert([i],bytes)]:=cat("",convert(i,hex));
od;
if length(m)=0 then return L fi; alpha:=m[1];
for i from 2 to length(m) do
beta:=m[i]; gamma:=cat(alpha,beta);
if type(T[gamma],string) then alpha:=gamma; next fi;
if n<N then T[gamma]:=cat("",convert(n,hex)); n:=n+1; fi;
L:=[op(L),T[alpha]]; alpha:=beta;
od; L:=[op(L),T[alpha]]; end;m:="GUGOGOGOGOL"; Ct:=table(); L:=LZW(m,Ct,256);iLZW:=proc(L,T,N) local i,j,m,n,alpha,beta,gamma; n:=128; m:="";
for i from 0 to n-1 do
T[cat("",convert(i,hex))]:=convert([i],bytes);
od;
if nops(L)=0 then return m fi; j:=L[1]; alpha:=T[j];
for i from 2 to nops(L) do
j:=L[i];
if type(T[j],string) then
beta:=T[j]; gamma:=beta[1];
if n<N then T[cat("",convert(n,hex))]:=cat(alpha,gamma); n:=n+1; fi;
m:=cat(m,alpha); alpha:=beta;
else
gamma:=alpha[1]; beta:=cat(alpha,gamma);
T[cat("",convert(n,hex))]:=beta; n:=n+1;
m:=cat(m,alpha); alpha:=beta;
fi;
od; m:=cat(m,alpha); end;
Dt:=table(); iLZW(L,Ct,256);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.39. P\303\251lda az LZW-k\303\263dra.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.40. A compress parancs.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.41. Digitaliz\303\241l\303\241s.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.42. DFT \303\251s IDFT.</Font></Text-field>with(DiscreteTransforms);Z:=Vector(5,[0,1+I,0,0,0]);ZZ:=FourierTransform(Z);InverseFourierTransform(ZZ);FourierTransform(ZZ);
<Text-field style="Heading 3" layout="Heading 3">*9.2.43. FFT.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.44. FFT algoritmus.</Text-field>#
# This procedure do the bit reversation of the
# number x which is k bit long.
#
reverse:=proc(x,k) local xx,i,y;
xx:=x; y:=0;
for i to k do
if type(xx,odd) then
y:=2*y+1; xx:=(xx-1)/2;
else
y:=2*y; xx:=xx/2;
fi;
od; y; end;#
# This procedure do the butterfly operation
# between the two terms A[i] and A[j] of the
# table A. The multiplier is w.
#
butterfly:=proc(A,i,j,w) local X,Y;
X:=A[i]; Y:=A[j]*w; A[i]:=X+Y; A[j]:=X-Y;
end;#
# This is an FFT procedure.
# It use the butterfly procedure to operate on the vector A.
# The number of rounds is k in the FFT.
# T is a table of the powers of primitive root of unity.
#
fft:=proc(A,T,k) local l,s,w,t;
for l from 0 to k-1 do
for s from 0 to 2^l-1 do
w:=T[s];
for t from 0 to 2^(k-l-1)-1 do
butterfly(A,2^(k-l)*s+t,2^(k-l)*s+t+2^(k-l-1),w);
od;
od;
od;
end;#
# The pre procedure do the preparation for FFT:
# The table T[0..2^(k-1)] of powers of the primitive
# root of unity prepared.
#
pre:=proc(T,k) local i;
Digits:=2*Digits;
for i from 0 to 2^k-1 do
T[i]:=evalf(exp(-2*Pi*I*reverse(i,k)/2^(k+1)));
od;
Digits:=Digits/2;
end;k:=5; A:=array(0..2^k-1); for i from 0 to 2^k -1 do A[i]:=0 od:
T:=array(0..2^(k-1)-1);pre(T,k-1): A[1]:=1+I: print(A);fft(A,T,k): print(A);for i from 0 to 2^k-1 do
j:=reverse(i,k);
if i<j then x:=A[i]; A[i]:=A[j]; A[j]:=x; fi;
od: print(A);
<Text-field style="Heading 3" layout="Heading 3">*9.2.45. IFFT algoritmus.</Text-field>#
# This procedure do the inverse butterfly operation
# between the two terms A[i] and A[j] of the
# table A. The power of primitive unity is w.
#
ibutterfly:=proc(A,i,j,w) local X,Y,e;
X:=A[i]+A[j]; Y:=A[i]-A[j]; A[i]:=X; A[j]:=Y/w;
end;#
# This procedure is a floating point IFFT procedure.
# It use the ibutterfly procedure to operate on the vector A.
# The number of round in the FFT is k and T is a table of the
# powers of primitive root of unity.
#
ifft:=proc(A,T,k) local l,s,w,t;
for l from k-1 to 0 by -1 do
for s from 0 to 2^l-1 do
w:=T[s];
for t from 0 to 2^(k-l-1)-1 do
ibutterfly(A,2^(k-l)*s+t,2^(k-l)*s+t+2^(k-l-1),w);
od;
od;
od; end;for i from 0 to 2^k-1 do
j:=reverse(i,k);
if i<j then x:=A[i]; A[i]:=A[j]; A[j]:=x; fi;
od: print(A);ifft(A,T,k): print(A);
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.46. Gyors szorz\303\241s FFT-vel.</Font></Text-field>#
# The digmul procedure do the digit-by-digit
# multiplication of the two numbers after the
# fft's. The result will be in the first table.
#
digmul:=proc(A,B,k) local i;
for i from 0 to 2^k-1 do A[i]:=A[i]*B[i]; od;
end;A:=array(0..2^k-1); for i from 0 to 2^k -1 do A[i]:=0 od:
B:=array(0..2^k-1); for i from 0 to 2^k -1 do B[i]:=0 od:A[0]:=1: A[1]:=1: A[2]:=1: print(A);#
# This is the polynom multiplication, do multiplication or squaring.
# A and B are the two polynomials, the FFT and IFFT use k rounds.
#
polmulfft:=proc(A,B,k) global T;
if A=B then
fft(A,T,k);
digmul(A,A,k);
ifft(A,T,k);
else
fft(A,T,k);
fft(B,T,k);
digmul(A,B,k);
ifft(A,T,k);
fi; A; end;polmulfft(A,A,k): print(map(x->x/2^k,A));#
# The fftpre procedure do the preparation for the
# table for fft, where x is the number, A is the
# table, m the modulus, and k is the number of
# rounds for the fft, hence the table is 2^k long.
#
fftpre:=proc(x,A,m,k) local i,xx;
xx:=x;
for i from 0 to 2^k-1 do A[i]:=irem(xx,m,'xx'); od;
end;#
# The norm procedure do the normalization
# after the ifft. A is the table, m the modulus,
# and k is the number of rounds for the fft,
# hence the table is 2^k long. The fraction parts are
# left in the table A.
#
fftnorm:=proc(A,m,k) local i,x;
x:=0;
for i from 2^k-1 to 0 by -1 do
A[i]:=A[i]/2^k;
x:=m*x+round(A[i]);
A[i]:=A[i]-round(A[i]);
od; x; end;#
# This is the main procedure, do the multiplication or the squaring.
# a and b are the two numbers, m is the modulus for the preparation.
# The FFT and IFFT use k rounds.
#
mulfft:=proc(a,b,m,k) global A,B,T;
if a=b then
fftpre(a,A,m,k);
fft(A,T,k);
digmul(A,A,k);
ifft(A,T,k);
fftnorm(A,m,k);
else
fftpre(a,A,m,k);
fft(A,T,k);
fftpre(b,B,m,k);
fft(B,T,k);
digmul(A,B,k);
ifft(A,T,k);
fftnorm(A,m,k);
fi;
end;mulfft(123456789,987654321,20,5);123456789*987654321;print(A);
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.47. DCT \303\251s IDCT.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.48. K\303\251tdimenzi\303\263s DFT \303\251s DCT.</Font></Text-field>#
# This procedure is one round of an FFT procedure.
# It use the butterfly procedure to operate on the
# vector A. Round r is done, with siccor size s,
# and repeated until the vector A is finished,
# i.e. in size N. The T is a table of the powers of
# primitive root of unity.
#
fftround:=proc(A,T,r,s,N) local i,j,w,t;
i:=0;
while i<N do
for j from 0 to 2^r-1 do
w:=T[j];
for t from 0 to s-1 do
butterfly(A,i+t,i+s+t,w);
od;
i:=i+2*s;
od;
od; end;#
# This procedure is an IFFT round. It use the ibutterfly
# procedure to operate on the vector A. Round r is done
# with siccor size s and repeated until the vector A is
# finished, i.e. in size N. The T is a table of the
# powers of primitive root of unity.
#
ifftround:=proc(A,T,r,s,N) local i,j,w,t;
i:=0;
while i<N do
for j from 0 to 2^r-1 do
w:=T[j];
for t from 0 to s-1 do
ibutterfly(A,i+t,i+s+t,w);
od;
i:=i+2*s;
od;
od; end;#
# This is a several-dimensional fft procedure. It works
# on the array A having size 2^(k[1]+k[2]+..+k[n]),
# i.e. as if it would have dimensions k[1],..k[n].
#
ffts:=proc(A,T,k) local i,r,s,N;
N:=convert(k,`+`); N:=2^N; s:=N;
for i to nops(k) do
for r from 0 to k[i]-1 do
s:=s/2;
fftround(A,T,r,s,N);
od;
od; end;#
# This is a several-dimensional ifft procedure. It works
# on the array A having size 2^(k[1]+k[2]+..+k[n]),
# i.e. as if it would have dimensions k[1],..k[n].
#
iffts:=proc(A,T,k) local i,r,s,N;
N:=convert(k,`+`); N:=2^N; s:=1;
for i from nops(k) to 1 by -1 do
for r from k[i]-1 to 0 by -1 do
ifftround(A,T,r,s,N);
s:=s*2;
od;
od; end;A:=array(0..2^k-1); for i from 0 to 2^k -1 do A[i]:=0 od: A[1]:=1.+I;
print(A);ffts(A,T,[2,3]): print(A);iffts(A,T,[2,3]): print(A);
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.49. Hangt\303\266m\303\266r\303\255t\303\251s.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.50. K\303\251pt\303\266m\303\266r\303\255t\303\251s.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.51. PNG.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.52. JPEG</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.2.53. DjVu.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.2.54. Mozg\303\263k\303\251p-t\303\266m\303\266r\303\255t\303\251s: MPEG.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.2.55. Tov<Font encoding="UTF-8">\303\241</Font>bbi feladatok megold<Font encoding="UTF-8">\303\241sokkal.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.2.56. Tov<Font encoding="UTF-8">\303\241</Font>bbi feladatok.</Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">9.3. Hibakorl\303\241toz\303\263 k\303\263dol\303\241s</Font></Text-field>restart; with(StringTools);
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.1. Parit\303\241sbites k\303\263d.</Font></Text-field>addparity:=proc(m::string) local i,c; c:=0;
for i to length(m) do
if m[i]="1" then c:=1-c; next; fi;
if m[i]<>"0" then return FAIL fi;
od; if c=1 then cat(m,"1") else cat(m,"0") fi; end;addparity("0110"); addparity("0010");LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.2. P\303\251lda.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.3. P\303\251lda: parit\303\241</Font>sbites <Font encoding="UTF-8">k\303\263d.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.4. Hibajelz\305\221 k\303\263d.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.5. K\303\263dok t\303\241vols\303\241ga \303\251s s\303\272lya.</Font></Text-field>HammingDistance("abcd","abdd");LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.6. Minim\303\241lis t\303\241vols\303\241g\303\272 dek\303\263dol\303\241s.</Font></Text-field>Dt:=table(): Dt["0000"]:=FAIL: Dt["0001"]:=FAIL: Dt["0010"]:="0010":
Dt["0011"]:="0010": Dt["0100"]:="0100": Dt["0101"]:="0100":
Dt["0110"]:=FAIL: Dt["0111"]:="1111": Dt["1000"]:=FAIL:
Dt["1001"]:="1111": Dt["1010"]:="0010": Dt["1011"]:="1111":
Dt["1100"]:="0100": Dt["1101"]:="1111": Dt["1110"]:="1111":
Dt["1111"]:="1111":
Dt["0011"]; Dt["0000"]; Dt["1110"];LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.7. Hibajav\303\255t\303\263 k\303\263d.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.3.8. Hibajav\303\255t\303\241</Font>s ismert hibahelyekkel.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.9. Ism\303\251tl\303\251ses k\303\263d.</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.10. K\303\251tdimenzi\303\263s parit\303\241sellen\305\221rz\303\251s.</Font></Text-field>m:=9: n:=8: rnd:=rand(0..1): A:=Matrix(m,n):
for i to m do for j to n do A[i,j]:=rnd(): od: od: A;B:=Matrix(m+1,n+1):
for i to m do s:=0: for j to n do B[i,j]:=A[i,j]: if A[i,j]<>0 then s:=1-s fi: od: B[i,n+1]:=s od:
for j to n+1 do s:=0: for i to m do if B[i,j]<>0 then s:=1-s; fi: od: B[m+1,j]:=s: od:
B;LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.11. Hamming-korl\303\241t.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.12. Singleton-korl\303\241t.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.13. Line\303\241ris k\303\263d.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.14. Gener\303\241torm\303\241trix, ellen\305\221rz\305\221 m\303\241trix.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.15. Szindr\303\263madek\303\263dol\303\241s.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.3.16<Font encoding="UTF-8">. P\303\251lda: Fano-k\303\263d.</Font></Text-field>isvectorspacemod2:=proc(S) local x,y,z;
for x in S do for y in S do z:=zip((xx,yy)->xx+yy mod 2,x,y);
if not z in S then return false fi; od; od; true; end;Fano:={[0,0,0,0,0,0,0],[1,1,1,1,1,1,1],[1,1,1,0,0,0,0],[0,0,0,1,1,1,1],[1,0,0,1,1,0,0],[0,1,1,0,0,1,1],[0,1,0,1,0,1,0],[1,0,1,0,1,0,1],[0,0,1,1,0,0,1],[1,1,0,0,1,1,0],[1,0,0,0,0,1,1],[0,1,1,1,1,0,0],[0,1,0,0,1,0,1],[1,0,1,1,0,1,0],[0,0,1,0,1,1,0],[1,1,0,1,0,0,1]};
isvectorspacemod2(Fano);with(linalg);rangemod2:=proc(A::matrix) local m,n,i,j,v,S;
m:=rowdim(A); n:=coldim(A); S:={};
for i from 0 to 2^n-1 do
v:=convert(i,base,2); v:=[op(v),0$j=nops(v)+1..n]; v:=vector(n,v);
v:=multiply(A,v); v:=map(x->x mod 2,v);
v:=convert(v,list); S:=S union {v};
od; S; end;G:=matrix([[1,1,1,1],[1,0,0,1],[1,0,1,1],[0,0,1,1],[0,0,0,1],[0,1,1,1],[0,1,0,1]]);rangemod2(G); evalb(Fano=%);addcol(G,1,2,1):addcol(%,1,3,1):addcol(%,1,4,1):map(x->x mod 2,%);addcol(%,2,1,1):addcol(%,2,3,1):map(x->x mod 2,%);addcol(%,3,2,1):map(x->x mod 2,%);addcol(%,4,2,1):addcol(%,4,3,1):G1:=map(x->x mod 2,%);rangemod2(G1); evalb(Fano=%);H:=matrix([[0,1,1,1,1,0,0],[1,0,1,1,0,1,0],[1,1,0,1,0,0,1]]);sindromemod2:=proc(H::matrix,St::table) local i,j,k,m,n,s,ss,sss,x;
m:=rowdim(H); n:=coldim(H); if m>=n then return FAIL fi;
for i from 0 to 2^m-1 do
s:=convert(i,base,2); s:=[op(s),0$j=nops(s)+1..m];
St[s]:=[1$j=1..n]
od;
for i from 0 to 2^n-1 do
ss:=convert(i,base,2); ss:=[op(ss),0$j=nops(%)+1..n];
sss:=convert(ss,vector); k:=multiply(H,sss);
k:=map(x->x mod 2,k); k:=convert(k,list); s:=St[%];
if convert(ss,`+`)<convert(s,`+`) then St[k]:=ss fi;
od; end;St:=table(): sindromemod2(H,St); print(St);c:=vector([0,1,0,0,1,0,1]); multiply(H,c); map(x->x mod 2,%);e:=vector([0,0,0,0,1,0,0]); v:=evalm(c+e); s:=multiply(H,v);
s:=convert(s,list) mod 2; St[s];e:=vector([0,0,0,0,1,0,1]); v:=evalm(c+e); s:=multiply(H,v);
s:=convert(s,list) mod 2; St[s];e:=vector([1,1,1,0,0,0,0]); v:=evalm(c+e); s:=multiply(H,v);
s:=convert(s,list) mod 2; St[s];
<Text-field style="Heading 3" layout="Heading 3">9.3.17<Font encoding="UTF-8">. P\303\251lda: Reed-M\303\274ller-k\303\263dok.</Font></Text-field>RM51basis:={
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],
[1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0],
[1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0],
[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0]};linenvelop:=proc(S) local x,y,SS,SSS; SS:=S;
while true do
SSS:=SS;
for x in SS do for y in SS do
SSS:=SSS union {zip((xx,yy)->xx+yy mod 2,x,y)}
od; od;
if SS=SSS then return(SS) fi;
SS:=SSS;
od; end;linenvelop(RM51basis); nops(%);
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.3.18. Hamming-k\303\263dok.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.3.19. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.20. Polinomk\303\263dok.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.21. CRC-k\303\263dok.</Font></Text-field>CRC1:=modp1(ConvertIn(x+1,x),2);CRC5USB:=modp1(ConvertIn(x^5+x^2+1,x),2);m:=5: k:=10: L:=[0,1,1,0,1,1,1,1,1,1]; [0$'i'=1..m,op(L)];
l:=modp1(ConvertIn(%,x),2); modp1(Rem(%,CRC5USB),2);
modp1(Add(l,%),2); modp1(ConvertOut(%),2);CRC8:=modp1(ConvertIn(x^8+x^2+x+1,x),2);CRC16IBM:=modp1(ConvertIn(x^16+x^15+x^2+1,x),2);CRC16CCITT:=modp1(ConvertIn(x^16+x^12+x^5+1,x),2);CRC32:=modp1(ConvertIn(x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1,x),2);CRC64ISO:=modp1(ConvertIn(x^64+x^4+x^3+x+1,x),2);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.3.22. A CRC-k\303\263dok hibajelz\305\221</Font> k<Font encoding="UTF-8">\303\251</Font>pess<Font encoding="UTF-8">\303\251</Font>ge.</Text-field>modp1(Factors(CRC1),2); m:=1; ifactor(2^m-1);modp1(Factors(CRC5USB),2); m:=5; ifactor(2^m-1);p:=modp1(ConvertIn(x,x),2); modp1(Powmod(p,31,CRC5USB),2);modp1(Factors(CRC8),2); m:=7; ifactor(2^m-1);modp1(Factors(CRC16IBM),2); m:=15; ifactor(2^m-1);modp1(Powmod(p,32767,CRC16IBM),2);
modp1(Powmod(p,32767/7,CRC16IBM),2);
modp1(Powmod(p,32767/31,CRC16IBM),2);
modp1(Powmod(p,32767/151,CRC16IBM),2);
modp1(Factors(CRC16CCITT),2); m:=15; ifactor(2^m-1);modp1(Powmod(p,32767,CRC16CCITT),2);
modp1(Powmod(p,32767/7,CRC16CCITT),2);
modp1(Powmod(p,32767/31,CRC16CCITT),2);
modp1(Powmod(p,32767/151,CRC16CCITT),2);modp1(Factors(CRC32),2); m:=32; ifactor(2^m-1);modp1(Powmod(p,2^32-1,CRC32),2);
modp1(Powmod(p,(2^32-1)/3,CRC32),2);
modp1(Powmod(p,(2^32-1)/5,CRC32),2);
modp1(Powmod(p,(2^32-1)/17,CRC32),2);
modp1(Powmod(p,(2^32-1)/257,CRC32),2);
modp1(Powmod(p,(2^32-1)/65537,CRC32),2);modp1(Factors(CRC64ISO),2); m:=64; ifactor(2^m-1);modp1(Powmod(p,2^64-1,CRC64ISO),2);
modp1(Powmod(p,(2^64-1)/3,CRC64ISO),2);
modp1(Powmod(p,(2^64-1)/5,CRC64ISO),2);
modp1(Powmod(p,(2^64-1)/17,CRC64ISO),2);
modp1(Powmod(p,(2^64-1)/257,CRC64ISO),2);
modp1(Powmod(p,(2^64-1)/65537,CRC64ISO),2);
modp1(Powmod(p,(2^64-1)/6700417,CRC64ISO),2);CRCcodeweigth:=proc(k::posint,crcpoly::modp1) local i,l,L,m,s,w;
m:=modp1(Degree(crcpoly),2); w:=k+m;
for i to 2^k-1 do
L:=convert(i,base,2); [0$'i'=1..m,op(L)]; modp1(ConvertIn(%,x),2);
modp1(Multiply(%,crcpoly),2); L:=modp1(ConvertOut(%),2);
s:=convert(%,`+`); if s<w then w:=s fi;
od; w; end;CRCcodeweigth(4,CRC32);CRCcodeweigth(8,CRC32);CRCcodeweigth(12,CRC32);CRCcodeweigth(16,CRC32);CRCcodeweigth(20,CRC32);CRCcodeweigth(4,CRC64ISO);CRCcodeweigth(8,CRC64ISO);CRCcodeweigth(12,CRC64ISO);CRCcodeweigth(16,CRC64ISO);CRCcodeweigth(20,CRC64ISO);
<Text-field style="Heading 3" layout="Heading 3">*9.3.23. A n<Font encoding="UTF-8">\303\251</Font>gy Golay-k<Font encoding="UTF-8">\303\263d.</Font></Text-field>Golay2:=modp1(ConvertIn(x^11+x^10+x^6+x^5+x^4+x^2+1,x),2);codedistribution:=proc(p::posint,k::posint,genpoly::modp1,y) local i,j,L,m,s,S;
m:=modp1(Degree(genpoly),p); S:=0;
for i to p^k-1 do
L:=convert(i,base,p); modp1(ConvertIn(%,x),p);
modp1(Multiply(%,genpoly),p); L:=modp1(ConvertOut(%),p);
[0$j=1..k+m-nops(L),op(L)];
s:=map(j->y[j],%); s:=convert(%,`*`); S:=S+s;
od; S; end;codedistribution(2,12,Golay2,`y`);alias(alpha=RootOf(x^5+2*x+1));beta:=Expand(alpha^22) mod 3;p:=Expand((x-beta)*(x-beta^3)*(x-beta^4)*(x-beta^5)*(x-beta^9)) mod 3;Golay3:=modp1(ConvertIn(p,x),3);codedistribution(3,6,Golay3,`y`);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3">9.3.24. Vandermonde-determin<Font encoding="UTF-8">\303\241</Font>ns.</Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.25. Reed-Solomon-k\303\263dok.</Font></Text-field>with(PolynomialTools);lgn:=8; n:=2^lgn-1; M:=Nextprime(Z^lgn,Z) mod 2; alpha:=Z+1;
ordermodM:=proc(M,Z,lgn,alpha) local i,beta; beta:=1;
for i to 2^lgn-1 do
beta:=modpol(beta*alpha,M,Z,2);
if beta=1 then return i fi;
od; FAIL end;
ordermodM(M,Z,lgn,alpha);
m:=16; g:=mul((z-alpha^i),i=1..m);normalizepolyzZ:=proc(p,M)
local i;
CoefficientList(expand(p) mod 2,z);
map(x->modpol(x,M,Z,2),%);
add(%[i]*z^(i-1),i=1..nops(%)); sort(%); end;g:=normalizepolyzZ(g,M);rnd:=rand(2^lgn): k:=n-m; mv:=Vector(k); for i to k do mv[i]:=rnd(i) od:
mv[1]; mv:=map(x->convert(x,base,2),mv): mv[1]; i:='i':
mv:=map(x->sum(x[i]*Z^(i-1),i=1..nops(x)),mv): mv[1];
c:=add(mv[i]*z^(i-1),i=1..k)*g;
c:=normalizepolyzZ(c,M);cv:=CoefficientVector(c,z); cv[1];
cvb:=map(x->CoefficientList(x,Z),cv): cvb[1];
cvd:=map(x->add(x[i]*2^(i-1),i=1..nops(x)),cvb): cvd[1];vvd:=cvd; vvd[2]; vvd[5];
vvd[2]:=cvd[2]+7 mod 2^lgn; vvd[5]:=cvd[5]+13 mod 2^lgn;vvb:=map(x->convert(x,base,2),vvd): vvb[2]; vvb[5];
vv:=map(x->add(x[i]*Z^(i-1),i=1..nops(x)),vvb): vv[2]; vv[5];v:=add(vv[i]*z^(i-1),i=1..n): c:=add(cv[i]*z^(i-1),i=1..n): e:=v-c:
e:=normalizepolyzZ(e,M);
ev:=Vector(255); ev:=CoefficientVector(e,z);sindrome:=proc(m,n,alpha,M,Z,sv,vv) local i,j,s,beta,gamma; beta:=1;
for i to m do beta:=modpol(beta*alpha,M,Z,2); gamma:=1; s:=0;
for j from 0 to n-1 do
s:=modpol(s+vv[j+1]*gamma,M,Z,2); gamma:=modpol(gamma*beta,M,Z,2);
od; sv[i]:=s;
od; end;sv:=Vector(m): sindrome(m,n,alpha,M,Z,sv,vv):
s:=add(sv[i]*z^(i-1),i=1..m);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.26. Reed-Solomon-k\303\263d dek\303\263dol\303\241sa.</Font></Text-field>L:=(1-alpha^1*z)*(1-alpha^4*z); L:=normalizepolyzZ(L,M);beta:=1: for j from 0 to n-1 do
subs(z=beta,L); beta:=modpol(beta/alpha,M,Z,2);
if modpol(%%,M,Z,2)=0 then print(j) fi od:L1:=(1-alpha^4*z); L4:=(1-alpha^1*z);E:=alpha^1*ev[2]*L1+alpha^4*ev[5]*L4; E:=normalizepolyzZ(E,M);modpol(subs(z=alpha^(-1),E)/alpha^1/subs(z=alpha^(-1),L1),M,Z,2);modpol(subs(z=alpha^(-4),E)/alpha^4/subs(z=alpha^(-4),L4),M,Z,2);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">9.3.27. T\303\251tel.</Font></Text-field>reedsolomondecodezZ:=proc(m::posint,s::polynom,M::polynom)
local x0,x1,x2,y0,y1,y2,r0,r1,r2,q,i,L,E;
x0:=1; y0:=0; r0:=z^m; x1:=0; y1:=1; r1:=collect(normalizepolyzZ(s,M),z);
do
if degree(r1,z)<m/2 then
L:=CoefficientList(y1,z);
E:=CoefficientList(r1,z);
E:=map(x->modpol(x/L[1],M,Z,2),E);
E:=add(E[i]*z^(i-1),i=1..nops(E));
L:=map(x->modpol(x/L[1],M,Z,2),L);
L:=add(L[i]*z^(i-1),i=1..nops(L));
return [L,E]
fi;
r2:=r0; x2:=x0; y2:=y0;
while degree(r2,z)>=degree(r1,z) do
q:=modpol(lcoeff(r2,z)/lcoeff(r1,z),M,Z,2);
q:=q*z^(degree(r2,z)-degree(r1,z));
r2:=normalizepolyzZ(r2-q*r1,M); r2:=collect(r2,z);
x2:=normalizepolyzZ(x2-q*x1,M);
y2:=normalizepolyzZ(y2-q*y1,M);
od;
r0:=r1; x0:=x1; y0:=y1; r1:=r2; x1:=x2; y1:=y2;
od; end;
reedsolomondecodezZ(m,s,M);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.3.28. P\303\251lda.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.3.29. K\303\263dr\303\266vid\303\255t\303\251s.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.3.30. K\303\263dok direkt szorzata.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.3.31. Kaszk\303\241d k\303\263dok.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3"><Font encoding="UTF-8">*9.3.32. Adat\303\241tsz\303\266v\303\251s.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.33. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.3.34. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.3.35. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.36. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.37. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.38. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.39. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.40. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.41. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.42. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.43. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.44. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.45. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">->9.3.46. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.3.47. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">*9.3.48. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.3.49. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.3.50. Feladat.</Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.3.51. Tov<Font encoding="UTF-8">\303\241</Font>bbi feladatok megold<Font encoding="UTF-8">\303\241sokkal.</Font></Text-field>
<Text-field style="Heading 3" layout="Heading 3">9.3.52. Tov<Font encoding="UTF-8">\303\241</Font>bbi feladatok.</Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1">10. Algoritmusok</Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn