問題タブ [galois-field]

非常に限られた組み込みプラットフォームで QR コードを生成しようとしています。エラー訂正コードワードの生成を除いて、仕様のすべてがかなり単純に見えます。私は多くの既存の実装を見てきましたが、それらはすべて、特にガロア体に関して、私の頭を真っ直ぐに進む多項式数学の束を実装しようとしています。数学的複雑さとメモリ要件の両方で、私が見ることができる最も簡単な方法は、仕様自体にレイアウトされている回路の概念です。

それらの説明により、GF(256) 加算と GF(256) 乗算とラベル付けされた部分を除いて、これを実装できると確信しています。

彼らはこの助けを提供します：

QR コードの多項式演算は、ビット単位のモジュロ 2 演算とバイト単位のモジュロ 100011101 演算を使用して計算されます。これは 2^8 のガロア体で、100011101 は体の素数モジュラス多項式 x^8+x^4+x^3+x^2+1 を表します。

これは私にとってほとんどギリシャ語です。

だから私の質問はこれです:この種のガロア体演算で加算と乗算を実行する最も簡単な方法は何ですか? 両方の入力数値が 8 ビット幅で、出力も 8 ビット幅である必要があるとします。いくつかの実装では、これを支援するために 2 つのルックアップ テーブルで事前計算またはハードコーディングされていますが、それらがどのように計算されるか、またはこの状況でどのように使用されるかはわかりません。2 つのテーブルで 512 バイトのメモリ ヒットは避けたいと思いますが、実際には代替手段が何であるかによって異なります。この回路で単一の乗算と加算演算を行う方法を理解するのに本当に助けが必要です。

ブロックの乗算 (アルゴリズム 1) の C コードを GCM SP-800-38D のドキュメントに掲載しています。11-12ページ。

コードを完成させたので、コードをテストできる方法があるかどうかを確認したいと思います。私が提示したコードの下に添付されています。128 ビット ブロックの代わりに、テスト目的のためだけに 24 ビット ブロックを使用したことに注意してください。必要に応じて提案をいただければ幸いです。

計算できるようになりたい

ここで、gは有限体GF（2 ^ m）にあります。ここで、mはかなり大きく、m = 256、384、512などであるため、ルックアップテーブルは解決策ではありません。同様のアイデア、Z / nZ用のmodpow（ HACの619〜620ページを参照）には非常に高速なアルゴリズムがあることを私は知っています。

1. サイクル（つまりg ^ x）を計算するための高速で非テーブルベースの方法は何ですか？
2. これは間違いなく希望に満ちた質問ですが、ここに来ます。モンゴメリの乗算/べき乗のアイデアをガロア体に「リサイクル」できるでしょうか。同型性があるのでそう思いたいのですが、よくわかりません。

備考：これはmath.stackoverflow.comへの私の投稿からのものです。これがこの質問をするのに最適なコミュニティだと思います。

Matlab には、10 進数と有限体数を含む行列のランクを計算するための組み込み関数があります。ただし、私が間違っていなければ、最低ランク (行ランクと列ランクの最小) のみを計算します。行ランクのみを計算したい、つまり、行列の独立した行の数を見つけたい（私の場合は有限フィールド）。これを行う機能または方法はありますか？

C++でのガロア体演算の実装を知っていますか? 少なくとも GF(2 ¹⁶ ) と GF(2 ³² ) のようなケースをカバーする必要があります。パフォーマンスが懸念されるため、実装では操作の最適化を検討する必要があります。

一般的な計算ライブラリか、このタスク専用の小さなライブラリの方がいいと思います。これらが不足しているため、読み取り可能なソース コードも歓迎します。

vbaでQRコードを生成する関数に取り組んでいます。私はこのチュートリアルに従っています。私は現在、このステップで誤り訂正語を生成する作業を行っています。これには GF(256) ログ/アンチログ テーブルが必要です。こちらを参照してください。テーブル全体を入力する必要はありません。これらのテーブルを生成するために使用される関数を誰かが知っているので、それらを配列に格納できますか? チュートリアルには、テーブルの生成方法へのリンクがありましたが、壊れていました。

先に言っておきますが、これはアクセスで実行するので、エクセルへの貼り付けがうまくいきません。しかし、これを書いているときに、アクセス テーブルを使用できることに気づきました。私はそれをすべてコードで行うことを好みますが。

ガロア LFSR コードがどのように機能するかを理解しようとしています。ウィキペディアのページには、例の図があります。C スニペット コードがあります。

ウィキペディアに記載されている図を理解できず、コードと関連付けることができません。トグルマスクは何をしていますか？ビットシーケンスの例とそれがシフトされたバージョンで操作がどのように機能しているかについて、誰でも説明できますか。私はフィールドを認識しておらず、コードを理解していません。私はオンラインでチェックしましたが、フィールドの用語を使わずにアルゴリズムの適切な説明を見つけることができませんでした. 親切に助けてください。

ガロア体 (GF4) で numpy 配列を使用したい。そこで、GF4 クラスを配列要素に設定しました。配列 + 整数計算では機能しますが、配列 + 配列計算では機能しません。

ただし、配列および配列 * 整数の計算でも機能します。

次のコードをどのように修正すればよいですか? クラスGF4を使いたいです。

GF(2) 有限体の多項式を読み取ろうとしていますが、これは基本的に係数または定数に対して 1 または 0 のみであり、多項式の 1 つの部分を他の部分と実際に区別する唯一の数値は指数です。しかし、指数は、結果のリスト内の場所の「場所」またはインデックスのみをマークすることになり、1 としてのみマークされます。結果のリスト内の他のすべての位置は 0 です。

例を含むいくつかのコード:

ご覧のとおり、次のように出力されます。

ただし、リストの先頭に 1 を出力する必要があります (多項式の次数は左から右に高から低になり、リストも同様です)。それが最高度なので、長さは正しいです。私は今、独学で Python を学んでいるので、プロの Python 関係者は私のコードにうんざりしていると思います。プロの方には、初心者の習慣をできるだけ早く取り除こうとしているので、より Pythonic な解決策や建設的な何かを提案してください。後でこれを関数に入れます (実際には、クラス内の関数に入ります)。これは、基本的な考え方を理解するためのものです。

編集：

以下の回答から（コードの一部だけのアイデアを信用していません）、Pythonicのように見えますが、正規表現を使用して抽出してintに変換するコードを最適に統合する方法がわかりません（cリスト内） ):

このコードを合理化し、より Pythonic にする方法を考えています。