跳到主要內容

臺灣博碩士論文加值系統

(44.200.194.255) 您好!臺灣時間:2024/07/15 01:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林瑋翔
研究生(外文):Wei-Hsiang Lin
論文名稱:改良式重覆相配演算法運用在多常數乘法器上之化簡
論文名稱(外文):Improving Modify IMA perform on MCM’s reduction
指導教授:白宏達
指導教授(外文):Hung-Ta Pai
學位類別:碩士
校院名稱:國立臺北大學
系所名稱:通訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:37
中文關鍵詞:多常數乘法器重覆相配演算法最佳化
外文關鍵詞:MCMIMAIterative Matching Algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:214
  • 評分評分:
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
在積體電路的設計上,有時會使用到大量的多常數乘法器(Multiple Constant Multiplications)。因此,化簡多常數乘法器就變成一個重要的議題。但在實做上因為運算量過大的關係,一直沒有辦法做到最佳化,只能選擇到次佳解。
重覆相配演算法(Iterative Matching Algorithm)一直是多常數乘法器的常見的化簡方式,是一種次佳解的演算法。這是一種運用經驗法則的方法,並不能保證最佳化。本論文提出預測路徑,計算相配位元組合總量,及多位元比較幾個改進方法,以得到在不同情況之下,更好的改進效果。
The design of integrated circuits is often involved with usage of many Multiple Constants Multipliers (MCMs).Therefore, it is very important to reduce the complexity of the MCM. However, the optimal reduction has been very difficult because of the large amount of calculations involved. Several sub-optimal algorithms have been proposed. One of the most popular sub-optimal algorithms is the Iterative Matching Algorithm (IMA).It is derived huristically and acceptable results are obtained under reasonable computational complexity. However, further reduction of the MCM is needed for mobile applications. Three approaches, including Predictive Matching, Total Matchings, and Multi-bit Matching, are proposed to improve the IMA. Simulation results show that these approaches are better than the IMA under most conditions.
1 緒論1
1.1 動機. . . . . . . . . . . . . 1
1.2 多常數乘法器簡化問題. . . . . 3
1.3 論文結構. . . . . . . . . . . 5
2 現有的多常數乘法器化簡方法. . . 7
2.1 秦氏搜尋法. . . . . . . . . . 7
2.2 重覆相配演算法(Iterative Matching Algorithm) . . 8
2.3 修正式重覆相配演算法(Modified Iterative Matching Algorithm) . . . . . . . . 19
3 在MIMA 實做基礎上新的演算法. . . . .21
3.1 預測路徑. . . . . . . . . . . . . 21
3.2 計算相配位元組合可供化簡的總數. . 24
3.3 多列(欄) 比對 . . . . . . . . . . 26
4 實驗結果 . . . . . . . . . . . . . 30
4.1 重覆相配演算法(Iterative Matching Algorithm) 的結果和修正式重覆相配演算法(Modified Iterative Matching Algorithm) 的結果的比較. . . . . . . . . . . 30
4.2 預測路徑和可化簡值和之前的比較. . . . . . . . . 32
5 結論 . . . . . . . . . . . . . .36
A.V.Oppenheim and R.W.Schafer, Discrete-Time Signal Processing 2/e, Prentice Hall,
New Jersey, 1999.
A.Chatterjee, R.K.Roy, and M.A.d’Abreu, “Greedy hardware optimization for linear
digital circuits usingnumber splitting and refactorization,” IEEE Transactions on Very
Large Scale Integration (VLSI) Systems, vol. 1, pp. 423–431, Dec 1993.
S.T.J.Fenn, M.Benaissa, and D.Taylor, “Gf(2m) multiplication and division over the
dual basis,” IEEE Transacitons on Computers, vol. 45, pp. 319–327, Mar. 1996.
M. Potkonjak, M.B.Srivastava, and A.Chandrakasan, “Efficient substitution of multiple
constant multiplications by shifts and additions using iterative pairwise matching,” in
31st Design Automation Conf., pp. 189– 194, 1994.
M. Potkonjak, M.B.Srivastava, and A.P.Chandrakasan, “Multiple constant multiplications:
Efficient and versatile framework and algorithms for exploring common subexpression
elimination,” IEEE Transactions on Computer-aided Design of Integrated Circuits
and Systems, pp. 151– 165, 1996.
S.Lin and D.J.Costello, Error Control Coding 2/e, Pearson Education International,
NJ, 2004.
R.Chien, “Cyclic decoding procedures for bose- chaudhuri-hocquenghem codes,” IEEE
Transactions on Information Theory, vol. 10, pp. 357– 363, Oct. 1964.
Y.Hung, “Efficient decoding of error control codes for multilevel flash memories,” M.S.
thesis, National Taipei University, 2007.
Y.Chen and K.K.Parhi, “Small area parallel chien search architectures for long bch
codes,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 12,
pp. 545– 549, May 2004.
T.H.Cormen, C.E.Leiserson, and R.L.Rivest, Introduction to Algorithms, The MIT.
Press, Cambridge, 1990.
A.Matsuura, M.Yukishita, and A.Nagoya, “An efficient hierarchical clustering method
for the multipleconstant multiplication problem,” IEEE Transactions on Very Large
Scale Integration (VLSI) Systems, vol. 12, pp. 83–88, Jan. 1997.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top