※ 配列宣言のサイズの間違えを指摘されましたので修正します。
プログラム言語の文法は決まっていて、また自分が作りたいものの仕様が見えていれば、きちっと作れば一発で動くはずなのですが、私の場合はどうしてもカットアンドトライ状態から抜けられなくて、バグったらそこで考えるという悪い習慣から抜けられないでいます。特にループ条件とか配列の数や方向などは適当で、エラーメッセージや結果が合わないことに気が付いてから見直すことしばしです。
こういう習慣は絶対によろしくないので、特に若い人は真似しないようにしましょう。自戒を込めて。
Excel:「実感がこもっていますねぇ~」
scilab:「今まで何度やり直しをさせられたか...」
LTspice:「オレはもう諦めている。こいつのキャラ直んねぇ~」
さて、前回はガロア体での掛け算 / 割り算をやってみました。
C 言語としては宣言、ループ、判定、配列などをやって見たことになるので、低レベルながらも演習してみた、という感じです。今回は自前の関数を作ってそれを使う、という演習も兼ねてリードソロモン符号を付けてみます。
元記事は以下のようです。
誤り訂正符号の付け方の実際(リードソロモン符号)
http://blogs.yahoo.co.jp/susanoo2001_hero/11193398.html
ここでは、上の記事と同じことをプログラムでやってみることにします。
自前の関数として、ガロア体内での積演算を行う product を作りました。積演算に使う配列は前回作成したものがそのまま使われています。
#include <stdio.h>
int alpha[256];
int ialpha[256];
int product(int, int);
int main(void)
{
int i,j;
alpha[0] = 1;
alpha[255] = 0;
ialpha[0] = 255;
/* べき乗 → 数値変換配列の作成 */
for (i = 0;i <=254;i++)
{
alpha[i+1] = alpha[i] * 2;
if (alpha[i+1] >= 256)
{
alpha[i+1] = alpha[i+1] - 256;
alpha[i+1] = alpha[i+1] ^ 0x1d; /* α^8 = α^4 + α^3 + α^2 + 1 を計算 */
}
}
/* 数値 → べき乗変換配列の作成 */
for (i = 1; i <=254; i++)
{
for (j = 0; j <=254; j++)
{
if (alpha[j] == i)
{
ialpha[i] = j;
}
}
}
/* 4 バイトの訂正符号を付加する場合の生成多項式の算出 G(X) = X^4 + α^75・X^3 + α^249・X^2 + α^78・X + α^6 */
int poly1[5], poly2[2], value1, value2;
poly1[0]=1;
poly1[1]=1;/* x + 1 */
poly1[2]=0;
poly1[3]=0;
poly1[4]=0;
poly2[0]=2;
poly2[1]=1;/* x + α */
for (i = 0; i <=2; i++)
{
value1 = product(poly1[4], poly2[0]);
value2 = product(poly1[3], poly2[1]);
poly1[4] = value1 ^ value2;
value1 = product(poly1[3], poly2[0]);
value2 = product(poly1[2], poly2[1]);
poly1[3] = value1 ^ value2;
value1 = product(poly1[2], poly2[0]);
value2 = product(poly1[1], poly2[1]);
poly1[2] = value1 ^ value2;
value1 = product(poly1[1], poly2[0]);
value2 = product(poly1[0], poly2[1]);
poly1[1] = value1 ^ value2;
value1 = product(poly1[0] , poly2[0] );
poly1[0] = value1;
poly2[0] = alpha[ialpha[poly2[0]] +1];
}
for (i = 4; i >=1; i--)
{
printf("a^%d・X^%d + ",ialpha[poly1[i]],i);
}
printf("a^%d\n", ialpha[poly1[0]]);
for (i = 4; i >=1; i--)
{
printf("0x%02x・X^%d + ",poly1[i],i);
}
printf("0x%02x\n", poly1[0]);
/* リードソロモン符号の生成 */
int Dx[10] = {0, 0, 0, 0, 0x2d, 0x1f, 0xbc, 0x74, 0x15, 0x3c};/* 元データ配列 */
int Tx[10] = {0, 0, 0, 0, 0x2d, 0x1f, 0xbc, 0x74, 0x15, 0x3c};/* 送信データ配列(訂正コード付加前)*/
int coef[4];
/* シフトレジスタによる割り算 ~ 訂正コード生成 */
for (i = 1; i <= 6; i++)
{
coef[3] = product(Dx[9], poly1[3]);
coef[2] = product(Dx[9], poly1[2]);
coef[1] = product(Dx[9], poly1[1]);
coef[0] = product(Dx[9], poly1[0]);
Dx[9] = Dx[8] ^ coef[3];
Dx[8] = Dx[7] ^ coef[2];
Dx[7] = Dx[6] ^ coef[1];
Dx[6] = Dx[5] ^ coef[0];
Dx[5] = Dx[4];
Dx[4] = Dx[3];
Dx[3] = Dx[2];
Dx[2] = Dx[1];
Dx[1] = Dx[0];
Dx[0] = 0;
}
/* 訂正コード付加 */
Tx[0] = Dx[6];
Tx[1] = Dx[7];
Tx[2] = Dx[8];
Tx[3] = Dx[9];
/* 送信データ表示 */
printf("Tx = ");
for (i = 0; i <=9; i++)
{
printf("%02x, ", Tx[i]);
}
printf("\n");
return 0;
}
int product(int a, int b) /* 積演算関数 */
{
int c;
if (a * b == 0) c = 0;
else c = alpha[(ialpha[a] + ialpha[b]) % 255];
return c;
}
元々のデータ列も同じで、上位と下位がひっくり返ってしまっていますが、結果は以下のようになります。
a^0・X^4 + a^75・X^3 + a^249・X^2 + a^78・X^1 + a^6
0x01・X^4 + 0x0f・X^3 + 0x36・X^2 + 0x78・X^1 + 0x40
Tx = 03, bf, 5f, 30, 2d, 1f, bc, 74, 15, 3c,
続行するには何かキーを押してください . . .
手計算の記事と同じ結果になりました。多分大丈夫でしょう。多項式の掛け算をもう少しスマートにならないかとは思うのですが、まだ知識も技術も足りないようです。
なお、上記結果の前半の 2 行は G(X) です。単にα表示と 16 進表示の両方を出してあるだけです。
実際に組み込みソフトウェアではこんな計算はやらないと思いますが、少しは経験になったかなというところでしょうか。ハードウェアを制御したり、I / F で通信したりするにはそれなりの準備が必要なので、C 言語演習関連および誤り訂正はこの程度にしておくことにします。
← にほんブログ村「科学」-「技術・工学」へ
↑ クリックをお願いします。
プログラム言語の文法は決まっていて、また自分が作りたいものの仕様が見えていれば、きちっと作れば一発で動くはずなのですが、私の場合はどうしてもカットアンドトライ状態から抜けられなくて、バグったらそこで考えるという悪い習慣から抜けられないでいます。特にループ条件とか配列の数や方向などは適当で、エラーメッセージや結果が合わないことに気が付いてから見直すことしばしです。
こういう習慣は絶対によろしくないので、特に若い人は真似しないようにしましょう。自戒を込めて。
Excel:「実感がこもっていますねぇ~」
scilab:「今まで何度やり直しをさせられたか...」
LTspice:「オレはもう諦めている。こいつのキャラ直んねぇ~」
さて、前回はガロア体での掛け算 / 割り算をやってみました。
C 言語としては宣言、ループ、判定、配列などをやって見たことになるので、低レベルながらも演習してみた、という感じです。今回は自前の関数を作ってそれを使う、という演習も兼ねてリードソロモン符号を付けてみます。
元記事は以下のようです。
誤り訂正符号の付け方の実際(リードソロモン符号)
http://blogs.yahoo.co.jp/susanoo2001_hero/11193398.html
ここでは、上の記事と同じことをプログラムでやってみることにします。
自前の関数として、ガロア体内での積演算を行う product を作りました。積演算に使う配列は前回作成したものがそのまま使われています。
#include <stdio.h>
int alpha[256];
int ialpha[256];
int product(int, int);
int main(void)
{
int i,j;
alpha[0] = 1;
alpha[255] = 0;
ialpha[0] = 255;
/* べき乗 → 数値変換配列の作成 */
for (i = 0;i <=254;i++)
{
alpha[i+1] = alpha[i] * 2;
if (alpha[i+1] >= 256)
{
alpha[i+1] = alpha[i+1] - 256;
alpha[i+1] = alpha[i+1] ^ 0x1d; /* α^8 = α^4 + α^3 + α^2 + 1 を計算 */
}
}
/* 数値 → べき乗変換配列の作成 */
for (i = 1; i <=254; i++)
{
for (j = 0; j <=254; j++)
{
if (alpha[j] == i)
{
ialpha[i] = j;
}
}
}
/* 4 バイトの訂正符号を付加する場合の生成多項式の算出 G(X) = X^4 + α^75・X^3 + α^249・X^2 + α^78・X + α^6 */
int poly1[5], poly2[2], value1, value2;
poly1[0]=1;
poly1[1]=1;/* x + 1 */
poly1[2]=0;
poly1[3]=0;
poly1[4]=0;
poly2[0]=2;
poly2[1]=1;/* x + α */
for (i = 0; i <=2; i++)
{
value1 = product(poly1[4], poly2[0]);
value2 = product(poly1[3], poly2[1]);
poly1[4] = value1 ^ value2;
value1 = product(poly1[3], poly2[0]);
value2 = product(poly1[2], poly2[1]);
poly1[3] = value1 ^ value2;
value1 = product(poly1[2], poly2[0]);
value2 = product(poly1[1], poly2[1]);
poly1[2] = value1 ^ value2;
value1 = product(poly1[1], poly2[0]);
value2 = product(poly1[0], poly2[1]);
poly1[1] = value1 ^ value2;
value1 = product(poly1[0] , poly2[0] );
poly1[0] = value1;
poly2[0] = alpha[ialpha[poly2[0]] +1];
}
for (i = 4; i >=1; i--)
{
printf("a^%d・X^%d + ",ialpha[poly1[i]],i);
}
printf("a^%d\n", ialpha[poly1[0]]);
for (i = 4; i >=1; i--)
{
printf("0x%02x・X^%d + ",poly1[i],i);
}
printf("0x%02x\n", poly1[0]);
/* リードソロモン符号の生成 */
int Dx[10] = {0, 0, 0, 0, 0x2d, 0x1f, 0xbc, 0x74, 0x15, 0x3c};/* 元データ配列 */
int Tx[10] = {0, 0, 0, 0, 0x2d, 0x1f, 0xbc, 0x74, 0x15, 0x3c};/* 送信データ配列(訂正コード付加前)*/
int coef[4];
/* シフトレジスタによる割り算 ~ 訂正コード生成 */
for (i = 1; i <= 6; i++)
{
coef[3] = product(Dx[9], poly1[3]);
coef[2] = product(Dx[9], poly1[2]);
coef[1] = product(Dx[9], poly1[1]);
coef[0] = product(Dx[9], poly1[0]);
Dx[9] = Dx[8] ^ coef[3];
Dx[8] = Dx[7] ^ coef[2];
Dx[7] = Dx[6] ^ coef[1];
Dx[6] = Dx[5] ^ coef[0];
Dx[5] = Dx[4];
Dx[4] = Dx[3];
Dx[3] = Dx[2];
Dx[2] = Dx[1];
Dx[1] = Dx[0];
Dx[0] = 0;
}
/* 訂正コード付加 */
Tx[0] = Dx[6];
Tx[1] = Dx[7];
Tx[2] = Dx[8];
Tx[3] = Dx[9];
/* 送信データ表示 */
printf("Tx = ");
for (i = 0; i <=9; i++)
{
printf("%02x, ", Tx[i]);
}
printf("\n");
return 0;
}
int product(int a, int b) /* 積演算関数 */
{
int c;
if (a * b == 0) c = 0;
else c = alpha[(ialpha[a] + ialpha[b]) % 255];
return c;
}
元々のデータ列も同じで、上位と下位がひっくり返ってしまっていますが、結果は以下のようになります。
a^0・X^4 + a^75・X^3 + a^249・X^2 + a^78・X^1 + a^6
0x01・X^4 + 0x0f・X^3 + 0x36・X^2 + 0x78・X^1 + 0x40
Tx = 03, bf, 5f, 30, 2d, 1f, bc, 74, 15, 3c,
続行するには何かキーを押してください . . .
手計算の記事と同じ結果になりました。多分大丈夫でしょう。多項式の掛け算をもう少しスマートにならないかとは思うのですが、まだ知識も技術も足りないようです。
なお、上記結果の前半の 2 行は G(X) です。単にα表示と 16 進表示の両方を出してあるだけです。
実際に組み込みソフトウェアではこんな計算はやらないと思いますが、少しは経験になったかなというところでしょうか。ハードウェアを制御したり、I / F で通信したりするにはそれなりの準備が必要なので、C 言語演習関連および誤り訂正はこの程度にしておくことにします。
← にほんブログ村「科学」-「技術・工学」へ
↑ クリックをお願いします。