どういうわけか、無線チャネルを介した情報のより信頼性の高い送信を行いたかったのです。これはある種の産業プロジェクトでも、他の深刻なものでもありません。それは趣味と自己開発のためのものです。子供の頃のトラウマが影響を受けました-正常に機能する無線制御車の欠如。それ以来、私は常にラジオのあらゆるものを簡単かつ自然に制御できるようにしたいと思っていました...
そして、私は逸脱します。小児期および青年期では、エラー修正コーディングのために、マトリックス法によるパリティチェックを適用することができましたが、現在、これは深刻ではありません。インターネットを見て、リードソロモン方式でのコーディングをやめることにしました。このアルゴリズムは完全に新しいものではなく、最初のCDで使用されていましたが、同時に、私が知る限り、現時点ではその関連性を失っていません。 Reed-Solomonコード自体に関するこの記事では、あまり拡張しません。これは、Habréで何度も、多くの人によって行われたものです。ここでは、GF [256]での乗算アルゴリズムの実装について説明します。それでも、読者にリンクをジャンプさせないために
、Galoisフィールドをまったく処理しなければならない理由を簡単に説明します。
Reed-Solomon RedundantCodingはマトリックスに関するものです。エンコードとデコードにはマトリックスを使用します。これらのプロセスには、行列の乗算と逆行列を見つける操作の両方があります-除算。ここでの除算には、おおよその整数ではなく、最も現実的で正確なものが必要です。また、コンピューターの正確な除算は解決できないタスクです。1を3で除算すると、整数はゼロになり、小数点以下のトリプルは無限になりますが、誰にとっても640キロバイトで十分です。
ガロアは19世紀初頭に住んでいましたが、ほとんど住んでいませんでした（21年、一般的に彼の性格について興味深い話がありますが、今ではそうではありません）。彼の作品はデジタルコーディングに非常に役立ちました。有限ガロアフィールドは、0からnまでの数値のセットです。これらのフィールドの本質と関心は、このセットの要素に対して、操作の結果がこのフィールド自体に含まれるように、加算-乗算-減算-除算操作を定義できることです。たとえば、セット（フィールド）を考えてみましょう。
, . « » , ( « », « »). , , 256, ( ) 8, . GF[256], GF Galois Field.
. , , , , , « » ( stm32 ) - .
算術について少し。加算と減算は、前述のように、ガロアフィールドで同じ操作であり（これはベース2フィールドの場合とまったく同じです）、ビット単位のXORとして実装されます。
乗算する場合、各オペランドは多項式として表されます。これは次のように発生します。数値のバイナリ表現が取得され、合計が書き込まれます。ここで、xの累乗はバイナリ桁の数値であり、その係数は桁の値です。
例：
さらに、多項式は、多項式の乗算の規則に従って乗算されます。つまり、最初の括弧内の各項は、2番目の括弧内の各項によって乗算されますが、それだけではありませんが、係数が複数になることはできないという事実を考慮に入れてください。
GF[8], 10 : « ? 10 [0,1,2,3,4,5,6,7]». . . ( ), . , , «» . ? ? ( , , , ). , . GF[8] : 11 13, 1011 1101
, 6 3 GF[8] . . . , , - «», . . , ( ). 1. ( ). , ( GF[8] ) . 2, , 1. , ( ) ( ). , , ( – ), 1.
. GF[8] c 11.
. - 256256 ( 88, ), . , . — , . , , ( 0). , GF[8] 2,
, , 1 7 2 . , , 等々。つまり、正の累乗と簡単な式の場合、残りの7を7で割る演算を使用して、2の任意の累乗を2の0から6の累乗として表すことができます。指数が負の数の場合
実際、度数の乗算の特性を思い出すと、数値の乗算は大幅に簡略化されます。そして、6に3を掛けるために、次数2が6に等しく、次数2が3に等しいことを確認し、累乗を追加して、結果を確認します。2はある程度、0から6の累乗の例として表すことができます。
そして、これはそれであるように見えます！プログラマーの幸福は、ガロアフィールドでの算術の実装です-数行のコード、多項式を気にする必要はありません...はい、そのようなコードのパフォーマンスは高くなりますが、もう1つの問題に遭遇しました：多項式11を生成するGFフィールド[8]の2の累乗の表が見つかりました簡単に。このリソースでさえです。しかし、私はGF [256]の学位表をグーグルで調べていなかったので、自分でコンパイルすることにしました。C＃が役に立ちます。多項式の法則に従って乗算アルゴリズムを実装する必要がありました。
これは、任意の多項式を使用したGF [2 ^ n]の有効な乗算関数です。制限-私は32ビットの算術を使用するので、nは16未満でなければなりません。また、ここに、数値の最上位ビットの番号を見つける関数が追加されています。
private uint GetLeadBitNum(UInt32 Val) {
int BitNum = 31;
uint CmpVal = 1u << BitNum;
while (Val < CmpVal) {
CmpVal >>= 1;
BitNum--;
}
return (uint)BitNum;
}
private uint Galois_b2_ext_mult(uint m1, uint m2, uint Poly) {
if (0 == m1 || 0 == m2) { return 0; }
uint m1_tmp = m1;
uint m2_tmp;
uint m1_bit_num = 0;
// , 2 .
// ( ( )), ,
// , - , ,
//( - 2)
uint PolyMultRez = 0;
while (m1_tmp != 0) {
uint bit_m1 = (m1_tmp & 1u) == 0u ? 0u : 1u;
m1_tmp = m1_tmp >> 1;
m2_tmp = m2;
uint m2_bit_num;
m2_bit_num = 0;
while (m2_tmp != 0) {
uint bit_m2 = (m2_tmp & 1u) == 0u ? 0u : 1u;
m2_tmp = m2_tmp >> 1;
if ((bit_m1 != 0) && (bit_m2 != 0)) {
int BitNum = (int)(m2_bit_num + m1_bit_num);
PolyMultRez ^= 1u << BitNum;
}
m2_bit_num = m2_bit_num + 1;
}
m1_bit_num = m1_bit_num + 1;
}
// PolyMultRez. .
// : , .
// -
// , ,
// ,
uint TmpDivisor_lead_bit_n;
uint TmpQuotient;
uint TmpDivisor = Poly;
uint TmpDividend = PolyMultRez;
uint TmpDividend_LeadBitNum;
uint TmpMult_bitNum;
uint TmpMult_rez;
TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);
TmpDivisor_lead_bit_n = GetLeadBitNum(TmpDivisor);
while (TmpDividend_LeadBitNum >= TmpDivisor_lead_bit_n) {
TmpQuotient = (TmpDividend_LeadBitNum - TmpDivisor_lead_bit_n);
TmpMult_bitNum = 0;
TmpMult_rez = 0;
while (TmpDivisor != 0) {
uint bit_TmpMult = (TmpDivisor & 1u) == 0u ? 0u : 1u;
TmpDivisor >>= 1;
TmpMult_rez ^= bit_TmpMult << (int)(TmpQuotient + TmpMult_bitNum);
TmpMult_bitNum = TmpMult_bitNum + 1;
}
TmpDividend = TmpDividend ^ TmpMult_rez;
TmpDivisor = Poly;
TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);
}
// .
return TmpDividend;
}ここで、上記の関数を使用して、必要なGF [256]の2の累乗のテーブルを作成し、それぞれ256の2つのテーブルを使用してstm32のGalois算術モジュールを作成できます。1つは直接用、もう1つは数値を累乗に変換するためのものです。Reed-Solomonコーディングの実装はまだ開始していませんが、準備ができたら、ここで共有すると思います。うまくいけば、それは短くなります。