一種循環冗餘校驗的快速計算方法
2023-05-16 21:33:21
專利名稱：一種循環冗餘校驗的快速計算方法
技術領域：
本發明涉及循環冗餘校驗技術，特別是指一種循環冗餘校驗的快速計算方法。
背景技術：
隨著技術的不斷進步，各種數據通信的應用越來越廣泛，由於傳輸距離、現場狀況、幹擾等諸多因素的影響，設備之間的通信數據常會發生一些無法預測的錯誤。為了降低錯誤所帶來的影響，一般在通信時採用數據校驗的方法，循環冗餘碼校驗(CRC)就是常用的重要校驗方法之一。
CRC校驗為數據傳輸提供了一種簡單而有效的突發差錯檢測方法，可適用於很多方面。CRC校驗採用多項式編碼方法，被處理的數據塊可以看作是一個n階的二進位多項式。比如假定待發送的二進位數據段為g(x)，生成多項式為m(x)，則得到的CRC校驗碼為c(x)，具體說就是，CRC校驗碼的編碼方法是用待發送的二進位數據g(x)除以生成多項式m(x)，將最後的餘數作為CRC校驗碼。該CRC編碼既可以通過軟體實現，也可以通過硬體實現；既可以用結構簡單，但處理時延較大的串行方法構造；也可以用結構複雜，但是處理時延較小的並行方法構造。
目前，CRC編碼技術已經較為成熟，主要採用的實現方案有以下三種第一種是基本的比特級構造方法，也可以稱作直接計算法，這是最簡單的CRC計算方法，是通過硬體實現的，如圖1所示，該方法在硬體上主要通過線性反饋移位寄存器(LFSR)來實現。移位寄存器由時鐘驅動，每個時鐘輸入數據移位寄存器參與計算，同時也直接輸出；當所有的輸入比特都處理完成之後，移位寄存器中剩下的就是CRC比特，將該CRC比特依次移出到數據流上，就完成了CRC編碼。在實際應用中，可採用以下算法具體實現a1.定義一個寄存器R用來存放循環冗餘校驗碼，寄存器的長度一般為處理器的基本存儲單元的整數倍，比如8比特、16比特、32比特等等，並且將寄存器R的值置為0；a2.如果寄存器R最左邊的比特等於1，則將下一個消息比特移入，並且將寄存器R和生成多項式進行異或；否則只將消息比特移入即可；a3.重複步驟a2，直到所有消息比特都被移入處理，留在寄存器R中的就是輸入序列的循環冗餘校驗碼。
這種方法所用的模塊代碼少，不需要存儲查找表，計算簡單，修改靈活，可移植性好，軟硬體實現的複雜度差不多，對任意長度生成多項式m(x)都適用。但如果發送的數據塊很長，該方法就不太適合，因為該方法需要逐比特處理，也就是一次只能處理一位數據，效率太低，運算量大，不能滿足實時處理的要求，對於高速數據通信更不適用。
第二種是標準查找表算法，該方法的CRC計算可認為是輸入比特和移位寄存器狀態比特構成的多項式對生成多項式的餘數，該方法需要預先提供CRC生成表。假定寄存器的寬度為n，輸入比特位數為m，則在實際應用中，當m＜n時，可採取下面的操作步驟b1.定義一個寬度為n比特的寄存器R用來存放循環冗餘校驗碼，寄存器的長度一般為處理器的基本存儲單元的整數倍，比如8比特、16比特、32比特等等，並且將寄存器R的值置為0，即設置(rn-1，...，r0)比特序列為0；b2.將寄存器R右移n-m比特，即得到(Rn-1，...，rn-k-r)序列，然後所得到的序列和m個輸入比特異或；b3.在查找表中找到對應的值，與寄存器R左移m比特得到的序列(rm-1，...，r0)異或，就得到新的CRC值；b4.重複步驟b2和b3，直到所有消息比特都被移入處理，留在寄存器R中的就是輸入序列的循環冗餘校驗碼。
當n＝m時，步驟b2和步驟b3會有些許改變b2』.將輸入的m個比特與寄存器R異或，也就是將輸入的m比特與(rn-k-1，...，r0)異或；b3』.在查找表裡面找到對應的值，就得到新的CRC值。
當n＜m時，不能採取這種算法。
這種算法需要提供存儲2m×n比特大小的查找表，每處理m比特需要執行一次查表和兩次異或操作，軟硬體實現時複雜度和性能差不多。與直接計算法相反，該方法運算量小，速度快，但是可移植性較差，且應用有局限性，不能處理m＞n時的情況，也就是說，每次處理的比特數m不能大於生成多項式的最高階數n，否則就不能應用該算法。
此外，所存儲的查找表隨著m的增加而成2的指數增加，比如每次處理8個比特時，查找表大小為256個存儲單元；每次處理16個比特時，查找表大小就變為65536個存儲單元，可見，這種方法的並行度不能過高。
第三種是並行循環冗餘校驗編碼方法，如圖2所示，這是一種基於線性反饋移位寄存器的並行結構，圖2中，d0～dm-1表示並行輸入序列的m個比特位，er，c為矩陣Fw的第r行第c列，x0～xm-1為輸出的系統狀態列向量，其中w為並行輸入級數。該方法實際是通過硬體門電路來構建當前CRCn生成多項式所對應的各個寄存器之間的關係，最終獲取CRC值。
不難看出，該方法的速度是常規方法的w倍，代價就是存儲一個F16矩陣並增加硬體的複雜度。該方法的並行度很高，適合硬體如採用FPGA實現，但該算法並不適合軟體比如用DSP晶片實現。原因很簡單，圖2所示的並行結構並行度為m，一般的處理器都達不到這麼高的並行度。
隨著第三代移動通信中高速數據業務的發展，CRC校驗也在第三代移動通信的數據傳輸中得以大量應用。但由於3GPP基帶處理的時延要求相當嚴格，基帶處理器的性能與單位時間內的業務處理能力緊密相關，這樣，CRC編碼的效率好壞，就會直接影響到基帶處理器的性能。如果沒有合適的快速CRC校驗的計算方法，將會使高速數據通信中的業務處理能力受到很大影響。
發明內容
有鑑於此，本發明的主要目的在於提供一種循環冗餘校驗的快速計算方法，能大大提高CRC校驗的處理速度，降低CRC校驗的處理時延，進而一定程度地提高業務處理能力。
本發明進一步的目的是一種循環冗餘校驗的快速計算方法，使其在保證快速計算速度的同時，達到最佳的存儲量/時延配置。
為達到上述目的，本發明的技術方案是這樣實現的一種循環冗餘校驗的快速計算方法，該方法包括以下步驟a.根據當前所採用CRCn生成器的邏輯結構，獲取並存儲該生成器中每個移位寄存器在處理每個輸入比特時的狀態；b.從步驟a所獲取的所有移位寄存器的全部狀態中，提取出處理完輸入序列每個比特後CRCn生成器中每個移位寄存器的狀態；並將所提取出的每個移位寄存器狀態組成中的移位寄存器初始狀態表示部分和輸入序列表示部分分別存儲；c.以每個分別存儲部分包含的自變量為地址索引，生成該存儲部分對應的查找表；d.以CRCn模式進行CRC校驗時，判斷當前需處理的比特數是否大於每次能處理的比特數m，如果不是，則按串行方式處理；如果是，則讀取m比特，分別以輸入比特和移位寄存器變量為地址索引，查找輸入序列表示部分對應的查找表和移位寄存器初始狀態表示部分對應的查找表，然後將所有查找結果進行異或並保存異或結果；將對應每個移位寄存器的異或結果分別作為該移位寄存器的當前狀態，返回步驟d。
其中，步驟c和步驟d之間進一步包括判斷分別存儲的移位寄存器初始狀態表示部分或輸入序列表示部分是否需要繼續細分，如果需要，則按給定條件將當前的存儲部分進一步劃分為一個以上存儲部分，並對劃分後的每個存儲部分分別生成對應的查找表；否則，直接執行步驟d。
該方法進一步包括預先設置需要進行細分的條件，則所述判斷是否需要細分為判斷是否符合細分條件，如果符合，則需要細分；否則不需要細分。這裡，所述進行細分的條件為步驟b中所劃分的分別存儲部分的存儲量大於給定存儲量。
如果將當前存儲部分進一步劃分為一個以上存儲部分，則步驟d中所述查找輸入序列表示部分對應的查找表和移位寄存器初始狀態表示部分對應的查找表是分別查找至少一個輸入序列表示部分對應的查找表和一個以上移位寄存器初始狀態表示部分對應的查找表。
上述方案中，可將每個存儲部分的內容分別存儲在表中。另外，CRCn生成器中每個移位寄存器的初始狀態存儲在寄存器中，或放置在向量中。
本發明所提供的循環冗餘校驗的快速計算方法，由於根據當前所採用CRCn生成多項式對應的邏輯結構，預先得出在不同輸入比特的處理狀態下，CRCn所用到的每個寄存器的當前狀態與其他寄存器及輸入比特位的關係，生成對應的查找表，使得在進行CRC校驗時，可直接根據預先生成的查找表計算出每個寄存器當前狀態下的輸出，從而大大提高了CRC校驗的處理速度，也就是降低了CRC校驗的處理時延。
本發明的方法對所得到的關係按寄存器值和輸入比特位值進行劃分，並可根據需要或根據算法複雜度的情況，對已劃分的寄存器部分或輸入比特位部分再細分，如此，可不同程度的減小存儲量，以較小的存儲代價，換取了很大的處理時延。並且，本發明方法具有相當的靈活性，在保證計算速度快的前提下，可隨時根據具體條件，確定最佳的存儲量/計算時間配置，能實現很高的並行度。
圖1為一種LFSR的組成結構示意圖；圖2為並行CRC體系結構示意圖；圖3為本發明方法的實現流程圖；
圖4為本發明一實施例的邏輯結構示意圖；圖5為圖4所述實施例的CRC計算過程示意圖。
具體實施例方式
本發明的基本思想就是根據當前所採用CRCn生成多項式對應的邏輯結構，預先得出在不同輸入比特的處理狀態下，CRCn所用到的每個移位寄存器的狀態更新情況與其它移位寄存器和輸入比特位之間的關係，並根據該關係生成對應的查找表；在進行CRCn校驗時，直接利用預先生成的查找表獲取每個移位寄存器當前狀態下的輸出。
如圖3所示，本發明方法的具體實現過程包括以下步驟步驟301根據當前所採用CRCn生成器的邏輯結構，獲取並存儲該生成器中所涉及的每個移位寄存器在處理每個輸入比特時的狀態。
步驟302從步驟301所獲取的所有移位寄存器的全部狀態中，提取出處理完輸入序列每個比特後CRCn生成器的每個移位寄存器的狀態。
步驟303～304將步驟302所提取出的每個移位寄存器狀態組成中的移位寄存器初始狀態表示部分和輸入序列表示部分分別存儲；並以每個分別存儲部分包含的自變量為地址索引，生成該存儲部分對應的查找表。
步驟305～306在以CRCn模式進行CRC校驗時，先判斷當前需處理的比特數是否大於每次能處理的比特數m，如果不是，則按現有技術中一般的串行方法處理；如果是，則執行步驟307。
步驟307～310讀取m比特的信息，分別以輸入比特和移位寄存器變量為地址索引，查找輸入序列表示部分對應的查找表和移位寄存器初始狀態表示部分對應的查找表，並將所有查找結果進行異或，保存異或結果；並且，將對應每個移位寄存器的異或結果分別作為該移位寄存器的當前狀態，然後返回步驟305。
在步驟304和步驟305之間還可以增加一個判斷，判斷分別存儲的移位寄存器初始狀態表示部分或輸入序列表示部分是否還需繼續細分，如果需要，則按給定條件將當前的存儲部分進一步劃分為一個以上存儲部分，並對劃分後的每個存儲部分分別生成對應的查找表。可預先設置細分條件，比如查找表的存儲量大於某個給定值就再細分，那麼，細分時就按照存儲量給定值來決定如何細分，具體說就是，當前存儲部分的查找表存儲量為64K，而給定值為32K，那麼，就會將當前存儲部分再進一步劃分為兩個存儲部分。如果進行了細分，則步驟308、或步驟309、或步驟308和步驟309要分別以每個存儲部分所含的自變量為地址索引，查找相應的查找表，再將所有查找結果進行異或。
對於上述每個步驟提到的存儲，都可以設置一個表進行存儲，如果某兩個表是從某個表中劃分出來的，則這兩個表可稱為原表的子表。
為了方便進一步詳細說明本發明中CRC的快速計算原理，下面以CRC16為例，同時結合CRC16的生成多項式和邏輯結構圖作為參考。
CRC16所採用的查找表的生成過程包括以下幾個步驟第一步，根據CRC16生成器的邏輯結構獲取每個移位寄存器在處理每個輸入比特時的狀態。
CRC16的生成多項式如公式(1)所示gcrc16(D)＝D16+D12+D5+1(1)CRC16的邏輯結構如圖4所示，CRC16的生成器包括16個移位寄存器R1～R16，圖4中的表示模2加，也就是異或。假設以R1～R16分別代表這16個移位寄存器的初始狀態，並且當前的輸入序列為M，Mi代表輸入序列的第i比特位，本實施例中，輸入序列M由8個比特位組成，即M1～M8。那麼，可以根據圖4得出每次處理一個輸入比特時每個移位寄存器的狀態更新情況，其中移位寄存器的所有狀態都是由初始狀態R1～R16和輸入序列M表示的。每個移位寄存器每個時刻的狀態具體如表一所示
表一表一中，第一列代表16個移位寄存器，第一行代表處理的輸入比特Mi，相應的，第二列為處理第一輸入比特M1時16個移位寄存器的當前狀態；第二列為處理第二輸入比特M2時16個移位寄存器的當前狀態，以此類推，表中的「+」表示模2加。
上述表一的具體生成方法包括以下過程首先，將圖4中16個移位寄存器的初始狀態存放在表一的第一列；然後，對於每個輸入比特執行根據當前輸入比特，用前一時刻的移位寄存器狀態和當前輸入表示出當前時刻移位寄存器的狀態，直至處理完8個比特。比如移位寄存器R1的當前狀態應該等於移位寄存器R16的當前狀態與輸入序列M的異或，而移位寄存器R2的當前狀態就等於移位寄存器R1的當前狀態；再比如根據圖4移位寄存器R6的當前狀態就等於移位寄存器R5的當前狀態與移位寄存器R16當前狀態和輸入序列M異或結果再異或，CRC16生成器中的移位寄存器狀態均以此類推。
第二步，提取處理完輸入序列每個比特後CRC16生成器的每個移位寄存器的狀態。
表一生成後，可根據表一的最後一列獲得每個移位寄存器處理完8個輸入比特後的狀態，分別用R』1～R』16來表示，則得到表二，表二為處理完輸入序列每個比特後移位寄存器的狀態列表
表二第三步，對所獲得的處理完輸入序列所有比特後每個移位寄存器的狀態細成進行劃分，並構造相應的查找表。
為了減少存儲量和簡化構造查找表的複雜度，將表二按照移位寄存器初始狀態R1～R16和輸入比特序列M1～M8分成兩個子表，表三為處理完輸入序列後每個移位寄存器狀態與其它移位寄存器初始狀態相關的部分，表四為處理完輸入序列後每個移位寄存器狀態與輸入比特序列相關的部分。
表三
表四這裡，所述構造相應的查找表就是根據表三或表四中所有自變量的不同取值，計算出對應的R』1～R』16值。以表四為例，表四中的自變量為M1～M8，由於M1～M8每個比特位均可取0或取1，所以M1～M8的取值共有256種不同組合。那麼，構造查找表的具體過程是先列出M1～M8的256種取值；再根據表四中R』1～R』16與M1～M8的關係，計算出M1～M8每種不同取值所對應的R』1～R』16的值；以M1～M8為地址索引，將所有的R』1～R』16值都存儲到寄存器中，每個字節的地址尋址一個字；最後形成的關於R』1～R』16的256種取值就是所需的查找表。比如M1～M8的取值為01111010時，由於R』1為M4+M8，這裡M4＝1，M8＝0，則計算出R』1的取值為1；同樣R』2為M3+M7，這裡M3＝1，M7＝1，則計算出R』2的取值為0；其它R』i(i＝3，4...16)的計算方法類似，不再贅述。如果用於處理的DSP晶片是以字為存儲單元的話，就不需要特殊的處理；如果是以字節為存儲單元的話，就需要對8比特寬度的M地址索引進行2倍的擴展。
表三中的自變量是R1～R16，總共有216種組合。如果直接以R1～R16為地址索引，將對應的R』1～R』16存儲到存儲器中，存儲量就是64K字。對於64K字的存儲量，可以直接採用；也可以繼續將表三進行劃分，以減少存儲量。如果需要繼續劃分表三，則執行第四步。
第四步，進一步細化處理完輸入序列後每個移位寄存器狀態與其它移位寄存器初始狀態相關的部分，也就是將表三進一步劃分為兩個子表，並構造每個子表相應的查找表。
將表三中的自變量R1～R16分成R1～R8和R9～R16兩組，相應的，將表三分為與兩組自變量對應的兩個子表表五和表六。通常情況下，表五以自變量R1～R8作為地址索引，將相應的R』1～R』16值存儲到存儲器中，形成查找表；表六以自變量R9～R16作為地址索引，將相應的R』1～R16值存儲到存儲器中，形成查找表。
表五
表六在實際操作中，如果輸入序列M的比特數為16、32等，同樣可以將處理完輸入序列後每個移位寄存器狀態與輸入比特序列相關的部分按上述類似的方法劃分，即可將表四進一步劃分為兩個子表，並構造每個子表相應的查找表。這裡，形成查找表的過程與第三步中所述構造查找表的過程相同。
經過以上四個步驟，本實施例中所需的查找表就構造完成了。實際上，在本實施例中，表五可以不構造查找表，只要將地址索引R1～R8進行算術移位，即可獲得對應的R』1～R』16。
基於上面所構造的查找表，以CRC16進行校驗時，CRC的計算過程如圖5所示包括以下步驟步驟501判斷當前需要處理的比特數是否小於每次能處理的比特數m，本實施例中m值取8，那麼，如果剩餘比特大於8，則執行步驟504；否則，執行步驟502。
步驟502～503按照一般的串行輸入方法對剩餘比特進行CRC計算處理，並讀出移位寄存器中的值，結束當前CRC計算流程。
步驟504將圖4所示的移位寄存器初始狀態存儲到一個16比特長的存儲單元R中。這裡，如果採用DSP實現，可存儲到一個寄存器中；如果採用FPGA實現，可存儲在一個16比特的向量中。
步驟505～506從待處理的比特流中取出m個比特存儲到存儲單元M中，其中m常取8、16等值，本實施例中取m＝8。以M1～M8為地址索引查找表四生成的查找表，獲取對應的R』1～R』16，分別存儲於第i個16比特存儲單元Ti中。如果M表被劃分為多個子表，比如M取16、32等值時，查找每個子表對應的查找表，並將獲取的R』1～R』16進行模2加後分別存儲於存儲單元Ti中。
步驟507以R1～R8為地址索引進行算術移位運算，將獲取的R』1～R』16構成的字或向量與對應的存儲單元Ti中的值進行模2加，結果再存儲到對應的存儲單元Ti中；再以R9～R16為地址索引，查找表六對應的查找表，將獲取的R』1～R』16構成的字或向量與對應的存儲單元Ti中的值進行模2加，結果存儲至對應的存儲單元Ti中。
如果存在更多的子表，比如CRC24、CRC32時，初始狀態有24、32比特寬，這些情況下，查找所有子表對應的查找表，每次將當前所獲取的表項與對應的存儲單元Ti中的值進行模2加，再存儲到對應的Ti中。
步驟508將存儲單元T1～T16的值存入R1～R16中，作為處理完m個比特後移位寄存器Ri的狀態，並作為下一階段CRC計算移位寄存器Ri的初始狀態，返回步驟501。
按照本發明方法進行CRC計算，在性能上，如果有T個子表，則需要進行T次查表操作和T-1次異或操作，可以在複雜度不增加的情況下加快CRC計算速度。在存儲開銷方面，在保證性能不變甚至提高的情況下，可明顯降低存儲開銷。以3GPP中常用的8位、12位、16位和24位CRC模式為例，當m＝8，即每次處理8個輸入比特時，每個子表大小都為256，單位由CRC長度決定。具體存儲開銷如表七所示
表七以上所述，僅為本發明的較佳實施例而已，並非用於限定本發明的保護範圍。
權利要求
1.一種循環冗餘校驗的快速計算方法，其特徵在於，該方法包括以下步驟a.根據當前所採用CRCn生成器的邏輯結構，獲取並存儲該生成器中每個移位寄存器在處理每個輸入比特時的狀態；b.從步驟a所獲取的所有移位寄存器的全部狀態中，提取出處理完輸入序列每個比特後CRCn生成器中每個移位寄存器的狀態；並將所提取出的每個移位寄存器狀態組成中的移位寄存器初始狀態表示部分和輸入序列表示部分分別存儲；c.以每個分別存儲部分包含的自變量為地址索引，生成該存儲部分對應的查找表；d.以CRCn模式進行CRC校驗時，判斷當前需處理的比特數是否大於每次能處理的比特數m，如果不是，則按串行方式處理；如果是，則讀取m比特，分別以輸入比特和移位寄存器變量為地址索引，查找輸入序列表示部分對應的查找表和移位寄存器初始狀態表示部分對應的查找表，然後將所有查找結果進行異或並保存異或結果；將對應每個移位寄存器的異或結果分別作為該移位寄存器的當前狀態，返回步驟d。
2.根據權利要求1所述的方法，其特徵在於，步驟c和步驟d之間進一步包括判斷分別存儲的移位寄存器初始狀態表示部分或輸入序列表示部分是否需要繼續細分，如果需要，則按給定條件將當前的存儲部分進一步劃分為一個以上存儲部分，並對劃分後的每個存儲部分分別生成對應的查找表；否則，直接執行步驟d。
3.根據權利要求2所述的方法，其特徵在於，該方法進一步包括預先設置需要進行細分的條件，則所述判斷是否需要細分為判斷是否符合細分條件，如果符合，則需要細分；否則不需要細分。
4.根據權利要求3所述的方法，其特徵在於，所述進行細分的條件為步驟b中所劃分的分別存儲部分的存儲量大於給定存儲量。
5.根據權利要求2所述的方法，其特徵在於，如果將當前存儲部分進一步劃分為一個以上存儲部分，則步驟d中所述查找輸入序列表示部分對應的查找表和移位寄存器初始狀態表示部分對應的查找表是分別查找至少一個輸入序列表示部分對應的查找表和一個以上移位寄存器初始狀態表示部分對應的查找表。
6.根據權利要求1所述的方法，其特徵在於，將每個存儲部分的內容分別存儲在表中。
7.根據權利要求1所述的方法，其特徵在於，CRCn生成器中每個移位寄存器的初始狀態存儲在寄存器中，或放置在向量中。
全文摘要
本發明公開了一種循環冗餘校驗的快速計算方法，根據當前所採用CRCn生成多項式對應的邏輯結構，預先得出在不同輸入比特的處理狀態下，CRCn所用到的每個移位寄存器的狀態更新情況與其它移位寄存器和輸入比特位之間的關係，並根據該關係生成對應的查找表；在進行CRCn校驗時，直接利用預先生成的查找表獲取每個移位寄存器當前狀態下的輸出。該方法能大大提高CRC校驗的處理速度，降低CRC校驗的處理時延，進而一定程度地提高業務處理能力，並且，該方法在保證快速計算速度的同時，能達到最佳的存儲量/時延配置。
文檔編號H03M13/09GK1633030SQ20031012244
公開日2005年6月29日 申請日期2003年12月22日 優先權日2003年12月22日
發明者趙訓威, 王剛強 申請人:普天信息技術研究院