(3.236.231.61) 您好!臺灣時間:2021/05/11 22:30
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:李明宗
研究生(外文):Ming-Chung Lee
論文名稱:腓特比解碼器之路徑計量值記憶體連結複雜度之降低研究
論文名稱(外文):Reducing Interconnect Overhead for Efficient Path Metric Memory Management in Viterbi Decoder
指導教授:謝明得謝明得引用關係許明華許明華引用關係
指導教授(外文):Ming-Der ShiehMing-Hwa Sheu
學位類別:碩士
校院名稱:國立雲林科技大學
系所名稱:電子與資訊工程研究所碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:103
中文關鍵詞:腓特比解碼器定位模式面積有效率架構
外文關鍵詞:Viterbi decoderarea-efficient architecturein-place mode
相關次數:
  • 被引用被引用:1
  • 點閱點閱:126
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:18
  • 收藏至我的研究室書目清單書目收藏:0
在數位通訊系統領域中,腓特比演算法(VA)為一公認的有效率之近似解碼演算法,並已廣泛地應用在迴旋碼的解碼上。在腓特比解碼器(VD)的實現上,如何有效管理路徑計量值記憶體(PMMU)並搭配運算單元(ACSU),以提高PMMU與ACSU間之等效記憶體頻寬同時簡化之間的連間線複雜度,已成為實現VD的關鍵技術之一。針對此問題,本論文首先研究蝴蝶模組與定位模式(in-place mode)間的特性,提出系統化公式將路徑計量值記憶體分割成許多區塊。另外,為了更有效降低PMMU與ACSU間連接線面積,我們發展一新定位模式(extended in-place mode)之演算法,此演算法可使得記憶體區塊與蝴蝶模組間的接線方式為單一且直接之區域化(locally)形式。本論文所發展之記憶體的管理架構具有下列的特性: (1)記憶體可以有系統的分割成多個獨立的區塊, (2)可應用於不同系統需求之實現和 (3)硬體實現簡易且控制電路具規則性。最後,我們將此研究成果應用於DAB (4,1,6)及CDMA (3,1,8)兩種系統之VD設計上,以達到理論與實際相結合之目的。
The Viterbi algorithm, widely used in digital communications, is known to be an efficient method for the realization of maximum likelihood decoding of convolutional codes. Of the key techniques to successfully designing the Viterbi decoders, how to efficiently manage the path metric memory unit (PMMU) and at the same time to minimize the interconnection networks between PMMU and add_compare_select unit (ACSU) is always a key concern of hardware implementation.
In this thesis, we first derive a systematic method for conflict-free address arrangement of in-place path metric update according to the butterfly-based computation. In this manner, we can increase the equivalent memory bandwidth at the expense of more complicated interconnects. To further reduce the interconnect overhead, we present a novel and efficient in-place scheduling technique, denoted as the extended in-place scheduling, such that every ACSU will only access a dedicated, partitioned memory bank; therefore, the interconnection network is simplified and the bank becomes conceptually local to the specific ACSU.
The resulting architecture has the following characteristics: (1) The whole memory can be systematically partitioned into several sets of banks and each set can be treated as a local memory of a specific ACSU. (2) The implementation can be derived in a simple way with regular controlling circuitry (3) The result can be easily applied to different applications of Viterbi decoder and the effectiveness of the developed techniques is very apparent for convolutional codes with a long memory order. Finally, to show the resulting performance, we apply the presented techniques to both DAB (4, 1, 6) and CDMA (3, 1, 8) systems and demonstrate the flexibility of our development.
中文摘要........................................... i
英文摘要........................................... ii
誌謝.............................................. iv
目錄.............................................. v
表目錄............................................ vii
圖目錄............................................ viii
第一章 簡介........................................ 1
第二章 迴旋碼與腓特比解碼器之架構......................4
2.1 迴旋碼..................................... 4
2.2 腓特比演算法................................ 6
2.2.1 腓特比演算法之歷史演進................... 6
2.2.2 腓特比演算法之解碼程序................... 6
2.3 腓特比解碼器之主要單元........................ 8
2.3.1 分支計量值單元..........................9
2.3.2 加-比較-選擇單元........................9
2.3.3 路徑計量值記憶體單元.....................11
2.3.4 存活記憶體單元..........................13
2.3.5 存活記憶體之追溯策略.....................16
2.3.5.1 各種追溯演算法.....................17
2.3.5.2 各種演算法之比較................... 21
2.4 架構分類.................................... 22
第三章 高效率且系統化之記憶體管理...................... 28
3.1 傳統定位模式之記憶體管理...................... 29
3.2 圖形理論之記憶體分割方式...................... 30
3.2.1 圖形理論............................... 30
3.2.2面積有效率之硬體架構..................... 31
3.3 系統化記憶體分割方式.......................... 33
3.3.1 旋轉及對稱特性.......................... 33
3.3.2 記憶體分割公式.......................... 35
3.3.3 系統化分割之硬體架構.................... 36
3.4 新發展之定址模式與架構........................ 44
3.4.1 新定位模式............................. 47
3.4.2 新定位模式之硬體架構.................... 49
3.4.3 簡化修正電路........................... 55
3.4.4 虛擬記憶體區塊之形式.................... 58
3.5 效能評估與比較............................... 63
第四章 (4,1,6)(3,1,8)VD之設計...................... 65
4.1 BMU之架構.................................. 69
4.2 ACSU之架構................................. 70
4.3 PMMU之架構................................. 72
4.4 AGU之架構.................................. 72
4.5 SMU架構................................... 73
4.6 N=64 P=8腓特比解碼器之模擬結果............... 74
4.6.1 BMU電路之模擬結果...................... 74
4.6.2 ACSU電路之模擬結果..................... 75
4.6.3 PMMU與AGU電路之模擬結果............... 76
第五章 結論 ....................................... 81
參考文獻........................................... 83
自傳.............................................. 88
[1] W. W. Peterson and E. J. Weldon, Jr., Error-Correcting Codes. Cambridge, MA: MIT Press, 1972.
[2] Stephen B. Wicker, Error Control Systems for Digital Communication and Storage. Prentice-Hill, 1995.
[3] A. J. Viterbi, “Convolutional codes and their performance in communication systems,” IEEE Transactions on Communications Technology, Vol. COM-19, No. 5, pp.751-772, Oct. 1971.
[4] 吳建明,謝明得,多功能腓特比解碼器之探討與應用於DAB系統的實現,雲林科技大學電子與資訊工程研究所碩士論文,1999
[5] A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Transactions on Information Theory, IT-13, pp. 260-269, Apr. 1967.
[6] J. K. Omura, “On the Viterbi decoding algorithm,” IEEE Transactions on Information Theory, Vol. 15, No. 1, pp. 177-179, Jan. 1969.
[7] H. L. Lou, “Implementing the Viterbi algorithm,” IEEE Signal Processing Magazine, Vol. 12, No. 5, pp. 42-52, Sep. 1995.
[8] C. B. Shung, P. H. Siegel, G. Ungerboeck, and H. K. Thapar, “VLSI architectures for metric normalization in the Viterbi algorithm,” IEEE ICC, Vol. 4, pp. 1723-1728, Apr.1990.
[9] C. M. Rader, “Memory management in a Viterbi decoder,” IEEE Transactions on Communications, COM-29, No.9, pp. 1399-1401, Sep. 1981.
[10] M. Biver , H. Kaeslin, and C. Tommasini, “ In-place updating of path metrics in Viterbi decoders,” IEEE Journal of Solid-State Circuit, Vol. 24, No.4 pp. 1158-1159, Aug. 1989.
[11] K. J. McGee, “Comment on in-place update of path metrics in Viterbi decoders,” IEEE Journal of Solid-State Circuits, Vol. 25, No. 4, pp. 1039-1040, Aug. 1990.
[12] D. A. F. Ei-Dib and M. I. Elmasry, “Low-power register-exchange Viterbi decoder for high-speed wireless communications” IEEE ISCAS, Vol. 5, pp. V737-740, May. 2002.
[13] T. K. Truong, M.-T. Shih, I. S. Reed, and E. H. Satorius, “A VLSI design for a trace-back Viterbi decoder,” IEEE Transactions on Communications, Vol. 40, No. 3, pp. 616-624, Mar. 1992.
[14] P. J. Black and T. H.-Y. Meng, “Hybrid survivor path architectures for Viterbi decoders,” IEEE ICASSP, Vol. 1, pp. 433-436, Apr. 1993.
[15] E. Boutillon and N. Demassieux, “High speed low power architecture for memory management in a Viterbi decoder,” IEEE ISCAS, Vol. 4, pp. 284-287, May 1996.
[16] M.-B. Lin, “New path history management circuit for Viterbi decoders” IEEE Transactions on Communications, Vol. 48, pp. 1605-1608, Oct. 2000.
[17] R. Cypher and C. B. Shung, “Generalized trace back techniques for survivor memory management in the Viterbi algorithm,” IEEE GLOBECOM, Vol. 2, pp. 1318-1322, Dec. 1990.
[18] G. Feygin and P. G. Gulak, “Survivor sequence memory management in Viterbi decoders,” IEEE ISCAS, Vol. 5, pp. 2967-2970, Jan. 1991.
[19] G. Feygin and P.G. Gulak, “Architectural tradeoffs for survivor sequence memory management in Viterbi decoder,” IEEE Transactions on Communications, Vol. 41, No. 3, pp. 425-429 Mar. 1993.
[20] C. B. Shung, H.-D. Lin, R. Cypher, P. H. Siegel, and H. K. Thapar, “Area-efficient architectures for the Viterbi algorithm - Part I: theory,” IEEE Transactions on Communications, Vol. 41, No. 4, pp. 636-543, Apr. 1993.
[21] C. B. Shung, H.-D. Lin, R. Cypher, P. H. Siegel, and H. K. Thapar, “Area-efficient architectures for the Viterbi algorithm - Part II: applications,” IEEE Transactions on Communications, Vol. 41, No. 4, pp. 802-807, May 1993.
[22] J. Sparso, H. N. Jorgensen, E. Paaske, S. Pedersen, and T. Rubner-Petersen: An area-efficient topology for VLSI implementation of Viterbi decoders and other shuffle-exchange type structures,” IEEE Journal of Solid-State Circuit, Vol. 26, No. 2, pp. 90-96, Feb. 1991.
[23] T. Gemmeke, M. Gansen, and T. G. Noll, “Implementation of scalable power and area efficient high-throughput Viterbi Decoder” IEEE Journal of Solid-State Circuit, Vol. 37, pp. 941-948, Jul. 2002.
[24] G. Fettweis and H. Meyr, “A 100Mbit/s Viterbi decoder chip: novel architecture and its realization,” IEEE SUPERCOM, Vol. 2, Apr. 1990.
[25] G. Fettweis and H. Meuer, “High-speed parallel Viterbi decoding: algorithm and VLSI architecture,” IEEE Communication Magazine, Vol. 29, pp. 46-55, May 1991.
[26] P. J. Black and T. H. Meng, “A 140-Mb/s, 32-state, radix-4 Viterbi decoder”, IEEE Journal of Solid-State Circuit, Vol. 27, pp. 1877-1885, Dec. 1992.
[27] C. Y. Chang and K. Yao, “Systolic array processing of the Viterbi algorithm”, IEEE Transactions on Information Theory, Vol. 35, No. 1, pp. 76-86, Jan. 1989.
[28] P. G. Gulak and T. Kailath, “Locally connected VLSI architectures for the Viterbi algorithm,” IEEE Journal on Selected Areas in Communications,” Vol. 6, No. 3, pp. 527-537, Apr. 1988.
[29] G. Feygin, P. G. Gulak, and P. Chow, “Generalized cascade Viterbi decoder- a locally connected multiprocessor with linear speed-up,” IEEE ICASSP, Vol. 4, pp. 1097-1100, Apr. 1991.
[30] G. Feygin, P. G. Gulak, and P. Chow, “A multiprocessor architecture for Viterbi decoders with linear speedup,” IEEE Transactions on Signal Processing, Vol. 41, No. 9, pp. 2907-2917, Sep. 1993.
[31] C.-W. Wang and Y.-N. Chang, “Design of Viterbi decoders with in-place state metric update and hybrid traceback processing,” IEEE Workshop on Signal Processing System, pp. 5-15, Sep. 2001.
[32] M. Boo, F. Arguello, J. D. Bruguera, R. Doallo, and E. L. Zapata, “High-Performance VLSI Architecture for the Viterbi Algorithm,” IEEE Transactions on Communications, Vol. 45, No. 2, pp. 168-176, Feb. 1997.
[33] S. Kubota, S. Kato, and T. Ishitani, “Novel Viterbi decoder VLSI implementation and its performance,” IEEE Transaction on Communication, Vol. 41, No. 8, pp. 1170-1178, Aug. 1993.
[34] T. Ishitani, K. Tansho, N. Miyahara, S. Kubota, and S. Kato, “A scarce-state-transition Viterbi-decoder VLSI for bit error correction,” IEEE Journal of Solid-State Circuit, Vol. 22, No. 4, pp. 575-581, Aug. 1987.
[35] G. Fettweis and H. Meyr, “Parallel Viterbi algorithm implementation: breaking the ACS-Bottleneck,” IEEE Transaction on Communication, Vol. 37, No. 8, pp. 785-790, Aug. 1989.
[36] B. K. Min and N. Demassieux, “A versatile architecture for VLSI implementation of the Viterbi algorithm,” IEEE ICASSP, Vol. 2, pp. 1101-1104, Apr. 1991.
[37] L. G. Johnson, “Conflict free memory addressing for dedicated FFT hardware,” IEEE Transactions on Circuits and System-II: Analog and Digital Signal Processing, Vol. 39, No. 5, pp. 312-316, May 1992.
[38] M.-D. Shieh, M.-H. Sheu, C.-M. Wu, and W.-S. Ju, “Efficient management of in-place path metric update and its implementation for Viterbi decoders” IEEE ISCAS, Vol. 4, pp. 449-452, Jun. 1998.
[39] C.-M. Wu, M.-D. Shieh, C.-H. Wu, and M.-H. Sheu, “An efficient approach for in-place scheduling of path metric update in Viterbi decoders” IEEE ISCAS, Vol. 3, pp. 61-64, 2000.
[40] C.-M. Wu, M.-D. Shieh, C.-H. Wu, and M.-H. Sheu, “VLSI architecture of extended in-place path metric update for Viterbi decoders” IEEE ISCAS, Vol. 4, pp. 206-209, May 2001.
[41] S.-Y Kim, H. Kim, and I.-C. Park, “Path metric memory management for minimizing interconnections in Viterbi decoders” IEE Electronics Letters, Vol. 37, No. 14, pp. 925-926, Jul. 2001.
[42] J. Kwak, “A simple and efficient path metric memory management for Viterbi decoder composed of many processing elements” IEEE Transactions on Communication, Vol. E86-B, No. 2, pp. 844-846, Feb. 2003.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