PetexSpace
← Quay lại blog

Giải phẫu mã QR: Cơ chế sửa lỗi Reed-Solomon và mã hóa ma trận

PetexSpace

Mã Quick Response (QR), được tiêu chuẩn hóa quốc tế theo ISO/IEC 18004, đại diện cho một trong những hệ thống ký hiệu hai chiều bền bỉ và phổ biến nhất trong điện toán hiện đại. Được phát triển ban đầu vào năm 1994 bởi Masahiro Hara tại Denso Wave nhằm theo dõi các linh kiện ô tô trong dây chuyền lắp ráp, mã QR được thiết kế để đáp ứng hai yêu cầu khắt khe: khả năng nhận diện quang học nhanh chóng ở mọi góc quét đa hướng, cùng khả năng bảo toàn dữ liệu mạnh mẽ trước những hư hỏng vật lý nghiêm trọng, vết bẩn và rách nát.

Khác với mã vạch một chiều vốn chỉ mã hóa thông tin dọc theo một trục không gian nằm ngang duy nhất, mã QR hoạt động như một ma trận phẳng rời rạc gồm các phần tử vuông sáng và tối được gọi là "module". Tầng truyền tải dữ liệu nền tảng tích hợp đại số trừu tượng trường hữu hạn, cụ thể là mã sửa lỗi Reed-Solomon được tính toán trên trường Galois GF(28)GF(2^8). Nền tảng đại số này cho phép bộ giải mã tái tạo dữ liệu bị mất, bị che khuất hoặc bị biến dạng mà không cần truyền lại.

Khi xây dựng các nền tảng web hiện đại, các kỹ sư thường xuyên cần các tiện ích để tạo mã QR chuẩn ISO trực tiếp cho các khóa bí mật xác thực, hồ sơ mạng hoặc trao đổi dữ liệu. Ngược lại, việc xác minh tải trọng ma trận và kiểm tra cấu trúc byte đòi hỏi các công cụ để giải mã QR client-side, đảm bảo dữ liệu nhạy cảm được giữ kín hoàn toàn trên thiết bị người dùng mà không bị truyền qua mạng bên ngoài.

1. Cấu trúc hình học của ma trận ISO/IEC 18004

Ma trận mã QR theo chuẩn ISO/IEC 18004 được cấu trúc trên một lưới tọa độ Descartes nghiêm ngặt. Kích thước vật lý dao động từ Version 1 (21×2121 \times 21 module) lên đến Version 40 (177×177177 \times 177 module). Mỗi phiên bản tiếp theo sẽ tăng kích thước lưới thêm đúng 4 module cho mỗi cạnh:

Dimension(V)=21+4(V−1)=17+4V\text{Dimension}(V) = 21 + 4(V - 1) = 17 + 4V

Trong đó V∈[1,40]V \in [1, 40] biểu thị phiên bản ma trận.

Bề mặt ma trận được phân chia có hệ thống giữa các mẫu chức năng (giúp định vị hình học, đồng bộ hóa và hiệu chỉnh góc nhìn) cùng vùng mã hóa (chứa các codeword dữ liệu, byte chẵn lẻ sửa lỗi, thông tin định dạng và chỉ thị phiên bản).

   +-----------------------------------------------------------------------+
   | [FINDER 1]                      [TIMING HORIZONTAL]        [FINDER 2] |
   |  7x7 Pattern                     Alternating B/W            7x7       |
   |  Ratio 1:1:3:1:1                                                      |
   |                                                                       |
   |  +---------+                                             +---------+  |
   |  | ### ### |                                             | ### ### |  |
   |  | #     # |                                             | #     # |  |
   |  | # ### # |             FORMAT INFORMATION              | # ### # |  |
   |  | # ### # |             (BCH Encoded Strip)             | # ### # |  |
   |  | #     # |                                             | #     # |  |
   |  | ### ### |                                             | ### ### |  |
   |  +---------+                                             +---------+  |
   |  [SEPARATOR]                                             [SEPARATOR]  |
   |                                                                       |
   |  [TIMING VERTICAL]            [DATA & PARITY AREA]                    |
   |   Alternating B/W              Interleaved Codewords                  |
   |                                Upward/Downward 2-module tracks        |
   |                                Mask Pattern Applied                   |
   |                                                                       |
   |                                              +-----------+            |
   |                                              | ALIGNMENT |            |
   |                                              | 5x5 Grid  |            |
   |                                              +-----------+            |
   |  +---------+                                                          |
   |  | ### ### |                                                          |
   |  | #     # |                                                          |
   |  | # ### # |                                                          |
   |  | # ### # |                                                          |
   |  | #     # |                                                          |
   |  | ### ### |               VERSION INFORMATION                        |
   |  +---------+               (Versions 7-40 only, 18-bit Golay)         |
   |  [FINDER 3]                                                           |
   +-----------------------------------------------------------------------+
      QUIET ZONE (Minimum 4 Modules of Unmarked Light Space on all 4 Sides)

