QR कोड चरण-दर-चरण कैसे बनता है

• टेक्स्ट किस तरह QR कोड में बदलता है, इसे 0~9 चरणों के visualization के साथ देखते हुए Nayuki QR Code generator library के काम करने के तरीके को समझा जा सकता है
• उदाहरण इनपुट Hello, world! 123 को 17 Unicode code points के रूप में विश्लेषित किया जाता है, और Numeric·Alphanumeric·Kanji नहीं बल्कि Byte mode में encode किया जाता है
• mode bits, character count, segment data और terminator bits को जोड़ने पर 19 data codewords बनते हैं, जो Version 1 की ECC L capacity में फिट हो जाते हैं
• Version 1 QR कोड में 1 block पर 19 data codewords और Reed–Solomon ECC codewords के 7 codewords जोड़े जाते हैं, फिर fixed patterns और data modules को place किया जाता है
• 8 masks की penalty की तुलना करके सबसे कम कुल score वाले Mask pattern 3 को चुना जाता है, यानी अंतिम परिणाम सिर्फ simple encoding नहीं बल्कि quality evaluation के बाद तय होता है

---

डेमो का उद्देश्य और इनपुट प्रोसेसिंग

• यह web application टेक्स्ट string को QR कोड में encode करने की प्रक्रिया को चरण-दर-चरण visualize करता है
• यह पेज QR Code generator library के internal working को समझने के लिए encoding प्रक्रिया को खोलकर दिखाता है
• user input items में text string, error correction level, minimum Version force करना, और mask pattern force करना शामिल है

चरण 0: Unicode characters का विश्लेषण

• उदाहरण string Hello, world! 123 है, और input text में code points की संख्या 17 है
• हर character के लिए जांचा जाता है कि उसे Numeric, Alphanumeric, Byte, Kanji mode में encode किया जा सकता है या नहीं
• पूरे string के लिए mode के अनुसार encodability इस प्रकार है
  • Numeric: संभव नहीं
  • Alphanumeric: संभव नहीं
  • Byte: संभव
  • Kanji: संभव नहीं
• पूरे characters को समेटने के लिए चुना गया segment mode Byte है

चरण 1: data segment बनाना

• हर character को bit string में बदला जाता है
• Numeric और Alphanumeric mode में लगातार आने वाले characters को समूह में encode किया जाता है
• Byte mode में एक character 8, 16, 24, 32 bits में से कोई एक उत्पन्न करता है
• इस उदाहरण में हर character की hexadecimal value को 8 bits में बदला जाता है
  • H: 48 → 01001000
  • e: 65 → 01100101
  • 1: 31 → 00110001
  • 2: 32 → 00110010
  • 3: 33 → 00110011
• सरलता के लिए demo program हमेशा single segment बनाता है
• total bit length को कम करने वाली optimal splitting method पर अलग से optimal text segmentation for QR codes में चर्चा की गई है

चरण 2: Version number फिट करना

• segment list को represent करने के लिए जरूरी कुल bit length, Version range के अनुसार बदलती है
  • Version 1~9: 148 bits, 19 codewords
  • Version 10~26: 156 bits, 20 codewords
  • Version 27~40: 156 bits, 20 codewords
• codeword को 8 bits, यानी 1 byte के रूप में define किया जाता है
• QR कोड की data codeword capacity, Version और error correction level के अनुसार बदलती है
• उदाहरण इनपुट चुने गए error correction level पर Version 1 में फिट हो जाता है
• अंतिम चुना गया Version number 1 है

चरण 3: segments जोड़ना, padding, और codewords बनाना

• कई bit strings को जोड़कर data bit string बनाई जाती है
  • Segment 0 mode: 0100, 4 bits
  • Segment 0 count: 00010001, 8 bits
  • Segment 0 data: 136 bits
  • Terminator: 0000, 4 bits
• cumulative bit count 152 bits है
• इस उदाहरण में Bit padding और Byte padding दोनों 0 bits हैं
• पूरे data codeword bytes को 8-bit units में बांटकर hexadecimal में दिखाया जाता है
  • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30

चरण 4: block division, ECC जोड़ना, interleave

• उदाहरण के block statistics इस प्रकार हैं
  • data codewords की संख्या: 19
  • blocks की संख्या: 1
  • छोटे block प्रति data codewords: 19
  • लंबे block प्रति data codewords: लागू नहीं
  • block प्रति ECC codewords: 7
  • छोटे blocks की संख्या: 1
  • लंबे blocks की संख्या: 0
• data codeword sequence को छोटे blocks और लंबे blocks में बांटा जाता है, और हर block के अंत में ECC codewords की गणना करके जोड़े जाते हैं
• Reed–Solomon error correction code की mathematical calculation लंबी, उबाऊ और कम रोचक होने के कारण छोड़ी गई है
• final codeword sequence data और ECC codewords को interleave करके बनती है
  • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30 85 A9 5E 07 0A 36 C9
