【正文】 監(jiān)視線，當系統(tǒng)正常運行，應在規(guī)定的時間內給監(jiān)視線提供一個高低電平發(fā)生變化的信號，如果在規(guī)定的時間內不發(fā)生變化，自動復位電路認為系統(tǒng)運行不正常并重新進行復位。 圖8 ADM708結構框圖AMD708SAR用于自動復位電路，由其結構框圖可知。表1 ADM708部分引腳功能引腳名稱功能說明手動復位輸入，能被TTL，CMOS邏輯電平或手動復位按鈕驅動。不確定時內部70上拉電流保持輸入為高。PFI電源故障輸入為電源故障比較器的放大輸入，為低。電源故障輸出。邏輯輸出，被觸發(fā)時為低200ms?？杀坏碗娖交蚴謩訌臀惠斎氲牡碗娖接|發(fā)，當WDO與MR相連時看門狗時鐘可被RESET觸發(fā)。引腳6為系統(tǒng)提供了監(jiān)視信號，引腳7為低電平復位輸出。SW5用于硬件復位，這里連接信號到BF53FLASH的引腳，其功能是在程序跑飛、出現(xiàn)死鎖時按下按鈕復位。具體RESET模塊連接方式見下圖：圖9 復位電路連接方式DSP使用的電源是數(shù)字電源，必須滿足一定要求，紋波不超過10%。Blackfin的動態(tài)電源管理控制器（DPMC）與PLL結合，使用戶能夠動態(tài)地控制處理器的性能和功耗。BF533提供5種運行模式，每種模式有不同的性能/功耗特性，支持3種不同的電源范圍。通過將處理器內部邏輯隔離為獨立的電源，同RTC和其他I/O分離，處理器能使用動態(tài)功率管理，而不影響RTC或其他I/O設備。各電壓域沒有時序的要求。表2 Blackfin電源范圍電源范圍VDD范圍最小值標稱值最大值除RTC所有內部邏輯VDDINTRTC內部邏輯和晶體I/OVDDRTC所有其它I/OVDDEXT321圖10 DSP電源連接方式上圖為DSP電源單元，這里的R21～R24都先設為0歐電阻是為了方便以后加電阻調壓方便。NDS8434A為P通道增強型場效應管，F(xiàn)airchild公司采用了高集成度的DMOS技術，有良好的整流效果，在元件上已經(jīng)畫出了其內部結構示意。P 溝道MOSFET 工作在線性區(qū)，對供電電流和電壓進行調節(jié)。當“2”輸入電壓下降至 “1”檢測電壓以下時，柵極驅動輸出將自動關閉。在DSP_VDD_INT與DSP_VDD_EXT之間加二極管保證了DSP_VDD_EXT≥DSP_VDD_INT。 DSP的仿真接口20世紀80年代，聯(lián)合測試行動組（JTAG），該規(guī)范提供了有效地測試引線間隔致密的電路板上零件的能力。利用JTAG接口，可以把DSP和計算機聯(lián)系起來，通過仿真器對DSP進行調試，包括程序的下載、調試及存儲器監(jiān)視等功能，在仿真時監(jiān)視和控制目標板上的處理器。仿真器提供全速仿真，允許查看和修改存儲器、寄存器和處理器堆棧。使用處理器JTAG接口可確保進行不干擾處理器運行的在線仿真——仿真器不會影響目標系統(tǒng)的裝載和定時。設計過程參考了模擬設備JTAG仿真技術參數(shù)EE68：ADI公司網(wǎng)站（）。圖11 JTAG接口連接方式 圖12 軟件引導方式在實時工作中，系統(tǒng)必須與PC機相脫離，無法依靠仿真器，因此需要將程序固化在系統(tǒng)中的永久性存儲設備上。引導裝載程序在系統(tǒng)上電或復位時，將程序從外部存儲源搬移到內部或外部的程序空間，然后運行程序，這個過程稱為BOOTLOADER。這為系統(tǒng)的設計提供了很大的便利條件，設計者只需根據(jù)要求建立引導表，而不需要考慮如何實現(xiàn)代碼搬移。Blackfin復位后，ADSPBF531/2/3處理器有兩種機制自動載入內部L1指令存儲器的程序。表3 引導模式BMODE20說明00從外部16位存儲器執(zhí)行（旁路引導ROM）01有8位或16位Flash引導10保留（從外部存儲器執(zhí)行，繞過引導程序）11由SPI串行EEPROM引導（8位，16位或24位地址范圍）上電復位或軟件初始化復位后，處理器采樣復位配置寄存器的BMODE腳，執(zhí)行以下引導模式：1. 從外部16位存儲器執(zhí)行—從地址0x2000000開始執(zhí)行，數(shù)據(jù)16位壓縮，此模式跳過引導ROM。所有的配置參數(shù)都設置為適合最慢的設備（3個周期的保持時間，15周期的R/W訪問時間，4個周期的建立時間）2. 從外部8位或16位外部Flash存儲器引導——位于引導ROM存儲空間的Flash引導程序通過異步存儲器Bank0設置。所有的設置參數(shù)都適合最慢的設備。（3個周期的保持時間；15個周期的R/W訪問時間；4個周期的建立時間。）3. 從SPI串行EEPROM引導（8位，16位或24位尋址）—SPI用PF2輸出引腳選擇一個SPI EEPROM設備，在地址0x00，0x0000或0x000000開始發(fā)出連續(xù)讀數(shù)據(jù)命令，直到檢測到確定的8位，16位或24位地址的EEPROM，然后將之存入L1指令存儲器的起始部分。無論上述何種引導模式，從外部存儲器設備首先要讀入一個10 個字節(jié)的頭。這個頭指定將被傳輸?shù)淖止?jié)數(shù)量和存儲器的目的地址。多存儲器模塊可被任何引導順序裝載，一旦所有模塊被裝載，程序從L1 指令SRAM 的起始部分開始執(zhí)行命令。此外，通過設置復位配置寄存器第4 位，應用程序可以使軟件復位跳過正常的引導順序。這樣，處理器直接跳到L1 指令存儲空間的起始部分開始執(zhí)行。為了方便調試，在電路板上考慮了這四種引導方式，通過JP3，JP4接插件上的短路塊可以控制電平的高低。 DSP與存儲器接口電路按照馮諾依曼的存儲程序的概念，任何指令和數(shù)據(jù)都是存放在存儲器中的，存儲器的性能是直接影響整個計算機系統(tǒng)性能的關鍵因素。L1存儲器是Blackfin 處理器內核中性能最高的最重要的存儲器。通過外部總線接口單元(EBIU)，片外存儲器可以由SDRAM、FLASH 和SRAM 進行擴展，可以訪問多達132MBytes 的物理存儲器。本裝置從CCD傳送過來的是電視信號，選用AD公司的10bit ADV7180作為視頻輸入接口。其主要特點如下：l 支持NTSC/PAL/SECAM彩色解調l 一個10bit模數(shù)轉換器，內部通道可配置為4CVBS，2Y/C，2YPrPbl 3個視頻帶有片上抗混疊濾波器輸入通道l 5階線形梳狀濾波器及CTI/DNR視頻增益l 自適應線形線形長度跟蹤（ADLLT）l NTSC/PAL/SECAM自動監(jiān)視l 8bit ITUR YCrCb 4:2:2 輸出l 4 通用輸出口l MPU接口l 圖13 ADV7180結構框圖圖14 a ADV7180連接方式圖14 b ADV7180連接方式3 軟件流程（1）采集圖象，編碼（2）中值濾波（3）改進濾波（4）灰度判別，將大于200的灰度置零（5）基于瞳孔閾值分離跟蹤定位算法（6）去除正上方90度的圖象，即45度到135度的范圍（7）紋理特征提取。先歸一化，要進行灰度插值運算。均衡化。（8）通過二維Gabor濾波器進行條形碼編碼（9）計算兩個編碼的hamming距離，設定閾值，判斷是否為同一條形碼 條形碼識別系統(tǒng)的算法分為條形碼定位，條形碼編碼和特征匹配三大部分，各部分又有各自的方法實現(xiàn)濾波，去噪，編碼，匹配等功能。4 與現(xiàn)有系統(tǒng)比較該系統(tǒng)比現(xiàn)有的條形碼識別系統(tǒng)復雜，技術上具有可行性，在實用性上和價格方面都比不上現(xiàn)有的條形碼識別系統(tǒng)。但通過DSP可以將條形碼識別系統(tǒng)做到很小，且在單獨使用時不需要電腦支持，且該系統(tǒng)可以在直流24V環(huán)境下工作，可用于某些特殊情況或緊急情況下。參 考 文 獻[1] ：電子工業(yè)出版社，2004年[2] 彭啟琮，李玉柏，：高等教育出版社，2002年[3] 朱銘倍，趙勇，：電子工業(yè)出版社，2002年[4] 蘇濤，蔡建隆，：西安電子科技大學，2003年【作者簡介】龍非池(1987 ) 男，通信與信息工程學院通信工程專業(yè)2005級本科生，曾獲2006電子科技大學高等數(shù)學競賽特等獎。圖節(jié)點著色問題中的禁忌搜索算法龍非池(電子科技大學通信與信息工程學院 成都 610054)【摘要】 本文針對圖節(jié)點著色問題，提出了基于禁忌搜索的優(yōu)化算法設計方案，能夠跳出局部極小點，實現(xiàn)全局最優(yōu)化。并提出禁忌搜索算法能較好的用于一般算法較難實現(xiàn)的著色問題的推廣問題List著色。通過實驗仿真，驗證了算法的高效性和可靠性?！娟P鍵詞】 節(jié)點著色 List著色 禁忌搜索算法 全局優(yōu)化Algorithm of Graph Coloring Based on Tabu SearchLONG Feichi (College of Communication and Information Engineering of UESTC Chengdu 610054)Abstract This paper brings forward an algorithm based on taboo search to meet graph coloring problem, which can enlarge the search space and implement the global optimization, and it proves that the algorithm of taboo search can be effectively implemented in the problem of list coloring. The results of simulation prove that the algorithm has high efficiency and reliability. Key words graph coloring list coloring the algorithm of tabu search overall optim ization圖節(jié)點著色問題是組合最優(yōu)化中典型的非確定多項式(NP)完全問題，也是圖論中研究得最久的一類問題。目前解決該問題的算法很多，如回溯算法、分支界定法、WelshPowell算法、神經(jīng)網(wǎng)絡、遺傳算法以及模擬退火算法等。綜合比較各種算法，前兩種算法是精確算法，但時間復雜性太大；后三種屬于近似算法，雖然時間復雜性可接受，能夠得到較好的近似解，但算法本身過于復雜，算法效率難以保證。本文采用禁忌搜索算法，它同時擁有高效性和魯棒性。禁忌搜索是一種全局逐步尋優(yōu)的人工智能算法，它常能有效的應用于一些典型NP問題，如TSP。但禁忌搜索存在一些參數(shù)較難設置，這也是應用于通信系統(tǒng)時研究的熱點。本文提出針對著色問題的禁忌搜索的具體設計方案，較好的設置了參數(shù)，并優(yōu)化了數(shù)據(jù)結構，通過實驗比較得到了較好的效果。最后提出通過領域簡單的變化，禁忌搜索能較好的用于一般算法難以實現(xiàn)的List著色問題。1圖節(jié)點著色問題圖的著色問題可分為邊著色、頂點著色、List著色和全著色，其中最主要的一種是節(jié)點著色。節(jié)點著色問題可描述如下：給定一個無向圖G=(V,E)，其中V是節(jié)點集V={1,2,…n}，E是邊集，其中(i,j)表示有連接(i,j)的一條邊。若，且Vi內部的任何兩個節(jié)點沒有E中的邊直接相連，則稱(V1,V2,…,Vn)為V的一個劃分。圖的節(jié)點著色問題可以描述為：求一個最小的k，使得(V1,V2,…,Vn)為V的一個劃分。：，6節(jié)點的無向圖G=(V,E)，其中一種著色方案：V1={C,E,F},V2={A},V3={B,D}通常的解決著色問題的算法采用蠻力法、貪婪法、深度優(yōu)先或廣度優(yōu)先等思想可以得到最優(yōu)解，但時間復雜性太大，如回溯法，其計算時間復雜性為指數(shù)階的；有的在多項式時間內能得到可行解，但不是最優(yōu)解，如WelshPowell算法和貪婪算法。WelshPowell算法只能保證最多使用(為圖中頂點的最大度)種顏色給一個圖正常著色，而由Brooks定理，對于既不是完全圖又不是奇圈的簡單連通圖，所需的顏色數(shù)。故通常的算法在解決圖節(jié)點著色問題這樣的NP完全問題時，存在很大的瓶頸，難以得到滿意的結果。而對于像遺傳算法和神經(jīng)網(wǎng)絡這樣復雜的啟發(fā)式算法，通常算法本身復雜性較大，并且算法效率難以分析，最終得到的是近似解，其是否最優(yōu)解也不能保證。2 禁忌搜索算法的設計禁忌搜索是對局部領域搜索的擴展。傳統(tǒng)局部鄰域搜索是基于貪婪思想在當前解的鄰域中進行搜索，搜索性能完全依賴于鄰域結構和初始解的選取，搜索結果容易陷入局部極小而無法保證全局最優(yōu)。而禁忌搜索從一個初始可行解s開始，通過變換得解的鄰域函數(shù)V(s)，按照某種選擇策略從中選取一個解s*，從s移動到s*，把s*作為一個新解，重新疊代搜索，直到滿足退出機制。為避免循環(huán)和陷入局部最優(yōu)，禁忌搜索使用禁忌表記錄已經(jīng)到達的局部最優(yōu)點，也即最近進行的移動狀態(tài)。在下一步的搜索中利用規(guī)定的禁忌規(guī)則，在一定搜索次數(shù)內不允許選擇這些已被禁的搜索點，從而可以跳出局部最優(yōu)的限制。為了數(shù)據(jù)結構的簡化，我們設頂點集合為有序，1,2,…n各代表一個頂點，如例子中的頂點ABCDEF分別編號為1,2,…n。對于顏色集C，用C={1,2,…m}來表示。這樣便可用一個行向量來作為解的數(shù)據(jù)結構，其中下標1,2,…n依次代表各個頂點，向量中下標對應的分量對應所著色，著色相同的即在同一劃分集Vi。如例子的解可表示為：s=[2 3 1 3 1 1]，共3種顏色。首先確定解的變化形式。一般而言，變化形式分為解的簡單變化、向量分量的變化和目標值的變化[3]。鑒于解的數(shù)據(jù)結構，采用分量變化形式，即對于頂點i，其顏色值從s[i]變?yōu)閖，其中j屬于顏色集C。對于領域，每一個解s的領居由那些滿足上面的變化且只有一個分量變化的解組成，每一個分量可以選擇m個顏色中的一個，那么對每一個解，共有n*(m1)個鄰居。例如，對于例子中的解s=[2 3 1 3 1 1]，它的一些領居為s1=[1 3 1 3 1 1],s2=[3 3 1 3 1 1],s3=[2 1 1 3 1 1],s4=[2 2 1 3 1 1]等。