Mẫu định vị (Finder Patterns) và tính bất biến affine

Đặc điểm trực quan dễ nhận biết nhất là ba Mẫu định vị (Position Detection Patterns) giống hệt nhau nằm ở các góc trên-trái, trên-phải và dưới-trái. Mỗi mẫu định vị bao gồm một khối vuông tối 3×33 \times 3 ở trung tâm, bao quanh bởi đường viền sáng rộng 1 module, và ngoài cùng là đường viền tối rộng 1 module, tạo thành cấu trúc 7×77 \times 7.

Khi một đường quét cắt qua tâm của mẫu định vị ở bất kỳ góc định hướng nào (từ 0∘0^\circ đến 360∘360^\circ), tỷ lệ độ rộng giữa các module đen và trắng luôn cho kết quả:

Pattern Ratio=1:1:3:1:1\text{Pattern Ratio} = 1 : 1 : 3 : 1 : 1

Tỷ lệ này là duy nhất về mặt toán học trong ma trận. Các bộ phát hiện cạnh trong thị giác máy tính quét tìm đặc trưng nhận dạng này để cô lập biên giới ma trận, tính toán các ma trận biến đổi affine, hiệu chỉnh độ nghiêng phối cảnh và xác định hướng xoay không gian của ký hiệu trong thời gian thực.

Các mẫu cấu trúc thứ cấp

  1. Vùng phân cách (Separators): Các đường viền sáng có độ rộng 1 module bao quanh mỗi mẫu định vị, ngăn không cho các module dữ liệu làm sai lệch tỷ lệ 1:1:3:1:11:1:3:1:1.
  2. Mẫu định thời (Timing Patterns): Nằm trên hàng 6 và cột 6 (chỉ số tính từ 0) nối liền giữa các mẫu định vị. Bao gồm các module tối và sáng xen kẽ, chúng xác lập tần số lấy mẫu vật lý và khoảng cách lưới tọa độ trên toàn bộ ma trận.
  3. Mẫu căn chỉnh (Alignment Patterns): Bắt buộc có từ Version 2 trở lên. Bao gồm một cấu trúc đồng tâm 5×55 \times 5 (một điểm tối ở tâm được bao quanh bởi một vòng sáng và đường viền tối ngoài cùng). Khi phiên bản tăng dần lên đến Version 40, một lưới gồm nhiều mẫu căn chỉnh sẽ bù trừ cho độ cong bề mặt vật lý (chẳng hạn như khi quét mã QR in trên vỏ lon hình trụ hoặc giấy bị nhăn).
  4. Vùng tĩnh (Quiet Zone): Một dải khoảng trắng không bị gián đoạn có độ rộng tối thiểu 4 module bao quanh toàn bộ ranh giới ngoài cùng, đảm bảo sự cô lập quang học khỏi các khối văn bản hoặc đồ họa liền kề.

2. Các chế độ mã hóa dữ liệu và đóng gói luồng bit