• zigzag scan में draw होने वाली अंतिम bit string भी इसी codeword sequence से बनती है

चरण 5~6: fixed patterns और codeword placement

• fixed pattern चरण में row 6 और column 6 पर timing pattern बनाया जाता है
• तीनों corners पर separator सहित 8×8 finder pattern रखा जाता है
• finder के आसपास temporary dummy format bits डाले जाते हैं
• codeword placement चरण में bottom-right corner से शुरू होने वाला zigzag scan निकाला जाता है
• zigzag scan function modules को छोड़ते हुए अभी तक unfilled modules पर जाता है
• data, ECC, और remainder modules अंतिम codeword bit values और zigzag order के अनुसार draw किए जाते हैं
• उदाहरण के तौर पर hexadecimal codeword C5 का binary रूप 11000101 है, और यह [dark, dark, light, light, light, dark, light, dark] module sequence बनाता है

चरण 7~9: mask apply करना और penalty calculation

• हर mask pattern केवल non-function modules को प्रभावित करता है
• mask को data, ECC, remainder modules पर XOR के रूप में apply किया जाता है
• actual format bits finder के आसपास draw किए जाते हैं
• penalty search में निम्न तत्वों की जांच की जाती है
  • एक ही रंग के 5 या अधिक लगातार आने वाले horizontal runs
  • एक ही रंग के 5 या अधिक लगातार आने वाले vertical runs
  • एक ही रंग के 2×2 boxes
  • horizontal finder-like patterns
  • vertical finder-like patterns
  • dark modules और light modules का balance
• उदाहरण QR कोड का size और color ratio इस प्रकार है
  • एक भुजा की लंबाई: 21
  • कुल modules: 441
  • light modules: 221
  • dark modules: 220
  • dark modules ratio: 49.887%
  • आधे के मुकाबले deviation: −0.113%
• 8 masks की total penalty इस प्रकार है
  • Mask 0: 1204
  • Mask 1: 1134
  • Mask 2: 1084
  • Mask 3: 1081
  • Mask 4: 1121
  • Mask 5: 1100
  • Mask 6: 1189
  • Mask 7: 1137
• सबसे कम total penalty वाला mask Mask pattern 3 है

source code

• web application का TypeScript source code file 0, file 1 के रूप में उपलब्ध है
• compiled JavaScript code creating-qr-code-steps.js में देखा जा सकता है

[GN⁺]

Hacker News की टिप्पणियाँ

• अफसोस है कि QR कोड की व्याख्या में ऑनलाइन लगभग हर जगह Reed-Solomon error correction calculation को छोड़ दिया जाता है
  यहाँ भी लेखक ने कहा कि यह “लंबा, उबाऊ, और खास दिलचस्प नहीं” है, लेकिन जब सब ऐसा सोचते हैं तो अब इसे ढूँढना काफ़ी मुश्किल हो गया है
  • मैंने ग्रेजुएट स्कूल में coding theory की क्लास ली थी, और वह मेरी पढ़ी हुई सबसे rigorous क्लासों में से एक थी; हम 5 लोगों के लिए यह कठिन थी, लेकिन फिर भी उसे लेना सही फैसला था
    Reed-Solomon को सेमेस्टर के थोड़ा मध्य के बाद पढ़ाया गया था, और मूल विचार यह है कि यह polynomial पर आधारित है। अगर पर्याप्त points हों तो polynomial uniquely तय हो जाती है, इसलिए अगर कुछ extra points जोड़ दिए जाएँ तो उनमें से कुछ गायब हो जाने पर भी उसे recover किया जा सकता है
    बाकी हिस्सा इसे binary data पर लागू करने का है, यानी finite fields का इस्तेमाल, जो गणितीय रूप से सुंदर है लेकिन काफ़ी जटिल भी हो जाता है
  • error correction calculation इन दो tutorials में समझाई गई है
    https://www.thonky.com/qr-code-tutorial/error-correction-cod...
    https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-...
  • https://www.quaxio.com/an_artisanal_qr_code.html और PagedOut! Issue #2 में long division के साथ error correction calculation तक शामिल करते हुए QR कोड को scratch से बनाने की सामग्री है
  • लंबा और उबाऊ है, लेकिन सच कहें तो पूरे विषय का सबसे दिलचस्प हिस्सा यही है
  • इस पर संबंधित Wikipedia लेख भी है
• Veritasium का हालिया वीडियो I used to hate QR codes. But they're actually genius भी इस विषय को कवर करता है
  https://www.youtube.com/watch?v=w5ebcowAJD8
