Cyclic redundancy code（CRC）有著簡單的架構及能夠偵側傳送資料的完整性之優點，因此近年來廣泛地使用於資料通訊與儲存設備中。傳統上利用CRC處理資料的方式為循序式，一次一個位元，然而隨著資料量之增加，勢必浪費許多寶貴的時間。在本論文中，基於Galois Field理論，我們藉由一簡單的Linear feedback shift register (LFSR)線路來實現CRC平行處理，並根據lookahead技術，發展其他LFSR應用上之平行方法。

In recent years, cyclic redundancy code (CRC) has been applied widely in storage devices and data communication because of its simple coding structure and keeping the integrity of transmitted data. In traditional way, data in serial performs the CRC computation one bit at a time. It must waste much time according to an increasing number of data. In this paper, we use a simple linear feedback shift register (LFSR) circuit for parallel CRC computation based on the theory of Galois Field and we are absorbed in developing our parallel approach based on lookahead technique for the other LFSR applications.

摘 要 ……..….…………………………………………………….…………… I
Abstract …..…………….………………………………………………………. II
誌 謝……….…….……………………………………………………………… IV
目 錄…... ………………………..……………………………………………… V
圖目錄………………..…………………………..……………………………… VII
表目錄…………………... ……………………..………………………………. IX
第一章 緒論. ……………………………..…..………………….. 1
第二章 Linear feedback shift register(LFSR)………………. 4
2.1 數學背景…………………………………..………………………… 4
2.2 LFSR之介紹…………..……..……………………………………… 8
2.3 利用LFSR建構有限體 …………………………………….. 9
2.4 利用LFSR求虛擬碼（Pseudorandom number）…………………… 11
2.5 利用LFSR求stream cipher………………………………………… 13
第三章 Cyclic redundancy code（CRC）…………….…………. 16
3.1 Cyclic redundancy code (CRC)之介紹與基本原理……..………….. 16
3.2 CRC之範例………………..…..……………………………….……... 19
第四章 平行技術（Parallel technique）…….…………….……. 23
4.1 CRC之平行技術………………………………………….………… 23
4.2 CRC平行技術之範例…………………….………………………… 27
4.3 模擬結果……………..…………………………………………….. 29
第五章 Cyclic redundancy code（CRC）之更新………………… 31
5.1 CRC之平行處理技術：lookahead 技術….. ……………………….. 31
5.2 新的更新CRC之平行處理方法………………………………..….. 34
5.3 我們提出方法之通式（General form）…………………………….…. 41
5.4 模擬結果…………………………………………………………….. 42
第六章 Data scrambler……………………………….….….……. 44
6.1 Data scrambler的介紹及其範例………………………...…………... 44
6.2 Data scrambler平行技術之通式……………………………………. 56
6.3 模擬結果…………………………………………..……………….. 64
第七章 未來工作及研究方向……………………………………. 65
參考文獻……………………..……………………………………. 66

[1] S. Lin and D.J. Costello, Jr, “Error Control Coding : Fubndamentals and Applications,” Prentice-Hall, Inc., 1995.
[2] W. W. Peterson and E. J. Weldon, “Error-Correcting Codes,” Cambrige, MA: The MIT Press. 1972.
[3] A. Perez, “Byte-wise CRC Calculation,” IEEE Micro,Vol.3,No.3,pp.40-50,Oct. 1983
[4] T.B. Pei and C. Zukowski, “High-Speed Parallel CRC Circuits in VLSI,”IEEE Transactions on Communications, Vol.40,No.4,pp.653-657,April 1992.
[5] Ming-Der Shieh, Ming-Hwa Sheu, Chung-Ho Chen and Hsin-Fu Lo, “A Systematic Approach for Parallel CRC Computations,” Journal of information Science and Engineering,No.36,pp.1-20, 1999.
[6] R. F. Hobson and K. L. Cheung,” A High-Performance CMOS 32-Bit Parallel CRC Engine,” IEEE Journal of Solid-State Circuits, Vol. 34,No. 2,pp. 233-235, February 1999.
[7] T. V. Ramabadran and S. S. Gaitonde, “A Tutorial on CRC Computations,” IEEE Micro, Vol. 8, No. 4, pp.62-75, Aug 1988.
[8] G. Albertengo and R. Sisto, “Parallel CRC Generation,”IEEE Micro, pp.63-71, Oct. 1990.
[9] R. J. Glaise and X. Jacquart, “Fast CRC Calculation,” in Proc. IEEEE International Conference on Computer Design, pp. 602-605, Oct. 1993.
[10] Michael Gutman, “A Method for Updating a Cyclic Redundancy Code, ”IEEE Transactions on Communications, Vol.40, No.6, pp.989-991, June 1992.
[11] R. F. Hobson and K. L. Cheung, “A High-Performance CMOS 32-Bit Parallel CRC Engine,” IEEE Journal of Solid-State Circuits, Vol. 34, No. 2, pp. 233-235, February 1999.
[12] David R. Smith “Digital Transmission Systems,”pp.322-329,Van Nostrand Reinhold, 1993.
[13] J.J. Spilker, Jr. Ph.D. “Digital Communications by Satellite,”pp.486-491, Prentice-Hall, Inc., 1995.