Các byte dữ liệu tải trọng không được ghi trực tiếp dưới dạng ASCII thô vào ma trận. Nhằm tối đa hóa mật độ lưu trữ trên các tập ký tự khác nhau, ISO/IEC 18004 định nghĩa nhiều chế độ mã hóa chuyên biệt.

Chế độ mã hóaChỉ thị chế độTập ký tự hỗ trợSố bit mỗi ký tựHiệu suất cải thiện so với 8-bit
Numeric0001Các chữ số từ 0 đến 93.33 bits/ký tựGiảm ~58.3%
Alphanumeric001045 ký tự: 0-9, A-Z, khoảng trắng, $ % * + - . / :5.5 bits/ký tựGiảm ~31.2%
Byte0100Luồng nhị phân toàn phần ISO-8859-1 hoặc UTF-88.0 bits/ký tựMức cơ sở
Kanji1000Ký tự Shift JIS13.0 bits/ký tựGiảm ~18.7% so với 16-bit

Cơ chế nén dữ liệu

Các chế độ Numeric và Alphanumeric đạt được mật độ bit phân số thông qua việc gom nhóm chuyển đổi cơ số:

  • Nén Numeric: Chuỗi đầu vào được phân vùng thành các cụm 3 chữ số. Mỗi số nguyên 3 chữ số (000000 đến 999999) được mã hóa thành một giá trị nhị phân 10 bit (210=1024>9992^{10} = 1024 > 999). Hai chữ số còn lại (nếu có) được mã hóa thành 7 bit (27=128>992^7 = 128 > 99), và một chữ số đơn lẻ còn lại sẽ chiếm 4 bit.
  • Nén Alphanumeric: Các ký tự được ghép thành từng cặp. Với các ký tự C1C_1 và C2C_2 được ánh xạ tới các giá trị trong bảng 0≤Vi≤440 \le V_i \le 44:
Pair Value=45×V(C1)+V(C2)\text{Pair Value} = 45 \times V(C_1) + V(C_2)

Vì 45×44+44=202445 \times 44 + 44 = 2024, số nguyên thu được vừa vặn trong một từ 11 bit (211=20482^{11} = 2048), mang lại hiệu suất thực tế là 5.55.5 bit cho mỗi ký tự.

Đóng khung và đệm luồng bit

Luồng bit liên tục được đóng khung tuần tự:

  1. Chỉ thị chế độ (Mode Indicator): Tiền tố 4 bit xác định chiến lược nén.
  2. Bộ đếm số lượng ký tự (Character Count Indicator): Độ dài trường được xác định bởi phiên bản ma trận và chế độ đang hoạt động (ví dụ, 8 bit cho chế độ Byte ở các Version 1-9; 16 bit ở các Version 10-40).
  3. Các bit dữ liệu: Tải trọng ký tự đã được nén.
  4. Ký tự kết thúc (Terminator): Một chuỗi bit chứa tối đa bốn số không (0000) báo hiệu việc hoàn tất dữ liệu tải trọng.
  5. Căn chỉnh byte: Các bit 0 được thêm vào cuối cho đến khi tổng độ dài luồng bit là bội số chính xác của 8.
  6. Đệm dung lượng (Capacity Padding): Nếu các byte đã gom lại chưa lấp đầy tổng dung lượng quy định cho phiên bản và cấp độ sửa lỗi đã chọn, bộ mã hóa sẽ liên tục xen kẽ giữa hai byte đệm tiêu chuẩn:
Pad Byte 1=0xEC=111011002\text{Pad Byte 1} = 0xEC = 11101100_2 Pad Byte 2=0x11=000100012\text{Pad Byte 2} = 0x11 = 00010001_2

Chuỗi xen kẽ này duy trì sự cân bằng đồng đều giữa các module tối và sáng trên các khối lưu trữ chưa dùng, tránh tạo ra các vùng lớn không có biến đổi tín hiệu.

3. Số học trường Galois: GF(28)GF(2^8) và toán học đa thức

Động cơ toán học giúp mã QR tồn tại nguyên vẹn trước hư hỏng là mã sửa lỗi đại số Reed-Solomon. Reed-Solomon hoạt động trên các ký hiệu thay vì các bit riêng lẻ. Trong ISO/IEC 18004, mỗi ký hiệu đại diện cho một byte 8-bit.

