用於產生變換的方法和設備的製作方法
2023-05-23 22:07:06 2
專利名稱：用於產生變換的方法和設備的製作方法
技術領域：
本發明涉及產生諸如循環冗餘碼、多項式碼和散列碼等變換的領域，尤其涉及用於產生變換的方法和設備。
背景技術：
在
圖1中示出已有技術的變換產生裝置10的例子。已有技術的變換產生裝置10具有數據寄存器(移位寄存器)12和中間餘數寄存器14。把圖1的特定產生裝置設計成用於計算循環冗餘碼(CRC-16)。在策略上將多個異或電路18與中間餘數寄存器14中的多個寄存器16耦合。數據位從數據寄存器12中移出並移入中間寄存器14。當數據位已完全移入中間寄存器14時，中間寄存器包含與數據位有關的CRC。還可以用軟體對變換產生裝置進行編碼。已證明用軟體模擬硬體來產生變換不是一種有效的方法，所以軟體方案一般每次都使用查詢表來計算一個字節或半字節(四位)。所建立的查詢表可用於任何尺寸的數據量(例如，1位、10位等)。
封包裝置(packetizer)用變換產生裝置來計算新形成的數據包的CRC。封包裝置接收來自各自源的包(數據)。然後，依據接收到的包的最終目的地對這些包進行分組。如果兩個小的包具有同一目的地，則把它們組合成一個包然後傳輸到該目的地。在已有技術的應用中，封包裝置從這兩個包中除去CRC，然後根據這兩個包的組合數據重新計算CRC。在其它情況下，封包裝置可接收一個大的包，需要把這個包分成兩個較小的包。在已有技術的應用中，要丟棄大包的CRC，並從兩個較小的包的暫存器(scratch)中計算新的CRC。由於接收到的包的CRC包含對計算輸出包的CRC有用的信息，所以這個處理不是有效的。
變換產生裝置還用於關聯存儲器。變換產生裝置計算散列碼或多項式碼(參見USPN 4,527,239 Brandin)來確定數據包的地址。當數據包是兩個原先的包的組合時，已有技術的關聯存儲器從暫存器中計算該新數據包的新變換(地址)。可通過用舊的變換來計算新變換的變換產生裝置來實現這些處理上的優點。
於是，需要一種從現有的變換中產生新的變換而不使用基礎數據的的變換產生裝置。
發明內容
一種克服了這些問題的方法，通過接收與第一數據串有關的第一變換來產生變換。還接收與第二數據串有關的第二變換。把第二變換附加到第一變換以形成用於第一-第二數據串的第一-第二組合變換。
實行此方法的設備，包括與一控制器耦合的輸入/輸出埠。控制器還與查詢存儲器、移位模塊和組合器相耦合。
附圖概述圖1是已有技術的變換產生裝置的示意圖；圖2是依據本發明的變換產生裝置的方框圖；圖3是在圖2的變換產生裝置中所使用的移位模塊的圖示表示；圖4是在圖2的變換產生裝置中所使用的組合器的圖示表示；圖5是依據本發明的變換產生裝置的另一個實施例的方框圖；圖6是移位模塊的流程圖；圖7是不移位模塊的流程圖；圖8是變換模塊的流程圖；圖9是不變換模塊的流程圖；圖10是關聯存儲器的方框圖；圖11是封包裝置的方框圖；圖12是普通用途計算機和包含計算機可讀指令的計算機可讀存儲介質的示意圖；圖13是用於CRC-32多項式碼的查詢表；以及圖14是用於CRC-32多項式碼的逆向查詢表。
本發明的較佳實施方式圖2示出本發明的變換產生裝置20的方框圖。與已有技術的變換產生裝置不同的是，變換產生裝置20可根據兩個先前的變換而不參考基礎數據來計算新的變換。為了理解變換產生裝置20是如何工作的，理解一些基礎數學是有幫助的。基礎數學以多項式碼為基礎，也包括循環冗餘碼，但不限於此。可用以下的公式來表示這些代碼Xn-kM(X)=Q(X)G(X)+R(X)這裡Xn-k是移位項M(X)是報文多項式；G(X)是產生裝置多項式；Q(X)是報文被產生裝置多項式除時獲得的商；以及R(X)是除法處理的餘數。
餘數是報文的CRC或變換。從以上公式中可看出，已被異或的兩個報文的變換等於經異或的與兩個報文有關的變換。如果第一報文為「A」，第二報文為「B」，則組合報文為「AB」。該報文多項式為AB(X)=XZA(X)+B(X)這裡Z等於報文B中的位數。
以及RAB(X)=R(XZA(X))+RB(X)於是，為了產生報文「AB」的變換，我們只需要把「B」的變換與「A0」變換相組合，這裡0表示Z個零。當知道「A」與「B」的變換時，我們只需要計算「A」的移位變換值並把它與「B」的變換相組合。幸運地，計算移位變換是一個簡單的處理過程。
變換產生裝置20使用以上所述的數學公式，用現有的變換來計算新變換。使用輸入/輸出埠22來接收現有的變換以及輸出新的變換。I/O埠22耦合到協調存儲器26、移位模塊28和組合器30的功能的控制器24。存儲器包含用於變換的查詢表。在圖13中示出這種查詢表的一個例子。圖13中的表以CRC-32變換為基礎，以字節為基礎來計算一個字節上的變換。可對其它多項式產生其它表。本發明不限於CRC多項式，還可適用各種其它的多項式。特定的多項式取決於變換產生裝置的應用。移位模塊28實行的功能是確定移位變換。組合器用於把例如一個移位第一變換和一第二變換相組合(XOR)，以形成第一-第二變換。第一-第二變換被定義為與第一-第二數據串有關的變換(例如，在通信的例子中，在第一數據串後立即傳輸第二數據串第一-第二數據串)。使第一變換移位並把它與第二變換相組合的處理叫做附加。可用軟體或使用由存儲器、微處理器和一些移位寄存器以及異或門構成的硬體來實現變換產生裝置。
圖3示出變換產生裝置20所使用的移位模塊28的示意圖。把待移位的變換存儲在變換寄存器40中，該存儲器具有輸入42、移位控制44和輸出46。輸出46連到異或門48。查詢寄存器50包含使用從待移位的變換得到的指針而選中的項。查詢寄存器50具有輸入52、移位控制54和輸出56。輸出56耦合到異或門48的第二輸入。異或門的輸出58被存儲在輸出寄存器60中。在適當的處理後，輸出寄存器60包含移位變換，經由輸出62把此變換傳輸到控制器24。
圖4示出變換產生裝置20所使用的組合器30的示意圖。第一寄存器70和第二寄存器72的輸出耦合到異或門74。在一個例子中，第一寄存器70包含已移位的第一變換，第二寄存器72包含第二變換。異或門74的輸出連到輸出寄存器76。一旦把已移位的第一變換與第二變換相組合，則輸出寄存器76包含第一-第二變換。
圖5是依據本發明的變換產生裝置100另一個實施例的方框圖。變換產生裝置100具有耦合到控制器24的I/O埠22。控制器24在總線102上與存儲器26、移位模塊28、不移位模塊104、變換模塊106、不變換模塊108和組合器30進行通信。存儲器26包含查詢表(例如，圖13中的表)以及逆向查詢表(在圖14中示出它的一個例子)。圖14所述的逆向查詢表以同一CRC-32為基礎，它採用一個字節接一個字節的方法。圖5的變換產生裝置100可類似於圖2的變換產生裝置20來組合變換。此外，變換產生裝置100可確定給出第一變換和第二數據串或給出第一數據串和第二變換的第一-第二變換。變換產生裝置100可從第一-第二組合變換中除去第二變換以確定第一變換。實際上，變換產生裝置100允許對給出足夠輸入的變換進行完整的變換處理作為變換或數據。在參考圖6-9詳細地說明每個模塊後，將更詳細地說明這是如何實現的。
圖6是移位模塊的流程圖。移位模塊確定移位報文(即，「A0」-XZA(X))的變換。在步驟120處理開始，在步驟124接收待移位的變換122。接著，在步驟128提取指針126。然後，在步驟130，把變換122向右移位指針126的位數。這形成了移位指針132。注意，使用單詞左和右是為了方便，它們基於最高位通常位於左邊的慣例。在使用不同的慣例時，必須改變單詞左和右以適應此慣例。接著，在步驟136，把移位變換132與有關指針126的項134相組合。這在步驟140形成移位變換138，從而在步驟142結束處理。注意，如果使第一變換移位的原因是為了產生第一-第二變換，則必須把第一變換移位第二數據串的位數。這是通過執行X次移位模塊來進行的，這裡X等於把第二數據串中數據位的數目被指針中的位數除。注意，實行移位模塊的另一個方法是使用類似於圖1所示的多項式產生裝置。把第一變換122置於中間冗餘寄存器14中。接著，處理數目等於第二數據串中數據位的數目的一些邏輯零(空)。
圖7是不移位模塊的流程圖。何時使用該模塊的一個例子是在把數據串「AB」的變換與數據串「B」的變換相組合時。這就留下了用於數據串「A0」或XZA(X)的變換。必須對此變換進行「不移位」，以找到用於數據串「A」的變換。在步驟150處理開始，在步驟154接收移位變換152。在步驟156，提取逆向指針158。逆向指針158等於移位變換152的最高部分160。在步驟164，把逆向指針158與逆向查詢表(例如，見圖14)中的指針162相結合。接著，把與指針162有關的項166與移位變換相組合。這在步驟172產生了中間產品170。在步驟174，把中間產品170向左移位，以形成移位的中間產品176。然後，在步驟178，把經移位的中間產品176與指針162相組合，以形成變換180，從而在步驟182結束處理。注意，如果「B」數據串中的位數不等於指針中的位數，則執行X次不移位模塊，這裡X=z/(指針中的位數)。
圖8是變換模塊的流程圖。變換模塊可確定給出第一變換和第二數據串的用於第一-第二數據串的第一-第二變換，而不必先把第二數據串轉換成第二變換。在步驟190處理開始，在步驟194提取第一變換194的最低部分192。在步驟200，把這部分與第二數據串196相組合以形成指針198。接著，在步驟206，把經移位的第一變換202與有關查詢表(例如，圖12)中該指針的項204相組合。在步驟210，產生組合的變換208，從而在步驟212結束處理。注意，如果指針為一個字節的長度，則變換模塊每次只能處理一個字節的數據。當第二數據串比一字節長時，則變換模塊每次執行一個字節數據，直到已執行整個第二數據串。在另一個例子中，假設第一變換等於全零(空)，則組合的變換隻是用於第二數據串的變換。在另一個實施例中，第一變換可以是一個先決條件，獲得的變換則是先決條件-第二變換。在另一個例子中，假設想要用於一個四級數據串的一個四級變換。提取四級數據串中的第一數據部分(例如，字節)。它指向查詢表中的一個項。當第四數據串不僅僅包含第一數據部分時，提取下一數據部分。把下一數據部分與該項的最低部分相組合以形成一指針。然後，把該項向右移位下一數據部分中的位數，以形成一移位項。把該移位項與有關該指針的第二項相組合。重複此處理，直到已處理整個四級數據串。
圖9是不變換模塊的流程圖。不變換模塊可確定給出第一-第二變換和第二數據串的用於第一數據串的第一變換。在步驟220，處理開始，在步驟226，提取第一-第二變換224的最高部分222。最高部分222是與逆向查詢表中的指針228有關的逆向指針。在步驟230訪問該指針。接著，在步驟236，把第一-第二變換224與和指針有關的項232相組合以形成中間產品234。在步驟238，把中間產品向左移位指針228中的位數。這形成了經移位的中間產品240。接著，在步驟246把指針228與第二數據串242相組合而形成結果244。在步驟250，結果244與已移位的中間產品240相組合，形成第一變換248，並在步驟252結束處理。如果第二數據串比指針長，則該模塊再重複多次。
變化模塊100可幹的一些例子包括從第一-第二-第三變換和第一變換中確定第二-第三變換。第一變換移位第二-第三數據串中的數據位數。把經移位的第一變換與第一-第二-第三變換相組合而形成第二-第三變換。在另一個例子中，變換產生器100可在接收到第四數據串後確定第一-第二-第三-第四變換。在一個例子中，變換模塊會首先計算第四變換(使用變換模塊)。使用移位模塊，把第一-第二-第三變換移位第四數據串中的位數。然後，使用組合器把經移位的第一-第二-第三變換與第四變換相組合。
圖10是關聯存儲器300的方框圖。關聯存儲器300使用變換產生器302使數據串與地址和確認符相聯。一般，地址是變換的一半，而確認符等於變換的另一半。目錄304在必要時存儲地址清單及其有關的確認符和連結清單。必需用連結清單來解決任何衝突。如果兩個不同的數據串變換到同一地址，則產生了衝突。連結清單指向存儲有衝突數據串的另一個地址。確認符用於識別是否訪問到與該數據串有關的正確地址。目錄示出數據串在存儲器(存儲器)306中所存儲的地址。由通過輸入/輸出埠310與外界進行通信的控制器308來控制此處理。如果所有的數據串都具有固定的長度，則可不必使用目錄將304。如果知道第一變換和第二變換來存儲第一-第二數據串，則使用變換產生器302可容易地進行查詢。還可對相反的次序(即，第二-第一數據串)進行快速搜索。對本領域內的技術人員來說，各種其它的快速搜索路徑也是明顯的。注意，對關聯存儲器的所屬多項式的要求不同於對CRC的多項式的要求。結果，可在此應用中使用許多其它的多項式產生器。
圖11是封包裝置320的方框圖。封包裝置320是這裡所述的使用變換產生器322的裝置的另一個例子。在一個例子中，封包裝置是路由器的一部分。控制器326接收輸入的包324。控制器326從輸入的包324中形成輸出的包328。通常，輸出的包328具有固定長度，輸入的包324具有不確定的長度或不同的長度。通常，輸入的數據都還未形成包。可從去向同一目的地的兩個小的包330、332中形成輸出的包334。該數據包包含數據部分(「A」或「B」)和一個CRC或變換[R(A)或R(B)]。如果給出各個包330、332的CRC，則可使用變換產生器322快速地確定組合成的包(「AB」)334的CRC[R(AB)]。在另一個例子中，輸入的包336太大，則必須把它分割成兩個包338、340。首先通過計算兩個數據串中較短的一個數據串的變換(例如，[r(C)])以及從組合成的變換中除去該變換而形成另一個CRC[R(D)]，可容易地計算兩個新的CRC。可以想到的另一個例子是需要對所需的CRC進行更多外加的處理。這裡所述的變換產生器可進行所有的這些計算，而不必使用下面數據的暫存器來重新計算CRC。
圖12是通用計算機350和包含計算機可讀指令的計算機可讀存儲介質352的示意圖。計算機可讀存儲介質352包含由計算機350所執行的指令，該指令執行變換產生器100的功能。這些指令可以是獨立的，也可以作為執行關聯存儲器300的功能或執行封包裝置320的功能的一組指令的一部分。
這樣，已描述了可從多個獨立的變換中確定組合變換而不必訪問以下數據的變換產生器。此外，變換產生器可執行在封包裝置和關聯存儲器中產生的各種其它的變換處理。變換產生器的用途不限於這裡所述的兩個例子(即，關聯存儲器和封包裝置)。許多其它的應用對本領域內的技術人員是顯而易見的。
雖然結合本發明的特殊實施例對本發明進行了描述，但很顯然，根據以上的描述，許多選擇、修改和變化對本領域內的技術人員是明顯的。因此，將這些選擇、修改和變化包含在附加的權利要求書中。
權利要求
1．一種產生變換的方法，其特徵在於包括以下步驟(a)接收與第一數據串有關的第一變換；(b)接收與第二數據串有關的第二變換；以及(c)把第二變換附加到第一變換來產生用於第一-第二數據串的第一-第二組合變換。
2．如權利要求1所述的方法，其特徵在於還包括以下步驟(d)從第一-第二組合變換中除去第二變換來形成移位的第一變換；(e)使移位的第一變換不移位來形成第一變換。
3．如權利要求2所述的方法，其特徵在於不移位步驟包括以下步驟(Ⅰ)從移位的第一變換中提取逆向指針；(ⅱ)讀取逆向查詢表中的一個指針；(ⅲ)把與該指針有關的查詢表的一個成員與移位的第一變換相組合來形成中間產物；(ⅳ)把中間產物按指針中的位數左移來形成移動的中間產物；以及(ⅴ)把移動的中間產物與該指針相組合。
4．如權利要求3所述的方法，其特徵在於步驟(ⅰ)到(ⅴ)重複X次，這裡X等於把指針中的位數被第二數據串中的位數除。
5．如權利要求1所述的方法，其特徵在於附加步驟包括以下步驟(ⅰ)第一變換向右移位第二數據串中的位數來形成移位的第一變換；以及(ⅱ)把移位的第一變換與第二變換相組合。
6．如權利要求1所述的方法，其特徵在於該變換是把多項式碼應用於數據串的結果。
7．如權利要求6所述的方法，其特徵在於多項式碼是循環冗餘碼。
8．如權利要求1所述的方法，其特徵在於還包括以下步驟(d)接收與第一-第二-第三數據串有關的第一-第二-第三變換。(e)第一變換移位第二-第三數據串中的位數來形成移位的第一變換；以及(f)把第一-第二-第三變換與移位的第一變換相組合來形成第二-第三變換。
9．如權利要求8所述的方法，其特徵在於還包括以下步驟(g)接收第四數據串；(h)計算第四變換；(ⅰ)第一-第二-第三變換移位第四數據串中的位數來形成移位的第一-第二-第三變換；以及(j)把移位的第一-第二-第三變換與第四變換相組合來形成第一-第二-第三-第四變換。
10．如權利要求9所述的方法，其特徵在於計算第四變換的步驟還包括以下步驟(ⅰ)提取第四數據串的第一數據部分；(ⅱ)訪問查詢存儲器表中與第一數據部分有關的成員；(ⅲ)當第四數據串不僅僅包含第一數據時，提取下一個數據部分；(ⅳ)把下一個數據部分與該成員的最低部分相組合來形成指針；(ⅴ)把該成員向右移動下一個數據部分中的位數來形成移動的成員；(ⅵ)把移動的成員同與指針有關的第二成員相組合；以及(ⅶ)重複步驟(ⅳ)到(ⅵ)，直到已處理了全部的第四數據串。
11．如權利要求8所述的方法，其特徵在於移位步驟包括以下步驟(Ⅰ)從第一變換中提取一指針；(ⅱ)第一變換向右移動指針中的位數來形成移動的第一變換；(ⅲ)把移動的第一變換同與指針有關的查詢表中的一個成員相組合。
12．如權利要求11所述的方法，其特徵在於步驟(ⅰ)到(ⅲ)重複X次，這裡X等於指針中的位數被第二-第三數據串中的位數除。
13．如權利要求8所述的方法，其特徵在於移位步驟包括以下步驟(Ⅰ)把第一變換置於多項式產生器的中間寄存器中；(ⅱ)處理等於第二-第三數據串中位數的許多邏輯零。
14．一種包含計算機可讀指令的計算機可讀存儲介質，在把所述存儲介質插入計算機時執行以下步驟(a)接收與第一數據串有關的第一變換；(b)接收與第二數據串有關的第二變換；以及(c)把第二變換附加到第一變換來產生用於第一-第二數據串的第一-第二組合變換。
15．如權利要求14所述的計算機可讀存儲介質，其特徵在於還包括以下步驟(d)從第一-第二組合變換中除去第二變換來形成移位的第一變換；(e)使移位的第一變換不移位來形成第一變換。
16．如權利要求14所述的計算機可讀存儲介質，其特徵在於附加步驟包括以下步驟(ⅰ)第一變換向右移位第二數據串中的位數來形成移位的第一變換；以及(ⅱ)把移位的第一變換與第二變換相組合。
17．一種變換產生器，其特徵在於包括輸入/輸出埠；耦合到輸入/輸出埠的控制器；耦合到控制器的查詢存儲器；耦合到控制器的移位模塊；以及耦合到控制器的組合器。
18．如權利要求17所述的變換產生器，其特徵在於還包括耦合到控制器的不移位模塊。
19．如權利要求17所述的變換產生器，其特徵在於還包括耦合到控制器的變換模塊。
20．如權利要求17所述的變換產生器，其特徵在於還包括耦合到控制器的不變換模塊。
全文摘要
一種變換產生器(20),具有輸入/輸出埠(22)。耦合到輸入/輸出埠(22)的是控制器(24)。輸入/輸出埠(22)接收輸入的變換和數據串並輸出新的變換。查詢存儲器(26)耦合到控制器(24)並用於確定新的變換。移位模塊(28)和組合器(30)也耦合到控制器(24)並與存儲器(26)一起使用來確定新的變換。
文檔編號G06F11/10GK1219305SQ97194318
公開日1999年6月9日 申請日期1997年3月4日 優先權日1996年3月8日
發明者克裡斯多弗·布蘭丁 申請人:新芯有限公司