[發(fā)明專利]一種并行LFSR架構(gòu)的實現(xiàn)方法

有效

• 申請?zhí)枺?/td>: 201610080848.9
• 申請日: 2016-02-05
• 公開（公告）號: CN105680870B
• 公開（公告）日: 2018-08-14
• 發(fā)明（設(shè)計）人: 沙金;胡光輝;陳萬雄;張盟盟;李偉
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號: H03M9/00
• 分類號: H03M9/00
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 李玉平

本發(fā)明公開一種并行LFSR架構(gòu)的實現(xiàn)方法，適用于基于LFSR結(jié)構(gòu)的各種硬件電路，如BCH編碼器、CRC校驗編碼器等。本發(fā)明基于狀態(tài)空間變換，提出了一種新的構(gòu)造轉(zhuǎn)換矩陣的方法，利用該矩陣完成狀態(tài)空間變換后得到的電路架構(gòu)比之前的架構(gòu)面積更小、復(fù)雜度更低，同時具有一致的速度。對應(yīng)于轉(zhuǎn)換矩陣構(gòu)造的方式，兩種搜索最優(yōu)轉(zhuǎn)換矩陣的算法也被提出，其中第二種算法比之前的搜索算法具有更短的搜索時間，能夠快速的找到最優(yōu)的轉(zhuǎn)換矩陣。

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

本發(fā)明屬于硬件系統(tǒng)中的并行LFSR架構(gòu)設(shè)計技術(shù)領(lǐng)域，涉及應(yīng)用LFSR的硬件電路設(shè)計，如并行BCH編碼器構(gòu)造和CRC校驗編碼器構(gòu)造，更為具體的是，設(shè)計應(yīng)用高速并行LFSR架構(gòu)處理數(shù)據(jù)的硬件系統(tǒng)。

背景技術(shù)

線性反饋移位寄存器(Linear Feedback Shift Register,LFSR)廣泛應(yīng)用于BCH編碼器設(shè)計和CRC校驗編碼器設(shè)計領(lǐng)域，用于計算兩個多項式的余子式。假設(shè)相關(guān)的生成多項式g(x)＝g_n-kx^n-k+…+g₁x+g₀(k為編碼前信息長度，n為編碼后信息長度)，則對應(yīng)串行LFSR編碼器結(jié)構(gòu)如圖1所示。圖中的⊕為異或操作，為伽羅華域的相乘操作，r_n-k-1(t),…,r₁(t),r₀(t)為存儲校驗位信息的寄存器，u(t)為輸入的待編碼信息。這種編碼器雖然結(jié)構(gòu)簡單，具有很高的運行速度，但還是受到輸入位寬的限制，吞吐率不高，很難應(yīng)用在高速通信系統(tǒng)中。

為解決現(xiàn)有的串行LFSR架構(gòu)在吞吐率上的劣勢，Jeff H.Derby提出了基于狀態(tài)空間模型的并行LFSR架構(gòu)，該架構(gòu)可同時處理pbit(稱p為并行度)的數(shù)據(jù)，只需要個時鐘周期即可完成校驗位的計算。

應(yīng)用狀態(tài)空間模型，普通的串行LFSR結(jié)構(gòu)(圖1)可以被描述為以下的公式：

R(t+1)＝A×R(t)+b×u(t)

其中R(t)為t時刻各校驗位寄存器的值，u(t)為t時刻輸入的待編碼信息，A和b的構(gòu)造如下：

b＝(g_n-k-1,…,g₁,g₀)^T

基于該串行公式能推導(dǎo)出p bit數(shù)據(jù)處理后的結(jié)果，即p bit數(shù)據(jù)并行輸入時校驗位的計算公式：

R(t+1)＝A^p×R(t)+B_p×U_p(t)

其中，U_p(t)和B_p的構(gòu)造如下：

U_p(t)＝(u(t_p),u(t_p+1),…,u(t_p+p-1))^T

B_p＝(A^p-1b,…,Ab,b)

該公式表示的電路結(jié)構(gòu)如圖2所示，由于矩陣A^p和B_p實際上表示的是電路兩個部分連接的方式，該類矩陣又被稱之為連接矩陣。

狀態(tài)空間變換法通過引入一個轉(zhuǎn)換矩陣T，將上述的公式轉(zhuǎn)換為：

R_T(t+1)＝A_pT×R_T(t)+B_pT×U_p(t)

R(t+1)＝T×R_T(t+1)

其中：