AlgorithmCalculateParity.hpp ファイル

可約ジェネレータのパリティチェックベクトルを求める。 [詳解]

#include <stdint.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <iostream>
#include <inttypes.h>
#include <NTL/GF2X.h>
#include <NTL/vec_GF2.h>
#include <NTL/mat_GF2.h>
#include <MTToolBox/ReducibleGenerator.hpp>
#include <MTToolBox/util.hpp>

[ソースコード]

データ構造
class	MTToolBox::AlgorithmCalculateParity< U, G >
	可約ジェネレータのパリティチェックベクトルを求める。 [詳解]

名前空間
	MTToolBox
	MTToolBox の名前空間

詳解

可約ジェネレータのパリティチェックベクトルを求める。

状態遷移関数の特性多項式 h を f * q という多項式の積で表すことができて、 かつ f の次数が状態空間が許す限り大きなメルセンヌ指数である場合、状 態遷移の周期が2^(deg(f))-1のゼロでない倍数となるように保証するような ベクトルを求めることができる。ケーリー・ハミルトンの式によって、hは 状態空間をannihilateするが、f, q も状態空間の部分空間をannihilateす る。このクラスでは、q によってannihilateされる部分空間の基底を求める ことによって、周期保証ベクトル（パリティベクトル）を求める。

状態空間の一部をパリティチェック用の部分空間Pとする。この空間のサイ ズは状態空間を表す配列の要素のサイズになるようにする。典型的には32ビッ トまたは64ビットである。状態空間からパリティチェック用の空間への射影 をPrとする。qのカーネルの基底を具体的に計算して、求めておく(Ker_q)。 Pr(Ker_q)はPの部分空間の基底になるので、PにおけるPr(Ker_q)の直交補空 間の基底を計算する。その基底からひとつのベクトルを取り出してパリティ チェックベクトルとする。

初期化後に、Pのビット列を取り出してパリティチェックベクトルとの内積 を計算する。内積が1ならば、Pr(Ker_q)に入っていないので、Ker_qにも入っ ていない。状態空間はKer_q と Ker_f の直和なので、Ker_q に入っていな ければ、Ker_f のベクトルを和の一部として含む。これにより周期が保証さ れる。内積が0の場合は、Ker_q に入っているかも知れないし、入っていな いかも知れないが、1ビット変更して内積が1になるように変更すれば周期が 保証できる。

著者

Mutsuo Saito (Manieth Corp.)

Makoto Matsumoto (Hiroshima University)

Copyright (C) 2015, 2016 Mutsuo Saito, Makoto Matsumoto, Manieth Corp. and Hiroshima University. All rights reserved.

The 3-clause BSD License is applied to this software, see LICENSE.txt