Ich wollte irgendwie eine zuverlässigere Übertragung von Informationen über den Funkkanal ermöglichen. Dies ist kein Industrieprojekt oder etwas anderes Ernstes. Es ist mehr für Hobbys und Selbstentwicklung. Betroffen von Kindheitstraumata - das Fehlen eines normal funktionierenden ferngesteuerten Autos. Seitdem wollte ich immer in der Lage sein, alles im Radio einfach und natürlich zu steuern ...
Und so schweife ich ab. In der Kindheit und Jugend könnte man zur fehlerkorrigierenden Codierung die Paritätsprüfung nach der Matrixmethode anwenden, aber jetzt ist dies nicht ernst. Nachdem ich mich im Internet umgesehen hatte, beschloss ich, nicht mehr mit der Reed-Solomon-Methode zu codieren. Der Algorithmus ist nicht ganz neu, er wurde in den ersten CDs verwendet, hat aber meines Wissens im Moment nicht an Relevanz verloren. In diesem Artikel über die Reed-Solomon-Codes selbst werde ich nicht viel erweitern - dies wurde für mich auf Habré viele Male und von vielen Menschen getan. Hier möchte ich die Implementierung des Multiplikationsalgorithmus in GF beschreiben [256]. Um den Leser nicht zu zwingen, auf Links zu springen, werde ich kurz beschreiben, warum Sie sich überhaupt
mit Galois-Feldern befassen müssen .
Bei der redundanten Codierung nach Reed-Solomon geht es um Matrizen. Wir verwenden Matrizen zum Codieren und Decodieren. In diesen Prozessen gibt es sowohl Operationen der Matrixmultiplikation als auch Operationen des Findens inverser Matrizen - Division. Die Division erfordert hier keine ungefähre ganze Zahl, sondern die realste, genaueste. Und die genaue Division für einen Computer ist eine unlösbare Aufgabe: Die Division eins durch drei ist null Ganzzahlen und eine unendliche Anzahl von Tripeln nach dem Dezimalpunkt, aber 640 Kilobyte reichen für alle.
Galois lebte zu Beginn des 19. Jahrhunderts, er lebte sehr wenig (21 Jahre, im Allgemeinen ist die Geschichte über seine Persönlichkeit interessant, aber jetzt geht es nicht mehr darum). Seine Arbeit war sehr nützlich in der digitalen Codierung. Ein endliches Galois-Feld ist eine Menge von Zahlen von Null bis n. Das Wesentliche und Interesse dieser Felder besteht darin, dass Sie für die Elemente dieser Menge Additions-Multiplikations-Subtraktions-Divisions-Operationen so definieren können, dass das Ergebnis der Operation in diesem Feld selbst liegt. Nehmen wir zum Beispiel eine Menge (Feld):
, . « » , ( « », « »). , , 256, ( ) 8, . GF[256], GF Galois Field.
. , , , , , « » ( stm32 ) - .
Ein bisschen über Arithmetik. Addition und Subtraktion sind, wie bereits erwähnt, dieselbe Operation in Galois-Feldern (dies ist genau der Fall für Felder der Basis 2) und werden als bitweises XOR implementiert.
Beim Multiplizieren wird jeder Operand als Polynom dargestellt. Es geschieht wie folgt: Die binäre Darstellung der Zahl wird genommen und die Summe wird geschrieben, wobei die Potenz von x die Zahl der binären Ziffer und ihr Koeffizient der Wert der Ziffer ist.
Beispiel:
Ferner werden die Polynome gemäß den Multiplikationsregeln der Polynome multipliziert, dh jeder Term in der ersten Klammer wird mit jedem Term in der zweiten multipliziert, aber nicht nur so, sondern unter Berücksichtigung der Tatsache, dass der Koeffizient nicht mehr als eins sein kann.
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 . , , . , 2 6 7 , —
, , . 6 3 , 6 3, — - , 2 0 6 :
Und so sieht es aus! Das Glück des Programmierers ist die Implementierung der Arithmetik im Galois-Feld - ein paar Codezeilen, keine Notwendigkeit, sich mit Polynomen zu beschäftigen ... Ja, und die Leistung eines solchen Codes wird hoch sein, aber dann bin ich auf ein anderes Problem gestoßen: Die Tabelle der Zweierpotenzen im GF-Feld [8] mit der Erzeugung des Polynoms 11 wird gefunden leicht. Auch diese Ressource ist. Aber ich habe die Grad-Tabelle für GF nicht gegoogelt [256], also habe ich beschlossen, sie selbst zu kompilieren. C # wird mir helfen. Ich musste den Multiplikationsalgorithmus nach den Regeln der Polynome implementieren.
Hier ist eine funktionierende Multiplikationsfunktion für GF [2 ^ n] mit einem beliebigen Polynom. Einschränkung - Ich verwende 32-Bit-Arithmetik, daher muss n kleiner als 16 sein. Außerdem wird hier eine Funktion hinzugefügt, um die Nummer des höchstwertigen Bits einer Zahl zu ermitteln
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;
}Mit der obigen Funktion können Sie nun eine Zweierpotenztabelle für die benötigte GF erstellen [256] und ein Galois-Arithmetikmodul für stm32 mit zwei Tabellen zu je 256 schreiben - eine für die direkte und die zweite für die Rückumrechnung der Zahl in ihre Potenz. Ich habe noch nicht einmal begonnen, die Reed-Solomon-Codierung zu implementieren, aber wenn sie fertig ist, werde ich sie hier teilen. Hoffentlich wird es kürzer.