糾錯解碼器的錢搜索單元的製作方法

2023-10-08 16:19:19

專利名稱：糾錯解碼器的錢搜索單元的製作方法
技術領域：
本發明涉及數字通信系統的檢錯和糾錯。
背景技術：
任何現代數字通信系統的一項重要功能是差錯控制編碼。差錯控制編碼是通信領域中用於處理數字系統中的檢錯和糾錯的技術。一般來說，檢錯/糾錯方案一般用於確保在數字數據的存儲和傳輸過程中，不引入數據差錯，或者可選地，如果數據引入了差錯，可以糾正引入的錯誤。通過向數據增加冗餘以實現數據的檢錯和/或糾錯的能力。傳輸或存儲的數據中包含冗餘位導致編碼信號或欄位的組成要比未編碼原始信號或欄位具有更多位。
檢錯/糾錯中一種常用方案通過使用被稱作裡德-所羅門(ReedSolomon)的編碼。裡德-所羅門碼是非二進位系統循環線性分組編碼。非二進位碼的碼元由幾位組成。如裡德-所羅門編碼的非二進位碼非常適於校正突發的差錯，因為這些編碼的校正是在碼元級別上完成的。如裡德-所羅門碼的系統碼生成包括未改變形式的報文碼元的碼字。解碼器將可逆數學函數應用在報文碼元上以產生冗餘，或奇偶碼元。然後，通過將奇偶碼元附加在報文碼元之後形成碼字。裡德-所羅門碼被認為是循環碼，因為任何有效碼字的循環移位同樣產生另一個有效碼字。循環碼字的流行是因為其可以通過高效並且廉價的解碼技術實現。最後，裡德-所羅門碼被認為是線性的，因為任何兩個有效碼字相加將得到另一個有效碼字。
典型的裡德-所羅門解碼器包括下列主要組件模塊
(i)伴隨式生成模塊，(ii)差錯多項式模塊，(iii)差錯位置模塊，以及(iv)差錯數量模塊，(v)糾錯模塊，以及(vi)延遲模塊。伴隨式生成模塊用於接收碼字和根據碼字生成伴隨式。該伴隨式用於在差錯多項式模塊中生成差錯多項式。差錯多項式傳輸到差錯位置和差錯數量模塊，其中分別確定碼字的差錯位置和數量。差錯向量是根據差錯的位置和數量產生的。延時的接收碼字通過糾錯模塊使用與特定碼字對應的差錯向量進行糾錯。
裡德-所羅門解碼器中用於執行差錯位置模塊的一個常見方法是通過使用稱作錢(Chien)的模塊(或錢搜索)，其使用高強度錢算法以計算多項式所有可能的值。錢模塊由一些單個的錢單元組成。錢搜索單元(參見圖11)是用於執行差錯位置多項式的單階或係數的硬體，因此共有(t+1)階(因為差錯多項式位置具有最大次數為t次以及t次多項式具有(t+1)個係數)。典型的錢搜索單元以迭代方式處理差錯位置多項式係數。在第一次迭代中，復用器接收與正在處理的碼字對應的合適的多項式係數，並將多項式係數發送到寄存器。在後續時鐘周期中，寄存器的輸出首先進入伽羅華(Galois)域乘法器，然後通過復用器反回到寄存器進行存儲。該過程共執行N個時鐘周期，其中N為碼字長度。
與這種實現相關的問題在於差錯位置是按照對應碼字字節的逆序生成的，因此在被添加到碼字進行校正前，需要通過LIFO模塊進行逆序。LIFO模塊是包括多個寄存器的硬體存儲元件。一旦所有寄存器存滿，LIFO模塊發送其輸出。最後輸入的元素成為第一個輸出元素，依次類推。使用LIFO模塊存在兩個問題其一是LIFO模塊為較大的存儲元件，並且因此增加了IC的門數和功耗。另一個問題是，LIFO模塊帶來了N個時鐘周期的延遲。該延遲發生是因為LIFO模塊需要N個時鐘周期來完成初始存滿，並且直到最後的元素被讀入LIFO才生成輸出。

發明內容
應用本發明有利於解決現有技術相應問題。本發明在差錯位置模塊中生成與每個碼字順序相同的係數差錯位置，這樣不需要使用LIFO模塊。本發明是用於計算根據單元中與係數對應的碼字而生成的單個差錯位置多項式係數的方法和裝置，其中接收與接收碼字相對應的差錯位置多項式係數。在第一個時鐘周期中，差錯位置多項式係數通過負指數的伽羅華域乘法器相乘。負指數的值是與該單元相對應的階數和碼字長度(N)的函數。相乘結果作為單元輸出。單元輸出結果通過具有正指數的伽羅華域乘法器迭代相乘N-1次。第二個伽羅華域乘法器的正指數值是階數的函數。


