วิธีสร้าง QR Code ทีละขั้นตอน

• ติดตามกระบวนการภายในที่ข้อความถูกแปลงเป็น QR Code ผ่านการแสดงภาพ ขั้นตอน 0~9 และทำความเข้าใจหลักการทำงานของ Nayuki QR Code generator library ได้
• อินพุตตัวอย่าง Hello, world! 123 ถูกวิเคราะห์เป็น Unicode code point 17 ตัว และถูกเข้ารหัสด้วย Byte mode เนื่องจากไม่ใช่ Numeric, Alphanumeric หรือ Kanji
• ผลจากการนำ mode bit, จำนวนอักขระ, segment data และ terminator bit มาเชื่อมต่อกัน ทำให้ได้ data codeword 19 ตัว ซึ่งพอดีกับความจุ ECC L ของ Version 1
• QR Code Version 1 จะนำ data codeword 19 ตัวใน 1 บล็อก มาต่อกับ Reed–Solomon ECC codeword 7 ตัว จากนั้นจึงจัดวาง fixed pattern และ data module
• เปรียบเทียบ penalty ของ mask ทั้ง 8 แบบ แล้วเลือก Mask pattern 3 ที่มีคะแนนรวมต่ำที่สุด ทำให้ผลลัพธ์สุดท้ายไม่ได้มาจากการเข้ารหัสอย่างเดียว แต่ยังผ่านการประเมินคุณภาพด้วย

---

จุดประสงค์ของเดโมและการประมวลผลอินพุต

• เว็บแอปพลิเคชันนี้แสดงภาพกระบวนการที่สตริงข้อความถูกเข้ารหัสเป็น QR Code แบบทีละขั้นตอน
• หน้าเว็บนี้คลี่ให้เห็นกระบวนการเข้ารหัสเพื่อช่วยให้เข้าใจการทำงานภายในของ QR Code generator library
• รายการอินพุตของผู้ใช้ประกอบด้วยสตริงข้อความ, ระดับการแก้ไขข้อผิดพลาด, การบังคับ Version ขั้นต่ำ และการบังคับ mask pattern

ขั้นตอนที่ 0: วิเคราะห์อักขระ Unicode

• สตริงตัวอย่างคือ Hello, world! 123 และมีจำนวน code point ของข้อความอินพุต 17 ตัว
• แต่ละอักขระจะถูกตรวจสอบว่าสามารถเข้ารหัสได้ในโหมด Numeric, Alphanumeric, Byte และ Kanji หรือไม่
• ความสามารถในการเข้ารหัสของสตริงทั้งหมดในแต่ละโหมดเป็นดังนี้
  • Numeric: ไม่ได้
  • Alphanumeric: ไม่ได้
  • Byte: ได้
  • Kanji: ไม่ได้
• โหมด segment ที่ถูกเลือกเพื่อเก็บข้อความทั้งหมดคือ Byte

ขั้นตอนที่ 1: สร้าง data segment

• อักขระแต่ละตัวจะถูกแปลงเป็นบิตสตริง
• ในโหมด Numeric และ Alphanumeric จะเข้ารหัสโดยจัดกลุ่มอักขระที่ต่อเนื่องกัน
• ในโหมด Byte อักขระหนึ่งตัวจะสร้างข้อมูลขนาด 8, 16, 24, 32 บิต อย่างใดอย่างหนึ่ง
• ในตัวอย่างนี้ ค่าเลขฐานสิบหกของแต่ละอักขระถูกแปลงเป็น 8 บิต
  • H: 48 → 01001000
  • e: 65 → 01100101
  • 1: 31 → 00110001
  • 2: 32 → 00110010
  • 3: 33 → 00110011
• โปรแกรมเดโมจะสร้าง single segment เพียงชุดเดียวเสมอเพื่อความเรียบง่าย
• วิธีแบ่ง segment ที่เหมาะสมที่สุดเพื่อลดความยาวรวมของบิต ถูกอธิบายแยกไว้ที่ optimal text segmentation for QR codes

ขั้นตอนที่ 2: ปรับให้ตรงกับหมายเลข Version

• ความยาวรวมของบิตที่ต้องใช้เพื่อแสดงรายการ segment จะแตกต่างกันตามช่วง Version
  • Version 1~9: 148 บิต, 19 codeword
  • Version 10~26: 156 บิต, 20 codeword
  • Version 27~40: 156 บิต, 20 codeword
