[發(fā)明專利]與數(shù)據(jù)流同步的數(shù)據(jù)檢索電路

有效

• 申請(qǐng)?zhí)枺?/td>: 201210224661.3
• 申請(qǐng)日: 2012-07-02
• 公開（公告）號(hào): CN102736888A
• 公開（公告）日: 2012-10-17
• 發(fā)明（設(shè)計(jì)）人: 程元斌
• 申請(qǐng)（專利權(quán)）人: 江漢大學(xué)
• 主分類號(hào): G06F7/04
• 分類號(hào): G06F7/04
• 代理公司: 北京三高永信知識(shí)產(chǎn)權(quán)代理有限責(zé)任公司 11138
• 代理人: 徐立

技術(shù)領(lǐng)域

本發(fā)明涉及信息處理領(lǐng)域，特別涉及一種與數(shù)據(jù)流同步的數(shù)據(jù)檢索電路。

背景技術(shù)

數(shù)據(jù)檢索是信息處理的常用運(yùn)算，涉及信息檢索、模式識(shí)別、信息安全等領(lǐng)域的諸多應(yīng)用。數(shù)據(jù)檢索的速度直接關(guān)系到這些應(yīng)用的性能。

現(xiàn)有的數(shù)據(jù)檢索可分為軟件檢索與硬件檢索兩大類。軟件檢索只能在每周期比較一個(gè)字符的基礎(chǔ)上進(jìn)行，其不足是顯而易見的。與軟件檢索相比，硬件檢索可以實(shí)現(xiàn)多個(gè)字符的并行比較，使檢索過程與數(shù)據(jù)流同步成為可能。其中，以自動(dòng)機(jī)理論為基礎(chǔ)的硬件檢索技術(shù)，由于其針對(duì)的是流的串行處理，所以基于該技術(shù)的數(shù)據(jù)檢索電路不僅結(jié)構(gòu)復(fù)雜，而且并行度不高，檢索速度受到明顯的限制。為了提高檢索速度，現(xiàn)有技術(shù)提供了一種字符串檢索電路。具體地，該字符串檢索電路基于流水線技術(shù)，每一周期可以對(duì)已輸入電路的n個(gè)字節(jié)與預(yù)先存于字典的樣本進(jìn)行一輪并行比較，但需要用到前一輪的比較結(jié)果，而對(duì)于m個(gè)字節(jié)的樣本，每一輪所需保存的中間結(jié)果就有m個(gè)。

在實(shí)現(xiàn)本發(fā)明的過程中，發(fā)明人發(fā)現(xiàn)現(xiàn)有技術(shù)至少存在以下問題：

眾所周知，流水線技術(shù)本質(zhì)上遵循的仍然是數(shù)據(jù)流的串行處理的程序邏輯，只是將流水線上位置靠后的指令提前執(zhí)行從而達(dá)到一種并行處理的效果而已。為了實(shí)現(xiàn)這種“并行”處理，普遍采用預(yù)測(cè)技術(shù)。對(duì)于具有N道指令的流水線，其每周期可能的結(jié)果數(shù)為2^N，然后第K道指令需要從2^(K-1)個(gè)預(yù)測(cè)中選擇正確的預(yù)測(cè)。這極大地帶來了電路的復(fù)雜性。

發(fā)明內(nèi)容

考慮到上述方面，本發(fā)明想要推出一種與數(shù)據(jù)流同步的數(shù)據(jù)檢索電路，當(dāng)待檢索數(shù)據(jù)流過時(shí)，僅僅根據(jù)當(dāng)前流過電路的數(shù)據(jù)與樣本數(shù)據(jù)的并行比較得出比較結(jié)果，這種比較是與數(shù)據(jù)的傳輸同步的，且完全不需要依賴歷史數(shù)據(jù)。基于此，本發(fā)明提供一種與數(shù)據(jù)流同步的數(shù)據(jù)檢索電路，所述技術(shù)方案如下：

