復(fù)數(shù)乘法運算的優(yōu)化方法研究與實現(xiàn)

李立珺

（西安郵電大學(xué) 陜西 西安 710121）

隨著通信及信息處理技術(shù)的發(fā)展，現(xiàn)代數(shù)字信號處理的速度要求越來越高，并且，隨著無線傳輸?shù)念l段越來越豐富，無線傳輸?shù)男诺拉h(huán)境越來越差，這就需要大量數(shù)字信號處理算法去消除信道引入的干擾。數(shù)字信號處理中，最為關(guān)鍵、采用最多的運算器件就是乘法器。由于乘法器的實現(xiàn)是耗費資源的，因此在采用邏輯資源實現(xiàn)乘法器以及復(fù)數(shù)乘法器的優(yōu)化實現(xiàn)方面，已經(jīng)有很多研究成果[1-4]。針對乘法器和復(fù)數(shù)乘法器如何在FPGA 中更有效的使用，在一些專著中給出了一些優(yōu)化方法[5，6]，以及兩大FPGA 提供商也給出了一些指導(dǎo)性的文檔[7-9]。前述研究成果其目的在于如何有效利用邏輯資源去實現(xiàn)乘法器或復(fù)數(shù)乘法器，前述的專著或指導(dǎo)文檔對于FPGA 中如何節(jié)約乘法器資源也只是基于數(shù)字信號處理的速度比較低，采用時分復(fù)用的優(yōu)化方法。在高速數(shù)字信號處理中，最為常用的復(fù)數(shù)乘法器以及FIR 濾波器的架構(gòu)如何優(yōu)化，這方面的研究較少。

文中針對最常用的復(fù)數(shù)乘法器給出了兩種優(yōu)化實現(xiàn)的架構(gòu)，在實現(xiàn)復(fù)數(shù)乘法運算時分別可以節(jié)省25%和50%的乘法器資源。并結(jié)合直接型的FIR 濾波器實現(xiàn)架構(gòu)給出了直接型FIR 濾波器的資源優(yōu)化實現(xiàn)架構(gòu)。同時也針對共軛復(fù)乘給出了相關(guān)的優(yōu)化方法。本文所給出的優(yōu)化方法，基本可以適用于所有的數(shù)字信號處理電路，尤其對于高速的數(shù)字信號處理，可以在節(jié)省資源的情況下，能夠利用流水線滿足高速信號處理的要求。

1 復(fù)數(shù)乘法器基本結(jié)構(gòu)

復(fù)數(shù)乘法運算廣泛的用于數(shù)字信號處理的設(shè)計中，假設(shè)有兩個復(fù)數(shù)x1=a+bj 和x2=c+dj 相乘，如式（1）所示：

其中，I=ac-bd，Q=ad+bc。其直接實現(xiàn)方法就是分別求出ac、bd、ad 和的乘積，然后分別計算I 和Q 的值，其直接實現(xiàn)架構(gòu)如圖1 所示。由圖1 可以看出，復(fù)數(shù)乘法的直接實現(xiàn)占用了4個乘法器，2個加法器。在實際設(shè)計的過程中，乘法器比加法器要耗費更多的資源；并且即使使用FPGA 中的乘法器IP 核來做乘法，其乘法器的IP 核資源也是十分有限的。

如果設(shè)計中所采用的乘法器的運行時鐘頻率不是很高，遠小于FPGA 所能支持的最高速率，可以使用時分復(fù)用的方式來節(jié)省乘法器資源。例如，如果要求復(fù)數(shù)乘法的運行頻率為25 M，那么我們可以只使用一個乘法器，使其運行在100 MHz 或更高的頻率上，用串行的方式依次計算出、、和的值，然后在利用加法器計算出和的值。但是，如果復(fù)數(shù)乘法器的運行時鐘頻率非常高，接近于FPGA 所能支持的最高速率，那我們就要采用其他方法來節(jié)省乘法器資源了。下面給出幾種復(fù)數(shù)乘法器的優(yōu)化實現(xiàn)方法。

圖1 復(fù)數(shù)乘法的直接實現(xiàn)Fig.1 Direct implementation of complex multiplication

