一種數據分組快速查找定位法的製作方法
2023-06-05 15:33:51
專利名稱：一種數據分組快速查找定位法的製作方法
技術領域：
本發明涉及數據分組的快速查找定位方法，尤其涉及運用硬體電路實現的數據分組快速查找定位方法。
背景技術：
目前，隨著高速信號處理技術應用的日益廣泛，對於數據分組查找定位的速度要求日益提高；普通的逐次比較數據分組查找定位法比較次數多、查找速度慢，尤其當數據的分組組數很大時，普通的逐次比較數據分組查找定位法所耗費的時間將成為限制高速信號處理的主要因素，不利於高速信號處理、分析功能的實現。為解決上述問題，本發明提出一種基於硬體電路的數據分組快速查找定位方法， 可以用最少的比較次數快速確定外部輸入數據在整個數據範圍內屬於哪一個分組，並將其所在的分組編號輸出。與普通的逐次比較數據分組查找定位法相比，本發明可大大減少查找比較次數，提高數據分組查找定位的速度，有利於高速信號處理、分析功能的實現。
發明內容
技術問題本發明要解決的技術問題是提供一種基於硬體電路的數據分組快速查找定位方法，該方法可以根據用戶設定的數據範圍和分組組數，用最少的比較次數快速確定外部輸入數據在整個數據範圍內屬於哪一個分組，並將其所在的分組編號輸出，大大提高數據分組查找定位的速度。技術方案為解決上述技術問題，本發明採用的技術方案是—種數據分組快速查找定位方法，包括以下步驟a)根據外部輸入數據是無符號數還是有符號數，轉換得到查找使用的輸入數據；b)判別用戶設定的數據範圍與數據分組的組數，並根據外部輸入數據是無符號數還是有符號數，轉換得到查找使用的數據範圍與數據分組的組數；c)由轉換得到的查找使用的數據範圍與數據分組的組數，計算查找使用的各數據分組之間的分組邊界值；d)分組邊界值存儲到存儲器中；e)分組查找定位過程由狀態機控制，將查找使用的輸入數據與存儲器中的分組邊界值進行比較，並根據本次比較的結果選擇下一次比較時所要使用的分組邊界值；f)當完成了分組查找定位過程所需的比較次數後，分組查找定位過程結束，最終輸出外部輸入數據所屬的分組編號；所述步驟a)中，外部輸入數據的無符號數和有符號數分別為固定長度無符號二進位數，和固定長度有符號二進位數；它們的長度為L比特，L為任意自然數。所述步驟a)中，查找使用的輸入數據轉換的方法為如果外部輸入數據是無符號數，則所述查找使用的輸入數據等於外部輸入數據；
如果外部輸入數據是有符號數，則所述查找使用的輸入數據為將外部輸入數據的最高位取反，其餘位保持不變，並將其視為無符號數； 綜上，查找使用的輸入數據始終為無符號數。所述步驟b)中，用戶設定的數據範圍是指，進行數據分組查找時，由用戶設定外部輸入數據可能出現的最小值b至最大值a ；數據分組是指，用戶根據需要，將由用戶設定的數據範圍均勻劃分為K個分組，K 為任意自然數；用戶設定的數據分組的組數即為K ；所述步驟b)中，查找使用的數據分組的組數的轉換方法為如果用戶設定的數據分組的組數K = 2N，則查找使用的數據分組的組數M = K ；如果用戶設定的數據分組的組數K興2n，且< K < 2N，則查找使用的數據分組的組數M = 2n;所述N為任意自然數。所述步驟b)中，查找使用的數據範圍分為下列4種情況1)如果用戶設定的數據分組的組數K = 2N，其中N為任意自然數，同時外部輸入數據為無符號數，則查找使用的數據範圍等於用戶設定的數據範圍，即查找使用的數據範圍的最小值Min = b，最大值Max = a ；2)如果用戶設定的數據分組的組數K興2n，且< K < 2ν，同時外部輸入數據為無符號數，則查找使用的數據範圍的計算方法為數據範圍的最小值Min = b，最大值Max =b+(a_b)*2N/K ；3)如果用戶設定的數據分組的組數K = 2n，同時外部輸入數據為有符號數，則查找使用的數據範圍計算方法為數據範圍的最小值Min = d，d為將b的最高位取反，其餘位保持不變；數據範圍的最大值Max = c, c為將a的最高位取反，其餘位保持不變；4)如果用戶設定的數據分組的組數K興2N，且< K < 2n，同時外部輸入數據為有符號數，則查找使用的數據範圍的計算方法為數據範圍的最小值Min = d，最大值Max =d+(c-d)*2N/K。所述步驟C)中，分組邊界值的求解方法為按照查找使用的數據分組的組數，將查找使用的數據範圍均勻劃分，得到各個數據分組；各數據分組中最小數據的值就是該數據分組的分組邊界值；分組邊界值的計算方法為V(i) = Min+(Max-Min)*i/M ；其中V(i)為第i個數據分組的分組邊界值，即第i個數據分組中最小數據的值，i為整數，0彡i ( M-I，M為查找使用的數據分組的組數。所述步驟d)中，使用存儲器按照順序存儲計算好的分組邊界值，存儲順序為第一個單元空閒；第二個單元存放第(M/2)組的分組邊界值；第三個和第四個單元分別存放第(M/4)組和第(3M/4)組的分組邊界值；第五個至第八個單元分別存放第(M/8)組、第 (3M/8)組、第(5M/8)組和第(7M/8)組的分組邊界值；並以此類推；分組邊界值的個數等於查找使用的數據分組的組數M減1，即2N_1，N為任意自然數，分組邊界值需要的存儲器的容量為單元，與查找使用的分組組數相等；所述單元是指存儲單元。所述步驟e)中，狀態機的控制步驟包括
1)狀態機首先初始化地址生成器的輸出地址為1，即存儲器的第二個單元；2)狀態機按地址生成器的輸出地址從分組邊界值存儲器中讀取分組邊界值，並將其與查找使用的輸入數據進行比較，比較的結果為1比特，若查找使用的輸入數據大於分組邊界值，則比較結果為1 ；反之則比較結果為0 ；3)狀態機根據本次讀取分組邊界值的存儲單元地址和本次比較的結果，控制地址生成器生成下一次讀取分組邊界值的存儲單元地址；將本次比較使用的分組邊界值的存儲單元地址左移1位，加上本次比較的結果，即可形成下一次比較使用的分組邊界值的存儲單元地址；4)判斷比較次數是否達到查找定位過程所需的比較次數N，如果未達到，則跳轉到步驟2)，如果已達到，則分組查找定位過程結束，將最後一次讀取分組邊界值所使用的存儲單元地址左移1位，加上最後一次比較的結果，就是查找使用的輸入數據所屬的分組編號，同時也是外部輸入數據所屬的分組編號，將此分組編號輸出。所述步驟f)中，分組查找定位過程所需的比較次數N = t = Iog2 (M) = Iog2 (2n)， 其中t為分組查找定位過程所需的比較次數，t與外部輸入數據的大小無關，僅由查找使用的數據分組的組數M決定。存儲器中的分組邊界值在用戶改變設定的數據範圍時重新計算並更新。有益效果通過本發明提供的一種基於硬體電路的數據分組快速查找定位方法， 可以大大減少分組查找定位過程中的數據比較次數，提高數據分組查找定位的速度。普通的逐次比較數據分組查找定位法在分組組數為K的情況下，其中< K彡2N，平均需要進行K/2次比較才能確定外部輸入數據的分組編號；利用本方法，可以將確定分組的比較次數減小到Iog2M次，其中M = 2n。本方法可以由現場可編程門陣列(FPGA)等電路形式實現， 為高速信號處理或分析算法提供數據分組快速查找定位功能。
圖1、本發明的模塊框圖，圖2、控制狀態機的狀態轉換圖，圖3、分組邊界值存儲器數據分布圖。
具體實施例方式下面結合
本發明的具體實施方式
。圖1為本發明實施例所基於的硬體電路的模塊框圖。在查找定位過程開始之前，首先根據外部輸入數據是無符號數還是有符號數，轉換得到查找使用的輸入數據；判別用戶設定的數據範圍與分組組數的情況並根據外部輸入數據是無符號數還是有符號數，轉換得到查找使用的數據範圍與分組組數；由轉換得到的查找使用的數據範圍與分組組數，計算查找使用的各數據分組之間的分組邊界值；分組邊界值按照特定的順序存儲到存儲器中，存儲順序如下(如圖2所示)第一個單元空閒； 第二個單元存放第(M/2)組的分組邊界值；第三個和第四個單元分別存放第(M/4)組和第(3M/4)組的分組邊界值；第五個至第八個單元分別存放第(M/8)組、第(3M/8)組、第 (5M/8)組和第(7M/8)組的分組邊界值；並以此類推。分組邊界值的個數等於查找使用的分組組數M減1，即2n-1，N為任意自然數，其需要的存儲器的容量為2N個單元，與查找使用的分組組數相等。完成分組邊界值計算存儲過程後，可以開始查找定位過程，具體過程如下首先將分組邊界值存儲器的地址初始化為1 ；根據外部輸入數據是二進位無符號數還是有符號數，轉換得到查找使用的輸入數據並輸入數據比較器，與從存儲器讀出的分組邊界值進行比較；比較的結果送入地址生成模塊用於產生下一次讀取分組邊界值時的存儲器地址，即將本次讀取的分組邊界值的地址左移1位，並加上本次數據比較的結果，形成下一次的分組邊界值讀取地址。整個查找定位過程需要多次重複進行數據比較，當比較次數達到查找定位過程所需的比較次數時，分組查找定位過程結束，查找比較的結果通過地址生成模塊輸出給後續模塊，為後續處理提供數據。整個查找定位過程由狀態機控制，其狀態轉換圖如圖3所示，具體過程如下電路上電後處於復位狀態，在此狀態，電路中各寄存器清零，此狀態下可以更改分組邊界值存儲器的內容；當復位信號結束後，電路將自動進入數據比較狀態，開始數據比較過程。在數據比較狀態，狀態機控制數據比較模塊讀取查找使用的輸入數據，並與從分組邊界值存儲器讀取的分組邊界值進行比較，比較的結果將被送入地址生成器，用於產生下一次的分組邊界值讀取地址或產生最終的比較結果；比較完成後，狀態機進入地址生成狀態。在地址生成狀態，狀態機將控制地址生成器，根據本次讀取分組邊界值的地址和本次數據比較的結果，生成下一次讀取分組邊界值的地址；當地址生成完成後，狀態機將判斷當前進行的數據比較次數是否達到了查找定位過程所需的比較次數N，如果沒有達到N， 則狀態機轉入數據比較狀態，繼續進行數據比較；若已達到N，則查找定位過程結束，進入完成狀態。在完成狀態，狀態機控制地址生成器輸出查找定位結果，即分組編號，並停留在此狀態，直到復位信號到來，重新回到復位狀態。實施例1現假設外部輸入數據為6位無符號數，用戶設定的數據範圍的最大值a為45，最小值b為5，用戶設定的分組組數K為8，各分組的數據範圍為第0組[5，10]、第1組[10， 15]、第 2 組[15，20]、第 3 組:[20，25]、第 4 組:[25，30]、第 5 組:[30，35]、第 6 組:[35， 40]、第7組[40，45]。假設此時外部輸入數據χ = 29，此數據應當屬於第4組[25，30]。由於用戶設定的分組組數8 = 23，且外部輸入數據為無符號數，按照分組邊界值的計算公式，各分組邊界值依次為5、10、15、20、25、30、35、40 ；按照分組邊界值的存儲方法， 分組邊界值存儲器中第0到第7個單元內容依次為空閒、25、15、35、10、20、30、40，分組邊界值存儲器的地址只需3位(二進位)；由於用戶設定的分組組數8 = 23，分組查找定位過程所需的比較次數t = Iog2S = 3。外部輸入數據為29，因為外部輸入數據是無符號數，所以查找使用的輸入數據也是29，整個分組查找定位過程如下初始化存儲器地址為1，查找使用的輸入數據29首先與1號地址的分組邊界值25比較，比較結果為大於(即1)，因此下一次比較的地址為本次地址1左移1位再加上比較結果1，得到3 ；查找使用的輸入數據29 再與3號地址的分組邊界值35進行比較，比較結果為小於(即0)，因此下一次比較的地址為本次地址3左移1位在加上比較結果0，得到6 ；查找使用的輸入數據29再次與6號地址的分組邊界值30進行比較，比較結果為小於(即0)，此時比較次數已達到8組數據查找定位時需要的3次，因此比較過程結束，輸出結果為本次地址6左移1位再加上比較結果0，取該結果的低3位得到4 (因為分組邊界值存儲器的地址只有3位)，即外部輸入數據29屬於分組編號為4的數據分組[25，30]，該結果與前面分析的情況一致。實施例2現假設外部輸入數據為7位有符號數，用戶設定的數據範圍的最大值a為35( 二進位補碼為0100011)，最小值b為-25 ( 二進位補碼為1100111)，用戶設定的分組組數K為 6，各分組的數據範圍為第0組[-25,-15]、第1組[-15,-5]、第2組[-5，5]、第3組[5， 15]、第4組[15，25]、第5組:[25，35]。假設此時外部輸入數據χ = _10，此數據應當屬於第 1 組[-15，-5]。由於用戶設定的分組組數22 < 6 < 23，所以查找使用的分組組數M = 23 = 8 ；因為外部輸入數據為有符號數，所以查找使用的數據範圍最小值Min = 39(把用戶設定的最小值b最高位取反，其餘位保持不變，轉換為二進位無符號數d = 0100111，其十進位為 39)，最大值Max = 119(把用戶設定的最大值a最高位取反，其餘位保持不變，轉換為二進位無符號數 c = 1100011，其十進位為 99 ；最大值 Max = d+(c-d)*2N/K = 39+(99-39) *8/6 =119)；按照分組邊界值的計算公式，各查找使用的分組邊界值依次為39、49、59、69、79、 89,99,109 ；按照分組邊界值的存儲方法，分組邊界值存儲器中第0到第7個單元內容依次為空閒、79、59、99、49、69、89、109，分組邊界值存儲器的地址只需3位(二進位)；由於用戶設定的分組組數22 < 6 < 23，分組查找定位過程所需的比較次數t = log223 = 3。外部輸入數據χ = -10，轉換為查找使用的輸入數據為54(-10的二進位補碼為1110110，最高位取反，其餘位保持不變，轉換為二進位無符號數為0110110，其十進位為54)，整個分組查找定位過程如下初始化存儲器地址為1，查找使用的輸入數據54首先與1號地址的分組邊界值79比較，比較結果為小於(即0)，因此下一次比較的地址為本次地址1左移1位再加上比較結果0，得到2 ；查找使用的輸入數據54再與2號地址的分組邊界值59進行比較，比較結果為小於(即0)，因此下一次比較的地址為本次地址2左移1位在加上比較結果0，得到4 ；查找使用的輸入數據54再次與4號地址的分組邊界值49進行比較，比較結果為大於 (即1)，此時比較次數達到8組數據查找定位時需要的3次，因此比較過程結束，輸出結果為本次地址4左移1位再加上比較結果1，取該結果的低3位得到1 (因為分組邊界值存儲器的地址只有3位)，即外部輸入數據-10屬於分組編號為1的數據分組[-15，-5]，該結果與前面分析的情況一致。該方法可以根據用戶設定的二進位數據範圍和分組組數快速查找並確定外部輸入的二進位數所在的分組編號，為高速信號處理或分析算法提供數據分組快速查找定位的功能。按照本發明提出的快速查找定位方法，可以用最少的比較次數快速確定外部輸入數據在用戶設定的數據範圍內屬於哪一個分組，並將其所在的分組編號輸出。與普通分組查找定位方法相比，本發明可大大減少查找比較次數，提高數據分組查找定位的速度。本發明可以由現場可編程門陣列(FPGA)等電路形式實現。以上具體實施方式
僅用於說明本發明，而非用於限定本發明。
權利要求
1.一種數據分組快速查找定位方法，其特徵在於包括以下步驟a)根據外部輸入數據是無符號數還是有符號數，轉換得到查找使用的輸入數據；b)判別用戶設定的數據範圍與數據分組的組數，並根據外部輸入數據是無符號數還是有符號數，轉換得到查找使用的數據範圍與數據分組的組數；c)由轉換得到的查找使用的數據範圍與數據分組的組數，計算查找使用的各數據分組之間的分組邊界值；d)分組邊界值存儲到存儲器中；e)分組查找定位過程由狀態機控制，將查找使用的輸入數據與存儲器中的分組邊界值進行比較，並根據本次比較的結果選擇下一次比較時所要使用的分組邊界值；f)當完成了分組查找定位過程所需的比較次數後，分組查找定位過程結束，最終輸出外部輸入數據所屬的分組編號；所述步驟a)中，外部輸入數據的無符號數和有符號數分別為固定長度無符號二進位數，和固定長度有符號二進位數；它們的長度為L比特，L為任意自然數。
2.如權利要求1所述的數據分組快速查找定位方法，其特徵在於所述步驟a)中，查找使用的輸入數據轉換的方法為如果外部輸入數據是無符號數，則所述查找使用的輸入數據等於外部輸入數據；如果外部輸入數據是有符號數，則所述查找使用的輸入數據為將外部輸入數據的最高位取反，其餘位保持不變，並將其視為無符號數；綜上，查找使用的輸入數據始終為無符號數。
3.如權利要求1所述的數據分組快速查找定位方法，其特徵在於所述步驟b)中，用戶設定的數據範圍是指，進行數據分組查找時，由用戶設定外部輸入數據可能出現的最小值b 至最大值a ；數據分組是指，用戶根據需要，將由用戶設定的數據範圍均勻劃分為K個分組，K為任意自然數；用戶設定的數據分組的組數即為K。
4.如權利要求3所述的數據分組快速查找定位方法，其特徵在於所述步驟b)中，查找使用的數據分組的組數的轉換方法為如果用戶設定的數據分組的組數K = 2N，則查找使用的數據分組的組數M = K ；如果用戶設定的數據分組的組數K興2n，且< K < 2N，則查找使用的數據分組的組數 M = 2N ；所述N為任意自然數。
5.如權利要求3所述的數據分組快速查找定位方法，其特徵在於所述步驟b)中，查找使用的數據範圍分為下列4種情況1)如果用戶設定的數據分組的組數K= 2N，其中N為任意自然數，同時外部輸入數據為無符號數，則查找使用的數據範圍等於用戶設定的數據範圍，即查找使用的數據範圍的最小值Min = b，最大值Max = a ；2)如果用戶設定的數據分組的組數K興2N，且2H< K < 2n，同時外部輸入數據為無符號數，則查找使用的數據範圍的計算方法為數據範圍的最小值Min = b，最大值Max = b+(a_b)*2N/K ；3)如果用戶設定的數據分組的組數K= 2n，同時外部輸入數據為有符號數，則查找使用的數據範圍計算方法為數據範圍的最小值Min = d，d為將b的最高位取反，其餘位保持不變；數據範圍的最大值Max = c, c為將a的最高位取反，其餘位保持不變；4)如果用戶設定的數據分組的組數K興2N，且< K < 2n，同時外部輸入數據為有符號數，則查找使用的數據範圍的計算方法為數據範圍的最小值Min = d，最大值Max = d+(c-d)*2N/K。
6.如權利要求1所述的數據分組快速查找定位方法，其特徵在於所述步驟c)中，分組邊界值的求解方法為按照查找使用的數據分組的組數，將查找使用的數據範圍均勻劃分，得到各個數據分組；各數據分組中最小數據的值就是該數據分組的分組邊界值；分組邊界值的計算方法為V(i) = Min+(Max-Min)*i/M ；其中V(i)為第i個數據分組的分組邊界值，即第i個數據分組中最小數據的值，i為整數，O彡i ( M-1，M為查找使用的數據分組的組數。
7.如權利要求1所述的數據分組快速查找定位方法，其特徵在於所述步驟d)中，使用存儲器按照順序存儲計算好的分組邊界值，存儲順序為第一個單元空閒；第二個單元存放第(M/2)組的分組邊界值；第三個和第四個單元分別存放第(M/4)組和第(3M/4)組的分組邊界值；第五個至第八個單元分別存放第(M/8)組、第(3M/8)組、第(5M/8)組和第 (7M/8)組的分組邊界值；並以此類推；分組邊界值的個數等於查找使用的數據分組的組數M減1，即2n-1，N為任意自然數，分組邊界值需要的存儲器的容量為單元，與查找使用的分組組數相等；所述單元是指存儲單元。
8.如權利要求7所述的數據分組快速查找定位方法，其特徵在於所述步驟e)中，狀態機的控制步驟包括1)狀態機首先初始化地址生成器的輸出地址為1，即存儲器的第二個單元；2)狀態機按地址生成器的輸出地址從分組邊界值存儲器中讀取分組邊界值，並將其與查找使用的輸入數據進行比較，比較的結果為1比特，若查找使用的輸入數據大於分組邊界值，則比較結果為1 ；反之則比較結果為O ；3)狀態機根據本次讀取分組邊界值的存儲單元地址和本次比較的結果，控制地址生成器生成下一次讀取分組邊界值的存儲單元地址；將本次比較使用的分組邊界值的存儲單元地址左移1位，加上本次比較的結果，即可形成下一次比較使用的分組邊界值的存儲單元地址；4)判斷比較次數是否達到查找定位過程所需的比較次數N，如果未達到，則跳轉到步驟2)，如果已達到，則分組查找定位過程結束，將最後一次讀取分組邊界值所使用的存儲單元地址左移1位，加上最後一次比較的結果，就是查找使用的輸入數據所屬的分組編號，同時也是外部輸入數據所屬的分組編號，將此分組編號輸出。
9.如權利要求1所述的數據分組快速查找定位方法，其特徵在於步驟f)中，分組查找定位過程所需的比較次數N = t = Iog2(M) = log2(2N)，其中t為分組查找定位過程所需的比較次數，t與外部輸入數據的大小無關，僅由查找使用的數據分組的組數M決定。
10.如權利要求1所述的數據分組快速查找定位方法，其特徵在於存儲器中的分組邊界值在用戶改變設定的數據範圍時重新計算並更新。
全文摘要
本發明公開了一種數據分組快速查找定位方法，首先判別用戶設定的數據範圍、分組組數和外部輸入數據的情況並轉換得到查找使用的數據範圍、分組組數和查找使用的輸入數據，計算、存儲各分組邊界值，再由狀態機控制整個分組查找定位過程。分組查找定位過程中將查找使用的輸入數據按特定方式與事先計算存儲好的分組邊界值進行比較。按照本發明提出的快速查找定位方法，可以用最少的比較次數快速確定外部輸入數據在用戶設定的數據範圍內屬於哪一個分組，並將其所在的分組編號輸出。
文檔編號G06F17/30GK102184214SQ20111011448
公開日2011年9月14日 申請日期2011年5月4日 優先權日2011年5月4日
發明者崔城, 張巖, 高禮忠 申請人:東南大學