糾錯編碼解碼方法和利用這種方法的電路的製作方法
2023-07-01 18:08:06
專利名稱：糾錯編碼解碼方法和利用這種方法的電路的製作方法
技術領域：
本發明涉及糾錯編碼解碼方法及其電路，特別是涉及在數據傳送或數據記錄等的數據發送中，對由比信息符號大的符號所構成裡德-所羅門代碼進行編碼和解碼的方法以及為實現這種方法的電路。
通常在傳輸數字信息時經常都要利用糾錯碼。例如在文獻「編碼理論」(今井秀樹著，電子情報通信學會編，平成2年3月15日初版發行)中，揭示出各種各樣的糾錯編碼解碼方法。其中，在裡德-所羅門代碼以8比特作為符號進行的符號糾錯方面，與計算機或數字裝置的適配性很好，適用於很多傳輸信息和記錄信息等的裝置。
另一方面，快速存貯器在能寫入抹除方面，作為即使設有電源時也能保存數據、而且能進行高於DRAM的高度集成化的設備受到注意，可望被作為存貯器磁碟來加以應用。但是，快速存貯器在重複進行寫入和抹除時會破壞內部單元，因而存在損壞數據的可能性。因此，在將數據記錄到快速存貯器的情況下，多半要採用糾錯碼，而在進行數據抹除時因為數據全都成為「1」，即以對此作檢驗來進行時抹除的確認。
一般，在於磁碟存貯器中記錄數據的情況中，以512位元組信息數據作為一個扇區來加以存貯。而由於存貯器中以8比特為單位進行存貯，故採用以8比特作為一個符號的裡德-所羅門代碼。但，在以8比特作為一個符號的裡德-所羅門代碼中，因為代碼長一般僅只取為255，所以採用分成為多個代碼字的方法。
對此，例如該代碼長一般可能為1023個符號，依靠採用以1個符號為10比特的裡德-所羅門代碼，即利用由1個代碼字的裡德-所羅門代碼來保護1扇區的數據的方法。
圖15是表示這樣的已有糾錯編碼解碼方法中的代碼結構的說明圖，專門列示裡德-所羅門代碼(418，410)。
其中，「418」為代碼符號長，「410」為信息長，可能進行4個符號的校正。在圖15中，30表示壓縮代碼部分，31表示實際信息數據符號部分，32表示檢驗符號部分，36為偽符號部分。
圖15所示的裡德-所羅門代碼原來是碼長為1023個符號的代碼，其中，設壓縮代碼部分30的605個符號為0。而如以1扇區為512位元組時，即成為4096比特，在10比特/符號時，就差4比特。因此另外加進4比特的偽符號部分36，從而實際信息數據符號部分31成為410個符號，將檢驗符號部分32生成10位元組的8個符號。
下面利用圖16說明生成圖15中裡德-所羅門代碼的檢驗字節的編碼電路。這裡像通常快速存貯器中進行處理那樣數據輸入以8比特為單位，檢驗符號輸出也以8比特為單位。在圖16中，22為8比特結構的信息數據輸入端，19為8比特/10比特轉換電路，23為GF(2E10)上的裡德-所羅門代碼的編碼電路，26為8比特檢驗符號輸出端，29為10比特/8比特轉換電路。
下面說明圖16結構的操作。編碼電路23中生成裡德-所羅門代碼的檢驗符號。為此預先將編碼電路23清「0」。
首先，由信息數據輸入端22輸入8比特的信息數據，送至8比特/10比特轉換電路19。在8比特/10比特轉換電路19中，如存儲10比特的信息，就將該信息輸入到編碼電路23。
在包含圖15中的偽符號部分36的4比特的實際信息數據符號部分31被全部輸入到編碼電路23中時，就得到8個符號(80比特)的檢驗符號部分32。亦即無需計算壓縮代碼部分30。
檢驗符號部分32通過10比特/8比特轉換電路29從高位開始進行10比特/8比特轉換，檢驗字節數據每次8比特由檢驗符號輸出端26輸出。亦即，10位元組的數據被作為檢驗符號輸出。
下面利用圖17說明已有的解碼方法，特別關於校正子計算的說明。隨便說明，圖17的結構是設想為快速存貯器，也含有數據抹除檢驗功能。在圖17中，1為輸入8比特接收信信號數據的數據輸入端，6為GF(2E10)上的有限域(伽羅區域)加法電路，7為10比特寄存器，8為GF(2E10)上的有限域係數乘法電路，9為校正子輸出端，20為檢測8比特數據是否全都為「1」、亦即是否為16進位碼「FF」的FF檢驗電路，21為抹除檢測標誌輸出電路。
首先，作為糾錯的解碼，預先將寄存器7加以清O。由數據輸入端1輸入的接收信號數據被輸入到8比特/10比特轉換電路19。在此8比特/10比特轉換電路19中如存放有10比特的數據的話，就將此信息在有限域加法電路5中與有限域係數乘法電路8的輸出作有限域加法運算。而後將加法結果輸入給寄存器7。並將寄存器7的輸出發送到有限域係數乘法電路8的輸入端。
在對圖15中的實際信息數據符號部分31和檢驗符號部分32全都輸入時的寄存器7狀態成為校正子Sj時，由校正子輸出端9輸出。
此時，裡德-所羅門代碼的起頭數據符號為「C」，即使符號單位上產生遣漏，但由於裡德-所羅門代碼為循環碼，通過校正仍可能照所遺漏的原樣解碼。
另一方面，在快速存貯器中抹除數據的情況下，數據就都成為「1」，就有必要檢查這一抹除過程的進行是否正常。
此時，由數據輸入端1進入的8比特數據被送入FF檢驗電路20，如檢測到1比特為「0」，即由抹除檢驗標誌輸出端21輸出異常標誌。
按照過去，在進行糾錯時，在作為積代碼結構的解碼中，一經存儲進存貯器之後即進行解碼。圖18為表示這樣的情況的例子的電路方框圖。圖中，59為緩衝存貯器，60為校正子電路，63為求取差錯位置和大小的差錯位置/大小檢測電路，64為校正電路，66為校正後的解碼數據輸出端。
在上述結構中，由數據輸入端1輸入的編碼數據存放在緩衝存貯器59中，然後解除其交錯狀態作為編碼序列輸入到校正子電路60。根據這樣得到的校正子信號由差錯位置/大小檢測電路63求取差錯位置及其大小，校正電路64讀出緩衝存貯器59中所存在的差錯位置的數據，進行差錯校正後寫入緩衝存貯器59。在積代碼等中，重複進行多次這種解碼操作，在全部解碼後由解碼數據輸出端65輸出。
在以一個緩衝存貯器進行上述這樣的操作時，必須分時進行接收信號數據的輸入、向校正子電路的輸出、差錯位置的數據的輸入輸出、校正後的數據的輸出等。特別是在進行積代碼等的多次重複解碼時，就有必要採用能作高速存取的緩衝存貯器。
而為保證存貯器等的可靠性，最好採用一比特糾錯、二比特差錯檢測代碼。(72、64)二進位的線性代碼為其典型示例。這裡「72」為比特符號長，「64」為比特信息長。亦即，檢驗比特為8比特。
這樣的代碼的解碼電路，往往對全部代碼比特數據作並行處理解碼，而且多半帶有用於檢測差錯的電路。對於這樣的代碼，例如在文獻「容錯系統論」(當麻喜弘編著，電子情報通信學會，平成2年6月10日初版發行)中有介紹。
圖19為表示歷來的(72、64)二進位線性代碼的解碼電路示例電路方框圖。圖中，66為由校正子電路60輸入信號的8輸入「或」電路，67為由差錯位置/大小檢測電路63輸入信號的72比特輸入「或非」電路，68為接收8輸入「或」電路66和72比特輸入「或非」電路67的輸出的2輸入」與」電路，49為由2輸入「與」電路68輸出不可校正檢測標誌的不可校正檢測標誌輸出端。
在上述這樣的結構中進行存貯器的糾錯時，因為數據母線為並行結構，所以72比特的代碼數據被一次輸入到校正子電路60。在校正子電路60中從接收信號數據生成8比特的校正子信息加以輸出。差錯位置/大小檢測電路63檢驗包含由奇偶檢測陣列確定的檢驗比特的各比特位置的8比特的格式與校正子信息是否一致。其結果被送到72比特輸入「或非」電路67和校正電路64。此時，將信息部分的64比特送至校正電路64。在校正電路64中對接收到各信息比特和各比特的差錯檢測結果分別進行「異或」邏輯運算，其結果由解碼數據輸出端65輸出。
由此代碼進行針對二比特差錯的糾錯。這在校正子信息非「0」、且與72比特的碼長的奇偶檢驗陣列的格式不相等時，就成為不可校正差錯檢測。8輸入「或」電路66檢驗校正子信息的8比特為非「0」，72比特輸入或「非」電路67檢驗1比特為無差錯，在2輸入「與」電路68中取二檢驗結果的邏輯積從不可校正檢測標誌輸出端49輸出。
有關上述這樣的結構及作用，例如在日本專利公開昭53-5099(D.W.ブライス、1972.11.8.申請)中曾有說明。
已有的糾錯編碼解碼方法由於為上述那樣構成，遺留有下述的各種問題。
第一個問題是，對於8比特的輸入輸出數據，例如在採用1符號10比特的裡德-所羅門代碼時，必須有8比特/10比特轉換電路和10比特/8比特轉換電路，符號時鐘也就必須產生8比特用和10比特用，因而必須有比特時鐘。
第二個問題是，為進行快速存貯器的抹除的檢測，必須要有檢測全部為「1」的特殊電路。
第三個問題是，即使裡德-所羅門代碼在符號單位上產生遺漏，由於裡德-所羅門代碼的循環碼，所以有可能通過校正進行遺漏的按原樣的解碼。
第三四問題是，在將編碼數據存入存貯器的情況下，由於存貯器對接收數據的輸入、解碼電路的輸入輸出、解碼結果的輸出進行分時存取，在要作多次解碼時就必須有高速存取的存貯器。
第五個問題是，在存貯器糾錯中用的(72、64)二進位線性代碼中，為輸出不可糾錯標誌，必須要有對72比特的1比特差錯檢測和對其結果進行邏輯運算的電路，為此必然會帶來很大的時間延時，同時還必須有用作邏輯運算的多個門數量的電路。
本發明的目的即為解決上述這樣的已有技術中的問題，依靠僅只處理8比特符號同時能省去冗長的電路，來提供一種結構簡單的能進行糾錯和編碼解碼而且可靠性良好的糾錯碼編碼方法及其電路。
為達到上述目的，根據本發明的一種糾錯編碼/解碼方法，用於對模元數比信息符號類數多的有限域中由「大符號」組成的裡德-所羅門代碼(以下簡稱RS碼)進行編碼和解碼，其特徵在於，它包括下列步驟傳送步驟，將偽數據放在RS碼的由超出所述信息符號位長度的「大符號」組成的部分，進行編碼，編碼之後只傳送此偽數據除去之後剩下的位數據；加入步驟，在解碼側，將偽數據作為不足以形成所述RS的符號的位數據先加入信息部分的符號中；傳送步驟，傳送檢驗符號時，無須修正就傳送所述「大符號」中與信息符號位長度相應的部分；傳送步驟，傳送檢驗符號時，RS碼由超出所述信息符號長度的「大符號」組成的部分在所述超出部分從多個信息符號收集、且分組成相當於所述信息符號位長的位長並傳送之後一起傳送；進行解碼時，加上虛擬位，並無須修正對檢驗符號對應於先傳送的所述「大符號」中信息符號位長度的部分進行校正子計算，並根據檢驗位數據對所述在超出後來傳送的所述「大符號」中所述信息符號的位長度的部分中一起傳送的數據進行校正子計算；根據先得出的信息和檢驗符號對所述校正子的計算結果求出有限域之和，並根據超出後來傳送的所述信息符號的位長度的數據對所述校正子的計算結果求出有限域之和。
根據本發明的一種RS碼編碼電路，所述RS碼由信息數據符號組成的「大符號」構成，所述電路的特徵在於，它包括加法器和輸出器，加法器將偽數據加入信息符號中，輸出器選擇並輸出檢驗符號對應於信息符號位長度的部分和檢驗符號超出分組成相當於信息符號位長度的位長度的位長度部分，作為檢驗符號數據。
根據本發明的一種RS碼解碼電路，所述RS碼由信息數據符號組成的「大符號」構成，所述電路的特徵在於，它包括加法器、校正器和求和器，加法器將偽數據加入信息符號和檢驗符號對應於信息符號位長的部分中，校正器對檢驗符號超出信息符號位長度的部分進行校正子計算，求和器對先得出的信息符號檢驗位組中信息符號位長度相應的所述部分的校正子和所述校正器得出的校正子求出有限域之和。
根據本發明的由信息數據符號組成的「大符號」構成的RS碼的糾錯解碼方法，其特徵在於，它包括下列步驟對檢驗符號超出信息符號位長度的部分作為刪除部分進行處理，並對此部分進行刪除校正；和在對應於所述進行所述刪除校正時得出的刪除部分的錯誤碼形只出現在超出所述刪除部分中信息符號位長度的部分時，確定在對應於所述信息符號位長度的部分中沒有出現誤差。
根據本發明的糾錯編碼/解碼由信息數據符號組成的「大符號」構成的RS碼的方法，其特徵在於，它包括下列步驟傳送對應於檢驗符號超過信息符號位長度的各部分的多個部分；和在解碼側，根據所述多個相對於各部分超出信息符號位長度的檢驗符號相應的各部分傳送的數據進行多數判定，由此對信息符號解碼。
根據本發明的糾錯編碼/解碼由信息數據符號組成的「大符號」構成的RS碼的方法，其特徵在於，它包括下列步驟用各檢驗位為信息數據符號長度的整數位的任意糾錯碼對各部分超出信息符號位長度的檢驗符號的各部分進行編碼；和在解碼側，通過相對於各部分超出信息符號位長度的檢驗符號相應的各部分對所述任意糾錯碼進行解碼來對信息符號進行解碼。
根據本發明的一種編碼電路，其特徵在於，它包括一個有限域求和電路，在編碼過程中將通過根據原先取得的偽碼形輸入的信息和檢驗符號得出的有限域求和結果作為經編碼的檢驗符號；和校正數據輸入器，輸入經校正的數據。
根據本發明的一種解碼電路，其特徵在於，它包括一個有限域求和電路和一個校正數據輸入器，有限域求和電路在解碼的過程中取代碼數據已傳送的校正子數據和基於原先獲得的偽碼形的校正子數據的有限域求和結果作為經編碼的校正子數據，校正數據輸入器則輸入經校正的數據。
為達到上述目的，根據本發明的糾錯編碼解碼方法，當進行糾錯代碼的編碼和解碼時，將信息和檢驗字節全部作0/1反相後送出，在解碼時將所讀出的數據由0/1反相後進行解碼的處理。
為達到上述目的，根據本發明的糾錯編碼解碼方法中提出，在壓縮碼長後的糾錯代碼的編碼和解碼中具有以使信息和檢驗符號全都成為「1」的數據作為代碼那樣，在壓縮部分增加數據格式來生成檢驗符號，並僅只發送信息和檢驗符號的處理；和在解碼側，將相當於壓縮部分的數據的校正子數據增加到由信息和檢驗符號生成的校正子數據增加到由信息和檢驗符號生成的校正子信息上的處理。
為達到上述目的，根據本發明的糾錯編碼解碼方法中提出，在壓縮碼長的糾錯代碼的編碼和解碼中具有在信息的一符號前的壓縮部分增加該代碼的固有數據格式生成檢驗符號，僅只發送信息和檢驗符號的處理；和在解碼側，將相當於增加在壓縮部分的代碼固有數據格式的校正子信息加到由信息和檢驗符號所生成的校正子信息上的處理。
為達到上述目的，根據本發明的糾錯解碼電路中提出，在將接收到的經糾錯編碼的數據由輸入單元存入緩衝存貯器並按前述糾錯代碼進行多次解碼操作的解碼電路中設置有將經糾錯編碼的數據存入緩衝存貯器並進行多次解碼操作的過程，對輸入數據進行校正子計算同時對緩衝存貯器的數據進行校正子計算的校正子計算手段；和選擇二個校正子信息同時作差錯校正進行解碼的手段。
為達到上述目的，根據本發明的糾錯編碼解碼方法中提出，在糾錯編碼和解碼中，具有在進行1比特糾錯、2比特差錯檢測的(76、64)二進位線性編碼中，僅以「1」、」3」、「7」來處理奇偶檢驗陣列加權的過程。
在上述方法中，根據本發明的糾錯編碼解碼方法，例如以8比特信息作為1個符號，對於由比其大的符號構成的裡德-所羅門代碼，不足的比特給於偽數據，作成1個符號，由此生成的裡德-所羅門代碼的檢驗符號以與信息相同的8比特連續在信息符號上進行發送，剩餘的檢驗符號的比特由後面匯總加以發送，在解碼中，在8比特的信息符號和8比特的檢驗符號上增加偽比特後進行校正子計算，對後續的剩餘部分匯集得的檢驗符號的比特數據進行校正計算。
在上述方法中，根據本發明的糾錯編碼解碼方法，例如在將信息和檢驗符號全部反相後存入快速存貯器等中，在讀出時將其全部反相加以解碼，由此即可能實現以快速存貯器的抹除狀態的全「1」來作為全「0」的編碼數據。
在上述方法中，根據本發明權利要求9中記述的糾錯編碼解碼方法，以壓縮部分中的信息和檢驗字節全部作為「1」的編碼來設定偽信息，在解碼側，將相當於壓縮部分數據的校正子數據附加到由信息和檢驗符號生成的校正子信息上來進行解碼。
在上述方法中，根據本發明的糾錯編碼解碼方法，在壓縮部分的起頭加以該代碼的固有數據，編碼中根據該固有數據生成檢驗符號，僅發送信息和檢驗符號，而在解碼中將相當於固有數據格式的校正子信息附加到由信息和檢驗符號生成的校正子信息上來進行解碼。
在上述方法中，根據本發明的糾錯解碼電路，選擇對應於輸入數據的校正子信息和對應於緩衝存貯器的數據的校正子信息，根據這些進行糾錯和解碼，由此來減少緩衝存貯器的存取次數從而有可能使緩衝存貯器低速化。
上述方法中，根據本發明的糾錯編碼解碼方法，在糾錯編碼和解碼中進行1比特糾錯、2比特檢測誤差的(76、60)二進位線性編碼中，以「 1」、「3」、「7」來構成奇偶檢驗陣列的加權，在檢測不可糾正差錯時，求取校正子信息的加權，根據此加權值進行不可糾正差錯檢測。
圖1為用於實現本發明實施例1的糾錯編碼解碼方法的電路方框圖；圖2為用於實現本發明實施例2的糾錯編碼解碼方法的電路方框圖；圖3為本發明實施例3的糾錯編碼解碼方法中的解碼電路的第一例電路方框圖；圖4為本發明實施例3的糾錯編碼解碼方法中的解碼電路的第二例電路方框圖；圖5為本發明實施例4糾錯編碼解碼方法中的進行同步判斷的電路方框圖；圖6為本發明實施例3的糾錯編碼解碼方法中，對應於圖8中所示的代碼結構的編碼電路的電路方框圖；圖7為說明本發明實施例3的糾錯編碼解碼方法中的編碼電路的其他示例的方框圖；圖8為在實行本發明實施例3時的(520、512)裡德-所羅門代碼的構成法的說明圖；圖9為在實行本發明實施例4時的代碼的構成法的說明圖；圖10為表明圖1結構中的校正子數據校正電路的第一例的電路方框圖；圖11為表明圖1結構中的校正子數據校正電路的第二例的電路方框圖12為用於實現本發明實施例6的糾錯編碼解碼方法的電路方框圖；圖13為用於實現本發明實施例7的糾錯編碼解碼方法的電路方框圖；圖14為表明圖13的偶數和加權」5」檢測電路的示例電路方框圖；圖15為歷來的糾錯編碼解碼方法中的代碼的結構示例的說明圖；圖16為生成圖15的裡德-所羅門代碼的檢驗字節的編碼電路的電路方框圖；圖17為歷來的糾錯編碼解碼方法中的解碼電路的電路方框圖；圖18為歷來的糾錯編碼解碼方法中進行積代碼結構的解碼的電路的電路方框圖；和圖19為歷來的糾錯編碼解碼方法中，(72、64)二進位線性代碼的解碼電路的電路方框圖。
圖1為實現本發明實施例1的糾錯紡碼解碼方法的電路方框圖，特別表示直到壓縮1符號10比特的(1023，1015)裡德-所羅門代碼的(520，512)裡德-所羅門代碼的編碼出差運算的解碼電路。
圖中，2為輸入作為1符號中剩餘比特的2比特偽數據(例如，「00」)的偽數據輸入電路，3為根據檢驗符號的超過部分(2比特×8符號)生成校正子數據的校正子數據校正電路，4為選擇輸出10比特的2個數據的選擇器，5為已有的GF(2E10)上的有限域加法電路，7為10比特寄存器，8為GF(2E10)上有限域係數乘法電路，6為選擇10比特的二個數據的選擇器，9為校正子信息輸出端，10為被連接到數據輸入端1的0/1反相電路。
順便提出，此實施例1解決前述的第一個和第二個問題。
現在按上述那樣的結構，對其操作加以說明。
在圖1的結構中，編碼數據全部以0/1反相狀態被記錄。亦即，由數據輸入端1輸入的編碼數據為以8比特的單位反相後的數據。此數據在0/1反相電路10中被加以反相。亦即，在記錄數據的全部比特為「1」的情況時，代碼反相全部成為「0」。因而在快速存貯器的抹除中，由於抹除數據全部成為「1」，作為0/1反相電路10的輸出就可能成為全部為「0」的代碼的校正子檢測。
亦就是第二個問題的解決。
下面說明對應於第一個問題的操作。
首先，早先被發送的512位元組信息，對作為剩餘比特的2比特例如作為「0」加以編碼，而在接收信號方也由偽數據輸入電路2增加偽數據(例如「0」)，作為10比特的符號通過選擇器4被輸入給有限域加法電路5。
有限域加法電路5的另一個輸入是從初始值作為「0」的寄存器7輸出，通過有限域係數乘法電路8，經由選擇器6輸出的數據。此電路系統進行與歷來的校正子電路同樣的運算。
接著，輸入8個符號檢驗字節，這僅對與信息符號相同的8比特數據加以輸入，與信息符號同樣，由偽數據輸入電路2增加偽數據(例如「0」)作為10比特的符號由選擇器4被輸入到有限域加法電路5，與先前的信息符號同樣地被進行校正子計算。
最後，作為代碼序列，各檢驗符號中的多餘比特2比特被匯集在8比特單位，作為8比特數據輸入2個符號。此數據被輸入到校正子數據校正電路3，成為a4j(d7a3j＋d6a2j＋d5aj＋d4)＋(d3a3j＋d2a2j＋d1aj＋d0)，進行GF(210)的有限域係數乘法和加法運算。這裡，di為以16進位表示的000(HEX)、100(HEX)、200(HEX)、300(HEX)中的一個。由此得到的校正數據與到前一檢驗符號為止的校正子數據在有限域加法電路5中相加。順便指出，前一檢驗符號為寄存器7送出的通過選擇器4經由選擇器6輸出的符號。然後，有限域加法電路5的加法結果再次被存貯到寄存器7中。而且，它作為校正子數據Sj由校正子輸出端9輸出。
現在根據圖10的電路方框說明校正子數據校正電路3的結構的第一例子。圖中，37為8比特接收信號數據輸入端，38～40為GF(210)上的有限域係數乘法電路，41～44為GF(210)上的有限域加法電路，45為10比特寄存器，46為GF(210)上的有限域係數乘法電路，47為校正數據輸出端。
在以上這樣的結構中的操作說明如下。
在此例中，針對8比特的輸入，4個符號的檢驗符號的高位2比特被一次輸入，這包含2個符號。以8比特由接收信號數據輸入端37輸入的符號，對此，被分別輸入到具有檢驗符號的次數依次從高起的a3j、a2j、aj的係數的有限域係數乘法電路38～40，將其結果在有限域加法電路41～43進行加法計算。
這些，由於僅高位2比特成為「1」，所以關係到低位8比特的邏輯電路可省略，從而能實現較小規模的電路。
有限域加法電路43的結果被輸入到有限域加法電路44，與有限域係數乘法電路46的輸出相加，再被輸入到寄存器45。寄存器45使初始值為」0」，將其輸出輸入到有限域係數乘法電路46。有限域係數乘法電路46能完成與圖1中的有限域係數乘法電路8相同的職能，但進行有限域係數乘法電路8的4倍的係數乘法運算。這是因為在8比特的數據上被分配以4個符號的檢驗字節的高位2比特。下一檢驗符號的高位2比特數據也被作同樣處理後，存貯進寄存器45中。經過上述這樣的處理，即完成校正數據的計算。
下面根據圖11的電路方框圖說明對校正子數據校正電路3的結構第二示例。圖11的結構為從圖10中所示結構去除寄存器45和有限域加法電路44、另外加入選擇器48形成的。
下面說明上述這種結構的操作。
圖11結構中直到有限域加法電路43為止的操作與圖10的情況是同樣的。
另一方面，對早先輸入的符號所得到的有限域加法電路43的輸出，通過有限域係數乘法電路46，經由選擇器48，由校正數據輸出端47輸出。
此結果通過圖1的選擇器4，與經由選擇器6輸出的寄存器7的輸出結果，在有限域加法電路5中相加，存入寄存器7。而後，由下一8比特符號數據所得的有限域加法電路43的輸出，按原樣通過選擇器48，進行與前面符號同樣的操作，由此來得到校正子信息。
圖2為實現本發明實施例2糾錯編碼解碼方法的電路方框圖，特別謀求解決第二個問題。
實施例1中因為是將代碼數據反相後記錄的，因而存在有無法區別是信息全部為「0」的代碼、還是抹除後全都成為「1」的情況的問題，圖2的結構即為解決這一問題。
圖2中，11為對應於8比特的2輸入數據的選擇器，選擇是通過0/1反相電路10取入還是直接取入由數據輸入端1來的輸入。
上述這樣的結構，通常情況下通過選擇器11對數據輸入端1來的接收信號數據進行直接取入校正子計算，只有在快速存貯器的抹除檢驗時才由選擇器11選擇取出通過0/1反相電路10輸入的數據進行校正子計算。
而且這裡通常的編碼數據不進行0/1反相即加以存貯。
不過，此實施例2示例表明的是對0/1反相電路10和選擇器11分開控制的結構，但兩者加以組合的功能亦可利用」異或」電路來實現是大家所熟知的。
上述實施例1和2中，說明的是針對第二個問題採用0/1反相電路來檢驗快速存貯器的抹除、亦即全「1」的狀態的方法，但在第三實施例中提出的是，通過僅對校正子選擇器7設定初始值來進行快速存貯器的抹除的檢驗的方法。此實施例3針對第三個問題提出，即使發生符號單位的遺漏也能對之進行檢測的方法。
圖8表示實現此實施例3時的(520、512)裡德-所羅門代碼的組成方式。應看到的是，圖8的代碼組成也能運用於解決實施例1中的第一問題。
圖8中，30為壓縮代碼部分，31為實際信息數據符號部分，32為檢驗符號部分，33為在信息和檢驗符號全為「1」時作成編碼所插入的偽符號，34為將10比特檢驗符號中的各高位2比特匯集附加到代碼序列後的附加檢驗符號。
以10比特作為1個符號的裡德-所羅門代碼，通常可取到1023個符號的代碼長。因而與圖15的已有例不同，將快速存貯器的存貯單位的8比特實際信息數據符號部分31作為1個符號，在高位2比特處插入作為偽數據的例如「0」。由此就可不必進行8比特/10比特轉換。
由此信息符號生成的檢驗符號部分32，為每1符號10比特，不保證高位2比特為固定數據。因而，僅將低位8比特連續地配置到8比特信息符號，高位2比特匯集成8比特單位，在作為檢驗字節的檢驗符號部分32之後，作為剩餘符號配置以2個符號的附加檢驗符號34。這些操作可作為符號時鐘處理，全部操作就可能作為符號時鐘。
下面按照圖8說明成為解決第二、第三問題的策略的代碼結構。例如，作為1個符號10比特的(1023、1015)裡德-所羅門代碼的示例，其原始多項式為P(X)＝X10＋X3＋1生成多項式為G(X)=j=SOS515(X-aj)]]>其中
aj＝β491β為P(X)的原始元。在這一情況下，將偽數據的起始部分作為0號，亦就是說實際信息符號部分31的起頭作為503號，而作為壓縮編碼部分30的符號部分中偽符號33，在278號位置設定19D(HEX)、454號設置OAB(HEX)，這樣在圖8中的實際信息數據符號部分31全為「1」、信息符號的高位2比特部分作為「0」的情況下，檢驗符號部分32的8比特就全部成為「1」。亦即，可能將成為快速存貯器的抹除狀態的全部為「1」的狀態看作為圖8中的(520，512)裡德-所羅門代碼的代碼。
下面說明圖8中所示的代碼結構中的編碼電路。
圖6為表明對應於圖8中的代碼結構的編碼電路的構成例的電路方框圖。圖中，22為8比特信息數據輸入端，2為信息符號的高位2比特的偽數據輸入電路，23為(例如)可設置線性反饋移位寄存器型式的初始值的GF(210)上的編碼電路，24為進行編碼電路23的寄存器的初始值設定的編碼電路初始值數據設定電路，25為將檢驗符號的低位8比特或集中高位2比特成為8比特符號作為輸出而進行選擇的選擇器，26為輸出檢驗字節數據的檢驗符號輸出端。
由圖可清楚看到，此電路結構在運算量、電路規模上基本與現有的編碼電路無大變化。
下面說明上述這樣結構的操作。
首先，在8比特信息數據進入信息數據輸入端22之前，輸入圖8中的偽符號33，由編碼電路23進行計算。然後，由於偽符號33為固定值，所以在隨後接著的信息數據被輸入之前的編碼電路中的狀態可以預先計算。例如，將編碼電路23作成在輸入歷來所採用那樣的信息符號時得到檢測符號的線性反饋寄存器型式，將檢驗符號看作是多項式次數的係數，如由高次起看該計算過程中成為的寄存器狀態，即成為174(HEX)、OB6(HEX)、105(HEX)、OEA(HEX)、26B(HEX)、260(HEX)、18F(HEX)、OD7(HEX)。因此就可以將此計算結果作為初始值，由編碼電路初始值數據設定電路24加給編碼電路23的寄存器。因而，用於賦於這樣的初始值的結構，例如就可採用像在觸發器電路的置位端和復位端直接地設定數據那樣的結構來實現。
接著，由信息數據輸入端22輸入的8比特信息數據，被2比特偽數據輸入電路2，增加2比特的例如「0」成為10比特的符號數據形式，輸入給編碼電路23。然後，在512個符號的8比特信息數據輸入結束時，編碼電路23中就得到8個符號的檢驗符號。其中該符號為1符號成為10比特的符號。為此，首先是各檢驗符號的低位8比特通過選擇器25後由檢驗符號輸出端26輸出，然後將各檢驗符號的高位2比特匯集成8比特的單位通過選擇器25後由檢驗符號輸出端26輸出。因此就有可能以8比特的信息數據的符號時鐘來處理全部的數據。
下面說明針對第二、第三問題的解決策略。圖7為用於此的結構示例，27為由8比特「異或」門構成的有限域加法電路，28為給有限域加法電路27加以校正數據的檢驗符號校正數據設定電路。如由圖中可看到的，這一電路在選擇電路25的輸出之前的結構與圖6的結構大致相同。不過，沒有用於設定初始值的電路，編碼電路23在輸入信息數據之前被清「0」。
下面說明上述這樣結構中的操作。
在圖7的結構中除將編碼電路23的初始值設定為「0」外，基本上與圖6的結構作同樣操作。而對於被作為固定值所給予的偽符號則作下面這樣的處理。即就是，因為裡德-所羅門代碼為線性代碼，所以對於由初始設定值「0」得到的檢驗符號，也可由檢驗符號校正數據設定電路28通過有限域加法電路27來對圖8中的偽符號33的檢驗符號作有限域加法計算。在此，針對偽符號33的檢驗符號，由高次開始看即成為04A(HEX)、016(HEX)、3AF(HEX)、294(HEX)、125(HEX)、09F(HEX)、02B(HEX)、274(HEX)、由於選擇器25每次輸出8比特，檢驗符號校正數據設定電路28的輸出，由高次開始看也就成為4A(HEX)、15(HEX)、AF(HEX)、94(HEX)、25(HEX)、9F(HEX)、2B(HEX)、74(HEX)、OE(HEX)、42(HEX)。然後，在選擇器25的輸出上由有限域加法電路27將檢驗符號校正數據設定電路28的輸出作有限域相加，再由檢驗符號輸出端26輸出。
下面說明該實施例3中的解碼電路示例。本發明的解碼中，因為在校正子計算上有其特點，所以與實施例1同樣對校正子電路部分加以說明。
圖3為運用於實施例3的解碼電路方框圖，與圖1結構的不同之點是，沒有0/1反相電路10，而代之的是在結構上增加校正子初始數據設定手段12。
下面說明上述這樣結構的操作。
以8比特為單位接收的接收信號數據中，因為不存在圖8中所輸入的偽符號33，所以與圖6的編碼電路中操作相同，預先計算出對應於緊接在寄存器7被輸入信息數據之前的偽信號33的校正子計算的中間結果，當將其設定在校正子初始數據設定手段12中。此時，例如，在與先前例中所示相同的參數中，校正子信息S0～S7被設定為S0＝09C(HEX)，S1＝1FB(HEX)，S2＝026(HEX)，S2＝10F(HEX)，S4＝145(HEX)，S5＝343(HEX)，S6＝248(HEX)，S7＝102(HEX)。
其後的操作與實施例1中的結構，僅僅沒有0/1反相電路10，是同樣的。
下面與圖7中說明的編碼電路同樣地說明在求得對信息數據的校正子信息後在圖8中的偽符號33的校正子數據中進行的校正方法。圖4是表示用於此目的的電路結構的電路方框圖，取代圖6中的校正子初始數據設定手段12，設置以校正子校正數據設定電路14。而13為進行GF(210)上的有限域加法運算的有限域加法電路13，由「異或」門構成。
圖4結構的操作，除校正子電路部分的寄存器7數初始值數據設定會成為「0」外，進行與圖6的結構同樣的運算。
在接收信號數據完全被輸入、得到校正子信息並由校正子信息輸出端9輸出時，將校正子校正數據設定電路14發出的各個圖8中的偽數據的校正子數值在有限域加法電路13中與接收信號數據中的校正子信息相加。此校正數據，例如，對先前示例中的參數中的校正子信息S0～S7，分別設定為S0＝193(HEX)，S1＝2AE(HEX)，S2＝2E4(HEX)，S3＝OD7(HEX)，S4＝34D(HEX)，S5＝17B(HEX)，S6＝OCD(HEX)，S7＝23A(HEX)。
而作為解決第二、第三問題的對策，本發明中由於進行對偽符號33的初始值的設定，除全部為第一狀態的數據外，即使接收信號數據以符號單位發生遺漏，由於已將偽數據部分看作為差錯，所以提高能夠檢測出遺漏的準確度。
而且與實施例2相同地，能夠僅在快速存貯器抹除時將校正子初始數據設定手段12或校正子校正數據設定電路14作為有關圖8中的偽符號33的校正子數據，通常也可以設定為「0」。
在此實施例中，在使用10比特符號的裡德-所羅門代碼的第一個問題的解決策略上已涉及到第二、第三個問題，但在例如8比特符號的裡德-所羅門代碼的壓縮代碼等方面，此實施例同樣也能實現解決第二、第三個問題的策略。
下面對本發明實施例4的糾錯編碼解碼方法加以說明。圖9為實現本實施例的代碼結構示例，是特別對圖8所作的改進。圖9中，35表示信息數據鄰近的壓縮代碼的代碼原始數據插入符號部分。
本實施例雖與實施例3中所示的解決第二、第三問題的相類似，但更加強了解決第三問題的策略。
下面對圖9進行說明。在代碼原始數據插入符號部分35的部分中，與圖8同樣地，設定除「0」外的該代碼固有的格式。例如，由K段交錯構成的裡德-所羅門代碼的結構中，在各段中設定由「1」到「K」的數值。
此方法中的編碼方法和解碼方法由實施例3中所說明的圖6、圖7、圖3、圖4的電路結構實現。
下面對圖9的編碼結構中的同步判定方法進行說明。圖5為實現其的結構示例電路方框圖。在圖5的結構中，在校正子信息輸出端9之前的系統，與圖3中結構相同。另一方面，15為求取差錯位置、差錯數值的差錯位置/大小檢測電路，16為檢查是否同步的同步判定電路，17為輸出差錯的位置和大小的差錯位置/大小輸出端，18為送出由同步判定電路16輸出的同步檢驗標誌的同步檢驗標誌輸出端。
下面說明上述這樣結構中的操作。
初始值數據認為是分別設定的所接收信號代碼的所期望的原始數據。根據由此得到的校正子信息輸出端9輸出的校正子信息，在差錯位置/大小檢測電路15中求取差錯位置多項式和差錯數值多項式，採用鏈式檢索來求得差錯位置和差錯大小。在此，雖然一般是進行接收到的裡德-所羅門代碼的代碼長部分的鏈式檢索，但在本實施例中，對含有插入代碼原始數據插入符號部分35的壓縮部分的壓縮代碼部分30也進行檢測。此時，在能加以正確校正的情況下，壓縮代碼長-1的「0」符號運行相連續，並相繼出現代碼原始數據插入符號部分35。由同步判定電路16監測此起頭的插入數據的狀態，如果認為是同步的，即由同步檢驗標誌輸出端18輸出標誌。另一方面，由差錯位置/大小輸出端17輸出包含著同步偏差信息的差錯位置和大小。
如這樣，依靠在壓縮部分的「0」運行和填入壓縮部分的起頭的原始數據，就能不增加代碼長而對符號單位的遺漏進行檢測和加以恢復。
而在實現本實施例的方法中，由於能幾乎按原樣使用實施例3中說明的編碼電路和解碼電路，所以例如在快速存貯器的抹除中採用實施例3的方法，在通常情況下也就可能採取本實施4的方法。
下面說明本發明實施例5的糾錯編碼解碼方法。本實施例對到目前為止所說明的實施例中，特別是對於第一問題的解決策略，提出不完備部分的解決策略。
到此為止已說明的實施例，例如在圖8、圖9那樣的代碼結構的解碼中，在進行判定信息符號位置上的高位2比特偽數據部分中具有差錯時，存在著不可能校正的差錯。
對此，在圖8、圖9中，後面附加的附加檢驗符號34如果使1個符號全部發生錯誤，例如就可能擴散為作為裡德-所羅門代碼的4個符號的差錯，但由於整體上附加的符號數量少，所以準確性也就小。而在出現錯誤時檢測出不可能校正的情況下，以此附加的符號消失來進行消失校正，如此消失位置的差錯的大小僅出現在檢驗符號的高位2比特中，也可以判斷為信息符號中無差錯。亦即，可能按差錯的大小檢測差錯。
而對於將後面附加的高位2比特匯集的符號，也可作為多數次發送信號或多數個符號記錄，而在解碼側作多次解碼的方法。
而作為將後面附加的高位2比特匯集後的符號的信息，也有以處於傳輸形式的例如8比特符號的裡德-所羅門代碼或4比特符號的裡德-所羅門代碼等的第二糾錯代碼進行編碼，在增加其檢驗數據後進行發送或記錄，在解碼側對將後面附加的高位2比特匯集後的符號，以第二糾錯代碼加以解碼後對信息符號進行解碼的方法。
下面對本發明的實施例6加以說明。圖12為實現本發明實施例6的糾錯編碼解碼方法的電路的電路方框圖，是特別針對解決第四問題所用結構的示例。圖中，61為用於輸入接收數據的數據輸入端1所輸入的代碼序列的校正子電路，62為選擇對應於緩衝存貯器59來的數據的校正子電路60的數據和對應於從數據輸入端1來的數據的校正子電路61的數據並輸入給差錯位置/大小檢測電路63的選擇器。至於其他結構，均與圖18的結構相同。
下面說這樣構成的操作。
由數據輸入端1輸入的代碼序列在被存入緩衝存貯器59的同時，被輸入至校正子電路61。校正子電路60對除緊接著接收的代碼序列以外的代碼序列進行校正子計算。
選擇器62分時選擇校正子電路60、61各自的數據後，輸入到差錯位置/大小檢測電路63。在差錯位置/大小檢測電路63中，按照所輸入的校正子信息求取差錯位置和差錯的大小，傳送至校正電路64。校正電路64由緩衝存貯器59中所存放的數據中取入相當於該差錯位置的數據，進行差錯校正再送回緩衝存貯留59。
由此，緩衝存貯器59和校正子電路60的數據存取，減少了輸入代碼長度，因而即使緩衝存貯器59的存取速度較慢亦能適應，而可以使例如歷來以昂貴的SRAM組成的緩衝存貯器59，成為廉價的DRAM。
下面說明本發明的實施例7。圖13為實現本發明實施例7的糾錯編碼解碼方法的電路的電路方框圖，是特別為解決第五問題的結構示例。圖中，51為由校正子電路60輸出的8比特校正子信號，50為由校正子信號51檢測偶數和加權「5」的偶數和加權「5」檢測電路，52為在偶數和加權「5」檢測電路50檢測偶數和加權「5」時輸出信號「1」的偶數和加權「5」檢測信號線，至於其他構成，除72比特輸入「或非」電路67外，與圖19的結構相同。
作為以1比特糾錯2比特進行檢測的代碼構成法有，由奇偶校驗陣列各自不同的奇數加權的比特序列來構成的方法。這在前面舉出的文獻中也有介紹。在(72、64)二進位線性代碼中，奇偶校驗陣列為8比特，但進行各自的奇數加數狀態的組合則成為如下狀態。
加權1＝8加權3＝56
加權5＝58加權7＝8。
而現有是選擇加權「1」、「3」、「5」的狀態，構成(72、64)代碼，但在本實施例中則取加權「1」、「3」、「7」來構成代碼。這時，例如說奇偶校驗陣列即使成為H=111111111111111111110111111000001000100000000000000000000010000000000000111101001110111010001000000111110110010010001000100010000001100010001000111010110001110011101000000110000001001111110110010001000000001010001000100010101000111110011100100011110001001001000001111100001000000101000100110010001100100011001111000101001001000100101001001011110100100000100100110110011000010010001000111000101110001000010100000111111000010000011100010010001010110110101010010000010100110111001111000100100100010001000010110011001001110000011001001000000010110000110010111000011100110011000001]]>也可能成為1比特糾錯2比特的差錯檢測。由此，在校正子計算中，與現有的最小結構相比也不改變延遲段數，雖然增加16個「異或」電路，但因為由校正子數據直接得到不可校正的檢測結果，總體來說是以較少的電路數量的結構而能實現高速且簡單的差錯檢測。
現按照上述觀點說明圖13的操作。
在此實施例的代碼結構中，由於奇偶校驗陣列中採用作為奇數加權的「1」、「3」、「7」的完全格式，故可以檢測出除不符合的校正子格式，亦即除「0」以外的偶數加權格式和加權「5」的格式。而由於校正子的「0」檢測是由8輸入「或」電路66進行檢測、並由2輸入「與」電路68使得不可校正標誌不為「1」，所以亦可以由偶數和加權「5」檢測電路50檢測偶數和加權「5」。
圖14為表明偶數和加權「5」檢測電路50的詳細結構的電路方框圖。圖中，53為2輸入「異或」電路，54為2輸入「與」電路，55為2輸入「或」電路，56為2輸入「異或非」電路。
如由圖中可理解的，現有技術雖然必須是71個2輸入「或」電路或「或非」電路，而本實施例的結構卻可能以極小的電路規模來實現同樣的功能。
這裡雖然是針對(72、64)二進位線性代碼所作的說明，但對於其他奇偶長度的代碼也同樣適用，這是不言而喻的。
本發明的糾錯代碼解碼方法由於作成以上這樣的結構，所以能取得下述的種種效果。
本發明對於第一個問題，在以比信息符號還大的比特長作為符號的裡德-所羅門代碼的代碼中，以信息比特的高位部分作為偽數據，而對檢驗符號的高位二比特由後面增加這樣來構成，所以不進行符號變換，並由於能僅以符號時鐘進行編碼解碼，所以取得能高速處理的效果。
本發明對於第二個問題，由於依靠代碼序列的反相或向壓縮部分設定偽數據，而能採用糾錯電路來實現快速存貯器的抹除檢驗，所以不要專門用於檢驗的電路，從而有取得簡化電路結構的效果。
本發明對於第三個問題，由於在壓縮部分重疊以代碼原始數據，以此來插入同步數據，所以具有不增加信息長或數據長，而能進行同步檢驗或恢復的效果。
本發明對第四個問題，由於設置有對應輸入數據的校正子電路，可由選擇器對現有的校正子電路選擇地進行解碼，所以與現有技術相比，可以使緩衝存貯器的存貯速度降低，從而具有適宜採用廉價存貯器的效果。
本發明對於第五個問題，在8比特的校正子信息長中，對於加權「1」、「3」、「7」的完全格式作對應的1比特糾錯，所以可能僅僅從校正子信息中直接檢測出除「0」以外的偶數和加權「5」來檢測不可校正的情況，從而其有能夠以較現有高的速度的小型電路來進行差錯檢測。
權利要求
1.一種糾錯編碼/解碼方法，用於對編碼長度經過壓縮的糾錯碼進行編碼和解碼，其特徵在於，該方法包括下列步驟往所述壓縮部分中加入數據碼形，產生檢驗符號，從而使信息和檢驗符號全為「1」的數據為代碼，並只傳送所述信息和檢驗符號；和在解碼側，往所述信息和檢驗符號所產生的校正子加入所述壓縮部分中數據相應的校正子數據。
2.一種糾錯編碼/解碼方法，用於對編碼長度經過壓縮的糾錯碼進行編碼和解碼，其特徵在於，該方法包括下列步驟往信息符號緊接前面的壓縮部分加入代碼數據碼形，從而產生檢驗符號，並只傳送所述信息和檢驗符號；和在解碼側，往所述信息和檢驗符號產生的校正子中加入加到所述壓縮部分的所述數據碼形相應的校正子。
3.一種編碼電路，其特徵在於，它包括一個有限域求和電路，在編碼過程中將根據原先取得的代碼數據輸入的信息和檢驗符號取得的檢驗符號有限域求和結果作為經編碼的檢驗符號；和一個校正數據輸入器，輸入經校正的數據。
4.一種解碼電路，其特徵在於，它包括一個有限域求和電路和一個校正數據輸入器，有限域求和電路在解碼過程中取代碼數據已傳送的校正子數據和基於預計代碼數據的校正子數據均有限域求和結果作為經編碼的校正子數據。
5.如權利要求4所述的糾錯解碼電路，其特徵在於，它包括校正裝置，進行解碼時，根據加到所述壓縮部分的代碼數據碼形相應的校正子和加到信息和檢驗符號所產生的校正子的校正子，通常也對壓縮部分施加校正；和確定裝置，根據對所述壓縮部分中所加數據的解碼結果確定同步損耗。
6.如權利要求1或2所述的糾錯編碼/解碼方法，其特徵在於，它包括下列步驟代碼數據碼形通常加到緊跟前一信息符號的壓縮部分，以產生檢驗符號，並只傳送信息和檢驗符號；在解碼過程中，往信息和檢驗符號所產生的校正子中加入被加到所述壓縮部分的代碼數據碼形相應的校正子；和在特殊情況下，往信息和檢驗符號所產生的校正子數據中加入基於偽碼形的加入使所有編碼數據為1的校正子數據。
全文摘要
一種糾錯編碼/解碼方法,用於對編碼長度經過壓縮的糾錯碼進行編碼和解碼,其特徵在於,該方法包括下列步驟:往所述壓縮部分中加入數據碼形,產生檢驗符號,從而使信息和檢驗符號全為「1」的數據為代碼,並只傳送所述信息和檢驗符號;和在解碼側,往所述信息和檢驗符號所產生的校正子加入所述壓縮部分中數據相應的校正子數據。
文檔編號H03M13/47GK1334646SQ0111736
公開日2002年2月6日 申請日期2001年4月23日 優先權日1995年5月30日
發明者吉田英夫 申請人:三菱電機株式會社