臺灣博碩士論文加值系統

本論文提出運用RS碼(Reed-Solomon Codes)於MPEG-4極低位元率影音編碼的容錯度技術。雖然MPEG-4已提出了一些針對容錯度(Error Resilience)的處理工具，例如：重新同步(Resynchronization)、資料分割(Data Partitioning)、資料恢復(Data Recovery)之可逆式變長度碼(RVLCs, Reversible Variable Length Codes)、蓋錯(Error Concealment)以及檔頭延伸碼(HEC, Header Extension Code)等技術，但是這些方法在檢測到錯誤資料後，都只在處理如何減少錯誤資料的移除量，避免將整個資料移除，但是對於錯誤的資料並無法進一步做資料更正。
而RS碼已被證實是一種功能強大的錯誤更正碼，它對於多重的錯誤具有相當高的偵測及更正能力，目前已被應用在許多的系統上，包括：(1)資料儲存設備(Storage Devices)，例如：磁帶(Tape)、CD(Compact Disk)、DVD(Digital Video Disc)、條碼(Barcodes)；(2)無線或移動通訊(Wireless or Mobile Communications)上，例如：數位細胞式行動電話(Cellular Telephones)、微波通訊(Microwave Links)；(3)衛星通訊(Satellite Communications)；(4)數位電視(Digital Television)；以及(5)高速數據機(High-Speed Modems)，例如：非對稱式數位迴路系統(ADSL, Asymmetric Digital Subscriber Line)。由此可見，如果能將RS碼對錯誤資料的偵測及更正能力，應用到MPEG-4極低位元率影音編碼的資料傳輸上，勢必大幅提高MPEG-4的容錯度功能。
因此，本論文研究發現以質因數計算的Cooley-Tukey演算法可以用於RS解碼上，以計算 的 點轉換(其中 )，而且這種RS解碼方法較直接計算所需的乘法運算及加法運算減少許多。而且，若將此快速RS解碼法，運用在MPEG-4的容錯技術上，可以改善傳統MPEG-4的容錯技術，且非常適用於極低位元率影音編碼的資料傳輸。

This thesis proposes a Fast Reed-Solomon decoding method to improve the error-resilient coding of MPEG-4 for low-bit-rate audiovisual coding. The error-resilient tools adopted by MPEG-4 can be classified as follows: the resynchronization, the data partitioning, the reversible variable length coder (RVLC) of data recovery, the error concealment, and the header extension code (HEC). These tools detect and locate errors, support fast resynchronization, and prevent the loss of entire information. Typical decoders discard all data between the two resynchronization markers as being in error.
Furthermore, Reed-Solomon codes are used to correct errors in many application systems including: 1) storage devices such as tape, compact disk (CD), digital video disc (DVD), barcodes; 2) wireless or mobile communications such as cellular telephones, microwave links; 3) satellite communications; 4) digital television; and 5) high-speed modems such as asymmetric digital subscriber line (ADSL). Thus, if the Reed-Solomon codes can be used for the error-resilient coding of MPEG-4, it will perform a better performance for low-bit-rate audiovisual coding.
In this thesis it is shown that the Cooley-Tukey algorithm with prime factors can be modified to decode the Reed-Solomon codes over , where . Finally, the proposed Reed-Solomon decoder is used along with the MPEG-4 algorithm for the error resilience. It is shown by computer simulation that this new method improves the error resilience technique and obtains a better performance than the conventional MPEG-4 method.

