用電路實(shí)現(xiàn)pascal三角形運(yùn)算
Pascal三角形，即(a-b)n展開項(xiàng)系數(shù)，是一個經(jīng)典的數(shù)學(xué)問題，然而它在通信、頻率補(bǔ)償、版圖布局布線優(yōu)化等很多方面都有廣泛的應(yīng)用。在一個小數(shù)分頻項(xiàng)目中，需要構(gòu)建一個四級的pascal三角形來進(jìn)行相位補(bǔ)償，如圖1所示，第二個累加器的溢出必須通過第一個微分控制分頻比，第三個累加器的溢出必須通過第二個微分控制分頻比，依此類推。第二個累加器使分頻比變?yōu)镹+1、N-1，第三個累加器將分頻比變?yōu)镹+1、N-2、N+1，第四個累加器的分頻比序列為N+1、N-3、N+3、N-1，正如圖2所示該序列構(gòu)成一個pascal三角形，每行的總和為零。依照這個規(guī)律可以設(shè)計實(shí)現(xiàn)pascal 三角形運(yùn)算的通用電路。
Pascal三角形的數(shù)學(xué)描述
pascal三角形通常用三角形的方式來表示，如圖2所示，也可以用一個二維的下三角矩陣來描述，如圖3所示。
矩陣a[n，n]可以用下面的公式來描述。
a[i, j]=a[i, j-1]+(-1)a[i+1, j] (式1)
(a[n, 1]=0，a[n, 2]=a[n, 3]=...=a[n, n]=1)
i≥1，j≥2。
矩陣中第一列的0是為了方便電路實(shí)現(xiàn)而人為加上去的。將此二維矩陣表達(dá)式(即式1)變成含有時間的一維方程。
a[i]j=a[i]j-1+(-1)a[i+1]j (式2)
i，j均大于1，a[n]2 =a[n]3=...a[n]n=1。下標(biāo)表示時間，a[n，1]=0表示剛開始整個電路的清零信號，其余第一列的0表示對應(yīng)pascal三角形的和為0，最后一行的1表示pascal三角形每一行對應(yīng)的輸入端有輸入值1時，產(chǎn)生的立即數(shù)為1。
此外，式2具有疊加性，可以把pascal三角形中的一行加上其余任意一行或者幾行，實(shí)現(xiàn)任意時鐘周期的延時。
Pascal三角形的基本電路
根據(jù)上面一維含時公式，先要構(gòu)建補(bǔ)碼電路，然后是一個加法電路，最后是一個延時電路。
假設(shè)一個數(shù)組a[n:0]表示數(shù)的各位，a[0]為最低位，對各位取反，然后最低位加1，得到一個新的數(shù)組b[n:0]，這個數(shù)組最低位為b[0]，對應(yīng)的邏輯關(guān)系是：
其余位按照這個規(guī)律依此類推,邏輯圖如圖4所示。
采用通用的全加器，邏輯表達(dá)式為：
示意圖參見圖5。其中CI為上一級的進(jìn)位，A、B為本級輸入信號，S為全加和，CO是本級進(jìn)位。
延時器采用帶清零的D觸發(fā)器來實(shí)現(xiàn)，見圖6。CLOCK為時鐘信號，CLEAR為清零信號，D是數(shù)據(jù)輸入信號，Q是原量輸出
。
[!--empirenews.page--]
電路設(shè)計
首先構(gòu)建一個4級pascal三角形電路，其中CLOCK是時鐘信號，IN1、IN2、IN3、IN4分別對應(yīng)于pascal三角形的前4行，CLEAR是清零信號。IN1、IN2、IN3、IN4輸入之前將觸發(fā)器清零，防止輸出不定態(tài)。D0、D1、D2、D3是從低到高的四位輸出，SIGN是符號位，這五位構(gòu)成輸出。值得注意的是，IN4經(jīng)過與自己直接相連的D觸發(fā)器產(chǎn)生的數(shù)只有一位，然而它的補(bǔ)碼需要4位，只好在高位加零，這樣補(bǔ)碼電路就可以簡化，圖7就是經(jīng)過簡化的電路圖。為了增加電路的直觀性，這里省略了電路中所有D觸發(fā)器的時鐘信號和清零信號，所有D觸發(fā)器的清零信號和時鐘信號分別連在一起。
圖7 pascal三角形實(shí)現(xiàn)電路
真值表
|
IN4
|
IN3
|
IN2
|
IN1
|
CP1
|
CP2
|
CP3
|
CP4
|
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
|
0
|
0
|
1
|
0
|
1
|
-1
|
0
|
0
|
|
0
|
0
|
1
|
1
|
2
|
-1
|
0
|
0
|
|
0
|
1
|
0
|
0
|
1
|
-2
|
1
|
0
|
|
0
|
1
|
0
|
1
|
2
|
-2
|
1
|
0
|
|
0
|
1
|
1
|
0
|
2
|
-3
|
1
|
0
|
|
1
|
0
|
0
|
0
|
1
|
-3
|
3
|
-1
|
|
1
|
0
|
0
|
1
|
2
|
-3
|
3
|
-1
|
|
1
|
0
|
1
|
0
|
2
|
-4
|
3
|
-1
|
|
1
|
0
|
1
|
1
|
3
|
-4
|
3
|
-1
|
|
1
|
1
|
0
|
0
|
2
|
-5
|
4
|
-1
|
|
1
|
1
|
0
|
1
|
3
|
-5
|
4
|
-1
|
|
1
|
1
|
1
|
0
|
3
|
-6
|
4
|
-1
|
|
1
|
1
|
1
|
1
|
4
|
-6
|
4
|
-1
|
電路的驗(yàn)證與擴(kuò)展
取IN1、IN2、IN3、IN4從0001到1111，并且給每組值以足夠的變化周期，可以得到下面的真值表。在viewlogic用XILINX公司的XC4000庫進(jìn)行模擬，除了可以忽略的毛刺和初始時無關(guān)緊要的不定態(tài)之外，得到的波形圖與真值表完全一致，其中CP1、CP2、CP3、CP4分別對應(yīng)于第1、2、3、4時鐘，周期波形圖如圖8所示。
圖8 波形圖
三級的電路得到驗(yàn)證之后，根據(jù)同樣的原理，可以在四級的基礎(chǔ)上進(jìn)行任意級的構(gòu)建。
小結(jié)
本文給出了pascal三角形運(yùn)算電路的設(shè)計思想與實(shí)現(xiàn)方法，以及在viewlogic下的驗(yàn)證，并且還可以根據(jù)需要進(jìn)行任意級的擴(kuò)展。Pascal三角形在版圖布局布線優(yōu)化等方面的具體應(yīng)用可以參考有關(guān)文獻(xiàn)，在此不再贅述。
下載文檔
