Entwickler-Ecke
Off Topic - Modulo-2-Division[Cyclic Redundancy Check]
Hidden - Sa 21.08.10 12:49
Titel: Modulo-2-Division[Cyclic Redundancy Check]
Hi =)
In dieser
PDF [
http://www.rds.org.uk/rds98/pdf/IEC%2062106-E_no%20print.pdf](Seite 13) heißt es:
| Zitat: |
Each transmitted 26-bit block contains an 10-bit checkword intended to enable the receiver/decoder to detect and correct errors which occur in transmission. This checkword is the sum (modulo 2) of:
- the remainder after multiplication by x^10 and then division (modulo 2) by the generator polynomial g(x), of the 16-bit information word,
- a 10-bit binary string d(x), called the "offset word",
where the generator polynomial, g(x) is given by:
g(x) = x^10 + x^8 + x^7 + x^5 + x^4 + x^3 + 1
and where the offset values, d(x), which are different for each block within a group are given in annex A. |
- modulo-2-Addition habe ich glaube ich schon geklärt: Es handelt sich um xor(Halbaddierer) :motz:
- modulo-2-Division gibt mir noch Rätsel auf: Eine bitweise Division macht für mich keinen Sinn, deshalb weiß ich damit nichts anzufangen.
- Was genau ist jetzt x("multiplication by x^10")? Wenn x die 16 Informationsbits sind, was wird dann mit x^10 multipliziert?
Die Anleitung gibt mir reichlich Rätsel auf :gruebel:
Ich
bin der Meinung, das verwendete Verfahren sei dies hier:
http://en.wikipedia.org/wiki/Error_detection_and_correction
Weitere Erklärungsversuche unternimmt der PDF-Autor auf Seite 60/61. :nixweiss:
lg,
Flamefire - Sa 21.08.10 13:03
der 1. Teil klingt nach CRC
Modulo 2 Division: schreib die Bitfolge als Polynom. also 10011->x^5+x^2+x
und dann einfach schriftlich dividieren wobei du immer modulo 2 rechnest (musst ja addieren/subtrahieren und das immer mod 2)
a) heißt: 16Bit information mit x^10 multiplizieren (alias 10 Nullen anhängen), dann durch g(x) dividieren und der Rest ist dan a
BenBE - Sa 21.08.10 13:50
Das ist CRC ;-)
Ist zwar ein recht komisches Polynom für sowas, aber gut; muss der Autor wissen, warum er gerade das nimmt.
Hast mal paar Beispiel-Blöcke zum Rechnen?
Hidden - Sa 21.08.10 14:23
Hi :)
x=10 ist also die Basis des Zahlensystems, danke.
Die Rechnung wäre also:
Delphi-Quelltext
1:
2:
3:
4:
| function Checkword(M: Integer): Integer;
begin
result := Mod2Div(M shl 10, BD10110111001) xor d;
end; |
Für Mod2Div muss ich mir jetzt eine Implementierung der Polynomdivision für diese spezielle Mod-2-Addition suchen - oder ist das auch einfacher? :lupe:
@BenBE: Beispiele sind ab Seite 60(genau eines). Die PDF ist anscheinend zum
Radio Data System [
http://en.wikipedia.org/wiki/Radio_Data_System], einer meiner Bekannten will sich da wohl was basteln.
lg,
Hidden - Mo 23.08.10 21:34
Moin!
Das Verfahren ist verstanden,
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
| function Checkword(M: Integer): Integer;
begin
result := Mod2Div(M shl 10, BD10110111001) xor d;
end;
function Mod2Div(P, Q: Integer): Integer;
var
i: Integer;
aSum: Integer;
begin
for i := 15 downto 0 do begin
aSum := P xor (Q shl i);
if aSum < P then
P := aSum;
end;
result := P;
end; |
E: Weil ich keine Bit-Zugriffe machen will, nutze ich hier, dass die Zahl durch xor entweder kleiner oder größer wird. Ist an führender Stelle eine 1, wird sie kleiner, sonst größer.
Irgendwelche Fehler?
PS: BD10110111001 lässt sich doch eigentlich in der IDE auch direkt als Binärzahl eingeben?
lg,
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!