کد کیوآر چگونه با ۳۰ درصد خرابی هنوز خوانده می‌شود؟

احتمالاً تابه‌حال با QR کدهای مخدوش مواجه شده‌اید؛ مثل کدی روی کاغذی که چند قطره قهوه روی مربع‌های سیاه و سفیدش به چشم می‌خورد، یا کدهای روی میز کافه‌ها که انگار خراشیده شده‌اند. در نگاه اول این کدها نباید قابل‌استفاده باشند، ولی وقتی دوربین گوشی یا یک دوربین عکاسی را مقابلشان می‌گیرید، کد را می‌شناسد و شما را به لینک یا پیامی که درونش ذخیره شده هدایت می‌کند.

اتفاق عجیب‌تر زمانی رخ می‌دهد که کد را بیشتر مخدوش کنید. شاید تا مدتی همچنان کار کند، اما ناگهان با پوشاندن چند مربع دیگر، گوشی از خواندنش بازمی‌ماند. چرا کدی که بخشی از بافت خود را از دست می‌دهد، هنوز اطلاعات درستی تحویل می‌دهد؟ آیا گوشی قسمت‌های گمشده را حدس می‌زند؟ آیا همه‌ی مربع‌های سیاه‌وسفید به یک اندازه اهمیت دارند؟

برای درک سازوکار کدهای کیو آر باید با دو دستاورد مهندسی آشنا شویم؛ اختراعی ژاپنی که برای حل مشکلات کارخانه‌های قطعه‌سازی خودرو شکل گرفت و روشی ریاضی که به دستگاه‌ها اجازه می‌دهد بخشی از اطلاعات آسیب‌دیده را بازسازی کنند.

اوایل دهه‌ی ۱۹۹۰، کارخانه‌های قطعات خودرو در ژاپن با مشکلی دست‌وپنجه نرم می‌کردند که امروز شاید چندان مهم به نظر نرسد. بارکدهای معمولی نمی‌توانستند تمام اطلاعات لازم برای شناسایی و مدیریت قطعات را در خود نگه دارند.

با تغییر شیوه‌های تولید، کارخانه‌ها به‌جای ساخت انبوه یک قطعه‌ی یکسان، مدل‌های متنوع‌تری تولید می‌کردند. هر قطعه اطلاعات مخصوص خودش را داشت و کارکنان باید مشخصات هرکدام را با سرعت و دقت ثبت می‌کردند.

بارکدهای رایج عمدتاً اطلاعات را در یک جهت ذخیره می‌کردند. ظرفیت محدود نمونه‌های معمول باعث می‌شد برای ثبت اطلاعات بیشتر، گاهی چندین بارکد کنار یکدیگر قرار بگیرند. در بعضی خطوط تولید، کارکنان مجبور بودند برای یک محصول حدود ۱۰ بارکد را پشت‌سرهم اسکن کنند؛ فرآیندی که قرار بود سرعت تولید را بالا ببرد، خودش وقت کارگران را می‌گرفت.

سال ۱۹۹۲، مهندسی به نام ماساهیرو هارا در شرکت ژاپنی دنسو با چالشی مشابه روبه‌رو شد. او روی دستگاه‌های بارکدخوان و فناوری‌های تشخیص نویسه کار می‌کرد و در ابتدا می‌خواست سرعت خواندن بارکدها را افزایش دهد؛ اما مشکل فقط از سرعت دستگاه ناشی نمی‌شد و خود بارکد محدودیت داشت.

هارا و یکی از همکارانش تصمیم گرفتند نوع جدیدی از کد بسازند که اطلاعات بیشتری ذخیره کند، فضای کمی بگیرد و به‌آسانی خوانده شود. ایده‌ای که به ذهنشان رسید، این بود که از دو بعد بهره بگیرند، یعنی به‌جای ذخیره‌ی اطلاعات در امتداد خطوط موازی، داده‌ها درون شبکه‌ای از خانه‌های سیاه‌وسفید و در دو جهت چیده شوند.

دنسو با هارا در سی‌امین سالگرد اختراع QR شرح داد که چگونه توسعه‌ی این فناوری در سال ۱۹۹۲ کلید خورد و سرانجام در سال ۱۹۹۴ به معرفی کد QR انجامید. QR مخفف عبارت Quick Response به معنای پاسخ سریع، نامی بود که هدف اصلی سازندگان را نشان می‌داد. سرعت موردنظر هارا به لطف سه مربع بزرگی حاصل شد که امروز در بیشتر کدهای QR می‌بینیم.

