利用平行處理架構之  CRC  網路封包錯誤更正器研製

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：75

、訪客IP：18.117.70.24

姓名

歐亭鎔(Ting-rong Ou) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

利用平行處理架構之 CRC 網路封包錯誤更正器研製
(The Design and Implementation of CRC Based Packet ErrorCorrector Using Parallel Architecture)

相關論文

★ 利用智慧天線系統實現精準室內定位技術	★ 電力線通訊之競爭存取與路由方法設計與實現
★ 設計與實作基於GRAPES函式庫之P2P即時串流系統	★ 利用離散餘弦基礎之聲音浮水印達到室內定位技術
★ 利用虛擬指紋建置法之智慧型天線系統實現精準室內定位技術	★ 即時影像串流自適應播放系統之研究
★ 利用模糊邏輯控制器於蜂巢式網路降低位置管理機制成本	★ 基於支持向量機及模糊推理之地震預警系統研製
★ 基於行動裝置之分散式多人會議系統	★ 以分群為基礎之3D無線與光學網路晶片頻道存取方法
★ 基於收前先聽LBR機制之授權型輔助接入LAA架構下於異質網路中暴露節點之研究	★ 支援跳頻之IEEE 802.15.4 ZigBee無線隨身網路機制設計與實現
★ 應用於IEEE 802.16行動無線都會網路省電模式參數設定之智慧策略	★ IEEE 802.15.4 ZigBee 無線隨身網路高效能路由演算法分析與設計
★ 應用於IEEE 802.16無線寬頻都會網路之具調適性自動重傳請求回報機制	★ 無線感測網路為基礎之空間平面圖自動建構之技術

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

現今的網路模型中的媒體存取控制（Medium Access Control - MAC）層使用
CRC-32 的編碼方式，先對原始資料進行編碼之後封裝為資料訊框再進行傳輸。當
接收端收到資料訊框後，會計算此訊框的 CRC-32 餘數以檢查所接收到的訊框是否
正確。如果 CRC-32 檢測訊框有錯誤，接收端的 MAC 層會使用 ARQ（Automatic
Repeat reQuest）協定進行訊框的重傳，以期待再次的重傳可以收到正確的訊框。
ARQ 詳細的運作機制如下，當傳送端送出訊框後，會等待接收端對這個訊框回應
一個「確認收到(acknowledge, ACK)」的訊息。如果經過一段時間傳送端沒有收到
ACK（稱之為 timeout），很可能接收端沒有收到該訊框或收到有錯的訊框（經由
CRC-32 檢查機制），這時傳送端就會重傳此訊框，以期待再次的重傳可以成功。
ARQ protocol 使得訊框得以在不可靠的通訊通道中提供可靠的通訊。從資訊理論的
角度可以發現一個位元的錯誤會造成整個資料訊框的錯誤與重送。因此，如果能適
當儲存之前發生錯誤的原始訊框資料，並比對重送但仍發生錯誤之訊框資料，有相
當大的機會可以找出正確的原始訊框資料，也因此達到 MAC 層支援錯誤修正之能
力。延續我們先前所研發的 CRC 網路封包錯誤更正器[1]，本論文進一步利用平行
架構來實作 CRC 網路封包錯誤更正器以減低電路複雜度以及所花費的時間。

摘要(英)

Usually, data frames encapsulated in the medium access control MAC layer are
protected by the well-known CRC-32 mechanism. The CRC-32 redundant information is
produced by encoding the original data according to a pre-specified polynomial function.
Upon the receiver receiving the data frame, it calculates the CRC-32 remainder of the
received frame for determining whether the received data frame is correct or not. If the
checking fails, the automatic repeat request (ARQ) protocol of MAC layer will be triggered to
retransmit the erroneous data frame from transmitter to receiver. ARQ protocol is designed to
achieve reliable transmissions over unreliable channel, and thus the packet loss probability is
decreased. However, there is an issue that one erroneous data bit in a data frame will cause
whole data frame to be retransmitted. This thesis proposes to properly store erroneous data
frame(s) and combine it with the newly retransmitted frame may find out the original data
frame. Based on our preliminary work [1], this thesis further utilizes the parallel architecture
to construct the CRC based packet error corrector, which has the features of low circuit
complexity and short processing time, as compared to the previously developed serial CRC
based packet error corrector (CEC).

關鍵字(中)

★ 封包錯誤更正

關鍵字(英)

★ CRC

論文目次

