Cách tạo mã QR từng bước

 (nayuki.io)
5 điểm bởi GN⁺ 2024-11-19 | 1 bình luận | Chia sẻ qua WhatsApp
  • Theo dõi quá trình nội bộ khi văn bản được chuyển thành mã QR qua phần trực quan hóa từ bước 0 đến 9, có thể xem nguyên lý hoạt động của thư viện Nayuki QR Code generator
  • Chuỗi nhập ví dụ Hello, world! 123 được phân tích thành 17 code point Unicode và được mã hóa ở chế độ Byte, không phải Numeric, Alphanumeric hay Kanji
  • Sau khi nối các bit chế độ, số ký tự, dữ liệu segment và bit kết thúc, tạo ra 19 codeword dữ liệu, vừa khớp với dung lượng ECC L của Version 1
  • Mã QR Version 1 gắn 19 codeword dữ liệu và 7 codeword ECC Reed–Solomon vào 1 khối, rồi bố trí các mẫu cố định và module dữ liệu
  • So sánh penalty của 8 mask và chọn Mask pattern 3 có tổng điểm thấp nhất; kết quả cuối cùng không chỉ là mã hóa đơn thuần mà còn được quyết định sau bước đánh giá chất lượng

Mục đích của demo và xử lý đầu vào

  • Ứng dụng web này trực quan hóa từng bước quá trình một chuỗi văn bản được mã hóa thành mã QR
  • Trang này diễn giải quá trình mã hóa để có thể hiểu hoạt động nội bộ của QR Code generator library
  • Các mục nhập của người dùng gồm chuỗi văn bản, mức sửa lỗi, ép Version tối thiểu và ép mẫu mask

Bước 0: Phân tích ký tự Unicode

  • Chuỗi ví dụ là Hello, world! 123, và số code point của văn bản nhập là 17
  • Mỗi ký tự được kiểm tra xem có thể mã hóa trong các chế độ Numeric, Alphanumeric, Byte, Kanji hay không
  • Khả năng mã hóa của toàn bộ chuỗi theo từng chế độ như sau
    • Numeric: không thể
    • Alphanumeric: không thể
    • Byte: có thể
    • Kanji: không thể
  • Chế độ segment được chọn để chứa toàn bộ ký tự là Byte

Bước 1: Tạo segment dữ liệu

  • Mỗi ký tự được chuyển thành chuỗi bit
  • Ở chế độ Numeric và Alphanumeric, các ký tự liên tiếp được gom lại để mã hóa
  • Ở chế độ Byte, một ký tự tạo ra một trong các độ dài 8, 16, 24, 32 bit
  • Trong ví dụ, giá trị thập lục phân của từng ký tự được chuyển thành 8 bit
    • H: 48 → 01001000
    • e: 65 → 01100101
    • 1: 31 → 00110001
    • 2: 32 → 00110010
    • 3: 33 → 00110011
  • Chương trình demo luôn tạo một segment duy nhất để đơn giản hóa
  • Cách phân tách tối ưu nhằm giảm tổng độ dài bit được trình bày riêng trong optimal text segmentation for QR codes

Bước 2: Khớp số Version

  • Tổng độ dài bit cần thiết để biểu diễn danh sách segment thay đổi theo phạm vi Version
    • Version 1~9: 148 bit, 19 codeword
    • Version 10~26: 156 bit, 20 codeword
    • Version 27~40: 156 bit, 20 codeword
  • Codeword được định nghĩa là 8 bit, tức 1 byte
  • Dung lượng codeword dữ liệu của mã QR thay đổi theo Version và mức sửa lỗi
  • Đầu vào ví dụ vừa khớp với Version 1 ở mức sửa lỗi đã chọn
  • Số Version cuối cùng được chọn là 1

Bước 3: Nối segment, padding và tạo codeword

  • Nối nhiều chuỗi bit lại để tạo chuỗi bit dữ liệu
    • Segment 0 mode: 0100, 4 bit
    • Segment 0 count: 00010001, 8 bit
    • Segment 0 data: 136 bit
    • Terminator: 0000, 4 bit
  • Tổng số bit tích lũy là 152 bit
  • Trong ví dụ, cả bit padding và byte padding đều là 0 bit
  • Toàn bộ byte codeword dữ liệu được chia theo đơn vị 8 bit và hiển thị ở dạng thập lục phân
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30