參照本發明的以下描述應該結合附圖，其中圖1是具有糾錯方案的數字數據傳輸系統的示意方框圖；圖2是說明典型糾錯方案的方法流程圖；圖3是示意不同糾錯方法的分層表示；圖4是示意裡德-所羅門解碼器的方框圖；圖5是示意應用本發明原理的裡德-所羅門解碼器典型實施方式的方框圖；圖6是示意根據本發明原理說明的典型的內部解碼器握手協議的方框圖；圖7是示意根據本發明原理，裡德-所羅門解碼器典型實施例中功能模塊之間握手協議的方框圖；圖8是根據本發明原理的典型裡德-所羅門解碼器的時序圖，說明了使用內部模塊信號交換的解碼器效率；圖9是根據本發明原理，除錢/Fomey模塊之外應用錢模塊的裡德-所羅門(RS)解碼器的典型實施方式的方框圖；圖10是在裡德-所羅門解碼器中實現的典型的現有技術錢搜索單元的方框圖；以及圖11是根據本發明原理，在裡德-所羅門解碼器中實現減少存儲需求和延遲的改進錢搜索單元的方框圖。
具體實施例方式
圖1根據本發明原理，描述了包括檢錯/糾錯方法的數字數據傳輸系統100的方框圖。檢錯/糾錯方法通常應用於保證在數據的傳輸和存儲期間，不會引入數據差錯，或者如果數據引入差錯，可以糾正引入的錯誤。通過向數據增加冗餘來實現數據檢錯/糾錯功能。傳輸中或存儲的數據中包含冗餘位導致編碼信號或欄位具有比未編碼信號或欄位更多的位數。附加開銷的補償是檢錯或者檢錯並糾錯的功能。通常根據編碼增益來測量使用差錯控制編碼獲得的性能改進。假設一個未編碼通信系統在信噪比(SNR)30dB時達到一給定誤碼率(BER)。如果系統添加編碼增益為3dB的差錯控制編碼方法，則該編碼系統將能夠在信噪比為27dB時達到該誤碼率。或者如果系統工作時的信噪比為30dB，則編碼系統所達到的誤碼率將與信噪比為33dB的未編碼系統相同。編碼增益的性能在於其允許通信系統(i)在比未編碼可能低的SNR中保持所希望BER；(ii)在給定NR時相比未編碼系統能夠達到較高的BER。
通過實施例的方式，編碼器110的功能是接受來自數據源的數字數據，並且將數據通過信道發送或者存儲在存儲介質(圖上集中顯示為信道或存儲設備115)或者操作或處理數據。通常情況是，在傳輸或存儲過程中，噪聲或差錯125可能被引入數據，因而破壞或改變原始數字數據的形式。解碼器120的功能是檢錯並糾錯或僅僅是檢測數字數據的指定部分是否受到破壞。
圖2是說明在發射機/信道/接收機環境中應用的各種檢錯/糾錯處理過程的流程圖。儘管上下文已經有所描述，但是現有技術人員顯然清楚這種檢錯/糾錯處理也能應用在廣播傳輸，數字數據存儲，或對數據進行處理或操作的任何過程中(以數據段，包，流等形式存在的數據)。作為實施例，僅僅說明但不限於下述可以使用檢錯/糾錯方法提高性能，完整性和可靠性的技術/設備(i)各種存儲設備，包括但不限於磁帶，光碟(CD)，數位化通用盤(DVD)，條形碼等；(ii)無線或移動通信(包括蜂窩電話，雙向收發機，微波連接等)；(iii)衛星通信；(iv)數字無線電，數位電視(DTV)，數字視頻廣播(DVB)等；(v)數據機，包括但不限於電纜，V.pcm，ADSL，xDSL等。
按照步驟210，在初始建立連接，協定傳輸信道參數後，傳輸源將數字數據處理為可傳輸的形式。按照步驟215，在傳輸之前，源產生差錯碼；差錯碼部分至少基於要傳輸的數字數據的值，因此提供數據冗餘度。按照步驟220，生成的差錯碼被附加、添加、復用，或者被包括在數字數據中，從發射機傳輸到接收機。按照步驟225，數字數據和差錯碼在接收機接收。如需要，按照步驟230在接收機執行初始信號處理。按照步驟235，接收機訪問差錯碼的冗餘位，並根據應用的差錯控制碼方案處理其中所包含的信息。按照步驟240，如果被處理的冗餘位肯定地檢查接收數字數據，則假設數據未被破壞。數字數據的進一步信號處理(如果有的話)按照步驟245在接收機繼續進行。
然而，如果被處理的冗餘位表明接收的數字數據(至少包括一個位出錯)被破壞，則按照步驟250，計算數據差錯以確定差錯是否能在正應用的差錯控制方法中得到校正。即，某些差錯控制方法只能檢錯，但不包括用於校正這些差錯的冗餘數據的屬性和類型。其它差錯控制方法僅使用其檢錯性能，而不論是否具有檢錯和糾錯兩種性能。通常在任何特定的數位訊號，報文或包的精度不很重要的時候使用該方法，但是數據的一致性和及時傳輸是極其重要的。這種應用的實例是語音，音頻和視頻應用的同步流數據。而且，甚至當使用差錯控制方法來檢錯和糾錯時，如果檢查出的差錯數量超出差錯校正能力時(即，超出差錯碼位所提供的冗餘信息)，那麼數據不可恢復。按照步驟255，如果數據可校正，那麼數據差錯被校正並且在接收機進行進一步的信號處理(如果有)。然而，如果差錯不可校正，則按照步驟260執行運算以確定數據精度是否必要。如果和純數據系統一樣需要數據精度，則單個位差錯十分關鍵的可能性很大，按照步驟265，將重發請求傳輸給傳輸源。如果和同步特性的數據報文的情況一樣，不可校正數據的精度不是必要的，則按照步驟270僅僅捨棄被破壞並且不可校正的數據，然後處理後續數據報文。
圖3說明各種差錯碼分類和方案的分層表示。差錯碼310分為兩類(i)自動重傳請求(ARQ)或檢測碼315，以及(ii)前向糾錯(FEC)碼320。ARQ僅是檢測類型的編碼，其中可通過接收機檢測出傳輸中的差錯，但不校正。接收機必須請求任何接收的數據，並且請求再次傳輸具有檢測差錯的接收數據。因為這些傳輸將佔用一定帶寬，所以ARQ碼通常使用「乾淨的」傳輸介質(其具有低差錯率)。一個最常見的實施例是簡單的奇偶校驗325，常常應用在RAM中檢測數據差錯。另一個實施例是應用於在乙太網傳輸中檢錯的循環冗餘校驗(CRC)330。如果檢測出差錯，將再次傳輸報文。因為乙太網主要通過線路傳輸，所以出錯機率小於其它介質。CRC和ARQ僅僅是差錯檢測碼方法中的兩類說明性實施例；本領域技術人員也知曉其它差錯檢測編碼方法。僅僅檢錯而不進行糾錯的差錯碼比糾錯碼顯著地減少了冗餘。而且，差錯檢測解碼器遠沒有糾錯解碼器複雜。使用差錯檢測碼方法的系統通常需要克服數據再次傳輸的開銷。即，數據的再次傳輸不會顯著地影響系統總通信量。
因為噪聲介質對特定的傳輸引入差錯的機率平等，所以使用ARQ方法意味數據不斷再次傳輸，系統通信量降低到不可接受的水平。這種情況下，如其名稱所示，糾錯碼不僅允許在接收端檢錯，還允許糾錯。這樣減少了數據再次傳輸的需要，僅當差錯數量遠遠大於所使用的糾錯方法可以校正的數量的時候才需要再次傳輸。糾錯也應用在單向通信中，其中不存在接收機請求再次傳輸報頭的機率。這些單向路徑的說明性實施例包括某些衛星傳輸和磁帶存儲介質。
糾錯碼可以分為兩種主要子類別。第一種為分組碼335，第二種為卷積碼340。分組碼335是經常使用的糾錯碼，它和定義了有限長度的報文分組共同使用。之所以命名為分組碼335是因為此子分類使用了能夠處理報文碼元的分組的編碼器，然後輸出碼字碼元的分組。分組碼通常能夠分成兩種類型二進位碼345和非二進位碼355。二進位碼345的一種實例是海明碼350，其特徵是每個字符具有四個信息位和三個校驗位。非二進位碼的示例是裡德-所羅門碼360。
與之相反，卷積碼340編碼器用於報文碼元的連續流，並且同時生成連續的編碼輸出流。這些編碼這樣命名，是因為編碼處理過程能夠視為編碼器的脈衝響應和報文碼元的卷積。卷積碼340的兩個實施例為網格(Trellis)編碼調製(TCM)365和二進位卷積碼370。
圖4是典型的裡德-所羅門(RS)解碼器的方框圖。如前所述，裡德-所羅門碼是非二進位系統循環線性分組碼。非二進位碼使用包括幾位的碼元。通常，非二進位碼的碼元長度為8位或一個字節。非二進位碼，如裡德-所羅門碼，可以很好地校正突發差錯，因為這些碼的校正是在碼元級上進行的。通過在解碼過程中處理碼元，這些碼能夠校正具有8個突發差錯的碼元，就象校正具有一位差錯的碼元那樣簡單。如裡德-所羅門碼的系統碼，生成包括未改變形式的報文碼元的碼字。編碼器將可逆數學函數應用在報文碼元上，以生成冗餘或奇偶碼元。然後，通過將奇偶碼元附加在報文碼元後形成碼字。因為任何有效碼字的循環移位同樣產生另一個有效碼字，裡德-所羅門碼被認為是循環碼。循環碼的普遍使用是因為存在有效可行和低開銷的解碼技術來實現它們。最後，裡德-所羅門碼被認為是線性的，因為任何兩個有效碼字相加可以得到另一個有效碼字。
差錯控制碼的理論利用了被稱作有限域或伽羅華域的數學概念。伽羅華域是有限個元素的集合。在這個集合上定義了加法和乘法運算，這些運算來自標準算術。例如，加法的恆等元素為0，乘法的恆等元素為1。裡德-所羅門碼使用具有循環和線性特性的碼的伽羅華域數學實現，並在階段為q＝pm的伽羅華域中運算，其中p是正素數，m是正整數。q階伽羅華域表示為GF(q)，包含q個不同元素。
特定的裡德-所羅門碼通過(n，k)碼表示。根據碼字中的碼元數目參數n表示碼字長度。參數k表示碼字中報文碼元數量。因而附加的奇偶碼元數目為n-k。碼的糾錯能力t＝(n-k)/2。碼能夠檢測並校正T個差錯，0≤T≤t。碼字基於報文碼元，使用裡德-所羅門編碼器生成。因為裡德-所羅門是系統碼，傳輸n個報文碼元，n-k個奇偶碼元附加在報文碼元後形成碼字。向傳輸的碼字增加的冗餘奇偶碼元的值，取決於報文碼元。接收機的解碼器使用該冗餘來檢錯和糾錯。
在接收機的解碼器，接收碼字作伴隨式生成塊410。解碼器執行的第一步是通過伴隨式生成塊410(也經常指伴隨式生成模塊，或伴隨式生成器)實現伴隨式運算。伴隨式包括n-k個碼元，其值根據接收碼字計算。伴隨式僅取決於差錯向量，獨立於傳輸的碼字。即，每個差錯向量具有唯一的伴隨式向量，但是如果差錯圖案相同，則多個不同的接收碼字將具有相同的伴隨式。首先計算伴隨式的原因是因為這樣做限定了差錯向量的搜索域。首先知道伴隨式將正確差錯向量的數目限制為2n個可能差錯向量中的2n-k個。
伴隨式生成塊410計算伴隨式的一個方法是通過生成器多項式使用伽羅華域代數來除接收碼字。除法的餘數被稱作伴隨多項式s(x)。通過計算S(x)在α到αn-k的值得出實際的伴隨式向量S(x)。然而，從硬體角度來看該方法並非效率最優，一種在硬體中常用的替換方法是直接計算在α到αn-k時接收碼字R(x)的值。伴隨式生成塊410通過計算接收碼字R在α到αn-k時的值(即，R(α)至R(αn-k))來計算伴隨式S。在裡德-所羅門碼中，n-k＝2t，因而，需要計算2t個伴隨式值[S1 S2S3...S(2t)]。這些值通常被並行計算，第一個伴隨式生成器計算接收碼字在α的值以得到S1，下一個伴隨式生成器計算接收碼字在α2的值以得到S2，依次類推。
一旦通過伴隨式生成模塊410計算出伴隨式，其值就傳輸到差錯多項式模塊420。這裡應用伴隨式來生成差錯位置多項式。該過程包括t個未知數的同步等式。幾種適合這些運算的快速算法，包括Berlekamp-Mαssey算法或歐幾裡得算法。這些算法利用裡德-所羅門碼的特殊矩陣結構，極大的減少了所需的計算量。
差錯多項式模塊420將差錯位置多項式(一旦已決定)傳輸到差錯位置模塊430和差錯數量模塊440。差錯位置模塊430計算差錯位置多項式的根以確定差錯位置。典型地，可使用錢搜索算法，或錢單元實現。差錯位置模塊430確定的差錯位置和先前決定的差錯位置多項式被共同傳輸到差錯數量模塊440。差錯數量模塊440通過計算t個未知數的同步等式來確定差錯數量。應用在差錯數量模塊440中的快速和廣泛使用的算法是Forney算法。
如果有錯的話，計算出的差錯位置和差錯數量被前向傳輸到糾錯模塊450，以恢復糾錯的碼字。通常將差錯位置和差錯數量的組合稱為差錯向量。差錯向量和碼字大小相同，在與差錯對應的位置上包含非零值。所有其它位置包括零。糾錯模塊450的另一輸入是延遲模塊460的輸出。延遲模塊460將獲得接收碼字，輸出具有延遲的相同接收碼字。在一個實施例中，糾錯模塊450通過使用伽羅華域加法器452和LIFO(後入先出)模塊454共同實現。通過使用伽羅華域加法器452將接收碼字和差錯向量相加來糾正接收碼字中的差錯。使用LIFO模塊454是因為差錯向量以接收碼字的逆序生成，所以LIFO操作必須應用於接收碼字或者差錯向量，以匹配兩個向量的字節順序。糾錯模塊450的輸出是原始碼字的解碼器估值。
圖5是裡德-所羅門解碼器實施方式的方框圖。輸入的接收碼字被轉送到伴隨式生成模塊510。一旦通過伴隨式生成模塊510計算出伴隨式S(x)，其值傳輸到歐幾裡得算法模塊520。歐幾裡得算法處理伴隨式S(x)以生成差錯位置多項式Λ(x)和差錯數量多項式Ω(x)。即，它求解下面的關鍵等式Λ(x)+[1+S(x)]＝Ω(x)mod x21+1等式1在裡德-所羅門解碼中應用的算法是基於用於尋找兩個多項式最大公約數(GCD)的歐幾裡得算法。歐幾裡得算法是人們所熟知的迭代多項式除法算法。
一旦計算出差錯位置多項式Λ(x)，需要計算其根。錢搜索算法用於查找這些根。錢搜索是計算多項式所有可能輸入值的高強度算法，然後確定哪個輸出為零。如果差錯出現在位置i，則下式等於零j=0tj-ij=0,]]>其中i＝0..(n-1) 等式2錢搜索計算等式2在所有的i和j時的值，並計算使等式為零的值的個數。零的位置就是差錯的位置，零的數目是差錯碼元的數目。
在典型的實施方式中，硬體中執行t+1階錢搜索。每階(其中一階包括一個乘法器，一個復用器和一個寄存器)代表在上面錢搜索等式中對於j取不同的值。搜索運行n個時鐘周期(每個時鐘周期代表上述等式i取不同的值)，檢查加法器的輸出以確定其結果是否為零。如果結果為零，則零檢測模塊將輸出1，否則輸出0。錢搜索模塊的輸出因此為一個由「0」或「1」組成的n位字符串。每個「1」代表差錯碼元的位置。
對於第一個時鐘周期，復用器將差錯位置多項式係數發送到寄存器。對於剩餘(n-1)個時鐘周期，乘法器輸出將通過復用器發送到寄存器。乘法器的指數為負值。然而，這些值可使用模算子預先計算出來。α-1的指數等於(-i模n)＝(-j模255)。例如，α-1等於α254，α-2等於α253，依次類推。
Foney算法用於計算差錯值Yi。為計算這些值，Foney算法使用差錯位置多項式Λ(x)和差錯數量多項式Ω(x)。差錯值的等式為Yi=(x),(x),]]>其中x＝α-i，α-i是Λ(x)的根 等式3計算Λ′(x)的導數實際非常簡單。例如，假定Λ(x)＝α4x3+α3x2+αx+α2。因而，Λ′(x)等於Λ′(x)＝3α4x2+2α3x+α＝(α4+α4+α4)x2+(α3+α3)x+α＝α4x2+α 等式4求導是通過取X的奇數冪的係數，並將其分配給X的低階冪(偶數冪)獲得的。
然後，使用同錢搜索中應用的相同類型的硬體和Λ′(x)多項式共同計算Ω(x)多項式。要計算Ω(x)，Ω0係數加上係數Ω1乘以α-1，係數Ω2乘以α-2，依次類推直到係數Ωt乘以α-t。然後將這些乘法器的輸出結果相加。
分子然後乘以分母的倒數。反轉乘法包括查找表，用以搜索分母的倒數。例如，如果分母是α3，則倒數是α-3，可以表示為α-i＝α(-1modn)＝α(-3mod255)＝α252等式5因為錢搜索和Foney算法都需要相同的硬體類型，所以可以在相同模塊中合併兩個功能，如錢/Forney模塊530所示。在實現中，錢搜索的輸出有兩個加法器。第一加法器將偶數階的值相加，另一個加法器將奇數階的值相加。為形成最後的錢搜索輸出，將這兩個加法器的輸出相加，零檢測模塊檢測根的位置。奇數階的加法器輸出用於Forney算法。奇數階的總和代表Forney等式的分母。該值取倒數，然後乘以根據差錯數量多項式計算出的分子的值。輸出與零檢測輸出作與(AND)運算的結果，因為差錯的值僅對實際差錯位置有效(否則它們應當設置為0)。
因而，錢/Forney模塊530使用差錯位置多項式和差錯數量多項式以生成差錯向量，差錯向量被轉送到糾錯模塊540。差錯向量和碼字大小相同，在與差錯對應的位置上包含非零值。所有其它位置包含零。糾錯模塊540的另一輸入是延遲模塊550的輸出。延遲模塊550獲得接收碼字，延遲輸出相同的接收碼字。在本實施方式中，糾錯模塊540通過使用伽羅華域加法器544和LIFO模塊542共同實現。通過使用伽羅華域加法器544將接收碼字和差錯向量相加來糾正接收碼字中的差錯。使用LIFO模塊542是因為差錯向量以接收碼字逆序生成，所以LIFO操作必須應用於接收的碼字或者差錯向量，以同步兩個向量的字節順序。糾錯模塊540的輸出是原始碼字的解碼器估計值。
內部解碼器組件模塊消息發送如前所述，裡德-所羅門解碼器至少包括四個主要組件或功能模塊。它們是伴隨式生成器，差錯多項式模塊，差錯位置模塊，以及差錯數量模塊。如果解碼器除檢錯外還糾錯，則解碼器還包括糾錯模塊。在現有技術的解碼器中，這些模塊形成一個「傳送管道」，其到一個模塊的輸入僅取決於前一模塊的輸出。即，一個模塊沒有對前一模塊的反饋。裡德一所羅門解碼器在執行特定碼字的解碼過程時(見圖4和圖5中的延遲模塊)，還需要使用存儲器或緩衝模塊來存儲接收到的碼字。差錯位置/數量模塊在執行解碼過程中生成差錯向量，該差錯向量與接收到的碼字異或(XOR)，接收到的碼字被存儲在存儲器中以形成解碼器的輸出。典型的，所使用的存儲器容量等於一個碼字，因此解碼器一次僅能夠處理一個碼字。
圖6是根據本發明原理說明內部解碼器握手協議的典型實施方式的方框圖。內部解碼器模塊A610和內部解碼器模塊B620表示在使用模塊間反饋或通信的裡德-所羅門解碼器中的任意兩個模塊(選自上面描述的功能模塊)。解碼「傳送管道」是數據信道630，表示裡德-所羅門解碼器功能模塊之間的現有技術中的單向信道。另外，本發明同樣示出了反饋信道。反饋信道可以認為是功能模塊將當前或將來的不活動狀態傳送到上行或下行功能模塊的裝置。例如，假定內部解碼器模塊A610已經完成特定碼字的處理功能。內部解碼器模塊A610將不活動報文發送到內部解碼器模塊B620中，表明它準備將特定碼字的計算結果發送到內部解碼器模塊B620。因此，這種不活動報文被稱做「準備發送」(RTS)報文650。相反地，假定內部解碼器模塊B620已經完成特定碼字的處理功能。內部解碼器模塊B620將不活動報文發送到內部解碼器模塊A610，表明準備接收。因此，這種不活動報文被稱做「準備接收」(RTR)報文640。
本發明的此種實施方式，通過在功能模塊之間的反饋或握手實現的解碼器其優勢在於允許適合智慧財產權(IP)內核的用戶可配置結構，使用戶基於所希望實現的存儲器大小來定製解碼器性能。
圖7是說明裡德-所羅門(RS)解碼器實施方式中的功能模塊之間握手協議的方框圖。圖4已經充分描述了伴隨式生成模塊410、差錯多項式模塊420、差錯位置模塊430、差錯數量模塊440、糾錯模塊450(包括伽羅華域加法器452和LIFO模塊454)以及延遲模塊460的功能、目的和操作，因此這裡不再重複。圖7還包括前述的不活動報文(或者握手信號)。處理模塊使用握手信號(如，RTS和RTR報文)，表明何時發送和/或準備接收數據。因此，伴隨式生成模塊410和差錯多項式模塊420能夠通過RTS信道710交換RTS報文，或通過RTR信道712交換RTR報文。差錯多項式模塊420和差錯位置模塊430能夠通過RTS信道718交換RTS報文，或通過RTR信道720交換RTR報文。差錯多項式模塊420和差錯數量模塊440能夠通過RTS信道724交換RTS報文，或通過RTR信道726交換RTR報文。差錯數量模塊420和糾錯模塊450能夠通過RTS信道724交換RTS報文，或通過RTR信道726交換RTR報文。伴隨式生成模塊410通過RTR信道740發送RTR報文來請求下一個接收碼字。糾錯模塊450還通過RTS信道760發送RTS報文到輸出處理級。另外，根據本發明的實施方式，有必要向延遲模塊460發送任何RTR或RTS報文(通過報文信道750)，來合適地調整延遲以便正在檢測和校正的接收碼字能夠和糾錯模塊450中的差錯向量正確同步。
本發明的優點在於，通過使內部解碼器功能模塊之間進行握手，當功能模塊不活動時(即，它完成了最後的工序)，功能模塊能夠請求接收更多數據進行處理。近似的，功能模塊能夠通知下行功能模塊，它已經完成自己的工作程序，可以在下行功能模塊能夠接收的任何時間發送結果。例如，儘管伴隨式生成模塊410通常使用固定(已知的)時鐘周期數來生成用於接收特定長度碼字的伴隨式，但是差錯多項式模塊420是一個執行時間可變化的迭代過程。另外，差錯位置模塊430和差錯數量模塊440典型地將採用固定(已知的)時鐘周期數，但是如果它確定碼字存在著大量差錯使其不可糾正，則捨棄有關該碼字的隨後處理，差錯位置模塊430和差錯數量模塊440能夠通過合適的RTR信道720，726向差錯多項式模塊420發送RTR報文來請求開始處理下一碼字。因此，差錯位置模塊430和差錯數量模塊440也能夠採用變化的時鐘周期完成。
應當注意，圖7說明的本發明實施方式僅僅是在不脫離本發明範圍的情況下實現的多個實施方式之一。例如，不需要解碼器的每個功能模塊發送RTS和RTR報文。而且，作為設計選擇，可僅在伴隨式生成模塊410和差錯多項式模塊420之間使用握手。其它變化也是可能的。而且，儘管RTS和RTR報文已說明和描述為通過RTS和RTR信道進行通信，但是這種描述僅僅是一種邏輯敘述，報文發送信道可以在與數據信道相分離的一個普通物理層報文信道上引入，或者，報文發送信道可以在與數據信道相同的物理層上引入。
根據本發明原理，用戶有通過改變存儲器分配大小設置解碼器性能。因此，實施方式中將存儲器大小分配等同於一個碼字將適於硬體和高效功耗設計，但是一次僅能處理一個碼字。分配的存儲器大於一個碼字長度的實施方式能在處理一個碼字的同時開始裝載第二個碼字。分配兩個碼字大小的存儲器實施方式可以同時處理兩個碼字，依次類推。當然，增加存儲器大小相應地導致硬體和功耗的開銷增大，但好處是解碼處理速度的相應提升和等待時間的降低，因為在特定的時間內可以處理更多的碼字。握手信號完全自動處理，以便用戶只需要輸入解碼器應用的存儲器大小。通過控制這一單個參數，用戶能夠根據速度，功耗和大小(門數)定製解碼器性能。
圖8是根據本發明原理的裡德-所羅門(RS)解碼器的時序圖，說明與使用內部模塊握手的解碼器相關的效率。時序圖810的上半部分說明在沒有內部模塊握手的典型解碼器中所需的時間。在這個方案中，碼字1(CW1)的處理過程起始於t0時刻。CW1伴隨式在t1時刻生成，結果被傳輸到差錯多項式模塊。差錯多項式模塊在t2時刻完成處理CW1，直到CW1在t4時刻被全部完成。碼字2(CW2)的處理因此起始於t4時刻。CW2的單函數順續處理直到t8時刻，CW2的差錯位置和差錯數量計算完成。注意在沒有內部模塊握手時處理兩個碼字的總時間為(t8-t0)。
時序圖820的下半部分說明具有內部模塊握手的解碼器的處理時間。注意到通過實現容納三個碼字的存儲器，解碼器能夠一次同時處理三個碼字。因為每個模塊通知先前的模塊已經準備好，所以在完成處理時能夠接收更多數據，因此獲得了效率。在本說明例中，碼字3(CW3)的處理完成時刻在t6和t7之間。
糾錯解碼器中的雙錢搜索模塊本發明的一個典型實施方式是使用雙錢搜索模塊來執行糾錯處理。應用本發明原理的解碼器降低了解碼器的延遲和解碼器對存儲器的需求。
圖9是根據本發明原理應用雙錢搜索模塊的裡德-所羅門解碼器示例實施方式的方框圖。輸入是接收碼字並被轉送到伴隨式生成模塊910。一旦通過伴隨式生成模塊910計算出伴隨式S(x)，則伴隨式被轉送到歐幾裡得算法模塊920。歐幾裡得算法用於處理伴隨式S(x)，以生成差錯位置多項式∧(x)和差錯數量多項式Ω(x)。
本發明的實施方式中，引入新的錢模塊930用於確定碼字中的差錯數目。一旦計算出差錯位置多項式∧(x)，錢模塊930應用錢搜索算法來計算其根。錢搜索是高強度算法，計算所有可能輸入值的多項式，然後確定哪個輸出為零。如果差錯出現在位置1，則下列等式為零j=0tj-ij=0,]]>其中i＝0..(n-1)等式6錢模塊930計算上述等式在i和j取所有值時的結果，以及計算等式等於零的次數。結果數字為檢測出的差錯數目。
如前所述，差錯多項式必須計算差錯位置和差錯數量。因為相同類型的硬體需要執行錢搜索和Forney算法，所以兩功能可以合併在相同的模塊中，如錢/Forney模塊940所示。在實現中，在錢搜索的輸出使用了兩個加法器。第一個加法器將所有偶數階的值相加，第二個加法器將所有奇數階的值相加。為生成最終的錢搜索結果，然後將這兩個加法器的輸出相加，零檢測模塊檢測根的位置。奇數階的加法器的輸出同樣應用於Forney算法中。奇數階的總和表示Forney等式的分母。該總和值反轉，然後乘以通過計算差錯數量多項式得出的分子值。輸出與零檢測輸出進行與(AND)運算，因為差錯值僅在實際出錯位置有效(否則他們應該被設置為零)。
因而，錢/Forney模塊940使用差錯位置多項式和差錯數量多項式來生成差錯向量，將其轉送到糾錯模塊950。差錯向量和碼字大小相同，包括在差錯對應位置的非零值。所有其它位置包括零。糾錯模塊950的另一個輸入是延遲模塊960的輸出。延遲模塊960輸入接收碼字，延遲輸出相同接收碼字。在此實施方式中，使用伽羅華域加法器954和LIFO模塊952執行糾錯模塊950。接收碼字中的差錯通過將接收碼字加在差錯向量上，使用Galios域加法器954進行校正。應用LIFO模塊952，是因為差錯向量是按照接收碼字的逆序生成，因此LIFO操作必須應用在接收碼字或者差錯向量上，以匹配兩向量的字節順序。糾錯模塊950的輸出是原始碼字的解碼器估計。
裡德-所羅門解碼器僅能校正到t個差錯，其中包含的奇偶字節數目為2t。如果檢測到多於t個差錯，一般需要將接收碼字不加改變不加糾錯地發送到解碼器輸出，因為如果檢測出大於t個差錯，則碼字不可糾正。在現有技術錢/Forney實現中，整個碼字必須在確定差錯個數之前進行處理。這樣，操作需要N個時鐘周期，N是碼字長度。一旦完成錢/Forney計算，確定差錯數目並與t的值比較。如果差錯數目小於或等於t，來自錢/Forney模塊的差錯值與接收碼字進行「異或」操作以進行糾錯，因而生成最後的解碼器輸出。然而，如果差錯數目多於t個，則接收碼字不被改變地被轉送作為解碼器輸出。因此，現有技術的方法需要存儲整個接收碼字直到錢/Forney模塊完成處理。這個方法還引入了等待時間的延遲，因為解碼器輸出直到模塊的全部N個時鐘周期完成才能繼續被轉送。
相比而言本發明此實施方式的碼字進行兩次錢算法；第一次為確定差錯數目，第二次為確定差錯位置。因此，當錢模塊930檢測到差錯數目大於閾值t時，接收碼字作為解碼器輸出，釋放存儲器。相反地，當差錯數目小於或等於閾值t時，數據傳輸到錢/Forney模塊以確定實際的差錯位置和數量。這種實施方式在結合使用本發明圖6至圖8的握手時可以得到優化。這種結合使得錢/Forney模塊940在錢模塊930確定下個碼字差錯數目的同時計算差錯。因而，錢/Forney模塊940的輸出能夠立刻發送並釋放對應存儲器。
糾錯解碼器的改進錢搜索單元如前所述，錢/Forney模塊接收兩個多項式作為輸入差錯位置和差錯數量多項式；並且生成差錯向量作為輸出。差錯向量是代表接收碼字中差錯值的解碼器估計的N字節解碼器估計向量。差錯向量與接收碼字進行異或(XOR)運算，以糾錯形成原始碼字的解碼器估計值。現有技術中應用錢/Foreny模塊確定差錯向量的解碼器產生與碼字向量逆序的差錯向量。即，在差錯向量(或相反，碼字)沒有被進一步處理的情況下碼字和差錯向量不能進行異或運算。進一步處理典型地採用LIFO(後入先出)操作的形式處理差錯向量或接收碼字，其目的在於將輸入逆序以便碼字和差錯向量可以進行異或運算。不過，這將帶來N個時鐘周期的延遲，其中N為碼字中字節數目。另外，某些現有技術使用大於單個碼字長度的存儲器大小，這樣就需要存儲器拆分到兩個或更多個獨立的LIFO時鐘中。如此將造成尋址複雜，並將存儲器大小限制到碼字長度的整數倍。
本發明的實施方式是一種新的錢/Forney單元，它產生與碼字正確同步的輸出。即，差錯向量和碼字向量在進行異或運算之前均不需要反轉，因此減少了對LIFO模塊或其它反轉裝置的需要。由於不需要延遲N個時鐘周期，所以減少了等待的周期。而且，本發明中本實施方式簡化了尋址方法(與現有技術相比)，除了碼字長度整數倍的存儲器大小外還支持其它存儲器大小。例如，可以使用兩倍半於碼字長度的存儲器，允許解碼器處理兩個碼字的同時加載下一個碼字的一部分。
圖10是現有技術中典型的錢搜索單元1000(用於錢搜索和錢/Forney模塊的基本模塊)的方框圖表示。錢搜索模塊用於計算差錯位置多項式，以便找到它的根。根的位置對應於接收碼字的出錯位置。圖10的錢搜索單元用於執行下列等式Xi=j=0tj-ij=0,]]>其中i＝0..(N-1)等式7計算等式9，碼字中在與差錯對應的字節位置上得到零值。錢搜索單元1000是用於執行上述等式單階的硬體結構。每階處理差錯位置多項式的單個係數。因此總共有(t+1)階(因為差錯位置多項式最大階數為t，t階的多項式具有(t+1)個係數)。
錢搜索單元1000以迭代形式處理差錯位置多項式係數。在第一次迭代中，復用器1020接收與正在處理的碼字對應的合適的多項式係數1010，將多項式係數傳遞給寄存器1030。在後續時鐘周期中，寄存器輸出首先被傳遞到乘法器1040，在那裡乘以α-j，然後通過復用器1020傳送回寄存器進行存儲對於總的N個時鐘周期執行此過程指數i表示迭代次數，指數j表示錢搜索單元的階。即，j的值從0增加到t，因此在硬體上總共執行(t+1)個錢搜索單元階。
說明例中，假定單元代表第二階(j＝1)。因此，在每一個時鐘周期中，寄存器輸出將乘以α-1，結果存儲回寄存器中。該過程產生下列序列λ+λα-1X+(λα-1)α-1X2+((λα-1)α-1)α-1X3+...
其中Xn代表n個時鐘周期的延遲通過合併各項，最終序列產生為λ+λα-1X+λα-2X2+λα-3X3+...+λα-(N-1)X(N-1)與這種實施方式相關的問題是，差錯位置按照對應碼字字節的逆序產生，因此在與碼字相加進行校正之前需要通過LIFO模塊進行逆序。LIFO模塊是包含多個寄存器的硬體存儲單元。一旦所有的寄存器都已填充，LIFO模塊就發送它的輸出。輸入的最後一個元素成為輸出的第一個元素，依次類推。使用LIFO模塊存在兩個問題。一個問題是LIFO模塊是一個大容量存儲單元，其增加了IC的門數和功耗。另一個問題是LIFO模塊帶來了N個時鐘周期的等待時間。該等待時間的發生是因為LIFO模塊在最初需要N個時鐘周期才能充滿，直到最後一個元素讀入LIFO，才會有輸出。
圖11是示意根據本發明原理的改進錢搜索單元1100的方框圖，其中存儲器需求和延遲都有所下降。本發明中的本實施方式的原理在於使錢搜索模塊產生在數學上等同於標準錢搜索所生成的序列，雖然係數以相反順序生成(此後稱做「正常順序」)。本實施方式執行下列兩個等式(等式10和等式11)用於以正常順序生成差錯位置進行碼字校正。
Xi=j=0tj-j(N-1)=0,]]>其中i＝0 等式8Xi=j=0tji,]]>其中i＝1..(N-1) 等式9回想圖10中的現有技術錢搜索單元1000以迭代方式處理差錯位置多項式係數，起始α的指數為0，隨著每個時鐘周期遞減直到該指數減至-j(N-1)。本實施方式中圖11的錢搜索單元1100，α的指數值從-j(N-1)並始，隨著每個時鐘周期遞增直到增至0。
因此，在第一個時鐘周期，多項式係數1110通過預乘法器1150乘以α-j(N-1)(其中j是階數)，再輸入到復用器1120，然後傳輸到寄存器1130存儲。在隨後的時鐘周期中，寄存器1130的輸出被轉送到乘法器1140，乘以α1然後通過復用器1120傳送回寄存器。
在說明例中，假定單元代表第二階(j＝1)。生成下列序列λα-(N-1)X+(λα-(N-1))αX2+((λα-(N-1)α)α×3+...
合併各項得到λα-(N-1)+λα-(N-2)X+λα-(N-3)×2+...+λα-1XN-2+λXN-1應當注意該序列中生成的係數與圖10中標準錢搜索單元1000產生的係數一致，除了它們的順序相反(如延遲係數的逆序所表示的)。圖11的錢搜索單元1100應用額外的伽羅華域乘法器(兩個而非1個)，但是在硬體實現中是微不足道的。不再需要LIFO模塊進行反轉以及由於避免填充LIF0所需要的延遲獲得的優勢和實用性可以抵銷為每個錢搜索單元提供額外的Galios域乘法器的不足。
在一個模塊內將錢搜索和Forney算法組合是一種通常的設計辦法，因為兩種算法都需要運行類似的功能。本發明中的本實施方式的原理如結合圖11所描述的同樣適用於Forney模塊單元，因為Forney算法使用非常近似的硬體來處理差錯數量多項式。本領域技術人員應當了解本發明原理可以擴展到Forney模塊單元和錢/Forney模塊單元的設計中。
許多現存系統使用「非定製」集成電路對裡德-所羅門碼進行編解碼。這些IC趨於支持一定數目的可編程性(例如RS(255，k)，其中t為1到16個碼元)。最近的趨勢是VHDL和Verilog設計(邏輯核或智慧財產權核)。標準IC具有大量優點。邏輯核能夠集成在其它VHDL或Verilog組件上，並綜合到FPGA(現場可編程門陣列)或ASIC(專用集成電路)-這允許所謂的「片上系統」設計，即，在單個IC上組合多個模塊。取決於產量，邏輯核常常比「標準」IC明顯降低了系統費用。
儘管本發明描述了硬體實現的情況，但是本發明原理不應被視為受此限制。直到最近，實時軟體實現需要大量的計算功能，但是最簡單的裡德-所羅門碼的除外(如碼字的值為t)。軟體實現裡德-所羅門碼的主要困難在於通用處理器不支持伽羅華域數學運算。例如，在軟體中執行伽羅華域的乘法需要對0測試，兩個對數表的查找，模加法(modulo add)，反對數表查找。然而，處理器性能的增長以及細心的設計意味著軟體實現也能夠以相對高的數據率工作。
儘管本發明還已經根據典型的實施方式和/或構成進行了描述，在本發明公開的範圍內還可以進一步改進。本申請試圖保護使用一般原理的對本發明的任何改變、應用或改進。而且，本申請意圖保護落入本發明所屬的公知常識以及落入權利要求中的限制範圍內的對本發明公開內容的偏離。
權利要求
1.在用於碼字的差錯檢測的解碼器中，一種用於計算單個差錯位置多項式係數的方法，該係數根據與所述單個差錯位置多項式係數對應的單元中的所述碼字而生成，所述方法包括步驟接收與所述碼字對應的差錯位置多項式係數(1110)；在與所述碼字的處理對應的第一個時鐘周期中，通過具有負指數部分(1150)的伽羅華域乘法器乘以所述差錯位置多項式係數(1110)，其中所述負指數部分是與所述單元對應的階數(j)和所述碼字長度(N)的函數，所述的乘法步驟的結果為單元輸出；以及使用具有正指數(1140)的伽羅華域乘法器在隨後的N-1個時鐘周期內，迭代乘以所述單元輸出，其中所述正指數是所述階數(j)的函數。
2.根據權利要求1的方法，其中所述的單元是錢搜索模塊中的錢搜索單元。
3.根據權利要求1的方法，其中所述的單元是Forney算法模塊的Forney算法單元。
4.根據權利要求1的方法，其中所述單元是錢/Forney模塊中的Forney算法單元。
5.根據權利要求1的方法，其中所述解碼器是裡德-所羅門解碼器。
6.在用於檢測碼字差錯的解碼器中，一種用於計算單個差錯位置多項式係數的方法，該係數根據與所述單個差錯位置多項式係數對應的單元中的所述碼字而生成，所述方法的操作通過以下等式的參數進行xi=j=0tj-j(N-1)]]>當i＝0；xi=j=0tjj]]>當i＝1，2，...，(N-1)；其中，Xi是第i個差錯位置的根，t比差錯位置多項式對應的係數總個數少1，Λj是第j個差錯多項式係數，N是碼字長度，α是伽羅華域元素；以及j是與所述單個差錯位置多項式係數對應的階數。
7.一種用於計算單個差錯位置多項式係數的設備，所述係數由與所述單個差錯位置多項式係數相對應的單元中的碼字而產生，所述設備引入用於所述碼字的差錯檢測的解碼器，所述設備包括用於接收與所述碼字對應的差錯位置多項式係數(1110)的裝置；通過具有負指數(1150)的伽羅華域乘法器，在與所述碼字處理對應的第一個時鐘周期中，用於和所述差錯位置多項式係數(1110)相乘的裝置，其中所述負指數是與所述單元對應的階數(j)以及所述碼字長度(N)的函數，所述的相乘的結果得到單元輸出；以及用於通過具有正指數部分(1140)的伽羅華域乘法器在隨後的N-1個時鐘周期中迭代乘以所述單元輸出的裝置，其中正指數部分是所述階數(j)的函數。
8.根據權利要求7的設備，其中所述的單元是錢搜索模塊中的錢搜索單元。
9.根據權利要求7的設備，其中所述的單元是Forney算法模塊的Forney算法單元。
10.根據權利要求7的設備，其中所述單元是錢/Forney模塊中的Forney算法單元。
11.根據權利要求7的設備，其中所述解碼器是裡德-所羅門解碼器。
全文摘要
一種結合了改進的錢搜索單元(1100)的解碼器和解碼方法，其降低了存儲需求和延遲時間。現有技術的錢搜索單元以迭代的方式處理差錯位置多項式係數，起始的α指數為「0」，α隨著每個時鐘周期減小，直到指數減到－j(N－1)。在改進的錢搜索單元(1100)中，α指數起始值為－j(N－1)，隨著每個時鐘周期增至0。因此，在第一個時鐘周期期間，多項式係數(1100)通過預乘法器(1150)相乘，轉送到復用器(1120)，並且發送到寄存器(1130)以便存儲。在後續時鐘周期內，寄存器(1130)的輸出被轉送到另一個乘法器(1140)，然後通過復用器(1120)發送回寄存器(1130)。
文檔編號G06F11/10GK1636324SQ03802640
公開日2005年7月6日 申請日期2003年1月22日 優先權日2002年1月23日
發明者L·R·小利特溫, D·韋萊斯 申請人:湯姆森許可公司