QR Code解碼器的設計與錯誤修正碼的研究

Design of QR Code Decoder and Research of Error Correction Code

陳威志(Wei-Chih Chen)

指導教授 ： 簡丞志

淡江大學/工學院/電機工程學系碩士班/碩士(2007年)

https://doi.org/10.6846/TKU.2007.00634

摘要

視能障礙輔助器之學習平台架構分為八部分，其中包含資料庫建檔、資料編碼、圖片產生、影像擷取、影像處理、錯誤修正、資料解碼、音源連結。本文提出一個符合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.

並列關鍵字

ECC ； Mask ； Error correction capability ； RS Code

參考文獻

[2] 莫俊鴻，QR碼之編碼及解碼器平臺設計，淡江大學電機研究所碩論文，民國九十五年。

[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.

[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.