Codierung < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Ich schreibe gerade in einem Seminar eine "kleine" Arbeit zur Codierung.
Gerade bin ich bei den sogenannten Permutationscodes.
Meine Frage ist nun, wozu diese gebraucht werden.
Wo liegt der Vorteil Codes zu permutieren? Ich habe nur gefunden, dass dies zur Speicherplatzkomprimierung dienen soll und dass dies z.B. bei CD's angewendet wird. Aber das ist auch schon alles.
Kann mir hier jemand nur in ein paar kurzen Worten sagen, was da genau passiert und wozu das genau notwendig oder wünschenswert ist.
Vielen Dank
|
|
| |
|
Könntest du dazu wenigstens eine deiner Quellen angeben ?
LG
|
|
|
| |
|
hab probleme mit dem link:
in google "meral arnavut permutation code Eteri Svanidze" einfügen.
erster beitrag und erste seite
Vielleicht sollte ich auch was zu meiner Arbeit schreiben:
ich habe erst die linearen codes eingeführt. anschließend beschäftige ich mich kurz mit der automorphismengruppe eines linearen codes. Danach konstruiere ich mit hilfe der gleichung [mm] x^{q+1}-y^q-y=0 [/mm] zu einem gegebenen endlichen Körper einen hermiteschen-Code H(s) und überprüfe ob verschiedene abbildungen [mm] \in [/mm] Aut(H(s)).
Ich wollte in der einleitung neben der gliederung der Arbeit noch auf den begriff der permutationscodes eingehen. da steck ich aber gerade fest.
|
|
|
| |
|
> in google "meral arnavut permutation code Eteri Svanidze"
> einfügen.
Hallo lustigerhurz,
beim Googeln bin ich auch noch auf etwas gestoßen, was
vermutlich die erste Autorin betrifft: ![[]](/images/popup.gif) Rating
Das ist leider nicht besonders motivierend ...
LG Al-Chw.
|
|
|
| |
|
uiui. Das nenne ich mal eine schlechte Bewertung :-D
Naja vielleicht war ich dann auch auf dem Holzweg. Aber weiter bin ich immernoch nicht.
Was für einen Nutzen bringen mir denn Permutationscodes?
|
|
|
| |
|
> uiui. Das nenne ich mal eine schlechte Bewertung :-D
sagt über die Qualität ihrer Paper zwar eigentlich nichts
aus ...
vielleicht denkt und schreibt sie besser als sie vorträgt 
> Naja vielleicht war ich dann auch auf dem Holzweg. Aber
> weiter bin ich immernoch nicht.
> Was für einen Nutzen bringen mir denn Permutationscodes?
Mir ist nur noch nicht klar, was unter einem Permutations-
Code überhaupt zu verstehen ist. Vielleicht laufen die ja
auch noch unter etwas anderen Bezeichnungen ?
An derselben Uni wie Meral Arnavut gibt es noch einen
Ziya Arnavut (ev. der Vater von Meral ?), der sich seit
langer Zeit mit Kompressionsalgorithmen befasst hat.
Er wird mit einer seiner Arbeiten auch zitiert in einem
Papier über den Burrows-Wheeler Compression Algorithm:
www.juergen-abel.info/Preprints/Preprint_Grundlagen_BWCA.pdf
Vielleicht hilft auch dieser Link weiter:
http://de.wikipedia.org/wiki/Burrows-Wheeler-Transformation
LG Al-Chw.
|
|
|
| |
|
hmm, nein. Das hilft mir nicht weiter.
Ich stelle meine Frage nochmals anders:
Welche Rolle spielt die Permutation bei der Codierung?
Was stellt eine Permutation mit einem linearen Code an. Welche Vorteile resultieren daraus. Wo hat das seine Anwendung?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:03 Sa 31.12.2011 | | Autor: | Infinit |
Hallo,
werfe mal einen Blick in meine Antwort, das sollte weiterhelfen.
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:30 So 01.01.2012 | | Autor: | felixf |
Moin!
> hab probleme mit dem link:
> in google "meral arnavut permutation code Eteri Svanidze"
> einfügen.
> erster beitrag und erste seite
Wow, ich muss ja echt sagen, Theorem 3.5 ist voll der Brueller. Ob die dafuer wohl die naechste Fields-Medallie bekommen? Und Corollary 3.6 erst... Das ganze wird nur noch von Theorem 3.7 uebertroffen.
Es ist immer wieder erstaunlich, was fuer Trivialitaeten von manchen Leuten als Theoreme bezeichnet werden...
> Vielleicht sollte ich auch was zu meiner Arbeit schreiben:
> ich habe erst die linearen codes eingeführt.
> anschließend beschäftige ich mich kurz mit der
> automorphismengruppe eines linearen codes. Danach
> konstruiere ich mit hilfe der gleichung [mm]x^{q+1}-y^q-y=0[/mm] zu
> einem gegebenen endlichen Körper einen hermiteschen-Code
> H(s) und überprüfe ob verschiedene abbildungen [mm]\in[/mm]
> Aut(H(s)).
> Ich wollte in der einleitung neben der gliederung der
> Arbeit noch auf den begriff der permutationscodes eingehen.
> da steck ich aber gerade fest.
Warum willst du umbedingt etwas ueber Permutationscodes schreiben? Wurde dir das so vorgegeben? Es gibt zig verschiedene Code-Arten, ueber die man etwas interessantes schreiben kann (und wo man recht einfach Anwendungsfaelle angeben kann), warum also ausgerechnet ueber Permutationscodes?
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:54 Sa 31.12.2011 | | Autor: | Infinit |
Hallo lustigerhurz,
den Permutationscode kenne ich zur Kurzbeschreibung eines Sets von Integerzahlen, dessen Inhalt man gemeinsam möglichst kurz und bündig kennzeichnen will, entweder um Speicherplatz zu sparen (heute nicht mehr so relevant wie noch vor 20 Jahren) oder um einen kurzen Übertragungscode zu generieren.
Die dahintersteckende Idee ist, dass man für ein Set, das aus N Zeichen besteht, eben nicht diese Zeichen getrennt abspeichert oder überträgt, sondern mit Hilfe eines Permutationsindexes beschreibt. Die Zuordnung solch eines Index zu einer bestimmten Reihenfolge an Einzelwerten muss einmal geschehen und sie ist auch im Empfänger bekannt. Demzufolge genügt es, diesen Index zu übertragen anstelle der Einzelwerte. Gerade in der digitalen Video- und Audiocodierung, die ja mit quantisierten Werten arbeitet, die wiederum durch einen Index in der Quantisierungstabelle beschrieben werden, lässt sich so Übertragungskapazität sparen.
Viele Grüße,
Infinit
|
|
|
| |
|
Vielen Dank, das geht genau in die Richtung die mich interessiert. Nur ganz verstanden habe ich das glaube ich noch nicht.
Ich versteh das jetzt so:
Anstatt eine Menge von Informationen zu verschicken, wird nur jeweils die Permutationsvorschrift verschickt, da dies weniger Speicher verbraucht und die Übertragungsgeschwindigkeit hoch ist.
Gerade der mathematischen Zusammenhang fehlt mir.
Bei Codes gibt es ja die Automorphismengruppe. Diese ist ja eine Menge von Abbildungen/Permutationen, welche angewandt auf Codewörter wieder Codewörter sind.
Jetzt ist meine Frage, wie hängt das mit dem zusammen, was Sie mir gerade erklärt haben?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:22 Sa 31.12.2011 | | Autor: | Infinit |
Hallo,
dass solch ein Automorphismus auftreten kann, leuchtet mir zwar ein, aber in den von mir angegebenen Beispielen findet solch eine Codierung genau einmal statt, nämlich für die Übertragung. Solch eine Selbstabbildung kann demzufolge nicht vorkommen bei diesen Anwendungen. Wenn ich außerdem weiss, und das ist ja immer der Fall, dass ich kein Element der Grundmenge übertrage, sondern einen Index, der zu einer bestimmten Permutation gehört, so kann eine Fehlinterpretation nicht vorkommen.
Viele Grüße,
Infinit
P.S.: Das "Du" wird in diesem Forum gepflegt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:33 So 01.01.2012 | | Autor: | felixf |
Moin Infinit,
> den Permutationscode kenne ich zur Kurzbeschreibung eines
> Sets von Integerzahlen, dessen Inhalt man gemeinsam
> möglichst kurz und bündig kennzeichnen will, entweder um
> Speicherplatz zu sparen (heute nicht mehr so relevant wie
> noch vor 20 Jahren) oder um einen kurzen Übertragungscode
> zu generieren.
ich vermute, dass es nicht um Permutationscodes in diesem Sinne geht. lustigerhurz scheint eine Arbeit ueber Codes im Sinne der Codierungstheorie (und nicht im Sinne der Datenkompression). Sprich: die Daten sollen aufgeblaeht werden, so dass man sie trotz Fehler bei der Uebertragung moeglichst noch rekonsturieren kann, und nicht geschrumpft werden.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:30 Mo 02.01.2012 | | Autor: | Infinit |
Hallo Felix,
nachdem ich den Parallelbeitrag von lustigerhurz gelesen hatte, kam mir diese Idee auch, aber da hatte ich schon meinen Beitrag abgesetzt und er hatte auch schon positiv darauf reagiert.
Tja. so schnell kann man auf die falsche Bahn kommen, aber vielleicht äußert sich lustigerhurz ja noch mal dazu.
Viele Grüße und ein gutes neues Jahr,
Infinit
|
|
|
| |
|
Ich wünsch euch allen erstmal einen guten Start ins neue Jahr 
felixf hat Recht. Meine Arbeit hat den Schwerpunkt "Codierungstheorie".
Hier nochmal eine Kurzfassung meiner Gliederung:
-endl Körper
-Lineare Codes
-Einführung in Gruppen und Permutationen
-Automorphismengruppe eines Codes
-Hermitesche Codes
Ich weiß nun nur nicht, was die Permutationen für eine Rolle spielen und wofür die Automorphismengruppe eines Codes gut sein soll.
@felixf:
>...die Daten sollen aufgeblaeht werden, so dass man sie trotz Fehler bei >der Uebertragung moeglichst noch rekonsturieren kann, und nicht >geschrumpft werden. ...
Was bedeutet das genau?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:54 Mo 02.01.2012 | | Autor: | Infinit |
Hallo,
auch Dir ein gutes neues Jahr.
Den Kommentar von Felix verstehe ich schon:
Ich war davon ausgegangen, dass dieser Permutationscode zur Datenkompression eingesetzt werden soll (was man übrigens auch macht), indem eben nur der Index solch einer Permutation übertragen wird und nicht das zu dieser Permutation gehörende Datenset.
Bei Dir geht es allerdings um die Möglichkeiten einer Datenkorrektur im Falle einer fehlerhaften Abspeicherung bzw. Übertragung. Hierzu muss man dem ursprünglichen Datenset etwas hinzufügen (die berühmtem RS-Blockcodes machen dies ja auch so), um Redundanz in den Datensatz zu bringen. Damit vergrößert sich der Datensatz um genau die Informationen,die dazubeitragen, einen eventuell auftretenden Fehler wieder zu korrigieren.
Diese beiden Aspekte, Nutzung zur Datenkompression durch Übertragung des Index sowie Redundanzhinzufügung zur Fehlerkorrektur, hatte Felix gemeint, wenn er vom Schrumpfen bzw. vom Aufblähen sprach.
Viele Grüße,
Infinit
|
|
|
| |
|
Okay, ich verstehe dass man einer Nachricht eine gewisse Art von Redundanz hinzufügt, um möglichst viele Fehler zu erkennen und wenn möglich diese auch zu korrigieren.
Aber wo spielen hier Permutationen eine Rolle, mal abgesehen von einer Umordnung der Info buw Prüfbits?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:47 Mo 02.01.2012 | | Autor: | Infinit |
Hallo lustigerhurz,
jetzt muss ich mit (m)einer Antwort etwas vorsichtig sein, um hier nicht noch mehr Verwirrung reinzubringen.
Viele der Codes zur Fehlerkorrektur leiden daran, dass ein Fehlerburst, also die gestörte Übertragung aufeinanderfolgender Daten, nicht sehr effizient bekämpft werden kann. Aus diesem Grunde führt man vor der Durchführung der Fehlersicherung ein Interleaving ein, so dass aufeianderfolgende Daten nicht aufeinanderfolgend mit dem Fehlersicherungsverfahren behandelt werden. Die Idee dahinter ist, solch einen Fehlerburst, falls er auf der Übertragungsstrecke entsteht, auseinanderzureißen und damit für die Fehlerkorrektur auf der Empfängerseite wieder handhabbar zu machen. Der technische Begriff hierfür ist das Interleaving, mathematisch betrachtet führst Du eine Permutation Deines Datensatzes durch, die Reihenfolge der Daten ändert sich. Ich muss allerdings gestehen, dass ich den Namen einer Permutationscodierung für diese zwei Schritte (Interleaving der Daten und anschließende Fehlersicherung bsp. durch Faltungs- oder Blockcodes) so noch nicht gehört habe. Beim Googeln fand ich jedoch solch eine Begriffskombination und vieleicht hift Dir das dazugehörige Dokument etwas weiter. Schau mal auf Seite 11 hier.
Wie gesagt, bitte vorsichtig genießen, da ich nicht weiß, ob dies in die von Dir angedachte Richtung geht.
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Mo 02.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
