淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2106200713512200
中文論文名稱 QR Code解碼器的設計與錯誤修正碼的研究
英文論文名稱 Design of QR Code Decoder and Research of Error Correction Code
校院名稱 淡江大學
系所名稱(中) 電機工程學系碩士班
系所名稱(英) Department of Electrical Engineering
學年度 95
學期 2
出版年 96
研究生中文姓名 陳威志
研究生英文姓名 Wei-Chih Chen
學號 694390278
學位類別 碩士
語文別 中文
口試日期 2007-05-29
論文頁數 67頁
口試委員 指導教授-簡丞志
委員-鄭智湧
委員-陳明達
中文關鍵字 錯誤修正碼  矩陣式條碼 
英文關鍵字 ECC  Mask  Error correction capability  RS Code 
學科別分類 學科別應用科學電機及電子
中文摘要   視能障礙輔助器之學習平台架構分為八部分,其中包含資料庫建檔、資料編碼、圖片產生、影像擷取、影像處理、錯誤修正、資料解碼、音源連結。本文提出一個符合QR Code錯誤修正能力的演算法,可解決擷取QR Code影像或影像處理時資料錯誤的發生,因此,視能障礙者讀取的pattern,經解碼後可信度將會提高。本文除了概述QR Code特性,編碼方式,錯誤修正等級和編碼驗證之外,特別著重在研究QR Code中ECC的演算法。我們將它分為兩部份,第一部份為小解碼,包括Pattern大小、儲存的模式、資料的擺設、MASK的種類資料的編碼、修正等級…等。第二部份為大解碼,QR Code的優勢是擁有極高的錯誤修正能力,因過程繁瑣,將這部份歸納為大解碼。採用錯誤控制碼中的一種叫Reed-Solomon Code,來實現錯誤修正,負責修正接受到的錯誤資料。本文採用Shortened的Reed-Solomon Code演算法來使QR Code Pattern的樣本數增加,編解碼器之研究結果以Visual C++作模擬,可滿足大部分的pattern大小及不同的修正等級,效果在於修正能力範圍內的錯誤,可完全修正。未來此平台將以DSP實現。
英文摘要 The learning platform for visual disabilities contains eight parts –establish data base, data encoding, pattern product, image capturing, image processing, error correction, decoding and sound connection. An algorithm in this work conform the function of QR Code ECC, which can be used to solve the errors occurring in image capturing or image processing. Therefore, after the process of decoding, the ability of a Dysopia person to read patterns can be improved.Aside from our focus on the algorithm in QR code ECC, QR code characteristics, encoding modes, ECC levels and encoding verification are introduced in this work as well. We divide the algorithm into two parts. The first part contributes to the minor decoding which covers the pattern size, storage modes, data placement, Mask level, encoding data and ECC level, etc. The second part corresponds to the extremely high error correction capability in QR code. Due to the complicated process in error correction, we use a certain method in ECC code, and it is named Reed-Solomon Code. This work incorporates the algorithm of Shortened RS Code to increase QR code pattern samples. Afterwards, the results are simulated by VC++. We claim the learning platform can be implemented by DSP hardware in the future.
論文目次 頁目錄
中文摘要 Ⅰ
英文摘要 Ⅱ
頁目錄 Ⅴ
圖目錄 Ⅷ
表目錄 Ⅹ

第一章緒論 1
1.1 前言 1
1.2 研究動機與目標 2
1.3 未來視障者之新式學習 3
1.4 流程簡介與研究方向 4

第二章 QR Code之背景 6
2.1 選用之考量因素 6
2.2 QR Code之發展歷史 7
2.3 QR Code之特性 8
2.3.1 High Capacity Encoding of Data 8
2.3.2 Small Printout Size 9
2.3.3 Dirt and Damage Resistant 10
2.3.4 Kanji and Kana Capability 10
2.3.5 Readable from any direction in 360° 11
2.3.6 Structured Append Feature 11
2.4 QR Code之編碼方式 12
2.4.1 QR Code之容量 12
2.4.2錯誤修正能力 17
2.4.3 QR Code架構 25

第三章 QR Code編碼 28
3.1 概述 28
3.2 編碼實例 29
3.3 編碼之驗證 38
3.5 結論 40

第四章 QR Code解碼器之ECC研究 42
4.1 概述 42
4.2 解碼 43
4.2.1資訊區之解碼 44
4.2.2 反Mask之動作 50
4.2.3 錯誤數量變換公式 52
4.2.4 ECC之研究 53
4.2.5 資料區之解碼 55
4.2.6錯誤修正之結果模擬 59
4.3 驗證 62
4.4 結論 63

第五章 結論 64
5.1 總結 64
5.2 未來研究方向 65
參考文獻 66

