臺灣博碩士論文加值系統

階層樹集合分割演算法(Set Partitioning in Hierarchical Tree, SPIHT)是一種對小波轉換係數很有效率的編碼法，可提供失真與無失真的資料壓縮。
原始SPIHT演算法需要大量的記憶體支援以及耗費大量的運算時間，十分不利於即時的應用和硬體實現。為了克服這兩個問題，一改良型階層樹集合分割編解碼演算法(MSPIHT)已被提出。它採用位元平面(Bit-plane)輸入方式，以旗標陣列(Flag Array)取代傳統SPIHT演算法所使用的列表(List)，可有效地改善記憶體需求過大的問題。此外，在編碼流程中亦也將三個列表(LIP、LSP、LIS)的處理流程加以整合，減少列表個別執行處理所耗費的時間。並使用檢查碼(Check Bit)的概念來降低編碼流程中，搜尋後代係數所需之時間。此改良型SPIHT編解碼演算法更具模組化和規律性，可使得編碼流程和編碼時間更加快速且穩定。
本論文藉由ALTERA DE2-115開發平台，以可程式化系統單晶片(SOPC)方式實現此改良型SPIHT演算法，除了功能驗證外亦探討其效能。實驗結果顯示此改良型SPIHT演算法相較於傳統方法，在不同壓縮率下編碼速度提升約70~90倍，並節省了40%記憶體需求。

The SPIHT scheme can be very efficient for data inherent in hierarchical self similarities. However, this scheme which exploited the self similarities in terms of dynamic data structures, imposed practical limitation on hardware implementation, especially for large-size data sequences. A Modified Set Partitioning In Hierarchical Trees (MSPIHT) Algorithm was proposed for solving these problems. Different from SPIHT, the MSPIHT used the Bit-Plane and flag concepts, which can reduce memory requirements and speed up the coding process. Besides, three lists in SPIHT coding process: LIP, LSP, and LIS were combined into one step to simplify the complexity of MSPIHT coding process. The searching time of descendant coefficient was also reduced by using Check Bit. Comparing with SPIHT, MSPIHT had more regular coding process, lower coding complexity, and shorter coding time.
In this study, we utilized ALTERA DE2-115 as a platform to implement MSPIHT coding by using SOPC. According to the experiment result, the hardware could be exactly implemented. Furthermore, MSPIHT encoding process was 70-90 times faster than SPIHT, and reduced 40% memory requirement.

摘要 I
ABSTRACT II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第一章 緒論 1
1-1 研究動機與目的 2
1-2 應用於心電圖之資料壓縮方法探討 3
1-3 研究方法 3
1-4 實驗設備 4
1-5 論文架構 5
第二章 小波轉換理論與心電圖壓縮系統 6
2-1 小波轉換 6
2-2 一維遞迴式離散周期性小波轉換(1-D DPWT) 7
2-3 一維非遞迴式離散周期性小波轉換(1-D NRDPWT) 10
2-4 心電圖壓縮系統 18
2-4-1 基於傳統小波轉換的心電圖壓縮系統 18
2-4-2 基於RRO-NRDPWT的心電圖壓縮系統 19
第三章 SPIHT壓縮編碼演算法 21
3-1 壓縮編碼 21
3-2 SPIHT壓縮編碼概述 22
3-3 SPIHT編碼演算法 24
3-4 SPIHT編碼流程 32
第四章 改良式SPIHT編碼演算法 42
4-1 SPIHT編碼之特性分析 42
4-2 MODIFIED SPIHT編碼演算法 47
4-3 MSPIHT編碼流程 57
第五章 系統架構及設計 63
5-1 開發背景 63
5-2 SOPC 64
5-3 開發流程工具 65
5-4 NIOS II微處理器 69
5-5 SOPC開發流程 70
5-6 系統架構 75
5-7 系統流程 76
第六章 實驗結果與分析 77
6-1 SPIHT硬體實現研究方式 77
6-2 SPIHT實驗結果分析 79
第七章 結論 84
7-1 結論 84
參考文獻 85

[1]Z. Lu,Y. D. Kim, and W. A. Pearlman, “Wavelet compression of ECG signals by the set partitioning in hierarchical trees (SPIHT) algorithm,” IEEE Transactions on Biomedical Engineering, vol. 47, pp. 849-856, 2000.