• codeword ถูกนิยามเป็น 8 บิต หรือ 1 ไบต์
• ความจุของ data codeword ใน QR Code จะแตกต่างกันไปตาม Version และระดับการแก้ไขข้อผิดพลาด
• อินพุตตัวอย่างนี้พอดีกับ Version 1 ภายใต้ระดับการแก้ไขข้อผิดพลาดที่เลือก
• หมายเลข Version ที่ถูกเลือกสุดท้ายคือ 1

ขั้นตอนที่ 3: เชื่อม segment, เติม padding และสร้าง codeword

• นำบิตสตริงหลายชุดมาเชื่อมกันเพื่อสร้าง data bit string
  • Segment 0 mode: 0100, 4 บิต
  • Segment 0 count: 00010001, 8 บิต
  • Segment 0 data: 136 บิต
  • Terminator: 0000, 4 บิต
• จำนวนบิตสะสมคือ 152 บิต
• ในตัวอย่างนี้ทั้ง Bit padding และ Byte padding มีขนาด 0 บิต
• ไบต์ data codeword ทั้งหมดจะถูกแบ่งตามหน่วย 8 บิตและแสดงเป็นเลขฐานสิบหก
  • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30

ขั้นตอนที่ 4: แบ่งบล็อก, เพิ่ม ECC และ interleave

• สถิติของบล็อกในตัวอย่างมีดังนี้
  • จำนวน data codeword: 19
  • จำนวนบล็อก: 1
  • data codeword ต่อ short block: 19
  • data codeword ต่อ long block: ไม่มี
  • ECC codeword ต่อบล็อก: 7
  • จำนวน short block: 1
  • จำนวน long block: 0
• ลำดับของ data codeword จะถูกแบ่งเป็น short block และ long block แล้วคำนวณ ECC codeword มาต่อท้ายแต่ละบล็อก
• กระบวนการทางคณิตศาสตร์ของการคำนวณ Reed–Solomon error correction code ถูกละไว้ เพราะยาว น่าเบื่อ และไม่น่าสนใจ
• ลำดับ codeword สุดท้ายประกอบขึ้นโดยนำ data และ ECC codeword มา 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
• data bit string สุดท้ายที่จะนำไปวาดด้วยการสแกนแบบซิกแซกก็ถูกสร้างจากลำดับ codeword นี้เช่นกัน

ขั้นตอนที่ 5~6: จัดวาง fixed pattern และ codeword

• ในขั้นตอน fixed pattern จะวาด timing pattern ไว้ที่แถว 6 และคอลัมน์ 6
• ที่มุมทั้งสามจะวาง 8×8 finder pattern แต่ละชุดพร้อม separator
• รอบ finder จะมี dummy format bits ชั่วคราว
• ในขั้นตอนการจัดวาง codeword จะคำนวณ การสแกนแบบซิกแซก ที่เริ่มจากมุมล่างขวา
• การสแกนแบบซิกแซกจะข้าม function module และเยี่ยมชมเฉพาะ module ที่ยังไม่ถูกเติมค่า
• data, ECC และ remainder module จะถูกวาดตามค่าบิตของ codeword สุดท้ายและลำดับการสแกนแบบซิกแซก
• ตัวอย่างเช่น codeword เลขฐานสิบหก C5 มีค่าไบนารีเป็น 11000101 และสร้างลำดับ module เป็น [dark, dark, light, light, light, dark, light, dark]

ขั้นตอนที่ 7~9: ใช้ mask และคำนวณ penalty

• mask pattern แต่ละแบบจะมีผลเฉพาะกับ non-function module เท่านั้น
• mask จะถูกใช้กับ data, ECC และ remainder module ด้วยการ XOR
• format bits จริงจะถูกวาดไว้รอบ finder
• การค้นหา penalty จะตรวจสอบองค์ประกอบต่อไปนี้
  • run แนวนอนที่มี module สีเดียวกันต่อเนื่องกัน 5 ตัวขึ้นไป
  • run แนวตั้งที่มี module สีเดียวกันต่อเนื่องกัน 5 ตัวขึ้นไป
  • box ขนาด 2×2 ที่มีสีเดียวกัน
  • finder-like pattern แนวนอน
  • finder-like pattern แนวตั้ง
  • ความสมดุลระหว่าง dark module และ light module
• ขนาดและสัดส่วนสีของ QR Code ตัวอย่างเป็นดังนี้
  • ความยาวด้าน: 21
  • จำนวน module ทั้งหมด: 441
  • light module: 221
  • dark module: 220
  • สัดส่วน dark module: 49.887%
  • ค่าความคลาดเคลื่อนจากครึ่งหนึ่ง: −0.113%