Các phép toán số học truyền thống (cộng, nhân, chia) trên số thực hoặc số nguyên không bảo toàn phạm vi 8-bit hữu hạn mà không xảy ra tràn số hoặc mất độ chính xác. Để thực hiện các phép toán khép kín trên cấu trúc byte chính xác, mã QR sử dụng lý thuyết trường Galois, cụ thể là trường hữu hạn chứa 28=2562^8 = 256 phần tử: GF(28)GF(2^8).

Xây dựng trường và đa thức nguyên thủy

Trong GF(28)GF(2^8), các phần tử được biểu diễn dưới dạng đa thức có bậc tối đa là 7 với các hệ số nhị phân:

A(x)=a7x7+a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0trong đoˊ ai∈{0,1}A(x) = a_7 x^7 + a_6 x^6 + a_5 x^5 + a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0 \quad \text{trong đó } a_i \in \{0, 1\}

Khi nhân hai đa thức 8-bit, tích số có thể đạt tới bậc 14, vượt quá giới hạn của một byte 8-bit. Để duy trì tính khép kín, tích số được rút gọn theo modulo của một đa thức nguyên thủy bất khả quy p(x)p(x) không thể phân tích thành nhân tử trong trường. Chuẩn ISO/IEC 18004 định nghĩa p(x)p(x) là:

p(x)=x8+x4+x3+x2+1p(x) = x^8 + x^4 + x^3 + x^2 + 1

Trong hệ thập lục phân, đa thức này tương ứng với 0x11D (hoặc 285 ở hệ thập phân).

Các phép toán trên trường

  1. Phép cộng và phép trừ: Trong các trường hữu hạn có đặc số 2, phép cộng và phép trừ là như nhau và tương đương với phép toán XOR bit (⊕\oplus):
A+B=A−B=A⊕BA + B = A - B = A \oplus B

Điểm mấu chốt là không có phép nhớ nào diễn ra qua ranh giới bit.

  1. Phép nhân qua bảng Log và Antilog: Phép nhân đa thức trực tiếp đi kèm rút gọn modulo với p(x)p(x) đòi hỏi chi phí tính toán rất lớn trong quá trình mã hóa thời gian thực. Thay vào đó, do GF(28)GF(2^8) có tính cyclic, mọi phần tử khác 0 trong trường đều có thể biểu diễn dưới dạng lũy thừa của một phần tử sinh nguyên thủy α=2\alpha = 2 (00000010200000010_2).

Với hai phần tử bất kỳ khác 0 là A=αiA = \alpha^i và B=αjB = \alpha^j:

A×B=αi×αj=α(i+j)(mod255)A \times B = \alpha^i \times \alpha^j = \alpha^{(i + j) \pmod{255}}

Bằng cách tính toán trước hai bảng tra cứu gồm 256 phần tử (một bảng lũy thừa/antilog expTable ánh xạ k→αkk \to \alpha^k và một bảng logarit rời rạc logTable ánh xạ αk→k\alpha^k \to k), phép nhân được rút gọn thành các phép tra bảng với thời gian không đổi:

function gfMultiply(a: number, b: number, expTable: Uint8Array, logTable: Uint8Array): number {
  if (a === 0 || b === 0) return 0;
  const exponent = (logTable[a] + logTable[b]) % 255;
  return expTable[exponent];
}
                     GALOIS FIELD GF(2^8) MULTIPLICATION
   Byte A ----------------> logTable[A] --------+
                                               |
                                               v
                                         [ Integer Addition ]
                                         [ Modulo 255       ]
                                               |
                                               v
   Byte B ----------------> logTable[B] --------+----> expTable[Sum] ----> Product

Thiết lập đa thức sinh

Để tạo ra ee byte chẵn lẻ sửa lỗi cho một khối dữ liệu nhất định, bộ mã hóa xây dựng một đa thức sinh g(x)g(x). Các nghiệm của đa thức là các lũy thừa liên tiếp của phần tử trường nguyên thủy α\alpha:

