000
07.01.2004, 01:52 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)
|
zu schreiben ist folgende einfache Funktion...
| C++: |
int* crc_check(int* b,int n,int* crc,int g);
|
b ist der zu checkende "text"
n ist die länge des "text" bzw intarrays,
crc ist das generatorpolynom (höchster koeffizient steht bei crc[0],
g ist der grad des polynoms das array crc hat also g+1 felder
wenn der algo drübergejagt ist steht das ergebnis in b... da das jedoch von Nullen angeführt wird (ist halt bei der polynomdivision so) soll nicht b zurückgegeben werden sondern der zeiger auf den rest, als der auf die letzten #g elemente....
genaueres zum verständnis siehe weiter unten...
ich habe das der einfachheit hablber mal mit integers gemacht... eigentlich müsste man einen text übergeben und am ende noch was dranhängen....
also die Idee ist folgende... Wir haben einen Sender und einen Empfänger. Der Empfänger weiss nicht ob das was er von Sender erhält korrekt ist... Um die daten zu verifizieren wird eine art checksumme ermittelt mittels derer der empfänger checken kann ob seine daten valide sind....
das ganze ist nichts anderes als eine binäre polynomdivision, deshalb besonders einfach weil man nur mit xors rechenen muss...
als beispiel nehmen wir mal folgendes:
zu übertragen: 1101011101
crc-polynom: 1011 das steht für x^3+x+1
in der praxis werden 16er und grössere polynome verwendet und man kann wohl auch mathematisch zeigen das das zu 99,999 weiss ich wieviel prozent funktioniert, das heisst der empfänger kann zu 99,999 prozent sicher sein das die daten die er erhalten hat korrekt sind (oder auch nicht dann lässt er sich die nochmal schicken)
aber zurück zur aufgabe....
das ganze läuft wie folgt ab
man schnappt sich den "text" und hängt grad des polynoms nullen ran...
in inserem beispiel wären das dann 1101011101 mit drei Nullen am ende als
1101011101000
mit dem machen wir jetzt eine polynomdivision mit dem polynom 1011
ist genauso wie in der schule gelernt nur das man das halt binär macht was halt besonders einfach ist weil man nur ein xor braucht...
schirttweise sieht das dann so aus...
| C++: |
1101011101000
1011
0110011101000
_1011
0011111101000
__1011
0001001101000
___1011
0000010101000
____0000 //hier wird nicht geteilt weil eine 0 vorne also zu nächsten stelle
0000010101000
_____1011
0000000011000
______0000
0000000011000
_______0000
0000000011000
________1011
0000000001110
_________1011
0000000000101 //rest ist also 101;
|
dem empfänger wird dann einfach der text plus dem rest geschickt...
er erhält dann 1101011101 + 101....
also 1101011101101
das das wiederum jagt der empänger wieder durch das polynom, ist der rest nicht 000 weiss er das ein fehler bei der übertragung passiert ist und muss sich den scheiss nochmal schicken lassen. Ist der Rest 000 weiss er das er mit einer hohen wahrscheinlichkeit davon ausgehen kann das alles in ordnung ist... Die Warhscheinlichkeit steigt tendenziell mit dem grad des polynomes
| C++: |
//dieser funktion übergibt man den zu senden text "hier der einfachheit halber als ints dargestellt und den rest den der anhängen soll, damit daraus das gesamt array gebastelt wird, das der crc_check funktion übergeben wird...
int* create_check(int*b,int n,int* r,int g){
int *rv=new int[n+g];
memcpy(rv,b,n*sizeof(int));
memcpy(rv+n,r,g*sizeof(int));
return rv;
}
int* crc_check(int* b,int n,int* crc,int g){
....
}
int main(){
int i,n=10,g=3;
int bits[]={1,1,0,1,0,1,1,1,0,1};
int crc[]={1,0,1,1};
int rest[]={0,0,0};
int *temp,*erg;
temp=create_check(bits,n,rest,g);
for(i=0;i<n+g;++i) printf("%d",temp[i]);
printf("\n\n\n");
erg=crc_check(temp,n+g,crc,g);
printf("Der Rest sieht also wie folgt aus: ");
for(i=0;i<g;++i) printf("%d",erg[i]);
printf("\n");
printf("Wir schicken dem Empfaenger also folgendes: ");
for(i=0;i<n;++i) printf("%d",bits[i]);
for(i=0;i<g;++i) printf("%d",erg[i]);
printf("\n");
memcpy(rest,erg,g*sizeof(int));
delete [] temp;
temp=create_check(bits,n,rest,g); //das hier bekommt der empfänger
printf("Der Empfaenger checkt das gleich mal ab....\n");
erg=crc_check(temp,n+g,crc,g);
printf("Der Rest sieht also wie folgt aus: ");
for(i=0;i<g;++i) printf("%d",erg[i]);
printf("\n");
printf("Wenn der Rest nur Nullen enthaelt ist ein Fehler unwahrscheinlich, sonst ist ein Fehler aufgetreten");
}
|
so ich hoffe es sind keine Fragen offen geblieben
eigentlich wollte ich das als golfrätsel spielen weil das wirklich nur ein zweizeiler ist... ich nehme aber auch andere Lösungen
so für die golfer ist par 140 und für beefy sind es diesmal 2 weniger als ich
@beefy
und nicht wieder bescheissen
so hat das auszusehen rumgefummelt wird nur an dem text zwischen den geschweiften klammern
| C++: |
int* crc_check(int* b,int n,int* crc,int g){....}
|
--
...fleißig wie zwei Weißbrote |
!