臺灣博碩士論文加值系統

科技的進步使得晶片面積愈小，而密度也相對地變大。也因此更突顯晶片內部繞線的高複雜度與低可靠度，進而影響晶片在生產時的良率(yield)。若能減低晶片內部傳輸的錯誤率，便可提高其可靠度。現今的晶片在傳輸資料大多以數位的方式，也有一部份的電子產品在傳送訊號時，相當容易產生出高電位轉為低電位的錯誤情況，因而將傳輸環境設定在完全非對稱通道上。
在完全非對稱通道的通訊上，伯登碼及伯格碼乃眾所皆知之編碼技術，而M-out-of-N Codes是其伯登碼之特例，以上技術皆為錯誤偵測更正之用。匯流排反相碼雖為減低匯流排功率消耗用途之編碼方法，但是將其方法應用於上述三個編碼技術上，更能降低完全非對稱通訊系統的傳輸錯誤率，也可降低在傳輸之中的功率消耗。在本論文中便提出反相編碼法，且依照三個編碼技術的特性，各別提出不同的最佳化方法，並計算出錯誤率的減少，最後再加以統整、比較。
從分析及實驗中，可得知改善後的伯登碼可降低12-21%的錯誤率，而M-out-of-N Codes降低14-31%的錯誤率，伯格碼亦可降低12-21%的錯誤率。再者伯格反相編碼方法具有匯流排反相碼的特性，尚可減少7-14%的資訊功率消耗。

Advances of technology make small area and large density in the chip. Therefore routing of high complexity and low reliability emerge from the chip, which affect the yield of production. If the internal parts of chip reduce the error rate, that reliability can be improved. Present chips mostly transfer data in a digital way. Because part of the electronic products in the transmission signal is relatively easy to produce a error conditions, which the signal reduce high voltage to low voltage, the transmission environment set up in fully-asymmetric channel.
In a communication of fully-asymmetric channel, the Borden codes and Berger codes are well known of the coding techniques, while the M-out-of-N codes is the special case of Borden codes. The above coding are error detection technology. Although the bus-invert codes can reduce power consumption of bus, that property add to the three coding technology above, which can reduce fully-asymmetric word error rate and the power consumption of bus. In this paper, we proposed inverting coding to improve the three coding techniques that present different optimization methods in accordance with the characteristics of individual and calculate the error rate reduction. Finally, it discusses and compares the advantages and disadvantages of these improved coding.
From the analysis and experiments, the improved code can reduce the Borden codes 12-21% error rate, while the M-out-of-N codes to reduce 14-31% error rate and Berger code can be reduced 12 -21% error rate. Moreover, Berger invert codes has the characteristics of bus-invert codes, they also can reduce the 7-14% of power consumption.

中文摘要 i
Abstract ii
致 謝 iii
目 錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 1
1.3 研究目的 2
1.4 本文架構編排 3
第二章 錯誤更正碼概論 5
2.1 背景及應用 5
2.2 通道及雜訊 6
2.3 編碼器類型 10
2.3.1 迴旋碼 10
2.3.2 區塊碼 10
2.4 錯誤更正碼類型 11
2.4.1 描述方式分類 11
2.4.2 行為分類 11
第三章 反相編碼方法 13
3.1 整體編解碼系統 13
3.2 模組及宣告 13
3.3 反相技術 14
3.3.1 伯登碼 15
3.3.2 M-out-of-N Codes 20
3.3.3 伯格碼 20
3.3.3.1 伯格反相碼 21
3.3.3.2 平行加法器 23
第四章 實驗結果 26
4.1 M-out-of-N Codes 26
4.2 伯登碼 27
4.3 伯格碼 29
4.3.1 電路設計 29
4.3.2 功能測試之驗證 31
4.3.3 電路佈局及面積比較 32
4.3.4 資訊功率消耗 35
第五章 結論 36
參考文獻 37
作者簡歷 40

圖目錄