• penalty รวมของ mask ทั้ง 8 แบบเป็นดังนี้
  • Mask 0: 1204
  • Mask 1: 1134
  • Mask 2: 1084
  • Mask 3: 1081
  • Mask 4: 1121
  • Mask 5: 1100
  • Mask 6: 1189
  • Mask 7: 1137
• mask ที่ได้ penalty รวมต่ำที่สุดคือ Mask pattern 3

ซอร์สโค้ด

• ซอร์สโค้ด TypeScript ของเว็บแอปพลิเคชันมีให้ที่ file 0, file 1
• โค้ด JavaScript ที่คอมไพล์แล้วสามารถดูได้ที่ creating-qr-code-steps.js

[GN⁺]

ความคิดเห็นจาก Hacker News

• น่าเสียดายที่คำอธิบายเรื่อง QR code ไม่ว่าดูที่ไหนออนไลน์ก็ดูเหมือนจะข้าม การคำนวณการแก้ไขข้อผิดพลาดแบบ Reed-Solomon ไป
  ที่นี่ผู้เขียนก็พูดว่า “ยาว น่าเบื่อ และไม่น่าสนใจเท่าไร” แต่พอทุกคนคิดแบบนั้น ตอนนี้เลยหาข้อมูลค่อนข้างยากแล้ว
  • ผมเคยเรียนวิชา coding theory ตอนบัณฑิตศึกษา เป็นวิชาที่เคร่งครัดทางคณิตศาสตร์ที่สุดในบรรดาวิชาที่เคยเรียน และยากสำหรับพวกเราทั้ง 5 คน แต่ผมก็คิดว่าดีแล้วที่ได้เรียน
    Reed-Solomon ถูกสอนหลังผ่านกลางเทอมไปสักพัก และใจความสำคัญคือมันอิงกับพหุนาม ถ้ามีจุดมากพอ พหุนามจะถูกกำหนดได้อย่างแน่นอน ดังนั้นถ้าใส่จุดส่วนเกินไว้ แม้บางจุดหายไปก็ยัง восстановить ได้
    ส่วนที่เหลือคือวิธีนำสิ่งนี้ไปใช้กับข้อมูลไบนารี หรือก็คือส่วนที่ใช้ฟิลด์จำกัด ซึ่งงดงามทางคณิตศาสตร์แต่ก็ค่อนข้างซับซ้อน
  • การคำนวณการแก้ไขข้อผิดพลาดมีอธิบายไว้ในสองบทเรียนนี้
    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 มีเนื้อหาเกี่ยวกับการสร้าง QR code ตั้งแต่ต้น รวมถึงการคำนวณการแก้ไขข้อผิดพลาดด้วยการหารยาว
  • มันยาวและน่าเบื่อก็จริง แต่จริง ๆ แล้วเป็น ส่วนที่น่าสนใจที่สุด ของทั้งหมด
  • มี บทความ Wikipedia ที่เกี่ยวข้องอยู่
• วิดีโอ Veritasium ล่าสุด I used to hate QR codes. But they're actually genius ก็พูดถึงหัวข้อนี้ด้วย
  https://www.youtube.com/watch?v=w5ebcowAJD8
• ชุดฟีดแบ็กที่ผู้เขียนได้รับค่อนข้างสนุกดี: https://www.nayuki.io/page/poor-feedback-from-readers
  • การล้อเลียนคนที่ภาษาอังกฤษไม่แข็งแรง และคอมเมนต์ที่ ดูถูกทั้งประเทศ ราวกับว่าคนที่ส่งอีเมลมาเป็นตัวแทนของประเทศนั้น ๆ ทั้งหมด บอกอะไรเกี่ยวกับเจ้าของบล็อกมากกว่าคนที่ส่งมา
    ในคอมเมนต์มีกลิ่นอายความเป็นชนชั้นนำแรงมาก ลองไล่ดูบล็อกคร่าว ๆ เห็นว่าเขาขอรับบริจาคเป็น Bitcoin พร้อมแนะนำ $3 แต่ดูเหมือนไม่ได้คำนึงว่าค่าธรรมเนียมอาจกินไปเป็นส่วนใหญ่
  • ต่อให้ได้รับข้อความที่ไม่ชอบ เวลาบ่นก็ควรหลีกเลี่ยงการผสม การเหยียดเชื้อชาติแบบเบา ๆ กับการวิจารณ์ทักษะภาษาอังกฤษของผู้เขียน
  • การล้อภาษาอังกฤษที่ไม่คล่องมักเป็น สัญญาณของความโง่เขลา เสมอ คนฉลาดก็ทำตัวเหมือนคนโง่ได้
  • ขอโทษนะ แต่ผู้เขียนบล็อกดูเป็นคนนิสัยไม่ค่อยดีเท่าไร
    ให้ความรู้สึกประมาณว่า “ไม่ นายเอาโค้ดจาก GitHub repository ของฉันไปใช้กับแชตบอตโปรเจกต์มหาวิทยาลัยของนายไม่ได้ มาตรฐานการเขียนโค้ดของนายไม่ถึงมาตรฐานของฉัน แถมภาษาอังกฤษของนายก็แย่มากด้วย”
  • พอเข้าใจเลยว่าการทำบล็อกส่วนตัวอาจเหนื่อยแค่ไหน ต้องรับมือกับคนสารพัดแบบ
    ยังดีที่เขาแชร์ฟีดแบ็กดี ๆ แยกไว้ด้วย: https://www.nayuki.io/page/decent-feedback-from-readers