g(x)=∏i=0e−1(x−αi)=(x−α0)(x−α1)(x−α2)…(x−αe−1)g(x) = \prod_{i=0}^{e-1} (x - \alpha^i) = (x - \alpha^0)(x - \alpha^1)(x - \alpha^2)\dots(x - \alpha^{e-1})

Ví dụ, việc tạo ra 2 byte sửa lỗi (e=2e = 2) đòi hỏi khai triển:

g(x)=(x−1)(x−α)=x2−(1+α)x+α=x2+(α0⊕α1)x+α1g(x) = (x - 1)(x - \alpha) = x^2 - (1 + \alpha)x + \alpha = x^2 + (\alpha^0 \oplus \alpha^1)x + \alpha^1

Vì α0=1\alpha^0 = 1 và α1=2\alpha^1 = 2, ta có 1⊕2=3=α251 \oplus 2 = 3 = \alpha^{25}, suy ra:

g(x)=x2+α25x+α1g(x) = x^2 + \alpha^{25}x + \alpha^1

Phép chia đa thức tổng hợp

Giả sử luồng dữ liệu gồm kk byte được biểu diễn dưới dạng đa thức thông điệp M(x)M(x) có bậc k−1k - 1:

M(x)=mk−1xk−1+mk−2xk−2+⋯+m1x+m0M(x) = m_{k-1}x^{k-1} + m_{k-2}x^{k-2} + \dots + m_1 x + m_0

Đa thức thông điệp được dịch trái ee vị trí (nhân với xex^e) để tạo khoảng trống cho các ký hiệu chẵn lẻ:

xeM(x)=Q(x)g(x)+R(x)x^e M(x) = Q(x) g(x) + R(x)

Trong đó R(x)R(x) là đa thức dư có bậc tối đa là e−1e - 1. Các hệ số của đa thức dư R(x)R(x) này chính là các codeword chẵn lẻ Reed-Solomon chuẩn xác được nối tiếp vào luồng dữ liệu.

/**
 * Computes Reed-Solomon parity codewords for a given data buffer over GF(2^8).
 */
export function computeReedSolomonParity(
  data: Uint8Array,
  parityCount: number,
  expTable: Uint8Array,
  logTable: Uint8Array,
  generatorPoly: Uint8Array
): Uint8Array {
  const remainder = new Uint8Array(parityCount);

  for (let i = 0; i < data.length; i++) {
    const factor = data[i] ^ remainder[0];
    // Shift remainder register left
    for (let j = 0; j < parityCount - 1; j++) {
      remainder[j] = remainder[j + 1];
    }
    remainder[parityCount - 1] = 0;

    if (factor !== 0) {
      const logFactor = logTable[factor];
      for (let j = 0; j < parityCount; j++) {
        const genCoeff = generatorPoly[j];
        if (genCoeff !== 0) {
          const product = expTable[(logTable[genCoeff] + logFactor) % 255];
          remainder[j] ^= product;
        }
      }
    }
  }

  return remainder;
}

4. Các cấp độ sửa lỗi và kỹ thuật xen kẽ khối Reed-Solomon

Chuẩn ISO/IEC 18004 quy định bốn cấp độ sửa lỗi (Error Correction Levels) khác nhau, cho phép các kỹ sư cân đối giữa mật độ thông tin và khả năng phục hồi vật lý.

Cấp độ ECTỷ lệ byte chẵn lẻDung lượng phục hồi xấp xỉKịch bản triển khai điển hình
Cấp L (Low)~7% tổng số codeword~7% số ký hiệu bị hỏngMàn hình hiển thị độ nét cao, sạch sẽ, màn hình di động
Cấp M (Medium)~15% tổng số codeword~15% số ký hiệu bị hỏngMặc định cho tem nhãn công nghiệp thông dụng
Cấp Q (Quartile)~25% tổng số codeword~25% số ký hiệu bị hỏngMôi trường dễ bị mài mòn mạnh hoặc bám bẩn
Cấp H (High)~30% tổng số codeword~30% số ký hiệu bị hỏngThẻ đeo có chèn logo trung tâm hoặc tác phẩm đồ họa

