(57)【要約】  誤り訂正符号処理方法は、降順記号若しくは昇順記号のいずれかまたは両方を算出し、情報記号列のすべての要素の排他的論理和をパリティとして算出する第１ステップと、降順記号の要素毎に排他的論理和を算出し、降順記号の下位ｎビット、若しくは昇順記号の要素毎に排他的論理和を算出し、昇順記号の下位ｎビットのいずれかまたは両方として生成する第２ステップと、パリティを並べた要素列の要素から降順に選択した要素の排他的論理和を算出し、降順記号の上位ｍビット、若しくは要素から昇順に選択した要素の排他的論理和を算出し、昇順記号の上位ｍビットのいずれかまたは両方を生成する第３ステップと、生成された降順記号若しくは昇順記号のいずれかまたは両方を、検査記号或いはシンドロームとして出力する第４ステップとを有する。
2011142133.tif 000002
【特許請求の範囲】
【請求項１】
長さL=２m+n（ｍは１以上の整数、ｎは２以上の整数）の情報記号列Ｖ＝（ｖL-1,ｖL-2,・・・ｖ1,ｖ0）をデータとして処理する誤り訂正符号処理方法であって、
情報記号列Ｖの要素ｖiの添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した情報記号列Ｖの全部で２m+n-1個の異なる要素の排他的論理和を要素とし、ｊの降順に並べた降順記号Q＝（ｑm+n-1,ｑm+n-2,・・・ｑ1,ｑ0）、若しくは情報記号列Ｖの要素ｖiの添字の小さいほうから昇順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した情報記号列Vの全部で２m+n-1個の異なる要素の排他的論理和を要素とし、ｊの降順に並べた昇順記号PP＝（ｐｐm+n-1, ｐｐm+n-2,・・・ｐｐ1, ｐｐ0）のいずれかまたは両方を算出する際に、前記情報記号列VがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n）の長さでｉ番目のワードの情報記号列をＷi＝（ｖi,Lw-1,ｖi,Lw-2,・・・,ｖi,1,ｖi,0）とし前記情報記号列Ｖをワードの情報記号列を降順に並べたもの（ＷM-1,ＷM-2, ・・・, Ｗ1,Ｗ0）で表した時、
ｉ番目の情報記号列Ｗiの要素ｖi,j（j＝０，１，２，・・・，２n−１）から添字jの大きいほうから降順に２k（ｋ＝０，１，２，・・・，ｎ−１）個を１組として２k個おきに選択した情報記号列Ｗiの全部で２n-1個の異なる要素の排他的論理和を要素としｋの降順に並べた降順記号QLi＝（ｑi,n-1,ｑi,n-2,・・・ｑi,1,ｑi,0）、若しくは情報記号列Ｗiの要素ｖi,j（j＝０，１，２，・・・，２n−１）から添字jの小さいほうから昇順に２k（ｋ＝０，１，２，・・・，ｎ−１）個を１組として２k個おきに選択した情報記号列Ｗiの全部で２n-1個の異なる要素の排他的論理和を要素としｋの降順に並べた昇順記号PPLi＝（ｐｐi,n-1, ｐｐi,n-2,・・・ｐｐi,1, ｐｐi,0）のいずれかまたは両方を算出し、情報記号列Ｗiのすべての要素の排他的論理和をパリティｐiとして算出する第１ステップと、
前記降順記号QLiの要素毎に添字ｉ＝０，１，２，・・・，Ｍ−１のすべてについて排他的論理和を算出し、前記降順記号Qの下位ｎビットのQL＝（ｑn-1,ｑn-2,・・・ｑ1,ｑ0）、若しくは前記昇順記号PPLiの要素毎に添字ｉ＝０，１，２，・・・，Ｍ−１のすべてについて排他的論理和を算出し、前記昇順記号PPの下位ｎビットのPPL＝（ｐｐn-1, ｐｐn-2,・・・ｐｐ1, ｐｐ0）のいずれかまたは両方として生成する第２ステップと、
前記パリティｐiを並べた要素列Ｐw＝（ｐM-1,ｐM-2, ・・・, ｐ1, ｐ0）の要素ｐiの添字ｉの大きいほうから降順に２k（ｋ＝０，１，２，・・・，ｍ−１）個を１組として２k個おきに選択した全部で２m-1個の異なる要素の排他的論理和を算出し、前記降順記号Qの上位ｍビットのQH＝（ｑm+n-1,ｑm+n-2,・・・ｑn+1,ｑn）、若しくは要素ｐiの添字ｉの小さいほうから昇順に２k（ｋ＝０，１，２，・・・，ｍ−１）個を１組として２k個おきに選択した全部で２m-1個の異なる要素の排他的論理和を算出し、前記昇順記号PPの上位ｍビットのPPH＝（ｐｐm+n-1,ｐｐm+n-2,・・・ｐｐn+1,ｐｐn）のいずれかまたは両方を生成する第３ステップと、
生成された前記降順記号Q若しくは前記昇順記号PPのいずれかまたは両方を、検査記号或いはシンドロームとして出力する第４ステップと
を有する誤り訂正符号処理方法。
【請求項２】
長さL＝２h−h−１（ｈは２以上の整数）の情報記号X＝（ｘL-1,ｘL-2,・・・,ｘ1,ｘ0）を情報データとして伝送する場合の誤り訂正符号処理方法であって、
符号語Ｙの符号長をN＝２h、検査記号をQ＝（ｑh-1,ｑh-2,・・・ｑ1,ｑ0）及びパリティｐとした時、
符号語Ｙの符号長が１ワード以下の場合は、長さＮの記号Ｘ'の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の内の添字ｉが０，２0，２1，・・・，２h-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に前記情報記号Ｘの要素を右から並べ拡張した記号Ｘ'＝（ｘL-1,ｘL-2,・・・,ｘL-N/2+1,0,ｘL-N/2,・・・,ｘ10,ｘ9,ｘ8,ｘ7,ｘ6,ｘ5,ｘ4,0,ｘ3,ｘ2,ｘ1,0,ｘ0,0,0,0）の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２h-1個の異なる要素の排他的論理和を算出し、前記検査記号Ｑの要素ｑj（ｊ＝０，１，２，・・・，ｈ−１）とし検査記号のデータとして生成する第５ステップと、
前記計算されたｑi及び情報記号のｘiの全要素の排他的論理和を算出しパリティｐとしデータとして生成する第６ステップと
を有し、符号語ＹがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n、ｍは1以上の整数でｈ＝ｍ+ｎ）の長さの場合は、長さＮの記号Ｘ'の要素ｘ'i（ｉ＝０，１，２，・・・，２m+n−１）の内の添字ｉが０，２0，２1，・・・，２m+n-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に前記情報記号Ｘの要素を右から並べ拡張した記号Ｘ'＝（ｘL-1,ｘL-2,・・・,ｘL-N/2+1,0,ｘL-N/2,・・・,ｘ10,ｘ9,ｘ8,ｘ7,ｘ6,ｘ5,ｘ4,0,ｘ3,ｘ2,ｘ1,0,ｘ0,0,0,0）の要素ｘ'i（ｉ＝０，１，２，・・・，２m+n−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した全部で２m+n-1個の異なる要素の排他的論理和をとり前記検査記号Qの要素を算出する際に、請求項１記載の前記情報記号列Ｖとして拡張した記号Ｘ' を使い請求項１の方法を用いて得られる前記降順記号Qを前記検査記号Qとし検査記号のデータとし、得られる前記要素列Ｐwの全ての要素の排他的論理和をパリティｐとして生成する第７ステップとを有し、
前記拡張した記号Ｘ'の追加された０の位置にある要素ｘ'i（ｉ＝０，２0，２1，・・・，２h-1）を添字ｉの昇順に前記パリティｐ，ｑk（ｋ＝０，１，２，・・・，ｈ−１）で置き換えることにより符号語Ｙ＝（ｘL-1,ｘL-2,・・・,ｘL-N/2+1,ｑh-1,ｘL-N/2,・・・,ｘ10,ｘ9,ｘ8,ｘ7,ｘ6,ｘ5,ｘ4,ｑ3,ｘ3,ｘ2,ｘ1,ｑ2,ｘ0,ｑ1,ｑ0,ｐ）をデータとして生成する第８ステップとを有する誤り訂正符号処理方法。
【請求項３】
請求項２記載の符号語Ｙがデータ伝送され受信した情報データである符号語Ｙ'＝（ｙ'N-1,y'N-2,・・・,y'1,y'0）を復号する誤り訂正符号処理方法であって、
符号語Ｙ'の符号長が１ワード以下の場合は、前記受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２h-1個の異なる要素の排他的論理和を算出しシンドロームＳ＝（ｓh-1,ｓh-2,・・・ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，ｈ−１）として生成する第９ステップと、
前記符号語Ｙ'の要素y'iの全要素の排他的論理和を算出し前記シンドロームＳの要素ｒとしデータとして生成する第１０ステップと、
前記シンドロームから誤りの有無と種類を判定する第１１ステップと、
ｒ＝１で１ビット誤りと判定された場合は、（ｓh -1, ｓh -2,・・・ｓ1,ｓ0）で指定される位置の前記符号語Ｙ'の要素の値を反転し前記符号語Ｙ'を訂正する第１２ステップと、
前記訂正された符号語Ｙ'から情報記号Ｚ＝（ｚL-1,ｚL-2,・・・,ｚ1,ｚ0）を抽出し誤り訂正後の情報データとして出力する第１３ステップと
を有し、
符号語Ｙ'がＭワードの長さの場合は、前記受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｎ−１）個を１組として２j個おきに選択した全部で２n-1個の異なる要素の排他的論理和を算出する際に、請求項１記載の前記情報記号列Ｖとして符号語Ｙ'を使い請求項１の方法を用いて得られる前記降順記号Qの要素をシンドロームＳ＝（ｓm+n-1,ｓm+n-2,・・・,ｓn, ,ｓn-1, ・・・,ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）とし、得られる前記要素列Ｐwの全ての要素の排他的論理和を前記シンドロームＳの要素ｒとして生成する第１４ステップと、
前記シンドロームから誤りの有無と種類を判定する第１５ステップと、
ｒ＝１で１ビット誤りと判定された場合は、前記シンドロームＳの上位ｍビットＳH＝（ｓm+n-1,ｓm+n-2,・・・,ｓn）に対応するワード番号及び前記シンドロームＳのｒのビット位置を除く下位ｎビットＳL＝（ｓn-1, ・・・,ｓ1,ｓ0）に対応するワード中のビット位置で指定される前記符号語Ｙ'の要素の値を反転し前記符号語Ｙ'を訂正する第１６ステップと、
前記訂正された符号語Ｙ'から情報記号Ｚ＝（ｚL-1,ｚL-2,・・・,ｚ1,ｚ0）を抽出し誤り訂正後の情報データとして出力する第１７ステップと
を有する誤り訂正符号処理方法。
【請求項４】
長さL＝２h−h−１（ｈは２以上の整数）の情報記号X＝（ｘ0,ｘ1,・・・ｘL-2,ｘL-1）を情報データとして伝送する場合の誤り訂正符号処理方法であって、
符号語Ｙの符号長をN＝２h、検査記号をPP＝（ｐｐh-1,ｐｐh-2 ,・・・ｐｐ1 ,ｐｐ0）及びパリティｐとした時、符号語Ｙの符号長が１ワード以下の場合は、長さＮの記号Ｘ'の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の内の添字ｉが０，２0，２1，・・・，２h-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に前記情報記号Ｘの要素を左から並べ拡張した記号Ｘ'＝（0,0,0,ｘ0,0,ｘ1,ｘ2,ｘ3,0,ｘ4,ｘ5,ｘ6,ｘ7,ｘ8,ｘ9,ｘ10,・・・,ｘL-N/2,0,ｘL-N/2+1,・・・, ｘL-2,ｘL-1）の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２h-1個の異なる要素の排他的論理和を算出し前記検査記号PPの要素ｐｐj（ｊ＝０，１，２，・・・，ｈ−１）とし検査記号のデータとして生成する第１８ステップと、
前記計算されたｐｐi及び情報記号のｘiの全要素の排他的論理和を算出し前記検査記号の内のパリティｐとしデータとして生成する第１９ステップと
を有し、
符号語ＹがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n、ｍは1以上の整数でｈ＝ｍ+ｎ）の長さの場合は、長さＮの記号Ｘ' ＝（ｘ'0,ｘ'1,ｘ'2,ｘ'3,ｘ'4,・・・, ｘ'N-2,ｘN-1）の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の内の添字ｉが０，２0，２1，・・・，２h-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に前記情報記号Ｘの要素を左から並べ拡張した記号Ｘ'＝（0,0,0,ｘ0,0,ｘ1,ｘ2,ｘ3,0,ｘ4,ｘ5,ｘ6,ｘ7,ｘ8,ｘ9,ｘ10,・・・,ｘL-N/2,0,ｘL-N/2+1,・・・, ｘL-2,ｘL-1）の要素ｘ'i（ｉ＝０，１，２，・・・，２m+n−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した全部で２m+n-1個の異なる要素の排他的論理和を算出する際に、請求項１記載の前記情報記号列Ｖとして拡張した記号Ｘ' を使い請求項１の方法を用いて得られる前記昇順記号PPを前記検査記号PPとし検査記号のデータとし、得られる前記要素列Ｐwの全ての要素の排他的論理和をパリティｐとして生成する第２０ステップとを有し、
前記拡張した記号Ｘ'の追加された０の位置にある要素ｘ'i（ｉ＝０，２0，２1，・・・，２h-1）を添字ｉの昇順に前記パリティｐ，ｐｐk（ｋ＝０，１，２，・・・，ｈ−１）で置き換えることにより符号語Ｙ＝（ｐ,ｐｐ0,ｐｐ1,ｘ0,ｐｐ2,ｘ1,ｘ2,ｘ3,ｐｐ3,ｘ4,ｘ5,ｘ6,ｘ7,ｘ8,ｘ9,ｘ10,・・・,ｘL-N/2,ｐｐh-1,ｘL-N/2+1,・・・, ｘL-2,ｘL-1）をデータとして生成する第２１ステップと
を有する誤り訂正符号処理方法。
【請求項５】
請求項４記載の符号語Ｙがデータ伝送され受信した情報データである符号語Ｙ'＝ （y'0, ,y'1,・・・,ｙ'N-2,y'N-1）を復号する誤り訂正符号処理方法であって、
符号語Ｙ'の符号長が１ワード以下の場合は、前記受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２n-1個の異なる要素の排他的論理和を算出しシンドロームＳ＝（ｓh-1,ｓh-2,・・・ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，h−１）として生成する第２２ステップと、
前記符号語Ｙ'の要素y'iの全要素の排他的論理和を算出し前記シンドロームＳの要素ｒとしデータとして生成する第２３ステップと、
前記シンドロームから誤りの有無と種類を判定する第２４ステップと、
ｒ＝１で１ビット誤りと判定された場合は、（ｓh-1,ｓh-2,・・・ｓ1,ｓ0）で指定される位置の前記符号語Ｙ'の要素の値を反転し前記符号語Ｙ'を訂正する第２５ステップと、
前記訂正された符号語Ｙ'から情報記号Ｚ＝（ｚ0,ｚ1,・・・,ｚL-2,ｚL-1）を抽出し誤り訂正後の情報データとして出力する第２６ステップと
を有し、
符号語Ｙ'がＭワードの長さの場合は、前記受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｎ−１）個を１組として２j個おきに選択した全部で２n-1個の異なる要素の排他的論理和を算出する際に、請求項１記載の前記情報記号列Ｖとして符号語Ｙ'を使い請求項１の方法を用いて得られる前記降順記号Qの要素をシンドロームＳ＝（ｓm+n-1,ｓm+n-2,・・・,ｓn, ,ｓn-1, ・・・,ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，ｎ−１）とし、得られる前記要素列Ｐwの全ての要素の排他的論理和を前記シンドロームＳの要素ｒとして生成する第２７ステップと、
前記シンドロームから誤りの有無と種類を判定する第２８ステップと、
ｒ＝１で１ビット誤りと判定された場合は、前記シンドロームＳの上位ｍビットＳH＝（ｓm+n-1,ｓm+n-2,・・・,ｓn）に対応するワード番号及び前記シンドロームＳのｒのビット位置を除く下位ｎビットＳL＝（ｓn-1, ・・・,ｓ1,ｓ0）に対応するワード中のビット位置で指定される前記符号語Ｙ'の要素の値を反転し前記符号語Ｙ'を訂正する第２９ステップと、
前記訂正された符号語Ｙ'から情報記号Ｚ＝（ｚ0,ｚ1,・・・,ｚL-2,ｚL-1）を抽出し誤り訂正後の情報データとして出力する第３０ステップと
を有する誤り訂正符号処理方法。
【請求項６】
プロセッサと、
請求項２、請求項３、請求項４または請求項５記載の方法を実行させる際に発行する命令として、検査記号の要素の符号語における位置の規則性に基づく、情報記号から符号語を生成するために情報記号を再配置する専用命令、復号された符号語から情報記号を抽出する専用命令、１ワード以下の長さの符号語に対する検査記号とシンドロームの計算を１サイクルで実行する専用命令、１ワード以下の長さの符号語の誤りの検出と訂正を１サイクルで実行する専用命令、及び２ワード以上の記号列の排他的論理和をとる規則性に基づく、２ワード以上の長さの記号列の検査記号とシンドロームの計算を効率よく実行するための補助命令、２ワード以上の長さの符号語の誤り検出・誤り訂正を効率よく実行するための補助命令を備えた命令メモリと、
前記プロセッサが前記命令メモリの専用命令と補助命令を含む命令を発行し検査行列・シンドロームの計算または誤り訂正の計算をして結果のデータを出力する専用演算回路と、
前記伝送する情報データ、前記受信した情報データ、前記結果のデータを入れるデータメモリと、
前記プロセッサ、前記専用演算回路及び前記データメモリ間のデータ転送を行うデータバスと
を備える請求項２、請求項３、請求項４または請求項５記載の方法を用いる誤り訂正符号処理装置。
【請求項７】
前記専用演算回路は、
検査行列・シンドロームの計算をして前記結果のデータを出力する検査行列・シンドローム演算回路と、誤り訂正の計算をして前記結果のデータを出力する誤り訂正回路と
を備える請求項６記載の誤り訂正符号処理装置。
【請求項８】
長さL＝２m+n（ｍは１以上の整数、ｎは２以上の整数）の情報記号X＝（ｘL-1,ｘL-2,・・・,ｘ1,ｘ0）を情報データとして伝送する場合の誤り訂正符号処理方法であって、
符号語Ｙの符号長がN＝２m+n+２（ｍ+ｎ）、検査記号がQ＝（ｑm+n-1,ｑm+n-2,・・・ｑ1,ｑ0），PP＝（ｐｐm+n-1,ｐｐm+n-2,・・・ｐｐ1,ｐｐ0）で、前記情報記号XがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n）の長さの場合、
請求項１記載の前記情報記号列Ｖとして拡張した前記情報記号Xを使い、請求項１の方法を用いて得られる前記降順記号Qを前記検査記号Qとし、前記昇順記号PPを前記検査記号PPとして生成する第３１ステップ
を有する誤り訂正符号処理方法。
【請求項９】
請求項８記載の符号語Ｙがデータ伝送され受信した情報データである符号語Ｙ'＝ （y'0, ,y'1,・・・,ｙ'N-2,y'N-1）を復号する誤り訂正符号処理方法であって、
前記符号語Ｙ'に含まれる受信した情報記号をX'＝（ｘ'L-1,ｘ'L-2,・・・,ｘ'1,ｘ'0）、送信した検査記号Q，PPに対応する受信した検査記号がそれぞれQ'＝（ｑ'm+n-1,ｑ'm+n-2,・・・ｑ'1,ｑ'0），PP'＝（ｐｐ'm+n-1,ｐｐ'm+n-2,・・・ｐｐ1,ｐｐ0）とした場合、
請求項１記載の前記情報記号列Ｖとして受信した情報記号X'を使い請求項１記載の方法を用いて得られる前記降順記号Qを検査記号ＳQ＝（ｓｑm+n-1, ｓｑm+n-2,・・・ｓｑ1, ｓｑ0）とし、前記昇順記号PPを検査記号SPP＝（ｓｐｐm+n-1, ｓｐｐm+n-2,・・・ｓｐｐ1, ｓｐｐ0）として生成する第３２ステップと、
受信した検査記号Q'と生成した検査記号SQの要素毎の排他的論理和を算出しシンドロームＳＳQ＝（ｓｓｑm+n-1, ｓｓｑm+n-2,・・・ｓｓｑ1, ｓｓｑ0）を生成し、受信した検査記号PP'と生成した検査記号SPPの要素毎の排他的論理和を算出し、シンドロームＳＳP＝（ｓｓｐm+n-1, ｓｓｐm+n-2,・・・ｓｓｐ1, ｓｓｐ0）を生成する第３３ステップと、
前記シンドロームＳＳQ，ＳＳPから誤りの有無と種類を判定する第３４ステップと、
前記シンドロームＳＳQ，ＳＳPの要素の少なくとも１ビットが１であり誤り有りと判定され、かつＳＳQとＳＳPの要素毎に排他的論理和をとった結果すべてのビットが１であり前記情報記号X'に１ビット誤りがあると判定された場合、前記シンドロームＳＳQの上位ｍビットをSSQHとし、下位ｎビットをSSQLとした時、前記情報記号X' においてSSQHで指定される位置のワード中で、SSQLで指定される位置の要素の値を反転し、前記情報記号X'を訂正する第３５ステップと
を有する誤り訂正符号処理方法。
【請求項１０】
情報記号をｘを変数（モジュロ２）とする多項式で表現した情報記号多項式にｘk（生成多項式の次数ｋ）を乗じたシフト情報記号多項式を生成多項式で除算し剰余を算出する第１の演算により、剰余の多項式の係数を検査記号として求め、情報記号と合わせて符号語を生成し、データとして送信するＣＲＣ符号化方法であって、
前記第１の演算における前記シフト情報記号多項式の変数ｘの最高次からの各項を前記生成多項式にｘのべき乗を乗算し引くことにより段階的に消去する各段の第２の演算を前記シフト情報記号多項式の係数を並べたベクトルから始まり各段の途中段階の剰余の係数を並べたベクトルに対する同一の行列Ｇとの積で表現し、所定の回数の前記行列Ｇのみの積を予め算出して前記第２の演算を前記所定の回数繰り返した後の前記第１の演算の部分演算単位を表現する部分演算行列とするステップ１と、
前記シフト情報記号多項式のベクトルと前記部分演算行列との積を途中段階の剰余のベクトルとして求めることから始めて前記所定の回数ごとの途中段階の剰余のベクトルと前記部分演算行列との積を次の途中段階の剰余のベクトルとして順次求める演算を行い、検査記号を生成するステップ２と
を有するＣＲＣ符号化方法。
【請求項１１】
請求項１０記載の符号語がデータ伝送され受信したデータである受信符号語を復号するＣＲＣ復号化方法であって、
前記受信符号語を多項式で表現した受信符号語多項式を請求項１０記載の前記生成多項式により除算し剰余を算出する第３の演算により、剰余の多項式の係数をシンドロームとして生成する際に、前記第３の演算における前記受信符号語多項式の変数ｘの最高次からの各項を前記生成多項式にｘのべき乗を乗算し引くことにより段階的に消去する各段の第４の演算において、前記受信符号語多項式のベクトルと前記部分演算行列との積を途中段階の剰余のベクトルとして求めることから始めて前記所定の回数ごとの途中段階の剰余のベクトルと請求項１０記載の前記部分演算行列との積を次の途中段階の剰余のベクトルとして順次求める演算を行い、シンドロームを生成するステップ１０と、
請求項１０記載の前記部分行列の逆行列を予め算出するステップ１１と、
前記シンドロームから誤りの有無と種類を判定するステップ１２と、
前記シンドロームにおいて１であるビットの総数が１個であり、前記受信符号語の下位から前記検査記号のビット幅中に１ビット誤りがあると判定された場合、前記シンドロームの１であるビット位置で指定される前記受信符号語のビットの値を反転し前記符号語を訂正するステップ１３と、
前記シンドロームにおいて１であるビットの総数が２個以上であり、前記シンドロームに前記逆行列を乗ずることを繰り返した結果、ｔ回目（ｔは１以上の整数）の結果のシンドロームにおいて１であるビットの総数が１個となり、前記検査記号のビット幅を単位幅として前記受信符号語の下位からｔ+１番目の位置のビット幅中に１ビット誤りがあると判定された場合、前記受信符号語の下位からｔ+１番目の位置のビット幅中の前記ｔ回目の結果のシンドロームの１であるビット位置で指定されるビットの値を反転し前記符号語を訂正するステップ１４と
を有するＣＲＣ復号化方法。
【請求項１２】
符号語を生成しデータとして送信する請求項１０記載のＣＲＣ符号化方法であって、
１ワードのビット数が前記検査記号のビット長ｋの自然数倍ｍで前記情報がＭワードの長さの時、
前記ステップ１において前記部分演算行列は前記所定の回数をｍｋ，（ｍ−１）ｋ，・・・，ｋ（ｋの倍数）としてｍ個の積行列Ｇmk，Ｇ(m-1)k，Ｇ(m-2)k，・・・，Ｇkであり、
前記ステップ２において前記シフト情報記号多項式のベクトルから始めて前記所定の回数ごとの途中段階の剰余のベクトルを順次求める演算を行うに替えて、前記シフト情報記号多項式のベクトルをワード毎にわけワード毎に一括した演算を順次行うに際して、１ワード中のビット幅ｋ単位のｋ個の要素を持つベクトルにわけてワード中の最初のビット幅のベクトルに対して積行列Ｇmkを乗じた結果のベクトルの要素とひとつ前のワードに対する前記一括した演算の結果のベクトルの要素との排他的論理和をとったベクトルの要素と、ワード中の次以降のビット幅の位置のｋ個の要素を持つ（ｍ−１）個のベクトルに対してそれぞれＧ(m-1)k，Ｇ(m-2)k，・・・，Ｇkを乗じた結果のベクトルの要素との排他的論理和をとりワード中の前記一括した演算として行うことを特徴とするＣＲＣ符号化方法。
【請求項１３】
請求項１２記載の符号語がデータ伝送され受信したデータである受信符号語を復号する請求項１１記載のＣＲＣ復号化方法であって、
１ワードのビット数が前記検査記号のビット長ｋの自然数倍ｍで、前記情報がＭワードの長さの時、
前記ステップ１０において、前記部分演算行列は前記所定の回数をｍｋ，（ｍ−１）ｋ，・・・，ｋ（ｋの倍数）としてｍ個の積行列Ｇmk，Ｇ(m-1)k，Ｇ(m-2)k，・・・，Ｇkであり、
前記ステップ１０において、前記受信符号語多項式のベクトルから始めて前記所定の回数ごとの途中段階の剰余のベクトルを順次求める演算を行うに替えて、前記受信符号語多項式のベクトルをワード毎にわけワード毎に一括した演算を順次行うに際して、１ワード中のビット幅ｋ単位のｋ個の要素を持つベクトルにわけてワード中の最初のビット幅のベクトルに対して積行列Ｇmkを乗じた結果のベクトルの要素とひとつ前のワードに対する前記一括した演算の結果のベクトルの要素との排他的論理和をとったベクトルの要素と、ワード中の次以降のビット幅の位置のｋ個の要素を持つ（ｍ−１）個のベクトルに対してそれぞれＧ(m-1)k，Ｇ(m-2)k，・・・，Ｇkを乗じた結果のベクトルの要素との排他的論理和をとりワード中の前記一括した演算として行い、
請求項１１記載の逆行列はＧkの逆行列Ｇ-kであることを特徴とするＣＲＣ復号化方法。
【請求項１４】
プロセッサと、
請求項１２または請求項１３記載の方法を実行させる際に発行する命令として、前記ステップ２または前記ステップ１０においてそれぞれ前記検査記号または前記シンドロームを算出するにおけるワード毎に一括した演算をする命令、及び、前記ステップ１３または前記ステップ１４において前記符号語の誤り訂正を行う命令を備えた命令メモリと、
前記プロセッサが前記命令メモリの命令を発行し、検査行列・シンドロームの計算または誤り訂正の計算をして結果のデータを出力する専用演算回路と、
前記伝送する情報データ、前記受信した情報データ、前記結果のデータを入れるデータメモリと、
前記プロセッサ、前記専用演算回路及び前記データメモリ間のデータ転送を行うデータバスと
を備える、請求項１２または請求項１３記載の方法を用いる誤り訂正符号処理装置。
【請求項１５】
前記専用演算回路は、
検査行列・シンドロームの計算をして前記結果のデータを出力する検査行列・シンドローム演算回路と、
誤り訂正の計算をして前記結果のデータを出力する誤り訂正回路と
を備える請求項１４記載の誤り訂正符号処理装置。
【請求項１６】
前記データメモリは、誤り位置計算のためのＬｏｏｋ−ｕｐ  Ｔａｂｌｅを保持している表引き用領域を含む
請求項１４または請求項１５に記載の誤り訂正符号処理装置。
【請求項１７】
前記専用演算回路は、再構成可能ハードウェアで構成されている
請求項１４または請求項１５に記載の誤り訂正符号処理装置。
【請求項１８】
送信システムから送られてくる符号語を受信し、符号語数をカウントするステップ１００と、
ビット誤り回数を、訂正可能な誤りを検出した場合にカウントするステップ１１０と、
前記ビット誤り回数と前記符号語数との商をビット誤り率としたとき、前記ビット誤り率がビット誤り率の上限を超えた場合には、誤り訂正レベルを上げ、前記誤り訂正レベルが前記誤り訂正レベルの上限を超えた場合には、前記誤り訂正レベルの上限を前記誤り訂正レベルとするとともに、前記誤り訂正レベルを前記送信システムに通知するステップ１２０と、
前記符号語数が誤り訂正レベル変更に必要な最小受信回数を超えかつ前記ビット誤り率がビット誤り率の下限を下回った場合には、前記誤り訂正レベルを下げ、前記誤り訂正レベルが前記誤り訂正レベルの下限を下回った場合には、前記誤り訂正レベルの下限を前記誤り訂正レベルとするとともに、前記誤り訂正レベルを前記送信システムに通知するステップ１３０と
を含む符号語長及び生成多項式の調整方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報通信や電子システム内部でのデータ伝送（以下では、両者を合わせて情報伝送という）における誤り訂正の効率化と低電力化を達成できる誤り訂正符号処理方法及びその装置に関するものである。
【背景技術】
【０００２】
情報伝送の分野では伝送誤りの可能性が常に存在するので、誤りを検出し訂正する手段が必要である。伝送中に1ビット誤りが発生する確率（以下、ビット誤り率という）が比較的低い応用分野では、符号化の効率が高く伝送効率の良い、拡大ハミング符号や高次元パリティ符号などの符号化方式が用いられている（非特許文献１〜３）。【０００３】
誤り訂正を伴う情報伝送の一般的な手順を図1に示す。送信側システムが、情報記号Xを受信側システムに伝送する場合、送信側システムは、まず符号化装置を用いて情報記号Xに誤り訂正用の検査記号を付加して符号語Yを生成して受信側システムに伝送する。このとき、通信路上で外乱による伝送誤り（Ｅ）が発生し、符号語Yの一部の値が変化する可能性がある。受信側システムが受信した符号語をY'とする。送信する情報記号、検査記号、符号語の関係を図２に示す。長さＬの情報記号に長さＮ−Ｌの検査記号をつけて構成される長さＮの符号語を(Ｎ,Ｌ)符号と呼ぶ。また、Ｌ/Ｎを(Ｎ,Ｌ)符号の符号化率と呼ぶ。【０００４】
復号及び誤り訂正の手順を図３に示す。受信側システムは、受信した符号語Y'を復号し、誤り検出・訂正を行うためのシンドロームと呼ばれる情報を計算し、受信した符号語Y'に伝送誤りが含まれているかどうかを検査する。もし訂正可能な誤りが含まれていることが分かった場合には、情報記号を訂正する。復号・誤り訂正回路が出力する情報記号をZで表わす。このとき、採用した誤り検出・訂正方式の能力に依存して、出力される情報記号Zに含まれる誤りは、次の4通りのいずれかになる。ここでは、1ビット誤り訂正・２ビット誤り検出可能な符号化方式について説明する。
(1)伝送路上で誤りが発生しなかった場合、復号・誤り訂正回路は、受信した符号語Y'には誤りがない（Y'=Y）と判断する。
(2)伝送路上で、復号・誤り訂正回路が検出・訂正可能な誤り（1ビット誤り）が発生した場合、復号・誤り訂正回路は、受信した符号語Y'の1ビット誤りを検出し、正しい値に訂正できる。
(3)伝送路上で、復号・誤り訂正回路が検出可能であるが訂正不可能な誤り（2ビット誤り）が発生した場合、復号・誤り訂正回路は、受信した符号語Y'の２ビット誤りを検出するが、正しい値に訂正出来ない。
(4)伝送路上で、復号・誤り訂正回路が検出可能でない誤り（３ビット以上の誤り）があった場合、復号・誤り訂正回路は、受信した符号語Y'に誤りがあることを検出できず、したがって、正しい値に訂正出来ない。【０００５】
1ビット誤り訂正可能・2ビット誤り検出可能な、拡大ハミング符号での符号化及び復号の方法とそこで用いられる基本演算について説明する。まず、単純なハミング符号を用いた1ビット誤り訂正法について説明し、1ビット誤り訂正・2ビット検出が可能な拡大ハミング符号について説明する。【０００６】
(1-1)ハミング符号を用いた符号化と復号
ハミング符号は、長さＬ＝２n−ｎ−１ビットの情報記号に対して、ｎビットの検査記号を付加して符号語を構成する（２n−１，２n−ｎ−１）符号であり、1ビット誤り訂正符号である。たとえば、ｎ＝４の場合には、(15,11) 符号となる。以下では、情報記号Ｘを式１で表し、符号語Ｙを式２で表す。【０００７】
【数１】
2011142133.tif 000003
【０００８】
【数２】
2011142133.tif 000004
【０００９】
ハミング符号では、符号化処理には生成行列Gが用いられ、復号には、検査行列Hが用いられる。検査行列Hは、大きさがｎ×（２n−１）の行列で、各列には、全零以外のすべてのｎ次元の列ベクタが含まれる。ｎ＝４の場合のハミング符号の検査行列Hの例を図４に示す。検査行列Hの列の並べ方は任意である。【００１０】
検査行列Hに対応する生成行列Gは、式３の性質を満たす行列である。ただし、加算は全て2を法とする加算（排他的論理和演算）によって行われる。GT，HTは、それぞれG，Hの転置行列を表し、以下同様に行列を表す文字の上付き文字がTである場合は、その行列の転置行列を表すものとする。【００１１】
【数３】
2011142133.tif 000005
【００１２】
検査行列Hが式４の形式をしている場合、この符号化方式を組織符号と呼ぶ。【００１３】
【数４】
2011142133.tif 000006
【００１４】
ここで、Aは大きさｎ×（２n−ｎ−１）の任意の行列、Inは、大きさｎ×ｎの単位行列である。組織符号では、検査行列Hに対応する生成行列Gは、式５で容易に求めることができる。【００１５】
【数５】
2011142133.tif 000007
【００１６】
ここで、ｍ＝２n−ｎ−１であり、ATは、Aの転置行列である。図４の検査行列H に対応する生成行列G を図５に示す。【００１７】
符号化は、情報記号Xに生成行列Gを掛けることによって行われる。情報記号Xを符号化して得られる符号語をYとする。たとえば、X＝[ 1 0 1 1 0 1 1 1 0 1 1 ] に対応する符号語は、図６に示すように、Y = [ 1 0 1 1 0 1 1 1 0 1 1 1 1 0 0 ] となる。【００１８】
復号と誤り訂正は、次のようにして行われる。受信した符号語をY'とし、受信した符号語にはたかだか1ビットしか誤りがないと仮定する。このとき、受信した符号語Y'のシンドロームSを式６で定義する。【００１９】
【数６】
2011142133.tif 000008
【００２０】
受信した符号語に誤りが含まれているかどうかは、シンドロームSの値によって、次のように判定する。【００２１】
Sの要素が全て0の場合、伝送誤りがなかったと判定する。【００２２】
Sが0以外の要素を含む場合、Sを転置したベクタと一致するHの列の位置に誤りがあったと判定される。【００２３】
たとえば、上記の例で、左から8ビット目に伝送誤りが発生し、受信した符号がY'=[ 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 ]であったとすると、シンドロームは、図７に示すように、S=[ 0 1 1 1 ]となり、このベクトルを転置すると、検査行列Hの左から8列目の値と一致するので、受信した符号語の左から8ビット目に誤りがあることが分かる。（ビット誤りが生じた位置に下線を引いてある。）【００２４】
(1-2)拡大ハミング符号を用いた符号化と復号
ハミング符号を用いると、1ビット誤りの訂正が可能である。しかし、2ビット誤りが発生した場合に、1ビット誤りが発生したのか2ビット誤りが発生したのかの区別が出来ないので、正しく訂正できない。1 ビット誤り訂正・2ビット誤り検出を行う方法として、ハミング符号を拡張した、拡大ハミング符号が用いられている。拡大ハミング符号での符号語は、生成行列G を用いて符号化した結果の符号語に、符号語全体のパリティビット（符号語の全ビットの排他的論理和）を付加することによって得られる。したがって、拡大ハミング符号での符号語長は２nとなる。【００２５】
先の例では、入力記号X＝[ 1 0 1 1 0 1 1 1 0 1 1 ]に対して生成行列Gを適用して得られる符号語[ 1 0 1 1 0 1 1 1 0 1 1 1 1 0 0 ]のパリティが0なので、末尾に0を付加して、Y＝[ 1 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 ]となる。【００２６】
拡大ハミング符号での復号及び誤り検出・訂正は、もとのハミング符号での検査行列Hの最後の列の後に要素が全て零の列ベクトルを追加し、その行列の最後の行の下に要素が全て1のベクトルを追加して得られる拡大検査行列H'を用いて行う。図４の検査行列H に対応する拡大検査行列H'を図８に示す。【００２７】
先の例で用いた符号語の左から8ビット目に誤りがある場合には、受信する符号語はY'=[ 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 ]となる。この符号語Y'に対して、拡大検査行列を用いてシンドロームY'H'Tを計算すると図９のように、[ 0 1 1 1 1 ] が得られる。【００２８】
乗算結果のベクトル[ 0 1 1 1 1 ]を転置すると、拡大検査行列の左から8列目と一致するので、受信した符号語の左から8ビット目に誤りが発生したことが知られる。受信した符号語に2ビット誤りがある場合には、受信する符号語に偶数個の1が含まれるので、Y'H'Tの最後の要素は0となる。拡大検査行列の最後の行の要素は全て1なので、検査結果を転置した列ベクトルは、拡大検査行列のどの列とも一致しない。この場合、2ビット誤りが発生したと判定する。3ビット以上の誤りがあった場合には、検出は不可能である。まとめると、次の＜場合1＞〜＜場合３＞のようになる。以下では、シンドロームをS=[sn-1,sn-2,・・・,s1,s0,ｒ]で表す。また、or(要素１，要素２，・・・，要素ｎ)は、全ての要素の論理和を行う論理関数とする。
＜場合1＞  Sの要素が全て0の場合（ｒ=0かつor(sn-1,sn-2,・・・,s1,s0)=0)には、誤りは発生しなかったと判定する。
＜場合2＞  Sの要素ｒ=1の場合、1ビット誤りが発生したと判定する。誤りが発生した位置は、Sと一致するパターンを持つ列に対応する要素である。
＜場合3＞  ＜場合１＞及び＜場合２＞以外の場合（ｒ=0かつor(sn-1,sn-2,・・・,s1,s0)=1)には、2ビット誤りが発生したと判定する。【００２９】
次に、これらの符号化を行うための装置及び復号・誤り訂正を行うための装置として実装する従来の手法は、
（A）汎用プロセッサ上のソフトウェアによる実装（以下、従来手法（Ａ）と呼ぶ）
（B）専用ハードウェア（ASIC: Application Specific Integrated Circuit）による実装（以下、従来手法（Ｂ）と呼ぶ）
の2種類に分類できる。【００３０】
図１０は、汎用プロセッサ上のソフトウェアによる従来の誤り訂正符号処理の実装を示す図である。図１０において、汎用プロセッサ１１０の外側には、命令メモリ１１１とデータメモリ１１２がある。命令メモリ１１１は、誤り訂正符号処理の符号化及び復号化演算のための命令を保持している。汎用プロセッサ１１０は、命令メモリ１１１から読み出された命令に従って、誤り訂正符号処理の符号化及び復号化演算を行う。また、汎用プロセッサ１１０は、命令メモリ１１１から読み出された命令に従って、データバス１１３を通じてデータメモリ１１２に保持されているデータを読み出す。さらに、汎用プロセッサ１１０は、汎用プロセッサ１１０で行われた演算結果を、データバス１１３を通じてデータメモリ１１２に格納する。【００３１】
図１１は、汎用プロセッサと専用周辺回路（ＡＳＩＣ）を用いた従来の誤り訂正符号処理の実装を示す図である。図１１において、汎用プロセッサ１２０の外側には、命令メモリ１２１、データメモリ１２２、符号化回路１２３及び復号化回路１２４がある。命令メモリ１２１は、誤り訂正符号処理の符号化及び復号化演算のための命令を保持している。汎用プロセッサ１２０は、命令メモリ１２１から読み出された命令に従って、データバス１２５を通じてデータメモリ１２２に保持されているコマンドとデータを読み出し、データバス１２５を通じて、符号化回路１２３及び復号化回路１２４に対し、実行すべき処理を指示するコマンドとデータを渡す。また、汎用プロセッサ１２０は、符号化回路１２３及び復号化回路１２４から、符号化及び復号化可能であったか等のステータス情報と、符号化及び復号化処理後の演算結果を読み出し、データバス１２５を通じてステータス情報と演算結果をデータメモリ１２２に格納する。符号化回路１２３は、命令メモリ１２１から読み出された命令に従って、誤り訂正符号処理の符号化演算を行う。復号化回路１２４は、命令メモリ１２１から読み出された命令に従って、誤り訂正符号処理の復号化演算を行う。ここで、符号化回路１２３及び復号化回路１２４は、ＡＳＩＣを用いている。また、符号化回路１２３は、検査記号を生成し、復号化回路１２４は、シンドローム生成及び誤り訂正を行う。【００３２】
従来手法（A）と従来手法（B）との間には、次のようなトレードオフが存在する。【００３３】
従来手法（A）は、従来手法（B）と比較して、次の(a)、(b)のような利点を持つ。
(a)実装するために必要なハードウェア量が少ない（プログラムを格納するためのメモリだけで十分である）。
(b)仕様変更に柔軟に対応できる（符号化方式の変更や符号長の変更に容易に対応できる）。【００３４】
しかし、従来手法（A）は、従来手法（B）と比較して、次の(c)、(d)のような欠点がある。
(c)実行時間が長い（実行サイクル数が多い）。
(d)消費電力量が大きい。
【先行技術文献】
【非特許文献】
【００３５】
【非特許文献１】RobertH. Morelos-Zaragoza: The art of error correcting coding, Second Ed., Wiley
【非特許文献２】Shu Lin, D.J. Costello, Jr.: Error Control Coding, Pearson Prentice Hall
【非特許文献３】Eiji Fujiwara: Code Design for Dependable Systems, Wiley
【発明の概要】
【発明が解決しようとする課題】
【００３６】
拡大ハミング符号は、他の同等の誤り訂正能力を持つ符号化方式よりも符号化率の点で優れており実用性が高い。しかし、拡大ハミング符号では、復号を行なったときに得られるビット誤りの情報から、誤りが発生したビットの位置を効率良く決定することが容易ではないという問題点がある。【００３７】
すなわち、拡大ハミング符号は、1ビット誤り訂正可能・2ビット誤り検出可能な符号化方式の中で、符号化率が最も高いという特徴を持っている。しかし、背景技術の従来例に示したように、1ビット誤りを検出した場合に、ビット誤りが含まれている位置を判定するためには、シンドロームS=Y'H'Tの演算結果を転置した列ベクトルと拡大検査行列の各列を比較して一致する列を特定する必要がある。ところが、組織符号を用いた場合には、検査行列の各列を2進数とみなした場合に列の並びに単調性がないので、シンドロームSと一致する列の特定を、ハードウェア量及び実行時間の両方で効率良く実行する方法は自明ではない。【００３８】
たとえば、組織符号を用いる拡大ハミング符号をソフトウェアによる従来手法(A)の方法で実装する場合、誤りが生じた位置を効率良く特定するためには、(a)一致する列ベクトルを逐次的に探索する、(b)ハッシングの技法を用いて探索を効率化する、(c)図１２に示すような、シンドロームからビット誤りの位置を求めるための変換表をあらかじめ用意し、表引きによって計算時間を短縮するなどの方法が考えられる。しかし、(a)の方法は計算量が多く、(b)、(c)の方法は、符号長が長い場合に多量のメモリが必要になるなどの問題がある。いずれも消費電力量の面では不利である。【００３９】
また、組織符号を用いる拡大ハミング符号を、従来手法(B)の方法で、専用ハードウェアを用いて高速化するためには、誤り位置の特定のための機構をハードウェアで実装せざるを得ない。その結果、ハードウェア量が増大し、消費電力も増大してしまうという問題がある。【００４０】
半導体の微細化が進んだ結果、VLSI（Very Large Scale Integration:大規模集積回路）の集積度が向上し、クロック周波数も向上し、性能が向上している。しかし、その結果、VLSIの消費電力が増大傾向にある。特に、汎用プロセッサでは、消費電力の増大に伴う発熱量の増大と温度上昇が大きな問題になっている。従来手法（B）は、消費電力量の点で従来手法（A）よりも優れているが、仕様変更や伝送路の伝送路誤り率の変化に柔軟に対応することが困難である。したがって、仕様変更や伝送路の伝送路誤り率の変化に柔軟に対応でき、かつ消費電力量の少ない実装方法を用いた誤り訂正符号処理装置を開発することが課題となっている。【００４１】
そこで、本発明は、このような従来の課題を解決するためになされたものであり、誤りの発生した位置を容易に特定でき、仕様変更や伝送路の伝送路誤り率の変化に柔軟に対応することができ、かつ、消費電力量の少ない誤り訂正符号処理方法及びその装置を提供することを目的とする。
【課題を解決するための手段】
【００４２】
上記目的を達成するために、本発明の一形態に係る誤り訂正符号処理方法及びその装置は、長さL=２m+n（ｍは１以上の整数、ｎは２以上の整数）の情報記号列Ｖ＝（ｖL-1,ｖL-2,・・・ｖ1,ｖ0）をデータとして処理する誤り訂正符号処理方法であって、情報記号列Ｖの要素ｖiの添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した情報記号列Ｖの全部で２m+n-1個の異なる要素の排他的論理和を要素とし、ｊの降順に並べた降順記号Q＝（ｑm+n-1,ｑm+n-2,・・・ｑ1,ｑ0）、若しくは情報記号列Ｖの要素ｖiの添字の小さいほうから昇順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した情報記号列Vの全部で２m+n-1個の異なる要素の排他的論理和を要素とし、ｊの降順に並べた昇順記号PP＝（ｐｐm+n-1, ｐｐm+n-2,・・・ｐｐ1, ｐｐ0）のいずれかまたは両方を算出する際に、前記情報記号列VがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n）の長さでｉ番目のワードの情報記号列をＷi＝（ｖi,Lw-1,ｖi,Lw-2,・・・,ｖi,1,ｖi,0）とし前記情報記号列Ｖをワードの情報記号列を降順に並べたもの（ＷM-1,ＷM-2, ・・・, Ｗ1,Ｗ0）で表した時、ｉ番目の情報記号列Ｗiの要素ｖi,j（j＝０，１，２，・・・，２n−１）から添字jの大きいほうから降順に２k（ｋ＝０，１，２，・・・，ｎ−１）個を１組として２k個おきに選択した情報記号列Ｗiの全部で２n-1個の異なる要素の排他的論理和を要素としｋの降順に並べた降順記号QLi＝（ｑi,n-1,ｑi,n-2,・・・ｑi,1,ｑi,0）、若しくは情報記号列Ｗiの要素ｖi,j（j＝０，１，２，・・・，２n−１）から添字jの小さいほうから昇順に２k（ｋ＝０，１，２，・・・，ｎ−１）個を１組として２k個おきに選択した情報記号列Ｗiの全部で２n-1個の異なる要素の排他的論理和を要素としｋの降順に並べた昇順記号PPLi＝（ｐｐi,n-1, ｐｐi,n-2,・・・ｐｐi,1, ｐｐi,0）のいずれかまたは両方を算出し、情報記号列Ｗiのすべての要素の排他的論理和をパリティｐiとして算出する第１ステップと、前記降順記号QLiの要素毎に添字ｉ＝０，１，２，・・・，Ｍ−１のすべてについて排他的論理和を算出し、前記降順記号Qの下位ｎビットのQL＝（ｑn-1,ｑn-2,・・・ｑ1,ｑ0）、若しくは前記昇順記号PPLiの要素毎に添字ｉ＝０，１，２，・・・，Ｍ−１のすべてについて排他的論理和を算出し、前記昇順記号PPの下位ｎビットのPPL＝（ｐｐn-1, ｐｐn-2,・・・ｐｐ1, ｐｐ0）のいずれかまたは両方として生成する第２ステップと、前記パリティｐiを並べた要素列Ｐw＝（ｐM-1,ｐM-2, ・・・, ｐ1, ｐ0）の要素ｐiの添字ｉの大きいほうから降順に２k（ｋ＝０，１，２，・・・，ｍ−１）個を１組として２k個おきに選択した全部で２m-1個の異なる要素の排他的論理和を算出し、前記降順記号Qの上位ｍビットのQH＝（ｑm+n-1,ｑm+n-2,・・・ｑn+1,ｑn）、若しくは要素ｐiの添字ｉの小さいほうから昇順に２k（ｋ＝０，１，２，・・・，ｍ−１）個を１組として２k個おきに選択した全部で２m-1個の異なる要素の排他的論理和を算出し、前記昇順記号PPの上位ｍビットのPPH＝（ｐｐm+n-1,ｐｐm+n-2,・・・ｐｐn+1,ｐｐn）のいずれかまたは両方を生成する第３ステップと、生成された前記降順記号Q若しくは前記昇順記号PPのいずれかまたは両方を、検査記号或いはシンドロームとして出力���る第４ステップとを有する。【００４３】
これにより、検査記号及びシンドロームが規則性を持つため、誤りの発生した位置を容易に特定でき、仕様変更や伝送路の伝送路誤り率の変化に柔軟に対応することができ、かつ、消費電力量の少ない誤り訂正符号処理方法を提供することができる。【００４４】
また、長さL＝２h−h−１（ｈは２以上の整数）の情報記号X＝（ｘL-1,ｘL-2,・・・,ｘ1,ｘ0）を情報データとして伝送する場合の誤り訂正符号処理方法であって、符号語Ｙの符号長をN＝２h、検査記号をQ＝（ｑh-1,ｑh-2,・・・ｑ1,ｑ0）及びパリティｐとした時、符号語Ｙの符号長が１ワード以下の場合は、長さＮの記号Ｘ'の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の内の添字ｉが０，２0，２1，・・・，２h-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に前記情報記号Ｘの要素を右から並べ拡張した記号Ｘ'＝（ｘL-1,ｘL-2,・・・,ｘL-N/2+1,0,ｘL-N/2,・・・,ｘ10,ｘ9,ｘ8,ｘ7,ｘ6,ｘ5,ｘ4,0,ｘ3,ｘ2,ｘ1,0,ｘ0,0,0,0）の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２h-1個の異なる要素の排他的論理和を算出し、前記検査記号Ｑの要素ｑj（ｊ＝０，１，２，・・・，ｈ−１）とし検査記号のデータとして生成する第５ステップと、前記計算されたｑi及び情報記号のｘiの全要素の排他的論理和を算出しパリティｐとしデータとして生成する第６ステップとを有し、符号語ＹがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n、ｍは1以上の整数でｈ＝ｍ+ｎ）の長さの場合は、長さＮの記号Ｘ'の要素ｘ'i（ｉ＝０，１，２，・・・，２m+n−１）の内の添字ｉが０，２0，２1，・・・，２m+n-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に前記情報記号Ｘの要素を右から並べ拡張した記号Ｘ'＝（ｘL-1,ｘL-2,・・・,ｘL-N/2+1,0,ｘL-N/2,・・・,ｘ10,ｘ9,ｘ8,ｘ7,ｘ6,ｘ5,ｘ4,0,ｘ3,ｘ2,ｘ1,0,ｘ0,0,0,0）の要素ｘ'i（ｉ＝０，１，２，・・・，２m+n−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した全部で２m+n-1個の異なる要素の排他的論理和をとり前記検査記号Qの要素を算出する際に、上記の前記情報記号列Ｖとして拡張した記号Ｘ' を使い上記の方法を用いて得られる前記降順記号Qを前記検査記号Qとし検査記号のデータとし、得られる前記要素列Ｐwの全ての要素の排他的論理和をパリティｐとして生成する第７ステップとを有し、前記拡張した記号Ｘ'の追加された０の位置にある要素ｘ'i（ｉ＝０，２0，２1，・・・，２h-1）を添字ｉの昇順に前記パリティｐ，ｑk（ｋ＝０，１，２，・・・，ｈ−１）で置き換えることにより符号語Ｙ＝（ｘL-1,ｘL-2,・・・,ｘL-N/2+1,ｑh-1,ｘL-N/2,・・・,ｘ10,ｘ9,ｘ8,ｘ7,ｘ6,ｘ5,ｘ4,ｑ3,ｘ3,ｘ2,ｘ1,ｑ2,ｘ0,ｑ1,ｑ0,ｐ）をデータとして生成する第８ステップとを有する。【００４５】
また、長さL＝２h−h−１（ｈは２以上の整数）の情報記号X＝（ｘ0,ｘ1,・・・ｘL-2,ｘL-1）を情報データとして伝送する場合の誤り訂正符号処理方法であって、符号語Ｙの符号長をN＝２h、検査記号をPP＝（ｐｐh-1,ｐｐh-2 ,・・・ｐｐ1 ,ｐｐ0）及びパリティｐとした時、符号語Ｙの符号長が１ワード以下の場合は、長さＮの記号Ｘ'の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の内の添字ｉが０，２0，２1，・・・，２h-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に前記情報記号Ｘの要素を左から並べ拡張した記号Ｘ'＝（0,0,0,ｘ0,0,ｘ1,ｘ2,ｘ3,0,ｘ4,ｘ5,ｘ6,ｘ7,ｘ8,ｘ9,ｘ10,・・・,ｘL-N/2,0,ｘL-N/2+1,・・・, ｘL-2,ｘL-1）の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２h-1個の異なる要素の排他的論理和を算出し前記検査記号PPの要素ｐｐj（ｊ＝０，１，２，・・・，ｈ−１）とし検査記号のデータとして生成する第１８ステップと、前記計算されたｐｐi及び情報記号のｘiの全要素の排他的論理和を算出し前記検査記号の内のパリティｐとしデータとして生成する第１９ステップとを有し、符号語ＹがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n、ｍは1以上の整数でｈ＝ｍ+ｎ）の長さの場合は、長さＮの記号Ｘ' ＝（ｘ'0,ｘ'1,ｘ'2,ｘ'3,ｘ'4,・・・, ｘ'N-2,ｘN-1）の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の内の添字ｉが０，２0，２1，・・・，２h-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に前記情報記号Ｘの要素を左から並べ拡張した記号Ｘ'＝（0,0,0,ｘ0,0,ｘ1,ｘ2,ｘ3,0,ｘ4,ｘ5,ｘ6,ｘ7,ｘ8,ｘ9,ｘ10,・・・,ｘL-N/2,0,ｘL-N/2+1,・・・, ｘL-2,ｘL-1）の要素ｘ'i（ｉ＝０，１，２，・・・，２m+n−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した全部で２m+n-1個の異なる要素の排他的論理和を算出する際に、上記の前記情報記号列Ｖとして拡張した記号Ｘ' を使い上記の方法を用いて得られる前記昇順記号PPを前記検査記号PPとし検査記号のデータとし、得られる前記要素列Ｐwの全ての要素の排他的論理和をパリティｐとして生成する第２０ステップとを有し、前記拡張した記号Ｘ'の追加された０の位置にある要素ｘ'i（ｉ＝０，２0，２1，・・・，２h-1）を添字ｉの昇順に前記パリティｐ，ｐｐk（ｋ＝０，１，２，・・・，ｈ−１）で置き換えることにより符号語Ｙ＝（ｐ,ｐｐ0,ｐｐ1,ｘ0,ｐｐ2,ｘ1,ｘ2,ｘ3,ｐｐ3,ｘ4,ｘ5,ｘ6,ｘ7,ｘ8,ｘ9,ｘ10,・・・,ｘL-N/2,ｐｐh-1,ｘL-N/2+1,・・・, ｘL-2,ｘL-1）をデータとして生成する第２１ステップとを有する。【００４６】
上記により、スーパー・ハミング符号での誤り訂正符号処理の符号化をすることができる。【００４７】
また、上記の符号語Ｙがデータ伝送され受信した情報データである符号語Ｙ'＝（ｙ'N-1,y'N-2,・・・,y'1,y'0）を復号する誤り訂正符号処理方法であって、符号語Ｙ'の符号長が１ワード以下の場合は、前記受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２h-1個の異なる要素の排他的論理和を算出しシンドロームＳ＝（ｓh-1,ｓh-2,・・・ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，ｈ−１）として生成する第９ステップと、前記符号語Ｙ'の要素y'iの全要素の排他的論理和を算出し前記シンドロームＳの要素ｒとしデータとして生成する第１０ステップと、前記シンドロームから誤りの有無と種類を判定する第１１ステップと、ｒ＝１で１ビット誤りと判定された場合は、（ｓh -1, ｓh -2,・・・ｓ1,ｓ0）で指定される位置の前記符号語Ｙ'の要素の値を反転し前記符号語Ｙ'を訂正する第１２ステップと、前記訂正された符号語Ｙ'から情報記号Ｚ＝（ｚL-1,ｚL-2,・・・,ｚ1,ｚ0）を抽出し誤り訂正後の情報データとして出力する第１３ステップとを有し、符号語Ｙ'がＭワードの長さの場合は、前記受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｎ−１）個を１組として２j個おきに選択した全部で２n-1個の異なる要素の排他的論理和を算出する際に、上記の前記情報記号列Ｖとして符号語Ｙ'を使い上記の方法を用いて得られる前記降順記号Qの要素をシンドロームＳ＝（ｓm+n-1,ｓm+n-2,・・・,ｓn, ,ｓn-1, ・・・,ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）とし、得られる前記要素列Ｐwの全ての要素の排他的論理和を前記シンドロームＳの要素ｒとして生成する第１４ステップと、前記シンドロームから誤りの有無と種類を判定する第１５ステップと、ｒ＝１で１ビット誤りと判定された場合は、前記シンドロームＳの上位ｍビットＳH＝（ｓm+n-1,ｓm+n-2,・・・,ｓn）に対応するワード番号及び前記シンドロームＳのｒのビット位置を除く下位ｎビットＳL＝（ｓn-1, ・・・,ｓ1,ｓ0）に対応するワード中のビット位置で指定される前記符号語Ｙ'の要素の値を反転し前記符号語Ｙ'を訂正する第１６ステップと、前記訂正された符号語Ｙ'から情報記号Ｚ＝（ｚL-1,ｚL-2,・・・,ｚ1,ｚ0）を抽出し誤り訂正後の情報データとして出力する第１７ステップとを有する。【００４８】
また、上記の符号語Ｙがデータ伝送され受信した情報データである符号語Ｙ'＝ （y'0, ,y'1,・・・,ｙ'N-2,y'N-1）を復号する誤り訂正符号処理方法であって、符号語Ｙ'の符号長が１ワード以下の場合は、前記受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２n-1個の異なる要素の排他的論理和を算出しシンドロームＳ＝（ｓh-1,ｓh-2,・・・ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，h−１）として生成する第２２ステップと、前記符号語Ｙ'の要素y'iの全要素の排他的論理和を算出し前記シンドロームＳの要素ｒとしデータとして生成する第２３ステップと、前記シンドロームから誤りの有無と種類を判定する第２４ステップと、ｒ＝１で１ビット誤りと判定された場合は、（ｓh-1,ｓh-2,・・・ｓ1,ｓ0）で指定される位置の前記符号語Ｙ'の要素の値を反転し前記符号語Ｙ'を訂正する第２５ステップと、前記訂正された符号語Ｙ'から情報記号Ｚ＝（ｚ0,ｚ1,・・・,ｚL-2,ｚL-1）を抽出し誤り訂正後の情報データとして出力する第２６ステップとを有し、符号語Ｙ'がＭワードの長さの場合は、前記受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｎ−１）個を１組として２j個おきに選択した全部で２n-1個の異なる要素の排他的論理和を算出する際に、上記の前記情報記号列Ｖとして符号語Ｙ'を使い上記の方法を用いて得られる前記降順記号Qの要素をシンドロームＳ＝（ｓm+n-1,ｓm+n-2,・・・,ｓn, ,ｓn-1, ・・・,ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，ｎ−１）とし、得られる前記要素列Ｐwの全ての要素の排他的論理和を前記シンドロームＳの要素ｒとして生成する第２７ステップと、前記シンドロームから誤りの有無と種類を判定する第２８ステップと、ｒ＝１で１ビット誤りと判定された場合は、前記シンドロームＳの上位ｍビットＳH＝（ｓm+n-1,ｓm+n-2,・・・,ｓn）に対応するワード番号及び前記シンドロームＳのｒのビット位置を除く下位ｎビットＳL＝（ｓn-1, ・・・,ｓ1,ｓ0）に対応するワード中のビット位置で指定される前記符号語Ｙ'の要素の値を反転し前記符号語Ｙ'を訂正する第２９ステップと、前記訂正された符号語Ｙ'から情報記号Ｚ＝（ｚ0,ｚ1,・・・,ｚL-2,ｚL-1）を抽出し誤り訂正後の情報データとして出力する第３０ステップとを有する。【００４９】
上記により、スーパー・ハミング符号での誤り訂正符号処理の復号化をすることができる。【００５０】
また、プロセッサと、上記の方法を実行させる際に発行する命令として、検査記号の要素の符号語における位置の規則性に基づく、情報記号から符号語を生成するために情報記号を再配置する専用命令、復号された符号語から情報記号を抽出する専用命令、１ワード以下の長さの符号語に対する検査記号とシンドロームの計算を１サイクルで実行する専用命令、１ワード以下の長さの符号語の誤りの検出と訂正を１サイクルで実行する専用命令、及び２ワード以上の記号列の排他的論理和をとる規則性に基づく、２ワード以上の長さの記号列の検査記号とシンドロームの計算を効率よく実行するための補助命令、２ワード以上の長さの符号語の誤り検出・誤り訂正を効率よく実行するための補助命令を備えた命令メモリと、前記プロセッサが前記命令メモリの専用命令と補助命令を含む命令を発行し検査行列・シンドロームの計算または誤り訂正の計算をして結果のデータを出力する専用演算回路と、前記伝送する情報データ、前記受信した情報データ、前記結果のデータを入れるデータメモリと、前記プロセッサ、前記専用演算回路及び前記データメモリ間のデータ転送を行うデータバスとを備える。【００５１】
また、前記専用演算回路は、検査行列・シンドロームの計算をして前記結果のデータを出力する検査行列・シンドローム演算回路と、誤り訂正の計算をして前記結果のデータを出力する誤り訂正回路とを備える。【００５２】
上記により、スーパー・ハミング符号での誤り訂正符号処理を実装化した装置を提供することができる。【００５３】
また、長さL＝２m+n（ｍは１以上の整数、ｎは２以上の整数）の情報記号X＝（ｘL-1,ｘL-2,・・・,ｘ1,ｘ0）を情報データとして伝送する場合の誤り訂正符号処理方法であって、符号語Ｙの符号長がN＝２m+n+２（ｍ+ｎ）、検査記号がQ＝（ｑm+n-1,ｑm+n-2,・・・ｑ1,ｑ0），PP＝（ｐｐm+n-1,ｐｐm+n-2,・・・ｐｐ1,ｐｐ0）で、前記情報記号XがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n）の長さの場合、上記の前記情報記号列Ｖとして拡張した前記情報記号Xを使い、上記の方法を用いて得られる前記降順記号Qを前記検査記号Qとし、前記昇順記号PPを前記検査記号PPとして生成する第３１ステップを有する。【００５４】
これにより、高次元パリティ符号での誤り訂正符号処理の符号化をすることができる。【００５５】
また、上記の符号語Ｙがデータ伝送され受信した情報データである符号語Ｙ'＝ （y'0, ,y'1,・・・,ｙ'N-2,y'N-1）を復号する誤り訂正符号処理方法であって、前記符号語Ｙ'に含まれる受信した情報記号をX'＝（ｘ'L-1,ｘ'L-2,・・・,ｘ'1,ｘ'0）、送信した検査記号Q，PPに対応する受信した検査記号がそれぞれQ'＝（ｑ'm+n-1,ｑ'm+n-2,・・・ｑ'1,ｑ'0），PP'＝（ｐｐ'm+n-1,ｐｐ'm+n-2,・・・ｐｐ1,ｐｐ0）とした場合、上記の前記情報記号列Ｖとして受信した情報記号X'を使い上記の方法を用いて得られる前記降順記号Qを検査記号ＳQ＝（ｓｑm+n-1, ｓｑm+n-2,・・・ｓｑ1, ｓｑ0）とし、前記昇順記号PPを検査記号SPP＝（ｓｐｐm+n-1, ｓｐｐm+n-2,・・・ｓｐｐ1, ｓｐｐ0）として生成する第３２ステップと、受信した検査記号Q'と生成した検査記号SQの要素毎の排他的論理和を算出しシンドロームＳＳQ＝（ｓｓｑm+n-1, ｓｓｑm+n-2,・・・ｓｓｑ1, ｓｓｑ0）を生成し、受信した検査記号PP'と生成した検査記号SPPの要素毎の排他的論理和を算出し、シンドロームＳＳP＝（ｓｓｐm+n-1, ｓｓｐm+n-2,・・・ｓｓｐ1, ｓｓｐ0）を生成する第３３ステップと、前記シンドロームＳＳQ，ＳＳPから誤りの有無と種類を判定する第３４ステップと、前記シンドロームＳＳQ，ＳＳPの要素の少なくとも１ビットが１であり誤り有りと判定され、かつＳＳQとＳＳPの要素毎に排他的論理和をとった結果すべてのビットが１であり前記情報記号X'に１ビット誤りがあると判定された場合、前記シンドロームＳＳQの上位ｍビットをSSQHとし、下位ｎビットをSSQLとした時、前記情報記号X' においてSSQHで指定される位置のワード中で、SSQLで指定される位置の要素の値を反転し、前記情報記号X'を訂正する第３５ステップとを有する。【００５６】
これにより、高次元パリティ符号での誤り訂正符号処理の復号化をすることができる。【００５７】
また、情報記号をｘを変数（モジュロ２）とする多項式で表現した情報記号多項式にｘk（生成多項式の次数ｋ）を乗じたシフト情報記号多項式を生成多項式で除算し剰余を算出する第１の演算により、剰余の多項式の係数を検査記号として求め、情報記号と合わせて符号語を生成し、データとして送信するＣＲＣ符号化方法であって、前記第１の演算における前記シフト情報記号多項式の変数ｘの最高次からの各項を前記生成多項式にｘのべき乗を乗算し引くことにより段階的に消去する各段の第２の演算を前記シフト情報記号多項式の係数を並べたベクトルから始まり各段の途中段階の剰余の係数を並べたベクトルに対する同一の行列Ｇとの積で表現し、所定の回数の前記行列Ｇのみの積を予め算出して前記第２の演算を前記所定の回数繰り返した後の前記第１の演算の部分演算単位を表現する部分演算行列とするステップ１と、前記シフト情報記号多項式のベクトルと前記部分演算行列との積を途中段階の剰余のベクトルとして求めることから始めて前記所定の回数ごとの途中段階の剰余のベクトルと前記部分演算行列との積を次の途中段階の剰余のベクトルとして順次求める演算を行い、検査記号を生成するステップ２とを有する。【００５８】
また、符号語を生成しデータとして送信する上記のＣＲＣ符号化方法であって、１ワードのビット数が前記検査記号のビット長ｋの自然数倍ｍで前記情報がＭワードの長さの時、前記ステップ１において前記部分演算行列は前記所定の回数をｍｋ，（ｍ−１）ｋ，・・・，ｋ（ｋの倍数）としてｍ個の積行列Ｇmk，Ｇ(m-1)k，Ｇ(m-2)k，・・・，Ｇkであり、前記ステップ２において前記シフト情報記号多項式のベクトルから始めて前記所定の回数ごとの途中段階の剰余のベクトルを順次求める演算を行うに替えて、前記シフト情報記号多項式のベクトルをワード毎にわけワード毎に一括した演算を順次行うに際して、１ワード中のビット幅ｋ単位のｋ個の要素を持つベクトルにわけてワード中の最初のビット幅のベクトルに対して積行列Ｇmkを乗じた結果のベクトルの要素とひとつ前のワードに対する前記一括した演算の結果のベクトルの要素との排他的論理和をとったベクトルの要素と、ワード中の次以降のビット幅の位置のｋ個の要素を持つ（ｍ−１）個のベクトルに対してそれぞれＧ(m-1)k，Ｇ(m-2)k，・・・，Ｇkを乗じた結果のベクトルの要素との排他的論理和をとりワード中の前記一括した演算として行うことを特徴とする。【００５９】
上記により、ＣＲＣ符号での誤り訂正符号処理の符号化をすることができる。【００６０】
また、上記の符号語がデータ伝送され受信したデータである受信符号語を復号するＣＲＣ復号化方法であって、前記受信符号語を多項式で表現した受信符号語多項式を上記の前記生成多項式により除算し剰余を算出する第３の演算により、剰余の多項式の係数をシンドロームとして生成する際に、前記第３の演算における前記受信符号語多項式の変数ｘの最高次からの各項を前記生成多項式にｘのべき乗を乗算し引くことにより段階的に消去する各段の第４の演算において、前記受信符号語多項式のベクトルと前記部分演算行列との積を途中段階の剰余のベクトルとして求めることから始めて前記所定の回数ごとの途中段階の剰余のベクトルと上記の前記部分演算行列との積を次の途中段階の剰余のベクトルとして順次求める演算を行い、シンドロームを生成するステップ１０と、上記の前記部分行列の逆行列を予め算出するステップ１１と、前記シンドロームから誤りの有無と種類を判定するステップ１２と、前記シンドロームにおいて１であるビットの総数が１個であり、前記受信符号語の下位から前記検査記号のビット幅中に１ビット誤りがあると判定された場合、前記シンドロームの１であるビット位置で指定される前記受信符号語のビットの値を反転し前記符号語を訂正するステップ１３と、前記シンドロームにおいて１であるビットの総数が２個以上であり、前記シンドロームに前記逆行列を乗ずることを繰り返した結果、ｔ回目（ｔは１以上の整数）の結果のシンドロームにおいて１であるビットの総数が１個となり、前記検査記号のビット幅を単位幅として前記受信符号語の下位からｔ+１番目の位置のビット幅中に１ビット誤りがあると判定された場合、前記受信符号語の下位からｔ+１番目の位置のビット幅中の前記ｔ回目の結果のシンドロームの１であるビット位置で指定されるビットの値を反転し前記符号語を訂正するステップ１４とを有する。【００６１】
また、上記の符号語がデータ伝送され受信したデータである受信符号語を復号する上記のＣＲＣ復号化方法であって、１ワードのビット数が前記検査記号のビット長ｋの自然数倍ｍで、前記情報がＭワードの長さの時、前記ステップ１０において、前記部分演算行列は前記所定の回数をｍｋ，（ｍ−１）ｋ，・・・，ｋ（ｋの倍数）としてｍ個の積行列Ｇmk，Ｇ(m-1)k，Ｇ(m-2)k，・・・，Ｇkであり、前記ステップ１０において、前記受信符号語多項式のベクトルから始めて前記所定の回数ごとの途中段階の剰余のベクトルを順次求める演算を行うに替えて、前記受信符号語多項式のベクトルをワード毎にわけワード毎に一括した演算を順次行うに際して、１ワード中のビット幅ｋ単位のｋ個の要素を持つベクトルにわけてワード中の最初のビット幅のベクトルに対して積行列Ｇmkを乗じた結果のベクトルの要素とひとつ前のワードに対する前記一括した演算の結果のベクトルの要素との排他的論理和をとったベクトルの要素と、ワード中の次以降のビット幅の位置のｋ個の要素を持つ（ｍ−１）個のベクトルに対してそれぞれＧ(m-1)k，Ｇ(m-2)k，・・・，Ｇkを乗じた結果のベクトルの要素との排他的論理和をとりワード中の前記一括した演算として行い、上記の逆行列はＧkの逆行列Ｇ-kであることを特徴とする。【００６２】
上記により、ＣＲＣ符号での誤り訂正符号処理の復号化に応用することができる。【００６３】
また、プロセッサと、上記の方法を実行させる際に発行する命令として、前記ステップ２または前記ステップ１０においてそれぞれ前記検査記号または前記シンドロームを算出するにおけるワード毎に一括した演算をする命令、及び、前記ステップ１３または前記ステップ１４において前記符号語の誤り訂正を行う命令を備えた命令メモリと、前記プロセッサが前記命令メモリの命令を発行し、検査行列・シンドロームの計算または誤り訂正の計算をして結果のデータを出力する専用演算回路と、前記伝送する情報データ、前記受信した情報データ、前記結果のデータを入れるデータメモリと、前記プロセッサ、前記専用演算回路及び前記データメモリ間のデータ転送を行うデータバスとを備える。【００６４】
また、前記専用演算回路は、検査行列・シンドロームの計算をして前記結果のデータを出力する検査行列・シンドローム演算回路と、誤り訂正の計算をして前記結果のデータを出力する誤り訂正回路とを備える。【００６５】
また、前記データメモリは、誤り位置計算のためのＬｏｏｋ−ｕｐ  Ｔａｂｌｅを保持している表引き用領域を含む。【００６６】
また、前記専用演算回路は、再構成可能ハードウェアで構成されている。【００６７】
上記により、ＣＲＣ符号での誤り訂正符号処理を実装化した装置を提供することができる。【００６８】
また、送信システムから送られてくる符号語を受信し、符号語数をカウントするステップ１００と、ビット誤り回数を、訂正可能な誤りを検出した場合にカウントするステップ１１０と、前記ビット誤り回数と前記符号語数との商をビット誤り率としたとき、前記ビット誤り率がビット誤り率の上限を超えた場合には、誤り訂正レベルを上げ、前記誤り訂正レベルが前記誤り訂正レベルの上限を超えた場合には、前記誤り訂正レベルの上限を前記誤り訂正レベルとするとともに、前記誤り訂正レベルを前記送信システムに通知するステップ１２０と、前記符号語数が誤り訂正レベル変更に必要な最小受信回数を超えかつ前記ビット誤り率がビット誤り率の下限を下回った場合には、前記誤り訂正レベルを下げ、前記誤り訂正レベルが前記誤り訂正レベルの下限を下回った場合には、前記誤り訂正レベルの下限を前記誤り訂正レベルとするとともに、前記誤り訂正レベルを前記送信システムに通知するステップ１３０とを含む。【００６９】
これにより、ビットの誤り率に対応して、適応的に符号長の長さを変更できるので、通信に必要となる電力量を削減することができる。
【発明の効果】
【００７０】
本発明は、誤りの発生した位置を容易に特定でき、仕様変更や伝送路の伝送路誤り率の変化に柔軟に対応することができ、かつ、消費電力量の少ない誤り訂正符号処理方法及びその装置を提供することができる。
【図面の簡単な説明】
【００７１】
【図１】図１は、誤り訂正を伴う情報伝送の手順を説明する図である。
【図２】図２は、符号化の手順を説明する図である。
【図３】図３は、復号及び誤り訂正の手順を説明する図である。
【図４】図４は、従来のハミング符号の検査行列の例を示す図である。
【図５】図５は、従来のハミング符号の生成行列の例を示す図である。
【図６】図６は、従来のハミング符号での符号語の計算例を示す図である。
【図７】図７は、従来のハミング符号での1ビット誤り発生位置の特定方法の例を示す図である。
【図８】図８は、従来の拡大ハミング符号での検査行列の例を示す図である。
【図９】図９は、従来の拡大ハミング符号での1ビット誤り発生位置の特定方法の例を示す図である。
【図１０】図１０は、汎用プロセッサ上のソフトウェアによる従来の誤り訂正符号処理の実装を示す図である。
【図１１】図１１は、汎用プロセッサと専用周辺回路（ASIC）を用いた従来の誤り訂正符号処理の実装を示す図である。
【図１２】図１２は、従来の拡大ハミング符号でのシンドロームとビット誤り位置の対応表の例を示す図である。
【図１３】図１３は、本発明に係る、スーパー・ハミング符号での検査行列の例を示す図である。
【図１４】図１４は、本発明に係る、スーパー・ハミング符号での検査記号及びパリティの計算式を示す図である。
【図１５】図１５は、本発明に係る、スーパー・ハミング符号での情報記号と符号語の対応関係の例を示す図である。
【図１６】図１６は、本発明に係る、スーパー・ハミング符号での検査記号の計算式の例を示す図である。
【図１７】図１７は、本発明に係る、スーパー・ハミング符号での生成行列の導出手順(1)を示す図である。
【図１８】図１８は、本発明に係る、スーパー・ハミング符号での生成行列の導出手順(2)を示す図である。
【図１９】図１９は、本発明に係る、スーパー・ハミング符号での生成行列の導出手順(3)を示す図である。
【図２０】図２０は、従来の拡大ハミング符号での検査行列の計算パターンの例を示す図である。
【図２１】図２１は、本発明に係る、スーパー・ハミング符号での検査記号の計算パターンの例を示す図である。
【図２２】図２２は、本発明に係る、誤り訂正処理装置を示す図である。
【図２３】図２３は、本発明に係る、1ワードの長さが16ビットの場合の各ビットのインデックスの割り当て方法を示す図である。
【図２４】図２４は、本発明に係る、4ワードからなる符号語での検査記号の埋め込み位置を示す図である。
【図２５】図２５は、本発明に係る、スーパー・ハミング符号での情報記号再配置命令（1）を示す図である。
【図２６】図２６は、本発明に係る、スーパー・ハミング符号での情報記号再配置命令（2）を示す図である。
【図２７】図２７は、本発明に係る、スーパー・ハミング符号での情報記号再配置命令（3）を示す図である。
【図２８】図２８は、本発明に係る、スーパー・ハミング符号での情報記号再配置命令（1）の適用例を示す図である。
【図２９】図２９は、本発明に係る、スーパー・ハミング符号での情報記号再配置命令（2）の適用例を示す図である。
【図３０】図３０は、本発明に係る、スーパー・ハミング符号での情報記号再配置命令（3）の適用例(1) を示す図である。
【図３１】図３１は、本発明に係る、スーパー・ハミング符号での情報記号再配置命令（3）の適用例(2) を示す図である。
【図３２】図３２は、本発明に係る、バレルシフタの実装方法の例を示す図である。
【図３３】図３３は、本発明に係る、スーパー・ハミング符号での情報記号抽出命令（1）を示す図である。
【図３４】図３４は、本発明に係る、スーパー・ハミング符号での情報記号抽出命令（2）を示す図である。
【図３５】図３５は、本発明に係る、スーパー・ハミング符号での情報記号抽出命令（3）を示す図である。
【図３６】図３６は、本発明に係る、スーパー・ハミング符号での情報記号の抽出命令（1）の適用例を示す図である。
【図３７】図３７は、本発明に係る、スーパー・ハミング符号での情報記号抽出命令（2）の適用例を示す図である。
【図３８】図３８は、本発明に係る、スーパー・ハミング符号での情報記号抽出命令（3）の適用例(1) を示す図である。
【図３９】図３９は、本発明に係る、スーパー・ハミング符号での情報記号抽出命令（4）の適用例(2) を示す図である。
【図４０】図４０は、本発明に係る、スーパー・ハミング符号での検査記号及びシンドロームの計算式を示す図である。
【図４１】図４１は、本発明に係る、スーパー・ハミング符号での検査記号及びシンドロームの計算パターンの例を示す図である。
【図４２】図４２は、本発明に係る、スーパー・ハミング符号での1ビット誤り訂正回路の図である。
【図４３】図４３は、本発明に係る、スーパー・ハミング符号での複数のワードに格納された情報記号に対する検査記号の計算式を示す図である。
【図４４】図４４は、本発明に係る、スーパー・ハミング符号での複数のワードに格納された情報記号に対する検査記号の計算手順を示す図である。
【図４５】図４５は、本発明に係る、スーパー・ハミング符号での複数のワードに格納された符号語のシンドロームの計算式を示す図である。
【図４６】図４６は、本発明に係る、スーパー・ハミング符号での複数のワードに格納された符号語のシンドロームの計算手順を示す図である。
【図４７】図４７は、本発明に係る、高次元パリティ符号での検査記号及びシンドロームの計算式を示す図である。
【図４８】図４８は、本発明に係る、高次元パリティ符号での検査記号及びシンドロームの計算パターンの例を示す図である。
【図４９】図４９は、本発明に係る、適応的符号語長調整型通信方式での符号語長調整手続きの例を示す図である。
【図５０】図５０は、従来のＣＲＣ符号での検査記号の計算フローを示す図である。
【図５１】図５１は、本発明に係る、生成多項式ｘ8＋ｘ2＋ｘ＋１を表す行列Ｇを示す図である。
【図５２】図５２は、本発明に係る、Ｇ8を表す行列を示す図である。
【図５３】図５３は、本発明に係る、Ｇ16を表す行列を示す図である。
【図５４】図５４は、本発明に係る、ＣＲＣ符号での×Ｇm専用演算器（ｎサイクル版）の構成を示す図である。
【図５５】図５５は、本発明に係る、図５１における（Ｇ8）T表の例を示す図である。
【図５６】図５６は、本発明に係る、ＣＲＣ符号での×Ｇm専用演算器（１サイクル版）の構成を示す図である。
【図５７】図５７は、本発明に係る、ＣＲＣ符号での検査記号計算回路の構成を示す図である。
【図５８】図５８は、本発明に係る、ＣＲＣ符号での誤り訂正回路の構成を示す図である。
【図５９】図５９は、本発明に係る、Ｇ-8を表す行列を示す図である。
【図６０Ａ】図６０Ａは、本発明に係る、提案手法（１）の構成を示す図である。
【図６０Ｂ】図６０Ｂは、本発明に係る、提案手法（２）の構成を示す図である。
【図６０Ｃ】図６０Ｃは、本発明に係る、提案手法（３）の構成を示す図である。
【図６１】図６１は、本発明に係る、図６０Ｃにおける×Ｇm専用演算器の構成を示す図である。
【図６２】図６２は、本発明に係る、符号語長及び生成多項式の調整手続きの例（受信側）を示す図である。
【発明を実施するための形態】
【００７２】
本発明の実施の一形態を説明する。
【００７３】
一般に広く用いられている組織符号を用いた拡大ハミング符号に基づく誤り訂正方式は高速化及び低電力化に関して問題がある。本願発明者は、その原因が検査行列から生成行列を求めるのが容易な組織符号を採用しているためであることに着目した。検査の容易さを考えると、検査行列の各行の並び方を工夫し、シンドロームから誤り位置を簡単に特定できるようにする必要があるが、そのためには、たとえば、検査行列の各行に単調性を持たせて、降順に並べればよいが、このような並べ方をすると、検査行列が式４の形式を保てなくなくなるので、任意のnに対して、与えられた検査行列から式３の条件を満たす生成行列を求めるのは簡単ではない。また、符号長を変えるたびに生成行列を求めなおす必要がある。
【００７４】
生成行列の決定が容易で、かつ専用命令での実行が効率良く実行できるように、拡大ハミング符号方式を改良する。改良された符号方式を、スーパー・ハミング符号と呼ぶことにする。スーパー・ハミング符号で用いる検査行列は、列の間に単調性があり、シンドロームからビット誤りが発生した位置を非常に容易に特定できる。したがって誤り訂正が高速化でき、消費電力量も削減できる。ｎ＝４の場合のスーパー・ハミング符号の検査行列の例を図13に示す。スーパー・ハミング符号での符号化及び復号化方法は次の通りである。以下では、符号長をN=２n、情報記号の長さをＬ＝２n−ｎ−１とする。検査記号の長さはｎ＋１である。送信する情報記号Xは式７で表される。
【００７５】
【数７】
2011142133.tif 000009
【００７６】
情報記号Xから、符号語Yを次のようにして生成する。まず、情報記号Xを式８のように拡張して符号語X'に変換する。
【００７７】
【数８】
2011142133.tif 000010
【００７８】
XとX'との対応関係は次のとおりである。まず、Xの要素を、右側（添字の値の小さい方）から、1個、3個、7個、．．．、２n-1−１個の、ｎ−１個のグループに分割し、それぞれをXi(i=0,・・・,n-2)とする。各Xi(i=0,・・・,n-2)は、式９のようになる。
【００７９】
【数９】
2011142133.tif 000011
【００８０】
次に、各Xi(i=0,・・・,n-2)の右側に0を1個ずつ追加し最後にさらに0を2個追加し、X'とする。X'は式１０で表される。この段階では、検査記号は付加されていない。
【００８１】
【数１０】
2011142133.tif 000012
【００８２】
ここで、0を追加した位置（要素のインデックス）は、右から順に０，２0，２1，・・・，２n-1である。また、Ｌ＝２n−ｎ−１であることから、X'の要素数は、Ｎ＝Ｌ＋ｎ＋１＝２nとなる。
【００８３】
次に、X'の検査記号Ｑ＝[ｑn-1，ｑn-2，・・・，ｑ0]及び符号語全体のパリティpを図14の式を用いて計算する。
【００８４】
符号化は、式１０で、ベクトルX'に0を挿入した要素、ｘ'i（ｉ＝２0，２1，・・・，２n-1）を検査記号ｑi（ｉ＝０，１，・・・，ｎ−１）で置き換えることによって行う。さらに、x0（最も右にある0）をこのようにして得られたX'の全ビットの排他的論理和（パリティ）pで置き換えて符号語Yとする。符号語Yは式１１で表される。
【００８５】
【数１１】
2011142133.tif 000013
【００８６】
情報記号Xと符号語Yの対応関係を図15に示す。また、n=4の場合の検査記号及びパリティの計算式の例を図16に示す。
【００８７】
従来手法であるハミング符号や拡大ハミング符号では、符号語を構成する際に、図２に示すように、情報記号のブロックと検査記号のブロックを分離して配置している。たとえば、拡大ハミング符号の場合、情報記号Ｘ＝[ｘL-1，ｘL-2，・・・，ｘ0]の検査記号をＱ＝[ｑn-1，ｑn-2，・・・，ｑ0]とすると、符号語Y は式１２のような構成になる。
【００８８】
【数１２】
2011142133.tif 000014
【００８９】
この構成は、符号語を生成する場合及び復号して情報記号を抽出する場合には容易であるが、先に述べたように、1ビット誤りが発生したビットの位置の特定が容易に行えない。
【００９０】
本発明では、符号語の２iのインデックスの位置に検査記号を配置する。これが本発明の特徴の一つであり、これにより、シンドロームの値から誤りの発生位置が容易に特定できる。
【００９１】
このようにして符号化することは、次の（Step1）〜（Step3）によって得られる生成行列Ｇ(3)を用いて符号化することと等価である。
【００９２】
（Step1）拡張された、大きさ２n×（２n−１）の生成行列Ｇ(1)を式１３のようにして構成する。
【００９３】
【数１３】
2011142133.tif 000015
【００９４】
ここで、Ｉmは式５に示されたｍ×ｍの単位行列、ＨTは式４の検査行列の転置行列である。n=4の場合の生成行列Ｇ(1)の例を図17に示す。
【００９５】
（Step2）生成行列Ｇ(1)の行を次のように入れ替える。生成行列Ｇ(1)のＨTに相当する部分行列の行ベクトルを２進数とみなしたとき上から下へと降順に並ぶように生成行列Ｇ(1)全体の各行を入れ替える。このようにして得られた生成行列をＧ(2)とする。n=4の場合の生成行列Ｇ(2)の例を図18に示す。
【００９６】
（Step3）対角要素が１になるように生成行列Ｇ(2)の列を入れ替える。この操作を加えた生成行列をＧ(3)とする。n=4の場合の生成行列Ｇ(3)の例を図19に示す。
【００９７】
生成行列Ｇ(3)を用いて符号化された符号語に含まれる情報記号は、単位行列を用いて計算が行われているので、式５を用いた計算結果と同じ値になる。また、検査記号の計算は、検査行列の転置の単位行列の部分には0が入力されるので、式５を用いて計算される検査記号と同じ値になる。生成行列Ｇ(3)を用いて符号化された結果は、式５を用いて計算した符号語の要素の順序を入れ替えた記号列になっている。スーパー・ハミング符号での復号、誤り検出、誤り訂正の手順は、拡大ハミング符号での処理手順とほぼ同じである。受信した符号語Ｙ'に対して、拡大ハミング符号の場合と同様に検査行列を適用して復号し、1ビット誤りの有無、2ビット誤りの有無を検査する。1ビット誤りが発見された場合には、シンドロームを用いて伝送誤りの位置を特定する。その際、検査行列の各列を2進数とみなすと、左から右に降順に並んでいるので、ビットパターンの比較や複雑な対応表などを用いることなく、伝送誤りが発生した位置が特定できる。したがって、拡大ハミング符号よりも誤り訂正は容易に行える。最後に、符号語の中に埋め込んであった検査記号を取り除けば、訂正されたデータが得られる。本方式は1ビット誤り訂正能力と2ビット誤り検出能力を持ち、拡大ハミング符号の誤り訂正・誤り検出能力と等価である。
【００９８】
以上、スーパー・ハミング符号での符号化及び復号化方法の手順をまとめると、以下の通りとなる。
【００９９】
長さL=２m+n（ｍは１以上の整数、ｎは２以上の整数）の情報記号列Ｖ＝（ｖL-1,ｖL-2,・・・ｖ1,ｖ0）をデータとして処理を行う場合、情報記号列Ｖの要素ｖiの添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した情報記号列Ｖの全部で２m+n-1個の異なる要素の排他的論理和を要素とし、ｊの降順に並べた降順記号Q＝（ｑm+n-1,ｑm+n-2,・・・ｑ1,ｑ0）、若しくは情報記号列Ｖの要素ｖiの添字の小さいほうから昇順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した情報記号列Vの全部で２m+n-1個の異なる要素の排他的論理和を要素とし、ｊの降順に並べた昇順記号PP＝（ｐｐm+n-1, ｐｐm+n-2,・・・ｐｐ1, ｐｐ0）のいずれかまたは両方を算出する際に、情報記号列VがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n）の長さでｉ番目のワードの情報記号列をＷi＝（ｖi,Lw-1,ｖi,Lw-2,・・・,ｖi,1,ｖi,0）とし情報記号列Ｖをワードの情報記号列を降順に並べたもの（ＷM-1,ＷM-2, ・・・, Ｗ1,Ｗ0）で表した時、ｉ番目の情報記号列Ｗiの要素ｖi,j（j＝０，１，２，・・・，２n−１）から添字jの大きいほうから降順に２k（ｋ＝０，１，２，・・・，ｎ−１）個を１組として２k個おきに選択した情報記号列Ｗiの全部で２n-1個の異なる要素の排他的論理和を要素としｋの降順に並べた降順記号QLi＝（ｑi,n-1,ｑi,n-2,・・・ｑi,1,ｑi,0）、若しくは情報記号列Ｗiの要素ｖi,j（j＝０，１，２，・・・，２n−１）から添字jの小さいほうから昇順に２k（ｋ＝０，１，２，・・・，ｎ−１）個を１組として２k個おきに選択した情報記号列Ｗiの全部で２n-1個の異なる要素の排他的論理和を要素としｋの降順に並べた昇順記号PPLi＝（ｐｐi,n-1, ｐｐi,n-2,・・・ｐｐi,1, ｐｐi,0）のいずれかまたは両方を算出し、情報記号列Ｗiのすべての要素の排他的論理和をパリティｐiとして算出する第１ステップと、降順記号QLiの要素毎に添字ｉ＝０，１，２，・・・，Ｍ−１のすべてについて排他的論理和を算出し、降順記号Qの下位ｎビットのQL＝（ｑn-1,ｑn-2,・・・ｑ1,ｑ0）、若しくは昇順記号PPLiの要素毎に添字ｉ＝０，１，２，・・・，Ｍ−１のすべてについて排他的論理和を算出し、昇順記号PPの下位ｎビットのPPL＝（ｐｐn-1, ｐｐn-2,・・・ｐｐ1, ｐｐ0）のいずれかまたは両方として生成する第２ステップと、パリティｐiを並べた要素列Ｐw＝（ｐM-1,ｐM-2, ・・・, ｐ1, ｐ0）の要素ｐiの添字ｉの大きいほうから降順に２k（ｋ＝０，１，２，・・・，ｍ−１）個を１組として２k個おきに選択した全部で２m-1個の異なる要素の排他的論理和を算出し、降順記号Qの上位ｍビットのQH＝（ｑm+n-1,ｑm+n-2,・・・ｑn+1,ｑn）、若しくは要素ｐiの添字ｉの小さいほうから昇順に２k（ｋ＝０，１，２，・・・，ｍ−１）個を１組として２k個おきに選択した全部で２m-1個の異なる要素の排他的論理和を算出し、昇順記号PPの上位ｍビットのPPH＝（ｐｐm+n-1,ｐｐm+n-2,・・・ｐｐn+1,ｐｐn）のいずれかまたは両方を生成する第３ステップと、生成された降順記号Q若しくは昇順記号PPのいずれかまたは両方を、検査記号或いはシンドロームとして出力する第４ステップとを有する方法を、符号化方法及び復号化方法の共通の処理として、長さL＝２h−h−１（ｈは２以上の整数）の情報記号X＝（ｘL-1,ｘL-2,・・・,ｘ1,���0）を情報データとして伝送する場合、符号語Ｙの符号長をN＝２h、検査記号をQ＝（ｑh-1,ｑh-2,・・・ｑ1,ｑ0）及びパリティｐとした時、符号語Ｙの符号長が１ワード以下の場合は、長さＮの記号Ｘ'の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の内の添字ｉが０，２0，２1，・・・，２h-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に情報記号Ｘの要素を右から並べ拡張した記号Ｘ'＝（ｘL-1,ｘL-2,・・・,ｘL-N/2+1,0,ｘL-N/2,・・・,ｘ10,ｘ9,ｘ8,ｘ7,ｘ6,ｘ5,ｘ4,0,ｘ3,ｘ2,ｘ1,0,ｘ0,0,0,0）の要素ｘ'i（ｉ＝０，１，２，・・・，２h−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２h-1個の異なる要素の排他的論理和を算出し、検査記号Ｑの要素ｑj（ｊ＝０，１，２，・・・，ｈ−１）とし検査記号のデータとして生成する第５ステップと、計算されたｑi及び情報記号のｘiの全要素の排他的論理和を算出し検査記号の内のパリティｐとしデータとして生成する第６ステップとを有し、符号語ＹがＭワード（Ｍ＝２m、１ワードのビット長Lw=２n、ｍは1以上の整数でｈ＝ｍ+ｎ）の長さの場合は、長さＮの記号Ｘ'の要素ｘ'i（ｉ＝０，１，２，・・・，２m+n−１）の内の添字ｉが０，２0，２1，・・・，２m+n-1の要素の位置を０とし、残りの位置の要素ｘ'iとして添字ｉの昇順に情報記号Ｘの要素を右から並べ拡張した記号Ｘ'＝（ｘL-1,ｘL-2,・・・,ｘL-N/2+1,0,ｘL-N/2,・・・,ｘ10,ｘ9,ｘ8,ｘ7,ｘ6,ｘ5,ｘ4,0,ｘ3,ｘ2,ｘ1,0,ｘ0,0,0,0）の要素ｘ'i（ｉ＝０，１，２，・・・，２m+n−１）の添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）個を１組として２j個おきに選択した全部で２m+n-1個の異なる要素の排他的論理和をとり検査記号Qの要素を算出する際に、共通の処理において情報記号列Ｖとして拡張した記号Ｘ' を使い得られる降順記号Qを検査記号Qとし検査記号のデータとし、得られる要素列Ｐwの全ての要素の排他的論理和をパリティｐとして生成する第７ステップを有し、拡張した記号Ｘ'の追加された０の位置にある要素ｘ'i（ｉ＝０，２0，２1，・・・，２h-1）を添字ｉの昇順にパリティｐ，ｑk（ｋ＝０，１，２，・・・，ｈ−１）で置き換えることにより符号語Ｙ＝（ｘL-1,ｘL-2,・・・,ｘL-N/2+1,ｑh-1,ｘL-N/2,・・・,ｘ10,ｘ9,ｘ8,ｘ7,ｘ6,ｘ5,ｘ4,ｑ3,ｘ3,ｘ2,ｘ1,ｑ2,ｘ0,ｑ1,ｑ0,ｐ）をデータとして生成する第８ステップとを有する方法によって符号化処理がされ、符号語Ｙがデータ伝送され受信した情報データである符号語Ｙ'＝（ｙ'N-1,y'N-2,・・・,y'1,y'0）を復号する場合、符号語Ｙ'の符号長が１ワード以下の場合は、受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｈ−１）個を１組として２j個おきに選択した全部で２h-1個の異なる要素の排他的論理和を算出しシンドロームＳ＝（ｓh-1,ｓh-2,・・・ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，ｈ−１）として生成する第９ステップと、符号語Ｙ'の要素y'iの全要素の排他的論理和を算出しシンドロームＳの要素ｒとしデータとして生成する第１０ステップと、シンドロームから誤りの有無と種類を判定する第１１ステップと、ｒ＝１で１ビット誤りと判定された場合は、（ｓh -1, ｓh -2,・・・ｓ1,ｓ0）で指定される位置の符号語Ｙ'の要素の値を反転し符号語Ｙ'を訂正する第１２ステップと、訂正された符号語Ｙ'から情報記号Ｚ＝（ｚL-1,ｚL-2,・・・,ｚ1,ｚ0）を抽出し誤り訂正後の情報データとして出力する第１３ステップとを有し、符号語Ｙ'がＭワードの長さの場合は、受信した符号語Ｙ'の要素y'i（ｉ＝０，１，２，・・・，N−１）から添字の大きいほうから降順に２j（ｊ＝０，１，２，・・・，ｎ−１）個を１組として２j個おきに選択した全部で２n-1個の異なる要素の排他的論理和を算出する際に、共通の処理において情報記号列Ｖとして符号語Ｙ'を使い得られる降順記号Qの要素をシンドロームＳ＝（ｓm+n-1,ｓm+n-2,・・・,ｓn, ,ｓn-1, ・・・,ｓ1,ｓ0,ｒ）の要素ｓj（ｊ＝０，１，２，・・・，ｍ＋ｎ−１）とし、得られる要素列Ｐwの全ての要素の排他的論理和をシンドロームＳの要素ｒとして生成する第１４ステップと、シンドロームから誤りの有無と種類を判定する第１５ステップと、ｒ＝１で１ビット誤りと判定された場合は、シンドロームＳの上位ｍビットＳH＝（ｓm+n-1,ｓm+n-2,・・・,ｓn）に対応するワード番号及びシンドロームＳのｒのビット位置を除く下位ｎビットＳL＝（ｓn-1, ・・・,ｓ1,ｓ0）に対応するワード中のビット位置で指定される符号語Ｙ'の要素の値を反転し符号語Ｙ'を訂正する第１６ステップと、訂正された符号語Ｙ'から情報記号Ｚ＝（ｚL-1,ｚL-2,・・・,ｚ1,ｚ0）を抽出し誤り訂正後の情報データとして出力する第１７ステップとを有する方法によって復号化処理がされる。ハミング符号及び拡大ハミング符号での検査記号及びシンドロームの計算式は高い規則性を持たない（図４、図５、図８参照）。そこで、スーパー・ハミング符号で符号化の方法を工夫することにより、図１３及び図１９のような規則性の高い計算式を用いてシンドロームの計算が行え、かつビット誤りが発生した位置の特定が容易に行える。n=4の場合について、拡大ハミング符号及びスーパー・ハミング符号で演算に用いる情報記号及び情報記号を拡張した記号のビット位置を、それぞれ図２０及び図２１に示す。図２０及び図２１から明らかなように、スーパー・ハミング符号の演算式は同じパターンの繰り返し構造になっており、符号語の長さが変化しても、同じ計算式を繰り返して適用すれば良いことがわかる。また、この計算パターンを命令として用意しておけば、効率
良く検査記号やシンドロームの計算が行える。
【０１００】
なお、情報記号の入力ｘL-1，ｘL-2，・・・，ｘ0を逆順にして、ｘ0，ｘ1，・・・，ｘL-1とし、検査記号の記号列ｑh-1,ｑh-2,・・・ｑ1,ｑ0の計算式と同じ形式の記号を検査記号として同様の処理が可能である。すなわち、図21においては演算に用いる情報記号を拡張した記号のビット位置と演算に用いないビット位置を反転したことに相当する。
【０１０１】
このように、スーパー・ハミング符号は符号長に対する柔軟性が高いので、この特徴を活かして、通信時の伝送誤り率に応じて最適な符号長を用いた通信システムを構築できる。たとえば、伝送誤り率が低い場合には、符号長を長くして伝送効率を上げることができ、処理時間のオーバーヘッドの減少と消費電力量の削減が可能になる。また、伝送誤り率が高い場合には、符号長を短くして、ビット誤りに対する耐性を向上させることが可能になる。
【０１０２】
（実施の形態１）
拡大ハミング符号などの誤り訂正符号では、符号化を行うときに、情報記号に対応する検査記号を計算する。また、受信した符号語を復号し、誤り訂正を行うために、シンドロームを計算する。これらの計算では、ビットベクトルの内積の計算が必要になる。この計算は、2つのベクトルの対応するビットごとの論理積とその結果の全ビットの2を法とした加算によって計算されるが、この演算は、排他的論理和演算を用いることによって行える。しかし、汎用計算機には、このような演算は命令としては用意されていないので、検査ベクトルやシンドロームの計算は、複数の演算命令や制御命令を組み合わせて実行せざるを得ない。そのため、検査記号やシンドロームの計算には、長い実行サイクル数が必要となる。また、誤り訂正の際にも、シンドロームの値を用いて、誤りが生じた位置を特定する必要があるが、汎用計算機にはこの演算に適した命令が含まれていないので、誤り位置の特定には長い実行サイクルが必要である。
【０１０３】
そこで、検査記号やシンドロームの計算を少ない実行サイクル数で実行できる命令や、誤り訂正を少ない実行サイクルで実行できる命令を備えた図２２に示すような特定応用分野向きプロセッサ（ASIP: Application Specific Instruction-set Processor）を用いる誤り訂正符号処理装置２２０を実施例のひとつとして以下に説明する。これにより、データの符号化、復号、誤り訂正、誤り検出などの処理を、効率良くかつ少ない消費電力量で実行できる。
【０１０４】
図２２において、誤り訂正符号処理装置２２０はＲＩＳＣ（Reduced Instruction Set Computer：縮小命令セットコンピュータ）プロセッサ２２２、検査行列・シンドローム演算回路２２３及び誤り訂正回路２２４を含み、これらは内部バス２２７でつながっている。また、誤り訂正符号処理装置２２０の外部には命令メモリ２２５があり、ここからＲＩＳＣプロセッサ２２２に命令を読み出し実行する。また、データメモリ２２６にはデータが保存されている。実行する命令の必要に応じて誤り訂正符号処理装置２２０にデータバス２２８を通じてデータメモリ２２６から読みだされたデータが入力され検査行列・シンドローム演算回路２２３及び誤り訂正回路２２４等の演算に使用された後、演算結果を、データバス２２８を通じてデータメモリ２２６に保存する。データメモリ２２６に書き込み或いは読み出される外部からの或いは外部へのデータは、データバス２２８を介し入出力インターフェース（図示せず）を通じ誤り訂正符号処理装置２２０の外部とやりとりされる。
【０１０５】
ＲＩＳＣプロセッサ２２２は命令として以下の（ａ）から（ｆ）で示す専用命令と補助命令を命令メモリ２２５に備える。なお、ここでプロセッサをＲＩＳＣプロセッサとしたが、ＣＩＳＣプロセッサなどのプロセッサでもよい。
【０１０６】
(a)情報記号から符号語を生成するために情報記号を再配置する専用命令
【０１０７】
プロセッサの1ワードのビット長をＮw＝２nとし、ビットのインデックスは、右端を0とし、左端をＮw−１とする。Ｎw＝１６の場合のインデックスの付け方を図２３に示す。式１０で、符号語に検査記号及びパリティを埋めていく位置は、ビットのインデックスが0もしくは2のべき乗になっている。1ワードが16ビットの場合（ｎ＝４）に、4ワードからなるデータに一連のインデックスを割り当てる場合を考える。最も小さいインデックスを持つ最初のワードの中には、ｎ＋１個の検査記号及びパリティが埋め込まれる。2ワード目の右端のインデックスは２n＝１６なので、この位置に検査記号が埋め込まれる。また同様に、3ワード目の右端のインデックスは２n+1＝３２なので、この位置にも検査記号が埋め込まれる。しかし、4ワード目に含まれるビットのインデックスは48〜63であり、いずれも2のべき乗ではないので、4ワード目には検査記号が埋め込まれない。この例について、検査記号が埋め込まれる位置を図２４に示す。Ｎwの値が異なっても、検査記号が埋め込まれる位置は、同様の規則に従う。
【０１０８】
まとめると、検査記号が埋め込まれる位置は次の(1)〜(3)のような規則に従うことが知られる。
(1)1ワード目にはｎ＋１個の検査記号が埋め込まれる。
(2)2ワード目以降で検査記号が埋め込まれる場合には、必ずワードの右端になる。
(3)4ワード目以降では、検査記号が埋め込まれないワードが存在する。
【０１０９】
上記の規則を考慮すると、図２５〜図２７に示すブロック図の機能を持つ3種類の命令を用いれば、任意の長さの情報記号を符号語の形式に変換できることが知られる。なお、図２５〜図２７は、Ｎw＝１６の場合を例として示してあるが、Ｎwが2のべき乗であれば、より長い語長であっても同様の3種類の命令で処理が可能である。これら3種類の命令を用いて、1ワードの長さが16ビットの場合に、4ワードを用いて表現される、式７の形の57ビットの情報記号Xを式８の形式の拡張された情報記号X'に変換する例を、図２８〜図３１に示す。X'のワード0を得るためには、図２５の再配置命令(1)を用いれば良い。X'のワード1及びワード2を得るためには、図２６の再配置命令(2)を用いれば良い。X'のワード3を得るためには、図２７の再配置命令(3)を用いれば良い。なお、X'の要素のサフィックスについては通し番号ではなく、各ワード内の番号で表示している。図２６及び図２７で用いられているバレルシフタは、入力された2ワード分のビット列[a2n-1,・・・,a1,a0]から1ワード分のビット列[bn-1,・・・,b1,b0]を効率良く切り出す演算器である。このとき、シフト量をｋ（０≦ｋ＜ｎ）とすると、出力は[bn-1,・・・,b1,b0]＝[an+k-1,・・・,ak+1,ak]となる。バレルシフタの実装例を図３２に示す。図３２の中央部の正方形の箱は、2対1のマルチプレクサであり、制御信号の値によって、2つの入力のうちの一方を選択する。
【０１１０】
Xのワード長が4よりも長い場合にも同様に、図２５〜２７の3種類の再配置命令を用いることにより、情報記号の再配置を効率良く行える。
【０１１１】
(b)復号された符号語から情報記号を抽出する専用命令
【０１１２】
前記(a)で述べた、検査記号が埋め込まれる位置に関する規則を考慮すると、図３３〜図３５に示すブロック図の機能を持つ3種類の命令を用いれば、任意の長さの符号語から情報記号を抽出できる。これら3種類の命令のうち、図３５の情報記号抽出命令行目(3)は、図２７の情報記号再配置命令(3)と同じ機能を持っているので、図２７の命令を両方の目的に用いてもよい。図３３〜図３５は、1語が16ビットのプロセッサでの命令の機能を示しているが、プロセッサの語長が2のべき乗であれば、より長い語長であっても同様の3種類の命令で処理が可能である。たとえば、1ワードの長さが16ビットの場合に、4ワード（64ビット）で表現される符号語から57ビットの情報記号を抽出する場合には、図３３〜図３５に示す情報記号抽出命令を用いれば良い。これら3種類の命令を用いて4ワードの符号語から情報記号を抽出する方法を、図３６〜図３９に示す。符号語がさらに長い場合にも、これら3種類の命令を用いることにより、情報記号の抽出を効率良く行える。
【０１１３】
(c)1ワード以下の長さの符号語に対する検査記号とシンドロームの計算を1サイクルで実行する専用命令
【０１１４】
1ワードのビット数がＮwの場合、Ｌ＝２n−ｎ−１以下の長さの情報記号を入力し、検査記号及びパリティまたはシンドロームを1サイクルで計算する専用命令は容易に実現できる。このとき、検査記号の計算では図１４のように、また、シンドロームの計算では図４０のように、入力の全ビットの排他的論理和p及びrを同時に計算しておくと、2ワード以上の長さの記号列の検査記号とシンドロームの計算で必要となる情報も同時に計算できる。演算対象となるビットの位置を図４１に示す。出力は、pまたはrを含めてもｎ＋１ビットなので、1ワード（Ｎw＝２nビット）に十分に納まる。
【０１１５】
(d)1ワード以下の長さの符号語の誤りの検出と訂正を1サイクルで実行する専用命令
【０１１６】
前記(c)の専用命令で計算されたシンドロームS=[sn-1,sn-2,・・・,s1,s0,ｒ]を用いて、誤り検出を行うためには、拡大ハミング符号の場合と同様に、表１に示すようにして誤りの有無と種類を判定できる。表１で、tは、ベクトル(sn-1,sn-2,・・・,s1,s0)の全ビットの論理和を表わす。
【０１１７】
【表１】
2011142133.tif 000016
【０１１８】
1ビット誤りの訂正を行う命令は、たとえば、図４２に示す回路を用いれば容易に実装できる。
【０１１９】
(e)上記(c)の命令を繰り返し用いて、2ワード以上の長さの記号列の検査記号とシンドロームの計算を効率良く実行するための補助命令
【０１２０】
式１０で表現される記号列の長さが2ワード分以上の長さを持つ場合には、検査記号（またはシンドローム）は次のようにして計算すれば良い。まず、検査記号の計算について説明する。1ワードのビット長Ｎ＝２nとする。また、符号化すべき記号列の長さをM＝２mワードとする。ワードの番号を、0からM-1とする。i番目のワードの検査記号をＱi＝[ｑi,n-1，ｑi,n-2，・・・，ｑi,1，ｑi,0]とする。また、i番目のワードの全ビットの排他的論理和をpiとする。全ワードに対する検査記号Ｑ＝[ｑm+n-1，・・・，ｑ1，ｑ0]は、図４３に示すように、各ワードの検査記号と全ビットの排他的論理和を用いて計算できる。
【０１２１】
M個のワードWM-1,WM-2,・・・,W1,W0に格納された拡張された情報記号に対する検査記号の計算手順の例を図４４に示す。図４４で、f(Wi）はWiに対する検査記号列を、parity(Wi)はWiの全ピットの排他的論理和を、binary(i)は整数iの二進数表現を、それぞれ表わす関数である。シンドロームの計算も図４５の式に示すように、各ワードのシンドロームと全ビットの排他的論理和を用いて計算できる。M個のワードWM-1,WM-2,・・・,W1,W0に格納された符号語に対するシンドロームの計算手順の例を図４６に示す。図４６で、ｇ(Wi）はWiに対するシンドロームを、parity(Wi)はWiの全ピットの排他的論理和を、binary(i)は整数iの二進数表現を、それぞれ表わす関数である。
【０１２２】
(f)2ワード以上の長さの符号語の誤り検出・誤り訂正を効率良く実行するための補助命令
【０１２３】
2ワード以上の長さの符号語に対して上記(e)の補助命令で生成されたシンドロームを解析すれば、符号語全体の誤り検出及び誤り訂正が容易に行える。得られたシンドロームの上位ｍビットSH＝[ｓm+n-1，・・・，ｓn+1，ｓn]は、ワードの番号に対応し、下位ｎビットSL＝[ｓn-1，・・・，ｓ1，ｓ0]は、ワード中のビット位置に対応しているので、1ビット誤りを訂正する場合、シンドロームの上位ｍビットSHを用いて誤りが発生したワードを特定でき、シンドロームの下位ｎビットSLを用いて誤りが発生したビットを容易に特定できる。なお、本願発明の符号化を行うための装置及び復号・誤り訂正を行うための装置を実装する手法は、上記のものに限られない。たとえば、図１０（従来手法（Ａ））及び図１１（従来手法（Ｂ））に示す従来の実装手法を用いてもよい。本発明の実施の形態１の特徴をまとめると、次の(1)〜(3)の通りである。
(1)＜高符号化率＞拡大ハミング符号と同じ高い符号化率を持つので、効率よく情報伝送が行える。
(2)＜高性能かつ低消費電力量＞実装方法として、図２２に示すように、符号化、復号化に適した専用命令を持つプロセッサを用いることにより、汎用プロセッサとソフトウェアによる実装方法と同様に仕様変更に柔軟に対応可能であり、専用ハードウェアによる実装方法と同様に、高性能かつ低消費電力量となる。実施の形態1での実装方法の特徴を従来手法と比較して表２に示す。
(3)＜仕様変更に対する柔軟性＞拡大ハミング符号を改良して検査記号の計算式に対称性を持たせている。これにより、符号語の長さが大きい場合にも計算が容易に行えるようになる。また、符号語の長さが変更されても対応が容易になる。
【０１２４】
上記の特徴(1)は、新しい符号化方式を用いることによる利点である。また、特徴(2)及び(3)は、符号化及び復号化処理の実装方法に伴う利点である。特徴(2)及び(3)に関して、従来手法と実施の形態１の手法を比較して表２に示す。なお、表２中で、実施例１の手法は、実施の形態１の手法に対応し、以下、提案手法とも呼ぶ。また、表２中で、他の手法（Ａ）は、従来手法（Ａ）に対応し、他の手法（Ｂ）は、従来手法（Ｂ）に対応する。
【０１２５】
【表２】
2011142133.tif 000017
【０１２６】
従来手法(A)を用いて、シンドロームの計算を行うためには、xの要素数をnとして、n×(n-1)回の排他的論理和演算が必要になるので、計算時間の複雑さはＯ（ｎ2）となる。また、受信したデータに対するシンドロームの計算が終わった後で、誤りの検出・訂正を行うためには、上記の場合分けに対応する条件判断と分岐、それに引き続くビット演算をソフトウェアで実行する必要がある。
【０１２７】
一方、従来手法(B)を用いてこれらの式を計算するためには、排他的論理和演算器を配置した規則性の高い演算回路を用いることにより、Ｏ（ｎ）の遅延時間で効率よく計算できる。また、受信した符号語に対するシンドロームの計算、誤りの検出・訂正は組合せ論理回路で実装可能である。ただし、符号長が長い場合には、複数のクロックサイクルで演算を行う必要があるので、データパス（演算回路）とコントローラ（順序回路）を組み合わせて実装することになる。
【０１２８】
従来手法(B)では、図１１に示すように、復号化回路１２４を周辺回路として、コンピュータのデータバス１２５に接続し、データメモリ１２２の入出力によってデータの授受を行うのが標準的な方法である。この場合、汎用プロセッサ１２０は、復号化回路１２４に対して、実行すべき処理（初期化、符号化、復号など）を指示するコマンドとデータを渡し、処理が終了するのを待ち、誤りがあったか、訂正可能であったかなどのステータス（状態）情報と訂正後のデータを受け取ることになる。
【０１２９】
従来手法(B)では、符号化で用いられる生成行列とシンドロームの計算に用いられる検査行列には共通点があるので、符号化と復号を同時に行わない場合には、同一の専用ハードウェア回路を用いて、符号化と復号の処理を効率的に行える。しかし、専用ハードウェアの内部構成（レジスタやメモリの大きさ、制御回路など）は、取り扱う符号化方式と符号長の上限を考慮して、あらかじめ作りこんでおく必要があるので、あらかじめ仕様が確定している場合以外には過剰な仕様にせざるを得ず、柔軟性や拡張性が乏しい。
【０１３０】
実施の形態１で提案する、専用命令を追加したプロセッサによる実装方式は、図２２に示す単純な命令セットを持つRISCプロセッサ２２２に、(1)情報記号の再配置を行う命令、(2)検査記号やシンドロームの計算を行う命令、(3)誤り検出と訂正を行う命令などを追加することにより符号化や復号の処理を効率良く実行させる方法である。提案手法の特徴は、表２に示したように、従来手法(B)と同程度の処理性能（実行サイクル数）と少ない消費電力量での実行能力を持ちつつ、汎用プロセッサ上でのソフトウェア処理と同様の柔軟さと拡張性が達成されることである。
【０１３１】
実行サイクル数に関しては、提案手法は従来手法(B)よりも少ないサイクル数で処理できる可能性が高い。その理由は次の通りである。従来手法(B)では、図１１に示す復号化回路１２４にコマンドとデータを与え、ステータスを確認し、結果のデータを取得するというプロトコルを実行する必要があり、これがオーバーヘッドになる。提案手法では、命令の実行がコマンドの実行に対応しており、プロセッサのレジスタを用いて演算回路にデータを渡すことができる。そのため、従来手法(B)で必要だった、プロトコルのオーバーヘッドを軽減できることになる。また、これに伴い、消費電力量も従来手法(B)よりも少なくなると期待できる。
【０１３２】
一方、本願発明は、情報伝送の他に、コンピュータのメモリやバスなどの伝送路の誤り訂正などの応用分野に適用可能である。コンピュータのメモリや伝送路などで、同時に転送するデータのビット数などのパラメータは固定されている場合には、専用ハードウェア回路で実装することで最大限の効果が発揮できる。また、情報伝送の場合には、通信方式の仕様が固定的かどうかによって、専用ハードウェア回路での実装と特定応用分野向きプロセッサ（ASIP）による実装の両方の選択肢がある。
【０１３３】
（実施の形態２）
高次元パリティ符号は、L＝２n個の情報記号に対して、２ｎ個の検査記号を付加して符号語を構成する。高次元パリティ符号で用いられる検査記号及びシンドロームの計算式を図４７に示す。この形式の高次元パリティは、1ビット誤り訂正可能、2ビット誤り検出可能である。したがって、拡大ハミング符号やスーパー・ハミング符号と同じ強さのビット誤り訂正・検出能力を持っている。
【０１３４】
符号化率の点では、高次元パリティ符号はハミング符号、拡大ハミング符号、スーパー・ハミング符号に劣るが、高次元パリティ符号の検査記号及びシンドロームの計算式は高い規則性を持っている。高次元パリティ符号で用いられる検査記号の計算式のうち、ｑn-1，ｑn-2，・・・，ｑ0，ｒの計算式は、スーパー・ハミング符号の検査記号の計算式と同じ形式である。また、図４８に示すように、高次元パリティ符号で用いられる検査記号の計算式のうち、ｐ0，ｐ1，・・・，ｐn-1の計算式は、入力ｘn-1，ｘn-2，・・・，ｘ0を逆順にして、ｘ0，ｘ1，・・・，ｘn-1とすると、ｑ0，ｑ1，・・・，ｑn-1の計算式と全く同じ形式になる。したがって、実施の形態１で述べた、スーパー・ハミング符号のための専用命令を拡張することにより、高次元パリティ符号を効率良く処理できる専用命令を実装できる。
【０１３５】
情報記号の長さが複数のワードに格納されている場合についても、実施の形態１で述べたスーパー・ハミング符号の場合と同様にして、容易に拡張できる。なお、復号化の手順は、以下のようになる。
(1)受信した検査記号と受信した情報記号から計算した検査記号の排他的論理和をとリ、シンドロームを生成する。シンドロームを検査し、
(a)全てのビットが０の場合は、誤りなし、（b）一つでも０でないビットがあった場合  は、次の(2)のステップへ。
(2)シンドロームのp成分とｑ成分の排他的論理和をとり、
(a)全てのビットが１の場合は、受信した情報記号に１ビット誤りあり、(b)いずれかのビットに一つだけ１がある場合は、受信した検査記号に１ビット誤りあり、(c)全てのビットが０の場合は、受信した情報記号に２ビット誤りありとする。
(3) 受信した情報記号に１ビット誤りがある場合に、シンドロームのｑ成分で指定される受信した情報記号の誤りを訂正する。
【０１３６】
（実施の形態３）
スーパー・ハミング符号は符号長に対する柔軟性が高いので、この特徴を活かして、通信時の伝送誤り率に応じて最適な符号長を用いた通信システムを構築できる。たとえば、伝送誤り率が低い場合には、符号長を長くして伝送効率を上げることができ、処理時間のオーバーヘッドの減少と消費電力量の削減が可能になる。また、伝送誤り率が高い場合には、符号長を短くして、ビット誤りに対する耐性を向上させることが可能になる。このような符号語長の調整による適用的通信方式は、次の(a)、(b)のような状況に有効に応用できる。
(a)ビット誤り率が未知の通信路に対する適用
(b)ビット誤り率が時間とともに緩やかに変化する通信路に対する適用
【０１３７】
符号語長の調整手続きの例を図４９に示す。符号長を変更する場合、送信システム側及び受信システム側の双方で、送受信システムの設定変更を行う必要があり、そのための時間的及びエネルギー（消費電力量）のオーバーヘッドが生じる。したがって、頻繁に符号語長の変更を行うことは好ましくない。上記の符号語長調整手続きでは、ビット誤り率の2つのしきい値（ＥH，ＥL）を用いて符号語長を調整することにより、ビット誤り率の微小な変動に対して頻繁に符号語長を変更する必要がなくなる。符号語長調整手続きの、ビット誤り率の変動に対するレスポンス（感度）は、パラメータＥH、ＥL、及びＣLの値を修正することによって制御可能である。
【０１３８】
（実施の形態４）
データ伝送を行う携帯端末を、伝送中に連続した複数ビットの誤り（以下、バースト誤りという）が発生する可能性がある環境で使用する場合、誤りを検出し訂正する手段としては、バースト誤り検出符号の中では計算量が小さく、複雑な演算が不要なＣＲＣ（Ｃｙｃｌｉｃ  Ｒｅｄｕｎｄａｎｃｙ  Ｃｈｅｃｋｉｎｇ：巡回）符号が用いられている。
【０１３９】
以下、本発明の実施の形態４に係るＣＲＣ符号に基づく誤り訂正符号処理方法について説明する。ここで、本発明のＣＲＣ符号化方法とは、以下（１）の回路で行われる検査記号計算方法を含む。また、本発明のＣＲＣ復号化方法とは、以下（２）及び（３）の回路で行われるシンドローム計算及び誤り訂正方法を含む。
【０１４０】
（１）検査記号計算回路
ＣＲＣ符号における検査記号は、情報記号Ｘの生成多項式ｇ（ｘ）による剰余で求められる。ここで、情報記号Ｘは、式１４によって表される。
【０１４１】
【数１４】
2011142133.tif 000018
【０１４２】
ｘiの係数αiは2のガロア体上で計算され、係数の加算は排他的論理和として計算される。計算機上では、情報はｘiの係数αiをｉビット目に配置したビット列で表現される。
【０１４３】
ＣＲＣ符号の検査記号の計算フローを図５０に示す。生成多項式を用いた符号化方法の検査記号を計算するための剰余演算は、以下（ａ）〜（ｄ）の手順で計算され、そのうち、（ｂ）及び（ｃ）は複数回の繰り返しが必要となる。
（ａ）中間データＡjの初期値Ａ0を情報記号をとする
（ｂ）中間データＡjを1ビットシフトし、データＡ’jを得る
（ｃ）Ａ’jの最上位ビットが1のとき、Ａ’jと生成多項式を表すビット列の排他的論理和を計算し、次ステップの中間データＡj+1を得る
（ｄ）情報記号のビット幅をＬiとすると、ｊ＜Ｌi−１であればｊ＝ｊ＋１ として（ｂ）にもどり、ｊ＝Ｌi−１であればＡ’Li-1（ｉは下付き文字）を検査記号とする
以下、上記（ｂ）及び（ｃ）を操作（Ａ）と表記する。
【０１４４】
操作（Ａ）は、Ａj+1＝ＡjＧの形式の行列演算に帰着させることができる。 また、ｎ回の連続した操作はＡj+1＝ＡjＧnと表すことができる。本発明では、任意のｎに対してＧnを乗ずる回路を使用することにより、検査記号の計算を高速化する。生成多項式ｘｘ8＋ｘ2＋ｘ＋１に対するＧを図５１に示す。
【０１４５】
情報記号のビット幅をＬi、検査記号のビット幅をＬcとすると、検査記号計算処理は式１５によって表される。
【０１４６】
【数１５】
2011142133.tif 000019
【０１４７】
ここで、Ｌc＜Ｌd＜Ｌi＋Ｌcとすると、検査記号計算処理は式１６により再帰的に分割することができる。
【０１４８】
【数１６】
2011142133.tif 000020
【０１４９】
式１６により処理をｎビット単位に分割し、Ｇ2n、Ｇnを計算する回路を用いて検査記号の計算を高速化する。たとえば、８ビット単位で検査行列を計算する場合にはＧ8及びＧ16を使用する。生成多項式ｘ8＋ｘ2＋ｘ＋１に対するＧ8及びＧ16はそれぞれ図５２及び図５３で表される。
【０１５０】
Ｇmを乗ずる専用演算器を図５４のように構成することにより、生成多項式を動的に変化させることができる。以下、操作（Ａ）の演算をｎサイクルで実行する方法について、（i）〜（vi）で説明する。
（i）ｎビットの入力データ用レジスタを持つ。入力されたデータは入力データ用レジスタに格納される。
（ii）ｎビットの行格納用レジスタ及びｎビット×ｎビットの行列表を持ち、行列表は行を指定することにより、指定された行の情報を行格納用レジスタに出力する。なお、図５４中の行列（Ｇm）T表は、Ｇmを表す行列の転置行列を表に配置したものである。たとえば、生成多項式ｘ8＋ｘ2＋ｘ＋１においてＧ8を乗ずる専用演算器のための表は、図５５のように構成される。行列表は、たとえば、RAMまたは複数のレジスタ等で実装する。
（iii）ｎビットの２入力AND演算器を持ち、AND演算器は入力データ用レジスタと行格納用レジスタの論理積を出力する。
（iv）ｎビットのパリティ演算器を持ち、パリティ演算器はAND演算器の出力に対して、すべてのビットの排他的論理和を出力する。
（v）ｎビットのシフトレジスタを持ち、シフトレジスタはパリティ演算器の演算結果を最下位ビットに格納する。また、シフトレジスタはシフト信号を入力することにより格納されている値を1ビット左シフトする。
（vi）シフトレジスタの出力を演算器の出力とする。
【０１５１】
なお、Ｇmを乗ずる専用演算器を図５６のように構成してもよい。図５６では、上記（ii）〜（v）の複数回の演算を並列に処理する専用演算器を用いることにより、処理をｎ並列化し、図５４と同じ演算を１サイクルで実行することができる。
【０１５２】
検査記号計算回路の実装例を図５７に示す。図５７は、１６ｂｉｔプロセッサに （２４，１６）ＣＲＣ符号処理回路を組み込むための回路である。生成多項式はｘ8＋ｘ2＋ｘ＋１を用いる。図５７中の、Ｇ8、Ｇ16はそれぞれ図５２、図５３の行列を乗ずる回路である。図５７の回路は、検査記号の計算途中の値をｒｄレジスタに、情報記号を順次ｒｓレジスタに入力することにより、１６回の操作（Ａ）を、図５４の専用演算器使用時には１サイクル、図５６の専用演算器使用時には８サイクルで行い、結果として得られる次の検査記号の途中結果をｒｄレジスタに書き戻す。
【０１５３】
（２）シンドローム計算回路
ＣＲＣ符号における符号語からシンドロームを求める計算は、情報記号から検査記号を求める計算と同じである。したがって、シンドロームの計算には、（１）の検査記号計算回路を用いるため、説明を省略する。
【０１５４】
（３）誤り訂正回路
ＣＲＣ符号において1ビット誤りの誤り位置は、（２）のシンドローム計算回路により得られたシンドロームより計算する。
【０１５５】
情報記号のビット幅をＬi、検査記号のビット幅をＬcとし、ｅビット目に誤りがある場合、シンドロームの計算は式１７で表される。
【０１５６】
【数１７】
2011142133.tif 000021
【０１５７】
また、ＣＲＣ符号の性質上、以下に表される式１８は、ｇ（ｘ）で割り切れるため、シンドロームは式１９で表される。
【０１５８】
【数１８】
2011142133.tif 000022
【０１５９】
【数１９】
2011142133.tif 000023
【０１６０】
ｇ（ｘ）はＬc次以上の多項式であることから、１ビット誤りが下位のＬcビット中にある場合、つまりｅ＜Ｌcである場合、ｘeｍｏｄｇ（ｘ）＝ｘeであるため誤り位置はｅに一致する。
【０１６１】
以下（i）、（ii）では、１ビット誤りが下位のＬcビット中にある場合とそれ以外の場合についての誤り訂正について説明する。
（i）１ビット誤りが下位のＬcビット中にある場合
検査記号のビット幅をＬcとする符号語の下位のＬcビット中に１ビット誤りがある場合は、シンドロームにおいて１であるビットの位置は誤りビットの位置と一致する。また、シンドロームにおいて１であるビットの総数が１個であるのは、下位からＬcビットに１ビット誤りがある場合のみである。
（ii）１ビット誤りが下位のＬcビット中にない場合
符号語Ｙに対するシンドロームをＳ’としたとき、符号語Ｙをｋビット右シフトしたビット列Ｙ’に対するシンドロームＳ’は、Ｓ’×Ｇ-nと一致する。Ｇ-nを乗ずる操作は、検査記号計算回路で用いたＧの逆行列をｎ回乗ずる操作を表す。
【０１６２】
符号語をｋビット右シフトし、同時にシンドロームにＧ-kを乗ずる。このとき、シンドロームにＧ-kを掛けたビット列Ｓ’において１であるビットの総数が１個である場合、下位からＬcビットに１ビット誤りがあると判定して誤りを訂正する。Ｓ’に１であるビットが２個以上の場合は上記操作を繰り返す。
【０１６３】
誤り訂正回路においても、生成多項式を動的に変更する場合は、検査記号計算と同様にＧmを乗ずる専用演算器を図５４または図５６のように構成する。
【０１６４】
誤り訂正回路の実装例を図５８に示す。図５８は、１６ｂｉｔプロセッサに （２４，１６）ＣＲＣ符号処理回路を組み込むための回路である。生成多項式はｘ8＋ｘ2＋ｘ＋１を用いる。図５８中のｂｉｔ  ｔｅｓｔは、入力値に1のビットが1個のみ存在する場合は入力値を、それ以外の場合は０を出力する回路である。また、図５８中のＧ-8は，図５９の行列を乗ずる回路である。図５８の回路は、符号語をｒｄレジスタに、シンドロームをｒｓレジスタの上位８ビットに入力することにより、図５４の専用演算器使用時には２サイクル、図５６の専用演算器使用時には１６サイクルで行い、訂正済みの符号語をｒｄレジスタに書き戻す。
【０１６５】
以上、CRC符号での符号化及び復号化方法の手順をまとめると、以下の通りとなる。情報記号をｘを変数（モジュロ２）とする多項式で表現した情報記号多項式にｘk（生成多項式の次数ｋ）を乗じたシフト情報記号多項式を生成多項式で除算し剰余を算出する第１の演算により、剰余の多項式の係数を検査記号として求め、情報記号と合わせて符号語を生成し、データとして送信する場合、第１の演算におけるシフト情報記号多項式の変数ｘの最高次からの各項を生成多項式にｘのべき乗を乗算し引くことにより段階的に消去する各段の第２の演算をシフト情報記号多項式の係数を並べたベクトルから始まり各段の途中段階の剰余の係数を並べたベクトルに対する同一の行列Ｇとの積で表現し、所定の回数の前記行列Ｇのみの積を予め算出して第２の演算を所定の回数繰り返した後の第１の演算の部分演算単位を表現する部分演算行列とするステップ１と、シフト情報記号多項式のベクトルと部分演算行列との積を途中段階の剰余のベクトルとして求めることから始めて所定の回数ごとの途中段階の剰余のベクトルと部分演算行列との積を次の途中段階の剰余のベクトルとして順次求める演算を行い、検査記号を生成するステップ２とを有する方法によって符号化処理がされ、符号語がデータ伝送され受信したデータである受信符号語を復号する場合、受信符号語を多項式で表現した受信符号語多項式を生成多項式により除算し剰余を算出する第３の演算により、剰余の多項式の係数をシンドロームとして生成する際に、第３の演算における受信符号語多項式の変数ｘの最高次からの各項を生成多項式にｘのべき乗を乗算し引くことにより段階的に消去する各段の第４の演算において、受信符号語多項式のベクトルと部分演算行列との積を途中段階の剰余のベクトルとして求めることから始めて前記所定の回数ごとの途中段階の剰余のベクトルと部分演算行列との積を次の途中段階の剰余のベクトルとして順次求める演算を行い、シンドロームを生成するステップ１０と、部分行列の逆行列を予め算出するステップ１１と、シンドロームから誤りの有無と種類を判定するステップ１２と、シンドロームにおいて１であるビットの総数が１個であり、受信符号語の下位から検査記号のビット幅中に１ビット誤りがあると判定された場合、シンドロームの１であるビット位置で指定される受信符号語のビットの値を反転し符号語を訂正するステップ１３と、シンドロームにおいて１であるビットの総数が２個以上であり、シンドロームに逆行列を乗ずることを繰り返した結果、ｔ回目（ｔは１以上の整数）の結果のシンドロームにおいて１であるビットの総数が１個となり、検査記号のビット幅を単位幅として受信符号語の下位からｔ+１番目の位置のビット幅中に１ビット誤りがあると判定された場合、受信符号語の下位からｔ+１番目の位置のビット幅中のｔ回目の結果のシンドロームの１であるビット位置で指定されるビットの値を反転し符号語を訂正するステップ１４とを有する方法によって復号化処理がされる。
【０１６６】
なお、符号語を生成しデータとして送信するＣＲＣ符号化方法であって、１ワードのビット数が検査記号のビット長ｋの自然数倍ｍで情報がＭワードの長さの時、ステップ１において部分演算行列は所定の回数をｍｋ，（ｍ−１）ｋ，・・・，ｋ（ｋの倍数）としてｍ個の積行列Ｇmk，Ｇ(m-1)k，Ｇ(m-2)k，・・・，Ｇkであり、ステップ２においてシフト情報記号多項式のベクトルから始めて所定の回数ごとの途中段階の剰余のベクトルを順次求める演算を行うに替えて、シフト情報記号多項式のベクトルをワード毎にわけワード毎に一括した演算を順次行うに際して、１ワード中のビット幅ｋ単位のｋ個の要素を持つベクトルにわけてワード中の最初のビット幅のベクトルに対して積行列Ｇmkを乗じた結果のベクトルの要素とひとつ前のワードに対する一括した演算の結果のベクトルの要素との排他的論理和をとったベクトルの要素と、ワード中の次以降のビット幅の位置のｋ個の要素を持つ（ｍ−１）個のベクトルに対してそれぞれＧ(m-1)k，Ｇ(m-2)k，・・・，Ｇkを乗じた結果のベクトルの要素との排他的論理和をとりワード中の一括した演算として行ってもよい。
【０１６７】
また、符号語がデータ伝送され受信したデータである受信符号語を復号するＣＲＣ復号化方法であって、１ワードのビット数が検査記号のビット長ｋの自然数倍ｍで、情報がＭワードの長さの時、ステップ１０において、部分演算行列は所定の回数をｍｋ，（ｍ−１）ｋ，・・・，ｋ（ｋの倍数）としてｍ個の積行列Ｇmk，Ｇ(m-1)k，Ｇ(m-2)k，・・・，Ｇkであり、ステップ１０において、受信符号語多項式のベクトルから始めて所定の回数ごとの途中段階の剰余のベクトルを順次求める演算を行うに替えて、受信符号語多項式のベクトルをワード毎にわけワード毎に一括した演算を順次行うに際して、１ワード中のビット幅ｋ単位のｋ個の要素を持つベクトルにわけてワード中の最初のビット幅のベクトルに対して積行列Ｇmkを乗じた結果のベクトルの要素とひとつ前のワードに対する一括した演算の結果のベクトルの要素との排他的論理和をとったベクトルの要素と、ワード中の次以降のビット幅の位置のｋ個の要素を持つ（ｍ−１）個のベクトルに対してそれぞれＧ(m-1)k，Ｇ(m-2)k，・・・，Ｇkを乗じた結果のベクトルの要素との排他的論理和をとりワード中の一括した演算として行い、逆行列はＧkの逆行列Ｇ-kであってもよい。
【０１６８】
（実施の形態５）
プロセッサベースのシステムにＣＲＣ符号に基づく符号化を行う機能及び復号化を行う機能を付加する従来の手法は、
（１）汎用プロセッサ上のソフトウェアによる実装  （以下、従来手法（１）と呼ぶ。）
（２）専用ハードウェア（ASIC）を追加することによる実装  （以下、従来手法（２）と呼ぶ。）
（３）動的再構成可能ハードウェアを追加することによる実装  （以下、従来手法（３）と呼ぶ。）
の3種類に分類できる。上記の手法には、次のようなトレードオフが存在する。
【０１６９】
従来手法（１）のソフトウェアによる実装方法は、元の処理に使用する汎用プロセッサをそのまま使うことができるためハードウェアを追加する必要がなく、符号化方式の変更や符号長の変更に容易に対応できるが、実行サイクル数が多いため実行時間が長く、消費電力量が多いという欠点がある。
【０１７０】
従来手法（２）は、専用の回路を使用できるため実行サイクル数が少ないが、実装するために追加するハードウェア量が多く、また、符号化方式の変更や符号長の変更に容易に対応できないという欠点がある。
【０１７１】
従来手法（３）は、動的に回路を再構成することにより生成多項式や符号長の仕様を変更することができるが、消費電力量が多く、実装するために必要なハードウェア量も多いという欠点がある。
【０１７２】
半導体の微細化が進んだ結果、VLSIの集積度が向上し、クロック周波数も向上し、性能が向上している。しかし、その結果、VLSIの消費電力が増大傾向にある。特に、汎用プロセッサでは、消費電力の増大に伴う発熱量の増大と温度上昇が大きな問題になっている。従来手法（２）は、消費電力の点で従来手法（１）よりも優れているが、仕様変更に柔軟に対応することが困難である。また、仕様変更に柔軟に対応できるハードウェアを用いる従来手法（３）もハードウェアの消費電力量が多く、低電力化には適さない。したがって、符号の誤り耐性や符号長の変更に柔軟に対応でき、消費電力が少なく、かつ実行時間の短い実装方法を開発することが課題となっている。しかし、前述のように従来手法ではこのような要求を満たすことは困難である。
【０１７３】
そこで、本発明の実施の形態５に係る実装手法（以下、提案手法（１）と呼ぶ）は、実施の形態４に係る検査記号の計算、シンドロームの計算及び誤り訂正のための専用命令を持つプロセッサを用いることにより、誤り訂正符号処理装置を実装している。
【０１７４】
図６０Ａは、本発明に係る、提案手法（１）の構成を示す図である。図６０Ａにおいて、専用命令を含むプロセッサ３１０の外側には、命令メモリ３１１とデータメモリ３１２がある。命令メモリ３１１は、検査記号の計算、シンドロームの計算及び誤り訂正のための専用命令を含む命令を保持している。専用命令を含むプロセッサ３１０は、命令メモリ３１１から読み出された命令に従って、誤り訂正符号処理の符号化及び復号化演算を行う。また、専用命令を含むプロセッサ３１０は、命令メモリ３１１によって読み出された命令に従って、データバス３１３を通じてデータメモリ３１２に保持されているデータを読み出す。さらに、専用命令を含むプロセッサ３１０は、専用命令を含むプロセッサ３１０で行われた演算結果を、データバス３１３を通じてデータメモリ３１２に格納する。
【０１７５】
提案手法（１）は、以下（ａ）〜（ｃ）の特徴を持つ。
（ａ）専用ハードウェア及び再構成可能ハードウェアによる実装方法と同様に、実行時間が短い。
（ｂ）汎用プロセッサによる実装方法と同様に、低消費電力である。
（ｃ）汎用プロセッサ及び再構成可能ハードウェアによる実装方法と同様に符号の誤り耐性や符号長の仕様変更に柔軟に対応可能である。
【０１７６】
表３は、従来手法（１）、従来手法（２）、従来手法（３）及び提案手法（１）の特徴をまとめたものである。
【０１７７】
【表３】
2011142133.tif 000024
【０１７８】
なお、本願発明の符号化を行うための装置及び復号化を行うための装置を実装する手法は、上記のものに限られない。たとえば、以下に示す提案手法（２）及び提案手法（３）により、符号化を行うための装置及び復号化を行うための装置を実装することができる。
【０１７９】
提案手法(２)は、検査記号/シンドローム計算については、提案手法（１）で用いる専用プロセッサを使用し、誤り訂正については、従来手法である表引きを使用する方法である。
【０１８０】
図６０Ｂは、本発明に係る、提案手法（２）の構成を示す図である。図６０Ｂにおいて、専用命令を含むプロセッサ３２０の外側には、命令メモリ３２１と表引き用領域を含むデータメモリ３２２がある。命令メモリ３２１は、検査記号の計算、シンドロームの計算及び誤り訂正のための専用命令を含む命令を保持している。専用命令を含むプロセッサ３２０は、命令メモリ３２１から読み出された命令に従って、誤り訂正符号処理の符号化及び復号化演算を行う。また、専用命令を含むプロセッサ３２０は、命令メモリ３２１によって読み出された命令に従って、データバス３２３を通じて表引き用領域を含むデータメモリ３２２に保持されているデータを読み出す。ここで、表引き用領域を含むデータメモリ３２２は、誤り位置計算をするためのＬｏｏｋ−ｕｐ  Ｔａｂｌｅを保持している表引き用領域を含むメモリのことである。さらに、専用命令を含むプロセッサ３２０は、専用命令を含むプロセッサ３２０で行われた演算結果を、データバス３２３を通じて表引き用領域を含むデータメモリ３２２に格納する。
【０１８１】
提案手法(１)では、符号長に比例したサイクル数を誤り位置の計算に要するが、提案手法（２）では、表引きを用いることで、メモリアクセス1回分のサイクル数での計算が可能となる。ただし、表引き用のデータを格納するために必要なメモリの領域が大幅に増加するため、提案手法（２）は、提案手法（１）と比較してデータメモリの増加させる必要がある。
【０１８２】
提案手法（３）は、検査記号/シンドローム計算及び誤り訂正ともに、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）等の再構成可能ハードウェアで×Gmを行う専用演算器を構成する方法である。
【０１８３】
図６０Ｃは、本発明に係る、提案手法（３）の構成を示す図である。図６０Ｃにおいて、専用命令を含む動的再構成可能プロセッサ３３０の外側には、命令メモリ３３１とデータメモリ３３２がある。命令メモリ３３１は、検査記号の計算、シンドロームの計算及び誤り訂正のための専用命令を含む命令を保持している。専用命令を含む動的再構成可能プロセッサ３３０は、命令メモリ３３１から読み出された命令に従って、誤り訂正符号処理の符号化及び復号化演算を行う。また、専用命令を含む動的再構成可能プロセッサ３３０は、命令メモリ３３１から読み出された命令に従って、データバス３３３を通じてデータメモリ３３２に保持されているデータを読み出す。さらに、専用命令を含む動的再構成可能プロセッサ３３０は、専用命令を含む動的再構成可能プロセッサ３３０で行われた演算結果を、データバス３３３を通じてデータメモリ３３２に格納する。
【０１８４】
図６１に示すように、提案手法（３）は、×Gmを行う専用演算器をＦＰＧＡのＬｏｏｋ−ｕｐ  Ｔａｂｌｅを用いて構成することができるため、提案手法（１）と同等に高速な演算が可能である。なお、提案手法（３）は、ＥＣＣ（Ｅｒｒｏｒ  Ｃｈｅｃｋｉｎｇ  ａｎｄ  Ｃｏｒｒｅｃｔｉｏｎ）命令追加対象のベースシステムが再構成可能ハードウェアで構成されている場合、ハードウェアを追加する必要がない。
【０１８５】
表４は、提案手法（１）、提案手法（２）及び提案手法（３）における、検査記号/シンドローム計算及び誤り訂正方法をまとめたものである。
【０１８６】
【表４】
2011142133.tif 000025
【０１８７】
表５は、提案手法（１）、提案手法（２）及び提案手法（３）の特徴をまとめたものである。
【０１８８】
【表５】
2011142133.tif 000026
【０１８９】
（実施の形態６）
実施の形態６として、符号語長及び生成多項式の調整手続きの例（受信側）を図６２及び表６に示す。
【０１９０】
【表６】
2011142133.tif 000027
【０１９１】
誤り訂正レベルLは、例えば表６に示すように６段階に分け各レベルにおいて使用する生成多項式と符号長を決めておく。ここでは、生成多項式として8ビットCRC（CRC-8）と16ビットCRC（CRC-16）のものを用いる（具体的には、それぞれｘ8+ｘ2 +ｘ+ 1とｘ16 +ｘ15 +ｘ2 + 1）。
【０１９２】
図６２において、受信した符号語数CRをカウントし、またビット誤り回数CEを訂正可能な誤りを検出した場合にカウントし、ビット誤り率CE/CRを計算し、伝送誤り率の指標としている。
【０１９３】
符号長又は生成多項式を変更する場合、送信システム側および受信システム側の双方で、送受信システムの設定変更を行う必要があり、そのための時間的およびエネルギー（消費電力量）のオーバーヘッドが生じる。したがって、頻繁に符号語長及び生成多項式の変更を行うことは好ましくない。上記の符号語長及び生成多項式の調整手続きでは、ビット誤り率の2つのしきい値（ＥH，ＥL）を用いて符号語長を調整することにより、ビット誤り率の微小な変動に対して頻繁に符号語長を変更する必要がなくなる。
【０１９４】
すなわち、受信システムにおいて、例えば図６２に示すように、ビット誤り率CE/CRがＥHを超えた場合は、誤り訂正レベルLを上げ、誤りが検出されず（誤り検出処理は図示せず）受信した符号語数CRが誤り訂正レベル変更に必要な最小受信回数CLを超えかつビット誤り率CE/CRがＥLを下回った場合は、誤り訂正レベルLを下げるようにする。また、受信システムにおいて、誤り訂正レベルLは、L+1の計算により誤り訂正レベルの上限LHを超えた場合はLHとして、L-1の計算により誤り訂正レベルの下限LLを下回る場合はLLとする。そして、受信システムにおいて算出された誤り訂正レベルを送信システムに通知することで、送信システム側および受信システム側の双方で、送受信システムの設定変更を行うことができる。
【０１９５】
符号語長及び生成多項式の調整手続きの、ビット誤り率の変動に対するレスポンス（感度）は、パラメータＥH、ＥL、およびＣLの値を修正することによって制御可能である。
【０１９６】
これにより、ビットの誤り率に対応して、適応的に符号長の長さを変更できるので、誤りの少ない通信では符号化効率の高い長い符号長の誤り訂正符号を利用でき、誤りの多い通信では誤り訂正強度の強い短い符号長の誤り訂正符号を利用することができ、情報の再送を減らしつつできるだけ通信効率の良い符号長を選択可能となり通信に必要となる電力量を削減することができる。
【実施例】
【０１９７】
次に、本発明の実施の形態５に係る誤り符号処理装置の効果を確かめる実験が行われたので、その実験結果について、表７を参照しながら説明する。【０１９８】
表７は、本実施の形態４に係る回路を組み込んだプロセッサと、汎用プロセッサとを使用して、ＣＲＣ符号での誤り符号処理装置を実装した際の実行サイクル数の比較を示す。ここで、表７では、図５６、図５７及び図５８で構成される回路を組み込んだプロセッサを用いる手法を提案手法（１）とし、汎用プロセッサを用いる手法を従来手法（１）としている。【０１９９】
【表７】
2011142133.tif 000028
【０２００】
表７では、１６，３２，６４ビットの情報記号の符号化及び復号化に必要な実行サイクル数及び従来手法（１）に対する提案手法（１）の実行サイクル数の削減率を記載している。表７より、提案手法（１）は、従来手法（１）と比べて９０％以上の実行サイクル数の削減効果を確認することができる。【０２０１】
これにより、計算の実行サイクル数が削減できるので、符号化及び復号化の処理に必要な電力量を削減することができる。【０２０２】
以上、本発明の実施の形態に係る誤り訂正符号処理方法及び誤り訂正符号装置について説明したが、本発明は、この実施の形態に限定されるものではない。【０２０３】
たとえば、上記誤り訂正符号装置の構成は、本発明を具体的に説明するために例示するためのものであり、本発明に係る誤り訂正符号装置は、上記構成の全てを必ずしも備える必要はない。言い換えると、本発明に係る誤り訂正符号装置は、本発明の効果を実現できる最小限の構成のみを備えればよい。【０２０４】
同様に、上記の誤り訂正符号処理方法は、本発明を具体的に説明するために例示するためのものであり、本発明に係る誤り訂正符号処理方法は、上記ステップの全てを必ずしも含む必要はない。言い換えると、本発明に係る誤り訂正符号処理方法は、本発明の効果を実現できる最小限のステップのみを含めばよい。また、上記のステップが実行される順序は、本発明を具体的に説明するために例示するためのものであり、上記以外の順序であってもよい。また、上記ステップの一部が、他のステップと同時（並列）に実行されてもよい。【０２０５】
さらに、本発明の主旨を逸脱しない限り、本実施の形態に対して当業者が思いつく範囲内の変更を施した各種変形例も本発明に含まれる。
【産業上の利用可能性】
【０２０６】
本発明は、情報伝送や、コンピュータのメモリやバスなどの伝送路における誤り検出及び誤り訂正を行うことができる。
【符号の説明】
【０２０７】
１１０、１２０    汎用プロセッサ
１１１、１２１、２２５、３１１、３２１、３３１    命令メモリ
１１２、１２２、２２６、３１２、３３２    データメモリ
１１３、１２５、２２８、３１３、３２３、３３３    データバス
１２３    符号化回路
１２４    復号化回路
２２０    誤り訂正符号処理装置
２２２    ＲＩＳＣプロセッサ
２２３    検査行列・シンドローム演算回路
２２４    誤り訂正回路
２２７    内部バス
３１０、３２０    専用命令を含むプロセッサ
３２２    表引き用領域を含むデータメモリ
３３０    専用命令を含む動的再構成可能プロセッサ
【図１】
2011142133.tif 000029
【図２】
2011142133.tif 000030
【図３】
2011142133.tif 000031
【図４】
2011142133.tif 000032
【図５】
2011142133.tif 000033
【図６】
2011142133.tif 000034
【図７】
2011142133.tif 000035
【図８】
2011142133.tif 000036
【図９】
2011142133.tif 000037
【図１０】
2011142133.tif 000038
【図１１】
2011142133.tif 000039
【図１２】
2011142133.tif 000040
【図１３】
2011142133.tif 000041
【図１４】
2011142133.tif 000042
【図１５】
2011142133.tif 000043
【図１６】
2011142133.tif 000044
【図１７】
2011142133.tif 000045
【図１８】
2011142133.tif 000046
【図１９】
2011142133.tif 000047
【図２０】
2011142133.tif 000048
【図２１】
2011142133.tif 000049
【図２２】
2011142133.tif 000050
【図２３】
2011142133.tif 000051
【図２４】
2011142133.tif 000052
【図２５】
2011142133.tif 000053
【図２６】
2011142133.tif 000054
【図２７】
2011142133.tif 000055
【図２８】
2011142133.tif 000056
【図２９】
2011142133.tif 000057
【図３０】
2011142133.tif 000058
【図３１】
2011142133.tif 000059
【図３２】
2011142133.tif 000060
【図３３】
2011142133.tif 000061
【図３４】
2011142133.tif 000062
【図３５】
2011142133.tif 000063
【図３６】
2011142133.tif 000064
【図３７】
2011142133.tif 000065
【図３８】
2011142133.tif 000066
【図３９】
2011142133.tif 000067
【図４０】
2011142133.tif 000068
【図４１】
2011142133.tif 000069
【図４２】
2011142133.tif 000070
【図４３】
2011142133.tif 000071
【図４４】
2011142133.tif 000072
【図４５】
2011142133.tif 000073
【図４６】
2011142133.tif 000074
【図４７】
2011142133.tif 000075
【図４８】
2011142133.tif 000076
【図４９】
2011142133.tif 000077
【図５０】
2011142133.tif 000078
【図５１】
2011142133.tif 000079
【図５２】
2011142133.tif 000080
【図５３】
2011142133.tif 000081
【図５４】
2011142133.tif 000082
【図５５】
2011142133.tif 000083
【図５６】
2011142133.tif 000084
【図５７】
2011142133.tif 000085
【図５８】
2011142133.tif 000086
【図５９】
2011142133.tif 000087
【図６０Ａ】
2011142133.tif 000088
【図６０Ｂ】
2011142133.tif 000089
【図６０Ｃ】
2011142133.tif 000090
【図６１】
2011142133.tif 000091
【図６２】
2011142133.tif 000092
【国際調査報告】
2011142133.tif 000093
2011142133.tif 000094
2011142133.tif 000095
2011142133.tif 000096
2011142133.tif 000097
2011142133.tif 000098
2011142133.tif 000099
2011142133.tif 000100