基于四叉樹的高速乘法器算法研究

摘要：提出了一種基于四叉樹結構的高速乘法器自動綜合優化算法以提升乘法器運算速度。首先對延時較大的高位積采用四叉樹遞歸直接構建，取代傳統部分積進位鏈，縮短關鍵路徑時延，進而進行分支折合和合并，相鄰乘法結果共享部分四叉樹，降低硬件開銷。算法同時支持不同面積約束下的自動綜合。依此算法的乘法器相比基于Booth算法和Wallace樹的乘法器速度提高了10％。

關鍵詞：進位鏈；延遲；四叉樹；分支合并；分支折合；遍歷

中圖分類號：TP309 文獻標志碼：A 文章編號：1001－3695(2010)10－3727－04