אלגוריתם מתקדם מאפשר לשלוף במהירות מידע מזיכרון של מערכות כגון טלפונים ומחשבים ולתקן שגיאות
העולם המודרני מייצר מידע רב מאוד בקצב מסחרר. כיצד מאחסנים אותו היטב בזיכרון הממוחשב ושולפים במהירות בעת הצורך? תורת הקידוד והאינפורמציה (תורת המידע) היא ענף מתמטי שלו יישומים רבים בטכנולוגיה ובמדע, ובעיקר במדעי המחשב. היא מבוססת על תורת ההסתברות ובאמצעותה ניתן לפתח ולבחון דרכים להעברת מידע ושמירתו במערכות מחשוב. בזכות כלים מתורה זו התפתחו וממשיכות להתפתח טכנולוגיות מידע מודרניות, כגון תקשורת סלולרית, מערכות אחסון נתונים ולווייני תקשורת. “כשמכניסים מידע לזיכרון של מערכת – כגון תמונות, סרטונים, קבצים ומסמכים – צריך לקודד אותו, לתת לו צורה, לייצג אותו פיזיקלית. זאת כדי שיוכל להיות מאוחסן ומשוחזר היטב בעת הצורך, מבלי שיופיעו בו שגיאות (כגון תמונה מטושטשת או אי יכולת לפתוח קובץ)”, מסביר פרופ’ יובל קסוטו מהפקולטה להנדסת חשמל ומחשבים בטכניון.
פרופ’ קסוטו עוסק בפיתוח שיטות קידוד מידע למערכות מחשוב מודרניות כגון מחשבים וטלפונים ניידים. קידוד מידע משמעותו הוספת ביטים – יחידות נתונים – לתוך השבב של המערכת. אלגוריתם פענוח אשר מוטמע במערכת, קורא את הביטים הללו ובעזרתם מתקן שגיאות. בסופו של דבר המטרה היא להצליח לאחסן מידע בזיכרון ולשמור על תקינותו. “כך למשל, אם רוצים להגדיל את נפח האחסון בטלפון הנייד או במחשב, יש לשנות את קידוד המידע, כך שיותר ביטים יצליחו להיכנס לתוך השבב. במצב כזה, כאשר הצפיפות בשבב גדלה, נוצרות יותר שגיאות במידע וצריך למצוא דרכים חדשות לשמור עליו, כלומר קודים מספיק חזקים. מסיבות פיזיקליות תמיד יהיו שגיאות בחלק מהביטים, אבל צריך להקפיד לתקן אותן לפני שהמידע מגיע למשתמש”, אומר פרופ’ קסוטו.
כיום רוב המשתמשים צריכים זיכרון מחשוב גדול ומהיר יותר מבעבר בשל כמות המידע האדירה שעליהם לשלוף מהמחשב במהירות. כאמור, ככל שהשבב צפוף יותר בנתונים, כך עולה הסיכון לשגיאות במידע. לפי תורת הקידוד והאינפורמציה, תיקון יעיל של שגיאות מצריך מבנה זיכרון המחולק ליחידות אחסון מידע גדולות, וזה המצב הקיים ברוב מערכות המחשוב כיום. אך יחידות מידע גדולות מאטות את הגישה ליחידות מידע קטנות. שכן, המערכת צריכה לקרוא ולתקן שגיאות בכולן, ורק לאחר מכן יכולה לשלוף את המידע הנדרש וכך העברתו מתעכבת. כלומר, הפתרונות הקיימים כיום אינם מאפשרים לגשת במהירות ליחידות מידע קטנות.
במחקרם האחרון, שזכה במענק מהקרן הלאומית למדע, ביקשו פרופ’ קסוטו וצוותו (בהובלת הדוקטורנט אשד רם) לתת מענה לבעיה ולמצוא שיטת קידוד שתאפשר לשלוף במהירות יחידות מידע קטנות מהזיכרון. כלומר, לבטל את הצורך לקרוא ולפענח יחידת מידע גדולה, לשלוף רק חלק קטן ממנה ולתקן את השגיאות שנוצרות בה בלבד. לשם כך הוסיפו לאלגוריתם הפענוח תכונה של גישה אקראית. כך יחידות המידע הקטנות יכולות להיות מוגנות ביעילות מפני שגיאות ובמקביל להישלף במהירות בעת הצורך. עד עתה צריך היה לבחור בין שתי האפשרויות.
החוקרים הדגימו את ביצועי האלגוריתם החדש בסימולציות, במחשב או טלפון נייד. הם ייצרו מידע, כגון תמונות או קבצים אחרים, הוסיפו שגיאות לחלק מהביטים בתת-היחידות שבו ואז קראו אותן באמצעות האלגוריתם החדש.
החוקרים הדגימו את ביצועי האלגוריתם החדש בסימולציות – כלומר דימו כיצד יפעל במחשב או טלפון נייד; הם ייצרו מידע (כגון תמונות או קבצים), הוסיפו שגיאות לחלק מהביטים בתת-היחידות שבו ואז קראו אותן באמצעות האלגוריתם החדש. באמצעות האלגוריתם הם קודדו יחידת מידע שלמה אך הצליחו לגשת במהירות לתת היחידות והראו שהשגיאות יכולות להיות מתוקנות בהסתברות גבוהה. תיאור מתמטי של אלגוריתם הפענוח החדש כגרף המחולק לתת-יחידות המחוברות ביניהן
“פיתחנו תורת קידוד נרחבת לתכונת הגישה האקראית והראינו שלאלגוריתם החדש, שמשלב אותה, יש כוח תיקון חזק מאוד. באמצעותו אפשר לקרוא ולתקן במהירות שגיאות גם בתת-יחידות מידע קטנות מבלי להגדיל את צריכת הזיכרון. הוא יעיל במיוחד כאשר מספר השגיאות בתת-היחידות קטן ביחס לסך כל השגיאות המתוקנות ביחידת המידע הגדולה. אך אנחנו יכולים לבנות קוד מתאים לכל מספר שגיאות בתת-היחידות ולתקן את כולן בהסתברות גבוהה”, מסכם פרופ’ קסוטו.
כיום ממשיכים החוקרים לפתח את האלגוריתם בשיתוף אוניברסיטאות ותעשיות בחו”ל כדי שבהמשך יוכלו להטמיעו בהתקני אחסון במחשבים וטלפונים ניידים.
החיים עצמם:
יובל קסוטו
פרופ’ יובל קסוטו, נשוי + שלושה (17, 15, 12), מתגורר בחיפה. אוהב לרוץ ולטייל במקומות קרובים (הוואדיות של חיפה) ורחוקים.
