臺灣博碩士論文加值系統

對於實現高解碼吞吐量的低密度奇偶檢查碼(Low-Density Parity Check Codes, LDPC codes) 使用最小和演算法(Min-Sum Algorithm, MSA)硬體，傳統數位電路在檢查節點更新(check-node units, CNU)實現找正確的前兩小值以及他們的位置(index)是採用樹狀結構演算法，然而此演算法在多項輸入比較值特別是在找尋第二小值，會對硬體面積以及複雜度產生很大的影響。本篇論文提出將數位域(digital-domain)轉成時域(time-domain)的方式來找尋正確前兩小值，因時域計算相較數位電路可以改善在多筆輸入訊號或長字長(long word length)情況的硬體複雜度，並且也有降低電路延遲(latency)等優點。

然而同樣採取時域計算的ISSCC2013[8]在長字長情況下，數位時域轉換器的硬體面積會有越來越大的趨勢且運算速度會降低。為了增加運算速度以及減少晶片面積，這篇論文亦提出針對各輸入比較訊號的最高位元(Most significant bit, MSB)資料做先行處理：設計出一種分類電路將其分類再將剩餘的數位值轉時域做計算，以此達到減少延遲電路數量的目的。本篇論文為了了減少設計的複雜度跟降低電路布局時間，除了為了減少高延遲電路的硬體面積以及因在數位流程中沒有仲裁電路布局是使用自行電路佈局方式，其他電路以及最後的架構整合均使用數位電路設計流程。本篇論文提出兩種依據解碼吞吐量(throughput)要求找小值電路架構，相較於傳統數位電路實現方式，可以減少約30%的晶片面積以及減少電路延遲。

For low-density parity-check (LDPC) decoders using the min-sum algorithm, the first two minimum values and the first minimum index must be found when updating the check node. Conventionally, this minimum-value finder is implemented digitally using a tree-structure scheme. In this thesis, we propose time-domain minimum-value finders, which process the mixed analog and digital signals. In addition, we propose digital to time converter (DTC) that firstly computes the signal of the most significant bit (MSB) in order to reduce the area of the delay elements. Compared to the conventional tree-structure-based scheme, the proposed time-domain minimum-value finders can reduce chip area and latency by more than 30\%.

1 簡介
1.1 動機
1.2 論文架構
2 背景
2.1 回顧低密度機偶檢查碼
2.2 最小和演算法
2.3 檢查節點找小值電路
2.4 回顧：LDPC找小值電路
2.4.1 數位方式：樹狀結構
2.4.2 類比計算：電壓域方式
2.4.3 類比計算：時域方式
3 時域最小值尋找電路
3.1 構想
3.2 有序排列
3.2.1 仲裁電路
3.2.2 有序排列數位時域轉換器設計
3.2.3 電路佈局
3.3 無序排列
3.3.1 概念
3.3.2 MUX架構數位時域轉換器
3.3.3 改良式數位時域轉換器
3.3.4 改良式仲裁電路
4 比較與結論
4.1 有序排列比較
4.2 無序排列比較
4.3 結論

IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless, IEEE Std 802.16e-2005 Std., 2006.
IEEE Standard for Information technology–Telecommunications and information exchange between systems–Local and metropolitan area networks, IEEE Std 802.11n-2009 Std., 2009.
A. Morello and V. Mignone, “DVB-S2: The second generation standard for satellite broad-band services,” Proceedings of the IEEE, vol. 94, no. 1, pp. 210 –227, 2006.
Mobile Multimedia Broadcasting (P. R. China) Part 1: Framing Structure, Channel Coding and Modulation for Broadcasting Channels, Std.
Quality Supervision and Quarantine, GB 20600-2006, digital terrestrial television broadcasting transmission system frame structure, channel coding and modulation, Beijing: China Standard Press Std., 2006.

C. L. Wey, M. D. Shieh and S. Y. Lin, “Algorithms of Finding the First Two Minimum Values and Their Hardware Implementation”, IEEE Trans on Circuits and Systems-I: regular paper, vol. 55, no. 11, pp. 3430-3437, Dec. 2008.
S. Hemati, A. Banihashemi, and C. Plett, “A 0.18- m CMOS analog min-sum iterative decoder for a (32,8) low-density parity-check (LDPC) code,” IEEE J. Solid-State Circuits, vol. 41, no. 11, pp.2531–2540, Nov. 2006.
Miyashita, D., Yamaki, R., Hashiyoshi, K., Kobayashi, H., Kousai, S., Oowaki, Y., Unekawa, Y., “A 10.4pJ/b (32, 8) LDPC decoder with time-domain analog and digital mixed-signal processing”, ISSCC Dig. Tech. papers, pp. 420-421, 2013.

R. G. Gallager, "Low-density parity-check codes," IRE Trans. Inf. Theory, vol. IT-8, pp21-28, Jan. 1962.
D. J. C. Mackay and R.M. Neal, "Near Shannon limit performance of low density parity check codes," Letters, col. 33, no. 6, pp. 457-458, Jun. 1996.
R. M. Tanner, "A recursive approach to low-complexity codes," IEEE Trans. Inf. Theory, vol. IT-27, no. 5, pp. 533-547, Sep. 1981.
C. L. Wey, M. D. Shieh and S. Y. Lin, “Algorithms of Finding the First Two Minimum Values and Their Hardware Implementation”, IEEE Trans on Circuits and Systems-I: regular paper, vol. 55, no. 11, pp. 3430-3437, Dec. 2008
S. Hemati, A. Banihashemi, and C. Plett, “A 0.18- m CMOS analog min-sum iterative decoder for a (32,8) low-density parity-check (LDPC) code,” IEEE J. Solid-State Circuits, vol. 41, no. 11, pp.2531–2540, Nov. 2006.
Miyashita, D., Yamaki, R., Hashiyoshi, K., Kobayashi, H., Kousai, S., Oowaki, Y., Unekawa, Y., “A 10.4pJ/b (32, 8) LDPC decoder with time-domain analog and digital mixed-signal processing”, ISSCC Dig. Tech. papers, pp. 420-421, 2013
Clark, L.T., Mozdzen, T.J., Hindman, N.D. , Chella, S. , Holbert, K.E.,” Temporal sequential logic hardening by design with a low power delay element,” RADECS 2011 12th European Conference on, pp.144-149, Sept. 2011 .
C.Y. Yu, C.C. Chung, C.J. Yu, C.Y. Lee,” A Low-Power DCO Using Interlaced Hysteresis Delay Cells”, Circuits and Systems II: Express Briefs, IEEE Transactions on , vol.59, pp.673-677, Oct. 2012 .