Berlekamp-Missアルゴリズム
19433 ワード
B M BMアルゴリズム
使い道
これは、常数係数の直線的な推論係数を求めるために使用することができますが、最短で求められるものは何のためにありますか?あなたはサイレントCayley-Hamiltn定理を最適化することができます.
アルゴリズムの概要
まず、数列f f fを設定して、f n=Σi=1 m a i f n−i(n>m)f_を満たすようにしたいです.n=\sum_｛i=1｝^{m}a_if_｛n−i｝(n＞m)fn=Σi=1 mm ai fn−i(n＞m)の最小m mと、対応する係数a a aは、インクリメンタル構造を考慮して構成される.は、まずn＞m n＞mが要求されるので、m=n m=n m、aはともに0であり、明らかに条件が満たされているので、初期は全0 0 であることができる. mの長さのa aはf 1…n−1 f_であると仮定する.｛1…n−1｝f 1…n−1は条件を満たし、f n f_n fnは、設定d e l t a n=Σi=1 m f n−i a i−f n delta_を満たしていない.n=\sum_｛i=1｝^{m}f_{n-i}a_i-f_n deltan=Σi=1 m fn−i ai−fnを作成すると、m’m’m’が最も短いa’a'a’がΣi=1 m’f n−i i i i’＝−d e l t a n＞sum_{i=1}^{m'}f_{n-i}a'_i=-delta_nΣi=1 m’fn−i ai’=−deltanその後a,a’a,a’はビットで加算すればいいですが、実際にはすでにいくつかの条件を満たさない場合があります.x x x＿d＿l＿a x＝Σi＝1 m’f x−i’−i＿i＿i＿i’−f＿x delta铂x=\sum_{i=1}^{m'}f_{x-i}a'_i-f_x deltax=Σi=1 m'fx−i ai'−−−fx a'a'a'を後ろにn−x n−n−x−xビットを移動し、前にn−−−−x−1 n−−−−−−−−−x−1−0 0 0 0−1−n−n−xビットを−1−1−−1−−−−−−−1−xビットして、このようにして得られた長さは、＋n＋n−n＋n−n−n＋n−n−n＋n＋n−n−n−n−n−n−n−n−n−x＋n−n−n−n−n−n−n−x＋n−n−n−n−x＋n−n−n−x＋n−n−x{deltatux}deltax−deltaiを乗ればいいです.作ったb bは明らかに私達が要求していますが、一番短いものではないかもしれません.以前に求めたa aを全部記録して(実はその一番短い係数を記録すればいいです.)f a＿i l＿failuを作ります.i failiはi番目のi番目のa a aがかけられた位置を表しています.最後に変数を作って最短の位置を記録してください.
コード
正しいかもしれませんが、zzqのブログに行ってデータを調べてください.
使い道
これは、常数係数の直線的な推論係数を求めるために使用することができますが、最短で求められるものは何のためにありますか?あなたはサイレントCayley-Hamiltn定理を最適化することができます.
アルゴリズムの概要
まず、数列f f fを設定して、f n=Σi=1 m a i f n−i(n>m)f_を満たすようにしたいです.n=\sum_｛i=1｝^{m}a_if_｛n−i｝(n＞m)fn=Σi=1 mm ai fn−i(n＞m)の最小m mと、対応する係数a a aは、インクリメンタル構造を考慮して構成される.
コード
正しいかもしれませんが、zzqのブログに行ってデータを調べてください.
# include