יתירות

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

יתירות בהנדסה

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

יתירות פסיבית מנצלת עודף בכושר או תפוקה לצימצום מידת ההשפעה של כשל. מקרה טיפוסי כזה הוא השימוש העודף בכבלים המחברים גשר תלוי כדי להפחית את הסיכון שבקריסת הגשר כולו, במקרה שאחד מהם ניתק או נקרע. הצבת שני פנסי דרך ברכב, כך שבמקרה של תקלה באחד מהם, לא נותר הנוהג ברכב ללא ראות כלל. דוגמה נוספת היא RAID קיצור של redundant array of independent disks, תצורת אחסון של כוננים קשיחים הנהוגה בשרתים, באופן המאפשר שחזור מידע שאבד בעת תקלה. בדוגמאות אילו, נוצלה תכונה הנדסית מובנית ולא נעשתה כל פעולת בדיקה או תהליך קבלת החלטות כלשהו לטיפול בתקלה. שיטה כזו של תכנון הנדסי נקראת גם "שולי ביטחון".

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

תורת האינפורמציה

ערך מורחב – יתירות בתורת האינפורמציה

את רעיון היתירות בתורת האינפורמציה הגה לראשונה קלוד שאנון אבי תורת האינפורמציה. יתירות בהקשר זה פירושה כמות הסיביות המינימלית הדרושה לשידור מידע פחות כמות הסיביות שמכיל המידע עצמו, במילים אחרות כמות השטח ה"מבוזבז" על מנת לשדר מסר מסוים. כל שפה טבעית מכילה יתירות טבעית המאפיינת אותה, זאת משום שאותיות מסוימות מופיעות לעיתים תדירות יותר מאשר אותיות אחרות, למשל בשפה העברית האות יו"ד היא הנפוצה ביותר (11.7 אחוז בקירוב) לעומת האות זי"ן שהיא הנדירה ביותר (רק כ-0.9 אחוז). יתירות טבעית היא חלק בלתי נפרד מהשפה ואמורה לסייע בהבנת השפה לבני אנוש. בעזרת חישוב אנטרופיה, הוכיח שאנון כי בשפה האנגלית, המכילה 26 אותיות, כל אות מסוגלת להכיל תאורטית $\ {\mbox{log}}_{2}26=4.7$ סיביות מידע, אולם בפועל בשל היתירות הטבעית, אותיות השפה האנגלית מעבירות פחות מידע, ליתר דיוק רק 1.5 סיביות לאות. מזה נובע כי יתירות השפה האנגלית היא $\ 4.7-1.5=3.2$ סיביות.

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

דחיסת מידע

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

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

סכום ביקורת

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

יתירות לשונית ויתירות רטורית

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

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

יתירות בתכנות

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

יתירות בקריפטוגרפיה

המושג יתירות בקריפטוגרפיה עלה לראשונה בהקשר של ניתוח תדירויות של צופנים קלאסיים כגון צופן החלפה או צופן ויז'נר. ההצלחה בניתוח הצופנים הקלאסיים נזקפה לא מעט לזכות היתירות הטבעית של השפה, זאת משום שיתירות טקסט המקור זלגה לתוך הטקסט המוצפן ואפשרה למנתח הצופן להבחין בדפוסים ייחודיים בטקסט המוצפן ובעזרת ניתוח סטטיסטי של תדירויות ניתן היה לחשוף חלק נכבד מטקסט המקור ואף את המפתח עצמו. שאנון טבע לראשונה את המונח Unicity distance שהוא מדד הכמות המינימלית של טקסט מוצפן הדרושה למנתח בעל עצמת חישוב בלתי מוגבלת כדי לפרוץ את הצופן או לחלץ את מפתח ההצפנה שבו נעשה שימוש. למשל לחילוץ מפתח ההצפנה בצופן החלפה חד-אלפביתי נדרשות לפחות 28 אותיות. הצופנים הסימטריים המודרניים פועלים על גושי מידע גדולים (כ-64 סיביות לפחות) משום כך אינם חשופים ליתירות הטבעית של שפת הטקסט המיועד להצפנה. לכן ניתוח סטטיסטי מסוג זה אינו ישים כנגדם.

יתירות מוספת

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

דוגמה נפוצה לפונקציית יתירות קריפטוגרפית מופיעה בתקן איזו ISO/IEC 9796 הפונקציה מוגדרת באופן הבא: לאחר שהמסר $\ x$ רופד והורחב לפי התקן, משלבים את $\ t$ הבתים של המסר עם $\ t$ בתים יתירים לסירוגין כך: $\ x_{2i-1}=x_{i},x_{2i}=S(x_{i})$. בכך מכפילים את אורך המסר ל-$\ 2t$ בתים. הפונקציה $\ S$ הנקראת Shaddow function מוגדרת עבור קלט $\ u$ בגודל בית אחד כדלהלן:

$\ S(u)=\pi (u_{2})\ ||\ \pi (u_{1})$ (הסמל || מייצג שרשור, קרי הדבקת ערכים זה לצד זה במקום חיבור אריתמטי).

כאשר $\ u_{1}$ ו-$\ u_{2}$ הם שני חצאי הבית הקרויים ניבלים (כל ניבל מיוצג על ידי ספרה הקסדצימלית אחת השווה ל-4 סיביות). הפונקציה $\ \pi$ היא טבלת תמורה סטטית הבאה:

לסיום מחברים לבית האחרון ב-XOR את מספר סיביות הריפוד (מתהליך הריפוד הקודם).

יתירות מאפשרת גם הצפנה עם אימות והבטחת שלמות, על ידי שילוב צופן גושים עם פונקציית יתירות כדלהלן: השולח מחשב פונקציה $\ h$ פומבית (פונקציית גיבוב למשל) על המסר ומקבל סכום ביקורת $\ T=h(M)$ אותו הוא משרשר למסר לפני ההצפנה $\ C=E_{K}(M\ ||\ T)$. כעת בפענוח ניתן לאמת את המסר על ידי בדיקת הטקסט המפוענח $\ M||T$ אם הוא מכיל את היתירות הדרושה על ידי שימוש באותה פונקציה. אם הטקסט אינו מכיל את היתירות הדרושה ניתן להסיק כי אינו אותנטי. אפשר להבחין בשני סוגי פונקציות יתירות קריפטוגרפיות האחת פונקציית יתירות פומבית הידועה גם לתוקף פוטנציאלי, פונקציה זו אינה עושה שימוש במפתח הצפנה והשנייה יתירות סודית כלומר הפועלת עם מפתח הצפנה סודי.

ראו גם

• פונקציית גיבוב
• בדיקת יתירות מחזורית
• חתימה דיגיטלית

קישורים חיצוניים

• Handbook of Applied Cryptography