Giới hạn phục hồi lỗi theo toán học

Mã Reed-Solomon thuộc nhóm mã phân tách khoảng cách tối đa (Maximum Distance Separable - MDS), đạt được giới hạn singleton tối ưu về mặt lý thuyết. Đối với mã MDS có ee ký hiệu chẵn lẻ:

2t+s≤e2t + s \le e

Trong đó:

  • tt đại diện cho số lỗi ký hiệu chưa biết (cả vị trí lỗi lẫn giá trị lỗi đều không biết trước).
  • ss đại diện cho số ký hiệu bị xóa đã biết (vị trí lỗi được xác định qua thị giác do vết xước hoặc vật cản, nhưng giá trị đã mất).

Do đó, ee ký hiệu chẵn lẻ có thể sửa được tối đa:

  • t=⌊e/2⌋t = \lfloor e / 2 \rfloor lỗi ngẫu nhiên, HOẶC
  • s=es = e điểm xóa đã biết, HOẶC
  • Bất kỳ tổ hợp tuyến tính trung gian nào thỏa mãn 2t+s≤e2t + s \le e.

Kiến trúc xen kẽ khối (Block Interleaving)

Trong ma trận Version 2 trở lên, dữ liệu hiếm khi được xử lý như một khối đơn nhất. Hư hỏng vật lý thường xuất hiện dưới dạng các vết trầy xước hoặc vết bẩn trải dài trong không gian, gây ra các chuỗi lỗi liên tiếp (burst errors). Nếu một khối Reed-Solomon đơn lẻ phải chịu một vết rách liên tục dài 30 byte, ngưỡng phục hồi của khối đó sẽ bị vượt quá, khiến toàn bộ mã không thể đọc được.

Để khắc phục điều này, tiêu chuẩn phân chia dữ liệu thành các khối Nhóm 1 và Nhóm 2, tạo các byte chẵn lẻ độc lập, sau đó sắp xếp xen kẽ có hệ thống cả byte dữ liệu lẫn byte chẵn lẻ trên bố cục vật lý.

   Original Data Stream: [ D1, D2, D3, D4, D5, D6, D7, D8 ]
   Partitioned into 2 Blocks:
     Block A: [ D1, D3, D5, D7 ] --> Parity A: [ PA1, PA2 ]
     Block B: [ D2, D4, D6, D8 ] --> Parity B: [ PB1, PB2 ]

   INTERLEAVED PHYSICAL TRANSMISSION SEQUENCE:
   Data Codewords:   [ D1, D2, D3, D4, D5, D6, D7, D8 ]
   Parity Codewords: [ PA1, PB1, PA2, PB2 ]

Khi một vết xước quang học phá hủy bốn byte liên tiếp trên nhãn in (ví dụ: phá hủy các byte tại chỉ số truyền tải từ 2 đến 5: D3,D4,D5,D6D3, D4, D5, D6), kỹ thuật xen kẽ đảm bảo rằng Khối A và Khối B mỗi khối chỉ chịu hai ký hiệu bị hỏng. Nhờ mỗi khối sở hữu nhiều từ chẵn lẻ, cả hai khối đều được phục hồi thành công.

5. Bố trí ma trận, phương pháp lọc mặt nạ và kết xuất trên trình duyệt

Sau khi luồng bit xen kẽ được lắp ráp, các codeword sẽ được ánh xạ vào lưới ma trận vật lý. Quá trình bố trí bắt đầu từ góc dưới cùng bên phải và tiến lên trên theo các cột rộng 2 module. Khi chạm đến đường biên trên cùng, dải module sẽ dịch sang trái hai module và tiếp tục đi xuống, bỏ qua các mẫu chức năng đã dành riêng (mẫu định vị, mẫu định thời và mẫu căn chỉnh).

   Module Placement Vector (Zigzag 2-Column Track)
   ^  | [Col 20] [Col 19] |
   |  |   (6)      (5)   |  Upward Phase
   |  |   (4)      (3)   |
   |  |   (2)      (1)   |
   |  +-------------------+
   |  Steps left 2 columns, reverses direction
   |  +-------------------+
   v  |   (7)      (8)   |  Downward Phase
      |   (9)     (10)   |