[2]B. U. Kohler, C. Hennig, and R. Orglmeister, “The principles of software QRS detection,” IEEE Engineering in Medicine and Biology Magazine, vol. 21, pp. 42-57, 2002.

[3]T. H. Chiang, and L. R. Dung, “A VLSI progressive coding for wavelet-based image compression,” IEEE Transactions on Consumer Electronics, vol. 53, pp. 569-577, 2007.

[4]W. B. Huang, Y.J. Chang, A.W.Y. Su, and Y.H. Kuo, “VLSI design Of A DWT/modified efficient SPIHT based image codec,” 4th Pacific Rim Conf. on Multimedia, 2003.

[5]C. T. Ku, H. S. Wang, K. C. Hung, and Y. S. Hung “A novel ECG data compression method based on nonrecursive discrete periodized wavelet transform,” IEEE Transactions on Biomedical Engineering,vol. 53, pp. 2577-2583, 2006.

[6]C. T. Ku, H. S. Wang, K. C. Hung, and Y. S. Hung “High efficient ECG compression based on reversible round-off non-recursive 1-D discrete periodized wavelet transform,” Medical engineering & physics, vol. 29, pp. 1149-1166, 2006.

[7]C. T. Ku, H. S. Wang, K. C. Hung, and Y. S. Hung “A Novel ECG Data Compression Based On Reversible Round-Off 1-D NRDPWT,” pp. 602-605, 2006.

[8]I. Daubechies, “Ten lectures on wavelet,” Ser. No.61 in CBMS-NSF series in Applied Mathematics. Philadelphia, PA: SIAM, 1992.

[9]K. C. Hung, Y. S. Hung, F. C. Hung, and J. C. Wang “An AOCA-based VLSI architecture for non-recursive 2D discrete periodized wavelet transform,” 14th Int. Conf. on Digital Signal Processing, Santorini, Greece, vol. 1, pp. 273-276, 2002.

[10]C. T. Ku, H. S. Wang, K. C. Hung, and T. C. Wu, “Wavelet-Based ECG Data Compression System With Linear Quality Control Scheme,” IEEE Transactions on Biomedical Engineering, vol. 57, pp. 1399-1409, 2010.

[11]A. Said and W. A. Pearlman, “A new, fast, and efficient image codec based on set partitioning in hierarchical trees,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, pp. 243-250, 1996.

[12]J. M. Shapiro, “Embedded image coding using zerotrees of wavelet coefficients,” IEEE Transactions on Signal Processing, vol. 41, pp. 3445-3462, 1993.

[13]K. Liu, E. Belyaev, and J.Guo, “VLSI Architecture of Arithmetic Coder Used in SPIHT,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, pp. 1-14, 2011.

[14]A. Nandi and R. Banakar, “Hardware modeling and implementation of modified SPIHT algorithm for compression of images,” 2th Int. Conf. on Industrial and Information Systems, 2007.

[15]E. Sharifahmadian, “Wavelet compression of multichannel ECG data by enhanced set partitioning in hierarchical trees algorithm,” 28th Int. Conf. on EMBS Annual, 2006.

[16]Y. Sun, H. Zhang, G.. Hu, “Real-time implementation of a new low-memory SPIHT image coding algorithm using DSP chip,” IEEE Transactions on Image Processing, vol. 11, pp. 1112-1116, 2002.

[17]Z. Wang and Y. Chen, “ECG signal compression based on MSPIHT algorithm,” 5th Int. Conf. on Information Technology and Application in Biomedicine, 2008.

[18]陳同孝、黃國峰、張真誠，2004，數位影像處理技術，旗標出版社。

[19]呂嘉陞，2008，心電圖學必備，第五版，合記出版社。

[20]鐘國亮，2004，資料壓縮的原理與應用，第二版，全華出版社。

[21] 潘松、黃繼業、曾毓，2006，SOPC設計實務，全華科技圖書。

[22]廖裕評、陸瑞強，2011，系統晶片設計-使用Nios II，第二版，全華圖書。

[23] Altera Corporation, 2011, Nios II Processor Reference Handbook,
http://www.altera.com/literature/lit-nio2.jsp

[24] Altera Corporation, 2009, Nios II Hardware Development Tutorial,
http://www.altera.com/literature/tt/tt_nios2_hardware_tutorial.pdf

[25]MIT心律不整心電圖資料庫http://www.physionet.org/physiobank/database/mitdb/