/*	
 *	clipffa.c
 *
 *	有限体演算 (Finite Field Arithmetic)
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2015 Naoyuki Sawa
 *
 *	* Sun Aug 16 19:57:01 JST 2015 Naoyuki Sawa
 *	- 作成開始。
 *	* Sat Aug 22 15:44:43 JST 2015 Naoyuki Sawa
 *	- Polynomial_Parse()を追加しました。
 *	* Tue Aug 25 00:57:49 JST 2015 Naoyuki Sawa
 *	- Polynomial_ParseF(),Polynomial_ParseV()を追加しました。
 *	* Wed Aug 26 23:08:45 JST 2015 Naoyuki Sawa
 *	- BCH符号の関数を作成開始しました。
 *	* Fri Aug 28 20:48:55 JST 2015 Naoyuki Sawa
 *	- GaloisField_Det(),GaloisField_Cof(),GaloisField_Solve()を追加しました。
 *	* Sat Aug 29 00:01:08 JST 2015 Naoyuki Sawa
 *	- BCH_Decode()を追加しました。
 *	* Sun Aug 30 13:35:11 JST 2015 Naoyuki Sawa
 *	- GaloisField_Deg()を追加しました。
 *	* Sun Aug 30 18:40:22 JST 2015 Naoyuki Sawa
 *	- リードソロモン符号の関数を作成開始しました。
 *	* Mon Aug 31 21:31:32 JST 2015 Naoyuki Sawa
 *	- GaloisField_NewDeg()を追加しました。
 */
#include "clip.h"
/****************************************************************************
 *	ガロア体
 ****************************************************************************/
//ガロア体を作成する。
//[in]
//	Gx		原始多項式。(0x2～0x1FF)
//[out]
//	戻り値		成功した場合、ガロア体を返す。
//			失敗した場合、NULLを返す。
//[note]
//	- Gxの中で、セットされている最上位ビットが(1<<deg)である場合、当関数はGF(2^deg)を生成する。
//	  例えば、Gx=0x13を指定した場合、GF(2^4)を生成する。Gx=0x11Dを指定した場合、GF(2^8)を生成する。
//	- Gxが、最長周期系列(=M系列)を生成する原始多項式ではない場合、当関数は失敗してNULLを返す。
//	  この性質を利用して、GF(2^1)～GF(2^8)を生成する、全ての原始多項式を列挙する事が出来ます。
//	  │int Gx;
//	  │for(Gx=(1<<1);Gx<(1<<9);Gx++) {
//	  │  ST_GaloisField* pGF=GaloisField_New(Gx);
//	  │  if(pGF){printf("%#11b %#5x\n",Gx,Gx);}
//	  │  free(pGF);
//	  │}
//	  □結果
//	  │       0b11   0x3
//	  │      0b111   0x7
//	  │     0b1011   0xb
//	  │     0b1101   0xd
//	  │    0b10011  0x13
//	  │    0b11001  0x19
//	  │   0b100101  0x25
//	  │   0b101001  0x29
//	  │   0b101111  0x2f
//	  │   0b110111  0x37
//	  │   0b111011  0x3b
//	  │   0b111101  0x3d
//	  │  0b1000011  0x43
//	  │  0b1011011  0x5b
//	  │  0b1100001  0x61
//	  │  0b1100111  0x67
//	  │  0b1101101  0x6d
//	  │  0b1110011  0x73
//	  │ 0b10000011  0x83
//	  │ 0b10001001  0x89
//	  │ 0b10001111  0x8f
//	  │ 0b10010001  0x91
//	  │ 0b10011101  0x9d
//	  │ 0b10100111  0xa7
//	  │ 0b10101011  0xab
//	  │ 0b10111001  0xb9
//	  │ 0b10111111  0xbf
//	  │ 0b11000001  0xc1
//	  │ 0b11001011  0xcb
//	  │ 0b11010011  0xd3
//	  │ 0b11010101  0xd5
//	  │ 0b11100101  0xe5
//	  │ 0b11101111  0xef
//	  │ 0b11110001  0xf1
//	  │ 0b11110111  0xf7
//	  │ 0b11111101  0xfd
//	  │0b100011101 0x11d
//	  │0b100101011 0x12b
//	  │0b100101101 0x12d
//	  │0b101001101 0x14d
//	  │0b101011111 0x15f
//	  │0b101100011 0x163
//	  │0b101100101 0x165
//	  │0b101101001 0x169
//	  │0b101110001 0x171
//	  │0b110000111 0x187
//	  │0b110001101 0x18d
//	  │0b110101001 0x1a9
//	  │0b111000011 0x1c3
//	  │0b111001111 0x1cf
//	  │0b111100111 0x1e7
//	  │0b111110101 0x1f5
ST_GaloisField* GaloisField_New(int Gx) {
	ST_GaloisField* pGF;
	int i, c;
	//当モジュールは、GF(2^1)～GF(2^8)の範囲を対象とする事にした。
	// - GF(2^9)以上も同じ方法で対応出来るが、まず利用しないので、メモリ節約のためにGF(2^8)までとした。
	// - GF(2^1)の原始多項式は0b1?,GF(2^8)の原始多項式は0b1????????なので、範囲外ならばエラー停止する。
	if((Gx <= (1<<0)) || (Gx >= (1<<9))) { DIE(); }
	//構造体のメモリを確保する。
	pGF = calloc(1, sizeof(ST_GaloisField));
	if(!pGF) { DIE(); }
	//原始多項式(Gx)の最上位ビット未満の位置のビットが全てセットされた値を、maxに求める。
	// - たとえば、Gx=0b100011101 ならば、max=0b011111111, deg=8 となる。
	//   要するに、max=(2^deg)-1 であり、ビット列表現の最大値に相当する。
	for(pGF->max = -1; pGF->max >= Gx; pGF->max >>= 1) { /** no job **/ }
	//拡大次数を、degに求める。
	pGF->deg = popcount(pGF->max);
	//logテーブルの全要素に'未使用(max)'を格納しておく。
	// - logテーブルに格納する値の範囲は0～(max-1)なので、未使用と意味する値としてmaxを使用出来ます。
	memset(pGF->log, pGF->max, sizeof pGF->log);
	//指数表現(i)=0～(max-1)に対応する、ビット列表現(c)=1～maxを求める。
	c = 1;	//(a^0)=1
	for(i = 0; i < pGF->max; i++) {
		//ビット列表現が0になったり、既に出現したビット列表現が再度出現したら、ガロア体ではない。
		// - 呼び出し元に対して、原始多項式が適切ではなかった事を伝えるために、ループを抜けてメモリを開放しNULLを返す。
		if(!c || (pGF->log[c] != pGF->max)) { break; }
		//expテーブルの、指数表現に対応する要素に、ビット列表現を格納する。
		pGF->exp[i] = c;
		//logテーブルの、ビット列表現に対応する要素に、指数表現を格納する。
		pGF->log[c] = i;
		//次のビット列表現を求める。
		if((c <<= 1) > pGF->max) { c ^= Gx; }
	}
	//ビット列表現が0になったり既に出現したビット列表現が再度出現してループを途中で抜けたか、又は、
	//ループを最後まで実行した結果、(a^max)=1 に戻らなかった場合は、ガロア体ではない。
	// - 呼び出し元に対して、原始多項式が適切ではなかった事を伝えるために、メモリを開放しNULLを返す。
	if((i != pGF->max) || (c != 1)) {
		GaloisField_Free(pGF);
		pGF = NULL;
	}
	//構造体のメモリ,又は,NULLを返す。
	return pGF;
}
/*--------------------------------------------------------------------------*/
//拡大次数を指定して、ガロア体を作成する。
//[in]
//	deg		拡大次数。(1～8)
//[out]
//	戻り値		ガロア体
//[note]
//	- これは、ユーティリティ関数です。
//	- 本来、特定のガロア体を作成するには、原始多項式を明示する必要が有ります。
//	  同じ拡大次数でも、原始多項式が異なると、ガロア体上での演算結果のビット列表現も異なるからです。
//	  しかし、テストプログラム作成時等、ビット列表現の違いが重要でない場合は、拡大次数だけを指定してガロア体を作成出来る方が便利だと思いました。
//	  また実際にも、QRコード等の仕様では、'特定の拡大次数の最小のビットパターンを持つ原始多項式'が指定されている事が多いようです。
//	- 以上の理由から、利便性のために、当関数を作成する事にしました。
//	  当関数はあくまでもテストプログラム作成時等だけに使用して、厳密な用途にはGaloisField_New()を使用して下さい。
ST_GaloisField* GaloisField_NewDeg(int deg) {
	//指定された次数の多項式を、最小のビットパターンから順に試して…
	int Gx    =  1<< deg;		//100...000
	int GxMax = (1<<(deg+1))-1;	//111...111
	do {
		//ガロア体が生成出来たら(=Gxが原始多項式だったら)、生成したガロア体を返す。
		ST_GaloisField* pGF = GaloisField_New(Gx);
		if(pGF) { return pGF; }
	} while(++Gx <= GxMax);
	//指定された次数の多項式の、全てのビットパターンでガロア体が生成出来なければ、エラー停止する。
	DIE();
}
/*--------------------------------------------------------------------------*/
//ガロア体を開放する。
//[in]
//	pGF		ガロア体	NULL可
void GaloisField_Free(ST_GaloisField* pGF) {
//不要	//NULLポインタでなければ…
//不要	if(pGF) {
		//構造体のメモリを開放する。
		free(pGF);
//不要	}
}
/*--------------------------------------------------------------------------*/
//ビット列表現の最大値を取得する。
//[in]
//	pGF		ガロア体
//[out]
//	戻り値		ビット列表現の最大値
//[note]
//	- GF(2^1)ならば0x1,GF(2^2)ならば0x3,...,GF(2^8)ならば0xFFを返す。
int GaloisField_Max(ST_GaloisField* pGF) {
	return pGF->max;
}
/*--------------------------------------------------------------------------*/
//拡大次数を取得する。
//[in]
//	pGF		ガロア体
//[out]
//	戻り値		拡大次数
//[note]
//	- GF(2^1)ならば1,GF(2^2)ならば2,...,GF(2^8)ならば8を返す。
int GaloisField_Deg(ST_GaloisField* pGF) {
	return pGF->deg;
}
/*--------------------------------------------------------------------------*/
//指数表現に対応する、ビット列表現を求める。
//[in]
//	pGF		ガロア体
//	i		指数表現	0～(2^deg)-2
//[out]
//	戻り値		ビット列表現	1～(2^deg)-1
//[note]
//	- ガロア体では a^((2^deg)-1) = a^0 なので、当関数の引数の範囲は 0～(2^deg)-2 とする。
int GaloisField_Exp(ST_GaloisField* pGF, int i) {
	//expテーブルの、指数表現に対応する要素に、ビット列表現が格納されている。
	// - 指数表現(i)は、0～(max-1)の範囲でなくてはならない。
	if((i < 0) || (i >= pGF->max)) { DIE(); }
	return pGF->exp[i];
}
/*--------------------------------------------------------------------------*/
//ビット列表現に対応する、指数表現を求める。
//[in]
//	pGF		ガロア体
//	c		ビット列表現	1～(2^deg)-1
//[out]
//	戻り値		指数表現	0～(2^deg)-2
//[note]
//	- ビット列表現 0 の指数表現は a^-∞ なので、当関数の引数には 0 は指定不可とした。
int GaloisField_Log(ST_GaloisField* pGF, int c) {
	//logテーブルの、ビット列表現に対応する要素に、指数表現が格納されている。
	// - ビット列表現(c)は、1～maxの範囲でなくてはならない。
	if((c <= 0) || (c > pGF->max)) { DIE(); }
	return pGF->log[c];
}
/*--------------------------------------------------------------------------*/
//指数表現＋指数表現⇒指数表現
int GaloisField_Add(ST_GaloisField* pGF, int x, int y) {
	if(((unsigned)x > (unsigned)pGF->max) ||
	   ((unsigned)y > (unsigned)pGF->max)) { DIE(); }
	return x ^ y;
}
/*--------------------------------------------------------------------------*/
//指数表現－指数表現⇒指数表現
int GaloisField_Sub(ST_GaloisField* pGF, int x, int y) {
	return GaloisField_Add(pGF, x, y);	//ガロア体上では(加算=減算)
}
/*--------------------------------------------------------------------------*/
//指数表現×指数表現⇒指数表現
int GaloisField_Mul(ST_GaloisField* pGF, int x, int y) {
	if(!x || !y) { return 0; }
	x = GaloisField_Log(pGF, x);	//1～max⇒0～(max-1)
	y = GaloisField_Log(pGF, y);	//1～max⇒0～(max-1)
	if((unsigned)(x += y) >= (unsigned)pGF->max) { x -= pGF->max; }
	return GaloisField_Exp(pGF, x);	//0～(max-1)⇒1～max
}
/*--------------------------------------------------------------------------*/
//指数表現÷指数表現⇒指数表現
int GaloisField_Div(ST_GaloisField* pGF, int x, int y) {
	if(!x) { return 0; }
	x = GaloisField_Log(pGF, x);	//1～max⇒0～(max-1)
	y = GaloisField_Log(pGF, y);	//1～max⇒0～(max-1)	(y=0)ならばここでエラー停止する。
	if((unsigned)(x -= y) >= (unsigned)pGF->max) { x += pGF->max; }
	return GaloisField_Exp(pGF, x);	//0～(max-1)⇒1～max
}
/*--------------------------------------------------------------------------*/
//A[n行][n列]の行列式(determinant)を求めます。
//[in]
//	pGF		ガロア体
//	A[n][n]		行列
//[out]
//	戻り値		行列式
//[note]
//	- clipflt1.cのmatnf_determinant()と同じ処理を、ガロア体上で行いました。
int GaloisField_Det(ST_GaloisField* pGF, const uint8_t* A/*[n][n]*/, int n) {
	int d, i, t;
	if(n < 1) { DIE(); }
	//余因子展開を用いて、行列式(determinant)を求めます。
	d = 0;
	for(i = 0; i < n; i++) {
		t = GaloisField_Cof(pGF, A, n, i, 0/*j*/);
		t = GaloisField_Mul(pGF, t, A[(n * i) + 0/*j*/]);
		d = GaloisField_Add(pGF, d, t);
	}
	//行列式を返します。
	return d;
}
/*--------------------------------------------------------------------------*/
//A[n行][n列]からi行j列を除いた、余因子(cofactor)を求めます。 */
//[in]
//	pGF		ガロア体
//	A[n][n]		行列
//	i		取り除く行
//	j		取り除く列
//[out]
//	戻り値		余因子
//[note]
//	- clipflt1.cのmatnf_cofactor()と同じ処理を、ガロア体上で行いました。
int GaloisField_Cof(ST_GaloisField* pGF, const uint8_t* A/*[n][n]*/, int n, int i, int j) {
	int d, k, l;
	uint8_t* B/*[n-1][n-1]*/;
	if((n < 1) || ((i < 0) || (i >= n)) || ((j < 0) || (j >= n))) { DIE(); }
	//A[n行][n列]からi行j列を除いた、小行列(submatrix)を作成します。
	if(!--n) { return 1; }	//小行列が0行0列になる場合
	B = malloc(n * n);
	if(!B) { DIE(); }
	for(k = 0; k <= n; k++) {
		for(l = 0; l <= n; l++) {
			if((k != i) && (l != j)) { *B++ = *A; }
			A++;
		}
	}
	B -= (n * n);
	//小行列式(minor determinant)を求めます。
	d = GaloisField_Det(pGF, B, n);
	//余因子(cofactor)を求めます。
//不要	if((i ^ j) & 1) { d = GaloisField_Sub(pGF, 0, d); }	⇒ガロア体上では±は同じなので不要
	//小行列を解放します。
	free(B);
	//余因子を返します。
	return d;
}
/*--------------------------------------------------------------------------*/
//連立方程式の解を求めます。
//[in]
//	pGF		ガロア体
//	A[n][n],b[n]	連立方程式
//	x[n]		連立方程式の解を格納する配列
//[out]
//	戻り値		行列式
//			行列式が0ならば、xは求められていません。
//[note]
//	- clipflt1.cのsolve_simultaneous_equations()と同じ処理を、ガロア体上で行いました。
int GaloisField_Solve(ST_GaloisField* pGF, const uint8_t* A/*[n][n]*/, const uint8_t* b/*[n]*/, uint8_t* x/*[n]*/, int n) {
	int d, i, j, t;
	//クラメルの公式を用いて、Aの逆行列を求めながら、bを掛けて、xを求めます。
	d = GaloisField_Det(pGF, A, n);
	if(d) {
		for(i = 0; i < n; i++) {
			x[i] = 0;
			for(j = 0; j < n; j++) {
				t = GaloisField_Cof(pGF, A, n, j, i);
				//                   順序注意!!~~~~
				t = GaloisField_Div(pGF, t, d);
				t = GaloisField_Mul(pGF, t, b[j]);
				x[i] = GaloisField_Add(pGF, x[i], t);
			}
		}
	}
	//行列式を返します。行列式が0ならば、xは求められていません。
	return d;
}
/****************************************************************************
 *	多項式
 ****************************************************************************/
