הצגת המקור של הדף "קוד פולינומי"

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

== הגדרה ==
בהינתן [[שדה סופי]] <math>GF(q)</math> (שהאיברים בו יוגדרו "סימבולים"), נגדיר לכל רצף סימבולים באורך <math>k</math>:{{כ}} <math>a_{k-1}\ldots a_0</math>, פולינום מתאים כך: <math>a_{k-1}x^{k-1} + \cdots + a_1x + a_0\,</math>.

בהינתן מספר <math>n</math> ופולינום יוצר <math>g(x)</math> שדרגתו <math>m \leq n</math>, הקוד הפולינומי שנוצר על ידי <math>g(x)</math> הוא אוסף מילות הקוד שדרגתן קטנה מ-<math>n</math> ה[[חלוקת פולינומים|מתחלקות]] ללא שארית בפולינום <math>g(x)</math>.{{הערה|Amnon Ta-Shma and Dean Doron, [http://www.cs.tau.ac.il/~amnon/Classes/2017-ECC/Lectures/Lecture2.pdf Polynomial Codes and Cyclic Codes], Error Correcting Codes, [[אוניברסיטת תל אביב|Tel Aviv University]]}}{{הערה|1= Ian F. Blake, Ronald C. Mullin, [https://books.google.co.il/books?id=lQfjBQAAQBAJ&pg=PA83&dq=polynomial+code&hl=en&sa=X&ved=2ahUKEwjM74aE9JXuAhVEqxoKHVSoCTIQ6AEwAnoECAQQAg#v=onepage&q=polynomial%20code&f=false The Mathematical Theory of Coding], Academic Press, 10 May 2014, page 66}}

== דוגמה ==

נגדיר את השדה <math>GF(2)=\{0,1\}</math> ונקבע את הקבועים <math>n=5</math>, <math>m=2</math>, כאשר הפולינום היוצר הוא <math>g(x)=x^2+x+1</math>. הקוד הפולינומי הנוצר על ידי ''g'' מורכב מהמילים הבאות:

:<math>0\cdot g(x),\quad 1\cdot g(x),\quad x\cdot g(x), \quad (x+1) \cdot g(x),</math>

:<math>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).</math>

או במפורש:

:<math>0,\quad x^2+x+1,\quad x^3+x^2+x,\quad x^3+2x^2+2x+1,</math>

:<math>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.</math>

מאחר שהקוד הפולינומי מוגדר מעל שדה גלואה בינארי <math>GF(2)=\{0,1\}</math> ופעולת החיבור מתבצעת [[חשבון מודולרי|מודולו 2]], מילות הקוד הן למעשה:

:<math>0,\quad x^2+x+1,\quad x^3+x^2+x,\quad x^3+1,</math>

:<math>x^4+x^3+x^2,\quad x^4+x^3+x+1,\quad x^4+x,\quad x^4+x^2+1.</math>

באופן שקול ניתן לייצג את מילות הקוד כמחרוזת של מקדמי הפולינום, כך:
:<math>00000,\quad 00111,\quad 01110,\quad 01001,</math>

:<math>11100,\quad 11011,\quad 10010,\quad 10101.</math>

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

== ראו גם ==
* [[חילוק פולינומים]]

== הערות שוליים ==
{{הערות שוליים}}

[[קטגוריה:תורת הקודים]]