Sự nhầm lẫn quang học và các mẫu mặt nạ (Masking Patterns)

Nếu dữ liệu thô chứa các chuỗi bit giống nhau kéo dài (chẳng hạn như các số 0 lặp lại từ phần đệm), ma trận vật lý sẽ xuất hiện các dải lớn toàn module đen hoặc trắng. Các vùng rộng không có sự biến đổi sẽ làm mất ổn định cơ chế kiểm soát độ lợi của cảm biến quang học và tạo cảm giác giả mạo mẫu định vị, gây nhầm lẫn cho logic xác định hướng của bộ giải mã.

Để đảm bảo entropy quang học đồng đều, toàn bộ vùng mã hóa được phủ mặt nạ XOR với một trong tám hàm lưới nhị phân tiêu chuẩn:

Mẫu mặt nạĐiều kiện thuật toán (Condition==0→Đảo ngược ModuleCondition == 0 \to \text{Đảo ngược Module})
000(row+col)(mod2)==0(row + col) \pmod 2 == 0
001row(mod2)==0row \pmod 2 == 0
010col(mod3)==0col \pmod 3 == 0
011(row+col)(mod3)==0(row + col) \pmod 3 == 0
100(⌊row/2⌋+⌊col/3⌋)(mod2)==0(\lfloor row / 2 \rfloor + \lfloor col / 3 \rfloor) \pmod 2 == 0
101(row×col)(mod2)+(row×col)(mod3)==0(row \times col) \pmod 2 + (row \times col) \pmod 3 == 0
110((row×col)(mod2)+(row×col)(mod3))(mod2)==0\Big((row \times col) \pmod 2 + (row \times col) \pmod 3\Big) \pmod 2 == 0
111((row+col)(mod2)+(row×col)(mod3))(mod2)==0\Big((row + col) \pmod 2 + (row \times col) \pmod 3\Big) \pmod 2 == 0

Mô hình tính điểm phạt theo ISO/IEC 18004

Bộ mã hóa tạo ra tám ma trận ứng viên bằng cách áp dụng tuần tự từng mẫu mặt nạ. Mỗi ma trận ứng viên được đánh giá dựa trên bốn công thức tính điểm phạt nghiêm ngặt (từ N1N_1 đến N4N_4):

  1. Điểm phạt N1N_1 (Các module giống nhau liền kề): Phạt các chuỗi từ 5 module trở lên có cùng màu liên tiếp trên bất kỳ hàng hoặc cột nào. Điểm số: 3+(k−5)3 + (k - 5) điểm cho một chuỗi có độ dài kk.
  2. Điểm phạt N2N_2 (Các cụm khối): Quét tìm các khối module 2×22 \times 2 có màu đồng nhất. Điểm số: 3×(m−1)(n−1)3 \times (m - 1)(n - 1) cho một khối m×nm \times n.
  3. Điểm phạt N3N_3 (Giả mạo mẫu định vị): Quét tìm sự xuất hiện của chuỗi mẫu tối-sáng 10111010000 hoặc 00001011101 trên bất kỳ hàng hoặc cột nào. Điểm số: 40 điểm cho mỗi lần xuất hiện.
  4. Điểm phạt N4N_4 (Mất cân bằng tỷ lệ sáng/tối): Tính toán phần trăm tổng số module tối PdarkP_{dark}. Đánh giá độ lệch so với phân bố lý tưởng 50%:
Deviation=∣Pdark−50∣\text{Deviation} = |P_{dark} - 50| Penalty N4=10×⌊Deviation5⌋\text{Penalty } N_4 = 10 \times \left\lfloor \frac{\text{Deviation}}{5} \right\rfloor

