Knobelaufgabe

Hallo!

ich hatte schon einmal hier gepostet, möchte das Problem allerdings komplett neu und mit mehr Hintergrund vorstellen. Nicht abschrecken lassen, ich glaube für einige hier ist das Kinderkram.

Ich schreibe aus Interesse an einem Parser. Für entsprechende Daten existieren bereits Parser, die ich zum Testen als Vergleich heranziehe.

Fakten:

Ich gehe davon aus, dass die existierenden Parser funktionieren, da sich die berechneten Ergebnisse untereinander decken.
Mein Parser parst sämtliche Informationen korrekt bis auf Positionsdaten (Längen- und Breitengrad)
Die Positionsdaten werden jedoch 100%ig korrekt extrahiert, weil es sich um eine fortlaufende Bitfolge handelt und alle nachfolgenden Elemente korrekt extrahiert werden

Beispiel mit einer Nachricht A:
Parser 1 ermittelt:

NE Longitude             : -73.50°
 NE Latitude              :  45.55°
 SW Longitude             : -80.16°
 SW Latitude              :  42.33°

Parser 2 ermittelt:

NE Longitude             : -44100
 NE Latitude              : 27330
 SW Longitude             : -48100
 SW Latitude              : 25400

Laut Doku handelt es sich bei den Feldern um Längen-/Breitengrad "to 0.1 minutes". D.h. die Ergebnisse von Parser 2 sind identisch zu Parser 1. Beispiel für NE Longitude:

NE Longitude: -44100 / 60 / 10 = -73.5°

Mein qualitativ hochwertiger Parser ermittelt:

NE Longitude             : 218044
 NE Latitude              : 27330
 SW Longitude             : 214044
 SW Latitude              : 25400

Die Breitengrade stimmen also. Nur bei den Längengraden stimmt was nicht. Rechne ich um erhalte ich z.B. für NE Longitude:

NE Longitude: 218044 / 60 / 10 = 363.41°

Wenn man sich jetzt folgendes Bild anschaut (das korrekte Ergebnis habe ich mit einem weißen Pfeil markiert): http://www.abload.de/img/unbenanntjvu04.png

Dann tun sich bei mir zwei Fragen auf:

1.) Wieso ist der Winkel negativ?
2.) Wo ist sind meine 363.41° angesiedelt und wie rechne ich das in 73.5° um?

Ich versteh das nicht

knivil

Die Positionsdaten werden jedoch 100%ig korrekt extrahiert, weil es sich um eine fortlaufende Bitfolge handelt und alle nachfolgenden Elemente korrekt extrahiert werden

Ach das glaube ich jetzt nicht.

Gib minimales Testbeispiel an!

MFK

Die Werte sind offenbar als Zweierkomplement codiert. Das musst du beim Parsen berücksichtigen.

Skym0sh0

1.- Mh, also deine 363,41° liegen für mich ausserhalb jedes Verständnisses. Da es nur 360° "gibt", fängt man ab 360° wieder bei 0 an zu rechnen (simpel ausgedrückt), durch eine Addition von 180, 90 oder 270 kommt man auch nichtmals in die Nähe des vermeintlich richtigen Ergebnisses.

2.- Was hat das mit C++ zu tun, ausser dass du es damit schreibst? Wenn ja, poste mal Quellcode oder wenigstens Pseudocode.

knivil schrieb:

Die Positionsdaten werden jedoch 100%ig korrekt extrahiert, weil es sich um eine fortlaufende Bitfolge handelt und alle nachfolgenden Elemente korrekt extrahiert werden

Ach ...

Ich würde das gerne als Annahme betrachten. Die Nachrichten bestehen aus Bits und man fragt dann die einzelnen Felder ab:

// [...]
channelA = getBits(12); // wandert intern 12 bits weiter
channelB = getBits(12); // wandert intern wieder 12 bits weiter
txrx= getBits(4);
power = getBits(1);
NE Longitude = getBits(18);
NE Latitude = getBits(17);
SW Longitude = getBits(18);
SW Latitude = getBits(17);
// [...]

