[發明專利]漢明距離計算方法、芯片和設備

在審

• 申請號: 201911415029.5
• 申請日: 2019-12-31
• 公開（公告）號: CN113129966A
• 公開（公告）日: 2021-07-16
• 發明（設計）人: 李祎;繆向水;程龍;李健聰;譚海波;石曉鐘;黃克驥
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G11C13/00
• 分類號: G11C13/00;G06K9/62
• 代理公司: 北京億騰知識產權代理事務所(普通合伙) 11309
• 代理人: 張靜娟;陳霽

本申請實施例提供一種計算字符串的漢明距離的方法、及漢明距離計算芯片和設備，所述芯片包括n個運算單元，每個運算單元中包括負極相連的兩個憶阻器，其電阻都處于第一阻值，所述方法包括：獲取第一字符串和第二字符串；對于任意一個字符對，將該字符對中的兩個字符對應的預設電位分別輸入該字符對對應的運算單元的兩個憶阻器的正極，其中對不同字符預設的電位之差大于使憶阻器由第一阻值阻變的閾值電壓的2倍；對所述n個運算單元中的各個憶阻器施加讀取電壓，所述讀取電壓使得不改變各個憶阻器的阻值、并在各個憶阻器中產生電流；基于所述n個運算單元中的各個憶阻器中的電流，確定第一字符串與第二字符串的漢明距離。該方法節約了功耗和延時。

技術領域

本申請涉及漢明距離計算技術領域，具體涉及一種漢明距離計算方法、芯片和設備。

背景技術

在信息論中，兩個等長字符串之間的漢明距離是兩個字符串對應位置的不同字符的個數。 傳統的漢明距離計算方法包括通過軟件或硬件計算的方法。其中，在通過程序計算兩個字符 串的漢明距離時，通過對兩個字符串的每個字符依次進行異或計算，并將異或計算的結果相 加，以獲取兩個字符串的漢明距離。在字符串的位數非常多的情況中，在進行上述計算過程 中，需要進行多次循環計算，并且在存儲器與處理器之間進行大量數據的傳輸。當前用于計 算漢明距離的硬件電路例如包括基于互補金屬氧化物半導體(Complementary Metal Oxide Semiconductor，CMOS)的異或(exclusive OR，XOR)門電路。該電路包括多個CMOS，其中 每個CMOS包括N型金屬氧化物半導體(N Metal OxideSemiconductor,NMOS)晶體管和P型金 屬氧化物半導體(P Metal Oxide Semiconductor,PMOS)晶體管，并且電路結構復雜，功耗大， 計算時間長。

因此，需要一種更有效的漢明距離計算方案。

發明內容

本申請實施例旨在提供一種更有效的漢明距離電路及基于其的漢明距離計算方法，以解 決現有技術中的不足。

為實現上述目的，本申請一方面提供一種計算字符串的漢明距離的方法，應用于漢明距 離計算芯片，所述漢明距離計算芯片包括n個運算單元，每個運算單元中包括負極相連的兩 個憶阻器，所述兩個憶阻器的電阻都處于第一阻值，其中n≥1，所述方法包括：獲取第一字 符串和第二字符串，所述第一字符串和第二字符串相同位上的兩個字符構成一個字符對，所 述字符對的個數等于n，且一個字符對對應一個運算單元；對于任意一個字符對，將該字符 對中的兩個字符對應的預設電位分別輸入該字符對對應的運算單元的兩個憶阻器的正極，其 中，當所述兩個字符不同時，兩個字符對應的預設電位的差值大于使所述憶阻器由所述第一 阻值轉換為第二阻值的閾值電壓的2倍；對所述n個運算單元中的各個憶阻器施加讀取電壓， 所述讀取電壓使得不改變各個憶阻器的阻值、并在各個憶阻器中產生電流；基于所述n個運 算單元中的各個憶阻器中的電流，確定第一字符串與第二字符串的漢明距離。

在該方法中，使用兩個憶阻器構成一位漢明距離運算核，所需器件數少，電路結構簡單， 以電壓信號為輸入，利用憶阻器的阻態改變來實現運算操作，并通過憶阻器的電阻態存儲運 算結果。并且，利用多個運算核同時對多位數據并行運算，能夠極大地提高信息處理的速度， 無需額外的數據傳輸與存儲，節約了計算功耗和計算時間。

在一種實施方式中，所述對所述n個運算單元中的各個憶阻器施加讀取電壓包括，控制 所述n個運算單元中的各個憶阻器并聯，以對各個憶阻器施加讀取電壓。

在一種實施方式中，各個運算單元中的兩個憶阻器的負極通過該運算單元中的輸出線相 連，各個運算單元中還包括開關元件；所述控制所述n個運算單元中的各個憶阻器并聯包括： 控制所述n個運算單元的開關元件閉合，使所述多個運算單元各自的輸出線連接；

所述基于所述n個運算單元中的各個憶阻器中的電流，確定第一字符串與第二字符串的 漢明距離包括：讀取所述輸出線上的電流，并根據所讀取的電流確定所述第一字符串與所述 第二字符串之間的漢明距離。