קוד פולינומי

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

הגדרה

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

בהינתן מספר ופולינום יוצר שדרגתו , הקוד הפולינומי שנוצר על ידי הוא אוסף מילות הקוד שדרגתן קטנה מ- המתחלקות ללא שארית בפולינום .[1][2]

דוגמה

נגדיר את השדה ונקבע את הקבועים , , כאשר הפולינום היוצר הוא . הקוד הפולינומי הנוצר על ידי g מורכב מהמילים הבאות:

או במפורש:

מאחר שהקוד הפולינומי מוגדר מעל שדה גלואה בינארי ופעולת החיבור מתבצעת מודולו 2, מילות הקוד הן למעשה:

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

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

ראו גם

הערות שוליים

  1. ^ Amnon Ta-Shma and Dean Doron, Polynomial Codes and Cyclic Codes, Error Correcting Codes, Tel Aviv University
  2. ^ Ian F. Blake, Ronald C. Mullin, The Mathematical Theory of Coding, Academic Press, 10 May 2014, page 66
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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