2 使用3個乘法器的復(fù)數(shù)乘法優(yōu)化結(jié)構(gòu)

2.1 原理推導(dǎo)

使用3個乘法器的復(fù)數(shù)乘法，參考文獻[6]給出了一種方法，即對I=ac-bd 做如下分解：

進一步化簡得到：

由于式（2）中，計算I 的時候，已經(jīng)計算出了bc 和ad 的結(jié)果，因此，只需再用一個加法器，就可以得到Q 的計算結(jié)果。

雖然利用式（2）節(jié)省了一個乘法器，但是，其實現(xiàn)架構(gòu)卻不利于完全采用FPGA 中的乘法器IP 核來實現(xiàn)，還必須附加額外的邏輯資源，這樣不利用高速（400 M 以上）的復(fù)數(shù)乘法運算，因此還需對其進一步優(yōu)化。注意到，對于式（1）中的I 和Q，還可以作如下分解：

由式（3）和式（4）可以看出，I 和Q 經(jīng)過因式分解之后，雖然還是4個乘積項的形式，但是，其中有一項（a-b）d 是I 和Q 的運算中相同的，因此，可以減少一次乘法運算，只需要使用3個乘法器就可以完成復(fù)數(shù)乘法運算。其實現(xiàn)架構(gòu)如圖2所示。圖2 所示的復(fù)數(shù)乘法實現(xiàn)架構(gòu)可以完全采用FPGA 中的乘法器IP 核來實現(xiàn)，不需要額外的邏輯資源，可以運行在很高的速率上。

2.2 優(yōu)化算法應(yīng)用于復(fù)數(shù)FIR 濾波器

數(shù)字信號處理中，最常用的一類濾波器就是FIR 濾波器，其數(shù)學(xué)表達式為

如果h（k）和x（n）都為實數(shù)，以N=4為例畫出其基本的實現(xiàn)架構(gòu)如圖3 所示[5，7]。

在通信信號處理中，我們常會碰到h（k）和x（n）為復(fù)數(shù)的情況，令h（k）=a（k）+jb（k）以及x（n）=c（n）+jd（n），那么，式（4）可以變換為

圖2 使用3個乘法器的復(fù)數(shù)乘法實現(xiàn)Fig.2 Implementation of complex multiplication with 3 multipliers

圖3 FIR 濾波器的實現(xiàn)（N=4）Fig.3 Implementation of FIR filter（N=4）

進一步整理得到

常規(guī)的實現(xiàn)方案是根據(jù)式（6）利用4個圖3 所示的實現(xiàn)架構(gòu)，分別計算出式（6）中的4個乘積和項，再利用加法器最終求得y（n）的實部和虛部。

利用式（3）和式（4）的分解方法，可以將式（6）的實部和虛部分別分解為

求出yI1（n）、yI2（n）和yQ2（n）之后，就可以利用式（7）和式（8）計算出yI（n）和yQ（n）的值。可以看出，相比傳統(tǒng)的實現(xiàn)架構(gòu)，利用圖4 的優(yōu)化實現(xiàn)架構(gòu)可以節(jié)省N個乘法器，N為FIR濾波器的抽頭數(shù)，節(jié)省比例為25%。

2.3 優(yōu)化算法應(yīng)用于共軛復(fù)數(shù)乘法

數(shù)字信號處理中，常常還會遇到的一類復(fù)數(shù)乘法就是共軛復(fù)數(shù)乘法。假設(shè)有兩個復(fù)數(shù)x1=a+bj 和x2=c+dj，其共軛復(fù)乘的表達形式為

其中，con j（x2）表示x2的共軛。通常的計算方法是先對x2的虛部d 按照補碼的規(guī)則取反加1，然后再按照下面的表達式相乘。

圖4 復(fù)數(shù)FIR 濾波器的優(yōu)化實現(xiàn)Fig.4 Optimized implementation of complex FIR filter

為了省掉對x2的虛部d 取反加1 的步驟，我們可以做適當變通，先將x1的實部和虛部互換，即令

對比式（9）和式（10）可以看到，兩者的實部和虛部是互換的關(guān)系，因此，可以取式（10）的實部作為共軛復(fù)乘的虛部，取式（10）的虛部作為共軛復(fù)乘的實部，這樣就省去了對x2的虛部取反加1 的步驟。最后，再利用上述復(fù)數(shù)乘法器的優(yōu)化方法，得到z=x1×con j（x2）的實部zI和虛部zQ分別為

