Je voulais en quelque sorte rendre plus fiable la transmission des informations via le canal radio. Ce n'est pas une sorte de projet industriel, ni autre chose de grave. C'est plus pour les loisirs et le développement personnel. Un traumatisme de l'enfance touché - l'absence d'une voiture radiocommandée fonctionnant normalement. Depuis, j'ai toujours voulu pouvoir contrôler facilement et naturellement n'importe quoi à la radio ...
Et donc, je m'éloigne du sujet. Dans l'enfance et l'adolescence, pour le codage correcteur d'erreurs, on pourrait appliquer le contrôle de parité par la méthode matricielle, mais maintenant ce n'est pas grave. Après avoir regardé sur Internet, j'ai décidé de m'arrêter au codage en utilisant la méthode Reed-Solomon. L'algorithme n'est pas entièrement nouveau, il a été utilisé dans les premiers CD, mais en même temps, pour autant que je sache, il n'a pas perdu de sa pertinence pour le moment. Dans cet article sur les codes Reed-Solomon eux-mêmes, je ne développerai pas grand chose - cela a été fait pour moi sur Habré de nombreuses fois et par de nombreuses personnes. Ici, je veux décrire l'implémentation de l'algorithme de multiplication dans GF [256]. Néanmoins, afin de ne pas forcer le lecteur à sauter sur des liens, je vais décrire brièvement pourquoi vous devez vous occuper des
champs galoisiens.
Le codage redondant Reed-Solomon concerne les matrices. Nous utilisons des matrices pour l'encodage et le décodage. Dans ces processus, il y a à la fois des opérations de multiplication matricielle et des opérations de recherche de matrices inverses - division. La division ici ne nécessite pas un entier approximatif, mais le plus réel, exact. Et la division exacte pour un ordinateur est une tâche insoluble: diviser un par trois, c'est zéro entier et un nombre infini de triplets après la virgule décimale, mais 640 kilo-octets suffiront à tout le monde.
Galois a vécu au début du 19ème siècle, a très peu vécu (21 ans, en général sur sa personnalité est une histoire intéressante, mais maintenant il ne s'agit pas de ça). Son travail a été très utile dans le codage numérique. Un corps de Galois fini est un ensemble de nombres de zéro à n. L'essence et l'intérêt de ces champs est que pour les éléments de cet ensemble, vous pouvez définir des opérations d'addition-multiplication-soustraction-division de telle sorte que le résultat de l'opération soit dans ce champ lui-même. Par exemple, prenons un ensemble (champ):
, . « » , ( « », « »). , , 256, ( ) 8, . GF[256], GF Galois Field.
. , , , , , « » ( stm32 ) - .
Un peu d'arithmétique. L'addition et la soustraction, comme mentionné précédemment, est la même opération dans les champs de Galois (c'est exactement le cas pour les champs de base 2), et elle est implémentée comme XOR bit à bit.
Lors de la multiplication, chaque opérande est représenté sous forme de polynôme. Cela se passe comme suit: une représentation binaire d'un nombre est prise, et la somme est écrite, où la puissance de x est le nombre du chiffre binaire et son coefficient est la valeur du chiffre.
Exemple:
De plus, les polynômes sont multipliés selon les règles de multiplication des polynômes, c'est-à-dire que chaque terme de la première tranche est multiplié par chaque terme de la seconde, mais pas seulement comme ça, mais en tenant compte du fait que le coefficient ne peut pas être plus d'un.
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 . , , etc. Cela signifie que 2 à toute puissance peut être représentée par deux à la puissance de zéro à 6 en utilisant l'opération consistant à obtenir le reste de la division par 7 dans le cas d'une puissance positive et d'une formule simplesi l'exposant est un nombre négatif
En fait, si nous rappelons la propriété de multiplier les degrés, alors la multiplication des nombres est grandement simplifiée. Et pour multiplier 6 par 3, nous regardons maintenant à quel degré deux est égal à 6 et à quel degré deux est égal à 3, additionnons les puissances et regardons le résultat - deux à un certain degré, qui peut être représenté par 2 à la puissance de 0 à 6 exemple:
Et on dirait que c'est ça! le bonheur du programmeur est l'implémentation de l'arithmétique dans le domaine de Galois - quelques lignes de code, pas besoin de s'embêter avec des polynômes ... Oui, et les performances d'un tel code seront élevées, mais ensuite je suis tombé sur un autre problème: la table des puissances de deux dans le champ GF [8] avec le polynôme générateur 11 se trouve facilement. Même cette ressource l'est. Mais je n'ai pas cherché sur Google la table des degrés pour GF [256], j'ai donc décidé de la compiler moi-même, C # m'aidera. J'ai dû implémenter l'algorithme de multiplication selon les règles des polynômes.
Voici une fonction de multiplication de travail pour GF [2 ^ n] avec un polynôme arbitraire. Restriction - J'utilise l'arithmétique 32 bits, donc n doit être inférieur à 16. Ici aussi est ajoutée une fonction pour trouver le nombre du bit le plus significatif d'un nombre
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;
}Maintenant, en utilisant la fonction ci-dessus, vous pouvez créer une table de puissances de deux pour le GF dont j'ai besoin [256] et écrire un module arithmétique Galois pour stm32 en utilisant deux tables de 256 chacune - une pour le direct, la seconde pour reconvertir le nombre à sa puissance. Je n'ai même pas encore commencé à implémenter le codage Reed-Solomon, mais quand il sera prêt, je pense que je vais le partager ici. Espérons que ce sera plus court.