中文摘要．．．．．．．．．．．．．．．．．．．．．．． 1
英文摘要．．．．．．．．．．．．．．．．．．．．．．． 3
目錄．．．．．．．．．．．．．．．．．．．．．．．．． 5
第一章 緒言．．．．．．．．．．．．．．．．．．．．． 6
1-1研究背景．．．．．．．．．．．．．．．．．．．． 7
1-2研究動機與目的．．．．．．．．．．．．．．．．． 9
1-3論文架構．．．．．．．．．．．．．．．．．．．． 10
第二章 MPEG-4容錯度處理技術．．．．．．．．．．．．． 10
2-1重新同步．．．．．．．．．．．．．．．．．．．． 10
2-2資料恢復．．．．．．．．．．．．．．．．．．．． 12
2-3蓋錯．．．．．．．．．．．．．．．．．．．．．． 12
第三章 Reed-Solomon編解碼原理．．．．．．．．．．．． 14
3-1 RS數學定義 ．．．．．．．．．．．．．．．．．． 14
3-2 RS編碼法 ．．．．．．．．．．．．．．．．．．． 16
3-3 RS解碼法 ．．．．．．．．．．．．．．．．．．． 18
第四章 Cooley-Turkey演算法 ．．．．．．．．．．．．． 22
4-1 離散傅立葉轉換 ．．．．．．．．．．．．．．．． 22
4-2 快速傅立葉轉換．．．．．．．．．．．．．．．．．． 23
4-3 Cooley-Tukey質因數演算法 ．．．．．．．．．．． 28
第五章 RS編解碼器．．．．．．．．．．．．．．．．．． 43
5-1 RS編碼器 ．．．．．．．．．．．．．．．．．．． 43
5-2 RS解碼器 ．．．．．．．．．．．．．．．．．．． 44
第六章 實驗結果．．．．．．．．．．．．．．．．．．． 46
第七章 結論與未來研究．．．．．．．．．．．．．．．． 59
參考文獻．．．．．．．．．．．．．．．．．．．．．．． 60

