• ベストアンサー

CRCアルゴリズムのZ/2Z上の多項式の係数列とは?

punchan_jpの回答

  • ベストアンサー
回答No.2

~上の多項式というと、~にはガロア体が入りそうですね。符号理 論の教科書を見ると、GF(2)上の多項式という表現がよく使われま すが、これの別の表現のような気がします。Z/2Z の 2 というのは、 GF(2) と関係あるかもしれません。で、それが当たっているとして… 簡単にいうと、二つの要素からなる集合で、その要素の中だけで加 減乗除が定義できるなら、その集合と演算をセットで、ガロア体 GF(2) といいます。この加減乗除において、0を表す要素と、1を表 す要素が必要ですので、GF(2) は結局0と1の集合です。乗算は普通 の演算と同じに考えればいいですが、加算に関しては 1+1=0 とい う排他的論理和を用いることになります。 GF(2)上の多項式というのは、係数がGF(2)の要素であるような多項 式です。多項式どうしの加減乗除を考えるときに、項の加減乗除が 必要ですが、それらの係数の演算を GF(2) 上の演算として行うと いう意味です。

iyokiti
質問者

お礼

早速の回答ありがとうございます。 「ガロア体」やはり符号理論の知識が必要なのですね。 どうやら「算数のドつぼ」にはまってしまったようです。 二進数の特殊な世界(排他的理論和?)がなぜ必要なのかという点も、すんなり納得できません。集合ももう一度やり直す必要ありです。 GF(2)に置き換えてくださった解説はなんとなく理解できました。 punchan_jpさんには "CRTのアルゴリズム" http://oshiete1.goo.ne.jp/kotaeru.php3?qid=33895 でもお世話になっており、重ねて御礼を申し上げます。 これからもよろしくお願い申し上げます。 ありがとうございました。