به یک کد QR نگاه کنید. احتمالاً سه مربع بزرگ را در گوشه‌های بالا-چپ، بالا-راست و پایین-چپ می‌بینید، درحالی‌که گوشه‌ی پایین-راست مربع چهارمی ندارد. پیش از اینکه گوشی اطلاعات کد را بخواند، باید بفهمد کد کجای تصویر قرار گرفته، چه اندازه‌ای دارد و از چه زاویه‌ای دیده می‌شود. اگر تصویر کمی کج، چرخیده یا از زاویه‌ای نامناسب ثبت شده باشد، دستگاه همچنان باید شبکه‌ی خانه‌های سیاه‌وسفید را تشخیص دهد.

او و همکارش نمونه‌های فراوانی از مواد چاپی، از مجله و تبلیغات گرفته تا نوشته‌های روی جعبه‌ها را بررسی کردند تا ترکیبی از ناحیه‌های سیاه‌وسفید بیابند که به‌ندرت در تصاویر معمولی ظاهر شود. جست‌وجوی آن‌ها سرانجام به نسبت مشخصی رسید.

الگوی ۱:۱:۳:۱:۱ به شما می‌گوید اگر خطی افقی یا عمودی از مرکز یکی از مربع‌های گوشه عبور کند، نسبت پهنای قسمت‌های متوالی سیاه، سفید، سیاه، سفید و سیاه برابر ۱ به ۱ به ۳ به ۱ به ۱ خواهد بود.

نسبت پنج‌بخشی به دستگاه کمک می‌کند الگوی موقعیت‌یابی را میان انبوهی از نقش‌ها و نوشته‌ها تشخیص دهد و قرارگیری سه الگو در سه گوشه نیز جهت کد را مشخص می‌کند. برای همین دیگر نیازی نیست کاربر کد را کاملا صاف و در جهت مشخصی جلوی اسکنر بگیرد.

ولی اگر داده‌های درون کد تصادفاً همین نسبت را بسازند چه؟ برای جلوگیری از چنین سردرگمی‌ای، QR پیش از چاپ، داده‌ها را با یکی از هشت الگوی پوشاننده (Mask) ترکیب می‌کند. نرم‌افزار سازنده هر هشت الگو را می‌آزماید و الگویی را برمی‌گزیند که کمترین شباهت را به الگوهای موقعیت‌یابی دارد و ناحیه‌های یکدستِ سیاه یا سفیدِ بزرگ کمتری می‌سازد. شماره‌ی الگوی انتخاب‌شده هم درون کد ثبت می‌شود تا گوشی بتواند اثرش را خنثی کند.

دو نوار باریک در کنار الگوهای موقعیت‌یابی، «اطلاعات قالب» را نگه می‌دارند؛ یعنی سطح تصحیح خطا و شماره‌ی الگوی پوشاننده. گوشی پیش از هر چیز باید همین نوارها را بخواند و برای احتیاط، این اطلاعات دو بار در کد تکرار شده‌اند. دورتادور کد هم حاشیه‌ای سفید به پهنای دست‌کم چهار خانه قرار می‌گیرد تا اسکنر مرز کد را از پس‌زمینه جدا کند. QR در ۴۰ نسخه ساخته می‌شود، از شبکه‌ی ۲۱×۲۱ خانه تا ۱۷۷×۱۷۷.

گوشی باتوجه‌به مجموعه‌ی این عناصر ساختاری می‌تواند تصویر ثبت‌شده در دوربین را به شبکه‌ای منظم از صفرها و یک‌ها تبدیل کند. مراحل بالا نحوه‌ی پیداشدن کد توسط گوشی را توضیح می‌دهند؛ ولی چرا باوجود تخریب قسمتی از شبکه، اطلاعات از بین نمی‌روند؟

فرض کنید سه عدد ۲، ۴ و ۶ را روی کاغذ نوشته‌اید. حالا عدد سوم پاک می‌شود و فقط دو عدد اول باقی می‌مانند. آیا می‌توانید عدد گمشده را پیدا کنید؟ احتمالاً پاسخ می‌دهید ۶؛ چون به نظر می‌رسد هر عدد دو واحد از عدد قبلی بزرگ‌تر باشد. بااین‌حال، نمی‌توان با قطعیت حکم داد. شاید دنباله از قانون دیگری پیروی کند و عدد سوم مقدار دیگری داشته باشد.

