#abstract_algebra #computer_science

קידוד

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

קוד, מילה ויתירות

קוד הוא תת קבוצה של $Z_{2}^{m}$ כלומר קבוצה של וקטורים בינאריים באורך $m$ .
מילה היא איבר בקבוצה $x \in Z_{2}^{m}$ . מילה תמיד מורכבת מ יתירות+מידע כאשר המידע והיתירות הן וקטורים בינארים מגדלים $k, n$ כך ש $k + n = m$ .

מילה נקראת חוקית כאשר היא קידוד של מידע כלשהו, כלומר ישנו איזשהו קופסה שחורה ״המקודד״ שיודע לקחת את המילה ולחלץ ממנה מידע. מילה לא חוקית משמעותה שנפלה שגיאה.

parity check

מזהה האם כמות השגיאות היא אי זוגית. אם היא זוגית לא נזהה את השגיאה.
נניח שהמידע שלנו הוא $v = (x_{1}, x_{2} \dots, x_{n})$ ונגדיר את המילה המקודדת כ $u = (x_{1} \dots, x_{n}, \sum_{i = 1}^{n} x_{i})$ כאשר הסכום הוא היתירות. לאחר העברת מידע ישנה מילה שמתקבלת בצד השני, נסמנה כ $u^{'} = (y_{1}, y_{2}, \dots, y_{n + 1})$ . נשים לב ש:

x_{1} + \dots + x_{n} + \sum_{i = 1}^{n} x_{i} = 2 \sum_{i = 1}^{n} x_{i} \equiv_{2} 0

חשוב: כל המתמטיקה היא מעל חוג השאריות מסדר 2
אם המילה המתקבלת שווה למילה שנשלחה כלומר $u = u^{'}$ יתקיים

\sum_{i = 1}^{n} y_{i} = 2 \sum_{i = 1}^{n} x_{i} \equiv_{2} 0

טכניקה זאת מוכרת גם בשם Checksum

שגיאה

נזכר ש $e_{i} = (0, \dots, \underset{i}{\underset{⏟}{1}}, \dots 0)$ ונגדיר שגיאה באינדקס $i$ להיות $u + e_{i}$ . כעת במצב של שגיאה אחת יתקיים $u^{'} = u + e_{i}$ כלומר

u^{'} = x_{1} + \dots + (x_{i} + 1) + \dots + \sum_{j = 1}^{n} x_{j} = 1

כלומר ניתן לראות שבמצב שבו יש שגיאה אחת (או מספר שגיאות אי זוגי), התוצאה של הסכימה תהיה $1$ ולכן נוכל לזהות שגיאות כאשר מספר השגיאות הוא אי זוגי. אם לעומת זאת מספר השגיאות הוא זוגי נקבל בסכימה $0$ שזה כמו שנקבל במצב שאין שגיאות בכלל ולכן לא נזהה.

קידוד ליניארי

נגדיר קידוד ליניארי עם מטריצות. נסתכל על $A \in Z_{2}^{k \times m}$ . ניצור ממנה את זוג המטריצות הבא

G = (\binom{I_{m}}{A}) H = (A I_{k})

כאשר $G$ היא המטריצה המקודדת ו $H$ היא המטריצה המפענת.

המידע הוא $v \in Z_{2}^{m}$ כלומר וקטור בגודל כמות עמודות המטריצה $A$ והיתירות היא באורך $k$ כמות שורות המטריצה $A$ .
המילה המקודדת היא $G \cdot v$ כלומר

u = G \cdot v = (\binom{I}{A}) v = (\binom{v}{A v})

כעת בנינו את המילה הנשלחת. איך מקודדים אותה ומזהים שגיאות?

הבחנה

אוסף המילים החוקיות הוא $I m (G)$ כלומר כל המילים $G v$

הצד השני בדומה לשיטה של בדיקת זוגיות, מקבל $u^{'}$ ומחשב $H \cdot u^{'}$ במטרה לקבל וקטור $0$ .
טענה: תהי מילה $u \in Z_{2}^{k + m}$ אזי

\exists_{v \in Z_{2}^{m}} : u = G v \leftrightarrow H u = 0

כלומר- קוד ליניארי הוא בעצם $N (H)$ כלומר מרחב האפס של המטריצה $H$ .

הוכחה-
$\leftarrow$ : נניח $u = G v$ אזי

H G = (A I) (\binom{I}{A}) = A I + A I = 2 A I \equiv_{2} 0

סך הכל נקבל שלכל $v$

H G v = 0 v = 0

$\to$ : נניח $H u = 0$ , יהי $v$ כלשהו והמילה הנשלחת $u = (\binom{v}{x})$ כדי ש $u$ תהיה מילה חוקית צריך להראות ש $x = A v$ . אכן:

H u = (A I) (\binom{v}{x}) = A v + x = 0 \overset{in Z_{2}}{\to} A v = x

נשיב לב

מסקנה מההוכחה הזאת היא שיתירות של מילה $u$ היא יחידה והיא תמיד $A v$

דוגמה:
$A = (\begin{matrix} 1 & 1 & 1 & 1 \end{matrix})$ , נשים לב שכמות העמודות = אורך המידע , כמות השורות = אורך היתירות, אם כן

G = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{matrix})

ו $v = (\begin{matrix} a \\ b \\ c \\ d \end{matrix})$ ומתקיים

G \cdot v = G (\begin{matrix} a \\ b \\ c \\ d \end{matrix}) = (\begin{matrix} a \\ b \\ c \\ d \\ a + b + c + d \end{matrix})

כיצד שגיאות משפיעות על התהליך?
נניח והתקבלה שגיאה אחת כלומר המילה שהגיע לצד השני היא $u^{'} = u + e_{i}$ ויתקיים

H u^{'} = H (u + e_{i}) = H u + H e_{i} = C_{i} (H)

כלומר נזהה כל שגיאה יחידה אמ״מ ב $H$ אין עמודות אפסים (שזה שקול לדרישה שב $A$ לא יהיו עמודות $0$ ). אם למשל העמודה ה $i$ ב $H$ הייתה $0$ במקרה הנ״ל עדיין היינו מקבלים בתוצאה $0$ שזה לא טוב.

מה לגבי שתי שגיאות? $e_{i}, e_{j}$ יתקיים

H u^{'} = H (u + e_{i} + e_{j}) = C_{i} (H) + C_{j} (H)

אם אלו היו זהות אז היינו מקבלים $0$ גם כן בגלל שאנחנו מעל השדה מודולו 2. ולכן נזהה 2 שגיאות אמ״מ ב $H$ אין זוג עמודות זהות.

מסקנה

אם אין עמודות אפסים ב $H$ ואין 2 עמודות זהות, במצב זה נזהה כל 2 שגיאות ונוכל לתקן שגיאה יחידה

שאלה:
בהינתן $k$ ביטי יתירות מה יהיה אורך המידע הגדול ביותר עבורו $H$ תהיה ללא עומדת אפסים וללא זוג עמודות זהות?
זוהי שאלה קומבינטורית , אם יש $k$ ביטי יתירות זה אומר שיש $k$ שורות ב $A$ כלומר כל עמודה יכולה להחזיק בתוכה $k$ ערכים ולכן יש $2^{k}$ צירופים שונים לבניית עמודה (כולל עמודות האפסים.) כמו כן נשים לב ש $H$ מורכבת מ $k$ עמודות יחידה ולכן גם הן תפוסות לנו, סך הכל אורך המידע הגדול ביותר עבורו $H$ תהיה ללא עמודות אפסים וללא זוג עמודות זהו הוא

m = 2^{k} - 1 - k

דוגמה נניח שיש 3 ביטי יתירות האפשרויות לעמודות של $A$ הן

A = (\begin{matrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \end{matrix})

כי $2^{3} - 1 - 3 = 4$ . ולכן $H$ תיראה ככה

H = (\begin{matrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{matrix})

מרחק המינג

מרחק המינג היא בעייה ידועה בעולם האלגוריתמים. נוכל לראות איך היא עוזרת לנו לפתור בעיות הקשורות לקידוד.

משקל המינג:
נגיד משקל המינג של וקטור $v \in Z_{2}^{n}$ להיות מספר האחדות שבו.
מרחק המינג:
מרחק המינג $d (u, v)$ בין שני וקטורים הוא מספר השורות השונות בינהם. בגלל שאנחנו מעל שדה המודולו 2, ניתן לחשב את הנ״ל על ידי חישוב משקל המינג של $u - v$ .

דוגמה-
עבור $(\begin{matrix} 1 & 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 1 & 1 \end{matrix})$ יתקיים שמרחק המינג שלהם הוא

(1 1 0 0) - (0 1 1 1) = (1 0 1 1)

הגדרה- המרחק $d_{m i n}$ של קוד הוא המרחק המינימלי בין שתי מילות קוד שונות.

טענה 1- בקוד ליניארי המרחק $d_{m i n}$ שווה למשקל המינימלי של מילות קוד שאינן וקטור האפס.
טענה 2- יהי $C$ קוד ליניארי עם מרחק $d_{m i n}$ . אם $d_{m i n} \geq 2 d + 1$ כאשר $d$ מספר כלשהו אז $C$ יצליח לזהות $2 d$ שגיאות ולתקן $d$ שגיאות אמ״מ אין ב $H$ המטריצה שהמילות החוקיות שייכות למרחב ה $0$ שלה היא מטריצה בלי עמודת 0 ובלי עמודות זהות.

דוגמה-
תהי המטריצה

H = (\begin{matrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{matrix})

נחשב את $d_{m i n}$ של הקוד שהוא מרחב האפסים של $H$ . ונראה כמה שגיאות ניתו להזות ולתקן.

נשים לב שסכימה של העמודות $C_{1} + C_{2} + C_{4}$ תניב $0$ כלומר יש וקטור $v$ ששייך למרחב האפסים של $H$ (כלומר הוא מילת קוד) והוא

H v = (\begin{matrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{matrix}) = \overset{―}{0}

המשקל של וקטור זה הוא $3$ ולכן $d_{m i n} \leq 3$ . לפי הטענה הקודמה אנחנו יודעים ש $d_{m i n} \geq 3$ אמ״מ אין במטריצה עמודת אפסים או עמודות זהות וזה בידיוק המצב אצלנו לכן $d_{m i n} = 3$ . כלומר במצב זה ניתן לזהות עד שתי שגיאות ולתקן שגיאה אחת.

כיצד מתקנים שגיאה?
נניח ואירעה שגיאה אחת בידיוק במילת קוד $v$ . כפי שאמרנו התוצאה שנקבל היא העמודה ה $i$ של $H$ ולכן נוכל לדעת שהשגיאה קרתה בסיבית ה $i$ של $v$ וכדי לתקן נוכל פשוט להחזיר לצד המקבל את

(v + e_{i}) + e_{i} \equiv_{2} v

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

נעסוק כעת בחוג הפולינומים מעל $Z_{2}$ . איבר בחוג נראה ככה

a_{0} + a_{1} x + \dots + a_{n - 1} x^{n}

כאשר המקדמים הם בינאריים.
נתרגם בין וקטורים בינאריים לפולינומים וההיפך לפי המקדמים למשל

x^{4} + x^{3} + x \leftrightarrow 11010

כלומר מידע הוא מחרוזת בינארית שמתורגמת לפולינום כזה. אם מעבירים $k$ ביטים של מידע אז דרגת פולינום המידע היא $k - 1$ .

משפט : יהי $f, g$ פולינומים מעל $Z_{2} [x]$ אזי קיימים פולינומים יחידים $q, r$ כך ש

f = q g + r

ומתקיים $\deg (r) < \deg (g)$ .

תהליך הקידוד הפולינומי

יהי $g$ פולינום מדרגה $m$ ( $m$ מייצג את אורך היתירות) ויהי $f$ פולינום מידע ומדרגה חסומה $k - 1$ .
נחשב

x^{m} \cdot f

כדי להזיז את המידע $m$ ביטים בשביל לתת מקום ליתירות.
נחלק

x^{m} f \neg g

היתירות היא שארית החלוקה $r (x)$ כלומר היתירות יחידה. סך הכל המילה היא

x^{m} f + r

טענה: מילים הן חוקיות אמ״מ הן מתחלקות ב $g$ .
הוכחה-

x^{m} f = q g + r \to x^{m} f + r = q g

דוגמה:

Pasted image 20230304174539.png|500

קודים ציקליים

יהי וקטור בינארי $(a_{0}, a_{1}, \dots, a_{n - 1})$ הזזה ציקלית שלו היא $(a_{n - 1}, a_{0}, a_{1}, \dots, a_{n - 1})$ .
קוד נקרא ציקלי אם כל הזזה ציקלית של מילה חוקית היא גם מילה חוקית.

למה צריך קוד ציקלי?

היתירות עבור כל מילה היא ייחודית. ולכן כל שגיאה תהפוך את היתירות להיות יתירות שלא מתאימה למילה. מכיוון שניתן לעשות הזזות בקוד ציקלי נוכל להעביר את 𝑚 הביטים עם הטעות להיות ביטי היתירות וכך נוכל לזהות שישנה שגיאה.

למשל:
עבור $01101001$ הזזה ציקלית אחת תביא אותנו ל $11010010$ ומתקיים

x^{7} + x^{6} + x^{4} + x = x (x^{6} + x^{5} + x^{3} + 1)

נשים לב

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

טענה: עבור קוד ציקלי ומילה חוקית $u$ נניח ש $u^{'}$ התקבלה על ידי טעויות בטווח של $m$ ביטים. אזי $u^{'}$ איננה חוקית.
הוכחה- נב״ש ששתיהן חוקיות, נבצע הזזות של $u$ ו $u^{'}$ כך שכל השגיאות ב $u^{'}$ יהיו ב $m$ הביטים האחרונים. נקבל שתי מילים חוקיות הנבדלות רק ביתירות, בסתירה .

טענה: הכפלה של פולינום ב $x^{k}$ שקולה לביצוע shift על המחרוזת הבינארית.

הזזה ציקלית באופן אלגברי

נתאר את פעולת ההזזה הציקלית באופן אלגבי: $u = a_{n - 1} x^{n - 1} + \dots + a_{0}$ .

אם $a_{n - 1} = 0$ אז ההזזה היא $w = a_{n - 2} x^{n - 1} + \dots + a_{0} x$ ומתקיים $w = x u$ .
אם $a_{n - 1} = 1$ אז $x u = x^{n} + a_{n - 2} x^{n - 1} + \dots + a_{0} x$ , יש $x^{n}$ מיותר וחסר אחד ולכן ההזזה הציקלית הנכונה היא $x u + x^{n} + 1 = a_{n - 2} x^{n - 1} + \dots + a_{0} x + 1$ .

משפט: יהי $g$ מדרגה $m$ ונביט בקידוד של $k$ ביטי מידע. נסמן $n = k + m$ ויתקיים
הקוד ציקלי אמ״מ $g$ מחלק של $x^{n} + 1$