Bài 13: Mã QR bị rách vẫn quét được? Bí mật của mã sửa lỗi Reed–Solomon

Bạn đã bao giờ quét một mã QR bị dính bẩn, bị xước, thậm chí bị in đè logo ở giữa – mà điện thoại vẫn đọc đúng? Đó không phải may mắn: mã QR được thiết kế để tự sửa lỗi nhờ một thuật toán toán học từ năm 1960.

Bài thứ mười ba của chuyên mục "Thuật toán trong đời sống": mã vạch, mã QR và các mã sửa lỗi.

1. Một chữ số "canh gác" trên mã vạch

Mỗi mã vạch sản phẩm EAN-13 (GTIN-13) gồm 13 chữ số, trong đó chữ số cuối cùng là chữ số kiểm tra. Theo hướng dẫn của tổ chức GS1, chữ số này được tính như sau:

1. Nhân 12 chữ số đầu lần lượt với trọng số 1, 3, 1, 3, … (tính từ trái sang).
2. Cộng tất cả lại được tổng S.
3. Chữ số kiểm tra = số nhỏ nhất cần cộng thêm vào S để được bội của 10.

Ví dụ: 12 chữ số đầu 893123456789 (893 là tiền tố GS1 của Việt Nam). Tổng có trọng số = 8·1+9·3+3·1+1·3+2·1+3·3+4·1+5·3+6·1+7·3+8·1+9·3 = 133. Bội của 10 gần nhất ≥ 133 là 140 → chữ số kiểm tra là 7. Mã đầy đủ: 8931234567897.

Nếu máy quét đọc nhầm một chữ số bất kỳ, tổng sẽ không còn chia hết cho 10 và máy báo lỗi để quét lại. Tuy nhiên chữ số kiểm tra chỉ phát hiện lỗi, không biết lỗi ở đâu để sửa.

2. Từ phát hiện đến sửa lỗi: mã Hamming

Muốn sửa được lỗi, ta phải thêm nhiều thông tin dư thừa hơn. Ví dụ đơn giản nhất là mã Hamming(7,4): cứ 4 bit dữ liệu thì thêm 3 bit kiểm tra chẵn lẻ, mỗi bit kiểm tra "canh" một nhóm vị trí khác nhau. Khi 1 bit bị đảo, ba phép kiểm tra cho ra một số nhị phân chỉ đúng vị trí bit bị lỗi – gọi là syndrome.

Chữ số kiểm tra EAN-13 và mã Hamming(7,4)

#include <bits/stdc++.h>
using namespace std;
// Chữ số kiểm tra EAN-13: nhân xen kẽ 1 và 3 cho 12 chữ số đầu
int checkDigit(const string& s12){
    int sum = 0;
    for(int i = 0; i < 12; i++) sum += (s12[i] - '0') * (i % 2 == 0 ? 1 : 3);
    return (10 - sum % 10) % 10;
}
// Mã Hamming(7,4): 4 bit dữ liệu + 3 bit kiểm tra, sửa được 1 bit lỗi
vector<int> encode(vector<int> d){            // d = {d1,d2,d3,d4}
    int p1 = d[0]^d[1]^d[3], p2 = d[0]^d[2]^d[3], p3 = d[1]^d[2]^d[3];
    return {p1, p2, d[0], p3, d[1], d[2], d[3]}; // vị trí 1..7
}
int syndrome(const vector<int>& c){           // trả về vị trí bit lỗi (0 = không lỗi)
    int s1 = c[0]^c[2]^c[4]^c[6], s2 = c[1]^c[2]^c[5]^c[6], s3 = c[3]^c[4]^c[5]^c[6];
    return s1 + 2*s2 + 4*s3;
}
int main(){
    string code = "893123456789";            // 12 chữ số đầu (893 = mã quốc gia Việt Nam)
    cout << "EAN-13 day du: " << code << checkDigit(code) << "\n";
    vector<int> c = encode({1, 0, 1, 1});
    c[4] ^= 1;                                // giả lập 1 bit bị lỗi khi truyền
    int pos = syndrome(c);
    cout << "Bit loi o vi tri: " << pos << "\n";
    if(pos) c[pos-1] ^= 1;                    // sửa lại
    cout << "Du lieu sau khi sua: " << c[2] << c[4] << c[5] << c[6] << "\n";
}

def check_digit(s12):
    # nhân xen kẽ trọng số 1 và 3 cho 12 chữ số đầu
    total = sum(int(ch) * (1 if i % 2 == 0 else 3) for i, ch in enumerate(s12))
    return (10 - total % 10) % 10

def encode(d):                     # Hamming(7,4): d = [d1, d2, d3, d4]
    p1 = d[0] ^ d[1] ^ d[3]
    p2 = d[0] ^ d[2] ^ d[3]
    p3 = d[1] ^ d[2] ^ d[3]
    return [p1, p2, d[0], p3, d[1], d[2], d[3]]