حالا تصور کنید از ابتدا می‌دانستیم اعداد بر اساس رابطه‌ی «دوبرابر شماره‌ی جایگاه» ساخته شده‌اند. در چنین وضعیتی، حتی پس از پاک شدن یکی از اعداد، به کمک رابطه‌ی مشخص می‌توانیم مقدار درستش را محاسبه کنیم.

یکی از مشهورترین روش‌های بازسازی داده، کد رید-سالومون نام دارد که دو ریاضی‌دان آمریکایی، ایروینگ رید و گوستاو سالومون، در سال ۱۹۶۰ معرفی‌اش کردند. کاربرد روش رید-سالومون به QR محدود نمی‌شود؛ مهندسان از خانواده‌ی کدهای یادشده در سامانه‌های ارتباطی، ذخیره‌سازی داده و دیسک‌های نوری هم بهره برده‌اند.

برای فهمیدن سازوکار الگوریتم، می‌توانیم به مفهوم ساده‌ای از ریاضیات دبیرستانی برگردیم. دو نقطه‌ی متفاوت روی صفحه، یک خط راست یکتا را مشخص می‌کنند؛ بنابراین وقتی بدانیم داده‌هایمان از یک رابطه‌ی خطی پیروی می‌کنند، با داشتن دو نقطه‌ی سالم می‌توانیم مقدار رابطه را در نقطه‌ی سومی که اطلاعاتش پاک شده، به دست بیاوریم.

برای یک چندجمله‌ای درجه‌ی دو، داشتن سه نقطه‌ی متفاوت کفایت می‌کند، برای چندجمله‌ای درجه‌ی سه به چهار نقطه نیاز داریم و الگو به همین ترتیب ادامه می‌یابد.

ایده‌ی رید-سالومون نیز به چندجمله‌ای‌ها و رابطه‌های ریاضی میان مقادیر تکیه دارد. البته در سامانه‌های دیجیتال، محاسبات روی اعداد حقیقی معمولی انجام نمی‌شوند، این روش از ساختارهایی به نام «میدان‌های متناهی» استفاده می‌کند.

در QR استاندارد، داده‌ها در واحدهای هشت‌بیتی به نام کدواژه (Codeword) سازمان‌دهی می‌شوند و هر کدواژه می‌تواند یکی از ۲۵۶ مقدار ممکن را بگیرد. رید-سالومون با محاسبات ریاضی روی مقادیر موجود، کدواژه‌های اضافی می‌سازد، اما این کدواژه‌های اضافی صرفاً نسخه‌ی تکراری اطلاعات اصلی نیستند و هرکدام از محاسبات مشخصی به دست می‌آیند و در کنار هم امکان تشخیص و تصحیح بخشی از خطاها را فراهم می‌آورند.

نکته‌ی مهم اینکه گوشی لزوماً نمی‌داند کدام مربع تصویر آسیب‌دیده و در بسیاری از موارد، صرفاً با داده‌هایی روبه‌رو می‌شود که مقدار اشتباهی دارند و باید خطا را هم شناسایی و هم اصلاح کند. در نتیجه، بازسازی اطلاعات هیچ شباهتی به حدس‌زدن یک کلمه از روی حروف باقی‌مانده ندارد و الگوریتم برای یافتن پاسخ، به سراغ رابطه‌های ریاضی از پیش تعریف‌شده می‌رود.

البته توان بازیابی اطلاعات هم محدودیت دارد و اگر تعداد خطاها از ظرفیت مشخصی فراتر رود، دیگر تضمینی برای بازسازی درست اطلاعات وجود نخواهد داشت؛ نکته‌ای که ما را به ویژگی مهم دیگری در طراحی QR می‌رساند.

کدهای QR در برابر آسیب سطوح مقاومت متفاوتی دارند. هنگام ساخت یک کد، می‌توان سطح تصحیح خطای آن را انتخاب کرد. استاندارد QR چهار سطح اصلی دارد که با حروف L و M و Q و H شناخته می‌شوند.

ارقام جدول در نگاه اول بسیار ساده به نظر می‌رسند و شاید تصور کنیم یک QR با سطح H حتی پس از بریده شدن ۳۰ درصد از مساحتش با قیچی، همچنان کار خواهد کرد؛ اما کمی صبر کنید!

طبق مستندات فنی درصدهای جدول به سهم کدواژه‌های قابل بازیابی اشاره دارند، نه به مساحت دقیق تصویر. فرض کنید کدی ۲۰۰ کدواژه در خود دارد؛ اگر سامانه‌ی تصحیح خطا ظرفیت اصلاح ۵۰ کدواژه‌ی اشتباه را داشته باشد، نرخ تصحیح خطایش ۲۵ درصد خواهد بود.