[1] Peng H. Ang, Peter A. Ruetz and David Auld, “Video compression makes big gains,” IEEE Spectrum, pp.16-19, October 1991.
[2] Garlo Baside et al., “The U.S. HDTV standard and the grand,” IEEE Spectrum, pp. 36-46, April 1995.
[3] D. J. Le Gall, “The MPEG video compression algorithm,” Signal Processing: Image Communication, Vol. 4, No. 2, pp. 129-140, April 1992.
[4] ISO/IEC-13818-2, Generic Coding of Moving Pictures and Associated Audio, International Organization for Standardization, Jan. 1995.
[5] S. Okubo, K. McCann, and A. Lippmann, “MPEG-2 requirements, profiles and performance verification — Framework for developing a generic video coding standard,” Signal Processing: Image Communication, pp. 201-209, July 1995.
[6] ISO/IEC 13818-2, Generic Coding of Moving Pictures and Associated Audio Information: Video, Nov. 1994.
[7] ISO/IEC JTC1/SC29/WG11, Working Draft 3.0 of ISO/IEC 14496-1 N1540, Feb. 1997.
[8] ISO/IEC JTC1/SC29/WG11, Overview of the MPEG-4 Standard, N1730, Stockholm meeting, July 1997.
[9] ISO/IEC JTC1/SC29/WG11, MPEG-4 Applications Document, N1729, Stockholm meeting, July 1997.
[10] ISO/IEC JTC1/SC29/WG11, Working Draft of ISO/IEC 14496-3 MPEG-4 Audio V3.0 Draft, N1631, April 1997.
[11] ISO/IEC JTC1/SC29/WG11, Working Draft 4.0 of ISO/IEC 14496-2, Coding of Moving Pictures and Audio, July 1997.
[12] ISO/IEC JTC1/SC29/WG11, DMIF (Delivery Multimedia Integration Framework) ISO/IEC 14496-6 Working Draft 1.0, N1763, July 1997.
[13] ISO/IEC JTC1/SC29/WG11, MPEG-7: Context and Objectives V4.0, N1733, July 1997.
[14] ISO/IEC JTC1/SC29/WG11, MPEG-7 Applications Document, N1735, July 1997.
[15] ISO/IEC JTC1/SC29/WG11, Second Draft of MPEG-7 Requirements, N1734, July 1997.
[16] J. L. Mitchell, W. B. Pennebaker, C. E. Fogg, and D. J. LeGall, MPEG Video Compression Standard, Chapman & Hall, New York, 1997.
[17] Atul Puri and Tsuhan Chan, Multimedia Systems, Standards, and Networks, Marcel Dekker, New York, 2000.
[18] S. B. Wicker and V. K. Bhargava, Reed-Solomon Codes and Their Application, New York: IEEE Press, 1994.
[19] DVD Specifications for Rewritable Disc (DVD-RAM) Part 1, Sep. 1999.
[20] I. S. Reed and X. Chen, Error-Control Coding for Data Networks, Kluwer Academic Publishers, 2001.
[21] H. Man, F. Kossentini, and Mark J. T. Smith, “A family of efficient and channel error resilient wavelet/subband image coders,” IEEE Trans. Circuits and Syst. Video Technol., vol.9, no.1, pp.95-108, Feb. 1999.
[22] I. Moccagatta, S. Soudagar, J. Liang, and H. Chen, “Error-resilient coding in JPEG-2000 and MPEG-4,” IEEE Journal on Selected Areas in Communications, vol.18, no.6, pp.899-914, June 2000.
[23] R. Talluri, I. Moccagatta, Y. Nag, and G. Cheung, “Error concealment by data partitioning,” Signal Processing: Image Communication, vol.14, pp.505-518, May 1999.
[24] R. Talluri, “Error-resilient video coding in ISO MPEG-4 standard,” IEEE Commun. Mag., vol.36, no.6, pp.112-119, July 1998.
[25] M.H.Jing, Y.H.Chen,T.K.Truong, 2000, “The New Implementation of multiplier andinverse module for the application in Finite Field”, submitted to IEE.
[26] Stephen B. Wicker. “ERROR CONTROL SYSTEMS for Digital Communication and Storage”, Prentice-Hall, Inc, 1995.
[27] I. S. Reed, T. K. Truong, R. L. Miller and B. Benjauthrit, “Further results on fast transforms for decoding Reed-Solomon codes over for ,” Deep Space Network Progress Report 42-50, Jet Propulsion Laboratory, Pasadena, California, pp. 132-154, January 1979.
[28] I. S. Reed, T. K. Truong, “A simplified algorithm for correcting both errors and erasures of RS codes,” Deep Space Network Progress Report 42-48, Jet Propulsion Laboratory, Pasadena, California, September 1978.
[29] J. H. Jeng, T. K. Truong, “On decoding of both errors and erasures of a Reed-Solomon code using an inverse-free Berlekamp-Massey algorithm”, IEEE Trans. Communications, vol. 47, no. 10, Oct. 1999, pp. 1488-1494.
[30] R. L. Miller, T. K. Truong and I. S. Reed, “Efficient program for decoding the (255, 223) Reed-Solomon codes over with both errors and erasures, using transform decoding,” IEE Proc., vol. 127, pt. E, no.10, July 1980.
[31] I. S. Reed, R. A. Scholtz, T. K. Truong, and L. R. Welch, “The fast decoding of Reed-Solomon codes using Fermat theoretic transforms and continued fractions,” IEEE Trans. Inform. Theory, vol. IT-24, no.1, pp.100-106, Jan. 1978.
[32] T. K. Truong, W. L. Eastman, I. S. Reed, and I. S. Hsu, “Simplified procedure for correcting both errors and erasures of Reed-Solomon code using Euclidean algorithm,” IEE Proc., vol. 135, pt. E, no. 6, pp. 318-324, Nov. 1988.
[33] Zhengdao Wang, “Application of Error-Control Coding in Satellite and Wireless Communications,” May 9, 2000.
[34] 王新梅, 肖國鎖, “糾錯碼”, 儒林圖書有限公司, 1993年12月初版。
[35] 金明浩, 陳延華, 張耀祖, 張肇健, 1999 ,” A New VLSI for Implementing the Multiplication and Inverse in the RS-Code” , 第四屆多媒體技術及應用學術研討會, pp.304, 高雄
[36] 金明浩, 袁國元, “利用RS-Code編解碼積體電路實現高可靠度磁碟陣列之研究”, 2000年6月.
[37] 繆紹綱, “數位影像處理活用Matlab”, 全華科技圖書股份有限公司, 1999年3月.