שינויים

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

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

נוספו 1,075 בתים, 12:05, 11 בינואר 2018
/* הרצאה 13 קודים ציקליים; פרק 22 מהספר */
*טענה: קוד פולינומי ב<math>R</math> יהיה ציקלי אם"ם הפולינום <math>g(x)</math> מחלק את <math>x^n-1</math>.
*הוכחה:
*בכיוון ראשון, נניח כי הקוד ציקלי:
**ראשית, נוכיח כי קבוצת המילים החוקיות <math>I</math> היא אידיאל של <math>R</math>.
***תהי <math>f(x)\in I</math> מילה חוקית. כיוון שהקוד ציקלי גם <math>x\cdot f(x)\in I</math>.
***באופן דומה, לכל <math>k</math> מתקיים כי <math>x^k\cdot f(x)\in I</math>.
***כיוון שהקוד לינארי, גם סכום של מילים חוקיות הוא מילה חוקית.
***ביחד, <math>a_{n-1}x^{n-1}f(x)+...+a_1xf(x)+a_0f(x)</math> הינה מילה חוקית.
***לכן לכל פולינום <math>h(x)\in R</math> מתקיים <math>h(x)f(x)\in I</math>, כלומר אוסף המילים החוקיות הינו אידיאל.
**כל אידיאל הוא ראשי, כלומר קיים פולינום <math>g(x)</math> כך שאוסף המילים החוקיות הוא <math>\{h(x)g(x)|h(x)\in R\}</math>.
***נוכיח זאת באופן דומה לחוג הפולינומים באופן כללי.
***ניקח