مقاومت بیشتر کد QR هزینه‌ای هم دارد؛ هرچه سهم اطلاعات کمکی بالا برود، فضای کمتری برای ذخیره‌ی داده‌های اصلی باقی می‌ماند. اگر بخواهیم پیوندی طولانی را در یک QR کوچک بگنجانیم، انتخاب بالاترین سطح تصحیح خطا به تولید کدی بزرگ‌تر و متراکم‌تر منجر می‌شود.

برای محیط تمیز و شرایط کنترل‌شده، شاید سطح پایین‌تر تصحیح خطا کافی باشد؛ اما برای کدی که روی بسته‌بندی صنعتی چاپ شده و در معرض گردوغبار یا لکه‌های روغن قرار دارد، مقاومت بالاتر اهمیت بیشتری پیدا می‌کند. مقاومت در برابر آلودگی و آسیب، از روز نخست جزو نیازهایی بود که سازندگان QR در محیط کارخانه درکش می‌کردند.

حتماً کدهای QR تبلیغاتی را دیده‌اید که لوگوی یک شرکت در مرکزشان جا خوش کرده؛ گاهی لوگو آن‌قدر بزرگ طراحی می‌شود که بخش قابل‌توجهی از مربع‌های سیاه‌وسفید را می‌پوشاند، اما گوشی بدون دردسر کد را می‌خواند.

طراحی‌های تبلیغاتی از قابلیت تصحیح خطا بهره می‌گیرند. اگر طراح مقدار داده‌ها، سطح تصحیح خطا و محل قرارگیری لوگو را به‌درستی تنظیم کند، دستگاه می‌تواند باوجود بخش پوشانده‌شده، اطلاعات را بازیابی کند. درواقع اطلاعات اصلی و داده‌های تصحیح خطا در قسمت‌های مختلف شبکه پخش شده‌اند و پوشاندن مرکز کد نیز می‌تواند باعث ازبین‌رفتن اطلاعات شود، فقط سامانه توان کافی برای جبران آسیب را دارد.

حالا شرایط دیگری را تصور کنید؛ به‌جای پوشاندن مرکز، بخشی از مربع‌های بزرگ یکی از گوشه‌ها را مخدوش می‌کنیم. در وضعیت جدید، ممکن است باوجود آسیب ظاهری کمتر، خواندن کد با مشکل روبه‌رو شود. اینجا باید به وظیفه‌ی مربع‌ها توجه کنیم.

در نظر داشته باشید که آسیب به یکی از مربع‌های بزرگ همیشه باعث شکست کد نمی‌شود و بعضی اسکنرها می‌توانند به کمک الگوهای باقی‌مانده و روش‌های پردازش تصویر، کدهای آسیب‌دیده را نیز بیابند. به‌علاوه بخشی از سایر اطلاعات ساختاری QR مانند سطح تصحیح خطا و الگوی پوشاننده‌ی داده‌ها هم در برابر خطا محافظت می‌شوند.

در نهایت، مقاومت یک QR به دو توانایی متفاوت بستگی دارد؛ نخست توانایی دستگاه در تشخیص شبکه‌ی کد از روی تصویر و دوم قابلیت اصلاح خطاهای داده‌های استخراج‌شده.

حالا می‌توانیم به کد آسیب‌دیده‌ی ابتدای داستان برگردیم و چند آزمایش عملی انجام دهیم.

ابتدا یک کد QR بسازید که نشانی اینترنتی کوتاهی را در خود ذخیره کرده باشد و ترجیحاً هنگام ساخت، سطح تصحیح خطا را روی H بگذارید. بعد کد را در اندازه‌ای مناسب چاپ کنید، از خوانده‌شدنش توسط گوشی مطمئن شوید و سپس چند نسخه‌ی یکسان از برگه تهیه کنید.

در نسخه‌ی اول، بخشی از مرکز QR را با ماژیک بپوشانید؛ در نسخه‌ی دوم، تقریباً همان مساحت را در گوشه‌ای دیگر مخدوش کنید و در نسخه‌ی سوم، به‌جای یک لکه‌ی بزرگ، چند علامت کوچک در نقاط پراکنده بگذارید. در هر مرحله، گوشی را از فاصله‌ای یکسان مقابل کد بگیرید و نتیجه را بررسی کنید.