関連するQ&A

  • CRCのアルゴリズムって、どんな計算するんですか?

    こんにちはお世話になります。 私はネットワークに興味があるオジサンです。 先日、データリンク層のプロトコル群を勉強していたとき、誤り訂正でCRCが出てきました。誤り訂正ではパリティーチェックやチェックサム等は聞き覚えがありましたが、CRCは始めて見たので興味を持ち少し調べてみようと思いました。 それが間違いの元でした。 インターネットでCRCの構造を詳しく解説するサイトが少なく、その解説は難しすぎて手におえません。 数学にはめっぽう弱い私には、多項式同士の加減乗除算などは頭痛の肥やしにしかなりません。 今ではCRCが気になって勉強に集中できない状態です。 そこで、表題にもあるCRCのアルゴリズムを、何方か分かり易く教えてくださいませんか。もしくは、CRCのアルゴリズムを簡単に解説している書籍をご存知でしたら教えてください。 カテゴリー(本来は数学系?)が違うかもしれませんが、何卒よろしくお願い申し上げます。

  • CRC方式(誤り制御方式)について

    CRC方式に関する問題なのですが、通信系の資格の取得しようと勉強しているのですが、誤り制御方式のところの問題をやっていましたら、答えだけで解説がなく意味がわからなく困っています。わかります方、よろしくお願い致します。 生成多項式をG(X)=X(6)+X(4)+X(2)+1とする。 (1)伝送したいデータがD=X(5)+Xのとき、送信データS=D´+CRCを多項式で表しなさい。 (2)受信データがX(14)+X(12)+X(10)+1のとき、この受信データに誤りが含まれていないことを示しなさい。次に、伝送したいデータDを多項式で表しなさい。 ※X(5)などの()内の数字はXの5条(ジョウ)です。

  • CRC方式について

    「CRC方式において、伝送路上でビット誤りが生起しなかったと仮定する。このとき、受信符号H(X)は、生成多項式G(X)で割り切れることを証明せよ。」という課題が出たのですが、どうすれば良いか、教えていただけませんか?

  • CRC方式について

    「CRC方式において、伝送路上でビット誤りが生起しなかったと仮定する。このとき、受信符号H(X)は、生成多項式G(X)で割り切れることを証明せよ。」という課題が出たのですが、どうすれば良いでしょうか?

  • 水平垂直パリティチェックとCRC方式について

    質問させてください。 基本情報処理試験において、誤り訂正方式の一つとして ・水平垂直パリティチェック ・CRC方式 というものがあります。 水平垂直パリティチェックは、ビット列を縦横に確認してデータに誤りがないか確認する方法、 CRC方式は、生成多項式という特別な式でデータに誤りがないか確認する方法 ということはわかるのですが、 それぞれのメリットデメリットは何でしょうか? 例えば、CRC方式では水平垂直パリティチェックではできない、2ビット以上の誤り訂正ができたりするのでしょうか? どなたか回答をお願いします。

  • CRCについて

    CRCの算出についてなのですが http://www2c.biglobe.ne.jp/~osakana/vc/pc/crc.html こちらのサイトを参考にすると 1. データを一つ(1バイト)とってきます 2. CRC値を左ビットシフトして、桁上がりがあればさらに生成多項式とXORを取ります 3. データを左ビットシフトして、桁上がりがあればCRC値と1のXORを取ります 4. あと7回(1バイト=8ビットなので)2と3を繰り返します 5. 残りのデータがあれば1に戻ります とあります。 例えばアドレス部00000000にデータ01が入っているもの(ファイルサイズ1バイト)を算出しようとした場合 手計算を行うとCRC16は0001、CRC32は00000001になりそうなのですが いくつかのフリーソフトで実際にバイナリエディタを用いて1バイトのファイルを作成し、試して見たところ CRC16が1E0E CRC32がA505DF1B と出ます。 一般的な算出方法では、上記の説明以外に何か別の処理、初期値などがあるのでしょうか? お分かりになる方是非教えてください。 よろしくお願いします。

  • CRCによる誤り検出の条件

    現在、CRCについて学んでいます。 その中で、誤り検出が可能な条件として、 誤りの多項式E(X)が生成多項式G(X)で割り切れないこと というのがあると思います。 そこで例えば、rビットのバースト誤りの際に、 E(X) = x^(i) + x^(i+1) + … + x^(i+r-1) = x^i * {1 + x + … + x^(r-1)} (ただ、この最後の式でx~x^(r-2)までは、誤りによってあったりなかったりする筈です) と表すことが出来て、生成多項式G(X)の次数がrであるとき、 1. x^iは(G(X)が2項以上の多項式であるなら)G(X)で割り切れない 2. {1 + x + … + x^(r-1)}は(次数がr-1であるから)G(X)で割り切れない 3. 従ってE(X)もG(X)で割り切れない よって生成多項式の次数がrの場合、rビット以下のバースト誤りは検出できるとなっていますが、、、 いくら1.や2.がG(X)で割り切れなくても、それらの積(=E(X))がG(X)で割り切れてしまうことはあるじゃないですか。 具体的には、i=1のとき、もしG(X)がx * {1 + x + … + x^(r-1)}であれば、割り切れますし、、、 同様の話で、 http://laputa.cs.shinshu-u.ac.jp/~yizawa/InfSys1/advanced/crc/ こちらのページの、「4. 巡回符号の誤り検出」という部分でも、 「これらは、3次の生成多項式、例えば G(x) = x^3+x+1 で割り切れないことは明らかです。」 という記述に対して、「例えばG(X) = x^3+x^2+x^1であれば割り切れてしまうのでは」と反論したくなります。 もちろん、割り切れないようなG(X)を選べばいいと言われればそれまでですが、、、以上の様にG(X)の内容によっては「G(X)の次数r以下のバースト誤りが検出できる」のが自明とは思えません。 そもそもそれが答え、、、? どなたかご説明お願いしますm(_ _)m

  • CRC8 ATMの計算方法

    CRC8 ATMの演算を行うツールの検証を行っているのですが、 CRCの机上計算方法を詳しく解説したサイトが無く生成多項式で 割って余りを求めると言う事しかわかりませんでした。 CRCを求める際はCRCの初期値も重要な筈ですが、CRCの初期値は 余りを求める際にどの様に使うのかを開設した物がなく、私に 検証を依頼してきた人に聞いてもまともな回答をもらえません でした(検証を依頼してきた人もちゃんと理解していない?)。 このサイトの別の質問の回答で 1. 与えられたデータの下位 (ビット送りの反対側) に「初期値」   を付加する 2. 生成多項式で割って余りを求める とあったので、その通りに計算しましたが初期値が0x00の時は ツールと机上計算の結果が一致するのですが、初期値0xFFの時は ツールと机上計算の結果が一致しませんでした。 実際の計算過程と結果は下記です。 生成多項式:x8+x2+x1+1(9'b100000111) 入力データ:0x12345678 CRC初期値:0x00 データ左送り、入出力反転なし 机上計算 初期値:0001001000110100010101100111100000000000(0x1234567800) 100000111 ---------------------------------------- 0001001000100010101100111100000000000 100000111 ---------------------------------------- 0001001010010101100111100000000000 100000111 ---------------------------------------- 0001011100101100111100000000000 100000111 ---------------------------------------- 0011101011100111100000000000 100000111 ---------------------------------------- 01101000000111100000000000 100000111 ---------------------------------------- 0101001110111100000000000 100000111 ---------------------------------------- 001001001111100000000000 100000111 ---------------------------------------- 0001000001100000000000 100000111 ---------------------------------------- 0000000010000000000 100000111 ---------------------------------------- 00000011100 なのでCRC(余り)は0x1C(00011100)でツールの結果0x1Cと一致。 CRC初期値:0xFF 机上計算 初期値:0001001000110100010101100111100011111111(0x12345678FF) 100000111 ---------------------------------------- 0001001000100010101100111100011111111 100000111 ---------------------------------------- 0001001010010101100111100011111111 100000111 ---------------------------------------- 0001011100101100111100011111111 100000111 ---------------------------------------- 0011101011100111100011111111 100000111 ---------------------------------------- 01101000000111100011111111 100000111 ---------------------------------------- 0101001110111100011111111 100000111 ---------------------------------------- 001001001111100011111111 100000111 ---------------------------------------- 0001000001100011111111 100000111 ---------------------------------------- 0000000010011111111 100000111 ---------------------------------------- 00011100011 なのでCRC(余り)は0xE3(11100011)でツールの結果0xCDと不一致 となりました。 これは計算の仕方が間違っているのでしょうか? それともツールの結果が間違っているのでしょうか? 何方かCRCの計算に詳しい人、ご回答をお願いします。

  • CRCの検定コードがどの文字でも同じになった!?

    C言語の初級者が質問します。 講義の課題で、「伝送誤り検出方式として巡回符号方式(CRC:Cyclic Redundancy Check)を使用した場合、送り側でアルファベット6文字の適当な単語を1文字ずつ入力した場合の検定コードを算出しなさい。生成多項式はCRC-16-CCITT(Xの16乗)+(Xの12乗)+(Xの5乗)+1を使用し、検定コードは2byteとする。 この課題に対し、一文字ずつ、検定コードを求めて合計6個の和を出して16進数で表現しようと考え、以下のプログラムを作りました。#include <stdio.h> #include <string.h> #include <stdlib.h> int main () { int t,s,i,m; int l; int flag; int crcReg[10]; // crcRegは一文字ごとのCRCの計算途中過程 res[]は一文字ごとのCRCの最終結果 char inData[6]; //文字列入力 int jyuroku[6]; int crcmax; printf("文字入力(6文字まで):"); gets(inData); // l=strlen(inData); for(i = 0;i < l; i++) { printf("%d番目は16進数で%X\n",i+1,inData[i]); // } printf("各文字の16進asciiは(0x必要か?)"); for(m = 0;m <l;m++) { printf("%d番目のascii:",m+1); scanf("%X", &jyuroku[m]); // } //**********************************(後半)********************************************** for(s=0;s < l; s++) {//文字の数だけ繰り返し crcReg[s]=0xFFFF; //CRCの初期値はどの文字の場合でも同じ printf("%d 番目の16進ascii:%X\n",s+1,jyuroku[s]); // for (t = 0;t < 8; t++) { //入力する16進数は8ビット=1バイト ゆえ8回繰り返し flag = (crcReg[s] ^ jyuroku[s] & 0x01); // 生成多項式をかけるかどうかの判定の前段階 crcReg[s] = crcReg[s] >> 1; //CRCの計算過程を1ビット右にシフト if (flag == 0x01) { //最下位ビットflagが1の時の処理 crcReg[s] = (crcReg[s] ^ 0x8408); //生成多項式は10進数で } else if (flag == 0x00) { } jyuroku[s] = jyuroku[s] >> 1; // asciiコードも1 ビットシフト } printf("CRCの結果は%X\n",crcReg[s]); // } crcmax = crcReg[0]+crcReg[1]+crcReg[2]+crcReg[3]+crcReg[4]+crcReg[5]; printf("\n kekka:%d",crcmax); // return 0; // } しかし、こうするとcrcReg[s](検定コード)がどの文字の場合でも同じ255(16進数ではFF)になって、6文字の単語は常に和が1530になってしまいます。255=16の2乗-1であることが問題解決の鍵だと思うのですが、何か問題点わかりますか?

  • BCH誤り訂正

    BCH誤り訂正なんですが 受信した符号を多項式で割ってあまりから誤りビットがでるのですが 訂正能力を超えた場合はどうでしょうか? 例えば2ビットまで訂正できるBCHで3ビット誤った符号を受信したときは 全く異なる訂正をしてしまうと思うのですが 何か手はあるのでしょうか? 普通はBCHのあとにCRCを行うのですがBCH内で演算して誤りビット数は出せるのでしょうか?