(57)【特許請求の範囲】
【請求項１】
送信多項式にエラーが含まれる受信情報を復号する際に、受信多項式を生成多項式で割った時の剰余と前記エラーとの関係を算定し、
この時の誤訂正確率ｐは、ガロア体〔ＧＦ（２n）〕の底〔ｎ〕、冗長データ長〔ｔ〕およびブロック長〔Ｌ〕の関数として、次式
【数１】
0004129608.tif 000018
で求まり、誤訂正確率ｐ以下にするためのガロア体〔ＧＦ（２n）〕、冗長データ長〔ｔ〕およびブロック長〔Ｌ〕の関係を算定することを特徴とするリードソロモン符号の設定方法。
【請求項２】
総データ量をＮビット、最大誤り訂正能力をｔ0％、最小誤り訂正能力をｔ1％とし、Ｎ＝Ｌ・ｎ、ｔ≧Ｌ・２ｔ0、２n≫１の条件に基づき、次式
【数２】
0004129608.tif 000019
により、ブロック長Ｌおよびガロア体の底ｎを求めることを特徴とする請求項１記載のリードソロモン符号の設定方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ディジタル信号の記録／再生系および伝送系等によってディジタルデータに生じた誤りを訂正するリードソロモン符号の設定方法に関するものである。
【０００２】
【従来の技術】
従来より、ディジタル・オーディオ・テープレコーダ（ＤＡＴ）やディジタル・ビデオ・テープレコーダ（Ｄ−ＶＴＲ）等において取り扱われるディジタルデータに生じた誤りを検出および訂正する誤り訂正符号として、リードソロモン符号が一般的に使用されている。
【０００３】
一般に、リードソロモン符号は、情報処理システムの高信頼度化の一手法として、情報のエラーを訂正する誤り訂正符号として、実用化されており、特に誤り訂正能力が高いものとして重要な符号である。
【０００４】
しかるに、前記リードソロモン符号の誤り訂正位置の検出に際しては、計算により求められる誤り訂正位置αiは、その情報を記録時の方向（順方向）とは逆方向に読み出す場合には、ガロア体αnと指数部ｎとの関係を定義したｌｏｇテーブル（図４参照）を使用して、ベクトル表現からべき表現に変換することにより、情報が不定長であっても容易に検出することが可能であることは、周知である。
【０００５】
図４に示すガロア体表現とベクトル表現との関係は、２の３乗のガロア体について例示したものであり、その計算例は次の通りである。
0004129608.tif 000002
【０００６】
図５は、前記図４に示すベクトル表現と共にリードソロモン符号をエンコードしてブロック符号化したデータの説明図である。
【０００７】
すなわち、図５において、データ全体のブロック長は、リードソロモン符号の場合、最大（２n）−１までであり、ｎ＝３の場合は、７（ブロック数）となる。そして、この場合、誤り訂正能力を１とすると、５サブブロックからなるユーザデータエリア（左側）と、２サブブロックからなる冗長または付加データエリア（右側）とから構成される。
【０００８】
そこで、図５に示す７サブブロックに対して、右側から順次ｘ0＝０，１、ｘ1＝ｘ（以上が付加データ）、ｘ2、ｘ3、ｘ4、ｘ5、ｘ6（以上がユーザデータ）のべき項として定義され、各べき項のユーザデータを、図５に示すベクトル表現（括弧内はガロア体表現）により、
ｘ6 ：０００  （０）
ｘ5 ：０１１  （α3）
ｘ4 ：０００  （０）
ｘ3 ：０００  （０）
ｘ2 ：０１０  （α）
と設定すると、ユーザデータエリアの情報多項式Ｉ（ｘ）は、図４に示す関係に基づいて、べき項とガロア体表現とから次式で示される。
Ｉ（ｘ）＝α3ｘ5＋αｘ2
【０００９】
ここで、この情報多項式Ｉ（ｘ）が、αとα2の根を持つ（割り切れる）冗長データが付加される。すなわち、この付加されるデータエリアはＲＳ多項式Ｒ（ｘ）と定義し、このＲＳ多項式Ｒ（ｘ）は前記情報多項式Ｉ（ｘ）を次式で示される生成多項式Ｇ（ｘ）で割算したときの剰余とされる。
0004129608.tif 000003
【００１０】
従って、前記ＲＳ多項式Ｒ（ｘ）の結果から、付加データエリアのｘ項は、図６に示すように、α6＝「１０１」とベクトル表示される。
【００１１】
そこで、図６に示す情報多項式Ｉ（ｘ）とＲＳ多項式Ｒ（ｘ）とからなる全体ブロックを送信多項式Ｊ（ｘ）と定義し、次式で示される。
0004129608.tif 000004
【００１２】
次に、受信多項式Ｋ（ｘ）について検討する。この場合、受信多項式Ｋ（ｘ）においては、一般にエラーＥ（ｘ）が含まれている。
【００１３】
そこで、受信多項式Ｋ（ｘ）を生成多項式Ｇ（ｘ）で割算したときの剰余を考えると、次式が得られる。
Ｋ（ｘ）ｍｏｄＧ（ｘ）＝〔Ｊ（ｘ）＋Ｅ（ｘ）〕ｍｏｄＧ（ｘ）
＝｛〔Ｊ（ｘ）ｍｏｄＧ（ｘ）〕
＋〔Ｅ（ｘ）ｍｏｄＧ（ｘ）〕｝ｍｏｄＧ（ｘ）
＝Ｅ（ｘ）ｍｏｄＧ（ｘ）
【００１４】
この場合、(1)どの位置でエラーを生じているか、(2)どの位の量のエラーを生じているか、の２つの情報を見出さなければ、誤り訂正を行うことができない。
【００１５】
従って、例えば図７の（ａ）に示すように、受信多項式Ｋ（ｘ）のｘ3のべき項にＥ（ｘ）＝ｘ3のエラーを生じた場合、受信多項式Ｋ（ｘ）は次式で示される。
Ｋ（ｘ）＝α3ｘ5＋ｘ3＋αｘ2＋α6ｘ
【００１６】
この場合、前記Ｅ（ｘ）ｍｏｄＧ（ｘ）を検討すると、次式が得られる。
0004129608.tif 000005
【００１７】
このことは、受信多項式Ｋ（ｘ）を生成多項式Ｇ（ｘ）で割算したときの剰余がｘ＋１であれば、受信多項式Ｋ（ｘ）にｘ3のエラーＥ（ｘ）が含まれているといえる。
【００１８】
また、図７の（ｂ）に示すように、受信多項式Ｋ（ｘ）のｘ3のべき項にＥ（ｘ）＝αｘ3のエラーを生じた場合、受信多項式Ｋ（ｘ）は次式で示される。
Ｋ（ｘ）＝α3ｘ5＋αｘ3＋αｘ2＋α6ｘ
【００１９】
この場合、前記Ｅ（ｘ）ｍｏｄＧ（ｘ）を検討すると、次式が得られる。
0004129608.tif 000006
【００２０】
このように、剰余がαｘ＋αであれば、受信多項式Ｋ（ｘ）にαｘ3のエラーＥ（ｘ）が含まれているといえる。
【００２１】
さらに、図７の（ｃ）に示すように、受信多項式Ｋ（ｘ）のｘ2のべき項にＥ（ｘ）＝ｘ2のエラーを生じた場合、受信多項式Ｋ（ｘ）は次式で示される。
Ｋ（ｘ）＝α3ｘ5＋ｘ2＋α6ｘ
【００２２】
この場合、前記Ｅ（ｘ）ｍｏｄＧ（ｘ）を検討すると、次式が得られる。
0004129608.tif 000007
【００２３】
このように、剰余がα4ｘ＋α3であれば、受信多項式Ｋ（ｘ）にｘ2のエラーＥ（ｘ）が含まれているといえる。
【００２４】
【発明が解決しようとする課題】
そこで、本発明者は鋭意研究並びに検討を重ねた結果、エラーと剰余の関係を、前述した受信多項式Ｋ（ｘ）と生成多項式Ｇ（ｘ）の剰余で一義的に定まる全てのエラー（１つのエラーからなるノーマルエラー）は、訂正できる一覧表を作成することができる。この場合、エラーが２つからなる誤り訂正不能部分は、計算上において分別することがてきることを突き止めた。
【００２５】
また、前述した従来のリードソロモン符号の復号法は、誤りを訂正することに主眼を置き、訂正能力一杯まで訂正することが多い。そこで、誤訂正が発生するという問題がある。従って、ある数の誤りまでは訂正し、それ以上の誤りは検出のみとする符号を構成し、その効率的な復号法を実現することが望まれる。
【００２６】
通常の復号法では誤り訂正のみを行う符号を構成し、復号において誤り位置多項式の係数を算出して、誤りの数を判定している。これは、誤りがある数以上であると判定すると、復号を中断するものであり、この復号法は効率が良くない難点がある。
【００２７】
また、多重エラーの検査の前に、まず単一エラーを検査して、それを訂正する方法は、復号アルゴリズムが複雑になり、最大復号ステップ数が多くなり、ソフトウェア量、ハードウェア量とも増大するという難点がある。特に、２重誤りを訂正し、それ以上の誤りを検出することができる符号の効率的な復号法が開発されていない。
【００２８】
そこで、本発明の目的は、送信多項式にエラーが含まれる受信情報を復号する際に、受信多項式を生成多項式で割った時の剰余と前記エラーとの関係を求め、この時の誤訂正確率ｐを算定することにより、誤訂正確率ｐが最も少なくなるようなリードソロモン符号の設定を行うことができるリードソロモン符号の設定方法を提供することにある。
【００２９】
【課題を解決するための手段】
前記目的を達成するために、本発明に係るリードソロモン符号の設定方法は、送信多項式にエラーが含まれる受信情報を復号する際に、受信多項式を生成多項式で割った時の剰余と前記エラーとの関係を算定し、
この時の誤訂正確率ｐは、ガロア体〔ＧＦ（２n）〕の底〔ｎ〕、冗長データ長〔ｔ〕およびブロック長〔Ｌ〕の関数として、次式
【００３０】
【数３】
0004129608.tif 000008
で求まり、誤訂正確率ｐ以下にするためのガロア体〔ＧＦ（２n）〕、冗長データ長〔ｔ〕およびブロック長〔Ｌ〕の関係を算定することを特徴とする。
【００３１】
前記のリードソロモン符号の設定方法において、総データ量をＮビット、最大誤り訂正能力をｔ0％、最小誤り訂正能力をｔ1％とし、Ｎ＝Ｌ・ｎ、ｔ≧Ｌ・２ｔ0、２n≫１の条件に基づき、次式
【００３２】
【数４】
0004129608.tif 000009
により、ブロック長Ｌおよびガロア体の底ｎを求めることができる。
【００３３】
【発明の実施の形態】
次に、本発明に係るリードソロモン符号の設定方法の実施例につき、添付図面を参照しながら以下詳細に説明する。
【００３４】
図１ないし図３は、本発明におけるリードソロモン符号の設定方法の一実施例を示す説明図であって、前述した図４ないし図７において説明したリードソロモン符号のエンコード方法に基づいて、全てのノーマルエラー（エラーが１つ）の場合に、エラーを含む受信多項式を生成多項式Ｇ（ｘ）で割算した時の剰余と前記エラーとの関係を示すものである。
【００３５】
１．エラーＥ（ｘ）についての一覧表の作成
前述した図７の（ａ）〜（ｃ）に示すように、それぞれ受信多項式Ｋ（ｘ）のべき項にエラーＥ（ｘ）を生じた場合の剰余、すなわちＥ（ｘ）ｍｏｄＧ（ｘ）は次の通りである。
0004129608.tif 000010
従って、前記Ｅ（ｘ）ｍｏｄＧ（ｘ）の関係式において、ｘの項を縦方向に規定し、定数項を横方向に規定して、それぞれ１〜α6，０について（ｘの項）＋（定数項）からなる剰余に対し、それぞれエラーＥ（ｘ）を算定すれば、図１に示すような一覧表を得ることができる。
【００３６】
すなわち、図１において、剰余が（ｘの項）＋（定数項）＝α3ｘ＋α2の場合、エラーＥ（ｘ）はα6ｘ2となる。従って、図１によれば、全てのノーマルエラーは、受信多項式Ｋ（ｘ）と生成多項式Ｇ（ｘ）の剰余により、一義的に定まり、そして訂正できることがわかる。なお、図１において、空欄となる部分は、誤り訂正不能部分、すなわち誤りが２つ以上存在しているので訂正できない部分として、計算上分別することができる部分である。
【００３７】
２．リードソロモン符号の誤訂正について
一般に、誤訂正が生じるメカニズムは、エラー多項式Ｅ（ｘ）が生成多項式Ｇ（ｘ）のＦ（ｘ）倍の場合であるか、それプラス１つのエラーを含む場合である。これを数式で示せば次式の通りである。
Ｅ（ｘ）＝Ｇ（ｘ）・Ｆ（ｘ）＋ｉαm・ｘn
但し、ｉ＝｛０，１｝；ｍ，ｎ＝｛０…６｝
一例として、エラー多項式Ｅ（ｘ）を次式で示す。
Ｅ（ｘ）＝ｘ2＋α4ｘ
【００３８】
そこで、受信データが図２の（ａ）に示すように、２つのエラーを含む場合、受信多項式Ｋ（ｘ）は次式で示される。
Ｋ（ｘ）＝α3ｘ5＋α3ｘ2＋α3ｘ
【００３９】
次いで、エラーＥ（ｘ）が含まれている前記受信多項式Ｋ（ｘ）を生成多項式Ｇ（ｘ）で割算した場合の剰余、すなわちＥ（ｘ）ｍｏｄＧ（ｘ）を求めると、次式が得られる。
0004129608.tif 000011
この結果、誤り訂正された前記受信データは、図２の（ｂ）に示すように、３つのエラーを含むようになる。
【００４０】
このような結果からわかるように、訂正能力以上の誤りがある場合、正しいデータまでも壊してしまう惧れがある。
【００４１】
３．誤訂正の生じる確率について
そこで、このような誤訂正の生じる確率を求める。この場合、エラーは訂正能力以上のランダム的なエラーが生じるものとする。
【００４２】
取り得る全ての誤り訂正、すなわちＥ（ｘ）ｍｏｄＧ（ｘ）は、図１の関係から、８2＝６４通りであり、そのうち結果を出すものは７2＋１＝５０通りであり、従って誤訂正確率は５０／６４＝０．７８１となる。
【００４３】
次に、Ｇ（ｘ）が４次の生成多項式であり、２つのエラーまで訂正できるものとする（図３参照）。この時、取り得る全ての誤り訂正、すなわちＥ（ｘ）ｍｏｄＧ（ｘ）は、８＊８＊８＊８＝４０９６通りであり、そのうち２つのエラーの結果を出す数は（２3−１）＊７＊（２3−１）＊６／２！＝１０２２通り、１つのエラーの結果を出す数は（２3−１）＊９＝４９通り、そしてエラーなしは１通りであり、従って誤訂正確率は（１０２２＋４９＋１）／４０９６＝０．２６１７となる。
【００４４】
４．誤訂正確率の一般化
次いで、誤訂正確率を一般化するために、次の通り定義する。
(a) ガロア体：ＧＦ（２n）
(b) 冗長データ長：ｔ
(c) ブロック長：Ｌ
【００４５】
そこで、取り得る全ての誤り訂正Ｅ（ｘ）ｍｏｄＧ（ｘ）は、２nt通りであり、そのうちｔ／２個のエラーを修正をするものは、（２n−１）t/2Ｃt/2 L通り、ｔ／２ -１個のエラーを修正をするものは、（２n−１）t/2 -1Ｃt/2 -1 L通りであり、以下同様になる。従って、誤訂正確率ｐは、次式で示される。
【００４６】
【数５】
0004129608.tif 000012
そこで、前記式において、第１項のみで近似すると、次式が得られる。
【００４７】
【数６】
0004129608.tif 000013
【００４８】
５．誤訂正確率を考慮したリードソロモン符号の決定
与えるデータは次の通りである。
(1) 誤訂正確率  ｐ以下
(2) 総データ長  Ｎビット
(3) 最大誤り訂正能力  ｔ0（％）
(4) 最小誤り訂正能力  ｔ1（％）
求めるデータは次の通りである。
(1) ガロア体の底  ｎ
(2) ブロック長  Ｌ
前述した誤訂正確率条件および最大誤り訂正条件の近似式から、
【００４９】
【数７】
0004129608.tif 000014
となる。但し、以下の式に従うものとする。
【００５０】
【数８】
0004129608.tif 000015
【００５１】
また、最小誤り訂正条件より、次式が得られる。
【００５２】
【数９】
0004129608.tif 000016
【００５３】
従って、前記式（Ｂ−１）と前記式（Ｂ−６）を満たすブロック長Ｌの値を求め、前記式（Ｂ−２）によってガロア体の底ｎの値を求めることにより、適正な誤訂正確率ｐを考慮したリードソロモン符号を決定することができる。
【００５４】
６．設計例１
総データ長Ｎ：    ６４ビット
誤訂正確率ｐ：      ０．１％以下
最大誤り訂正ｔ0：２５％
最小誤り訂正ｔ1：  ３％
上記の設計条件において、前記式（Ｂ−１）を満たすブロック長Ｌの値は、Ｌ＝４，５，６，７，８である。また、前記式（Ｂ−５）からブロック長Ｌの値は８以上となるので、ブロック長Ｌは８に設定される。
【００５５】
従って、ブロック長Ｌ＝８の場合、ガロア体の底ｎ＝８となり、誤訂正確率ｐは０．０４２４％、最小誤り訂正ｔ1は３．１２５％、ユーザデータＮは３２ビットである。
【００５６】
以上、本発明の好適な実施例について説明したが、本発明は前記実施例に限定されることなく、本発明の精神を逸脱しない範囲内において、多くの設計変更を行うことができる。
【００５７】
【発明の効果】
前述した実施例から明らかなように、本発明に係るリードソロモン符号の設定方法は、送信多項式にエラーが含まれる受信情報を復号する際に、受信多項式を生成多項式で割った時の剰余と前記エラーとの関係を算定し、
この時の誤訂正確率ｐは、ガロア体〔ＧＦ（２n）〕の底〔ｎ〕、冗長データ長〔ｔ〕およびブロック長〔Ｌ〕の関数として、次式
【００５８】
【数１０】
0004129608.tif 000017
で求まり、誤訂正確率ｐ以下にするためのガロア体〔ＧＦ（２n）〕、冗長データ長〔ｔ〕およびブロック長〔Ｌ〕の関係を算定することにより、リードソロモン符号の設定すなわちディジタルデータの誤り訂正を、簡便かつ低コストに達成することができる。
【図面の簡単な説明】
【図１】本発明に係るリードソロモン符号の設定方法を実施するためのエラーを含む受信多項式を生成多項式で割算した場合の剰余と前記エラーとの関係を示す説明図である。
【図２】（ａ）は本発明に係るリードソロモン符号の設定方法による受信状態における誤りを含むベクトル表示を行ったデータの説明図、（ｂ）は（ａ）に示すデータの誤り訂正（訂正能力１の場合）を行う状態を示すデータの説明図である。
【図３】本発明に係るリードソロモン符号の設定方法による別のデータの誤り訂正（訂正能力２の場合）を行う状態を示すデータの説明図である。
【図４】リードソロモン符号のガロア体表現とベクトル表現との関係を示す説明図である。
【図５】リードソロモン符号をブロック符号化してそれぞれベクトル表示を行ったデータの説明図である。
【図６】ブロック符号化したリードソロモン符号の送信状態におけるベクトル表示を行ったデータの説明図である。
【図７】（ａ）〜（ｃ）はブロック符号化したリードソロモン符号の受信状態における種々の誤りを含むベクトル表示を行ったデータのそれぞれ説明図である。
【図１】
0004129608.tif 000020
【図２】
0004129608.tif 000021
【図３】
0004129608.tif 000022
【図４】
0004129608.tif 000023
【図５】
0004129608.tif 000024
【図６】
0004129608.tif 000025
【図７】
0004129608.tif 000026