刀具自動標志中數據矩陣碼的編碼技術研究

摘要：為了自動標志數字化車間中的刀具資源，研究了含校驗位的數據矩陣碼編碼技術，用軟件實現了其算法并在某打標設備上成功實施，提高了刀具編碼的糾錯能力和系統的可靠性。

關鍵詞：刀具標志；校驗位；數據矩陣碼；編碼算法；糾錯

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2008)05-1453-02

刀具的自動標志技術是數字化車間庫存管理以及生產過程管理與監控的關鍵技術。由于生產過程和其自身的特點，造成對其進行自動標志具有相當大的難度。針對國內外刀具資源自動標志技術的研究現狀，筆者提出了采用直接打標技術DPM和數據矩陣碼技術實現刀具的自動直接標志。用DPM技術標刻在刀具上的條碼精度高、牢固耐磨，便于實現刀具的動態跟蹤。但是一維條碼占用面積大，反差要求高（>70%），不適于刀具表面直接標志。而數據矩陣碼(data matrix)編碼密度高、糾錯能力強、識別可靠性高，因此采用DPM技術時首先考慮使用data matrix碼制。由于data matrix采用了最先進的糾錯碼技術之一RS(Reed－Solomon)錯誤控制碼。該碼以伽羅華域GF(256)為其循環域，編譯碼過程均比較復雜，而且關于RS碼在data matrix中的使用原理及方法，國內外的文獻中都鮮有提及，這在很大程度上限制了我國關于data matrix的應用。本文研究并實現了刀具自動標志中data matrix的編碼算法，為上述問題的解決提供了技術基礎。

1Data matrix碼簡介

Data matrix是一種矩陣式二維條碼符號。它的最小尺寸是目前所有條碼中最小的，特別適用于小零件的直接標志。每個data matrix符號由規則排列的方形模塊構成的數據區組成；數據區的四周由探測圖形包圍；探測圖形的四周則由空白區包圍，如圖1(a)所示。在較大的符號中，數據區由定位圖形分隔，如圖1(b)所示。

2刀具信息的data matrix數據編碼方法

首先分析要表示的刀具信息，選取合適的編碼方案，按所選方案將信息流轉換為碼字流，并加入必要的填充字符。如果用戶沒有規定矩陣尺寸，那么應選取能滿足要求的最小尺寸。

刀具編碼信息作為整個系統的信息源頭，其正確性具有決定性影響。為了防止在輸入過程中發生錯誤，筆者未直接采用某種data matrix編碼方案去編碼刀具信息，而是先在刀具編碼信息后設置校驗碼。校驗碼是在已有編碼結構的基礎上，通過事先規定好的數學方法計算出來，附在原編碼信息的后面，與原編碼信息一起構成刀具整個編碼信息[1]。使用時，校驗碼與原編碼信息一起輸入系統，由計算機用同樣的數學方法，按刀具輸入信息計算出校驗碼，并將它與輸入的校驗碼進行比較，以檢查輸入是否有錯。譯碼時，同樣可以在譯出刀具信息后，利用校驗碼檢查譯碼結果是否正確。某刀具庫的編碼如圖2所示。

第一~四位為分類碼，用大寫字母表示；第五~八位為擴展位和順序碼，用阿拉伯數字表示；最后一位為校驗碼，它可以根據前八位信息用相應的數學方法計算出來。比如：前八位信息是ABCD1234，得出校驗碼的一種簡單數學方法是根據前八位對應的ASCII值算術平均后取余數得出。這樣刀具的編碼信息就是ABCD12344。

Data matrix共有六種編碼方案，即ASCII、 C40 、Text、 X12、 EDIFACT 和Base256代碼集。

根據上面的刀具編碼規則和各種編碼方案適用的字符集，選擇使用前兩種編碼方案，即ASCII編碼和C40編碼。

2．1ASCII編碼

ASCII編碼是data matrix第一個符號字符的缺省集。它能為ASCII數據、雙位數字型數據和符號控制字符編碼。符號控制字符包括功能字符、填充字符和轉向其他代碼集的切換字符。ASCII數據被編碼為碼字1~128（ASCII值+1）。擴展ASCII（ASCII值128~255）使用上移位符號控制字符進行編碼。數字對00~99是通過碼字130~229（數字值+130）進行編碼。切換字符可用來將ASCII編碼轉換為其他任意一種編碼方案。各編碼方案可通過不同的方法轉回ASCII編碼集。填充字符僅在為填滿符號的剩余數據容量時才使用[2]。

2．2C40編碼

C40編碼可將三個數字字母型數據字符用兩個碼字表示。大寫字母、數字和空格也可用單個C40值表示。所有其他的ASCII字符和特殊字符均由兩個C40值表示。一個C40切換字符僅對其后的單個C40值有效。利用切換碼字230，可以從ASCII編碼轉換為C40編碼。緊跟在以C40編碼的一對碼字后的碼字254充當非鎖定碼字，以便重新轉換回ASCII編碼。否則，C40編碼將繼續有效，直到符號結束。

三個C40值(C1C2C3)編碼如下：(1 600×C1)+(40×C2)+C3+1，計算結果被模256除后的商數為第一個碼字（表示最高八位），余數為第二個碼字（表示最低八位）[2]。

3刀具信息的data matrix糾錯碼字的編碼方法

對于少于255個碼字的data matrix符號，錯誤糾正碼字根據數據碼字通過Reed－Solomon算法利用生成多項式計算得出。對于多于255個碼字的data matrix符號，需要對數據碼字分塊，然后通過Reed－Solomon算法計算每塊的錯誤糾正碼字。

