基於模運算的校驗碼（們）

08-15

基於模運算的校驗碼（們）

來自專欄 Liu言雜記8 人贊了文章

內容

「條形碼」
國際標準書號ISBN
第二代身份證

「條形碼」

通常講的「條形碼」，源頭是UPC（universal product code，商品統一代碼）。這是由美國的喬·伍德蘭德（Joe Woodland）和貝尼·西爾佛（Beny Silver）兩位工程師研究出來的，最初他們用條形碼錶示食品項目並研製相應的識別系統設備。1949年獲得了美國的專利。UPC碼共有A、B、C、D、E等五種版本（就不詳細列出了）。

我國目前常用的條形碼實際上是EAN（European Article Number）條碼。

EAN條碼是歐洲的國際物品編碼協會（International Article

Numbering Association）制定的一種條碼，在UPC-A標準的基礎上建立。EAN條碼符號有標準版和縮短版兩種，標準版由13位數字構成，又稱為EAN-13碼，縮短版表示8位數字構成，又稱為EAN-8碼。兩種條碼的最後一位為校驗位，由前面的12位或7位數字計算得出。我國於1991年加入EAN組織。

（題圖就是一種食品的EAN-13碼）

EAN-13碼由前綴碼、生產廠商代碼（廠商識別碼）、商品項目代碼和校驗碼組成。

