以NIOSⅡ處理器為基礎的音樂檢索FPGA硬體電路之實現

Abstract

隨著數位內容數量的大幅成長，包含聲音、音樂、影像、視訊等多媒體資料，對於數位內容的檢索也變成一個很重要的課題。音樂檢索則是針對音樂部份，使用者透過啍唱、語音與敲擊等不同的方式來選取網路上或資料庫中的歌曲。在目前多媒體數位內容日趨成熟，人們對於資訊需求不再侷限於文字上而已，愈來愈多的圖片、聲音、影像等多媒體將會成為搜尋對象。 目前的音樂檢索均以字串比對為核心，不單單只有精確比對也要允許錯誤比對(近似比對)。但若在資料量大時作比對，會需要大量的計算時間。以精確比對為例子，m為搜尋音符的個數，n為歌曲的音符個數，精確比對的時間複雜度為O(m × n)。 String Matching是很普遍且重要的問題，要在T=t1t2...tn中搜尋字串P=p1p2...pm，P及T有可能是一個檔案中的字元、DNA鹼基對(DNA base pairs)、程式中的一段程式碼、一多邊形的角或是樂譜中的音符及拍子等等。要在T中找尋有符合P字串的位置，也就是F = {i | 1≦i≦n-m+1 , titi+1...ti+m-1 = P}，這類問題最有名的就是Boyer-Moore[13]和Knuth Morris Pratt[14]演算法。 本篇論文採用Fast Text Searching Allowing Errors[6]理論基礎實現硬體的音樂檢索。對於只有Shift、AND、OR的演算法非常適合應用在硬體上面，且對時間複雜度更有大大的改善。當搜尋音符個數為m，歌曲音符個數為n時，時間複雜度為O(n)，和允許錯誤個數d無關；相較於應用在軟體上面時間複雜度是O (d× n)。將整個電路放置在Altera公司的Stratix開發板上，搭配使用者端利用Borland C++ Builder程式開發使用者介面，透過網路便可組成一個完整快速又兼具FPGA特性的音樂檢索系統。With a great deal growth of digital contents such as media data of voices、musics、images and videos,it becomes an important topic for digital contents retrieval.The music retrieval focuses on the part of musics,and users retrieve songs from internet or database by humming、voicing and keying.In this day,people are no longer restricted to get resources in words with the maturation of media techniques. Accordingly,more and more pictures、voices and images would be objects to be searched. Music retrieval is based on the core of string matching presently.There are not only exact matching but approximate matching(allowing errors).However,it’s would take large number of time when it proceeds with huge datas.Take exact matching,m denotes the number of querying notes and n denotes the number of music notes,and the time complexity is O(m × n). String matching is a normal and significant problem. We are searching for the set of starting positions F = {i | 1≦i≦n-m+1 ,titi+1...ti+m-1 = P} for a string P=p1p2...pm inside a large text file T=t1t2...tn.The characters may be English characters in a text file, DNA base pairs, lines of source code, angles between edges in polygons, music notes and tempo in a musical score, and so forth. The two most famous algorithms for this problem are the Boyer-Moore algorithm [13] and the Knuth Morris Pratt algorithm [14]. This thesis adopts Fast Text Searching Allowing Errors[6] as theorem to achieve music retrieval.It’s very suitable to apply on hardware with Shift、AND、OR algorithm only,and improves time cost significantly.m denotes the number of querying notes and n denotes the number of music notes.The hardware time complexity of the algorithm is O(n) irrelevant to the number of allowing errors(d) while O (d × n) for software.We append our circuits on Stratix development board by Altera corp. accompany with user querying UI(user interface) coded by Borland C++ 6.0 composed with network forms a high-speed FPGA music retrieval system.