圖 1 - 1 系統區塊圖 3
圖 2 - 1 通訊傳輸模型圖 5
圖 2 - 2 編解碼過程示意圖 6
圖 2 - 3 典型資料傳輸區塊圖 7
圖 2 - 4 離散無記憶通道區塊圖 7
圖 2 - 5 二元對稱通道模型圖 8
圖 2 - 6 (a)(b) 二元非對稱通道模型圖 9
圖 2 - 7 迴旋碼的編碼器結構圖 10
圖 2 - 8區塊碼的編碼器結構圖 11
圖 3 - 1 編解碼系統區塊圖 13
圖 3 - 2 匯流排反相碼電路示意圖 15
圖 3 - 3 對稱與非對稱的漢明距離示意圖 16
圖 3 - 4 系統傳輸檢查示意圖 16
圖 3 - 5 伯登碼完全自我檢查電路方塊 17
圖 3 - 6 伯登碼改善方法(1)流程圖 18
圖 3 - 7 伯登碼方法(1)之示意圖 18
圖 3 - 8 伯登碼改善方法(2)流程圖 19
圖 3 - 9 伯登碼方法(2)之示意圖 19
圖 3 - 10 錯誤率減少示意分佈圖(n=6) 20
圖 3 - 11 一個伯格碼 (a)編碼器及(b)檢查器用在完全非對稱通道上 21
圖 3 - 12 在 的BGI 編碼器 23
圖 3 - 13 所提出的BGI 檢查器 23
圖 3 - 14 計數n=14的平行加法器電路 24
圖 3 - 15 計數位元0個數的半加器 24
圖 3 - 16 計數位元0個數的全加器 24
圖 4 - 1 錯誤率減少示意分佈圖(n=14) 27
圖 4 - 2 資訊數量分布比較圖(1) 28
圖 4 - 3 資訊數量分布比較圖(2) 28
圖 4 - 4 伯格反相碼之編碼器電路圖 30
圖 4 - 5 模擬完全非對稱通道之電路圖 30
圖 4 - 6 伯格反相碼之檢查器電路圖 31
圖 4 - 7 傳輸位元0個數較多之波形圖 32
圖 4 - 8 傳輸位元1個數較多之波形圖 32
圖 4 - 9 伯格碼佈局圖 33
圖 4 - 10 伯格反相碼佈局圖 34

表目錄


表 3 - 1 此論文中的宣告及註解 14
表 4 - 1 M-out-of-N Codes錯誤率比較 26
表 4 - 2 錯誤率的比較 29
表 4 - 3 額外面積比較表 35
表 4 - 4 資訊功耗的比較 35
表 5 - 1 各編碼參數比較表 36