def syndrome(c):                   # vị trí bit lỗi, 0 nếu không lỗi
    s1 = c[0] ^ c[2] ^ c[4] ^ c[6]
    s2 = c[1] ^ c[2] ^ c[5] ^ c[6]
    s3 = c[3] ^ c[4] ^ c[5] ^ c[6]
    return s1 + 2 * s2 + 4 * s3

code = "893123456789"              # 893 = tiền tố mã vạch của Việt Nam
print("EAN-13 day du:", code + str(check_digit(code)))
c = encode([1, 0, 1, 1])
c[4] ^= 1                          # giả lập nhiễu làm hỏng 1 bit
pos = syndrome(c)
print("Bit loi o vi tri:", pos)
if pos: c[pos - 1] ^= 1
print("Du lieu sau khi sua:", c[2], c[4], c[5], c[6])

Kết quả chạy:

EAN-13 day du: 8931234567897
Bit loi o vi tri: 5
Du lieu sau khi sua: 1011

3. Reed–Solomon: "vũ khí" bên trong mã QR

Mã QR do Masahiro Hara và nhóm kỹ sư Denso Wave (Nhật Bản) phát triển, công bố năm 1994. Theo trang chính thức của Denso Wave, khả năng sửa lỗi của mã QR được thực hiện bằng cách thêm mã Reed–Solomon vào dữ liệu gốc.

Mã Reed–Solomon do Irving Reed và Gustave Solomon (Phòng thí nghiệm Lincoln, MIT) công bố năm 1960 trong bài báo "Polynomial Codes Over Certain Finite Fields". Ý tưởng cốt lõi:

• Coi các byte dữ liệu là hệ số của một đa thức trên một trường hữu hạn.
• Gửi đi nhiều giá trị của đa thức hơn mức cần thiết. Giống như 2 điểm đã xác định một đường thẳng, nếu ta gửi thêm vài điểm nữa thì dù vài điểm bị sai, vẫn khôi phục được đường thẳng đúng.
• Reed–Solomon sửa lỗi theo từng byte, rất hợp với lỗi "cụm" như một vết bẩn hay vết xước che cả một vùng.

Mã QR có 4 mức sửa lỗi. Theo bảng của Denso Wave, các mức này khôi phục được khoảng:

Mức	Phần dữ liệu khôi phục được	Khi nào dùng
L	≈ 7%	Môi trường sạch, cần chứa nhiều dữ liệu
M	≈ 15%	Mức được chọn phổ biến nhất
Q	≈ 25%	Nhà xưởng, nơi mã dễ bị bẩn
H	≈ 30%	Mã chịu nhiều hư hại, hoặc có in logo ở giữa

Mức càng cao thì càng phải thêm nhiều byte dư thừa, nên mã QR to hơn (nhiều ô hơn) với cùng một nội dung. Đây là sự đánh đổi kinh điển giữa độ an toàn và dung lượng.

4. Reed–Solomon còn ở đâu?

• Đĩa CD, DVD: theo MIT Lincoln Laboratory, Reed–Solomon giúp đĩa phát âm thanh, hình ảnh không bị ảnh hưởng bởi vết xước.
• Tàu thăm dò Voyager: gửi dữ liệu về Trái Đất từ khoảng cách hàng tỷ dặm.
• Các loại mã vạch 2 chiều khác, truyền hình số, ổ lưu trữ…

5. Bạn học được gì từ đây?

• Phép chia lấy dư (mod) – kiến thức lớp 6 – đã đủ để tạo chữ số kiểm tra.
• Thêm dữ liệu dư thừa một cách thông minh giúp phát hiện rồi sửa lỗi.
• Phép XOR và đa thức là những công cụ rất hay gặp trong lập trình thi đấu.

Bài tập luyện tập

• Viết chương trình kiểm tra một mã vạch 13 chữ số có hợp lệ hay không. Thử với mã vạch trên một hộp sữa trong nhà bạn!
• CSES – Bit Strings (đếm xâu nhị phân, làm quen với phép mod)
• CSES – Gray Code (các xâu bit liên tiếp chỉ khác nhau 1 bit)

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 14: Blockchain và Bitcoin hoạt động thế nào? Hàm băm và bằng chứng công việc

Đọc tiếp: Blockchain & hàm băm →

← Bài trước: máy tính chơi cờXem tất cả 27 bài →

Nguồn tham khảo

• Denso Wave – QR Code fundamentals
• DENSO – Masahiro Hara, người phát triển mã QR
• QRcode.com (Denso Wave) – Error correction feature
• Reed & Solomon (1960) – Polynomial Codes Over Certain Finite Fields
• MIT Lincoln Laboratory – Empowering digital communications
• GS1 – How to calculate a check digit manually