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