一種與數(shù)據(jù)流同步的數(shù)據(jù)檢索電路，所述電路包括：

移位寄存器，用于在時(shí)鐘信號(hào)作用下，每個(gè)時(shí)鐘周期接收輸入數(shù)據(jù)流中的一個(gè)數(shù)據(jù)單元，同時(shí)將前一個(gè)時(shí)鐘周期存放的數(shù)據(jù)移動(dòng)一個(gè)數(shù)據(jù)單元；

樣本寄存器，用于預(yù)先設(shè)置樣本數(shù)據(jù)，所述樣本數(shù)據(jù)包括若干數(shù)據(jù)單元；

模2加運(yùn)算電路，用于將所述移位寄存器中的數(shù)據(jù)和所述樣本寄存器中的數(shù)據(jù)進(jìn)行模2加運(yùn)算；

提取指示寄存器，用于指示所述模2加運(yùn)算的運(yùn)算結(jié)果中的有效位部分；

結(jié)果提取與判決電路，用于提取所述模2加運(yùn)算的運(yùn)算結(jié)果中的有效位部分；并根據(jù)所述有效位部分判決是否檢索到與所述樣本數(shù)據(jù)一致的數(shù)據(jù)；若判決為檢索到與所述樣本數(shù)據(jù)一致的數(shù)據(jù)，則產(chǎn)生匹配信號(hào)。

其中，所述數(shù)據(jù)單元的寬度大小為1、8或16位。

其中，所述移位寄存器與所述樣本寄存器長(zhǎng)度相同；而所述樣本數(shù)據(jù)的長(zhǎng)度小于或者等于所述樣本寄存器的長(zhǎng)度。

其中，所述模2加運(yùn)算電路具體用于，

將所述移位寄存器中的數(shù)據(jù)和所述樣本寄存器中相對(duì)應(yīng)的數(shù)據(jù)單元分別進(jìn)行模2加運(yùn)算；將所述移位寄存器中的數(shù)據(jù)和所述樣本寄存器中相對(duì)應(yīng)的第i個(gè)數(shù)據(jù)單元進(jìn)行模2加運(yùn)算為，

其中，B_i為所述移位寄存器中數(shù)據(jù)的第i個(gè)數(shù)據(jù)單元，S_i為所述樣本寄存器中第i個(gè)數(shù)據(jù)單元，n為所述數(shù)據(jù)單元的寬度，b_ij與s_ij分別為所述B_i與所述S_i中第j個(gè)比特；M_i為將所述移位寄存器中的數(shù)據(jù)和所述樣本寄存器中相對(duì)應(yīng)的第i個(gè)數(shù)據(jù)單元進(jìn)行模2加運(yùn)算的運(yùn)算結(jié)果，M_i具體為一個(gè)比特的布爾數(shù)據(jù)。

其中，所述提取指示寄存器具體用于，

預(yù)先設(shè)置指示所述模2加運(yùn)算的運(yùn)算結(jié)果的有效部分的指示數(shù)據(jù)；所述指示數(shù)據(jù)為，

其中，所述樣本數(shù)據(jù)的長(zhǎng)度為m+1，所述移位寄存器的長(zhǎng)度為n+1，且m≤n；f_i為所述指示數(shù)據(jù)的第i個(gè)比特?cái)?shù)據(jù)。

其中，所述結(jié)果提取與判決電路具體用于，

將所述模2加運(yùn)算的運(yùn)算結(jié)果和所述指示數(shù)據(jù)中相對(duì)應(yīng)位的數(shù)據(jù)分別進(jìn)行與運(yùn)算，提取出所述模2加運(yùn)算的運(yùn)算結(jié)果中的有效位部分；所述將所述模2加運(yùn)算的運(yùn)算結(jié)果和所述指示數(shù)據(jù)中相對(duì)應(yīng)的第i位數(shù)據(jù)進(jìn)行與運(yùn)算為，

C_i＝M_if_i