שינויים

קפיצה אל: ניווט, חיפוש

מבנים אלגבריים למדעי המחשב - ארז שיינר

נוספו 247 בתים, 10:42, 17 בינואר 2021
/* הרצאה 13 קודים ציקליים; פרק 22 מהספר */
**הוכחה:
***אכן <math>x\cdot f(x)= a_{n-1}x^n+...+a_0x=a_{n-1}(x^n-1) + a_{n-1} + a_{n-2}x^{n-1}+...+a_0x</math>
 
 
*במילים פשוטות:
**יהי <math>f(x)=a_{n-1}x^{n-1}+...+a_0</math>
**אם <math>a_n=0</math> אזי ההזזה הציקלית היא <math>x\cdot f(x)</math>
**אם <math>a_n=1</math> אזי ההזה הציקלית היא <math>x\cdot f(x) +x^n +1</math>
***(מכבים את הביט האחרון, ומוסיפים ביט ראשון)
***נסמן <math>h(x)=x^k+t(x)</math> ולכן <math>h(x)g(x)=x^kg(x)+t(x)g(x)</math>.
***כעת <math>x^kg(x) = x\cdot x^{k-1}g(x)</math>.
***נחשב את השארית מודולו <math>x\cdot x^n{k-1}g(x) + x^n +1</math> ונקבל ההזזה היא הזזה ציקלית של המילה החוקית <math>x^{k-1}g(x)\in I</math>ולכן גם היא מילה חוקית כי הקוד ציקלי.***כיוון שהקוד ציקלי, גם המילה המוזזת הינה חוקית, ולכן כלומר <math>x\cdot x^kg{k-1}g(x)\equiv + x^n +1=q(x)g(x) \mod x^n-1</math>.***נחזור לחלוקה בשארית המקורית, נחשב את השאריות מודולו <math>x^n-1</math> נציב ונקבל:****כי <math>0=q(x)g(x)+=t(x)g(x)+r(x)</math>****נעביר אגף ונוציא גורם משותף <math>r(x)=(q(x)+t(x))g(x)=r(x)</math>***כיוון ש <math>\deg(r)<\deg(g)</math> נובע כי <math>r(x)=0</math>.
**בכיוון השני, נניח כי <math>x^n-1=t(x)g(x)</math> ונוכיח כי מדובר בקוד ציקלי.
***נוכיח כי לכל מילה חוקית <math>h(x)g(x)\in I</math> גם השארית <math>xh(x)g(x) \mod x^n-1</math> היא מילה חוקית.