Ma trận ứng viên có tổng điểm thấp nhất (N1+N2+N3+N4N_1 + N_2 + N_3 + N_4) sẽ được chọn làm mẫu sản xuất tối ưu. Chỉ số mặt nạ 3-bit và cấp độ sửa lỗi 2-bit được mã hóa cùng nhau thành một chuỗi 15-bit được bảo vệ bởi mã Bose-Chaudhuri-Hocquenghem (BCH) (15,5)(15, 5), được phủ mặt nạ XOR với 101010000010010, và ghi liền kề với các mẫu định vị.

Kết xuất ma trận phía client-side

Quy trình làm việc truyền thống của các kỹ sư thường sử dụng các endpoint kết xuất trên đám mây để chuyển đổi chuỗi ký tự thành hình ảnh mã vạch. Tuy nhiên, việc truyền các khóa xác thực nội bộ, địa chỉ thiết bị mạng hoặc thông tin đăng nhập nhạy cảm qua các kết nối HTTP từ xa sẽ khiến dữ liệu quan trọng đối mặt với nguy cơ bị ghi log trung gian, lưu bộ nhớ đệm proxy và đánh chặn.

PetexSpace giải quyết vấn đề này thông qua việc thực thi hoàn toàn trong trình duyệt. Toàn bộ chu trình xử lý, từ việc tách token chuỗi UTF-8 và chia đa thức trường Galois cho đến đánh giá điểm phạt và rasterize lên canvas, đều chạy bằng TypeScript thuần túy bên trong sandbox của trình duyệt. Tận dụng ngữ cảnh HTML5 Canvas 2D tiêu chuẩn hoặc đồ họa véc-tơ Scalable Vector Graphics (SVG) có tính khai báo, quá trình kết xuất mã vạch diễn ra với tốc độ thực thi máy gốc và đảm bảo tuyệt đối không có dữ liệu đo từ xa nào gửi qua mạng.

Bài viết liên quan

CryptographyData EncodingBase32

So sánh Base32 và Base64: Khác biệt cấu trúc, quy tắc đệm và ứng dụng mật mã học

Đặc tả kỹ thuật chuyên sâu về các chuẩn mã hóa nhị phân sang văn bản theo RFC 4648, đối chiếu cơ chế đóng gói bitwise, ma trận đệm (padding), tính công thái học của bảng chữ cái và quá trình thực thi trực tiếp trên trình duyệt giữa Base32 và Base64.

PetexSpace
CryptographyXác thựcSecurity

Kiến trúc của Mật khẩu Một lần Dựa trên Thời gian: Khám phá RFC 6238 và Cơ chế Tạo HMAC

Phân tích toán học và giao thức toàn diện về Mật khẩu Một lần Dựa trên Thời gian (TOTP) theo chuẩn RFC 6238, khám phá kỹ thuật dynamic truncation, bộ đếm bước HMAC-SHA1, xử lý lệch đồng hồ và thực thi an toàn ngay trên trình duyệt.

PetexSpace
CryptographyWeb CryptoSecurity

Tính ngẫu nhiên mật mã học trong trình duyệt: Math.random so với crypto.getRandomValues

Nghiên cứu chuyên sâu về kiến trúc giữa bộ tạo số giả ngẫu nhiên (PRNG) và bộ tạo số giả ngẫu nhiên an toàn về mặt mật mã (CSPRNG) trong môi trường runtime trình duyệt, phân tích chi tiết xorshift128+, các cuộc tấn công tái tạo trạng thái và Web Cryptography API.

PetexSpace
CryptographyXác thựcKhóa truy cập

Passkey so với TOTP: Bước chuyển dịch mật mã học từ khóa bí mật dùng chung sang chữ ký khóa công khai

Phân tích kiến trúc và bảo mật so sánh giữa Mật khẩu một lần dựa trên thời gian RFC 6238 với Passkey FIDO2/WebAuthn, đi sâu vào khả năng chống tấn công phi kỹ thuật Adversary-in-the-Middle và ràng buộc nguồn gốc.

PetexSpace