תווית שרוטה עדיין נסרקת, וזה לא מזל

שנה של הובלת פרחים לחנויות לימדה אותי שתווית היא עצם פיזי לפני שהיא נתונים.

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

רובן עדיין נסרקו. הנחתי שהסורק עושה משהו מתוחכם עם תמונה מטושטשת.

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

אלה שני מוצרים שונים, ורוב שרשרת האספקה קונה את הראשון בלי לשים לב שהייתה בחירה.

ספרת ביקורת יודעת רק לומר לא

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

יחידת הקמעונאות נושאת EAN-13, שמסתיים בספרת ביקורת אחת מודולו 10. ארגז המשלוח נושא ITF-14, גם הוא ספרת ביקורת אחת מודולו 10. תווית הלוגיסטיקה שעל המשטח נושאת GS1-128, שהוא Code 128 מתחת, ו־Code 128 מגן על עצמו בתו ביקורת יחיד מודולו 103.

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

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

מה ריד־סולומון קונה במקום

אירווינג ריד וגוסטב סולומון פרסמו את הבנייה ב־1960, במאמר בשם Polynomial Codes over Certain Finite Fields. הרעיון קטן מספיק כדי לנסח אותו במשפט.

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

הוצאתם n − k סמלים על יתירות. בתמורה אתם יכולים לתקן עד (n − k) / 2 סמלים פגומים כשאינכם יודעים אילו מהם פגומים, ועד n − k כשאתם כן יודעים. קודי ריד־סולומון הם מפרידי מרחק מרבי, כלומר המרחק המינימלי שלהם הוא בדיוק n − k + 1. זה הטוב ביותר שקוד כלשהו יכול לעשות עבור התקורה הזו, וזה חסם מוכח ולא תכונה של מימוש של מישהו.

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

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

ארבע הרמות בקוד QR הן החלטה מסחרית

קודי QR, שמוגדרים ב־ISO/IEC 18004, נושאים יתירות ריד־סולומון מעל GF(256): 256 סמלים, בית אחד כל אחד. התקן חושף את התקורה כחוגה עם ארבעה מצבים.

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

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

Data Matrix בוחר בגישה האחרת. הגרסה הנוכחית שלו, ECC 200 ב־ISO/IEC 16022, אינה מציעה חוגה: היתירות קבועה לכל גודל סמל. GS1 DataMatrix, שהוא הפרופיל של GS1 לסימבולוגיה הזו ונכתב כמילה אחת כדי להבחין, הוא מה שסריאליזציה של תרופות רצה עליו תחת הדירקטיבה האירופית לתרופות מזויפות. זו בדיקת שפיות טובה על כל מה שלמעלה. סימון אריזה שחייב להישאר קריא דרך הפצה, אחסון וטיפול עד לדלפק ניפוק הוא סמל דו־ממדי עם תיקון אמיתי, לא ליניארי עם ספרת ביקורת.

RFID הוא סיפור של זיהוי, והייתי רשלן בעניין הזה

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

EPC UHF Gen2, שתוקנן כ־ISO/IEC 18000-63, מגן על הודעות ממשק האוויר שלו בבדיקות יתירות מחזורית: CRC-5 על השאילתה, CRC-16 על החבילה. CRC מזהה. הוא אינו מתקן.

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

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

למה בניתי אחד מעל 32 סמלים ולא 256

ברקודים עובדים מעל GF(256) משום שהסמל שלהם הוא בית, ובית הוא מה שהמטען כבר ממילא. זו ירושה, לא אופטימיזציה.

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

GF(32) מחזיק אלפבית של עשרים אותיות בסמל אחד ועוד נשאר מקום. אותה בנייה, אותו חסם מרחק, גודל שדה שנבחר לפי האלפבית ולא נורש ממילת מכונה.

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

שני התוצרים פתוחים: עבודת הקידוד בכתובת https://doi.org/10.6084/m9.figshare.32885588 וערכת הכלים עם תיקון השגיאות בכתובת https://doi.org/10.6084/m9.figshare.32963456.

מה שכל זה אינו מתקן

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

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

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

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

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