根據(jù)式（11）和式（12），利用3個乘法器即可實現(xiàn)共軛復(fù)乘。

3 使用2個乘法器的復(fù)數(shù)乘法優(yōu)化結(jié)構(gòu)

如果復(fù)數(shù)的位寬不大，但是，復(fù)數(shù)乘法要求的運算速率很高，那么，為了節(jié)省乘法器資源，我們可以僅使用兩個乘法器來實現(xiàn)復(fù)數(shù)乘法。依然采用復(fù)數(shù)x1=a+bj 和x2=c+dj 相乘來闡述其原理。

假設(shè)復(fù)數(shù)實部和虛部的位寬都小于或等于k 比特，乘法器IP 核可以實現(xiàn)的乘法運算的最大位寬為2k 比特，那么我們可以做如下變換。令

進一步，可以得到

式（13）和式（14）相減，得到

式（13）和式（14）相加，得到

利用式（15）可以得到復(fù)乘之后的虛部值

由式（16）可以得到

如果a、b、c 和d 的位寬都小于k 比特，那么ac 以及bd乘積的位寬都小于2k 比特，因此，從式（18）中，直接取低位的2k 比特（LSB），就是bd 的乘積，直接取高位的2k 比特就是的乘積，進而可以求得復(fù)乘之后的實部值I=ac-bd。上述討論是基于無符號數(shù)而言的，如果a、b、c 和d 都是有符號數(shù)，那么可以先將符號提取出來，根據(jù)其符號位計算出結(jié)果的符號位，具體乘法運算都按照無符號數(shù)來處理。具體其實現(xiàn)架構(gòu)如圖5 所示。

圖5 使用2個乘法器實現(xiàn)復(fù)數(shù)乘法實現(xiàn)Fig.5 Implementation of complex multiplication with 2 multipliers

4 結(jié)論

傳統(tǒng)的復(fù)數(shù)乘法需要占用4個乘法器，文中對此進行了改進，分別給出了使用3個乘法器和2個乘法器的優(yōu)化實現(xiàn)方法，并針對基于FPGA 的實現(xiàn)，給出了數(shù)字信號處理中常用的復(fù)數(shù)FIR 濾波器和共軛復(fù)乘的優(yōu)化實現(xiàn)方法，尤其針對復(fù)數(shù)FIR 濾波器的實現(xiàn)而言，能夠節(jié)省25%的乘法器資源，在濾波器的階數(shù)很高的時候，對于實際的工程設(shè)計具有很好的可借鑒性。

[1]Kong M Y，Langiois J M P，Al-Khalili D.Efficient FPGA implementation of complex multipliers using the logarithmic number system[C]//Circuits and Systems，2008.ISCAS 2008.IEEE International Symposium on.IEEE，2008：3154-3157.

[2]Satoh K，Tada J，Tamura Y，et al.Complex multiplier suited for FPGA structure[C]//Proc.ITC-CSCC，2008：341-344.

[3]Berkeman A，Owall V，Torkelson M.A low logic depth complex multiplier[C]//Solid-State Circuits Conference，1998.ESSCIRC'98.Proceedings of the 24th European.IEEE，1998：204-207.

[4]Berkeman A，Owall V，Torkelson M.A low logic depth complex multiplier using distributed arithmetic [J].Solid-State Circuits，IEEE Journal of，2000，35（4）：656-659.

[5]何賓.FPGA數(shù)字信號處理實現(xiàn)原理及方法[M].北京：清華大學(xué)出版社，2010.

[6]高亞軍.基于FPGA的數(shù)字信號處理[M].北京：電子工業(yè)出版社，2012.

[7]Xilinx，DSP：Designing for Optimal Results[M].Edition 1.0，March，2005.

[8]Xilinx，Virtex-5 FPGA Xtreme DSP Design Considerations[M].User Guide，UG193（v3.5）January 26，2012.

[9]Altera，Implementing Multipliers in FPGA Devices，Application Note 306[M].ver.3.0，2004.