前綴碼是國際EAN組織標識各會員組織的代碼，我國為690-695；
變長的生產廠商代碼是EAN編碼組織分配給廠商的代碼；
商品項目代碼由廠商自行編碼；
校驗碼，只有一位，取值範圍從0到9，目的是校驗代碼的正確性。計算方法是用1分別乘以EAN-13的前12位(位數從左到右為1到12）中的奇數位，用3乘以偶數位，二者求和得到結果S，然後校驗碼為 $(10-S)(mod 10)$ 。

換言之用1分別乘以EAN-13的所有奇數位(位數從左到右為1到13），用3乘以全部偶數位，二者的和是10的倍數。

例如：某產品的條形碼的前12位是694 021189000，那麼按照下圖可以計算出來最後一位為4。

新版國際標準書號ISBN-13

為什麼叫做「新版」呢？是因為ISO於1972年頒布了ISBN國際標準，2007年1月1日前，ISBN由10位數字組成。而2007年1月1日起，實行新版ISBN。

新版國際標準書號（International Standard Book

Number）號碼由13位數字組成，並以四個連接號或四個空格加以分割，每組（共5組）數字都有固定的含義。

第一組：978或979；
第二組：國家、語言或區位代碼（例如中國大陸為「978-7」表示漢語）；
第三組：表示出版社代碼，由各國家或地區的國際標準書號分配中心，分配給各個出版社；
第四組：書序碼，是該出版物的代碼，由出版社具體給出；
第五組：校驗碼，只有一位，計算方法與EAN-13相同。

例如：我覺得有一本很好的書，ISBN是978-7-302-32015-？。其中，

978-7表示漢語；
302表示出版社為「清華大學出版社」；
32015為圖書的代碼；
9+8+3+2+2+1=25，3(7+7+0+3+0+5)=66，於是校驗碼為(10-(25+66))(mod 10)=9。

所以這本寫得很好的書的完整的ISBN是：978-7-302-32015-9。

第二代居民身份證

1984年4月6日國務院發布《中華人民共和國居民身份證試行條例》，並且開始頒發第一代居民身份證。2004年3月29日起，中國大陸正式開始為居民換髮第二代居民身份證。

第二代居民身份證的編碼方法是：

前1、2位數字表示所在省（直轄市、自治區）的代碼（例如北京市為11）
第3、4位數字表示所在地級市（自治州）的代碼
第5、6位數字表示所在區（縣、自治縣、縣級市）的代碼
第7-14位數字表示出生年月日
第15、16位數字表示所在地的派出所的代碼
第17位數字表示性別，奇數表示男性，偶數表示女性
第18位數字是校檢碼（由前17位計算得來）

校檢碼的計算方法符合ISO/IEC 7064:2003：

為表述的方便性，將身份證的18位數自左而右記作 $K_{17}, K_{16},…, K_1, K_0$ 。

1. 將前17位數分別乘以不同的係數。從左至右前17位的係數（ $W_{17}, W_{16},…, W_1, W_0$ ）分別為：7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2。

——可以看出 $W_i = 2^i (mod 11)$

2. 將這17個數字和係數相乘的結果累加後模11求余；

3. 餘數0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10分別對應（相當於下述公式中的函數 $f$ ）的校驗碼為1, 0, X, 9, 8, 7, 6, 5, 4, 3, 2。

——即校驗碼與餘數的和模11餘1，X代表10。（這是因為10在羅馬數字中表示作X）。

這個計算方法使用公式表示就是： $K_0=fleft( sum_{i=1}^{17}{K_i imes W_imod 11} ight)=left(12- sum_{i=1}^{17}{K_i imes W_i} ight)mod 11$ 。

於是， $sum_{i=0}^{17}{K_i imes W_i} equiv 1(mod 11)$ ，即 $sum_{i=0}^{17}{K_i imes 2^i} equiv 1(mod 11)$ 。

例如：一個（虛擬）的身份證號的前17位為11010420180915195，最後一位校驗碼的計算過程是：

$left( sum_{i=1}^{17}{K_i imes W_imod 11} ight)=left( 241 mod 11 ight)=10$

再通過查表即得校驗碼是2：

（一）第二代身份證的驗證碼可以發現1個字元的錯誤——

假設某個 $K_j$ 被錯抄成 $K_j$ ，那麼計算錯誤的身份證的 $left( sum_{i=0,i e j}^{17}{K_i imes 2^i+K_j imes 2^j} ight)mod 11$ 。它和正確的校驗和 $left( sum_{i=0}^{17}{K_i imes 2^imod 11} ight)=1$ 相比，差異為 $left( K_j-K_j ight) imes 2^j$ 。由於2和 $left( K_j-K_j ight)$ 都與素數11矛盾，因此 $left( K_j-K_j ight) imes 2^jmod 11 e 0$ ，於是 $left( sum_{i=1,i e j}^{17}{K_i imes 2^i+K_j imes 2^j} ight)mod 11 e 0$ ，不能通過校驗。

（二）第二代身份證的驗證碼可以糾正1個已知位置的錯誤——

假設某個 $K_j$ 被錯抄成 $K_j$ ，那麼計算錯誤的身份證的校驗和為 $left( sum_{i=1,i e j}^{17}{K_i imes 2^i+K_j imes 2^j} ight)mod 11 e 1$ 。可以通過 $K_j=left( K_j-left( sum_{i=0,i e j}^{17}{K_i imes 2^i+K_j imes 2^j-1} ight) imes 6^j ight)mod 11$ 計算恢復出正確的 $K_j$ 。

（三）第二代身份證的驗證碼可以發現2個相鄰字元的顛倒錯誤——

假設某個 $K_j$ 和被 $K_{j+1}$ 抄顛倒，那麼錯誤的身份證的校驗和 $left( sum_{i=0,i e j,i e j+1}^{17}{K_i imes 2^i+K_{j+1} imes 2^j+K_j imes 2^{j+1}} ight)mod 11$ 。它和正確的校驗和 $left( sum_{i=0}^{17}{K_i imes 2^imod 11} ight)=1$ 相比，差異為 $left( K_j-K_{j+1} ight) imes left( 2^{j+1}-2^j ight)mod 11=left( K_j-K_{j+1} ight) imes 2^jmod 11$ 。由於2和 $left( K_j-K_{j+1} ight)$ 都與素數11矛盾，因此 $left( K_j-K_{j+1} ight) imes 2^jmod 11 e 0$ ，於是 $left( sum_{i=0,i e j,i e j+1}^{17}{K_i imes 2^i+K_{j+1} imes 2^j+K_j imes 2^{j+1}} ight)mod 11 e 0$ ，不能通過校驗。

最後，提一句，二維碼的糾錯能力很強，所以可以犧牲一些信息做出特型二維碼，那是因為它使用了更複雜的糾錯碼——通常是Reed–Solomon codes，而它，就複雜得多了。