臺灣博碩士論文加值系統

　　應用於計算循環冗餘檢查碼(CRC)的Linear Feedback Shift Register (LFSR)電路，平行處理技巧是提供了在低運作頻率下提高輸出量 (throughput) 的方法。理想上，LFSR電路每週期處理M位元的資料其運作頻率可以減少為原來的M倍。但是由於增加輸出量LFSR電路中的Feedback Loop電路複雜度也會跟著增加，導致critical path時間延遲增加而限制了實際的輸出量增加只為原來的M/2倍。在本論文中，我們利用狀態-空間轉換技巧將M位元LFSR電路中Feedback loop電路的複雜度降為和一位元相同的LFSR電路。再透過pipeline技巧使整個電路的critical path時間延遲降低進而使實際輸出量提高至預期的M倍。最後我們更以狀態-空間轉換技巧為基礎發展了CRC產生器。透過CRC產生器可以自動產生指定的CRC電路。

　　Parallelization of the linear-feedback shift register used to compute the cyclic redundancy code (CRC) has long been recognized as a way to increase throughput. In all applications of this technique reported previously, the achievable increase in throughput is limited by an increase in the circuit complexity within the feedback loop; for a cir¬cuit that processes M bits of the input sequence in parallel, the throughput increase, or speed-up, appears to be asymptotically lim¬ited to M/2. In this thesis, we use a state-space transformation technique for the M-bits-at-a-time CRC system that reduces the complexity of its feed¬back loop to exactly that of the original one-bit-at-a-time system. The resulting hardware implementations can achieve a full speed-up factor of M compared to the one-bit-at-a-time system. We also develop the CRC generator to generate synthesizable Verilog RTL codes for specified generating polynomials.

Chapter 1 Introduction............................1
1.1 Introduction to Data Transmission and
Storage System............................1
1.2 Motivation................................2

Chapter 2 Mathematical Background.................5
2.1 Introduction to Algebra...................5
2.1.1 Groups....................................5
2.1.2 Fields....................................6
2.1.3 Binary Field Arithmetic...................6
2.2 Linear Block Codes........................9
2.2.1 Linear Systematic Block Code.............10
2.2.2 Syndrome and Error Detection.............12
2.3 Cyclic Codes.............................17
2.3.1 Encoding of Cyclic Codes.................19
2.3.2 Syndrome Computation.....................20
2.3.3 Error-Detecting Capability...............21
2.4 Cyclic Redundancy Codes Computation......23
2.4.1 Implementing the CRC Algorithm in Hardware.
.........................................25
2.4.2 Commonly Used CRC Polynomials............27

Chapter 3 High-speed CRC Computations............28
3.1 Parallel CRC Computation.................29
3.2 Lookahead Techniques for Parallel CRC
Computations.............................32
3.3 State-Space Transformation...............40
3.3.1. State-Space Transformation for CRC.......43
3.3.2. Pipelining Outside the Feedback Loop.....46

Chapter 4 Efficient Design of State-Space Transformation.........................49
4.1 Derivation for Practical Use.............50
4.2 System Block.............................52
4.3 Hardware Implementation..................53
4.3.1 Block 1 – Computation Block.............53
4.3.2 Block 2 - BMt and A-(M-F) × T coefficient
block....................................57
4.3.3 Block3 – Core Feedback Loop Circuit.....59
4.3.4 Example..................................60
4.3.5 Timing Diagram...........................62
4.3.6 Area Distribution........................63
4.3.7 Interface Description....................64
4.3.8 Experiment results.......................65

Chapter 5 CRC Generator..........................66
5.1 Graphical User Interface of CRC Generator
.........................................66
5.2 C++ Codes................................68
5.3 Matlab Codes.............................70

Chapter 6 Conclusions and Future Works...........72
6.1 Conclusions..............................72
6.2 Future Works.............................73

References.......................................74
Appendix A.......................................76
C++ Codes........................................76
Appendix B.......................................88
Matlab Codes – Generate matlab_def.v............88

[1]S. Lin and D. J. Costello, Jr, Error Control Coding: Fundamentals and applications, Prentice-Hall, Inc., 1983.

[2]S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice-Hall, Inc., 1995.

[3]T. B. Pei and C. Zukowski, "High-speed parallel CRC circuits in VLSI," IEEE Transactions on Communications, Vol. 40, No. 4, pp. 653-657, 1992.

[4]M. D. Shieh, H. F. Lo, and M. H. Sheu, “A systematic approach for parallel CRC computation,” Journal of Information Science and Engineering, Vol. 17, pp. 445-461, May 2001.

[5]J.H. Derby, “High-speed CRC computation using state-space transformations,” in Proc. Global Telecommunications Conference, Vol.1, pp. 166 -170, Nov. 2001.

[6]T. V. Ramabadran and S. S. Gaitonde, "A tutorial on CRC computations," IEEE Micro, Vol. 8, No. 4, pp. 62-75, 1988.

[7]T. Henriksson, H. Eriksson, U. Nordqvist, P. Larsson-Edefors, and D. Liu, “VLSI implementation of CRC-32 for 10 Gigabit Ethernet,” in Proc. International Conference on Electronics, Circuits and Systems, Vol. 3, pp. 1215 -1218, Sep. 2001.

[8]F. Monteiro, A. Dandache, A. M'Sir, and B. Lepley, “A polynomial division pipelined architecture for CRC error detecting codes,” in Proc. 13th International Conference on Microelectronics, pp. 133-136, Oct. 2001.

[9]G. Campobello, G. Patane, and M. Russo, “Parallel CRC realization,” IEEE Transactions on Computers, Vol.52, pp. 1312 -1319, Oct. 2003.

[10]R. J. Glaise and X. Jacquart, "Fast CRC calculation," in Proc. IEEE International Conference on Computer Design, pp. 602-605, 1993.

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

[12]A. Perez, "Byte-wise CRC calculation," IEEE Micro, Vol. 3, No. 3, pp. 40-50, 1983.

[13]J. H. Derby, "Parallel encoders for cyclic codes using state-space transformations," to be submitted to IEEE Trans. communication.