摘? 要: 對二維條碼" title="二維條碼">二維條碼PDF417的基本概念、用途、優勢做了系統的介紹,著重分析了PDF417條碼的具體譯碼過程,并給出該條碼作為多進制碼,進行R-S糾錯譯碼時所要注意的有關域運算及模運算。
關鍵詞: PDF417條碼? 有限域? 錯誤糾正容量? 錯誤位置多項式
?
條碼的使用,極大地提高了數據采集和信息處理的速度,改善了人們的工作和生活環境,提高了工作效率,為管理的科學化和現代化作出了很大貢獻。
受信息容量的限制,一維條碼的使用不得不依賴于后臺的數據庫。在沒有數據庫或不便聯網的地方,一維條碼的使用便受到了局限。為此,美國Symbol公司發明了一種被稱作便攜數據文件" title="數據文件">數據文件的二維條碼——PDF417條碼。
1 PDF417條碼簡介
PDF417是一種具有高密度、高容量的便攜式數據文件,它能容納大量信息而不需要與外部數據庫相連。一個PDF417符號能容納1千字節數據,是尺寸同樣大小的一維條碼的百倍。通過使用PDF417,諸如人員信息、檔案信息、發貨標簽、裝船清單、設備校準信息、機動車登記等立即變成機器可識讀的標識。
PDF417條碼具有一個顯著的優點便是糾錯能力強,它采用了目前世界上最先進的錯誤糾正技術。這種隱含子符號在內的錯誤糾正技術,不僅可以有效地防止譯碼錯誤,提高譯碼的速度及可靠性;而且可以將由于條碼符號破損、沾污等丟失的信息破譯出來。錯誤糾正可分為八個等級,當等級為八時最高,可以將符號受損面積達50%的條碼符號所含的信息復現出來。
圖1為PDF417碼符號結構。符號的頂部和底部為空白區。上下空白區之間為多行結構。每行的數據符號字符數相同,行與行左右對齊直接銜接。
?
?
圖2為符號字符的結構。每一符號由4個條和4個空構成,自左向右從條開始。每一個條或空包含1～6個模塊。在一個符號字符中,4個條和4個空的總模塊數為17。
?
?
2 譯碼的具體過程
譯碼的具體過程如圖3所示。
?
?
2.1 條碼的糾錯譯碼
PDF417條碼在識讀過程中,由于條碼圖案的損壞,或掃描及掃描后的數據傳輸出錯,會出現突發錯誤。Reed-Solomon" title="Reed-Solomon">Reed-Solomon碼特別適合糾正突發錯誤。故采用R-S碼進行糾錯譯碼。
R-S碼是一類具有很強糾錯能力的多進制BCH碼,其譯碼步驟主要分為三步:
第一步由收到碼字R(x)計算d-1個伴隨式分量sj;第二步由伴隨式求錯誤位置多項式,得出錯誤圖樣
;第三步由R(x)-
得出最可能發送的碼字
。
其中錯誤圖樣包括隨機錯誤(既不知錯誤位置,又不知錯誤大小)和刪除錯誤(知道錯誤所在位置,不知錯誤大小)。在求刪除錯誤時,二進制BCH碼的糾錯糾刪譯碼很簡單。把收到的R(x)中刪除位置全填上0,并送到譯碼器譯碼。但多進制碼必須對伴隨式進行修正。該伴隨式包含兩個錯誤位置多項式:一是刪除位置多項式,另一是錯誤位置多項式。總的錯誤位置多項式等于二者的乘積。
2.2 條碼譯碼過程
417條碼碼字集包含929個碼字:0～928。所謂碼字集即一種條形碼制中所給定的數據字符的范圍。
碼字0～899:用于表示數據(根據當前的壓縮模式" title="壓縮模式">壓縮模式和GLI解釋)，每個碼字表示一個或多個數字、字母或符號。
碼字900～928：900、901、902、913、924用于各壓縮模式標記;925、926、927用于GLI(全球標識標記符,不同的GLI具有相應的碼字解釋);922、923、928用于宏417碼(當文件內容太長,無法用一個417條碼符號表示時,可用包含多個宏417條碼的分塊表示);921用于條碼識讀器初始化;903～912,914～920保留待用。
為了有效地壓縮并表示數據,PDF417采用三種數據壓縮模式設置來組成字符集。
2.2.1 文本壓縮模式(TC)
碼字為900時鎖定該模式,分管大寫字母型子模式、小寫字母型子模式、混合型子模式、標點型子模式。通過標準字符集所對應的特定數值可以完成各子模式間的切換,可進行轉移切換(即只對切換后的第一個碼字有限,隨后返回),亦可進行鎖定切換(該模式切換到下一個切換前一直有效)。
每種子模式選擇文件中出現頻率較高的一種字符組成的字符集。在子模式中,GLI標準規定了文本壓縮模式下每個字符所對應的值(0～29),一個字符對對應一個單獨的碼字:
碼字=30×H+L
式中:H、L依次表示字符對中的高位和低位字符值。
任何模式到文本壓縮模式(TC)的鎖定都是到大寫字母型子模式的(Alpha)鎖定。在文本壓縮模式中,每一個碼字用兩個基為30的值表示(范圍為0~29)。如果在一個字符串的尾部有奇數個基為30的值,需要用值為29的虛擬字符ps填充最后一個碼字。算法如下:
(1)收到碼字/30，商為高位字符值,余數為低位字符值;
(2)由字符值確定是哪種子模式;
(3)查找該子模式下,字符值對應的文本值,恢復原始信息。
2.2.2 字節壓縮模式(BC)
當所要表示的字節總數不是6的倍數時,用碼字901鎖定;否則用924鎖定,碼字913轉移為該模式,通過基256至基900的轉移,將2位十六進制的數據序列轉換為碼字序列。算法如下:
(1) 用924鎖定模式
例如:一個2位十六進制的數據序列01H，02H，03H，04H，05H，06H (H代表十六進制)
1×256e5+2×256e4+3×256e3+4×256e2+5×256+6=1×900e4+620×900e3+89×900e2+74×900+846
從而表示為一個碼字序列:924,1,620,89,74,846
(2)用901鎖定模式
????前6字節的轉換方法同上,剩下的每字節對應一個碼字,依次直接表示數列:01H，02H，03H，04H，05H，06H，07H，08H，04H
轉換為一個碼字序列:901,1,620,89,74,846,7,8,4
????將收到的每5個mod900的碼字轉換為十進制數,繼而轉換為6個mod256數,分別按十六進制的數輸出。若碼字個數非6的倍數,則將碼字個數被6整除后余下的mod900的碼字直接按十六進制輸出。
2.2.3 數字壓縮模式(NC)
碼字為902時鎖定該模式,通過基10至基900的換算,實現數據位數的壓縮,能把約3個數字位用一個碼字表示。當數字位數大于13,用數字壓縮模式;數字位數小于13,用文本壓縮模式。算法如下:
(1)每15個碼字從左到右分為一組(每15個碼字可轉換為44個數字位),其最后一組碼字可少于15個。
(2)對于每一組碼字先執行基900至基10的轉換,然后去掉前導位1。
2.2.4 譯碼的總體流程
???? 譯碼的總體流程圖如圖4所示。
?
?
3 有關PDF417譯碼過程中的幾個關鍵問題
3.1 有關域的運算
PDF417條碼碼字集包含929個碼字,即碼字取值范圍為0~928,故譯碼始終在有限域GF(929)中進行,超出GF(929)域的項必須通過mod(929)轉化到GF(929)中。
錯誤糾正碼字δ>-929,在有限域GF(929)中的負值等于該值的補數;如果δ<=-929,在有限域GF(929)中的負值=余數(δ/929)的補數。
3.2 從已知的簡單模2算法到PDF417需用的模929算法方案的實現
3.2.1 本原元與本原多項式
GF(929)中的所有元素均能由3生成,故PDF417碼的本原元為3，而GF(929)中以3為根的最小多項式為
m(x)=x-3
故該式為PDF417碼的本原多項式。
3.2.2 求逆運算
在GF(929)中所有的除法均通過求逆得到。求逆即：
xix-i=1? --->? x-i為xi的逆(x為本原元)。
域中元素通過GF(929) <---> 3i mod929轉換為3i(i=0，1，...927)。求逆后再次通過上式,轉換至GF(929)中,即:
GF(929)--->ximod929--->x-imod929--->GF(929)
二維條碼PDF417技術在國內的使用正處于上升階段。它數據容量更大,超越了字母數字的限制,條碼相對尺寸小" title="尺寸小">尺寸小,具有抗損毀能力,不再需要后臺數據庫的支持,應用范圍非常廣泛。同時用戶可以根據需要進行前端加密,從而提高條碼的保密性和防偽性。一些大廠商、大企業、大銀行或是政府性質的部門等實力雄厚的單位是二維條碼的主要使用單位。如果將此技術進一步推廣,市場前景將非常可觀。
本算法已通過軟件實現。
?
參考文獻
1 王新梅.糾錯碼與差錯控制.北京:人民郵電出版社,2001.4:242～293
2 R.E.Blahut，徐秉錚譯.差錯控制碼的理論與實踐.廣州:華南理工大學出版社,1988
3 S.Lin，T.Kasam.Encoding and decoding of reed-solomon?codes in dual basis.電子學報,1986;(4):6～20
4 曹志剛,錢亞生.現代通信原理.北京:清華大學出版社,1992:332～364