Bước 4: Chia khối, thêm ECC và interleave

  • Thống kê khối của ví dụ như sau
    • Số codeword dữ liệu: 19
    • Số khối: 1
    • Codeword dữ liệu trên mỗi khối ngắn: 19
    • Codeword dữ liệu trên mỗi khối dài: không áp dụng
    • Codeword ECC trên mỗi khối: 7
    • Số khối ngắn: 1
    • Số khối dài: 0
  • Chuỗi codeword dữ liệu được chia thành khối ngắn và khối dài, rồi tính và gắn codeword ECC vào cuối mỗi khối
  • Quá trình toán học để tính mã sửa lỗi Reed–Solomon bị lược bỏ vì dài, tẻ nhạt và không thú vị
  • Chuỗi codeword cuối cùng được cấu thành bằng cách interleave codeword dữ liệu và ECC
    • 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
  • Chuỗi bit cuối cùng sẽ được vẽ theo quét zigzag cũng được tạo từ chuỗi codeword này

Bước 5~6: Bố trí mẫu cố định và codeword

  • Ở bước mẫu cố định, vẽ timing pattern tại hàng 6 và cột 6
  • Ở ba góc, đặt finder pattern 8×8 bao gồm cả separator
  • Quanh finder có các dummy format bits tạm thời
  • Ở bước bố trí codeword, tính quét zigzag bắt đầu từ góc dưới bên phải
  • Quét zigzag bỏ qua các module chức năng (function module) và đi qua các module chưa được điền
  • Các module dữ liệu, ECC và remainder được vẽ theo giá trị bit của codeword cuối cùng và thứ tự zigzag
  • Ví dụ, codeword thập lục phân C5 là nhị phân 11000101, tạo ra chuỗi module [dark, dark, light, light, light, dark, light, dark]

Bước 7~9: Áp dụng mask và tính penalty

  • Mỗi mẫu mask chỉ ảnh hưởng đến các module không phải chức năng (non-function module)
  • Mask được áp dụng cho các module dữ liệu, ECC và remainder bằng phép XOR
  • Format bits thực tế được vẽ quanh finder
  • Quá trình tìm penalty kiểm tra các yếu tố sau
    • Run ngang có từ 5 module cùng màu trở lên liên tiếp
    • Run dọc có từ 5 module cùng màu trở lên liên tiếp
    • Box 2×2 cùng màu
    • Mẫu ngang giống finder
    • Mẫu dọc giống finder
    • Cân bằng giữa module tối và module sáng
  • Kích thước và tỷ lệ màu của mã QR ví dụ như sau
    • Độ dài một cạnh: 21
    • Tổng số module: 441
    • Module sáng: 221
    • Module tối: 220
    • Tỷ lệ module tối: 49.887%
    • Độ lệch so với một nửa: −0.113%
  • Tổng penalty của 8 mask như sau
    • 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 có tổng penalty thấp nhất là Mask pattern 3