مقاومت QR در برابر آسیب، روی دیگری هم دارد. شاید دیده باشید که برخی از مردم، وقتی می‌خواهند اسناد شخصی‌شان را در گروه‌ها یا شبکه‌های اجتماعی به اشتراک بگذارند، برای احتیاط روی کد QR را حسابی خط می‌زنند که متأسفانه برای حفظ امنیت و اطلاعاتشان کافی نیست.

برای کسی که باحوصله سراغ تصویر می‌رود، کار از آنچه فکر می‌کنید ساده‌تر پیش می‌رود. گوشی نمی‌داند کدام خانه‌ها آسیب دیده‌اند، ولی چنین فردی دقیقاً می‌بیند کجای کد پوشیده شده. در نظریه‌ی کدگذاری، به داده‌ای که جایش معلوم ولی مقدارش نامعلوم باشد پاک‌شدگی (Erasure) می‌گویند. رید-سالومون می‌تواند تقریباً دو برابر خطاهای ناشناخته، پاک‌شدگی را جبران کند؛ پس ظرفیتی که در جدول سطوح تصحیح خطا دیدیم، برای او عملاً بزرگ‌تر می‌شود.

بخش زیادی از خط‌خطی‌ها هم روی قسمت‌هایی می‌افتند که رازی در خود ندارند. الگوهای موقعیت‌یابی، خطوط زمان‌بندی و الگوهای تنظیم در همه‌ی کدهای هم‌اندازه یکسان‌اند و می‌توان دوباره رسمشان کرد. اطلاعات قالب هم دو نسخه دارد. خطوط ماژیک یا قلم‌موی نیمه‌شفاف برنامه‌های ویرایش عکس هم بسیاری از خانه‌ها را فقط کم‌رنگ می‌کنند و کاملاً نمی‌پوشانند.

اگر می‌خواهید ذوق سفر یا کنسرتتان را با دیگران قسمت کنید، کد را کامل از قاب بیرون بگذارید یا تمامش را زیر یک مستطیل توپر و مات پنهان کنید. خط‌خطی، تار کردن و پیکسلی کردن ملایم تضمینی نمی‌دهند. بارکدهای دیگر و نوشته‌های چاپی روی بلیت، مثل نام و شماره‌ی رزرو، هم همین حکم را دارند. کدی که برای تاب‌آوردن خرابی طراحی شده، با چند خط ماژیک تسلیم نمی‌شود.

وقتی هارا و همکارش QR را در سال ۱۹۹۴ معرفی کردند، به حل مشکلی صنعتی می‌اندیشیدند و نمی‌توانستند تمام کاربردهای آینده‌ی دستاوردشان را پیش‌بینی کنند.

یکی از دلایل موفقیت جهانی QR به تصمیم دنسو برای عمومی‌کردن مشخصات فنی بازمی‌گشت. شرکت باوجود در اختیار داشتن حقوق ثبت اختراع، اعلام کرد جلوی استفاده‌ی دیگران از فناوری استاندارد QR را نمی‌گیرد و به‌این‌ترتیب سایر شرکت‌ها توانستند بدون پرداخت هزینه‌ی مجوز، کدهای کیوآر را در محصولات و خدماتشان به کار بگیرند.

کدی که ابتدا برای مدیریت قطعات خودرو متولد شده بود، به‌تدریج به صنایع غذایی، دارویی و حمل‌ونقل راه یافت و از اوایل دهه‌ی ۲۰۰۰، ورود قابلیت اسکن QR به تلفن‌های همراه نیز راه را برای استفاده‌ی عمومی هموار ساخت. سرانجام این فناوری از کارخانه‌ها بیرون آمد و روی بلیت‌ها، بسته‌بندی‌ها، پوسترها، منوها و صفحه‌های نمایش جای گرفت.

امروز وقتی گوشی را مقابل یک QR مخدوش می‌گیریم، زنجیره‌ای از رویدادها در کسری از ثانیه پشت‌سرهم رخ می‌دهند. دوربین تصویر را ثبت می‌کند، نرم‌افزار الگوهای موقعیت‌یابی را می‌یابد، شبکه‌ی مربع‌ها را تشخیص می‌دهد و خانه‌ها را به داده‌های دیجیتال تبدیل می‌کند.

اگر بخشی از داده‌ها اشتباه خوانده شده باشند، الگوریتم تصحیح خطا تلاش می‌کند مقدار درستشان را بازسازی کند. کد QR آسیب را نادیده نمی‌گیرد، از ابتدا طوری طراحی شده که مقدار مشخصی از خرابی را تاب بیاورد.