(57)【要約】リードソロモン・エンコーダ方法に、データ・ブロックにＮ個の０を追加することと、その係数がデータ・ブロックのデータおよび０である多項式Ｐ（ｘ）の連続するホーマー・リダクションを実行することが含まれる。剰余β（ｉ）に、対応する多項式係数Ｄ（ｉ）（ｘ）をかけ、結果の積のすべての合計をとる。この積の合計をパリティ記号としてデータ・ブロックに追加して、コードワードを形成する。リード・ソロモン・デコーダ方法に、コードワードとシンドローム・ベクトルとの内積としてシンドロームを計算することが含まれる。シンドロームが０と等しい場合に、単にパリティ記号を除去することによってコードワードを復号する。シンドロームが０と等しくない場合に、誤りの位置のエラー・ロケータ多項式を形成し、解くことと、それらの位置でのエラー・マグニチュードのエラー・マグニチュード多項式を形成し、解くことと、コードワード内の誤りを訂正することによって、コードワードを訂正する。コードワードは、パリティ記号を除去することによって復号される。これらの方法は、ソフトウェアで実行される。【特許請求の範囲】
【請求項１】
データ・ブロックにＮ個の０を追加することと、
その係数が前記データ・ブロックのデータおよび前記０である多項式
【数１】
2007518353.tif 000024
の連続するホーナー・リダクションを実行することであって、前記リダクションは、複数の剰余β（ｉ）（ｉ＝０からＮ−１）を作る、実行することと、
前記剰余β（ｉ）に、メモリに保管された対応する多項式係数Ｄ（ｉ）（ｘ）をかけ、結果の積のすべての合計
【数２】
2007518353.tif 000025
をとることであって、前記積の前記合計は、多項式の前記剰余係数を表し、前記多項式の前記剰余係数は、生成多項式
【数３】
2007518353.tif 000026
による前記多項式Ｐ（ｘ）の除算である、かけ、合計をとることと、
コードワードを形成するために、前記積の前記合計を、パリティ記号として前記データ・ブロックに追加することと
を含む、リードソロモン・エンコーダ方法。
【請求項２】
前記方法が、ソフトウェアで実行される、請求項１に記載の方法。
【請求項３】
請求項１に記載の方法を実行するエンコーダを含む通信デバイス。
【請求項４】
データ記号およびパリティ記号を含むコードワードを復号するリードソロモン・デコーダ方法であって、
前記コードワードとメモリに保管されたシンドローム・ベクトルとの内積としてシンドロームを計算することであって、前記シンドローム・ベクトルは、多項式
【数４】
2007518353.tif 000027
の係数であり、シンドローム・ベクトルの個数ｉは、前記コードワード内のパリティ記号の個数と等しい、計算することと、
前記シンドロームが０と等しい場合に、単に前記パリティ記号を除去することによって前記コードワードを復号することと、
前記シンドロームが０と等しくない場合に、誤りの位置のエラー・ロケータ多項式を形成し、解くことと、前記位置でのエラー・マグニチュードのエラー・マグニチュード多項式を形成し、解くことと、前記コードワード内の前記誤りを訂正することとによって、コードワードを訂正し、前記パリティ記号を除去することによって復号することと
を含む、リードソロモン・デコーダ方法。
【請求項５】
前記方法が、ソフトウェアで実行される、請求項４に記載の方法。
【請求項６】
前記シンドローム・ベクトルのそれぞれの大きさが、前記コードワードの大きさと等しい、請求項４に記載の方法。
【請求項７】
請求項４に記載の方法を実行するデコーダを含む通信デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、全般的には多項式によって生成される誤り訂正符号化および復号に関し、具体的には、リードソロモン符号化、誤り検出、および誤り訂正の技法に関する。
【背景技術】
【０００２】
【非特許文献１】Ｒ．Ｅ．Ｂｌａｈｕｔ、「Ｔｈｅｏｒｙ  ａｎｄ  ｐｒａｃｔｉｃｅ  ｏｆ  ｅｒｒｏｒ  ｃｏｎｔｒｏｌ  ｃｏｄｅｓ」、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ、１９８４年
【非特許文献２】Ｓ．Ｂ．Ｗｉｃｋｅｒ、「Ｅｒｒｏｒ  ｃｏｎｔｒｏｌ  ｓｙｓｔｅｍｓ  ｆｏｒ  ｄｉｇｉｔａｌ  ｃｏｍｍｕｎｉｃａｔｉｏｎ  ａｎｄ  ｓｔｏｒａｇｅ」、Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，Ｉｎｃ．、１９９５年
【発明の開示】
【課題を解決するための手段】
【０００３】
リードソロモン・コーディング方式およびリードソロモン復号方式は、衛星、モデム、オーディオ・コンパクト・ディスク、および無線電話機など、多数の通信システムで使用されている。各通信システムは、リードソロモン・コードを定義するパラメータの値の異なるセットを有する。リードソロモン・エンコーダ／デコーダは、ガロア域（ＧＦ）算術を使用して、通信のブロックをより大きいブロックに写像する。各ブロックは、入力ブロックに基づく過剰に簡略化された多項式に対応する。
【０００４】
ハードウェアで実装される時に、リードソロモン・エンコーダ／デコーダは、かなりの量の論理ゲートおよび他のハードウェアを必要とする。例えば並列処理およびプロセスの算術表現を減らすことによるなど、多くの努力が、ハードウェアの量を減らすことを対象としてきた。
【０００５】
さまざまな通信システムに固有のリードソロモン・デコーダは、計算の複雑さおよび低電力要件の故に専用ハードウェア・ブロックで実装されてきた。例えば、Ｒ．Ｅ．Ｂｌａｈｕｔ、「Ｔｈｅｏｒｙ  ａｎｄ  ｐｒａｃｔｉｃｅ  ｏｆ  ｅｒｒｏｒ  ｃｏｎｔｒｏｌ  ｃｏｄｅｓ」、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ、１９８４年、およびＳ．Ｂ．Ｗｉｃｋｅｒ、「Ｅｒｒｏｒ  ｃｏｎｔｒｏｌ  ｓｙｓｔｅｍｓ  ｆｏｒ  ｄｉｇｉｔａｌ  ｃｏｍｍｕｎｉｃａｔｉｏｎ  ａｎｄ  ｓｔｏｒａｇｅ」、Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，Ｉｎｃ．、１９９５年を参照されたい。本開示の符号化方法および復号方法全体が、ガロア域多項式除算を使用せずにソフトウェアで実行される。この復号方法は、エラー・ロケータ（ｅｒｒｏｒ  ｌｏｃａｔｏｒ）およびエラー・マグニチュード（ｅｒｒｏｒ  ｍａｇｎｉｔｕｄｅ）の両方に必要なシステム方程式を直接に解くことによって、ソフトウェアでも実行される。
【０００６】
本開示のリードソロモン・エンコーダ方法に、データ・ブロックにＮ個の０を追加することと、その係数がデータ・ブロックのデータおよび０である多項式
【数１】
2007518353.tif 000002
の連続するホーナー・リダクション（Ｈｏｒｎｅｒ  ｒｅｄｕｃｔｉｏｎ）を実行することが含まれ、このリダクションは、複数の剰余β（ｉ）（ｉ＝０からＮ−１）を作る。剰余β（ｉ）に、メモリに保管された対応する多項式係数Ｄ（ｉ）（ｘ）をかけ、結果の積のすべての合計
【数２】
2007518353.tif 000003
をとる。この積の合計は、多項式の剰余係数を表し、これは、生成多項式
【数３】
2007518353.tif 000004
による多項式Ｐ（ｘ）の除算である。この積の合計を、パリティ記号としてデータ・ブロックに追加して、コードワードを形成する。この方法は、ソフトウェアで実行される。
【０００７】
データ記号およびパリティ記号を含むコードワードを復号する本開示のリード・ソロモン・デコーダ方法に、コードワードとメモリに保管されたシンドローム（ｓｙｎｄｒｏｍｅ）ベクトルとの内積としてシンドロームを計算することが含まれ、このシンドローム・ベクトルは、多項式
【数４】
2007518353.tif 000005
の係数であり、シンドローム・ベクトルの個数ｉは、コードワード内のパリティ記号の個数と等しい。シンドロームが０と等しい場合に、単にパリティ記号を除去することによってコードワードを復号する。シンドロームが０と等しくない場合に、誤りの位置のエラー・ロケータ多項式を形成し、解くことと、それらの位置でのエラー・マグニチュードのエラー・マグニチュード多項式を形成し、解くことと、コードワード内の誤りを訂正することによって、コードワードを訂正する。コードワードは、パリティ記号を除去することによって復号される。この方法は、ソフトウェアで実行される。
【０００８】
本開示の上記および他の態様は、添付図面と共に検討される時の本開示の次の詳細な説明から明白になる。
【発明を実施するための最良の形態】
【０００９】
エンコーダ
エンコーダ方式は、一般に、データ記号からなるデータのブロックをとり、パリティ記号を追加して、コードワードと称するものを作る。リードソロモン符号化システムでは、パリティ記号が、２つの多項式の除算の剰余である。
【００１０】
第１の多項式
【数５】
2007518353.tif 000006
は、ガロア域ＧＦ（２ｎ）内の長さ２ｎのデータ・ブロックである。第２の多項式
【数６】
2007518353.tif 000007
は、ＧＦ（２ｎ）内の生成多項式である。αｊおよびａｉは、ＧＦ（２ｎ）内のフィールド要素（ｆｉｅｌｄ  ｅｌｅｍｅｎｔ）である。
【００１１】
ＧＦ乗算およびＧＦ加算だけを使用することによってＧＦ（２ｎ）で多項式除算の剰余を計算するために、式を簡略化し、諸部分を事前に計算しまたは事前に決定し、メモリに保管する。これは、ソフトウェア実装をもたらし、適応可能または再構成可能である。
【００１２】
Ｑ（ｉ）が、生成多項式
【数７】
2007518353.tif 000008
によるデータＰ（ｘ）の除算の商であると仮定すると、
ｉ＝０について、
【数８】
2007518353.tif 000009
ｉ＝１について、
【数９】
2007518353.tif 000010
ｉ＝２について、
【数１０】
2007518353.tif 000011
である。一般に、ｉ＝Ｎ−１について、
【数１１】
2007518353.tif 000012
である。単純な計算の後の上の式の剰余を、
【数１２】
2007518353.tif 000013
と書くことができる。係数β（ｉ）は、表１に示されているように、Ｐ（ｘ）の連続するホーナー・リダクションの剰余である。
【００１３】
【表１】
2007518353.tif 000014
【００１４】
Ｎ個の多項式
【数１３】
2007518353.tif 000015
が、事前に決定され、メモリに保管される。剰余係数β（ｉ）に、メモリからの対応する多項式係数Ｄ（ｉ）（ｘ）をかける。すべての結果の積の合計
【数１４】
2007518353.tif 000016
は、多項式の剰余係数を表し、これは、生成多項式ｇ（ｘ）によるデータ多項式Ｐ（ｘ）の除算である。
【００１５】
符号化方法を、図１に、データにＮ個の０を追加することとして示す。次に、データ・ブロックのデータおよび０の係数であるＰ（ｘ）の多項式のホーナー・リダクションを実行する。次に、剰余多項式係数を計算するために、リダクションの剰余に、メモリに保管された対応する多項式係数Ｄ（ｘ）をかける。コードワードを形成するために、その剰余多項式係数をオリジナル・データに追加する。
【００１６】
具体的な例は、次の通りである。
ＲＳ（２５６，２４０）は、２４０個のデータ記号および１６個のパリティ記号を含む長さ２５６のコードワードである。
【００１７】
生成多項式ｇ（ｘ）の所与の係数は、次の通りである。
１，５９，１３，１０４，１８９，６８，２０９，３０，８，１６３，６５，４１，２２９，９８，５０，３６，５９
【００１８】
生成多項式ｇ（ｘ）の所与のルート｛αｉ｝は、次の通りである。
１，２，４，８，１６，３２，６４，１２８，２９，５８，１１６，２３２，２０５，１３５，１９，３８
【００１９】
結果の事前計算され保管されるＤ（ｉ）（ｘ）多項式係数は、次の通りである。
１
１      １
１      ３      ２
１      ７    １４      ８
１    １５    ５４  １２０    ６４
１    ３１  １９８    ６３  １４７  １１６
１    ６３      １  ２１８    ３２  ２２７    ３８
１  １２７  １２２  １５４  １６４    １１    ６８  １１７
１  ２５５    １１    ８１    ５４  ２３９  １７３  ２００    ２４
１  ２２６  ２０７  １５８  ２４５  ２３５  １６４  ２３２  １９７    ３７
１  ２１６  １９４  １５９  １１１  １９９    ９４    ９５  １１３  １５７  １９３
１  １７２  １３０  １６３    ５０  １２３  ２１９  １６２  ２４８  １４４  １１６  １６０
１    ６８  １１９    ６７  １１８  ２２０    ３１      ７    ８４    ９２  １２７  ２１３    ９７
１  １３７    ７３  ２２７    １７  １７７    １７    ５２    １３    ４６    ４３    ８３  １３２  １２０
１    １４    ５４  １１４    ７０  １７４  １５１    ４３  １５８  １９５  １２７  １６６  ２１０  ２３４  １６３
１    ２９  １９６  １１１  １６３  １１２    ７４    １０  １０５  １０５  １３９  １３２  １５１    ３２  １３４    ２６
【００２０】
１６個の追加された０を有するデータＰ（ｘ）は、次の通りである。
１３１，２４４，２４１，２１，７０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０
【００２１】
Ｐ（ｘ）の連続するホーナー・リダクションからの剰余係数｛β（ｉ）｝は、次の通りである。
２１３，６０，１４５，１３２，１７，４４，２１４，９４，５，２６，１３，７８，１８５，１６５，２１５，９７
【００２２】
Ｄ（ｉ）（ｘ）と｛β（ｉ）｝のガロア乗算および合計の後に、パリティ記号は次のようになる。
９７，９４，１７３，５１，１７２，２６，６５，４２，１４９，２２，１４９，２２９，３７，５５，１１７，６１
【００２３】
このパリティ記号が、データ・ブロックに追加され、コードワードは、次のようになる。
１３１，２４４，２４１，２１，７０，９７，９４，１７３，５１，１７２，２６，６５，４２，１４９，２２，１４９，２２９，３７，５５，１１７，６１
【００２４】
デコーダ
受け取られたコードワードは、
【数１５】
2007518353.tif 000017
と表される。
【００２５】
受け取ったコードワードのデータ部分を復号し、パリティ・ビットを受け取ったパリティ・ビットと比較することによってコードワードの妥当性を検査するのではなく、復号は、図２に示されているように、シンドロームを計算することによって直接に開始される。
【００２６】
シンドローム計算は、式
Ｓｉ＝ＣＴΣｉ    ｉ＝（１，２，…Ｎ−１）
として記述され、ここで、Ｃは、その要素がコードワード多項式Ｃ（ｘ）の係数であるベクトルであり、Σｉは、その要素が次の多項式
【数１６】
2007518353.tif 000018
の係数であるシンドローム・ベクトルであり、ここで、シンドローム・ベクトルの個数Ｎは、コードワード内のパリティ記号の個数と等しく、シンドローム・ベクトルの大きさは、それぞれ、コードワードの大きさと等しい。シンドローム・ベクトルも、メモリに保管される。
【００２７】
シンドロームが０と等しい場合に、コードワードは、単にパリティ記号を除去することによって復号され、復号処理が停止する。シンドロームが０と等しくない場合には、コードワードは、誤りの位置のエラー・ロケータ多項式を形成し、解くことと、それらの位置でのエラー・マグニチュードのエラー・マグニチュード多項式を形成し、解くことと、コードワード内の誤りを訂正することによって、訂正される。コードワードは、受け取った（壊れている）コードワードから誤りベクトルを引く（ＧＦでの加算と同一）ことによって、誤りを訂正される。コードワードは、パリティ記号を除去することによって復号される。これを図２に示す。この復号アルゴリズムも、Ｐｅｔｅｒｓｏｎ−Ｇｏｒｅｎｓｔｅｉｎ−Ｚｉｅｒｌｅｒ法を使用してソフトウェアで実行される。
【００２８】
シンドロームが０と異なる場合の処理の例に、シンドローム行列式
【数１７】
2007518353.tif 000019
を形成することが含まれる。前の式では、Λｉが、エラー・ロケータ多項式の係数である。
【００２９】
ＧＦでは、拡張されたシステム行列を、ガウス・リダクション（Ｇａｕｓｓ  ｒｅｄｕｃｔｉｏｎ）を使用することによって上三角形に簡単に変換でき、したがって、この形で行列反転を避けることができる。
【数１８】
2007518353.tif 000020
このシステムの階数は、ユークリッド・トレース（Ｅｕｃｌｉｄｉａｎ  ｔｒａｃｅ）になる。次に、このシステム方程式を簡単に解くことができ、Λ０＝ΞＮ−１、Λ１＝ΞＮ−１Λ０＋ΞＮ−２、などである。
【００３０】
エラー・ロケータ多項式
【数１９】
2007518353.tif 000021
をチェン探索（Ｃｈｉｅｎ  ｓｅａｒｃｈ）を使用して解く。エラー・ロケータ多項式の解の逆数は、誤りの位置を表し、ここで、ｍは、Ｎ／２以下である。
【００３１】
ｍ個の誤りのエラー・マグニチュードを、エラー・マグニチュード・システム方程式を使用して計算する
【数２０】
2007518353.tif 000022
エラー・マグニチュード多項式を、エラー・ロケータ多項式に似た形で解いて、誤りの大きさ
【数２１】
2007518353.tif 000023
を得る。
【００３２】
具体的な例は、次の通りである。
計算されたシンドロームは、次の通りである。
１，３３，１３１，２４，１３６，１５３，２１６，４９，２３４，８１，２３３，８７，７０，１６６，１０６，５５
【００３３】
形成される拡張された上三角形エラー・ロケータ・システム行列は、次の通りである。
１  ３３  １３１  ２４  １３６  １５３  ２１６    ４９  ２３４
０    １    ３０  ４４  ２０４    ９５  ２２２  １５１    ４４
０    ０      １  ８０    ４４  １０５  １８１  １４２    １８
０    ０      ０    １  １２７    ７１    ５６  １１８    １７
０    ０      ０    ０      １  ２２６    ７７  ２１３  １３９
０    ０      ０    ０      ０      １  ２１４  １７６    ２８
０    ０      ０    ０      ０      ０      １    ７６    ２１
０    ０      ０    ０      ０      ０      ０      １  ２４６
【００３４】
エラー・ロケータ多項式の解は、次の通りである。
２４６，６６，２３２，１２８，１８５，２０２，１７，２５
【００３５】
誤りは、次の通りである。
１，２，３，４，５，６，２０，２１
【００３６】
本開示を、詳細に説明し、図示したが、これが例示だけのために行われ、制限と解釈されてはならないことを明瞭に理解されたい。本開示の範囲は、添付請求項の用語だけによって制限される。
【図面の簡単な説明】
【００３７】
【図１】本開示の原理によるリードソロモン・エンコーダの流れ図である。
【図２】本開示の原理によるリードソロモン・デコーダの流れ図である。
【図１】
2007518353.tif 000028
【図２】
2007518353.tif 000029
【国際調査報告】
2007518353.tif 000030