(Wen es genauer interessiert: http://gpsd.berlios.de/AIVDM.html#_type_22_channel_management , da sind die Felder enthalten.)
Und bei mir stimmen immer ALLE Felder bis auf die Werte in Longitude. Die werden wohl ganz besonders umgerechnet.

MFK schrieb:

Die Werte sind offenbar als Zweierkomplement codiert. Das musst du beim Parsen berücksichtigen.

D.h. ich muss alle bits einmal kippen?

MFK

ThisIsOurDestiny schrieb:

D.h. ich muss alle bits einmal kippen?

Sind wir in der Ratestunde?

http://de.wikipedia.org/wiki/Zweierkomplement

MFK schrieb:

ThisIsOurDestiny schrieb:

D.h. ich muss alle bits einmal kippen?

Sind wir in der Ratestunde?

http://de.wikipedia.org/wiki/Zweierkomplement

Ok ok ich gebe mir Mühe:

Bei der Codierung in der Zweierkomplementdarstellung ist dagegen die explizite Unterscheidung zwischen einem ausgezeichneten Vorzeichenbit und den Bits, die den Betrag beschreiben, nicht notwendig. Negative Zahlen sind daran zu erkennen, dass das höchstwertige Bit den Wert 1 hat.

218044 wird laut Protokoll in eine 18 Bit Variable gesteckt.
Binär sieht der Wert so aus:

11 0101 0011 1011 1100 (MSB links)

Das Vorzeichenbit ist 1, die Zahl ist also eine negative Zahl. Das prüfe ich wie folgt:

if(m_NE_Longitude & 0x20000) {
     m_NE_Longitude &= 0x1FFFF; // Alle bits nach dem Minuszeichen holen
}

Jetzt komme ich nicht weiter. Ich bin immer noch weit vom Ergebnis entfernt

MFK

Wenn das MSB gesetzt ist, musst du einfach nur 2^18 abziehen.

MFK

Nanu...

volkard

MFK schrieb:

Das tut nicht. Man muss die "eingeschobenen" Bits auf 1 setzen. Außerdem muss m_NE_Longitude 32 Bit groß sein.

Jup, hab's gerade gelöscht, als ich die Bits noch einschoeben wollte, hab ich aber Deine Lösung gesehen, die viel hübscher ist.

Okay hier wurde wohl gelöscht... also erstmal trotzdem danke an Mfk und Volkhard die sich hier echt Mühe geben!

Trotzdem raffe ich das nicht ganz.

long m_NE_Longitude1 = six.getBits(18);

		if(m_NE_Longitude1 & 0x20000) {
			m_NE_Longitude1 -= 0x40000;	
			cout<<m_NE_Longitude1<<endl;
		}

Also was hier passiert: Irgendwo in der Doku wird stehen, dass die Longitude als Zweierkomplement gespeichert wird. Das habe ich erstmal überlesen.

Also prüfen wir, ob die Longitude positiv oder negativ ist, indem wir das MSB betrachten.

Falls sie negativ ist, ziehen wir 2^18 ab. Hier meine Frage: Warum

Mal so nebenbei, die Lösung ist richtig, ich verstehe nur den Part mit 2^18 nicht

MFK

ThisIsOurDestiny schrieb:

Falls sie negativ ist, ziehen wir 2^18 ab. Hier meine Frage: Warum

Weil das Zweierkomplement so funktioniert.

Mit 18 Bits kannst du (ohne Vorzeichen) Werte von 0 bis 262143 darstellen.

Für das Zweierkomplement nimmst du jetzt die obere Hälfte dieser Werte (131072 bis 262143, das sind genau die, bei denen das MSB 1 ist) und deutest sie um auf -131072 bis -1. Diese Werte sind also alle um genau 262144 verschoben.

Ok ich hab's verstanden. Was soll ich sagen, danke an euch, erstens habe ich wieder was gelernt (Doku korrekt lesen, Two's Complement) und zweitens hat das Forum hier mal wieder gezeigt, dass hier viele schlaue Köpfe unterwegs sind, die helfen, wenn man mal nicht weiterweiß