שינויים

*משפט: הפולינום <math>g(x)</math> מחלק את <math>x^n-+1</math> אם ורק אם הקוד הפולינומי הינו ציקלי.*שימו לב: n הוא אורך המילה המקודדת, שכולל הן את המידע והן את היתירות.

**ראשית נסמן ב<math>I</math> את אוסף כל המילים החוקיות, כלומר כל הפולינומים מהצורה <math>f(x)g(x)</math> כאשר <math>\deg(f)<k</math>.**כעת, בכיוון ראשון, נניח כי הקוד הינו הוא ציקלי:***נחלק את <math>x^n{k-1</math> ב<math>}g(x)</math> עם שארית, ונוכיח כי השארית היא אפס.מילה חוקית***כיוון שהקוד ציקלי, גם ההזזה הציקלית <math>x\cdot x^n{k-1=h(x)}g(x)+r(x)^n+1</math>חוקית***שימו לב שכלומר <math>h(x)g(x)\not\in I</math> כיוון ש<math>\deg(h)=k</math>.***נסמן <math>h(x)=x^k+t(x)</math> ולכן <math>h(x)g(x)=+x^kg(x)n+t1=h(x)g(x)</math>.***כעת לכן <math>x^kg(x) n+1= x\cdot x^{k-1}g(x)</math>.***<math>x\cdot x^{k-1}gh(x) + x^n +1</math> היא הזזה ציקלית של המילה החוקית <math>x^{k-1}) g(x)</math> ולכן גם היא מילה חוקית כי הקוד ציקלי, כפי שרצינו.***כלומר בכיוון שני, נניח כי <math>x\cdot x^{k-1}g(x) + x^n +1=qt(x)g(x)</math>***נציב ונקבל נשים לב כי <math>qdeg(x)g(x)=t(x)g(x)+r(x)=k</math>***נעביר אגף ונוציא גורם משותף תהי מילה חוקית <math>(qh(x)+t(x))g(x)=r(x)</math>***כיוון ש אם <math>\deg(r)<h\deg(cdot g)<n</math> נובע כי אז ההזזה הציקלית היא <math>rxh(x)g(x)=0</math>**בכיוון השני, נניח והיא מילה חוקית כי <math>x^n-1=tdeg(xh(x)g(x)<k</math> ונוכיח כי מדובר בקוד ציקלי.***נוכיח אחרת, נניח כי לכל מילה חוקית <math>deg(h(x)\cdot g(x)\in I=n</math> גם השארית ולכן ההזזה הציקלית היא <math>xh(x)g(x) \mod +x^n-+1</math> היא מילה חוקית.***נבצע חלוקה עם שארית של כלומר ההזזה הציקלית היא <math>xh(x\cdot h)g(x)</math> ב<math>+t(x)</math>.***<math>xhg(x)=q(xh(x)+t(x)+r)\cdot g(x)</math>***כיוון ש<math>\deg(xh(x))=deg(t(x))=k</math>, מתקיים נובע כי <math>\deg(r)<k</math>, ולכן <math>rxh(x)g+t(x)\in I)<k</math>.***נכפול את שני הצדדים בלכן <math>g(x)</math> ונקבל <math>xh(x)g(x)=q(x)(x^n-1)+rt(x)g(x)</math>.***לכן אכן השארית של <math>xh(x)\cdot g(x)</math> מודולו <math>x^n-1</math> היא מילה חוקית, כפי שרצינו.