Kann mir vielleicht irgendwer erklären was diese Skizze 2.4 sagt? Ich denke es wird mit Beispiel 2.27 klarer: Der Satellit sendet seine eigene Sequenz andauernd. Jedoch verstehe ich dann nicht was Beispiel 2.28 bedeutet. Was für Korrelationen rechnet der da und wieso? Ich habe mir das irgendwie so vorgestellt: Der Satellit sendet andauernd seine Sequenznummer und der Empfänger korreliert dann und wenn 1 herauskommt, dann weiß er, dass das dies und jener Satellit ist. Jedoch ist mir dann das Beispiel 2.28 irgendwie nicht versändlich. Wieso verschiebt er da dauernd die Bits heraum und rechnet Korellationen aus?
> Wieso verschiebt er da dauernd die Bits heraum und rechnet > Korellationen aus? Weil der "dumme" (unsynchronisierte) Empfänger auf der Erde nicht weiss, wann die Sequenz vom Satellit eigentlich anfängt... Mit dem Korrelationspeak ist das erkennbar.
Und weil der Satellit nicht weiss wann der Empfaenger eingeschalten wird.
:
Bearbeitet durch User
Ich bin noch anfänger in diesem Gebiet. Kann mir vielleicht wer erklären, wieso genau im Detail das notwendig ist was gemacht wird? Was bedeuten diese zyklischen Verschiebungen überhaupt? Und wieso sind sie notwendig? Offenbar geht es da darum, dass sich der Satellit dem Gerät bekannt macht. Das geschieht durch seine Nummer. Jedoch würde meiner Meinung nach reichen einfach die Sequenznummer zu vergleichen. Hat das vielleicht mit Start und Stopbit was zu tun? Weil das Gerät eben einfach so 7 aufeinanderfolgende Bits aufzeichnet und daraus den Korellation berechnet?
Manki E. schrieb: > Was bedeuten diese zyklischen Verschiebungen überhaupt? Das ist reines Ausprobieren: du hast eine Sequenz aus 7 Elementen, deine Vergleichssequenz kannst du also in 7 verschiedenen Positionen darüberlegen und dann gucken, ob's passt.
Jörg Wunsch schrieb: > Das ist reines Ausprobieren: du hast eine Sequenz aus 7 Elementen, > deine Vergleichssequenz kannst du also in 7 verschiedenen Positionen > darüberlegen und dann gucken, ob's passt. Aber wozu all das?
Mit dieser Funktionalitaet kann man auch weit unterhalb der Rauschschwelle uebertragen. Die Sequenz ist gleichzeitig Codierung. Die Sequenz ist dann etwas laenger. Man korreliert das Empfangssignal mit der Sequenz und erhaelt so die Daten. So koennen alle Satelitten gleichzeitig senden.
Einpaar fragen zu diesen Erklärungen hier: Es steht zum Beispiel
1 | Die Summe der 3 Sequenzen ist z = x + y20 + z20. |
Aber soltle da nicht eher stehen:
1 | Die Summe der 3 Sequenzen ist w = x + y20 + z20. |
? Weitere Frage: Es steht auch
1 | In Bild 2.5 ist durch die Pfeile angedeutet, dass x,y und z an z |
2 | vorbeigeschoben werden und die Korrelation berechnet wird |
Diesen Satz verstehe ich aber üerhaupt nicht. Was heißt denn vorbeigeschoben?? Was soll das alles heißen? Und wieso wird z an z vorbeigeschoben?
Manki E. schrieb: > Aber soltle da nicht eher stehen: > Die Summe der 3 Sequenzen ist w = x + y20 + z20. Nein, auch falsch :) Es sollte stehen: w = x +y20 + z60 Das ist der Geist der neuen Zeit: Wissenschaftliche Texte in Arduino-Qualität. Die Idee ist didaktisch nicht schlecht, aber die Umsetzung... vergessen wir das.
Manki E. schrieb: > Offenbar geht es da darum, dass sich der Satellit dem Gerät > bekannt macht. Ja. > Das geschieht durch seine Nummer. Hmmm... ja... teilweise. > Jedoch würde meiner Meinung nach reichen einfach die > Sequenznummer zu vergleichen. Ach so. Und wo nimmt der Empfänger die Sequenznummer her, wenn er im Wesentlichen nur Rauschen empfängt? Er empfängt 99% Rauschen, das vielleicht um 1% schwankt. Wie willst Du dort ein Signal erkennen? > Hat das vielleicht mit Start und Stopbit was zu tun? Weil > das Gerät eben einfach so 7 aufeinanderfolgende Bits > aufzeichnet und daraus den Korellation berechnet? Ja, schon besser. Der Schlüssel ist das "eben einfach so": Das Signal ist viel zu schwach, um direkt die Einsen und Nullen zu erkennen. Also berechnet der Empfänger pausenlos die Korrelation zwischen dem Empfangssignal und dem Signalmuster, auf das er wartet. Wenn die Kreuzkorrelations- funktion dann ein Maximum zeigt, weiss der Empfänger, dass er das Signal erwischt hat, ohne es direkt zu sehen. Korrelationsempfang ist Magie. :)
> Was bedeuten diese zyklischen Verschiebungen überhaupt?
Praktisch gesehen eine Zeitverschiebung. Die 0en und 1en der Sequenz
werden ja hintereinander gesendet (Morsen macht ja auch sowas...). Der
Empfänger empfängt dann auch nur einzelne 0en und 1en als Endlosbitstrom
und weiss eigentlich erstmal nicht, wo eine Sequenz anfängt. Mit dem
Korrelationspeak kann er den exakten zeitlichen Anfang der Sequenz
finden, sich also auf den Sender synchronisieren.
Hat man mehrere Sender, die mit unterschiedlichen Sequenzen auf
derselben Frequenz senden, die aber alle zum selben Zeitpunkt anfangen,
kann man über die zeitliche Differenz der Korrelationspeaks die
Unterschiede in den Abständen zum Empfänger rausbekommen. Wenn man
weiss, wo die Sender gerade sind (kann man auch in das Sendesignal
einbauen), weiss man damit dann auch, wo der Empfänger steht.
Jörg Wunsch schrieb: > Das ist reines Ausprobieren: Wirklich? Wird mich wundern wenn's dafür keine Theorie gäbe :-)
Johann L. schrieb: > Jörg Wunsch schrieb: >> Das ist reines Ausprobieren: > > Wirklich? Ja. > Wird mich wundern wenn's dafür keine Theorie gäbe :-) Ähh?! Die Theorie dahinter heißt "Abwarten". Wenn Du auf ein bestimmtes Muster in einem seriellen Datenstrom wartest, dann musst Du halt warten, bis das Muster kommt. Das ist die ganze Theorie. Du hast Jörgs Bemerkung vermutlich missverstanden. Übrigens ist auch das Bestimmen von Folgenfamilien mit bestimmten Korrelationseigenschaften viel Ausprobiererei. Analytische Ergebnisse gibts nur für bestimmte Typen von Folgen.
Manki E. schrieb: > Aber wozu all das? http://de.wikipedia.org/wiki/Linear_r%C3%BCckgekoppeltes_Schieberegister#Gold-Folgen http://de.wikipedia.org/wiki/Codemultiplexverfahren http://de.wikipedia.org/wiki/Frequenzspreizung 1) Digitale Modulationsverfahren haben den Vorteil das auch bei einen hohen rauschpegel resp geringen Signalpegel noch sicher ein Signal detektiert werden kann. 2) Das empfangene Signal ist ein gemisch aus den Signalen mehrere Sender. Durch die Codespreizungen ist es moglich einezelne Sender zu selktierem. Hier kann man daraus die Satelliten erkennen die gearde sichtbar sind. 3) aus der aktuellen codephase der Signale zueinander kann man einen Laufzeitunterschied zwischen den Satelliten bestimmen. 4) damit plus kenntnis der Bahndaten und der Gangungenauikeit der Zeitbasis des Satelliten (Atomuhr) (deren Nummer ja man nun dank der Codespreizung kennt) kann der GPS-Empfänger bestimmen. Die WP versucht es ohne viel Formel-Mathe zu erklären: http://de.wikipedia.org/wiki/GPS-Technik Dieses MI-paper scheint auch brauchbar: http://www.ni.com/white-paper/4450/en/ MfG,
Johann L. schrieb: > Wird mich wundern wenn's dafür keine Theorie gäbe :-) Das Ausprobieren nennt sich hier „Korrelation“. :)
Jörg Wunsch schrieb: > Johann L. schrieb: >> Wird mich wundern wenn's dafür keine Theorie gäbe :-) > > Das Ausprobieren nennt sich hier „Korrelation“. :) Klar, mit roher Gewalt kommt man hier zum Ziel. Allgemeiner formuliert: Finde
so dass
wobei die a_k durch Rotation (der Komponenten) von a entstehen. Es ist
zu erwarten, dass eine Lösung in R^n existiert, aber gibt es auch eine
(und welche) in {-1,1}^n ?
Wenn eine Lösung für n = 97 gesucht ist, hilft auch Warten nix (Lösung
von Reiner) und Ausprobieren wird irgendwann ... langsam.
Für n = 5 z.B.
mit
Die Eigenvektoren von M sind offenbar von der Gestalt
mit einer (primitiven) 5. Einheitswurzel zeta_5.
Johann L. schrieb: > Jörg Wunsch schrieb: >> Johann L. schrieb: >>> Wird mich wundern wenn's dafür keine Theorie gäbe :-) >> >> Das Ausprobieren nennt sich hier „Korrelation“. :) > > Klar, mit roher Gewalt kommt man hier zum Ziel. > > Allgemeiner formuliert: Finde >
> so dass >
> wobei die a_k durch Rotation (der Komponenten) von a entstehen. Es ist > zu erwarten, dass eine Lösung in R^n existiert, aber gibt es auch eine > (und welche) in {-1,1}^n ? Und worin besteht der Zusammenhang mit den Goldfolgen? Der Trick bei der GPS Korrelation sind die orthogonal zueinander stehenden Codes, also geringe Kreuzkorrelation, hohe Autokorrelation (Peak im Spektrum). MfG,
Die verschiedenen Codefolgen sollen eine minimale Kreuzkorelation haben, sie wird kaum Null sein. Viel aufwendiger ist das Locken der Phase. Denn wenn die Phasenkorrelation ein Dirac Delta ist, ist locken auf die Phase nicht trivial. Dh waehrend eines Phasenunterschiedes von weniger als einem Bit, bekommt man ein Signal, sonst ist nichts. Man sollte die Phase also kleiner als ein Bit genau regeln koennen und hat nur die Signalamplitude als Eingangsgroesse. Auf beide Seiten nimmt das signal ab. Das kann man zB Loesen indem die Phase beschleunigt wird, wenn kein signal da ist und gebremst wird, wenn signal da ist. Dh der Regelkreis ist immer da, wo das Signal abgewuergt wird.
Fpga Kuechle schrieb: > Johann L. schrieb: >> Jörg Wunsch schrieb: >>> Johann L. schrieb: >>>> Wird mich wundern wenn's dafür keine Theorie gäbe :-) >>> >>> Das Ausprobieren nennt sich hier „Korrelation“. :) >> >> Klar, mit roher Gewalt kommt man hier zum Ziel. >> >> Allgemeiner formuliert: Finde >>
>> so dass >>
>> wobei die a_k durch Rotation (der Komponenten) von a entstehen. Es ist >> zu erwarten, dass eine Lösung in R^n existiert, aber gibt es auch eine >> (und welche) in {-1,1}^n ? > > > Der Trick bei der GPS Korrelation sind die orthogonal zueinander > stehenden Codes, Das ist ja alles klar. Aber muss man geeignene Folgen wirklich raten? Und für welche n existieren überhaupt solche Folgen? > also geringe Kreuzkorrelation, hohe Autokorrelation Zu Gold-Folgen lese ich: "A set of Gold codes can be generated with the following steps. Pick two maximum length sequences of the same length 2n − 1 such that their absolute cross-correlation is less than or equal to 2(n+2)/2, ..." Meine Frage: Bedeutet dieses "pick" dumpfes Rumprobieren bis die Bedingungen erfüllt sind, oder geht das auch schlauer? Die Beschreibung von Gold-Codes fährt fort mit Ausführungen zu LFSRs und XOrs etc., also einer verbrämten Darstellung so dass Leute, die ein entsprechendes Programm zu schreiben haben, wissen, wo sie wann welches XOr machen müssen. Unter der Haube sind es Operationen in endlichen Körpern, und ein Großteil des LFSR-Zeugs beruht darauf, dass die multiplikative Gruppe des zugrunde liegenden Körpers zyklisch erzeugt ist. Das Bitgefutschel ist also nix anderes als Arithmetik über einem endlichen Körper der Charakteristik 2. Es gibt also einen mächtigen theoretischen Unterbau, und da dachte ich, dass es eben besser geht aus Rumprobiererei wenn Folgen wie 1, -1, 1, 1 , -1, -1, -1 zu finden sind. > Und worin besteht der Zusammenhang mit den Goldfolgen? Es ist gerade die Bedingung minimaler Korrelation — außer an einer Stelle: die Bedingung <a,a> = n ist trivialerweise erfüllt und ich hab sie weggelassen.
:
Bearbeitet durch User
> oder geht das auch schlauer? Das "maximum length sequence" ist ja schon mal eine gewisse Schlauheit ;) Und dann gibt es noch "preferred pairs": http://www.gaussianwaves.com/2010/10/preferred-pairs-m-sequences-generation-for-gold-codes-2/
LFSR sind einfache Werkzeuge, auch beschrieben unter : http://www.ibrtses.com/simulations/lfsr.html mit links auf effektiv implementierbare Folgen. Beim zitierten Paper werden Folgen mit bis zu 150bit erklaert, was eine Folgenlaenge von 2^150 bit abdeckt...
Georg A. schrieb: > http://www.gaussianwaves.com/2010/10/preferred-pairs-m-sequences-generation-for-gold-codes-2/ Auch nicht wirklich hilfreich : Generating Preferred Pairs of m-sequences: 1) Take a m-sequence [Math Processing Error] for given length [Math Processing Error] [Math Processing Error] ,where [Math Processing Error] is the number of registers in the LFSR). 2) Decimate the m-sequence by a decimation factor of q. This is our second sequence. [Math Processing Error] etc...
>>Aber muss man geeignene Folgen wirklich raten? >>Und für welche n existieren überhaupt solche Folgen? Nein, man kann solche Folgen konstruieren. Es sind Maxium Length Sequences und diese folgen mathematischen Regeln, sie sind nicht reduzierbare Polynome und solche Polynome kann man direkt berechnen durch deren Faktorization. Im Grunde für alle N > 2 existieren solche Folgen, wenn ich mich recht erinnere. >Meine Frage: Bedeutet dieses "pick" dumpfes Rumprobieren bis die >Bedingungen erfüllt sind, oder geht das auch schlauer? Das geht auch schlauer. Zum einen kann man Gold Codes durch M-Sequences direkt konstruieren. Auch hier gilt das die sich ergebende Faktiorzation beider Polynome wiederum teilfremd zueinander sein müssen. Dann kann man über die sogenannte Hadamard Transformation auf einen empfangenen Code wie bei einer FFT mit gleicher Komplexität wie bei einer FFT das "Spektrum" ausrechnen. Es geht sogar schneller als bei der FFT da man bei der Hadamard Transformation nur mit Additionen auskommt, statt Multiplikationen wie bei der FFT. Das "Spektrum" ist aber eher ein Output wie bei der Autokorrelation, dh. der höchste Peak gibt die zeitliche Position des Urspungs der korrelierten Sequenz an. Man kann aber auch mit Hilfe der FFT korrelieren, im Falle der M-Sequenzes ist das aber ineffizenter. Gruß hagen
Hagen Re schrieb: >>>Aber muss man geeignene Folgen wirklich raten? >>>Und für welche n existieren überhaupt solche Folgen? > sie sind nicht > reduzierbare Polynome und solche Polynome kann man direkt berechnen > durch deren Faktorization. ?Nicht reduzierbare Polynome kann man Faktorisieren/direkt berechnen? Bitte erläuetern. Oder verwechsele ich hier nicht reduzierbar mit "Irreduzible". Das ist doch synonym, oder? http://de.wikipedia.org/wiki/Irreduzibles_Polynom >>Meine Frage: Bedeutet dieses "pick" dumpfes Rumprobieren bis die >>Bedingungen erfüllt sind, oder geht das auch schlauer? Also inzwischen tendiere ich auch eher zu der Aussage das man optimale Codes wie Primzahlen nicht pauschal berechnen kann. Beispiel "maximum length folgen" Die entshenen doch aus Primitiven Polynomen http://de.wikipedia.org/wiki/Primitives_Polynom. Für diese gibt es IMHO keine berechnungs- sondern eine Prüfvorschrift. Mein Prof in der Codierungstheorie erzählte in der Vorlesung bei den primitiven Folgen wie sie in den 70igern das rechenzentrum lahmlegten um "neue" primitive Polynome zu testen/bestimmen. Analog die Mersenne-Primzahl, es gibt eine Berechnungsvorschrift für Mersenne-Zahlen, aber nicht für Mersenne-Primzahl. Nicht jede Mersenne-Zahle ist eine Primzahl, aber es gibt ein gutes (schnelle) Testverfaheren auf prim für Mersenne-Zahlen. http://de.wikipedia.org/wiki/Mersenne-Primzahl So ähnlich ist das mit Zahlenfolgen in der Kommunikationstechnik. Man kann beweisen das es eine nach bestimmtem Eigenschaften optimale Folge gibt, diese aber nicht direkt berechnen. Man kann aber bestimmte Folgen auswählen und prüfen. Was letzlich auch nur synonym zu "durchprobieren" ist. Der Verdienst von Robert Gold is nun aus den (Gott-gegebenen) Maximum-lenght folgen einen Cod konstruiert zu haben der bezüglich AKF und KKF gewünschte Eigenschaften zeigt. MfG,
>?Nicht reduzierbare Polynome kann man Faktorisieren/direkt berechnen? >Bitte erläuetern. Oder verwechsele ich hier nicht reduzierbar mit >"Irreduzible". Das ist doch synonym, oder? Ja, irreducible=nicht reduzierbar, quasi wie Teilerfremd in N nur eben in GF(2). Primitive Polynome sind nicht reduzierbar und ähnlich wie Primzahlen. >Also inzwischen tendiere ich auch eher zu der Aussage das man optimale >Codes wie Primzahlen nicht pauschal berechnen kann. Natürlich kann man Primzahlen berechnen. Man spricht aber eher von "konstruieren". Die Algorithmen kennzeichnen sich immer dadurch das sie zu einem kleinen Teil eine Suche/Testen durchführen. Eine direkte Berechung per mathm. Forml ist bis heute aber noch nicht möglich. Dh. aber nicht das es keine effizienten Algorithmen gäbe mit denen man Primzahlen konstruieren könnte. Und so wie man zb. in N sehr große industrielle Primzahlen für RSA uä. Kryptoverfahren konstruieren kann so geht das auch in GF(2). Alle meine nicht reduzierbaren Polynome bis Degree 32 habe ich errechnet, und das geht auch ziemlich schnell. Zb. gibt es 24000 Polynome mit Degree 20 und mit meiner nicht optimierten Berechnung dauert das 21 Sekunden um alle zu errechnen. ZB. bie Berechnung von 2x 512 Bit Primzahlen für RSA dauert bei mir unter 1 Sekunde. Diese sind natürlich von sogenannter industieller Qualität. Das Erzeugen eines ECP Zertifikates, also der Beweis das es echte Primzahlen sind, dauert dann pro Primzahl ca. 5-10 Minuten. Dabei wird immer ein Verfahren verwendet das aus einer optimierten Suche und Testen besteht. Die Suche zb. immer mehrstufig mit Siebverfahren die Kandidaten konstruieren die mit hoher Wahrscheinlichkeit den gewünschten Anforderungen genügen. Einfachstes Beispiel: alle durch 2 teilbaren Zahlen brauch man nicht auf Primzahl testen. Das kann man so erweitern das man zb. ein Teilbarkeitssieb benutzt für alle Primzahlen < 2^16 und das wie eine große Tabelle der Reste per Additionen inkrementiert für den nächsten Kandidaten. So filtert man ganz ohne Divisionen alle Zahlen raus die durch alle Primzahlen < 2^16 teilbar sind. Danach benutzt man verschiedene Testverfahren wie zb. Rabin Miller oder wie bei mir den Baile/Selfridge/Wagstaff Strong Lucas Pseudo Prim Test. Bei der Erzeugung primitiver Polynome wird in GF(2) eine modulare Multiplikation implementiert und das Ausgangspolynom=Seed faktorisiert. Danach wird inkrementell diese Faktorisation inkrementiert und das Zielpolynom daraus erzeugt und per Moduklarer Exponentation in GF(2) auf Primitivität getestet. Also auch hier optimierte Suche zur Erzeugung der wahrscheinlichsten Kandidaten und deren anschließender Überprüfung der gewünschten Eigenschaften. >Was letzlich auch nur synonym zu "durchprobieren" ist. Ja und Nein, je nach Sichtweise. Durchprobieren=Brute Force Methode= wähle per Zufall oder alles sequentiell und teste es dann. Das ist das Worst Case Szenario das immer die größte Komplexität besitzt. "Konstruieren" heist das man nur vorgefilterte Kandidaten "durchprobiert" und somit beschänkt sich die Komplexität nur noch auf die Kandidaten die man nicht vorfiltern konnte. Das kann eine enorme Reduktion an Aufwand bedeuten, so groß das ein "Durchprobieren" Algorithmus im Vergleich zu einem "Konstruieren" wirklich den Unterschied ausmacht zwischen, ich warte bis an mein Lebensende zu ich hab das Ergebnis in 20 Sekunden. Nicht destotrotzt: wir teilen beide grundsätzlich die selbe Ansicht. Gruß Hagen
Hagen Re schrieb: >>?Nicht reduzierbare Polynome kann man Faktorisieren/direkt berechnen? >>Bitte erläuetern. Oder verwechsele ich hier nicht reduzierbar mit >>"Irreduzible". Das ist doch synonym, oder? > > Ja, irreducible=nicht reduzierbar, quasi wie Teilerfremd in N nur eben > in GF(2). Primitive Polynome sind nicht reduzierbar und ähnlich wie > Primzahlen. > >>Also inzwischen tendiere ich auch eher zu der Aussage das man optimale >>Codes wie Primzahlen nicht pauschal berechnen kann. > > Natürlich kann man Primzahlen berechnen. Man spricht aber eher von > "konstruieren". >>Was letzlich auch nur synonym zu "durchprobieren" ist. > > Ja und Nein, je nach Sichtweise. Durchprobieren=Brute Force Methode= > wähle per Zufall oder alles sequentiell und teste es dann. ... > Nicht destotrotzt: wir teilen beide grundsätzlich die selbe Ansicht. Dank den ausführlichen Erläuterungen seh ich das ebenso, vielen Dank. MfG,
Hagen Re schrieb: >>?Nicht reduzierbare Polynome kann man Faktorisieren/direkt berechnen? >>Bitte erläuetern. Oder verwechsele ich hier nicht reduzierbar mit >>"Irreduzible". Das ist doch synonym, oder? > > Ja, irreducible=nicht reduzierbar, quasi wie Teilerfremd in N nur eben > in GF(2). Primitive Polynome sind nicht reduzierbar und ähnlich wie > Primzahlen. > >>Also inzwischen tendiere ich auch eher zu der Aussage das man optimale >>Codes wie Primzahlen nicht pauschal berechnen kann. > > Natürlich kann man Primzahlen berechnen. Man spricht aber eher von > "konstruieren". "Konstruktion" im mathematischen Sinne ist etwas anderes, z.B. eine Linie mit Zirkel und Lineal zu halbieren oder aus n gegebenen Prinzahlen eine Zahl zu konstruieren, welche keine dieser Prinzahlen als Teiler besitzt. So gibt es bis dato keine Verfahren,das aus einer Zahl n die nächstgrößere Primzahl konstruiert — oder irgendeine Primzahl größer als n konstruiert. > Bei der Erzeugung primitiver Polynome wird in GF(2) eine modulare > Multiplikation implementiert und das Ausgangspolynom=Seed faktorisiert. Hort sich irgendwie komplziert an. Meine Polynome erhalte ich so: 1) Implementiere Basisarithmetik über GF(q^n) wobei ich GF(q^n) darstelle als GF(q)[r] mit einer Nullstelle r des Polynoms p(x) aus GF(q)[x]. 2) Wähle ein Polynom p vom Grad n aus GF(q)[x]. Damit es irreduzibel vom Grad n ist, muss offenbar der n-te und der 0-te Koeffiziern ungleich 0 sein und die Summe der Koeffizienten muss ungleich 0 mod q sein. (Für q=2: die Anzahl der Koeffizienten != 0 ist ungerade.) 3) Wahle ein a aus GF(q)[r] und berechne
Wenn das Ergebnis != 1 ist gehe zu 2) denn p ist nicht irreduzibel über GF(q). 4) Berechne
für alle Primteiler t von q^n-1. Falls einer dieser Werte = 1 ist: Gehe zu 2 denn p ist nicht irreduzibel über GF(q). 5) Fertig. p ist irreduzibel, und a ist zyklischer Erzeuger von GF(q^n)*. Das funktioniert deshalb schnell, weil es "viele" irreduzible Polynome gibt (das auszurechnen ist ein einfahes kombinatorisches Problem) und es außerdem viele primitive Einheitswurzeln gibt, so dass die Wahrscheinlichkeit, zufällig eine zu finden, recht hoch ist. Weil ich i.d.R ohnehin eine primitive Einheitswurzel brauche ist die Irreduzibilität von p "nur" ein Nebenprodukt. Übrigens ist p in GF(q^n) nicht irreduzibel sondern zerfällt offenbar in n Linearfaktoren. Wie es von da aus konkret weitergeht ist mir aber immer noch net klar :-(
:
Bearbeitet durch User
>"Konstruktion" im mathematischen Sinne ist etwas anderes, z.B. eine >Linie mit Zirkel und Lineal zu halbieren oder aus n gegebenen Prinzahlen >eine Zahl zu konstruieren, welche keine dieser Prinzahlen als Teiler >besitzt. naja, das ist doch was ich unter Konstruktion verstehe, und eine Konstruktion wird ebenfalls mit Hilfe mathematischer Algorithmen berechnet. Ich denke das ist eine Frage der Definition der Wortbedeutungen. ich verstehe unter berechnen alles was durch beliebige Algorithmen berechenbar ist, quasi was ein Computer=Rechner rechnen kann. Der Unterschied besteht für mich darin ob irgendwas direkt oder nur indirekt berechnenbar ist, also zb. auf direkten Wege errechne ich das 1+1=2 ist. Oder aber ich erzeuge linear oder per Zufall alle Zahlen zwischen 0 und 9 und subtrahriere nun davon 1 und überprüfe ob wiederum 1 raus kommt. Aber das ist Wortklauberei.
Nochmal zum MItkommen für Langsame: JEDER Satellit in der Umlaufbahn hat eine FIXE Sequenznummer, die sich nicht ändert. Sagen wir es gibt 4 Satelliten in der Umlaufbahn mit den Sequenznummern:
Auf allen Satelliten befindet sich (zur Vreinfachung) eine Atomuhr. Außerdem wissen die Satelliten ihre eigenen Positionen. Sagen wir in (x,y,z) Koordinaten, damit das alles sehr einfach wird. Die Satelliten senden andauernd ihre Sequenznummern heraus. Nehmen wir mal an nur einer. Wie GPS dabei noch funktioniert sei dahingestellt. Das werde ich heute hoffentlich nicht im Laufe des tages verstehen. Der GPS Empfänger kennt zunächst einmal ALLE Sequenzen ALLER Satelliten. Er wartet auf eine Verbindung. Die Frage die sich mir hier stellt ist: Wie wartet er? Einige von euch sagen, dass er dauernd korreliert. Aber wie? Ich mein da ist im Prinzip nichts in der Luft außer Rauschen. Ich stell mir das gerade so vor: Der Empfänger misst ein E-Feld (Spannung) eine bestimmte Zeitlang. Stoppt dann, und digitalisiert diese Spannung in zb 4 Bits, damit er autokorrelieren kann. Die Frage ist: Was korreliert er genau? Die Sequenz die er empfangen hat mit sich selbst? Angenommen das stimmt, dann bekommt er zwei Werte raus: einmal 0 und einmal 1. Aber was macht er jetzt damit genau? Beachte, dass hier nur ein einziger Satellit sendet. Was wenn nur der zweite Satellit sendet? Da kommt dann wieder 0 oder 1 raus, je nachdem um wieviel Bits verschoben die Sequenzen ankommen. Man wüsste also nicht ob das der eine oder andere Satellit ist. Irgendwie verstehe ich den ganzen Sinn dahinter noch nicht ganz.
Der Empfaenger korreliert natuerlich dauernd. Da wird nichts gestoppt. In der Regel 10 Satelliten gleichzeitig. Welche Satelliten da sein muessen ist in den auch gesendeten Bahndaten ersichtlich. Das waeren dann die Ephimeris daten. Diese Daten werden von jedem Satelliten gesendet, dh wenn man einen hat, erfaehrt man die Bahndaten von allen. Deshalb dauert die Erstacquisition auch etwas laenger. Und ja. Das Signal kommt erst wenn die Sequenz(en) aufs Bit gelockt sind. Es wird das Antennen signal mit den vorgegebenen Sequenzen korreliert.
:
Bearbeitet durch User
hmmm, wie man enstsprechende Sequenzen erstellt weiß ich immer noch net.
Ist eine solche Sequenz c_0.. c_{n-1} gegeben, erhält man das Spektrum
der Matrix M durch
Und der zyklischen Matrix
(Die Indices werden mod n genommen) Der erste Eigenwert ist 1 oder -1, der Rest des Spektrums liegt auf einem Kreis mit Radius Wurzel(n+1) um den Ursprung.
Zumindest gilt das für die Werte von n für welche ich entsprechende Sequenzen finden konnte (per brute force). Als Bedingung, dass eine solche Sequenz existiert, d.h.
hab ich bisher: 1) n ist 3 mod 4 (gilt mindestens bis n = 35, dann macht mein Schleppi schlapp) 2) n ist nicht 27. Keine Ahnung warum 27 aus der Reihe tanzt, vielleicht weil es nicht quadratfrei ist... Für andere n (n ungleich 3 mod 4) gibt's scheinbar keine solchen Sequenzen. Für n = 3 gibt es 1 Sequenz, und für die anderen n < 30 (7, 11, 15, 19, 23) gibt es je zwei Sequenzen, d.h. 1 Sequenz mod Spiegelung. Für n = 31 gibt es 4 verschiedene Sequenzen, bzw. 8 Stück wenn Spiegelungen unterschieden werden.
Manki E. schrieb: > Nochmal zum MItkommen für Langsame: JEDER Satellit in > der Umlaufbahn hat eine FIXE Sequenznummer, die sich > nicht ändert. Hmm, ja... nehmen wir als Beispiele mal zwei Sequenzen, nämlich (110000) und (101000). Bei der Kreuzkorrelation können die Werte 0 und 1 auftreten, in der Autokorrelation jeder Folge jedoch der Wert 2. Das kann man leicht nachrechnen. In der Praxis nimmt man wesentlich längere Folgen, da sind die Unterschiede sehr viel stärker ausgeprägt, d.h. das Maximum der Autokorrelation ist SEHR viel größer als das Maximun der Kreuzkorrelation. > Das werde ich heute hoffentlich nicht im Laufe des > tages verstehen. "...nicht..."? > Der GPS Empfänger kennt zunächst einmal ALLE Sequenzen > ALLER Satelliten. Ja. > Er wartet auf eine Verbindung. Naja... er empfängt. Ja. > Die Frage die sich mir hier stellt ist: Wie wartet er? Einige > von euch sagen, dass er dauernd korreliert. Ja. "Ich aber sage Euch: Er korreliert dauernd." > Aber wie? Ich mein da ist im Prinzip nichts in der Luft außer > Rauschen. Das ist korrekt. > Ich stell mir das gerade so vor: Der Empfänger misst ein > E-Feld (Spannung) eine bestimmte Zeitlang. Stoppt dann, > und digitalisiert diese Spannung in zb 4 Bits, damit er > autokorrelieren kann. Nein, anders. Man kann sich das ungefähr so vorstellen: Der Empfänger nimmt das E-Feld auf, und zwar dauernd. Er macht das kontinuierlich, ohne Unterbrechung. Im GPS-Gerät ist außerdem eine Logik vorhanden, die die Sequenzen aller Satelliten erzeugen kann. Jetzt kommt's: > Die Frage ist: Was korreliert er genau? Die Sequenz die er > empfangen hat mit sich selbst? Nein. Er korreliert das empfangene Rauschen mit der (intern erzeugten) Sequenz des Satelliten, den er gerade empfangen möchte. Er multipliziert also beide Signale und schickt das Ergebnis auf einen Tiefpass (=integriert das Ergebnis). Das ist übrigens die Kreuzkorrelation. > Angenommen das stimmt, dann bekommt er zwei Werte raus: > einmal 0 und einmal 1. Nein, auch nicht. Hinter dem Tiefpass liegt eine Spannung an. Die Spannung ist analog, d.h. kann beliebige positive und negative Zwischenwerte annehmen. > Aber was macht er jetzt damit genau? Naja, es passiert folgendes: Da die lokal erzeugte Folge sicher nicht sofort synchron zur (im Rauschen versteckten) empfangenen Folge sein wird - das wäre ja enormer Zufall -, schwankt der Korrelationskoeffizient (=die Spannung hinter dem Tiefpass) um Null herum. Der Empfänger probiert das eine Weile, und wenn er merkt, dass es nix wird mit der Korrelation, macht er bei der internen Folgenerzeugung eine winzige Pause, so dass sich die Phasenlage zwischen der intern erzeugten und der empfangenen (im Rauschen versteckten) Folge um z.B. eine halbe Bitzelle verschiebt. Die Folgenerzeugung, der Empfang und die Korrelation laufen natürlich kontinuierlich weiter. Jetzt wartet das GPS-Gerät wieder und beobachtet den Korrelationskoeffizienten (=die Spannung hinter dem Tiefpass). Wenn sie weiterhin nur um Null schwankt, verschiebt er die intern erzeugte Folge wiederum um eine halbe Bitzelle, und so weiter. Irgendwann, wenn er das lange genug gemacht hat, wird die intern erzeugte Folge mit der empfangenen ungefähr synchron laufen. Das ist der Moment, in dem die Spannung hinter dem Tiefpass langsam, aber stetig ansteigt. Jetzt weiss der Empfänger, dass er ganz nahe am verborgenen Schatz dran ist. Durch geringes Variieren der Geschwindigkeit der intern erzeugten Folge versucht der Empfänger, den Korrelations- koeffizienten auf ein Maximum zu bringen und dort zu halten. Wenn er das geschafft hat, hat der Empfänger die vom Satelliten erzeugte Folge RAUSCHFREI und IN DER RICHTIGEN ZEITLICHEN LAGE zur Verfügung! Kein Empfänger der Welt kann das schwache, vom Satelliten gesendete Signal DIREKT in der erforderlichen Weise rauschfrei verstärken. Deshalb erzeugt der Empfänger sich eine perfekte Kopie und reguliert sie, geleitet vom Korrelationskoeffizienten, genau synchron zur empfangenen Folge. Korrelationsempfang ist Magie: Man kann das Signal nicht sehen - aber man weiss, dass es da ist! Man sieht nur den Korrelationskoeffizienten - aber das genügt ja :) > Beachte, dass hier nur ein einziger Satellit sendet. Was wenn > nur der zweite Satellit sendet? Da kommt dann wieder 0 oder 1 > raus, je nachdem um wieviel Bits verschoben die Sequenzen > ankommen. Man wüsste also nicht ob das der eine oder andere > Satellit ist. Hä?! Kann das sein, dass Du übersehen hast, dass bei der Korrelation ein INTEGRAL beteiligt ist? Die empfangene (im Rauschen versteckte) Folge und die lokal erzeugte (rauschfreie) Vergleichsfolge werden multipliziert und anschließend INTEGRIERT (=zeitlich gemittelt). Wenn die empfangene Folge und die Vergleichsfolge verschieden sind, schwankt dieser zeitliche Mittelwert um Null herum. Wenn die empfangene Folge und die Vergleichsfolge IDENTISCH, aber ZEITLICH VERSCHOBEN sind, schwankt der zeitliche Mittelwert um Null herum. Wenn die empfangene Folge und die Vergleichsfolge IDENTISCH sind und SYNCHRON (=gleichzeitig, in gleicher Phase) laufen, DANN UND NUR DANN wird zeitliche Mittelwert positiv und viel größer als Null. > Irgendwie verstehe ich den ganzen Sinn dahinter noch nicht > ganz. Das merkt man. Nicht übelnehmen... Drei Anmerkungen noch: 1) Der geneigte Leser bemerkt leicht, dass sowohl die Auto- wie auch die Kreuzkorrelation eine Rolle spielen. Jede einzelne Folge wird anhand ihrer Autokorrelationsfunktion erkannt; die verschiedenen Folgen dürfen aber nicht kreuzkorrelieren, damit sie sich nicht beim Empfang gegenseitig stören. Das wird beim Festlegen der Folgen berücksichtigt. 2) Zur Positionsbestimmung werden ja Laufzeiten ausgewertet; man wird also so viele Korrelatoren benötigen, wie Satelliten gleichzeitg empfangen werden sollen. Das sind mindestens vier, gern aber auch mehr. Der Aufwand ist, wie man sieht, recht beträchtlich. 3) Oben habe ich eine theoretisch denkbare und vereinfachte Arbeitsweise beschrieben. Da in der Praxis noch zahlreiche weitere Effekte eine Rolle spielen (z.B. der Dopplereffekt), arbeiten echte GPS-Empfänger im Detail anders. Das ändert aber nichts an den grundlegenden Ideen. Ich hoffe, es hilft weiter.
Johann L. schrieb: > wie man enstsprechende Sequenzen erstellt weiß ich immer > noch net. > > Ist eine solche Sequenz c_0.. c_{n-1} gegeben, 1) Was sind "entsprechende", "solche" Sequenzen? Vermutlich suchst Du nach (binären) Folgen mit zweiwertiger AKF?! Die zweiwertige AKF ist, damit es für Dich etwas spannender wird, zwar eine hinreichende, aber keine notwendige Bedingung für die technische Anwendung. M.a.W: Man kann auch mehrwertige AKF zulassen, wenn das Verhältnis des Hauptwertes zu den Nebenwerten gut genug ist. 2) Dass einzelne Folgen mit guter AKF nutzlos sind, hast Du weiter oben selbst schon gesagt. Interessant sind Mengen solcher Folgen mit passender AKF und KKF. 3) m-Sequenzen werden i.d.R. mit Schieberegistern erzeugt; man betrachtet also nur Folgen der Länge n = 2^r - 1 (mit natürlichem r > 0). Das hattest Du doch oben schon mal angefangen. Warum hast Du den Weg wieder verlassen? 4) Das ist nicht als persönlicher Angriff gemeint, aber warum müssen Mathematiker eigentlich immer auch triviale und einfach verständliche Sachverhalten in einem Symbolwust ersäufen? Beweisen ist ja nur die eine Sache. Eine andere ist erklären. Eine Erklärung, die nur der verstehen kann, der den Sachverhalt bereits verstanden hat, ist nutzlos.
:
Bearbeitet durch User
Angehängte Dateien:
-
corr-43.svg
3,6 KB
Reinier Z. schrieb: > Johann L. schrieb: > >> wie man enstsprechende Sequenzen erstellt weiß ich immer >> noch net. >> >> Ist eine solche Sequenz c_0.. c_{n-1} gegeben, > > 1) > Was sind "entsprechende", "solche" Sequenzen? Eine Folge wie im OP: Eine Folge der Länge n aus -1 und 1. Bezeichnet c die Folge und c <<< k die um k Stellen rotierte Folge, dann sind folgende Bedingungen zu erfüllen ("*" ist Standard-Skalarprodukt): (c <<< k) * (c <<< j) = n falls k = j (trivial) und -1 falls k != j. > Vermutlich suchst Du nach (binären) Folgen mit > zweiwertiger AKF?! Diese Bedingung ist ja nicht hinreichend. > Die zweiwertige AKF ist, damit es für Dich etwas spannender > wird, zwar eine hinreichende, aber keine notwendige > Bedingung für die technische Anwendung. M.a.W: Man kann > auch mehrwertige AKF zulassen, wenn das Verhältnis des > Hauptwertes zu den Nebenwerten gut genug ist. Folgendes sieht ganz interessant aus; wird aber noch dauern bis ich das näher anschauen kann: http://ipnpr.jpl.nasa.gov/progress_report/42-82/82O.PDF > 3) > m-Sequenzen werden i.d.R. mit Schieberegistern erzeugt; > man betrachtet also nur Folgen der Länge n = 2^r - 1 Ja, evtl. kann man die Folgebn so implementieren. Wie ich oben bereits schrieb, ist diese Implementierung effizient, aber dadurch gelangt man weder zu einem besseren Verständnis noch wird klar, ob für gegebenes r eine Folge überhaupt existiert. Notwendig scheint r = 3 mod 4 zu sein. > Das hattest Du doch oben schon mal angefangen. Warum > hast Du den Weg wieder verlassen? Das Muster, für welche r es Sequenzen gibt, ist ja unregelmäßig. r = 3 mod 4 würd ich ja noch akzeptieren, aber dass bei 27 eine Lücke ist ist schon seltsam. (Bei 39 scheint auch eine zu sein). > 4) > Das ist nicht als persönlicher Angriff gemeint, aber warum > müssen Mathematiker eigentlich immer auch triviale und > einfach verständliche Sachverhalten in einem Symbolwust > ersäufen? Es also LFSR hinzuschreiben ist wie gesagt nicht erhellend, um mehr darüber zu erfahren kann man die allwissende Müllhalde befragen, und dazu ist es hilfreich, eine Vorstellung von der "Mechanik" der Folge zu bekommen. E- und Nachrichtentechniker wissen das alles bestimmt auswendig und im Schlaf... bei mir ist das nicht so (und wenn du den NASA-Artikel überfliegst, wirst du sehen, dass es eher algebraisch formuliert ist denn LFSR-ig. Matzematische Notation ist einerseits eindeutig und klar verständlich, andererseits dem Problem besser angemessen als Prosa: Die Folge c << 1, die aus c durch 1-maliges Rotieren hervorgeht, lässt sich darstellen als c <<< 1 = M * c Mit einer Matrix M. Entsprechend stellt sich die k-fach rotierte Folge dar als
Die Bedingung an die Autokorrelation ist also
c liegt also im orthogonalen Komplement von (M^2-M)c, dem von (M^3-M)c usw., und vielleicht hat man ja Glück und c liegt sogar im Nullraum von M^2-M und dem von M^3-M etc., dann könnte c recht einfach bestimmt werden. Vielleicht kommt man auch mit der Matrix C weiter, welche man aus den Vektoren c<<<k aufbaut. Die Eigenvektoren dieser Matrix sind ja bekannt, fehlt nur noch das Spektrum von C um C selbst zu bestimmen. Immerhin sind schon mal die Beträge der Eigenwerte bekannt, bleiben noch (n-1)/2 Unbekannte :-(( Ob man das genze über den komplexen Zahlen betrachtet (bzw. Kreisteilungskörper) oder über einem endlichen Körper GF(p^n), den man als Vektorraum über GF(p) betrachtet, macht bis hierhin kaum einen Unterschied. Die längste Folge, die ich gefunden hab, hat Länge 43 (siehe Grafik).
> Bedingung
(c <<< k) * (c <<< j) = n falls k = j (trivial) und -1 falls k != j.
Damit kommt man natuerlich nur auf kurze Folgen. Die verwendeten Folgen
sind aber eher laenger. Das GPS verwendet meines Wissen 8 bit Folgen,
mit einer Laenge von 256 bit.
:
Bearbeitet durch User
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.