• ค่อนข้างยอดเยี่ยม อยากเห็น ตัวถอดรหัส ในแนวเดียวกันด้วย
  • คุณอาจชอบคู่มือของ Piko และ blinry ที่ว่าด้วยวิธีอ่าน QR code โดยไม่ใช้คอมพิวเตอร์: https://qr.blinry.org/
  • เห็นด้วย ผมทึ่งเสมอเวลาเห็นโทรศัพท์ถอดรหัส QR code ที่มืด เบลอ และหลุดออกนอกจอไปประมาณ 1/4 ได้เร็วขนาดนั้น
  • ผมยังคงมองหาคู่มือการสร้าง QR reader จากศูนย์อยู่
    ไม่อยากได้แบบที่ Google เจอว่า “แค่เสียบไลบรารี computer vision นี้เข้าไปแล้วใส่ภาพ ก็ได้ผลลัพธ์ออกมา”
    อยากได้คู่มือที่สมมติว่ามีข้อมูลภาพดิบที่ถอดรหัสภาพมาแล้ว จากนั้นค่อย ๆ implement อัลกอริทึมทั้งหมดที่จำเป็น
• ดีที่มีคำอธิบาย ส่วนตัวแค่อยากสร้างให้เร็ว ๆ แต่พอค้นหาก็เจอแต่เว็บที่เต็มไปด้วยโฆษณา หรือเว็บที่ “ต้องสมัครก่อนจึงจะใช้ได้”
  บน GitHub ก็เจออยู่ไม่กี่ตัวแต่มีปัญหาอื่น เลยใช้ไลบรารีที่ออกแบบมาดีซึ่งเคยใช้มาก่อน สร้างเองแบบเร็ว ๆ ใช้เวลาประมาณ 15 นาที
  https://greggman.github.io/qr-code/
  อาจเพิ่มตัวเลือกได้อีก แต่จริง ๆ แล้วผู้ใช้ส่วนใหญ่น่าจะไม่ต้องการตัวเลือกพวกนั้น
  • ดีใจที่มีประโยชน์ ผมเองก็อยากลองเขียน implementation เองมาสักพักแล้ว แต่สิ่งที่หาได้มีแต่ แพ็กเกจสำเร็จรูป สำหรับ Python หรือ Golang
    ถ้ามีแหล่งข้อมูลที่มีประโยชน์เกี่ยวกับส่วนการแก้ไขข้อผิดพลาดของ QR code ก็อยากรู้เหมือนกัน
• เคยทำ implementation ภาษา Rust ไว้เมื่อก่อน
  https://github.com/aabiji/qr
  • เคยทำ implementation ภาษาแอสเซมบลี PDP-10 ไว้เมื่อก่อน
    https://github.com/PDP-10/its/blob/master/src/lars/qrcode.8
• ถ้าไม่ใช่บทความของปีปัจจุบัน แนวปฏิบัติที่ดีคือใส่ปีของบทความไว้ในชื่อเรื่องด้วย ซึ่งในที่นี้คือ 2018
  • เห็นด้วย ลิงก์ต้นฉบับเท่าที่ผมเห็นไม่มีวันที่ และตอนนี้แก้ไขไม่ได้แล้ว
• ดีเลย การเรียนรู้ว่า QR code ทำงานอย่างไรอยู่ในรายการสิ่งที่อยากทำมานานแล้ว และนี่เป็น บทความปูพื้นฐาน ที่ดี
• ตอนนี้รู้แล้วว่ามันทำงานอย่างไร ก็เอาไปใช้ใน SQL query ได้ด้วย: https://github.com/Florents-Tselai/pgQR