CONTENTS
中文摘要 ................................................................................................................................... iv
ABSTRACT ............................................................................................................................... v
CONTENTS .............................................................................................................................. vi
FIGURE LIST ........................................................................................................................... ix
TABLE LIST ............................................................................................................................. xi
1 INTRODUCTION ................................................................................................................... 1
2 BACKGROUND ..................................................................................................................... 3
2-1 The Basic Concept of FEC ............................................................................................ 4
2-2 The Basic Concept of ARQ ........................................................................................... 5
2-3 The Basic Concept of HARQ ........................................................................................ 6
2-4 The Basic Concept of CRC Detection ........................................................................... 9
2-5 Computation of CRC ..................................................................................................... 9
2-5-1 Serial Computation of CRC ....................................................................................... 9
2-5-2 Parallel computation of CRC ................................................................................... 10
3 RELATED WORKS ............................................................................................................. 11
4 CRC BASED ERROR CORRECTOR (CEC) ...................................................................... 13
4-1 Linear Feedback Shift Register (LFSR) ...................................................................... 13
4-2 The Concept of CEC ................................................................................................... 15
4-3 The CEC Type-I Scheme ............................................................................................. 20
4-4 The CEC Type-II Scheme ........................................................................................... 21
4-5 The Analysis of Processing Delay of CEC Scheme .................................................... 25
4-5-1 Processing Delay of CEC Type-I Scheme ............................................................... 25
4-5-2 Processing Delay of CEC Type-II Scheme ............................................................. 25
5 CRC-BASED ERROR CORRECTOR USING PARALLEL ARCHITECTURE (P-CEC) 27
5-1 The P-CEC Type-I Scheme ......................................................................................... 27
5-2 The P-CEC Type-II Scheme ........................................................................................ 29
5-3 The Analysis of Processing Delay of P-CEC Scheme ................................................ 32
5-3-1 Processing Delay of P-CEC Type-I Scheme ........................................................... 32
5-3-2 Processing Delay of P-CEC Type-II Scheme .......................................................... 32
6 THE BACKGROUND OF SIMULATION .......................................................................... 33
6-1 The Flow of Digital Circuit ......................................................................................... 33
6-2 The Software of Digital Circuit-Modelsim、Quartus II ............................................. 34
6-3 Hardware Description Language-Verilog ................................................................... 34
6-4 Introduction of FPGA .................................................................................................. 35
7 SIMULATION AND VERIFICATION ................................................................................ 37
7-1 The Specification of Simulation .................................................................................. 37
7-2 The CEC Type-I Simulation and Verification ............................................................. 44
7-2-1 The CEC Type-I Simulation .................................................................................... 44
7-2-2 The CEC Type-I Verification .................................................................................. 46
7-2-3 The CEC Type-I Synthesis ...................................................................................... 47
7-3 The CEC Type-II Simulation and Verification ........................................................... 48
7-3-1 The CEC Type-II Simulation .................................................................................. 48
7-3-2 The CEC Type-II Verification ................................................................................. 49
7-3-3 The CEC Type-II Synthesis ..................................................................................... 51
7-4 The P-CEC Type-I Simulation and Verification ......................................................... 52
7-4-1 The P-CEC Type-I Simulation ................................................................................ 52
7-4-2 The P-CEC Type-I Verification .............................................................................. 53
7-4-3 The P-CEC Type-I Synthesis .................................................................................. 55
7-5 The P-CEC Type-II Simulation and Verification ........................................................ 56
7-5-1 The P-CEC Type-II Simulation ............................................................................... 56
7-5-2 The P-CEC Type-II Verification ............................................................................. 57
7-5-3 The P-CEC Type-II Synthesis ................................................................................. 59
7-6 The Comparison of CEC and P-CEC .......................................................................... 60
8 CONCLUSIONS ................................................................................................................... 61
9 REFERENCES ...................................................................................................................... 62

參考文獻

[1] Huei-Yu Lee, ―A CRC Based Error Corrector (CEC) for Wireless Networks,‖ National
Central University Department of Communication Engineering, National Central
University Master thesis, Jul. 1998.
[2] H. Dubois-Ferri`ere, D. Estrin, and M. Vetterli, ―Packet Combining in Sensor Networks,‖
in Proceedings of the ACM International Conference on Embedded Networked Sensor
Systems, pp. 102–115, Nov. 2005.
[3] B. Han, L. J, S. Lee, B. Bhattacharjee, and R. R. Miller, ―All Bits are not Equal-a Study
of IEEE 802.11 Communication Bit Errors,‖ in INFOCOM, pp. 1602–1610, Apr. 2009.
[4] M. Zorzi, ―Some Results on Error Control for Burst-error Channels Under Delay
Constraints,‖ IEEE Transactions on Vehicular Technology, Vol. 50, pp. 12–24, Jan. 2001.
[5] A. Miu, H. Balakrishnan, and C.E. Koksal, ―Improving Loss Resilience with Multi-radio
Diversity in Wireless Networks,‖ in Proceedings of the ACM International Conference on
Mobile Computing and Networking (MOBICOM), pp. 16–30, Aug. 2005.
[6] R.J. Benice and A. J. Frey, ―Comparisons of Error Control Techniques,‖ IEEE
Transactions on Communication Technology, Vol 12, pp. 146-154, Dec. 1964.
[7] Peterson, W. W. and Brown, D. T., ―Cyclic Codes for Error Detection‖, Proceedings of
the IRE 49: 228, Jan. 1961.
[8] S. Joshi, P. Dubey and M. Kaplan, ―A New Parallel Algorithm for CRC Generation,‖
IEEE International Conference on Communications, Vol. 3, pp.18-22, Jun. 2000.
[9] Campobello G, Patane G, Russo M., ―Parallel CRC Realization,‖ IEEE Transactions on
Computers, 52 (10), pp. 1312–1319, 2003.
[10] P.S. Sindhu, ―Retransmission Error Control with Memory,‖ IEEE/ACM Transactions on
Networking, Vol. 25, pp. 473–479, May1977.
[11] S.S. Chakraborty, E.Y., and M. Liinaharja, ―An ARQ Scheme with Packet Combining,‖
IEEE Communications Letters, Vol. 2, pp. 200–202, Jul. 1998.

指導教授

許獻聰(Shiann-tsong Sheu)

審核日期

2010-7-26

推文