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

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

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

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

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

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

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

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

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

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

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

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

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

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

سه مربع گوشه‌ها، موقعیت، زاویه و جهت QR را به اسکنر نشان می‌دهند

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

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

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

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

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

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

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

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

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

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

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

رید–سالومون اطلاعات گمشده را حدس نمی‌زند؛ آن‌ها را از روی روابط ریاضی بازسازی می‌کند

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

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

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

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

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

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

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

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

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

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

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

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

افزایش مقاومت QR، فضای کمتری برای ذخیره‌ی داده‌های اصلی باقی می‌گذارد

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

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

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