קוד פולינומי

בתורת הקודים, קוד פולינומי הוא סוג של קוד ליניארי בו אוסף של מילות קוד חוקיות מורכב מהפולינומים (בדרך כלל בעלי אורך קבוע) שמתחלקים ללא שארית בפולינום קבוע נתון (בעל אורך קצר יותר, שנקרא הפולינום היוצר).

הגדרה

בהינתן שדה סופי $GF(q)$ (שהאיברים בו יוגדרו "סימבולים"), נגדיר לכל רצף סימבולים באורך $k$:‏ $a_{k-1}\ldots a_{0}$, פולינום מתאים כך: $a_{k-1}x^{k-1}+\cdots +a_{1}x+a_{0}\,$.

בהינתן מספר $n$ ופולינום יוצר $g(x)$ שדרגתו $m\leq n$, הקוד הפולינומי שנוצר על ידי $g(x)$ הוא אוסף מילות הקוד שדרגתן קטנה מ-$n$ המתחלקות ללא שארית בפולינום $g(x)$.

דוגמה

נגדיר את השדה $GF(2)=\{0,1\}$ ונקבע את הקבועים $n=5$, $m=2$, כאשר הפולינום היוצר הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)=x^2+x+1} . הקוד הפולינומי הנוצר על ידי g מורכב מהמילים הבאות:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\cdot g(x),\quad 1\cdot g(x),\quad x\cdot g(x), \quad (x+1) \cdot g(x),}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2 \cdot g(x),\quad (x^2+1)\cdot g(x),\quad (x^2+x)\cdot g(x), \quad (x^2+x+1) \cdot g(x).}

או במפורש:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0,\quad x^2+x+1,\quad x^3+x^2+x,\quad x^3+2x^2+2x+1,}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^4+x^3+x^2,\quad x^4+x^3+2x^2+x+1,\quad x^4+2x^3+2x^2+x,\quad x^4+2x^3+3x^2+2x+1.}

מאחר שהקוד הפולינומי מוגדר מעל שדה גלואה בינארי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle GF(2)=\{0,1\}} ופעולת החיבור מתבצעת מודולו 2, מילות הקוד הן למעשה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0,\quad x^2+x+1,\quad x^3+x^2+x,\quad x^3+1,}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^4+x^3+x^2,\quad x^4+x^3+x+1,\quad x^4+x,\quad x^4+x^2+1.}

באופן שקול ניתן לייצג את מילות הקוד כמחרוזת של מקדמי הפולינום, כך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 00000,\quad 00111,\quad 01110,\quad 01001,}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 11100,\quad 11011,\quad 10010,\quad 10101.}

קוד פולינומי זה, ככל קוד פולינומי אחר, הוא קוד ליניארי, כלומר כל צירוף ליניארי של מילות קוד מהווה מילת קוד בפני עצמו. במקרה לעיל, בו השדה מעליו מוגדרים הפולינומים הוא שדה גלואה בינארי, צירוף ליניארי ניתן לחישוב גם על ידי פעולת XOR על מילות הקוד בצורתן כמחרוזת בינארית של מקדמי הפולינום (למשל $00111\oplus 10010=10101$).

ראו גם

• חילוק פולינומים

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

קוד פולינומי30354482Q7226636