Thuật toán chữ số kiểm tra là tên gọi chung cho một họ quy tắc có cùng hình dạng: lấy các chữ số đứng trước, nhân chúng với những trọng số đã định, cộng lại, chia cho một số gọi là mô-đun, rồi dùng phần dư để suy ra chữ số cuối cùng. Đọc hết bài này, bạn sẽ phân biệt được ba nhánh lớn trong họ đó, hiểu vì sao cùng một khung mà các thành viên lại cho ra kết quả khác nhau, và biết những câu hỏi nào cần trả lời trước khi chọn một thuật toán cho hệ thống của mình.
Họ thuật toán chữ số kiểm tra có mấy nhánh?
Có thể chia họ này thành ba nhánh theo mô-đun mà chúng dùng, vì mô-đun quyết định phần lớn tính chất của thuật toán. Nhánh thứ nhất lấy dư cho mười, và bên trong nó có một nhánh con dùng cách nhân đôi rồi cộng các chữ số của kết quả. Nhánh thứ hai lấy dư cho mười một, và trong thực tế thường xuất hiện dưới vài biến thể khác nhau về cách xử lý phần dư. Nhánh thứ ba lấy dư cho chín mươi bảy, thường được dùng cho những chuỗi dài và có lẫn chữ cái.
Ba nhánh này không phải ba mức chất lượng. Không có nhánh nào tốt hơn một cách phổ quát. Mỗi nhánh ra đời để giải một bài toán cụ thể của một hệ thống cụ thể, và việc chọn sai nhánh chỉ làm cho thuật toán không bắt được loại lỗi mà bạn quan tâm. Về mặt tiêu chuẩn, họ thuật toán chữ số kiểm tra quốc tế được gom trong bộ tiêu chuẩn ISO 7064, và một trong những thành viên quen thuộc nhất của bộ đó là biến thể dùng cho số tài khoản ngân hàng quốc tế, thường được nhắc tới dưới tên MOD 97-10.
mod-10, mod-11 và mod-97 khác nhau ở đâu
Sự khác biệt lớn nhất nằm ở kích thước của không gian kết quả, và điều đó kéo theo một hệ quả rất thực tế về cách biểu diễn chữ số kiểm tra.
| Nhánh | Không gian phần dư | Hệ quả khi biểu diễn |
|---|---|---|
| Lấy dư cho mười | Ít khả năng phân biệt nhất | Chữ số kiểm tra luôn nằm gọn trong một chữ số |
| Lấy dư cho mười một | Nhiều khả năng hơn | Phần dư có thể cần một ký tự ngoài dãy chữ số, đôi khi là chữ X |
| Lấy dư cho chín mươi bảy | Nhiều khả năng nhất | Thường dùng cho chuỗi dài và chuỗi có chữ cái |
Hàng thứ hai là hàng hay gây nhầm lẫn nhất khi triển khai. Khi phần dư có nhiều khả năng hơn số chữ số hiện có, hệ thống buộc phải quy định một phép ánh xạ bổ sung để biến phần dư thành một ký tự hợp lệ. Chính phép ánh xạ đó, chứ không phải bản thân phép chia, là chỗ các biến thể tách khỏi nhau. Có biến thể quy định dùng một chữ cái, có biến thể quy định bỏ qua trường hợp đặc biệt rồi tính lại, và có biến thể chỉ đơn giản là không cho phép chuỗi rơi vào trường hợp đó.
Hàng thứ ba giải thích vì sao nhánh lấy dư cho chín mươi bảy lại hợp với những chuỗi dài: khi chuỗi có lẫn chữ cái, người ta cần một cách chuyển chữ cái thành chữ số trước khi chia, và một mô-đun lớn giúp giữ được nhiều thông tin hơn trong một hoặc hai ký tự kiểm tra.
Trọng số và phép lấy dư: các tham số bên trong một họ
Nếu bỏ qua phần trình bày và chỉ nhìn vào cấu trúc, mọi thành viên của họ đều có bốn tham số. Tham số thứ nhất là dãy trọng số, quy định mỗi vị trí trong chuỗi được nhân với bao nhiêu. Tham số thứ hai là mô-đun, tức số chia dùng ở bước cuối. Tham số thứ ba là cách chọn chiều: trọng số được gán từ trái sang phải hay từ phải sang trái. Tham số thứ tư là phép ánh xạ từ phần dư sang ký tự kiểm tra.
Bốn tham số này giải thích một hiện tượng mà người mới thường thấy khó hiểu: hai hệ thống có thể trông rất giống nhau ở phần mô tả, cùng nói tới việc nhân với trọng số rồi lấy dư, nhưng không bao giờ cho ra cùng một chữ số kiểm tra. Chỉ cần lệch chiều gán trọng số, kết quả đã khác hoàn toàn trên cùng một chuỗi đầu vào.
Vì vậy, khi đọc mô tả của một hệ thống, điều cần tìm không phải là câu thuật toán này dùng nhân rồi lấy dư, mà là bốn tham số nói trên. Một bản mô tả chỉ có câu chung chung thì chưa đủ để triển khai đúng, và cách duy nhất để kiểm chứng là đối chiếu với mẫu do chính hệ thống đó công bố.
Vì sao có thuật toán bắt được lỗi đổi chỗ hai chữ số?
Đây là câu hỏi phân biệt người hiểu thuật toán với người chỉ biết chép công thức. Lỗi đổi chỗ xảy ra khi hai chữ số liền kề bị gõ ngược thứ tự cho nhau, một lỗi rất phổ biến khi nhập số bằng bàn phím. Nếu dãy trọng số đối xứng, nghĩa là hai vị trí liền kề được nhân với cùng một giá trị, thì việc đổi chỗ hai chữ số không làm thay đổi tổng, và phép kiểm tra sẽ không phát hiện được gì.
Ngược lại, khi dãy trọng số không đối xứng, hai vị trí liền kề được nhân với hai giá trị khác nhau, nên phép đổi chỗ làm tổng thay đổi theo một lượng phụ thuộc vào hiệu của hai trọng số và hiệu của hai chữ số. Nhờ vậy thuật toán mới phân biệt được thứ tự đúng với thứ tự sai. Đây cũng là lý do có những thuật toán rất giỏi bắt lỗi gõ sai một chữ số nhưng lại yếu hơn hẳn với lỗi đổi chỗ: chúng dùng dãy trọng số có tính đối xứng cao.
Không có thuật toán nào trong họ này bắt được mọi loại lỗi, và cũng không nên quảng cáo chúng như vậy. Điều chúng làm được là biến một phép kiểm tra tốn kém thành một phép tính rẻ, đủ nhanh để chạy ngay khi người dùng gõ xong.
Bốn câu hỏi cần trả lời trước khi chọn thuật toán
Khi bạn phải quyết định dùng thuật toán nào cho một loại số mới, bốn câu hỏi sau sẽ thu hẹp lựa chọn nhanh hơn bất kỳ so sánh lý thuyết nào.
- Chuỗi dài bao nhiêu ký tự. Chuỗi càng dài thì lỗi đổi chỗ và lỗi bỏ sót càng khó thấy bằng mắt, nên khả năng bắt lỗi của thuật toán càng quan trọng.
- Tập ký tự là toàn chữ số hay có lẫn chữ cái. Có chữ cái thì phải có bước chuyển chữ thành số trước khi chia, và bước đó phải được quy định rõ.
- Lỗi chủ yếu đến từ con người hay từ máy. Dữ liệu do người gõ tay cần ưu tiên khả năng bắt lỗi đổi chỗ; dữ liệu do máy sinh có thể chấp nhận một thuật toán đơn giản hơn.
- Khi phần dư rơi vào trường hợp cần ký tự ngoài dãy chữ số thì biểu diễn thế nào. Trả lời muộn câu này sẽ khiến bạn phải sửa cả cơ sở dữ liệu về sau.
Nếu hệ thống bạn đang tích hợp đã có quy định sẵn, đừng tự nghĩ ra quy tắc mới. Hãy triển khai đúng theo bản mô tả mà hệ thống đó công bố, rồi tự kiểm tra lại bằng những mẫu cũng do họ công bố.
Phần dành cho nhà phát triển: một họ thuật toán, một cách triển khai
Điểm hay của việc nhìn họ thuật toán như một họ là bạn chỉ cần viết một lần phần khung, rồi thay tham số cho từng hệ thống. Điều này nghe hiển nhiên, nhưng rất nhiều dự án lại viết mỗi hệ thống một hàm riêng, và hậu quả là mỗi hàm có một cách xử lý phần dư hơi khác nhau.
- Hãy để bốn tham số nói trên là dữ liệu cấu hình, không phải những con số nằm rải trong mã nguồn. Khi một hệ thống sửa quy tắc, bạn chỉ đổi dữ liệu.
- Viết một bộ kiểm tra bằng những mẫu đã công bố cho từng hệ thống, và chạy nó mỗi lần bạn sửa khung. Một lỗi lệch chiều trọng số rất khó nhìn ra bằng mắt thường.
- Trả về phần dư trước khi ánh xạ, đừng chỉ trả về chữ số cuối. Khi có sự cố, phần dư là thứ duy nhất cho biết thuật toán dừng ở đâu.
- Đừng để hàm kiểm tra tự đoán hệ thống. Hãy nhận hệ thống như một tham số đầu vào, và để tầng nhận diện làm việc đó riêng.
- Ghi lại thuật toán nào đã được dùng cho từng kết luận trong quá khứ. Quy tắc đổi theo thời gian, và nếu không có ghi chú này bạn sẽ không giải thích được vì sao một giá trị từng được chấp nhận.
Điều nên làm tiếp
Nếu bạn đang cân nhắc giữa hai thuật toán, hãy tự tay dựng hai chuỗi giống nhau về mọi mặt trừ đúng hai chữ số liền kề bị đổi chỗ, rồi xem thuật toán bạn đang dùng có phân biệt được không. Đó là phép thử nhanh nhất và cũng thực tế nhất. Bài cấu trúc IBAN và phép kiểm tra mod-97 đi vào một trường hợp dùng rất cụ thể của nhánh thứ ba, còn bài kiểm tra số: ký tự, độ dài và chữ số kiểm tra đặt lớp chữ số kiểm tra vào đúng vị trí của nó trong toàn bộ đường ống. Nếu bạn muốn thử ngay trên một chuỗi cụ thể, công cụ kiểm tra số sẽ chỉ ra hệ thống nào khớp và phần dư tính ra là bao nhiêu.
Các tham số thuật toán được nhắc trong bài thuộc kiến thức công khai; mọi con số minh họa, nếu có, đều là giá trị hư cấu được dựng ra để giải thích cơ chế, không phải số do bất kỳ hệ thống nào cấp và không phải mẫu thử của bất kỳ tổ chức nào.