//多項式を作成する。
//[in]
//	pGF		ガロア体
//[out]
//	戻り値		多項式
//[note]
// - ガロア体の作成と開放は、呼び出し側の処理でおこなってください。
// - ガロア体pGFを係数とする、255次以下の多項式として使用出来ます。
//   作成直後の多項式は、全ての項の係数が0です。
ST_Polynomial* Polynomial_New(ST_GaloisField* pGF) {
	ST_Polynomial* pP;
	//構造体のメモリを確保する。
	pP = calloc(1, sizeof(ST_Polynomial));
	if(!pP) { DIE(); }
	//ガロア体のポインタを格納する。
	pP->pGF = pGF;
	//構造体のメモリを返す。
	return pP;
}
/*--------------------------------------------------------------------------*/
//多項式を開放する。
//[in]
//	pP		多項式
void Polynomial_Free(ST_Polynomial* pP) {
//不要	//NULLポインタでなければ…
//不要	if(pP) {
		//構造体のメモリを開放する。
		free(pP);
//不要	}
}
/*--------------------------------------------------------------------------*/
//次数を取得する。
//[in]
//	pP		多項式
//[out]
//	戻り値		次数
//[note]
//	- 全ての係数が0ならば、厳密には次数=(-∞)だが、便宜的に(-1)を返す事にした。
int Polynomial_Deg(ST_Polynomial* pP) {
	int i;
	//係数が0でない最上位の項を探す。
	//全ての係数が0ならば、厳密には次数=(-∞)だが、便宜的に(-1)を返す事にした。
	for(i = ARRAY_SIZE(pP->coef) - 1; i >= 0; i--) {
		//係数が0でない項が見つかったらループを抜けて、その項の次数を返す。
		if(pP->coef[i]) { break; }
	}
	//係数が0でない最上位の項の次数,又は,-1を返す。
	return i;
}
/*--------------------------------------------------------------------------*/
//項の係数を取得する。
//[in]
//	pP		多項式
//	i		項の次数
//[out]
//	戻り値		項の係数
int Polynomial_GetCoef(ST_Polynomial* pP, int i) {
	if((unsigned)i >= (unsigned)ARRAY_SIZE(pP->coef)) { DIE(); }	//項の次数が配列サイズ以上ならば、エラー停止する。
	return pP->coef[i];
}
/*--------------------------------------------------------------------------*/
//項の係数を設定する。
//[in]
//	pP		多項式
//	i		項の次数
//	c		項の係数
void Polynomial_SetCoef(ST_Polynomial* pP, int i, int c) {
	if((unsigned)i >= (unsigned)ARRAY_SIZE(pP->coef)) { DIE(); }	//項の次数が配列サイズ以上ならば、エラー停止する。
	if((unsigned)c > (unsigned)GaloisField_Max(pP->pGF)) { DIE(); }	//係数がガロア体のビット列表現の最大値を超えていたら、エラー停止する。
	pP->coef[i] = c;
}
/*--------------------------------------------------------------------------*/
//項の係数に、直接、加算する。
//[in]
//	pP		多項式
//	i		項の次数
//	c		加算する値
void Polynomial_AddCoef(ST_Polynomial* pP, int i, int c) {
	Polynomial_SetCoef(pP, i,
		GaloisField_Add(pP->pGF,	//加算
			Polynomial_GetCoef(pP, i),
			c));
}
/*--------------------------------------------------------------------------*/
//項の係数に、直接、減算する。
//[in]
//	pP		多項式
//	i		項の次数
//	c		減算する値
void Polynomial_SubCoef(ST_Polynomial* pP, int i, int c) {
	Polynomial_SetCoef(pP, i,
		GaloisField_Sub(pP->pGF,	//減算
			Polynomial_GetCoef(pP, i),
			c));
}
/*--------------------------------------------------------------------------*/
//項の係数に、直接、乗算する。
//[in]
//	pP		多項式
//	i		項の次数
//	c		乗算する値
void Polynomial_MulCoef(ST_Polynomial* pP, int i, int c) {
	Polynomial_SetCoef(pP, i,
		GaloisField_Mul(pP->pGF,	//乗算
			Polynomial_GetCoef(pP, i),
			c));
}
/*--------------------------------------------------------------------------*/
//項の係数に、直接、除算する。
//[in]
//	pP		多項式
//	i		項の次数
//	c		除算する値
void Polynomial_DivCoef(ST_Polynomial* pP, int i, int c) {
	Polynomial_SetCoef(pP, i,
		GaloisField_Div(pP->pGF,	//除算
			Polynomial_GetCoef(pP, i),
			c));
}
/*--------------------------------------------------------------------------*/
//多項式＋多項式⇒多項式
ST_Polynomial* Polynomial_Add(ST_Polynomial* pP1, ST_Polynomial* pP2) {
	ST_GaloisField* pGF;
	ST_Polynomial* pP3;
	int i, c1, c2, c3;
	if(pP1->pGF != pP2->pGF) { DIE(); }	//P1とP2が異なるガロア体上の多項式ならば、エラー停止する。
	//ガロア体のポインタを取得する。
	pGF = pP1->pGF;
	//結果を格納する多項式を作成する。	呼び出し側で開放する。
	pP3 = Polynomial_New(pGF);
	//全ての項について…
	for(i = 0; i < ARRAY_SIZE(pP1->coef); i++) {
		//多項式1と多項式2の項の係数を加算し、多項式3の項の係数に格納する。
		c1 = Polynomial_GetCoef(pP1, i);
		c2 = Polynomial_GetCoef(pP2, i);
		c3 = GaloisField_Add(pGF, c1, c2);	//加算
		Polynomial_SetCoef(pP3, i, c3);
	}
	//結果を格納した多項式を返す。
	return pP3;
}
/*--------------------------------------------------------------------------*/
//多項式－多項式⇒多項式
ST_Polynomial* Polynomial_Sub(ST_Polynomial* pP1, ST_Polynomial* pP2) {
	return Polynomial_Add(pP1, pP2);	//ガロア体上では(加算=減算)
}
/*--------------------------------------------------------------------------*/
//多項式×多項式⇒多項式
ST_Polynomial* Polynomial_Mul(ST_Polynomial* pP1, ST_Polynomial* pP2) {
	ST_GaloisField* pGF;
	ST_Polynomial* pP3;
	int i1, c1, i2, c2, i3, c3;
	if(pP1->pGF != pP2->pGF) { DIE(); }	//P1とP2が異なるガロア体上の多項式ならば、エラー停止する。
	//ガロア体のポインタを取得する。
	pGF = pP1->pGF;
	//結果を格納する多項式を作成する。	呼び出し側で開放する。
	pP3 = Polynomial_New(pGF);
	//多項式1の全ての項について…
	for(i1 = 0; i1 < ARRAY_SIZE(pP1->coef); i1++) {
		c1 = Polynomial_GetCoef(pP1, i1);
		//多項式2の全ての項について…
		for(i2 = 0; i2 < ARRAY_SIZE(pP2->coef); i2++) {
			c2 = Polynomial_GetCoef(pP2, i2);
			//多項式1と多項式2の項の係数を乗算する。
			c3 = GaloisField_Mul(pGF, c1, c2);	//乗算
			//乗算結果が0でなければ、多項式3の項に加算する。
			// - '乗算結果が0でなければ'という判断は必須です。
			//   さもないと、多項式1,2の値に係らず、項の次数が配列サイズ以上の項に対して加算しようとして、Polynomial_AddCoef()がエラー停止します。
			//   ただし、この判断を行っても、多項式1,2の次数の合計が項の次数が配列サイズ以上だった場合は、Polynomial_AddCoef()がエラー停止します。
			if(c3) {
				i3 = i1 + i2;
				Polynomial_AddCoef(pP3, i3, c3);
			}
		}
	}
	//結果を格納した多項式を返す。
	return pP3;
}
/*--------------------------------------------------------------------------*/
static void Polynomial_DivMod(ST_Polynomial* pP1, ST_Polynomial* pP2, ST_Polynomial** ppQuot, ST_Polynomial** ppRem) {
	ST_GaloisField* pGF;
	ST_Polynomial *pQuot, *pRem;
	int deg, div, quot, i1, i2;
	if(pP1->pGF != pP2->pGF) { DIE(); }	//P1とP2が異なるガロア体上の多項式ならば、エラー停止する。
	//ガロア体のポインタを取得する。
	pGF = pP1->pGF;
	//結果を格納する多項式を作成する。	呼び出し側で開放する。
	pQuot = Polynomial_New(pGF);
	pRem  = Polynomial_New(pGF);
	//多項式2の次数を取得する。
	deg = Polynomial_Deg(pP2);
	if(deg < 0) { DIE(); }			//0除算エラー
	//多項式2の最上位の項の係数を取得する。
	div = Polynomial_GetCoef(pP2, deg);
	//筆算ループ
	for(i1 = ARRAY_SIZE(pP1->coef) - 1; i1 >= 0; i1--) {
		//被序数の桁上げ
		memmove(&pRem->coef[1], &pRem->coef[0], ARRAY_SIZE(pRem->coef) - 1);		//pRem  *= x^1	厳密にはPolynomial_Mul()を使うべきだが、処理が単純なのでメモリ操作で代用する事にした。
		Polynomial_SetCoef(pRem, 0, Polynomial_GetCoef(pP1, i1));
		//除算
		quot = GaloisField_Div(pGF, Polynomial_GetCoef(pRem, deg), div);
		//商の桁上げ
		memmove(&pQuot->coef[1], &pQuot->coef[0], ARRAY_SIZE(pQuot->coef) - 1);		//pQuot *= x^1	厳密にはPolynomial_Mul()を使うべきだが、処理が単純なのでメモリ操作で代用する事にした。
		Polynomial_SetCoef(pQuot, 0, quot);
		//減算
		for(i2 = ARRAY_SIZE(pP2->coef) - 1; i2 >= 0; i2--) {
			Polynomial_SubCoef(pRem, i2,
				GaloisField_Mul(pGF,
					Polynomial_GetCoef(pP2, i2),
					quot));
		}
	}
	//商,又は,剰余の多項式を格納する。格納しなかった多項式は開放する。
	if(ppQuot) { *ppQuot = pQuot; } else { Polynomial_Free(pQuot); }
	if(ppRem ) { *ppRem  = pRem;  } else { Polynomial_Free(pRem);  }
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//多項式÷多項式⇒多項式
ST_Polynomial* Polynomial_Div(ST_Polynomial* pP1, ST_Polynomial* pP2) {
	ST_Polynomial* pQuot;
	Polynomial_DivMod(pP1, pP2, &pQuot, NULL);	//商
	return pQuot;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//多項式％多項式⇒多項式
ST_Polynomial* Polynomial_Mod(ST_Polynomial* pP1, ST_Polynomial* pP2) {
	ST_Polynomial* pRem;
	Polynomial_DivMod(pP1, pP2, NULL, &pRem);	//剰余
	return pRem;
}
/*--------------------------------------------------------------------------*/
//多項式の変数に値を代入した結果を求める。
//[in]
//	pP		多項式
//	x		代入する値
//[out]
//	戻り値		結果の値
int Polynomial_Assign(ST_Polynomial* pP, int x) {
	int sum = 0;
	int x_i = 1;
	int i;
	for(i = 0; i < ARRAY_SIZE(pP->coef); i++) {
		//sum = sum + x^i
		sum = GaloisField_Add(pP->pGF,
			sum,
			GaloisField_Mul(pP->pGF,
				Polynomial_GetCoef(pP, i),
				x_i));
		//x^(i+1) = x^i * x
		x_i = GaloisField_Mul(pP->pGF,
			x_i,
			x);
	}
	return sum;
}
/*--------------------------------------------------------------------------*/
//文字列表現を作成する。
//[in]
//	pP		多項式
//[out]
//	戻り値		文字列
//[note]
//	- 当関数が返す文字列は、呼び出し側にてfree()で開放してください。
char* Polynomial_Str(ST_Polynomial* pP) {
	char *s, **argv;
	int i, c, argc;
	argv = calloc(ARRAY_SIZE(pP->coef) + 1/*NULL*/, sizeof(char**));
	if(!argv) { DIE(); }
	argc = 0;
	for(i = ARRAY_SIZE(pP->coef) - 1; i >= 0; i--) {
		c = Polynomial_GetCoef(pP, i);
		if(c) {
			char* s;
			int a = GaloisField_Log(pP->pGF, c);
			switch(a) {
			case 0:
				switch(i) {
				case 0:  s = strdup_printf("1");       break;
				case 1:  s = strdup_printf("x");       break;
				default: s = strdup_printf("x^%d", i); break;
				}
				break;
			case 1:
				switch(i) {
				case 0:  s = strdup_printf("a");        break;
				case 1:  s = strdup_printf("ax");       break;
				default: s = strdup_printf("ax^%d", i); break;
				}
				break;
			default:
				switch(i) {
				case 0:  s = strdup_printf("a^%d",     a);    break;
				case 1:  s = strdup_printf("a^%dx",    a);    break;
				default: s = strdup_printf("a^%dx^%d", a, i); break;
				}
				break;
			}
			argv[argc++] = s;
		}
	}
	if(!argc) { argv[argc++] = strdup_printf("%d", 0); }	//全ての項の係数が0だった場合
	s = strjoinv(" + ", argv);
	strfreev(argv);
	return s;
}
/*--------------------------------------------------------------------------*/
//文字列表現をパースして多項式を作成する。
//[in]
//	pGF		ガロア体
//	str		文字列
//[out]
//	戻り値		多項式
//[note]
//	- 文字列表現の書式は、Polynomial_Str()の出力形式に互換です。
//		文字列表現	:	項
//				|	文字列表現 (+|-) 項
//				;
//		項		:	数値
//				|	a
//				|	a^数値
//				|	           x
//				|	           x^数値
//				|	a      [*] x
//				|	a      [*] x^数値
//				|	a^数値 [*] x
//				|	a^数値 [*] x^数値
//				;
//		数値		:	[0-9]+
//				;
//	- トークンの間に空白文字が有っても無くても構いません。
//<例>
//	│ST_GaloisField* pGF=GaloisField_New(0x11D);
//	│ST_Polynomial* pP=Polynomial_Parse(pGF,"a ^ 9 * x ^ 8 + a^7 x^6 + 5x^4 - a^3 + x^2 - ax - 1");
//	│//                                                                       ~~~              ~ どちらもx^0の項の係数なので合算されます。
//	│puts(Polynomial_Str(pP)); //⇒a^9x^8 + a^7x^6 + a^50x^4 + x^2 + ax + a^223
ST_Polynomial* Polynomial_Parse(ST_GaloisField* pGF, const char* str) {
	ST_Polynomial* pP = Polynomial_New(pGF);			//多項式を作成する。
	char *s, **argv = strsplit_set(str, "+-", 0);			//項に分割する。ガロア体上では(加算=減算)なので'+'と'-'は区別不要です。
	int c, i, argc = 0;
	if(!(s = argv[argc++])) { goto L_ERR; }				//最初の項を取得する。項が一つも無ければエラー停止する。<例> ""
	do {
		while(isspace(*s)) { s++; }
		if(*s == '\0') { goto L_ERR; }				//空白文字だけのの項が有ったらエラー停止する。<例> "a^5x^4 +  + a^3x^2"
		//--- 係数 ---
		c = 1;
		//123...
		if(isdigit(*s)) {
			c = strtol(s, (char**)&s, 10);			//(base=10)必須。(base=0)にすると'a^0x'の0xをプレフィクスと見なしてパースに失敗する。
			while(isspace(*s)) { s++; }
			//123*...
			if(*s == '*') {
				s++;	//'*'
				while(isspace(*s)) { s++; }
			}
		//a...
		} else if(*s == 'a') {
			s++;	//'a'
			while(isspace(*s)) { s++; }
			i = 1;
			//a^...
			if(*s == '^') {
				s++;	//'^'
				while(isspace(*s)) { s++; }
				//a^123...
				if(isdigit(*s)) {
					i = strtol(s, (char**)&s, 10);	//(base=10)必須。(base=0)にすると'a^0x'の0xをプレフィクスと見なしてパースに失敗する。
					while(isspace(*s)) { s++; }
				} else {
					goto L_ERR;			//'a^'の後に数値が無ければエラー停止する。<例> "a^x^2"
				}
			}
			//a[^123]...
			c = GaloisField_Exp(pGF, i);
			//a[^123]*...
			if(*s == '*') {
				s++;	//'*'
				while(isspace(*s)) { s++; }
			}
		}
		//--- 項の次数 ---
		i = 0;
		//[(123|a[^123])[*]]x...
		if(*s == 'x') {
			s++;	//'x'
			while(isspace(*s)) { s++; }
			i = 1;
			//[123|a[^123][*]]x^...
			if(*s == '^') {
				s++;	//'^'
				while(isspace(*s)) { s++; }
				//[123|a[^123][*]]x^123...
				if(isdigit(*s)) {
					i = strtol(s, (char**)&s, 10);	//(base=10)必須。(base=0)にすると'a^0x'の0xをプレフィクスと見なしてパースに失敗する。
					while(isspace(*s)) { s++; }
				} else {
					goto L_ERR;			//'x^'の後に数値が無ければエラー停止する。<例> "a^2 * x^y"
				}
			}
		}
		if(*s != '\0') { goto L_ERR; }				//項の末尾に余分な文字が有ればエラー停止する。<例> "a^2 * x^3 * x"
		//[(123|a[^123])[*]][x[^123]]
		Polynomial_AddCoef(pP, i, c);				//同じ次数の項が複数回指定された場合のためにPolynomial_SetCoef()ではなくPolynomial_AddCoef()とする。ガロア体上では(加算=減算)なのでPolynomial_AddCoef()とPolynomial_SubCoef()の使い分けは不要です。
	} while((s = argv[argc++]));					//次の項を取得する。項が無くなったらループを抜ける。
	strfreev(argv);							//項に分割したメモリを開放する。
	return pP;							//多項式を返す。
L_ERR:
	die("Polynomial_Parse:'%s'", str);
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
ST_Polynomial* Polynomial_ParseF(ST_GaloisField* pGF, const char* fmt, ...) {
	ST_Polynomial* pP;
	va_list ap;
	va_start(ap, fmt);
	pP = Polynomial_ParseV(pGF, fmt, ap);
	va_end(ap);
	return pP;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
ST_Polynomial* Polynomial_ParseV(ST_GaloisField* pGF, const char* fmt, va_list ap) {
	char* str = strdup_vprintf(fmt, ap);
	ST_Polynomial* pP = Polynomial_Parse(pGF, str);
	free(str);
	return pP;
}
/****************************************************************************
 *	BCH符号
 ****************************************************************************/
//BCH符号の生成多項式を作成する。
//[in]
//	pGF		ガロア体
//	d		符号間距離
//[out]
//	戻り値		生成多項式
//[note]
//	- pGF上でa^1,a^2,...,a^(d-1),及び,それらの共役根を根に持つ最小多項式を計算します。
static ST_Polynomial* BCH_GeneratorPolynomial_New(ST_GaloisField* pGF, int d/*=(2Q+1)*/) {
	ST_Polynomial* pP1 = Polynomial_Parse(pGF, "1");
	const int max = GaloisField_Max(pGF);
	int i;
	for(i = 1; i < d; i++) {
		int j = i;
		do {
			if((j <<= 1) >= max) { j -= max; }				//次の共役根を求める。
			if(!j) { DIE(); }						//max=(2^m)-1=奇数なので、j=0になる事は無いはず。(バグ)
			if(j < i) { break; }						//iより低い次数に一致したら、既に掛けているので飛ばす。
		} while(j != i);							//1周して元に戻ったら抜ける。
		if(j < i) { continue; }							//iより低い次数に一致したら、既に掛けているので飛ばす。
		do {
			ST_Polynomial* pP2 = Polynomial_ParseF(pGF, "x - a^%d", j);	//(x-a),(x-a^2),(x-a^3),…
			ST_Polynomial* pP3 = Polynomial_Mul(pP1, pP2);			//(x-a)*(x-a^2)*(x-a^3)*…
			Polynomial_Free(pP1);
			Polynomial_Free(pP2);
			pP1 = pP3;
			if((j <<= 1) >= max) { j -= max; }				//次の共役根を求める。
		} while(j != i);							//1周して元に戻ったら抜ける。
	}
	for(i = Polynomial_Deg(pP1); i >= 0; i--) {					//以上の処理で求めた多項式の、全ての項の係数が0,又は,1である事を確認する。
		if(Polynomial_GetCoef(pP1, i) & ~1) { DIE(); }				//そうなっていなければ、バグです。
	}
	return pP1;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//BCH符号化復号化器を作成する。
//[in]
//	pGF		ガロア体
//	q		訂正可能符号語数
//[out]
//	戻り値		BCH符号化復号化器
ST_BCH* BCH_New(ST_GaloisField* pGF, int q) {
	ST_BCH* pBCH;
	//構造体のメモリを確保する。
	pBCH = calloc(1, sizeof(ST_BCH));
	if(!pBCH) { DIE(); }
	//ガロア体のポインタを格納する。
	pBCH->pGF = pGF;
	//訂正可能符号語数,符号間距離を格納する。
	pBCH->q = q;
	pBCH->d = q * 2 + 1;			//訂正可能符号語数Qの時、符号間距離d=(2Q+1)
	//BCH符号の生成多項式を作成する。
	pBCH->pGP = BCH_GeneratorPolynomial_New(pBCH->pGF, pBCH->d);
	//総符号語数,情報符号語数,検査符号語数を格納する。
	pBCH->n = GaloisField_Max(pBCH->pGF);	//総符号語数
	pBCH->m = Polynomial_Deg(pBCH->pGP);	//検査符号語数
	pBCH->k = pBCH->n - pBCH->m;		//情報符号語数
	if(pBCH->n <= pBCH->m) { DIE(); }	//総符号語数が検査符号語数以下,即ち,情報符号語数が0以下であってはならない。
	//構造体のメモリを返す。
	return pBCH;
}
/*--------------------------------------------------------------------------*/
//BCH符号化復号化器を開放する。
//[in]
//	pBCH		BCH符号化復号化器
void BCH_Free(ST_BCH* pBCH) {
	//NULLポインタでなければ…
	if(pBCH) {
		//生成多項式を開放する。
		Polynomial_Free(pBCH->pGP);
		//構造体のメモリを開放する。
		free(pBCH);
	}
}
/*--------------------------------------------------------------------------*/
//情報符号語を符号化して、送信符号語を作成する。
//[in]
//	pBCH		BCH符号化復号化器
//	aInfo		情報符号語		当関数がbitarray_lsb1st_get()で操作するので、ワードアライメントされている必要が有ります。
//[out]
//	aSend		送信符号語		当関数がbitarray_lsb1st_set()で操作するので、ワードアライメントされている必要が有ります。
void BCH_Encode(ST_BCH* pBCH, const void* aInfo/*int[(k+31)/32]*/, void* aSend/*int[(n+31)/32]*/) {
	ST_Polynomial *pP1, *pP2, *pP3;
	int i, t;
	//情報多項式 * x^m
	pP1 = Polynomial_New(pBCH->pGF);
	for(i = 0; i < pBCH->k; i++) {
		t = bitarray_lsb1st_get(aInfo, i, 1);
		Polynomial_SetCoef(pP1, pBCH->m + i, t);
	}
	//検査多項式 = (情報多項式 * x^m) % 生成多項式
	pP2 = Polynomial_Mod(pP1, pBCH->pGP);
	//送信多項式 = (情報多項式 * x^m) + 検査多項式
	pP3 = Polynomial_Add(pP1, pP2);
	//送信多項式の係数を、送信符号語に格納する。
	for(i = 0; i < pBCH->n; i++) {
		t = Polynomial_GetCoef(pP3, i);
		bitarray_lsb1st_set(aSend, i, 1, t);
	}
	//多項式を開放する。
	Polynomial_Free(pP1);
	Polynomial_Free(pP2);
	Polynomial_Free(pP3);
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
void BCH_EncodeN(ST_BCH* pBCH, const void* aInfK/*int[(K+31)/32]*/, void* aSenN/*int[(N+31)/32]*/, int N) {	//短縮BCH符号
	void *aInfo, *aSend;
	int K, i, t;
	//短縮した総符号語数が、BCH符号化復号化器の総符号語数超過,又は,検査符号語数未満ならば、エラー停止する。
	if((N > pBCH->n) || (N < pBCH->m)) { DIE(); }
	//短縮した情報符号語数を求める。
	K = N - pBCH->n + pBCH->k;
	//BCH符号化復号化器の情報符号語数に合わせるための、一時的なビット配列を確保する。
	if(!(aInfo = bitarray_alloc(pBCH->k))) { DIE(); }
	//BCH符号化復号化器の総符号語数に合わせるための、一時的なビット配列を確保する。
	if(!(aSend = bitarray_alloc(pBCH->n))) { DIE(); }
	//指定された情報符号語を、一時的なビット配列にコピーする。K以上のビットは0のままとする。
	for(i = 0; i < K; i++) {
		t = bitarray_lsb1st_get(aInfK, i, 1);
		    bitarray_lsb1st_set(aInfo, i, 1, t);
	}
	//BCH符号化復号化器の総符号語数と情報符号語数を用いて、符号化を行う。
	BCH_Encode(pBCH, aInfo, aSend);
	//一時的なビット配列を、指定された送信符号語にコピーする。N以上のビットは捨てる。
	for(i = 0; i < N; i++) {
		t = bitarray_lsb1st_get(aSend, i, 1);
		    bitarray_lsb1st_set(aSenN, i, 1, t);
	}
	//一時的なビット配列を開放する。
	bitarray_free(aInfo);
	bitarray_free(aSend);
}
/*--------------------------------------------------------------------------*/
//トゥープリッツ行列を作成する。
//[in]
//	s[n*2]		トゥープリッツ行列の要素となる値。s[0]は参照しない。
//[out]
//	戻り値		トゥープリッツ行列。呼び出し側にてfree()で開放せよ。
//[note]
//	- 厳密には、当関数が作成する行列は、トゥープリッツ行列の左右反転した形です。
//	  処理しやすさの都合上、呼び出し側の処理も含めて、左右反転した形にしました。
//	- 入力s[]の要素と、出力A[][]の要素の対応は、以下の通りです。
//	  n=2の場合
//		│s[1] s[2]│
//		│s[2] s[3]│
//	  n=3の場合
//		│s[1] s[2] s[3]│
//		│s[2] s[3] s[4]│
//		│s[3] s[4] s[5]│
//	  n=4の場合
//		│s[1] s[2] s[3] s[4]│
//		│s[2] s[3] s[4] s[5]│
//		│s[3] s[4] s[5] s[6]│
//		│s[4] s[5] s[6] s[7]│
//	  n=5～の場合も同様
static uint8_t* BCH_ToeplitzMatrix_New(const uint8_t* s/*[n*2]*/, int n) {
	uint8_t* A;
	int i, j;
	if(n < 1) { DIE(); }
	A = malloc(n * n);
	if(!A) { DIE(); }
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++) {
			A[(n * i) + j] = s[1 + i + j];
			//~~~~~~~~~~~BCH_ToeplitzMatrix_New()とReedSolomon_VanDerMonde_New()とで逆である事に注意
		}
	}
	return A;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//受信符号語を復号化して、情報符号語を作成する。
//[in]
//	pBCH		BCH符号化復号化器
//	aRecv		受信符号語		当関数がbitarray_lsb1st_get()で操作するので、ワードアライメントされている必要が有ります。
//[out]
//	aInfo		情報符号語		当関数がbitarray_lsb1st_set()で操作するので、ワードアライメントされている必要が有ります。
//	戻り値		誤りが無ければ、0を返す。			┬これらの場合、aInfoに正しい情報符号語を格納する。
//			誤りが有り、訂正出来た場合は、誤り個数を返す。	┘
//			誤りが有り、訂正不可能ならば、(-1)を返す。	─この場合、aInfoの内容は不定(実際には訂正前の情報符号語)となる。
//[note]
//	- アプリケーションの観点からは、戻り値が(-1)でなければ、aInfoに正しい情報符号語が格納されていると見なして構わない。
//	  ただし、訂正可能符号語数を超える誤りによって、偶然正しい符号語に一致した場合との区別は出来ない。(他の誤り訂正方式の場合も同様)
//	- □参照資料
//	  │『改訂新版 やり直しのための工業数学 情報通信編』(CQ出版社)
//	  │「9.6 BCH符号の復号化」(p.122～p.126)
//	  │「9.7 複数個のビット誤りを訂正するBCH符号」(p.126～p.136) ← 特にこれが参考になった。誤り位置検出多項式の説明が判り易い。
int BCH_Decode(ST_BCH* pBCH, const void* aRecv/*int[(n+31)/32]*/, void* aInfo/*int[(k+31)/32]*/) {
	ST_Polynomial* pP;
	int i, q, t;
	uint8_t *A, s[256], x[256];
	//--- ①シンドローム値の計算 ---
	//受信多項式を作成する。
	pP = Polynomial_New(pBCH->pGF);
	for(i = 0; i < pBCH->n; i++) {
		t = bitarray_lsb1st_get(aRecv, i, 1);
		Polynomial_SetCoef(pP, i, t);
		//受信符号語のうち、情報符号語の部分ならば…
		if(i >= pBCH->m) {
			//訂正前の情報符号語を格納しておく。
			// - 誤りが無ければ、このまま結果となる。誤りが有れば、この後の処理で訂正する。
			bitarray_lsb1st_set(aInfo, i - pBCH->m, 1, t);
		}
	}
	//シンドロームを計算する。
	// - s[i-1]=Si=P(a^i),i=1～d-1
	t = 0;
	for(i = 1; i < pBCH->d; i++) {	//a^1～a^(d-1)
		//□参照資料
		//│http://ja.wikipedia.org/wiki/剰余の定理
		//│多項式に関する剰余の定理は、多項式f(x)をモニックな(=最高次の係数が1である)二項一次多項式x-aで割ったときの剰余はf(a)であるという定理。
		//│またとくに、f(a)=0ならばf(x)がx-aを因数に持つことが従う(=因数定理)。
		s[i - 1] = Polynomial_Assign(pP, GaloisField_Exp(pBCH->pGF, i));	//Si=P(a^i),i=1～d-1
		t |= s[i - 1];
	}
	//受信多項式を開放する。
	Polynomial_Free(pP);
	//シンドロームが全て0ならば、訂正不要なのでここまで。
	if(!t) { return 0; }	//誤り無し
	//--- ②誤りのビット数の算出 ---
	//--- ③誤り位置検出多項式 ^L(x) の係数計算 ---
	//誤り個数Q～1の順に…
	for(q = pBCH->q; q; q--) {
		//トゥープリッツ行列を作成する。
		A = BCH_ToeplitzMatrix_New(s, q);
		//連立方程式の解を求める。
		// - 連立方程式の解は、誤り位置検出多項式の係数となる。
		//   x[0] = L1, x[1] = L2, ..., x[q-2] = L(q-1), x[q-1] = Lq
		t = GaloisField_Solve(pBCH->pGF, A, s, x, q);
		//トゥープリッツ行列を開放する。
		free(A);
		//連立方程式の解が求まったら、ループを抜ける。
		if(t) { break; }
	}
	//どの誤り個数に対しても、連立方程式の解が求まらなければ、訂正不可能なのでここまで。
	if(!q) { return -1; }	//訂正不可能
	//--- ④誤りが発生したビット位置の計算 ---
	//--- ⑤誤りの訂正 ---
	//誤り位置検出多項式を作成する。
	// - 誤り位置検出多項式 = Lq * x^q + L(q-1) * x^(q-1) + ... + L2 * x^2 + L1 * x + 1
	pP = Polynomial_Parse(pBCH->pGF, "1");
	for(i = 1; i <= q; i++) {
		Polynomial_SetCoef(pP, i, x[i - 1]);
	}
	//誤り位置を示す x = a^(m+i) (i=0,1,2,...,(k-1)) を順に、誤り位置検出多項式に代入する。
	// - 検査符号語の部分はaInfo[]に含まないので、a^0～a^(m-1) の部分は訂正する必要が無い。
	for(i = 0; i < pBCH->k; i++) {
		//代入した結果が0になったら…
		if(!Polynomial_Assign(pP, GaloisField_Exp(pBCH->pGF, pBCH->m + i))) {
			//この位置の情報符号語の、ビットを反転する。
			t = bitarray_lsb1st_get(aInfo, i, 1);
			    bitarray_lsb1st_set(aInfo, i, 1, t ^ 1);
		}
	}
	//誤り位置検出多項式を開放する。
	Polynomial_Free(pP);
	//誤り個数を返す。
	return q;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
int BCH_DecodeN(ST_BCH* pBCH, const void* aRecN/*int[(N+31)/32]*/, void* aInfK/*int[(K+31)/32]*/, int N) {	//短縮BCH符号
	void *aInfo, *aRecv;
	int K, i, t, q;
	//短縮した総符号語数が、BCH符号化復号化器の総符号語数超過,又は,検査符号語数未満ならば、エラー停止する。
	if((N > pBCH->n) || (N < pBCH->m)) { DIE(); }
	//短縮した情報符号語数を求める。
	K = N - pBCH->n + pBCH->k;
	//BCH符号化復号化器の情報符号語数に合わせるための、一時的なビット配列を確保する。
	if(!(aInfo = bitarray_alloc(pBCH->k))) { DIE(); }
	//BCH符号化復号化器の総符号語数に合わせるための、一時的なビット配列を確保する。
	if(!(aRecv = bitarray_alloc(pBCH->n))) { DIE(); }
	//指定された受信符号語を、一時的なビット配列にコピーする。N以上のビットは0のままとする。
	for(i = 0; i < N; i++) {
		t = bitarray_lsb1st_get(aRecN, i, 1);
		    bitarray_lsb1st_set(aRecv, i, 1, t);
	}
	//BCH符号化復号化器の総符号語数と情報符号語数を用いて、復号化を行う。
	q = BCH_Decode(pBCH, aRecv, aInfo);
	//一時的なビット配列を、指定された情報符号語にコピーする。K以上のビットは捨てる。
	for(i = 0; i < K; i++) {
		t = bitarray_lsb1st_get(aInfo, i, 1);
		    bitarray_lsb1st_set(aInfK, i, 1, t);
	}
	//一時的なビット配列を開放する。
	bitarray_free(aInfo);
	bitarray_free(aRecv);
	return q;
}
/****************************************************************************
 *	リードソロモン符号
 ****************************************************************************/
//リードソロモン符号の生成多項式を作成する。
//[in]
//	pGF		ガロア体
//	deg		次数
//[out]
//	戻り値		生成多項式
//[note]
//	- (x-a^0)×(x-a^1)×...×(x-a^(deg-1)) を計算します。
static ST_Polynomial* ReedSolomon_GeneratorPolynomial_New(ST_GaloisField* pGF, int deg) {
	ST_Polynomial* pP1 = Polynomial_Parse(pGF, "1");			//( 0 )次の生成多項式 = 1
	int i;
	for(i = 0; i < deg; i++) {						//i=0～(deg-1)について…
		ST_Polynomial* pP2 = Polynomial_ParseF(pGF, "x - a^%d", i);	//                                        (x-a^i)
		ST_Polynomial* pP3 = Polynomial_Mul(pP1, pP2);			//(i+1)次の生成多項式 = i次の生成多項式 * (x-a^i)
		Polynomial_Free(pP1);
		Polynomial_Free(pP2);
		pP1 = pP3;
	}
	return pP1;								//(deg)次の生成多項式を返す。
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//リードソロモン符号化復号化器を作成する。
//[in]
//	pGF		ガロア体
//	q		訂正可能符号語数
//[out]
//	戻り値		リードソロモン符号化復号化器
ST_ReedSolomon* ReedSolomon_New(ST_GaloisField* pGF, int q) {
	ST_ReedSolomon* pRS;
	//構造体のメモリを確保する。
	pRS = calloc(1, sizeof(ST_ReedSolomon));
	if(!pRS) { DIE(); }
	//ガロア体のポインタを格納する。
	pRS->pGF = pGF;
	//訂正可能符号語数,符号間距離を格納する。
	pRS->q = q;
	pRS->d = q * 2 + 1;			//訂正可能符号語数Qの時、符号間距離d=(2Q+1)
	//総符号語数,情報符号語数,検査符号語数を格納する。
	pRS->n = GaloisField_Max(pRS->pGF);	//総符号語数
	pRS->m = pRS->d - 1;			//検査符号語数
	pRS->k = pRS->n - pRS->m;		//情報符号語数
	if(pRS->n <= pRS->m) { DIE(); }		//総符号語数が検査符号語数以下,即ち,情報符号語数が0以下であってはならない。
	//リードソロモン符号の生成多項式を作成する。
	pRS->pGP = ReedSolomon_GeneratorPolynomial_New(pRS->pGF,
		pRS->m);	//生成多項式の次数=検査符号語数		検査符号語数は生成多項式の最上位の係数(1)を含まないので-1は不要。
	//構造体のメモリを返す。
	return pRS;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//検査符号語数を指定して、リードソロモン符号化復号化器を作成する。
//[in]
//	pGF		ガロア体
//	m		検査符号語数
//[out]
//	戻り値		リードソロモン符号化復号化器
//[note]
//	- 今後、QRコードに対応する時のために、作成した関数です。
//	  ReedSolomon_New() では、検査符号語数が偶数のリードソロモン符号化復号化器しか作成出来ません。
//	  しかしQRコードの仕様には、検査符号語数が奇数の場合も有るため、そのための関数を用意しました。
ST_ReedSolomon* ReedSolomon_NewM(ST_GaloisField* pGF, int m) {	//QRコード用
	ST_ReedSolomon* pRS;
	//構造体のメモリを確保する。
	pRS = calloc(1, sizeof(ST_ReedSolomon));
	if(!pRS) { DIE(); }
	//ガロア体のポインタを格納する。
	pRS->pGF = pGF;
	//総符号語数,情報符号語数,検査符号語数を格納する。
	pRS->n = GaloisField_Max(pRS->pGF);	//総符号語数
	pRS->m = m;				//検査符号語数
	pRS->k = pRS->n - pRS->m;		//情報符号語数
	if(pRS->n <= pRS->m) { DIE(); }		//総符号語数が検査符号語数以下,即ち,情報符号語数が0以下であってはならない。
	//訂正可能符号語数,符号間距離を格納する。
	pRS->d = (pRS->m + 1);			//検査符号語数mの時、符号間距離d=(m+1)
	pRS->q = (pRS->d - 1) / 2;		//符号間距離dの時、訂正可能符号語数Q=(d-1)/2
	//リードソロモン符号の生成多項式を作成する。
	pRS->pGP = ReedSolomon_GeneratorPolynomial_New(pRS->pGF,
		pRS->m);	//生成多項式の次数=検査符号語数		検査符号語数は生成多項式の最上位の係数(1)を含まないので-1は不要。
	//構造体のメモリを返す。
	return pRS;
}
/*--------------------------------------------------------------------------*/
//リードソロモン符号化復号化器を開放する。
//[in]
//	pRS		リードソロモン符号化復号化器
void ReedSolomon_Free(ST_ReedSolomon* pRS) {
	//NULLポインタでなければ…
	if(pRS) {
		//生成多項式を開放する。
		Polynomial_Free(pRS->pGP);
		//構造体のメモリを開放する。
		free(pRS);
	}
}
/*--------------------------------------------------------------------------*/
//情報符号語を符号化して、送信符号語を作成する。
//[in]
//	pRS		リードソロモン符号化復号化器
//	aInfo		情報符号語		当関数がbitarray_lsb1st_get()で操作するので、ワードアライメントされている必要が有ります。
//[out]
//	aSend		送信符号語		当関数がbitarray_lsb1st_set()で操作するので、ワードアライメントされている必要が有ります。
void ReedSolomon_Encode(ST_ReedSolomon* pRS, const void* aInfo/*int[(r*k+31)/32]*/, void* aSend/*int[(r*n+31)/32]*/) {	//r=pGF->deg
	const int r = GaloisField_Deg(pRS->pGF);
	ST_Polynomial *pP1, *pP2, *pP3;
	int i, t;
	//情報多項式 * x^m
	pP1 = Polynomial_New(pRS->pGF);
	for(i = 0; i < pRS->k; i++) {
		t = bitarray_lsb1st_get(aInfo, r * i, r);
		Polynomial_SetCoef(pP1, pRS->m + i, t);
	}
	//検査多項式 = (情報多項式 * x^m) % 生成多項式
	pP2 = Polynomial_Mod(pP1, pRS->pGP);
	//送信多項式 = (情報多項式 * x^m) + 検査多項式
	pP3 = Polynomial_Add(pP1, pP2);
	//送信多項式の係数を、送信符号語に格納する。
	for(i = 0; i < pRS->n; i++) {
		t = Polynomial_GetCoef(pP3, i);
		bitarray_lsb1st_set(aSend, r * i, r, t);
	}
	//多項式を開放する。
	Polynomial_Free(pP1);
	Polynomial_Free(pP2);
	Polynomial_Free(pP3);
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
void ReedSolomon_EncodeN(ST_ReedSolomon* pRS, const void* aInfK/*int[(r*K+31)/32]*/, void* aSenN/*int[(r*N+31)/32]*/, int N) {	//r=pGF->deg	//短縮RS符号
	const int r = GaloisField_Deg(pRS->pGF);
	void *aInfo, *aSend;
	int K, i, t;
	//短縮した総符号語数が、リードソロモン符号化復号化器の総符号語数超過,又は,検査符号語数未満ならば、エラー停止する。
	if((N > pRS->n) || (N < pRS->m)) { DIE(); }
	//短縮した情報符号語数を求める。
	K = N - pRS->n + pRS->k;
	//リードソロモン符号化復号化器の情報符号語数に合わせるための、一時的なビット配列を確保する。
	if(!(aInfo = bitarray_alloc(r * pRS->k))) { DIE(); }
	//リードソロモン符号化復号化器の総符号語数に合わせるための、一時的なビット配列を確保する。
	if(!(aSend = bitarray_alloc(r * pRS->n))) { DIE(); }
	//指定された情報符号語を、一時的なビット配列にコピーする。K以上のビットは0のままとする。
	for(i = 0; i < K; i++) {
		t = bitarray_lsb1st_get(aInfK, r * i, r);
		    bitarray_lsb1st_set(aInfo, r * i, r, t);
	}
	//リードソロモン符号化復号化器の総符号語数と情報符号語数を用いて、符号化を行う。
	ReedSolomon_Encode(pRS, aInfo, aSend);
	//一時的なビット配列を、指定された送信符号語にコピーする。N以上のビットは捨てる。
	for(i = 0; i < N; i++) {
		t = bitarray_lsb1st_get(aSend, r * i, r);
		    bitarray_lsb1st_set(aSenN, r * i, r, t);
	}
	//一時的なビット配列を開放する。
	bitarray_free(aInfo);
	bitarray_free(aSend);
}
/*--------------------------------------------------------------------------*/
//ファンデアモンデ行列を作成する。
//[in]
//	s[n*2]		ファンデアモンデ行列の等比数列の係数。
//[out]
//	戻り値		ファンデアモンデ行列。呼び出し側にてfree()で開放せよ。
//[note]
//	- 入力x[]の要素と、出力A[][]の要素の対応は、以下の通りです。
//	  n=2の場合
//		│1          1       │
//		│a^x[0]     a^ x[1] │
//	  n=3の場合
//		│1          1          1          │
//		│a^ x[0]    a^ x[1]    a^ x[2]    │
//		│a^(x[0]*2) a^(x[1]*2) a^(x[2]*2) │
//	  n=4の場合
//		│1          1          1          1          │
//		│a^ x[0]    a^ x[1]    a^ x[2]    a^ x[3]    │
//		│a^(x[0]*2) a^(x[1]*2) a^(x[2]*2) a^(x[3]*2) │
//		│a^(x[0]*3) a^(x[1]*3) a^(x[2]*3) a^(x[3]*3) │
//	  n=5～の場合も同様
static uint8_t* ReedSolomon_VanDerMonde_New(ST_GaloisField* pGF, const uint8_t* x/*[n]*/, int n) {
	uint8_t* A;
	int i, j, t, u;
	if(n < 1) { DIE(); }
	A = malloc(n * n);
	if(!A) { DIE(); }
	for(i = 0; i < n; i++) {
		t = 1;
		u = GaloisField_Exp(pGF, *x++);		//   a^x[0]
		for(j = 0; j < n; j++) {
			A[(n * j) + i] = t;
			//~~~~~~~~~~~BCH_ToeplitzMatrix_New()とReedSolomon_VanDerMonde_New()とで逆である事に注意
			t = GaloisField_Mul(pGF, t, u);	//1⇒a^x[i]⇒a^(x[i]*2)⇒...⇒a^(x[i]*(n-1))
		}
	}
	return A;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//受信符号語を復号化して、情報符号語を作成する。
//[in]
//	pRS		リードソロモン符号化復号化器
//	aRecv		受信符号語		当関数がbitarray_lsb1st_get()で操作するので、ワードアライメントされている必要が有ります。
//[out]
//	aInfo		情報符号語		当関数がbitarray_lsb1st_set()で操作するので、ワードアライメントされている必要が有ります。
//	戻り値		誤りが無ければ、0を返す。			┬これらの場合、aInfoに正しい情報符号語を格納する。
//			誤りが有り、訂正出来た場合は、誤り個数を返す。	┘
//			誤りが有り、訂正不可能ならば、(-1)を返す。	─この場合、aInfoの内容は不定(実際には訂正前の情報符号語)となる。
//[note]
//	- アプリケーションの観点からは、戻り値が(-1)でなければ、aInfoに正しい情報符号語が格納されていると見なして構わない。
//	  ただし、訂正可能符号語数を超える誤りによって、偶然正しい符号語に一致した場合との区別は出来ない。(他の誤り訂正方式の場合も同様)
//	- □参照資料
//	  │『改訂新版 やり直しのための工業数学 情報通信編』(CQ出版社)
//	  │「10.3 RS符号の復号化」(p.143～p.147)
//	  │「10.4 複数個のビット誤りを訂正するRS符号」(p.148～p.157) ← 特にこれが参考になった。誤り位置検出多項式,誤り内容方程式の説明が判り易い。
int ReedSolomon_Decode(ST_ReedSolomon* pRS, const void* aRecv/*int[(r*n+31)/32]*/, void* aInfo/*int[(r*k+31)/32]*/) {	//r=pGF->deg
	const int r = GaloisField_Deg(pRS->pGF);
	ST_Polynomial* pP;
	int i, q, t;
	uint8_t *A, s[256], x[256], y[256];
	//--- ①シンドローム値の計算 ---
	//受信多項式を作成する。
	pP = Polynomial_New(pRS->pGF);
	for(i = 0; i < pRS->n; i++) {
		t = bitarray_lsb1st_get(aRecv, r * i, r);
		Polynomial_SetCoef(pP, i, t);
		//受信符号語のうち、情報符号語の部分ならば…
		if(i >= pRS->m) {
			//訂正前の情報符号語を格納しておく。
			// - 誤りが無ければ、このまま結果となる。誤りが有れば、この後の処理で訂正する。
			bitarray_lsb1st_set(aInfo, r * (i - pRS->m), r, t);
		}
	}
	//シンドロームを計算する。
	// - s[i]=Si=P(a^i),i=0～m-1
	t = 0;
	for(i = 0; i < pRS->m; i++) {	//a^0～a^(m-1)
		//□参照資料
		//│http://ja.wikipedia.org/wiki/剰余の定理
		//│多項式に関する剰余の定理は、多項式f(x)をモニックな(=最高次の係数が1である)二項一次多項式x-aで割ったときの剰余はf(a)であるという定理。
		//│またとくに、f(a)=0ならばf(x)がx-aを因数に持つことが従う(=因数定理)。
		s[i] = Polynomial_Assign(pP, GaloisField_Exp(pRS->pGF, i));	//Si=P(a^i),i=0～m-1
		t |= s[i];
	}
	//受信多項式を開放する。
	Polynomial_Free(pP);
	//シンドロームが全て0ならば、訂正不要なのでここまで。
	if(!t) { return 0; }	//誤り無し
	//--- ②誤りのブロック数の算出 ---
	//--- ③誤り位置検出多項式 ^L(x) の係数計算 ---
	//誤り個数Q～1の順に…
	for(q = pRS->q; q; q--) {
		//トゥープリッツ行列を作成する。
		A = BCH_ToeplitzMatrix_New(s, q);	//BCH符号の処理と同じなので、BCH符号のサブルーチンをそのまま使用する事にした。
		//連立方程式の解を求める。
		// - 連立方程式の解は、誤り位置検出多項式の係数となる。
		//   x[0] = L1, x[1] = L2, ..., x[q-2] = L(q-1), x[q-1] = Lq
		t = GaloisField_Solve(pRS->pGF, A, s, x, q);
		//トゥープリッツ行列を開放する。
		free(A);
		//連立方程式の解が求まったら、ループを抜ける。
		if(t) { break; }
	}
	//どの誤り個数に対しても、連立方程式の解が求まらなければ、訂正不可能なのでここまで。
	if(!q) { return -1; }	//訂正不可能
	//--- ④誤りが発生したブロック位置の計算 ---
	//誤り位置検出多項式を作成する。
	// - 誤り位置検出多項式 = Lq * x^q + L(q-1) * x^(q-1) + ... + L2 * x^2 + L1 * x + 1
	pP = Polynomial_Parse(pRS->pGF, "1");
	for(i = 1; i <= q; i++) {
		Polynomial_SetCoef(pP, i, x[i - 1]);
	}
	//誤り位置を示す x = a^i (i=0,1,2,...,(n-1)) を順に、誤り位置検出多項式に代入する。
	// - BCH_Decode()では情報符号語の部分だけで良かったが、ReedSolomon_Decode()では検査符号語の部分も含めて実行する必要が有ります。
	//   この後の処理で、誤り内容方程式を解くために、検査符号語の部分も含めて、全ての誤り位置が必要だからです。
	t = 0;
	for(i = 0; i < pRS->n; i++) {
		//代入した結果が0になったら…
		if(!Polynomial_Assign(pP, GaloisField_Exp(pRS->pGF, i))) {
			//誤り位置を格納する。
			if(t < q) { x[t] = i; }	//訂正可能符号語数を超える誤りが発生した場合、代入した結果が0になる箇所が、q未満,又は,q超過になる事が有る。
			t++;
		}
	}
	//誤り位置検出多項式を開放する。
	Polynomial_Free(pP);
	//訂正可能符号語数を超える誤りが発生した場合、代入した結果が0になる箇所が、q未満,又は,q超過になる事が有る。
	if(t != q) { return -1; }
	//--- ⑤誤り値の計算(誤り内容方程式を利用) ---
	//ファンデアモンデ行列を作成する。
	// - ファンデアモンデ行列は、誤り内容方程式の行列表現である。
	A = ReedSolomon_VanDerMonde_New(pRS->pGF, x, q);
	//連立方程式の解を求める。
	// - 連立方程式の解は、誤り内容となる。
	//   x[0] = E1, x[1] = E2, ..., x[q-2] = E(q-1), x[q-1] = Eq
	t = GaloisField_Solve(pRS->pGF, A, s, y, q);
	if(!t) { DIE(); }
	//ファンデアモンデ行列を開放する。
	free(A);
	//--- ⑥誤りの訂正 ---
	//個々の誤り位置について…
	for(i = 0; i < q; i++) {
		//情報符号語の部分ならば…
		if(x[i] >= pRS->m) {
			//この位置の情報符号語の、ビットを反転する。	ガロア体上の加減算はビットを反転と同じ
			t = bitarray_lsb1st_get(aInfo, r * (x[i] - pRS->m), r);
			    bitarray_lsb1st_set(aInfo, r * (x[i] - pRS->m), r, t ^ y[i]);
		}
	}
	//誤り個数を返す。
	return q;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
int ReedSolomon_DecodeN(ST_ReedSolomon* pRS, const void* aRecN/*int[(r*N+31)/32]*/, void* aInfK/*int[(r*K+31)/32]*/, int N) {	//r=pGF->deg	//短縮RS符号
	const int r = GaloisField_Deg(pRS->pGF);
	void *aInfo, *aRecv;
	int K, i, t, q;
	//短縮した総符号語数が、リードソロモン符号化復号化器の総符号語数超過,又は,検査符号語数未満ならば、エラー停止する。
	if((N > pRS->n) || (N < pRS->m)) { DIE(); }
	//短縮した情報符号語数を求める。
	K = N - pRS->n + pRS->k;
	//リードソロモン符号化復号化器の情報符号語数に合わせるための、一時的なビット配列を確保する。
	if(!(aInfo = bitarray_alloc(r * pRS->k))) { DIE(); }
	//リードソロモン符号化復号化器の総符号語数に合わせるための、一時的なビット配列を確保する。
	if(!(aRecv = bitarray_alloc(r * pRS->n))) { DIE(); }
	//指定された受信符号語を、一時的なビット配列にコピーする。N以上のビットは0のままとする。
	for(i = 0; i < N; i++) {
		t = bitarray_lsb1st_get(aRecN, r * i, r);
		    bitarray_lsb1st_set(aRecv, r * i, r, t);
	}
	//リードソロモン符号化復号化器の総符号語数と情報符号語数を用いて、復号化を行う。
	q = ReedSolomon_Decode(pRS, aRecv, aInfo);
	//一時的なビット配列を、指定された情報符号語にコピーする。K以上のビットは捨てる。
	for(i = 0; i < K; i++) {
		t = bitarray_lsb1st_get(aInfo, r * i, r);
		    bitarray_lsb1st_set(aInfK, r * i, r, t);
	}
	//一時的なビット配列を開放する。
	bitarray_free(aInfo);
	bitarray_free(aRecv);
	return q;
}
/****************************************************************************
 *	使用例
 ****************************************************************************/
#if 0
//■JIS X 0510:2004｢二次元ｺｰﾄﾞｼﾝﾎﾞﾙ-QRｺｰﾄﾞ-基本仕様｣
//│p.65｢附属書C(規定)形式情報｣の<例>をｴﾝｺｰﾄﾞ,ﾃﾞｺｰﾄﾞした例を示す:
void TestBCH(){
  ST_GaloisField* pGF;
  ST_BCH* pBCH;
  int i,t;
  int src[( 5+31)/32];
  int dst[(15+31)/32];
  //--- 準備 ---
  pGF=GaloisField_New(0x13);//原始多項式を指定してｶﾞﾛｱ体を生成する｡
  pBCH=BCH_New(pGF,3);//訂正可能符号語数を指定してBCH符号化復号化器を作成する｡
  printf("(%d,%d)BCH符号\n",pBCH->n,pBCH->k);//(15,5)BCH符号
  //--- 送信 ---
  bitarray_lsb1st_set(src,0,1,1);//┬情報符号語=00101
  bitarray_lsb1st_set(src,2,1,1);//┘
  printf("情報符号語=");
  for(i=(pBCH->k-1);i>=0;i--){
    t=bitarray_lsb1st_get(src,i,1);
    printf("%d",t);//─情報符号語=00101
  }
  printf("\n");
  BCH_Encode(pBCH,src,dst);//5ﾋﾞｯﾄの情報符号語をｴﾝｺｰﾄﾞし､15ﾋﾞｯﾄの送信符号語を作成する｡
  printf("送信符号語=");
  for(i=(pBCH->n-1);i>=0;i--){
    t=bitarray_lsb1st_get(dst,i,1);
    printf("%d",t);//─送信符号語=001010011011100
  }
  printf("\n");
  //--- 受信 ---
  i= 0;bitarray_lsb1st_set(dst,i,1,bitarray_lsb1st_get(dst,i,1)^1);//誤り1
  i= 5;bitarray_lsb1st_set(dst,i,1,bitarray_lsb1st_get(dst,i,1)^1);//誤り2
  i=10;bitarray_lsb1st_set(dst,i,1,bitarray_lsb1st_get(dst,i,1)^1);//誤り3
  printf("受信符号語=");
  for(i=(pBCH->n-1);i>=0;i--){
    t=bitarray_lsb1st_get(dst,i,1);
    printf("%d",t);//─受信符号語=001000011111101
  }
  printf("\n");
  t=BCH_Decode(pBCH,dst,src);//15ﾋﾞｯﾄの受信符号語をﾃﾞｺｰﾄﾞし､5ﾋﾞｯﾄの情報符号語を作成する｡
  printf("誤り個数=%d\n",t);//誤り個数=3
  printf("情報符号語=");
  for(i=(pBCH->k-1);i>=0;i--){
    t=bitarray_lsb1st_get(src,i,1);
    printf("%d",t);//─情報符号語=00101
  }
  printf("\n");
  //--- 開放 ---
  BCH_Free(pBCH);//BCH符号化復号化器を開放する｡
  GaloisField_Free(pGF);//ｶﾞﾛｱ体を開放する｡
}
/*--------------------------------------------------------------------------*/
//■JIS X 0510:2004｢二次元ｺｰﾄﾞｼﾝﾎﾞﾙ-QRｺｰﾄﾞ-基本仕様｣
//│p.73｢附属書G(参考)ｼﾝﾎﾞﾙの符号化例｣の<手順1,2>をｴﾝｺｰﾄﾞ,ﾃﾞｺｰﾄﾞした例を示す:
void TestRS(){
  ST_GaloisField* pGF;
  ST_ReedSolomon* pRS;
  int i,t;
  int src[(8*16+31)/32];
  int dst[(8*26+31)/32];
  //--- 準備 ---
  pGF=GaloisField_New(0x11D);//原始多項式を指定してｶﾞﾛｱ体を生成する｡
  pRS=ReedSolomon_New(pGF,5);//訂正可能符号語数を指定してRS符号化復号化器を作成する｡
  printf("(%d,%d)RS符号\n",26,(26-pRS->m));//(26,16)RS符号
  //--- 送信 ---
  src[3]=BIN32(00010000,00100000,00001100,01010110);
  src[2]=BIN32(01100001,10000000,11101100,00010001);
  src[1]=BIN32(11101100,00010001,11101100,00010001);
  src[0]=BIN32(11101100,00010001,11101100,00010001);
  printf("情報符号語=");
  for(i=(8*16-8);i>=0;i-=8){
    t=bitarray_lsb1st_get(src,i,8);
    printf("%02X ",t);//─情報符号語=10 20 0C 56 61 80 EC 11 EC 11 EC 11 EC 11 EC 11
  }
  printf("\n");
  ReedSolomon_EncodeN(pRS,src,dst,26);//16ﾊﾞｲﾄの情報符号語をｴﾝｺｰﾄﾞし､26ﾊﾞｲﾄの送信符号語を作成する｡
  printf("送信符号語=");
  for(i=(8*26-8);i>=0;i-=8){
    t=bitarray_lsb1st_get(dst,i,8);
    printf("%02X ",t);//─送信符号語=10 20 0C 56 61 80 EC 11 EC 11 EC 11 EC 11 EC 11 A5 24 D4 C1 ED 36 C7 87 2C 55
  }
  printf("\n");
  //--- 受信 ---
  i=8* 3;bitarray_lsb1st_set(dst,i,8,bitarray_lsb1st_get(dst,i,8)^0x11);//誤り1
  i=8* 8;bitarray_lsb1st_set(dst,i,8,bitarray_lsb1st_get(dst,i,8)^0x22);//誤り2
  i=8*13;bitarray_lsb1st_set(dst,i,8,bitarray_lsb1st_get(dst,i,8)^0x33);//誤り3
  i=8*18;bitarray_lsb1st_set(dst,i,8,bitarray_lsb1st_get(dst,i,8)^0x44);//誤り2
  i=8*23;bitarray_lsb1st_set(dst,i,8,bitarray_lsb1st_get(dst,i,8)^0x55);//誤り3
  printf("受信符号語=");
  for(i=(8*26-8);i>=0;i-=8){
    t=bitarray_lsb1st_get(dst,i,8);
    printf("%02X ",t);//─受信符号語=10 20 59 56 61 80 EC 55 EC 11 EC 11 DF 11 EC 11 A5 06 D4 C1 ED 36 D6 87 2C 55
  }
  printf("\n");
  t=ReedSolomon_DecodeN(pRS,dst,src,26);//26ﾊﾞｲﾄの受信符号語をﾃﾞｺｰﾄﾞし､16ﾊﾞｲﾄの情報符号語を作成する｡
  printf("誤り個数=%d\n",t);//誤り個数=5
  printf("情報符号語=");
  for(i=(8*16-8);i>=0;i-=8){
    t=bitarray_lsb1st_get(src,i,8);
    printf("%02X ",t);//─情報符号語=10 20 0C 56 61 80 EC 11 EC 11 EC 11 EC 11 EC 11
  }
  printf("\n");
  //--- 開放 ---
  ReedSolomon_Free(pRS);//RS符号化復号化器を開放する｡
  GaloisField_Free(pGF);//ｶﾞﾛｱ体を開放する｡
}
#endif
