用於執行循環冗餘碼檢錯的技術的製作方法

2023-07-20 14:41:56

專利名稱：用於執行循環冗餘碼檢錯的技術的製作方法
技術領域：
本文所描述的本發明的實施方式涉及數據傳輸完整性，本發明的實施方式尤
其涉及可用於執行諸如使用循環冗餘碼(CRC)的數據檢錯算法中涉及的各種函數 的技術。
北旦 冃豕
循環冗餘碼(CRC)已在各種算法中用來確保從發送設備或系統向接收設備 或系統傳送的數據的完整性。通常，CRC檢錯通過隨傳送的數據編碼一表示該傳 送的代碼與一生成多項式之間的算術無進位除法運算(即，模2)的餘數的碼來實 現。然後，同一生成多項式可在接收器處在對所傳送的數據進行的另一無進位除法 運算中使用，可將其結果與編碼的餘數值進行比較來檢測所傳送數據中的任何差 錯。
執行CRC檢錯的一種現有技術包括"基於表"的算法，該算法用在包含預先 計算出的無進位除法運算中涉及的一個或多個算術運算的結果的表內的査找操作 來代替這一個或多個算術運算。例如，

圖1示出現有技術的基於表的CRC檢錯算 法，其中32位元組的寄存器包含與位流相關聯的CRC碼的當前值。存儲在該寄存器 內的值代表待傳送數據的增加。數據可在傳送之前用CRC碼來擴充。當來自該數 據的非擴充部分的新字節在CRC的計算中被使用時，在該新字節與包含當前CRC 值的寄存器的最低有效字節之間進行布爾"異或"(XOR)運算。XOR運算的結果 被用於索引有256個條目的表(例如每個條目有4位元組)，該表包含預先計算出的 表索引乘以值232與生成多項式之間的無進位(例如，模2)除法運算的結果。然 後，將從該表格的查找操作返回的字節與保持當前CRC值的寄存器的未被納入考 慮的剩餘字節(即，寄存器的3個最高有效字節)進行XOR。在進行XOR運算之 前，將這些字節向右移位一個字節的位置。該XOR運算的結果是要被用於擴充該 數據的下一個CRC值，並且被與老的CRC值保持在同一寄存器內。
參照圖1討論的運算需要處理資源(例如，循環時間和功率)來進行計算，
並且在實現CRC算法的計算機系統內還需要許多輸入/輸出和/或存儲器訪問操作。
使問題進一步複雜化的是許多實現CRC算法的系統在所傳送的數據部分內使用位 反射技術這一事實。更具體地， 一些CRC生成算法(例如，"CRC32c")在CRC 碼計算之前在它們各自的字節內對位進行反射。位反射是諸如字節或字節集合的二 進位數據段的位以鏡像方式交換位置的過程。例如，"1010"經反射的表示是"0101"。 通常，位反射與處理器中特定尋址方案(例如，"小端(little endian)")的使用的 組合導致輸入流的位被按適於由軟體CRC生成算法快速處理的次序存儲。
對於圖1所示的現有技術CRC算法，應對數據的經反射版本還引入另一層面 的複雜性和計算強度。通常，許多現有技術CRC算法，尤其是那些使用基於表的 實現的算法可能需要過多的硬體和/或軟體資源，並且實現這些算法的系統所需的 功率增大。
附圖簡要說明
要求保護的主題在本說明書的結語部分中被詳細、明確地指出。然而，通過 閱讀附圖同時參考以下詳細描述，可獲得對要求保護的主題——就運算的組織和方 法而言——及其目的、特徵和優點的最佳理解，附圖中 圖1示出循環冗餘碼(CRC)生成的現有技術實現。 圖2是示出在執行本發明的至少一個實施方式時使用的運算的流程圖。 圖3示出根據本發明一實施方式的在無進位乘以二進位數據片時所涉及的各 種運算。
圖4示出可在其中使用一個實施方式的點對點(PtP)計算機系統。 圖5示出可在其中使用本發明一實施方式的前端總線(FSB)計算機系統。
詳細描述
在以下詳細描述中，闡述了許多具體細節以便於提供對要求保護的主題的透 徹理解。然而，本領域技術人員應該理解，要求保護的主題可在沒有這些具體細節 的情況下實施。在其它實例中，未描述公知的方法、過程、組件和電路以避免混淆 要求保護的主題。
本說明書中對"一種實施方式"或"一實施方式"的引述表示與該實施方式 相關地描述的特定特徵、結構或特性被包括在本發明至少一個實施方式中。本說明 書中各處出現術語"在一個實施方式中"不必然全部指代同一實施方式。
本發明的至少一個實施方式通過使用可用於執行由計算機實現的CRC生成算 法或其它計算算法的某些方面的兩條新的微處理器指令來對現有技術的循環冗餘
碼(CRC)檢錯實現進行改進。貫穿本公開，術語"指令"的使用應當表示在由機
器執行時使該機器執行與該指令相稱的各種操作的任何機器可讀構造，諸如可由 "位"表示的一組電信號或電磁信號。例如，在一實施方式中，指令可以是計算機 可讀指令，在由處理器執行時該指令使該處理器執行由該指令指示的或與該指令的 目的一致的一個或一組操作。特別地，在一實施方式中，指令可以是存儲在諸如載 波、磁碟、半導體存儲器設備、硬碟驅動器、壓縮盤等的某種介質中的一組位或其 表示。與微處理器架構相關，術語"指令"的使用可表示用戶可視的"宏指令"，
諸如特定指令集架構(ISA)內的指令、或從根據ISA的宏指令得到或解碼的"微 指令"。
不是如現有技術中那樣依賴於基於表的CRC檢錯算法，本發明的至少一個實 施方式代之以包括兩條新指令其一用於執行無進位(例如，模2)乘法，而另一 指令用於在待檢錯的數據段上進行位反射。在其它實施方式中，這兩條指令可被組 合成一條指令，而在其它實施方式中，這兩條指令可被細分成執行與這些指令一致 的某些任務的其它指令。
此外，在本發明一實施方式中，數據段的無進位除以一多項式生成元("生成 元generator")是由將生成元的模2算術倒數乘以該數據段的指令(例如"無進位 乘法"或稱"CMUL"指令)來執行的。本公開中使用術語'模2算術倒數'來表 示以2為底的指數值與生成多項式的模2除法得到的商，其中以2為底的指數值的 冪等於生成多項式的次數與輸入數據片的長度之和。在本發明又一實施方式中，對 己與生成多項式的倒數相乘的輸入數據片進行反射。由此，在這種實施方式中，相 比於諸如使用基於表的CRC檢錯實現的一些現有技術CRC算法實現，執行無進位 除法必需的處理循環次數可得以減少。在某些實施方式中這可能成立，因為用戶層 面的軟體程序在生成將要隨數據段編碼的CRC時只能發放相對少量的指令(例如 在某些應用中為4條指令)，而不能執行許多其它操作，諸如移位運算、異或(XOR) 布爾運算、以及査表操作。在某些實施方式中，作為本發明的一部分提出的這些指 令取代了所有這些示例性的現有技術運算，而在其它實施方式中，該指令可只取代 這些運算的一個子集。在任一情形中，本發明的實施方式可在現有技術實現的某些 部分上改進CRC檢錯性能。
在本發明一實施方式中，對要在其上進行CRC檢錯的數據段執行位反射。在
其它實施方式中，位反射可能並不必要，且可在不執行位反射的情況下用其相應數 據段生成CRC並將其隨相應數據段編碼。在本發明的又一實施方式中，位反射可
在CRC初始值上執行。在執行位反射的本發明一實施方式中，位反射可在CRC生 成之前執行。在其它實施方式中，位反射可在CRC生成之後執行。例如，在一實 施方式中，位反射("BREF")指令可在執行無進位乘法(CMUL)指令之前執行。
要在其上進行CRC檢錯的的數據段可以是任意大小，這取決於特定應用中什 麼大小適當。為了本公開的目的，數據片輸入大小(以位數計)表示成、"，且生 成多項式的最大冪("次數")將被表示成""。將使用36位和64位數據段("片") 來說明示例。然而，應該理解，本發明的實施方式不限於32位和64位的片，而是 可包括大於或小於32位及64位的位的片。
CRC可通過計算無進位算術除法運算的餘數而生成，其中被除數是將被檢錯 的數據流或數據流的一部分("數據片")而除數是一生成多項式。然後，可將該餘 數編碼到另一數據流中，並從發送設備或系統傳送到接收設備或系統。可在接收器 處可進行相同操作來驗證該數據流或數據片(為本公開的目的，"數據流"和"數 據片"可進行互換引用)的完整性。
通常，在一實施方式中，CRC可通過執行以下操作來計算選擇可以取決於 應用的初始CRC值，在該初始CRC值與將在其上進行CRC檢錯的部分或整個(經 反射的或未經反射的)數據片之間執行異或布爾(XOR)運算，將CRC值從其當 前狀態更新到下一狀態，直到沒有其它數據片要用相應的CRC進行編碼或解碼。 在一實施方式中，CRC值可根據如下所述的操作和計算進行更新。
在一實施方式中，餘數值可根據下式生成formula see original document page 9
在上式中，"r"表示等於無進位除法運算的餘數的數字(由"t"位表示)，"S" 是等於要在其上進行CRC檢錯操作的數據片的值的數字(由"s"位表示)。S還 可以等於由等於S乘以2t+s的值表示的被除數的不全為零值的一組s個最高有效位 表示的值。同樣在上式中，"g"是表示生成多項式的數字(由"t+l"位表示)。在 本文描述的本發明實施方式的說明中，g通常比r多用一位來表示。在上式中，將 數據片S乘以一常數，即2的t與s之和次冪，其結果通過使用模2除法除以生成 元g。
可以看出，上式等價於下式，在下式中，上式的餘數是通過在數據片與多項
式生成元的倒數之間進行的無進位乘法運算而計算得到
rs位的片=Lt(g* x MS(S x q ))
在上式中，餘數r可通過生成元g的t個最低有效位(在式中由"g*"表示) 與數據片S和常數21+5模2算術除以生成元g的"s+1 "位商q+的模2算術乘積的 s個最高有效位(在式中由"Ms"表示)的模2算術乘積的t個最低有效位(在式 中由"Lt"表示)來計算。上式可應用於任意數目的數據片。例如，如果數據片S 是32位的，則餘數可通過下式計算
r32位的片=32!(g* x 32m(S x q+))
在上式中，"32m"表示S與q+的模-2算術乘積的32個最高有效位，其中q+ 是33位長(數據片長加一位)並表示常數2"除以生成元g的模-2算術商。在其 中數據片S為64位長的另一實施方式中，餘數r可通過下式計算
f64位的片=32!(g815 x 64m(S x q+》
在該式中，"64m"表示S與q+的模2算術乘積的64個最高有效位，其中q+ 是65位長(數據片長加一位)並表示常數2^除以生成元g的模2算術商。
類似地，對應於8位數據片的餘數s可通過下式計算
rs位的片=32!(g^ x 8m(S x q+))
在該式中，"8m"表示s與q+的模2算術乘積的8個最高有效位，其中q+是 33位長(數據片長加一位)並且表示常數2^除以生成元g的模2算術商。在本發 明的實施方式中，可以按不同次序執行各個運算以實現以上各式。圖2是示出根據 本發明一實施方式的無進位乘法指令的處理中涉及的運算的流程圖。
參考圖2， g+和q+在運算201中計算。如以上所討論的，gf表示生成元g的t 個最低有效位，而q+表示常數2t+s除以生成元g的s+l位模2算術商。數字q+可被 概念化為生成多項式的模2算術倒數。在運算205，將數據片S乘以q+。運算205 得到是s的位大小兩倍的數字，該數字的s個最高有效位在運算210中被與§*相乘。 運算210得到"t+s-l"位的數字，該數字的t個最低有效位就是所需的餘數r。
有利的是，從上述無進位乘法指令得到的餘數r可通過使用一系列布爾XOR 運算來實現，正如在無進位除法運算情形中一樣。因此，在一實施方式中，圖2 所示的執行以上各式的運算可簡化成一系列XOR和位移運算。這是因為無進位乘 法如同其名稱所暗示的一樣，並不包括因兩個具有多個位的操作數間各次乘法運算 而導致的進位。例如，在涉及各有2位的操作數，其中兩個操作數都由二進位值表 示，諸如11 x 11的乘法運算中，結果將是IOOI (二進位)。然而，在相同操作數 的無進位乘法中，結果應該是IOI，這可通過將操作數的經移位版本作XOR來得
到。無進位乘法的該有益特性使得本發明至少一個實施方式能夠相對快速地計算 CRC。此外，因為在一實施方式中，無進位乘法由被設計成由處理硬體或軟體執行
的指令執行，所以用戶軟體不需要進行本發明一實施方式中涉及的移位和XOR運
算。取而代之，這些運算可由該處理硬體或軟體進行處理。
為了進一步示出根據本發明一實施方式的無進位乘法，圖3示出將二進位數 據片11010與生成元的模2算術倒數011010無進位相乘所涉及的各種運算。首先， 對該數據片進行位反射以產生經反射的數據片01011。在一實施方式中，位反射通 過執行諸如以上討論並在下文進一步詳細描述的BREF指令的位反射指令得到。在 其它實施方式中，該數據片可不被位反射。然後，對經反射的數據片中除最低有效 位之外的所有位進行檢查(從右至左)以判定它們是"1"還是"0"。由於二進位 無進位乘法的特性，只需要執行與數據片各最高有效位(即，除最低有效位之外的 所有位)中1的個數相等次數的XOR和左移位運算就能生成CRC。
在圖3中，在從右至左檢査數據片時，包含"1"值的第一非最低有效位的位 置是比特位置一301。相應地，將生成元的模2算術倒數011010的經左移位版本 310與生成元的模2算術倒數011010的未移位版本305進行XOR。數據片中從右 至左包含"1"值的下一個比特位置是比特位置三303。相應地，將生成元倒數310 的經左移位版本315與生成元倒數310進行XOR，其結果320就是所需結果。
在一實施方式中，以上參照圖2和3討論的實施方式的CRC檢錯算法可通過 使用根據任何給定ISA設計成由一個處理器或多個處理器執行的兩條新指令來實 現。雖然在某些實施方式中，這些指令的操作可能取決於使用它們的特定ISA，但 是這些指令的功能可跨任何ISA應用。
在一實施方式中，使用位反射指令("BREF")來執行位交換功能，藉此在位 置"i"處的位與在位置處的位被交換，反之亦然，其中"1"是寄存器長 度，且i的範圍可從O至l-l。在特定處理硬體實現中，BREF指令可通過以下方式 工作
DEST <-BREF(DEST)
在上述操作中，BREF指令對寄存器或其它存儲結構("DEST")的內容執行 位反射操作，並將結果置於DEST中。在其它實施方式中，BREF指令可對除了 DEST之外的寄存器或其它存儲結構的內容進行操作。不管具體硬體實現如何， BREF指令都起到返回經位反射的值的作用。
在一實施方式中，無進位乘法指令("CMUL")對一值的經位反射版本或原
始值進行操作以產生可隨該值編碼的CRC、或其某一更改版本。此外CMUL指令 可對應於各種長度的數據片，諸如32位數據片和64位數據片。取決於執行指令的 處理資源的微架構，可使用一個或多個寄存器或其它存儲結構來存儲CMUL指令 的操作數和/或結果。例如，在一實施方式中，32位CMUL指令可執行以下運算〈-CMUL(EAX)
在以上運算中，CMUL對源操作數與存儲在32位寄存器或其它存儲結構 "EAX"中的操作數執行無進位乘法運算，並將64位結果置於諸如通用寄存器等 的32位存儲結構"EDX"和EAX。在其它實施方式中，CMUL可對存儲在除EAX 之外的另一結構中的操作數進行運算。類似地，CMUL可通過對源操作數與存儲 在兩個32位存儲結構或一個64位存儲結構中的操作數執行運算並將128位結果存 儲在兩個64位寄存器或其它存儲結構內來對存儲在64位寄存器或其它存儲結構中 的兩個操作數執行運算。
在一實施方式中，由BREF和CMUL指令支持的以上各個運算在諸如微處理 器的半導體器件內的硬體邏輯中實現。在其它實施方式中，以上運算可通過使用軟 件而由BREF和CMUL指令支持，而在其它實施方式中，以上參考BREF和CMUL 描述的運算可通過使用硬體邏輯和軟體的某種組合來實現。為了說明對於32位數 據片操作數如何實現BREF和CMUL的至少一個示例，以下是根據本發明一實施 方式的在特定硬體配置中如何實現BREF和CMUL的討論。在其它實施方式中， 也可使用其它硬體配置來實現BREF和CMUL。
指令BREF反射給定寄存器或其它存儲結構的位，並且在一實施方式中，可 通過將各個存儲結構條目適當"連線"到相應反射條目來實現。在一實施方式中， 反射可在單個處理器時鐘周期內發生。在一實施方式中，指令CMUL在源操作數 與32位寄存器(例如"EAX")或64位寄存器(例如"RAX")之間執行無進位 (即，"多項式")乘法。結果是64位或128位數字，其中32 (或64)個最高有效 位被存儲在諸如"EDX"的32位寄存器(或諸如"RDX"的64位寄存器)中， 且32 (或64)個最低有效位存儲在寄存器EAX (或RAX)中。
描述輸入^和B與輸出C和D的位之間關係的邏輯函數可從無進位乘法運算 的規範中導出。
以下描述根據一實施方式的32位無進位乘法器的特定硬體實現 在一實施方式中，寄存器EAX存儲對應於32位數據片的初始數字A
爿=[a31a30...a0]
假設一包含生成元的源操作數
5 = [631630...60]
乘法運算的結果可表示成 = [d3lK c3,c30…c。]
位a。是^的最低有效位。類似地，6。是萬的最低有效位，c。是C的最低有效
位，^是D的最低有效位。在一實施方式中，數字D在此乘法完成之後在寄存器
EDX中找到，而數字C在此乘法完成之後在寄存器EAX中找到。
c0 = a060
c3l = a。631 fl々3。十…十a3160
以及
^ = o
d。 = a3A十<33062十...十a,63i
d[31:0]和c[31:0]的等式也可寫成:
以及:
c,.=十a力,一,. 」=o 7 , 乂
31
《= ，"A+,"
以下描述其中執行64位無進位乘法的一實施方式
在一實施方式中，寄存器RAX存儲對應於64位數據片的初始數字」
假設一包含生成元的源操作數
乘法運算的結果可表示成=[《3《2. 乂 c63c62…c0 ]
位"。是^的最低有效位。類似地，^是B的最低有效位，c。是C的最低有效 位，^是D的最低有效位。在一實施方式中，數D在此乘法完成之後在寄存器RDX 中找到，而數C可在乘法完成之後在寄存器RAX中找到。C0 = a0Z)0
C63 = 。A3 #62 … "6360
以及
《2 = a6A3
<i。 = a6262十...十
d[63:0]和c[63:0]的等式也可寫成
c, = a力，， /=o J '力
以及
63
可以看出，以上&和di的等式的邏輯函數的每一個可通過使用XOR樹在諸如 互補金屬氧化物半導體(CMOS)邏輯的硬體中實現。在32位示例中，"最深"的 XOR樹(包含最多次XOR運算)是用於實現函數C3,的那一個，它採用了32個輸 入。根據一實施方式，在32位示例中，實現CMUL的全部XOR樹可能用到的XOR 門總數由此等於1+2+...+30+31+30+29+...+1 =961，且在這一實施方式中可能用到 的AND門的總數是1+2+...+32+31+.= 1024。因此，根據一實施方式，實現 CMUL可能用到的門的總數為1985。
在64位示例中，根據一實施方式，實現CMUL指令的全部XOR樹可能用到 的XOR門總數等於1+2+...+62+63+62+61+...+1 = 3969。此外，在這一實施方式中 可能用到的AND門的總數是1+2+...+64+63+...1 =4096。因此，根據一實施方式， 實現CMUL指令可能用到的門總數為8065。
如上所述，上述各式中的一個或多個可在軟體中實現。"軟體"可包括一條或 多條機器可讀指令，這些指令在由機器執行時使該機器執行運算以實施本發明至少 一個實施方式。
圖4示出可使用一實施方式的點對點(PtP)計算機系統。特別地，圖4示出 其中處理器、存儲器、和輸入/輸出設備由多個點對點接口互連的系統。
圖4的系統還包括若干處理器，為清楚起見僅示出了其中兩個處理器470、 480。處理器470、 480可各自包括一本地存儲器控制器集線器(MCH) 472、 482 來與存儲器22、 24連接。處理器470、 480可通過使用PtP接口電路478、 488經 由點對點(ptp)接口 450來交換數據。處理器470、 480可通過使用點對點接口電 路476、 494、 486、 498經由各個PtP接口 452、 454各自與晶片組490交換數據。 晶片組490也可經由高性能圖形接口 439與高性能圖形電路438交換數據。
本發明至少一個實施方式可位於圖4的各個PtP總線代理內的處理核心中。 然而，本發明的其它實施方式可存在於圖4系統內的其它電路、邏輯單元或裝置中。 此外，本發明的其它實施方式可分布在圖4所示的若干電路、邏輯單元或裝置中。
圖5示出可使用本發明一實施方式的前端總線(FSB)計算機系統。處理器 505從一級(Ll)高速緩存510和主存儲器515存取數據。在本發明其它實施方式 中，高速緩存可以是計算機系統存儲器分層結構內的二級(L2)高速緩存或其它 存儲器。此外，在某些實施方式中，圖5的計算機系統包括Ll高速緩存和L2高 速緩存兩者，它們構成了在Ll與L2高速緩存之間共享一致性數據的包含式高速 緩存分層結構。在其它實施方式中，可存在一個以上的高速緩存分層結構。
在圖5的處理器內示出的是本發明一實施方式506。然而，本發明其它實施方 式可在該系統內諸如圖形控制器的其它裝置內實現，或者分布在系統內硬體、軟體 及其某種組合中。
主存儲器可以在各種存儲器源中實現，諸如動態隨機存取存儲器(DRAM)、 硬碟驅動器(HDD) 520、或通過網絡接口 530位於計算機系統遠程的包括各種存 儲設備和技術的存儲器源。高速緩存可位於處理器內或處理器附近，諸如在處理器 的局域總線507上。此外，高速緩存可包含諸如六電晶體(6T)單元的相對快速 的存儲單元或者存取速度大致相等或更快的其它存儲單元。
圖5的計算機系統可以是可經由專用於PtP網絡上各個代理的總線信號通信 的諸如微處理器的總線代理的點對點(PtP)網絡。本發明的至少一個實施方式在 各個總線代理內或至少與其相關聯，使得存儲操作可在總線代理之間以迅捷方式進 行。
在以上說明書中，參照其具體實施方式
對本發明進行描述。然而，顯而易見 的是可作出各種更改和變化而不背離本發明的較寬泛的精神和範圍。因此，說明書 和附圖應被視為說明而非限制。
權利要求
1.一種方法，包括對具有第一位數的第一二進位操作數與具有第二位數的第二二進位操作數執行第一無進位乘法運算；存儲所述第一無進位乘法運算的結果的多個最高有效位，所述最高有效位的個數等於所述第一位數。
2. 如權利要求1所述的方法，還包括對所述第一二進位操作數執行位反射運算。
3. 如權利要求1所述的方法，其特徵在於，所述第二二進位操作數是多項式 生成元的模-2算術倒數值。
4. 如權利要求1所述的方法，還包括在所述結果的所述多個最高有效位與一 循環冗餘碼(CRC)生成多項式中除所述CRC生成多項式的最高有效位之外的所 有位之間執行第二無進位乘法運算。
5. 如權利要求4所述的方法，還包括存儲所述第二無進位乘法運算的結果的 多個最低有效位，所述最低有效位的個數比所述CRC生成元多項式的位數少一。
6. 如權利要求5所述的方法，其特徵在於，所述第一二進位操作數是第一循 環冗餘碼(CRC)與一數據片的第一部分之間的布爾異或(XOR)運算的結果， 並且其中所述第二無進位乘法的結果構成第二 CRC。
7. 如權利要求6所述的方法，還包括在所述第二 CRC與一輸出值之間執行 XOR運算以生成要隨所述數據片的所述第一部分一起從發送器向接收器傳送的第 三CRC。
8. 如權利要求7所述的方法，其特徵在於，在所述無進位乘法運算之前執行位反射操作。
9. 一種其上存儲有指令集的機器可讀介質，所述指令集在由機器執行的情況下使所述機器執行一種方法，所述方法包括對具有第一位數的第一二進位操作數與具有第二位數的第二二進位操作數執行第一無進位乘法運算；存儲所述第一無進位乘法運算的結果的多個最高有效位，所述最高有效位的 個數等於所述第一位數。
10. 如權利要求9所述的機器可讀介質，其特徵在於，所述方法還包括對所述 第一二進位操作數執行位反射操作。
11. 如權利要求IO所述的機器可讀介質，其特徵在於，所述第二二進位操作數是一多項式生成元的模2算術倒數值。
12. 如權利要求11所述的機器可讀介質，其特徵在於，所述方法還包括在所述結果的所述多個最高有效位與一第三二進位操作數中除了所述第三二進位操作 數的最高有效位之外的所有位之間執行第二無進位乘法運算。
13. 如權利要求12所述的機器可讀介質，其特徵在於，所述方法還包括存儲 所述第二無進位乘法運算的結果的多個最低有效位，所述最低有效位的個數比所述 第三二進位操作數的位數少一。
14. 如權利要求13所述的機器可讀介質，其特徵在於，所述第一無進位乘法 運算僅通過執行單條指令來實現。
15. 如權利要求IO所述的機器可讀介質，其特徵在於，所述位反射操作僅通 過執行單條指令來實現。
16. 如權利要求12所述的機器可讀介質，其特徵在於，所述第二無進位乘法 運算僅通過執行單條指令來實現。
17. —種設備，包括第一邏輯，用於對具有第一位數的第一二進位操作數與具有第二位數的第二 二進位操作數執行第一無進位乘法運算；第一存儲單元，用於存儲所述第一無進位乘法運算的結果的多個最高有效位，所述最高有效位的個數等於所述第一位數。
18. 如權利要求17所述的設備，還包括用於對所述第一二進位操作數執行位 反射操作的第三邏輯。
19. 如權利要求17所述的設備，其特徵在於，所述第二二進位操作數是一多 項式生成元的模2算術倒數值。
20. 如權利要求17所述的設備，還包括第二邏輯，用於在所述結果的所述多 個最高有效位與一第三二進位操作數中除了所述第三二進位操作數的最高有效位 之外的所有位之間執行第二無進位乘法運算。
21. 如權利要求20所述的設備，還包括用於存儲所述第二無進位乘法運算的 結果的多個最低有效位的第二存儲單元，所述最低有效位的個數比所述第三二進位 操作數的位數少一。
22. 如權利要求21所述的設備，其特徵在於，所述第一二進位操作數是第一 循環冗餘碼(CRC)與一數據片的第一部分之間的布爾異或(XOR)運算的結果， 並且其中所述第二無進位乘法的結果構成第二 CRC。
23. 如權利要求23所述的設備，還包括XOR裝置，用於在所述第二CRC與 一輸出值之間執行XOR運算以生成要隨所述數據片的所述第一部分一起從發送器 向接收器傳送的第三CRC。
24. 如權利要求23所述的設備，還包括用於發送所述第三循環冗餘碼和所述 數據片的所述第一部分的發送器。
25. 如權利要求23所述的設備，還包括用於接收所述第三循環冗餘碼和所述 數據片的所述第一部分的接收器。
26. —種系統，包括處理器，用於執行指令以對具有第一位數的第一二進位操作數與具有第二位 數的第二二進位操作數執行第一無進位乘法運算；存儲器，用於存儲所述第一無進位乘法運算的結果的多個最高有效位，所述 最高有效位的個數等於所述第一位數。
27. 如權利要求26所述的系統，其特徵在於，所述處理器被包含在發送設備內。
28. 如權利要求26所述的系統，其特徵在於，所述處理器被包含在接收設備內。
29. 如權利要求26所述的系統，其特徵在於，所述處理器包括用於在所述結 果的所述多個最高有效位與一第三二進位操作數中除了所述第三二進位操作數的 最高有效位之外的所有位之間執行第二無進位乘法運算的第二邏輯。
30. 如權利要求29所述的系統，其特徵在於，所述存儲器用於存儲所述第二 無進位乘法運算的結果的多個最低有效位，所述最低有效位的個數比所述第三操作 數的位數少一。
全文摘要
一種執行無進位乘法和位反射運算的技術。更具體地，本發明的實施方式包括一種執行循環冗餘碼(CRC)生成的技術。
文檔編號H03M13/09GK101185245SQ200680018423
公開日2008年5月21日 申請日期2006年5月25日 優先權日2005年5月25日
發明者M·科納維斯 申請人:英特爾公司