圖目錄
圖1.1 點字範例 3
圖1.2 QR Code點字範例3
圖1.3 平台架構流程圖5
圖2.1 QR Code之高容量特性 8
圖2.2 一維條碼及QR Code輸出大小比較圖9
圖2.3 Micro QR Code與QR Code輸出大小比較圖9
圖2.4 QR Code之修正特性10
圖2.5 QR Code支援片假名及漢字之10
圖2.6 QR Code可360度讀取之特性11
圖2.7 QR Code可分割讀取之特性11
圖2.8 QR Code架構圖25
圖2.9 資料區填入方式示意圖 26
圖2.10資訊區分佈圖 27
圖3.1 RS Code編碼電路 31
圖3.2 資料區填入後之QR Code圖形34
圖3.3 編碼之最終圖形37
圖3.4 QR Code編碼程式38
圖3.5 編碼程式輸出結果38
圖3.6 程式產生之QR Code範例 39
圖4.1解碼流程圖43
圖4.2影像處理後之矩陣值 44
圖4.3資訊區讀取範例 45
圖4.4設定三個錯誤之範例 47
圖4.5反Mask之範例 50
圖4.6 Mask之實例 51
圖4.7解碼範例59
圖4.8錯誤修正結果範例60
圖4.9錯誤修正的兩個範例61

表目錄
表2.1 QR Code之Data容量表 8
表2.2 Version1~Version10的Data容量 13
表2.3 Version11~Version20的Data容量14
表2.4 Version21~Version30的Data容量15
表2.5 Version31~Version40的Data容量16
表2.6 各錯誤修正等級之修正能力17
表2.7 Version1~Version8錯誤修正特性 18
表2.8 Version9~Version14錯誤修正特性 19
表2.9 Version15~Version19錯誤修正特性 20
表2.10 Version20~Version25錯誤修正特性 21
表2.11 Version26~Version30錯誤修正特性 22
表2.12 Version31~Version35錯誤修正特性 23
表2.13 Version36~Version40錯誤修正特性 24
表3.1 Version1之容量表 29
表3.2 字元符號對照表 30
表3.3 Reed-Solomon Code之生成多項式對照表 32
表3.4 多項式之α對照表 33
表3.5 Mask對照表 35
表3.6修正等級之二進制表示 36
參考文獻 參考文獻

[1] 曾琴蓮,李俊秀,世界發明、發現大事典,1995出版。
[2] 莫俊鴻,QR碼之編碼及解碼器平臺設計,淡江大學電機研究所碩論文,民國九十五年。
[3] Liangzheng Xia, Digital Image Processing, Southeast University Publishing House, NanJing, China, 1999.
[4] Garm Yu, Z. Y. Wang, Yi Li, Ling He, “An application and implementation of two-dimensional symbols for circuit board quality control system,” IEEE International Conference, June 2004, pp. 379-401.
[5] R. Muniz, L. Junco, and A. Otero. “A Robust Software Barcode Reader Using the Hough Transform,” 1999 International Conference on Information Intelligence and Systems, IEEE, IEEE Computer Society Press, 1999, pp. 313–319.
[6] H. Kurosaka, K. Miyamoto, Y. Nagase, H. Ikegami, K. Sato, and M. Otsubo. “Mobile Phone Application LSI Design Using C based Design Methodology,” Technical Report 4, NEC Corporation, Apr. 2003.
[7] Stephen B. Wicker, Error Control Systems for Digital Comunication and Storage, USA: 1995.
[8] ISO/IEC 18004:2005. Information technology – Automatic identification and data capture techniques – Bar code symbology – QR Code, 2005.
[9] http://www.denso-wave.com/qrcode/index-e.html
[10] http://www.swetake.com/whatsnew.html.
[11] 陳政雄,利用VLSI設計一低複雜度的RS編/解碼架構,中正大學電機研究所碩士論文,民國九十年。
[12] Shu Lin, Daniel J. Costello, Error Control Coding, USA: 2004.
[13] O’Gorman, F., and M.B. Clowes, “Finding Picture Edges through Collinearity of Feature Points”, IEEE Transactions on Computers, vol. C-25, 1976, pp. 449-454.
[14] E. Ohbuchi, H. Hanaizumi, and L.A. Hock, “Barcode readers using the camera device in mobile phones,” International Conference on Cyberworlds, Nov. 2004, pp. 260-265.
[15] Joiner, L.L.; Komo, J.J., “Time domain decoding of extended Reed-Solomon codes,” Southeastcon '96. 'Bringing Together Education, Science and Technology'., Proceedings of the IEEE, 11-14 Apr. 1996, pp. 238-241.
[16] Khan, M.A.; Afzal, S.; Manzoor, R., “Hardware implementation of shortened (48,38) Reed Solomon forward error correcting code, “Multi Topic Conference, 2003. INMIC 2003. 7th International, 8-9 Dec. 2003, pp. 90-95.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2009-06-28公開。
  • 同意授權瀏覽/列印電子全文服務,於2009-06-28起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信