קודים לגילוי שגיאות

מוטיבציה

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

הגדרות

גילוי ותיקון שגיאות

המרחק המינימלי קובע את יכולת הגילוי והתיקון של שגיאות של קוד.

באופן כללי:

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

בדיקת זוגיות

נניח עבור הקוד:

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

ביט הזוגיות מתקבל מ-$XOR$ שאר הסיביות:

קוד חזרות

כל ביט משודר $r$ פעמים.

מינוח: להפעיל קוד חזרות על קוד $A$ עם $r=?$.

קוד $X\; out\; of\; Y$.

כל מילת הקוד באורך $Y$ מכילות בדיוק $X$ אחדים.
מספר המילים בקוד יהיה $\begin{pmatrix}Y\\X\end{pmatrix}=\frac{Y!}{X!(Y-X)!}$.
מרחק הקוד: 2 (לכל $X$ ו-$Y$)
⇐ יכולת גילוי של שגיאה בודדת.

אסמבלי

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

כמה רגיסטרים יש לנו בריסק-5? יש לנו $32$ רגיסטרים שכל אחד מהם הוא בגודל של מילה($32$ ביטים בקורס זה).
הרגיסטר $x0$ הוא מיוחד וערכו תמיד $0$.
מכיוון שיש לנו מספר מוגבל של רגיסטרים נשאף לבנות תוכנות שמשתמשות בזיכרון ביעילות.

הרגיסטרים שיש במערכת:

Name	Reg #	Use	Saver
$zero	0	Constant 0	-
ra	1	Return Address	Caller
sp	2	Stack Pointer	Callee
gp	3	Global Pointer	-
tp	4	Thread Pointer	-
t0-t2	5-7	Temp	Caller
s0-s1	8-9	Saved Registers	Callee
a0-a7	10-17	Function arguments/return values	Caller
s2-s11	18-27	Saved Registers	Callee
t3-t6	28-31	Temp	Caller
כשאנחנו רוצים לגשת לכתובת בזיכרון אנו נעשה זאת לפי בתים ולא לפי ביטים(כל בית הוא 8 ביטים):
​
אם נחתנו באמצע מילה אז הוא יספור 4 בתים מהנקודה בה נחתנו(ולכן מומלץ לא לעשות את זה)

תרגול

int* arr = {1,2,3,4,5,6,0};

lw t0,12(s0)
slli t1,t0,2
add t2,s0,t1
lw t3,0(t2)
addi t3,t3,1
sw t3,0(t2)
lw t0,0(s0)
addi t1,x0,-1
xor t0,t0,t1
addi t0,t0,1

נסתכל על מה כל שורה עושה ולאחר מכן נגלה מה הקוד הזה עושה בכללותו.
השורה lw t0,12(s0) טוענת את הערך $arr[3]=4$ במערך לרגיסטר $t_{0}$.
השורה slli t1,t0,2 מזיזה את הביטים ב-$t_{0}$ ב-2 שמאלה ומציבה זאת ב-$t_{1}$. כלומר, כעת $t_{1}=2^2t_{0}=16$.
השורה add t2,s0,t1 מחברת בין $s_{0}$ שבו יש את הכתובת של $arr$ ל-$t_{1}$ ומציבה את הערך ב-$t_{2}$. כלומר, ב-$t_{2}$ תהיה את הכתובת של האיבר החמישי במערך.
השורה lw t3,0(t2) מציבה ב-$t_{3}$ את הערך $arr[4]=5$.
השורה addi t3,t3,1 מציבה ב-$t_{3}$ את $t_{3}+1=6$.
השורה sw t3,0(t2) מציבה את הערך שנמצא ב-$t_{3}$ במקום בזכרון שאליו מצביע $t_{2}$ שהוא $\&arr[4]$.
לכן, קטע הקוד הזה מבצע $t_{0}=4$ ואז $arr[t_{0}]++$.

השורה lw t0,0(s0) שמה ברגיסטר $t_{0}$ את הערך $arr[0]=1$.
השורה addi t1,x0,-1 מציבה ברגיסטר $t_{1}$ את הערך $-1$.
השורה xor t0,t0,t1 מבצעת את פעולת ה-$XOR$ בין המילים ברגיסטרים ומאחסנת זאת ברגיסטר $t_{0}$. מכיוון ש-$t_{1}$ הוא $-1$ ולכן הוא בעצם רק אחדים, אז זה בעצם מבצע $t_{0}=not(t_{0})$.
השורה addi t0,t0,1 מבצעת $t_{0}=t_{0}+1$.
קטע הקוד הזה שם ברגיסטר $t_{0}$ את המשלים ל-$2$ של $-arr[0]$.

הפקודה slt t0,s0,s1 מבצעת:

לכן, נוכל להשתמש בה לפי ההשוואה הבאה bne t0,x0,label. זאת מכיוון שאנו יודעים כי רגיסטר $x_{0}$ הוא $0$ תמיד ואין לנו דרך לדעת באיזה רגיסטר יש $1$ אם לא השמנו בו את ערך זה.

נוכל להשתמש באותה פקודה ממקודם רק הפוך: slt t0,s1,s0 ואז נקבל את הערך $0$ ב-$t_{1}$ אם $s_{1}\geq s_{0}$.
לכן, נוכל עכשיו להשתמש בפקודת ההשוואה: beq t0,x0,label.

נציב ברגיסטר $t_{1}$ את הערך $1$ כך: addi t1,x0,1
כעת, נשתמש שוב בפקודה $slt$ כך: slt t0,t1,s0 שתיתן לנו $1$ אם $1<s_{0}$.
לבסוף, נבצע את ההשוואה: bne t0,x0,label.