13

非常に限られた組み込みプラットフォームで 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 バイトのメモリ ヒットは避けたいと思いますが、実際には代替手段が何であるかによって異なります。この回路で単一の乗算と加算演算を行う方法を理解するのに本当に助けが必要です。

4

2 に答える 2

11

実際には、必要なテーブルは 1 つだけです。それは GP(256) 乗算用です。すべての算術演算はキャリーなしであることに注意してください。つまり、キャリーの伝播はありません。

キャリーなしの加算と減算は xor と同等です。

したがって、GF(256) では、a + bとa - bはどちらも と同等a xor bです。

GF(256) 乗算もキャリーレスであり、キャリーレス加算/減算と同様の方法でキャリーレス乗算を使用して実行できます。これは、インテルの CLMUL 命令セットなどを介したハードウェア サポートにより効率的に実行できます。

ただし、難しいのは modulo を減らすこと100011101です。通常の整数除算では、一連の比較/減算ステップを使用して行います。GF(256) では、一連の比較/xor ステップを使用してほぼ同じ方法でそれを行います。

実際、すべての 256 x 256 乗算を事前に計算して 65536 エントリのルックアップ テーブルに入れる方が高速であるという点では、十分に悪いことです。

次の pdf の 3 ページには、GF256 算術に関する非常に優れたリファレンスがあります。

http://www.eecs.harvard.edu/~michaelm/CS222/eccnotes.pdf

于 2011-12-09T03:37:00.537 に答える
6

(私は著者なので、最初の回答で zxing へのポインターをフォローアップしています。)

足し算についての答えはまさに正しいです。そのため、この分野での作業はコンピューターで行うと便利です。

http://code.google.com/p/zxing/source/browse/trunk/core/src/com/google/zxing/common/reedsolomon/GenericGF.javaを参照してください。

はい、乗算が機能し、GF256 用です。a * b は実際には exp(log(a) + log(b)) と同じです。また、GF256 には 256 個の要素しかないため、"x" の一意の累乗は 255 個しかなく、対数についても同じです。したがって、これらはルックアップ テーブルに簡単に入れることができます。テーブルは 256 で「ラップ アラウンド」するため、「% サイズ」が表示されます。「/ サイズ」を文で説明するのは少し難しいです。これは、0 ～ 255 ではなく、実際には 1 ～ 255 が「ラップ アラウンド」であるためです。したがって、必要なのは単純なモジュラスだけではありません。

おそらく最後の部分は、既約多項式を法としてどのように簡約するかということです。既約多項式は x^8 にいくつかの低べき乗項を加えたものです。これを I(x) = x^8 + R(x) と呼びます。また、定義により、多項式はフィールドで 0 に合同です。I(x) == 0. だから x^8 == -R(x). そして、便利なことに、足し算と引き算は同じなので、x^8 == -R(x) == R(x) です。

高べき多項式を簡約する必要があるのは、指数テーブルを作成するときだけです。大きくなりすぎるまで x を掛け続けます (これは左シフトです)。x^8 項が得られます。ただし、x^8 は R(x) と同じです。したがって、x^8 を取り出して R(x) を追加します。R(x) は単に x^7 まで累乗するだけなので、すべて GF(256) の 1 バイトのままです。そして、このフィールドに追加する方法を知っています。

役に立ちますか？

于 2011-12-09T17:27:38.677 に答える