[1] T.-C. Huang and C.-N. Liu, “Integrated Invert Codes for Low-Power High-Dependability Encoders and Checkers in NoC,” Submitted to IEEE Trans. on VLSI, Oct. 2008.
[2] C.-N. Liu, S.-D. Lin and T.-C. Huang, “Berger Inver Codes: A Low-Power Dependable Code for Fully Asymmetric Communication,” PAL Consortium Conference on Innovation Applications of System Prototyping and Circuit Design, pp.336-340, Oct. 17, 2008.
[3] C.-N. Liu, S.-C. Lo and T.-C. Huang, “Inverting Codes for Low-Power Dependable Fully Asymmetric Communication and Storage Systems,” ILT Conference, pp.896-901, June 5, 2009.
[4] A. Avizienis, “Arithmetic codes: Cost and effectiveness studies for application in digital system design,” IEEE Trans. Computers, vol. C-20, pp. 1322-1331, Nov. 1971.
[5] Dana Crowe and Alec Feinberg. Design for Reliability. CRC Press, Boca Raton, 2001.
[6] C. V. Freiman, “Optimal error detection codes for completely asymmetric binary channels,” Information and Control, vol. 5, pp. 64-71, Mar. 1962.
[7] G. Corrigan, “Self-Checking Memory Cell Array Apparatus,” US Patnet 373,963, Jul. 7, 1992.
[8] H. Deogun, et. al. “Leakage and Crosstalk-aware Bus Encoding for Total Power Reduction”, In Proc. Design Automation Conference, pages. 779-782, 2002.
[9] M. Nicolaidis, ”Implementation Techniques of Self-Checking Arithmetic Operations and Data Paths Based on Double-Rail and Parity Codes,” US Patent 5,450,340, Sep. 12, 1995.
[10] M. J. Ashjaee and S. M. Reddy, “On totally self-checking checkers for separable codes,” IEEE Trans. Computers, vol. C-26, pp.737-744, Aug. 1977.
[11] J. F. Wakerly, Error, Detecting Codes, Self-Checking Circuits and Applications. New York: Elsevier North-Holland, 1978, pp. 40-50.
[12] M. R. Stan and W. P. Burleson, ”Bus-invert coding for low-power I/O,” IEEE Trans. VLSI Systems, vol. 3, pp. 49–58, Mar. 1995.
[13] Y. Shin, K. Choi, and Y.-H. Chang, “Narrow Bus Encoding for Low-Power DSP Systems,” IEEE Trans. On VLSI Systems, vol.9, no.5, pp.656-660, Oct. 2001.
[14] B. R. Larson, “M out of N Checker Circuit,” US Patent 4,498,177, Feb. 5, 1985.
[15] D.A. Anderson and G. Metze, “Design of Totally Self-Checking Check Circuits for m-Out-of-n Codes,” IEEE Trans. Computers, vol. C-22, pp. 263-269, Mar. 1973.
[16] S.J. Piestrak, ”Design of Self-Testing Checkers for m-out-of-n Codes Using Parallel Counters,” Journal of Electronic Testing: Theory and Applications, vol. 12, pp. 63-68, 1998.
[17] W.-F. Chang and C.-W. Wu, “Low-cost modular totally self-checking checker design for m-out-of-n code,'' IEEE Trans. Computers, vol. 48, no. 8, pp. 815-826, Aug. 1999.
[18] D. A. Pierce Jr. and P. K. Lala, “Modular implementation of efficient self-checking checkers for the Berger code,” Journal of Electronic Testing: Theory and Applications, vol. 9, no. 3, pp.279-294, Dec. 1996.
[19] J. M. Berger, “A note on error detection codes for asymmetric channels,” Information and Control, vol. 4, pp. 68-73, Mar. 1961.
[20] J. F. Wakerly, ”Detection of unidirectional multiple errors using low-cost arithmetic codes,” IEEE Trans. Computers, vol. C-24, pp. 210-212, Feb. 1975.
[21] M. M. Blaum and J. Bruck, ”Method and Apparatus for Encoding and Decoding Unordered Error Correcting Codes,” US Patent 5,285,454, Feb. 8, 1994.
[22] M. A. Marouf and A. D. Friedman, ”Design of self-checking checkers for Berger codes,” in Proc. 8th Annu. Symp. on Fault-Tolerant Computing, Toulouse, France, June 21-23, 1978, pp. 179-184.
[23] N. Izawa and H. Arakawa, “Totally Self-Checking Checker,” US Patent 5,179,561, Jan. 12, 1993.
[24] P. G. Emma, R. K. Montoye, and W. R. Reohr, “Dynamic memory architecture employing passive expiration of data,” US Patent 7,290,203, Oct. 30, 2007.
[25] S. Hideo and G. Kunio, “Optical Recording Medium, Optical Recording Medium Reader-Writer, Information Recording method and Information Reading Method,” Japan Patent 11-296648, Oct. 29, 1999.
[26] S. J. Piestrak, “Design of fast self-testing checkers for Berger codes,” IEEE Trans. Computers, vol. C-36, pp. 629-634, May 1987.
[27] S. J. Piestrak, “Comments on ‘Novel totally self-checking Berger checker designs based on generalized Berger code partitioning’,’’ IEEE Trans. Computers, vol.51, no.6, pp.735-736, June 2002.
[28] G.P. Biswas and I. Sengupta, “A design technique of TSC checker for Borden's code,” VLSI Design, pp. 529-530 Jan. 1997.
[29] N.K. Jha, “A totally self-checking checker for Borden's code,” IEEE Trans. Computer-Aided Design of IC and Systems, vol. 8, pp. 731-736, July 1989 .
[30] K. W. Current, “Pipelined Binary Parallel Counters Employing Latched Quaternary Logic Full Adders,” IEEE Transactions on Computers, vol. C-29, no. 5, pp.400-403, May 1980.
[31] S. Tarnick, “Design of Embedded m-out-of-n Code Checkers Using Complete Parallel Counters,” IEEE Int’l Symp. on On-Line Test, pp.285-292, July 2007.
[32] L. Rong, K. E. Kerr, A. S. Botha, “A novel approach for CMOS parallel counter design,” 25th EUROMICRO Conference, vol. 1, pp.112-119, Sep. 1999.
[33] C. E. Shannon, “A Mathematical Theory of Communication,” Bell Syst. Tech. J., pp. 379-423(Part 1); pp.623-56(Part 2), July 1948.
Books:
[34] 陳後守、邱茂清、王忠炫、吳昭明, “錯誤更正碼(Error-Correcting Codes),” 教育部顧問室通訊科技人才培育先導型計畫, pp.1-10, 2007。