• लेखक को मिली feedback का यह संकलन काफ़ी दिलचस्प है: https://www.nayuki.io/page/poor-feedback-from-readers
  • जिन लोगों की English अच्छी नहीं है उनका मज़ाक उड़ाना, और ईमेल भेजने वालों को जैसे उस देश का प्रतिनिधि नमूना मानकर पूरे देश को नीचा दिखाने वाली टिप्पणी करना, यह भेजने वालों से ज़्यादा ब्लॉग चलाने वाले के बारे में बताता है
    टिप्पणियों में एक elitist लहजा काफ़ी साफ़ महसूस होता है। ब्लॉग को सरसरी तौर पर देखने पर लगा कि वह Bitcoin donation माँगते हुए $3 सुझाता है, लेकिन शायद यह नहीं सोचता कि fees में उसका बड़ा हिस्सा चला जा सकता है
  • अगर आपको कोई संदेश पसंद नहीं आया, तब भी शिकायत करते समय हल्का नस्लवाद और लेखक की English क्षमता की आलोचना को मिलाना बेहतर नहीं है
  • टूटी-फूटी English का मज़ाक उड़ाना हमेशा मूर्खता का संकेत होता है। होशियार लोग भी मूर्खों जैसा व्यवहार कर सकते हैं
  • माफ़ कीजिए, लेकिन ब्लॉग लेखक काफ़ी खराब इंसान जैसा लगता है
    कुछ ऐसा भाव आता है: “नहीं, तुम अपने कॉलेज प्रोजेक्ट chatbot में मेरे GitHub repository का code इस्तेमाल नहीं कर सकते। तुम्हारे coding standards मेरे स्तर के नहीं हैं। और तुम्हारी English भी खराब है”
  • मैं समझ सकता हूँ कि personal blog चलाना कितना कठिन हो सकता है। आपको हर तरह के लोगों से जूझना पड़ता है
    अच्छी बात यह है कि उसने अच्छा feedback भी अलग से साझा किया है: https://www.nayuki.io/page/decent-feedback-from-readers
• काफ़ी बढ़िया है। मैं यही चीज़ decoder के लिए भी देखना चाहूँगा
  • आपको Piko और blinry की वह guide भी पसंद आ सकती है जिसमें बिना कंप्यूटर के QR कोड पढ़ने का तरीका बताया गया है: https://qr.blinry.org/
  • सहमत। जब फ़ोन अंधेरा, धुंधला, और लगभग 1/4 हिस्सा स्क्रीन के बाहर निकले हुए QR कोड को भी इतनी जल्दी decode कर देता है, तो मैं हमेशा हैरान रह जाता हूँ
  • मैं लगातार ऐसी guide ढूँढ रहा हूँ जो QR reader को 0 से implement करना सिखाए
    मुझे Google पर दिखने वाले “बस यह computer vision library जोड़ो, image दो, और result ले लो” वाले तरीके नहीं चाहिए
    मैं ऐसी guide चाहता हूँ जो यह मानकर चले कि decoded raw image data पहले से मौजूद है, और फिर ज़रूरी सारे algorithms को implement करके आगे बढ़े
• अच्छा लगा कि इसमें explanation है। मैं तो बस इसे जल्दी बनाना चाहता था, लेकिन search करने पर ads से भरी sites या “साइन अप करो तभी इस्तेमाल कर सकते हो” वाली sites ही मिलीं
  GitHub पर भी कुछ मिले, लेकिन उनमें दूसरी समस्याएँ थीं, इसलिए मैंने पहले इस्तेमाल की हुई एक अच्छी तरह designed library से खुद जल्दी बना लिया, और लगभग 15 मिनट लगे
  https://greggman.github.io/qr-code/
  और options जोड़े जा सकते हैं, लेकिन सच कहूँ तो ज़्यादातर users को शायद उनकी ज़रूरत नहीं होगी
  • यह उपयोगी लगा, यह सुनकर खुशी हुई। मैं भी कुछ समय से implementation खुद आज़माना चाहता था, लेकिन मुझे सिर्फ Python या Golang के ready-made packages ही मिल पाए
    QR कोड के संदर्भ में अगर error correction वाले हिस्से को समझने के लिए कोई उपयोगी सामग्री हो, तो मैं उसके बारे में जानना चाहूँगा
• मैंने पहले एक Rust implementation बनाई थी
  https://github.com/aabiji/qr
  • मैंने पहले एक PDP-10 assembly implementation बनाई थी
    https://github.com/PDP-10/its/blob/master/src/lars/qrcode.8
• अगर यह इस साल की पोस्ट नहीं है, तो शीर्षक में पोस्ट का वर्ष, यहाँ 2018, जोड़ना एक अच्छा convention है
  • सहमत। जहाँ तक मैं देख पाया, मूल लिंक पर तारीख नहीं थी, और अब इसे बदला भी नहीं जा सकता
• बढ़िया। QR कोड कैसे काम करते हैं यह सीखना बहुत समय से मेरी to-do list में था, और यह एक अच्छा introductory लेख था
• अब जब आपको इसका काम करने का तरीका पता है, तो आप इसे SQL query में भी इस्तेमाल कर सकते हैं: https://github.com/Florents-Tselai/pgQR