Mã nguồn

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-11-19
Ý kiến trên Hacker News
  • Thật tiếc là ở đâu trên mạng cũng có vẻ bỏ qua phần tính toán sửa lỗi Reed-Solomon khi giải thích về mã QR
    Ở đây tác giả cũng nói nó “dài, chán và không mấy thú vị”, nhưng vì ai cũng nghĩ vậy nên giờ tìm nội dung này khá khó
    • Ở cao học tôi từng học môn lý thuyết mã hóa, và đó là môn chặt chẽ nhất trong các môn tôi từng học; cả 5 người đều thấy khó, nhưng tôi nghĩ mình đã đúng khi học nó
      Reed-Solomon được học sau khoảng hơn nửa học kỳ một chút, và cốt lõi là nó dựa trên đa thức. Nếu có đủ điểm thì đa thức được xác định chính xác, nên nếu thêm các điểm dư thừa, ta có thể khôi phục ngay cả khi một số điểm biến mất
      Phần còn lại là cách áp dụng điều đó vào dữ liệu nhị phân, tức là phần dùng trường hữu hạn; nó đẹp về mặt toán học nhưng trở nên khá phức tạp
    • Hai hướng dẫn này giải thích phần tính toán sửa lỗi
      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 và PagedOut! Issue #2 có nội dung tạo mã QR từ đầu, bao gồm cả tính toán sửa lỗi bằng phép chia dài
    • Nó dài và chán, nhưng thực ra là phần thú vị nhất trong toàn bộ thứ này
    • Có một bài viết Wikipedia liên quan
  • Video Veritasium gần đây I used to hate QR codes. But they're actually genius cũng nói về chủ đề này
    https://www.youtube.com/watch?v=w5ebcowAJD8
  • Bộ sưu tập phản hồi mà tác giả nhận được khá thú vị: https://www.nayuki.io/page/poor-feedback-from-readers
    • Việc chế giễu những người không giỏi tiếng Anh và đưa ra những bình luận hạ thấp cả một quốc gia như thể những người gửi email là mẫu đại diện của nước đó cho thấy nhiều điều về chủ blog hơn là về những người gửi
      Tôi cảm nhận rõ không khí tinh hoa chủ nghĩa trong các bình luận. Lướt qua blog thì thấy tác giả xin quyên góp Bitcoin và đề xuất $3, nhưng có vẻ không tính đến việc một phần đáng kể có thể mất vào phí giao dịch
    • Dù nhận được những tin nhắn không thích, tốt hơn là khi phàn nàn đừng trộn thêm phân biệt chủng tộc nhẹ và chỉ trích khả năng tiếng Anh của người viết
    • Chế giễu tiếng Anh kém luôn là dấu hiệu của sự ngốc nghếch. Người thông minh cũng có thể hành xử như kẻ ngốc
    • Xin lỗi, nhưng người viết blog trông có vẻ là một người khá tệ
      Cảm giác như: “Không, bạn không được dùng mã trong kho GitHub của tôi cho chatbot dự án đại học của bạn. Tiêu chuẩn lập trình của bạn không đạt tiêu chuẩn của tôi. Và tiếng Anh của bạn cũng tệ nữa”
    • Có thể hiểu việc vận hành blog cá nhân có thể vất vả đến mức nào. Phải đối phó với đủ loại người
      May là tác giả cũng chia sẻ riêng những phản hồi tốt: https://www.nayuki.io/page/decent-feedback-from-readers
  • Khá tuyệt. Tôi cũng muốn xem bộ giải mã theo cùng cách
    • Bạn cũng có thể thích hướng dẫn của Piko và blinry về cách đọc mã QR mà không cần máy tính: https://qr.blinry.org/
    • Đồng cảm. Tôi luôn ngạc nhiên khi điện thoại giải mã nhanh đến vậy cả những mã QR tối, mờ và khoảng 1/4 nằm ngoài màn hình
    • Tôi vẫn đang tìm một hướng dẫn triển khai QR reader từ con số 0
      Tôi không muốn kiểu “chỉ cần gắn thư viện computer vision này vào rồi đưa ảnh vào là có kết quả” như thấy trên Google
      Tôi đang tìm một hướng dẫn giả định rằng đã có dữ liệu ảnh thô đã được giải mã, rồi triển khai tất cả các thuật toán cần thiết
  • Có phần giải thích nên rất hay. Cá nhân tôi chỉ muốn tạo thật nhanh, nhưng khi tìm kiếm thì toàn ra các trang đầy quảng cáo hoặc trang “phải đăng ký mới dùng được”
    Tôi cũng tìm thấy vài cái trên GitHub nhưng có vấn đề khác, nên đã tự tạo nhanh bằng một thư viện được thiết kế tốt mà trước đây từng dùng, mất khoảng 15 phút
    https://greggman.github.io/qr-code/
    Có thể thêm nhiều tùy chọn hơn, nhưng thật ra tôi nghĩ đa số người dùng không cần những tùy chọn đó
    • Rất vui vì nó hữu ích. Tôi cũng đã muốn tự viết một implementation trong một thời gian, nhưng những gì tìm được chỉ là gói hoàn chỉnh cho Python hoặc Golang
      Nếu có tài liệu hữu ích nào về phần sửa lỗi liên quan đến mã QR thì tôi muốn biết
  • Trước đây tôi từng tạo một implementation bằng Rust
    https://github.com/aabiji/qr
  • Nếu bài viết không phải của năm hiện tại thì thêm năm của bài vào tiêu đề, ở đây là 2018, là một thông lệ tốt
    • Đồng ý. Theo tôi thấy thì liên kết gốc không có ngày, và giờ thì không thể sửa được nữa
  • Hay. Tìm hiểu cách mã QR hoạt động đã nằm trong danh sách việc cần làm của tôi từ lâu, và đây là một bài nhập môn tốt
  • Giờ đã biết cách nó hoạt động, bạn cũng có thể dùng trong truy vấn SQL: https://github.com/Florents-Tselai/pgQR