| Japanese | English |

Welcome to ML-LABO


例：Reed-Solomon Code Encoder/Decoder の C++ コード

弊社では、開発のために C++離散数学ライブラリを完備しております。 社内で使われている C++離散数学ライブラリには、ガロア体のクラスライブラリ Galois も含まれています。 このライブラリを使うと、リード・ソロモン符号の符号化と復号化は、次のように簡単に記述できます。

/////////////////////////////////////////////////////////////////////
// Reed-Solomon Code Encoder/Decoder のデモ
//
// 注：このソフトウェアは、製品ＩＰコアの C++ モデルではありません
/////////////////////////////////////////////////////////////////////
      

#include "Galois.h"

void main()
{
  // ガロア体GF(2)と拡大体（生成多項式 100011101）
  const GaloisField GF2(2);
  const GaloisField GF256( GF2, "(1,0,0,0,1,1,1,0,1)" );

  // 符号シンボル長、情報シンボル長、チェックシンボル数
  const int CODE_BLOCK_LEN = 240;
  const int INFO_BLOCK_LEN = 224;
  const int GENERATOR_DEGREE = 16;

  // 単位元
  const GaloisFieldElement alpha(GF256, "(0,0,0,0,0,0,1,0)");

  // RS符号の生成多項式
  GaloisFieldPolynomial g(GF256); g = 1;
  GaloisFieldPolynomial x(GF256); x = 1; x <<= 1;
  for ( int j = 0; j < GENERATOR_DEGREE; j++ ) g *= (x + Pow(alpha,j));

  GaloisFieldPolynomial i(GF256), c(GF256), e(GF256), r(GF256), s(GF256);
  GaloisFieldPolynomial Lambda (GF256), dLambda(GF256), Omega(GF256);
  GaloisFieldElement ev(GF256);
  GaloisFieldPolynomial sx(GF256), tx(GF256);
  GaloisFieldPolynomial Q_temp(GF256), A22(GF256), A12(GF256), A_temp(GF256);
  GaloisFieldElement Q(GF256), y (GF256), yi(GF256), p(GF256), q(GF256);

  for ( int t = 0; t <= (GENERATOR_DEGREE/2); t++ ) {
     for ( int iter = 0; iter < ((t == 0) ? 1: 10); iter++ ) {

      /////////////////////////////////////////////////////////////////////
      // 情報シンボル系列をランダムに生成
      /////////////////////////////////////////////////////////////////////

      i.Rand(INFO_BLOCK_LEN-1);

      /////////////////////////////////////////////////////////////////////
      // ＲＳ符号化
      /////////////////////////////////////////////////////////////////////

      s = 0;
      for ( int j = INFO_BLOCK_LEN-1; j >= 0; j-- ) {
        s <<= 1;
        s -= ( i.GetCoefficient(j) - s.GetCoefficient(GENERATOR_DEGREE) ) * g;
        s.SetCoefficient(0,GENERATOR_DEGREE);
      };
      c = (i<<GENERATOR_DEGREE) + s;

      /////////////////////////////////////////////////////////////////////
      // 符号シンボル系列にエラーを加える
      /////////////////////////////////////////////////////////////////////

      int el; //
      e = 0;
      for ( int k = 0; k < t; k++ ) {
        ev.Rand(); //cout << ev;
        el = random(CODE_BLOCK_LEN);
        e.SetCoefficient( ev, el );
        cout << "Add error " << ev << " at " << dec << el << "\n";
      };
      cout << "\n";

      r = c + e;

      /////////////////////////////////////////////////////////////////////
      // ＲＳ復号化
      /////////////////////////////////////////////////////////////////////

      // 受信シンボル系列 r から、シンドローム多項式 s を求める
      //
      for ( int j = 0; j < GENERATOR_DEGREE; j++ ) s.SetCoefficient( r.On(Pow(alpha,j)), j );

      // エラー位置多項式 Lambda （およびその形式的微分dLambda）と
      // エラー数値多項式 Omega を求める
      //
      sx.SetCoefficient( 1, GENERATOR_DEGREE );
      tx = s;
      A22 = 1;
      A12 = 0;
      while ( tx.GetDegree() >= (GENERATOR_DEGREE / 2) ) {
        Q_temp = sx / tx;
        sx = sx % tx;
        A_temp = A12 + (A22 * Q);
        A_temp = A12 + (A22 * Q_temp);
        A12 = A22;
        A22 = A_temp;
        swap( sx, tx );
      };
      Lambda = A22;
      dLambda = 0;
      for ( int j = 1; j <= Lambda.GetDegree(); j++ )
      dLambda.SetCoefficient( Lambda.GetCoefficient(j) * (j % 2), j-1);
      Omega = tx;

      // エラー位置とエラー値を求める
      //
      for ( int j = 0; j < CODE_BLOCK_LEN; j++ ) {
        y = Pow(alpha,255-j);
        if ( Lambda.On(y) == 0 ) {
          p = Omega.On(y);
          q = y * dLambda.On(y);
          r.SetCoefficient( r.GetCoefficient(j) + (p/q), j );
          cout << "Find error " << (p/q) << " at " << j << "\n";
        };
      };
    };
  };
};

リード・ソロモン符号の符号器/復号器のような抽象的なディジタル回路を開発する際には、 VHDL記述とVHDLテストベンチをいきなり開発するのではなく、一般に、それらの作業と並行して、C++ の検査ソフトも開発して、 VHDL記述の中間テストをしたり、テストベンチで使用するテストパターンを生成したりしますが、その検査ソフトも、 上に示した例のように、簡単に開発できます。しかも、 C++離散数学ライブラリは C++ で記述されておりますので、 高速ですし、他のライブラリと組み合わせて使用することも容易です。

弊社では、並列・パイプライン処理にもとづくリード・ソロモン符号の符号器/復号器を、 極めて安価にご提供しておりますが、それは、C++離散数学ライブラリを始めとする開発ツールを充実させることによって、 開発期間を短縮しているからです。

わざわざＩＰコアを自社開発されたり、海外のＩＰコアベンダーから高価なＩＰコアを購入されているお客様には、 「どうしてこんな価格にできるのか？」とか「こんな価格で売られると困る！」とおっしゃる方もありますが、 弊社のC++離散数学ライブラリをお使いになれば、弊社のＩＰコアの価格に納得されることでしょう。

arrow

Example