3．1Reed－Solomon糾錯碼

Reed－Solomon(RS)是糾正隨機錯誤和突發錯誤以及糾正隨機和突發組合錯誤的最好的一類碼，在糾多個突發錯誤方面非常有效，因而被廣泛應用于數字通信和信息存儲領域。在二維條碼中，PDF417、data matrix和 QR Code等均采用RS碼進行糾錯。RS碼是有限域GF（pm）上pm進制的BCH循環碼，p為質數，m為大于2的任意整數。當p=2時，每個碼字的長度為m位。在給定n和k后（n是糾錯編碼后的碼字總數；k是數據碼字數），RS（n，k）碼可以糾正(n-k)/2個隨機錯誤，是糾錯能力最強的（n，k）碼[3]。

3．2有限域GF(28)上域元素間的算術運算

在RS糾錯編碼過程中，核心運算是基于伽羅華域GF（28）上的域元素間的運算。由伽羅華域性質可知，若α是GF（28）本原域元素，則GF(28)中每一元素都可表示成α的冪。Data matrix碼采用GF(28)上的本原多項式為p(x)＝x8+x5+x3+x2+1。根據本原多項式可構造出GF(28)中所有域元素。為便于在計算機中運算，可以給出域元素的兩種表示式，即多項式表示法和冪表示法。多項式表示法用于加法（減法）運算，冪表示法用于進行乘法（除法）運算，兩種形式之間可相互轉換。

3．2．1GF(28)上的加法（減法）運算

3．2．2GF(28)上的乘法

依然用多項式形式進行GF(28)上的任意兩個元素a和b的相乘運算很不方便，為此可以用域元素的冪表示法進行乘法運算。任意兩個元素a和b的相乘運算步驟如下：

a)計算兩個元素a和b對應的冪表示法的冪指數a1和b1。

b)將a1和b1兩個冪指數的數值進行模255加法，得到結果c1。

c)計算冪指數c1相應的域元素αc1的元素值[5]。

3．2．3GF(28)上的除法

對于每個非零的域元素b，都有一個對應的乘法逆元素b-1使得b×b-1=1。因此，可以將除法運算轉換成對乘法逆元素的乘法運算。

3．3刀具信息糾錯碼字的生成

刀具的數據碼字多項式可用歐幾里德除法表示為d(x)=g(x) q(x)+r(x)，令c(x)=g(x)q(x)，則c(x)=d(x)-r(x)。考慮到GF(2m)上加法和減法的等價性，有c(x)=d(x)+r(x)， 用生成多項式g(x)去除刀具數據碼字多項式d(x)，可求得相應的余式r(x)，由d(x)和r(x)組成了碼字c(x)。在data matrix碼的編碼中，將k個輸入數據碼字用生成多項式g(x)來產生(n-k)個糾錯碼字，添加在數據碼字之后，合成n個信息碼字。其中，每個碼字都是有限域GF(28)中的一個元素。生成多項式為g(x)=n-ki=0gixi=n-ki=1(x+ai)。其中：r=n-k是生成多項式的次數(糾錯碼字個數)；α是GF(28)的本原域元素。

刀具編碼算法分為三步：

a)假定待編碼的刀具信息（含校驗碼的碼字）是d＝（d0，d1，…，dk-1），相應的多項式是 d(x)，用xn-k乘以d(x)。其中：n是糾錯編碼后的碼字總數；k是數據碼字數。

b)生成多項式g(x)=(x+α1）（x+α2）…（x+αn-k）。其中：n-k是糾錯碼字的個數；α是有限域GF(28)上的本原域元素。求余式r(x)=xn-kd(x) mod g(x)。

c) 聯合r(x)和xn-kd(x)，編碼后的碼字多項式: 

c(x)=xn-kd(x)+xn-kd(x) mod g(x)

糾錯碼字能夠糾正兩種類型的錯誤，即E錯誤（已知位置上的錯誤碼字）和T錯誤（未知位置上的錯誤碼字）。E錯誤是不能被掃描或不能被譯碼的符號字符。T錯誤是被錯誤譯碼的符號字符。本文設計的校驗碼使得譯碼結果中出現的T錯誤可以及時發現，提高了刀具編碼的糾錯能力，減少了錯誤調用刀具的幾率，使系統的可靠性大幅度提高。

4Data matrix編碼算法的實施

目前筆者已經將上述的data matrix編碼算法程序成功嵌入某打標設備的控制軟件中，完成了刀具條碼的標刻工作。主操作程序界面如圖3所示。

5結束語

本文將通用的數據矩陣碼的編碼方法和含校驗碼的某刀具庫的制造資源編碼進行結合，提高了傳統的刀具編碼糾錯能力和系統的可靠性，打破了國外data matrix編碼的技術壁壘。這為數字化車間中刀具等制造資源的庫存管理及其在生產過程中的動態跟蹤提供了一個很好的技術基礎。

參考文獻：

［1］楊杰，劉云．基于CIMS環境的刀具編碼系統的研究[J].機電工程技術，2004，33(3)：23-24.

[2]ISO/IEC 16022：2000，Technical corrigendum 1， informational technology－international symbology specification－data matrix[S].2004.

[3] 劉悅，尚振宏，劉明業.快速響應矩陣碼糾錯算法的研究[J].微電子學與計算機，2005，22(11):45-47.

[4] 黃宏博，肖俊嶺，佟俐鵑.基于Reed－Solomon算法的QR碼糾錯編碼[J].計算機工程，2003，29(1):93-95.

[5]SWEENEY P.差錯控制編碼 [M].俞越，張丹，譯.北京：清華大學出版社，2004：88-92.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”