heute ist der Geburtstag von
Gabriel Cramer (31.07.1704 - 04.01.1752)


Auf das Thema antworten  [ 11 Beiträge ] 
SS09: 10. Übung am 9.6.2009 
Autor Nachricht

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag SS09: 10. Übung am 9.6.2009
Beispiel 3:
Fehler in einer einzelnen Stelle erkennen bedeutet, dass je 2 Codeworte Hamming-Abstand von mindestens 2 haben müssen.
Ein (4,M,2)-Code kann auf jedenfall höchstens 8 Codeworte haben, also M <= 8. Weil: wenn man von jedem Codewort die letzte Stelle streicht haben je 2 Codeworte immer noch Abstand 1. Also gibt es eine injektive Abbildung von C nach {0,1}^3 - also M=|C|<=8. Siehe Satz 1.0.2 (Singleton-Schranke).
Diese Schranke wird bei d=2 auch immer erreicht. Dazu führt man ein Paritätsbit ein.
P(abc) := Anzahl der 1er in abc, modulo 2
(oder allgemein P(a1,...,an) := summe der a_i (mod q))
C := {abcd | a,b,c binär, d=P(abc)}
|C|=8
z.z: d(C)>=2
sei ABCD, EFGH aus C beliebig mit ABCD != EFGH.
z.z: d(ABCD,EFGH) > 1
Jedenfalls gilt auch ABC != EFG da die letzte stelle eine funktion der ersten 3 stellen ist.
Fall 1: d(ABC,EFG) > 1
=> fertig, weil dann d(ABCD,EFGH) > 1
Fall 2: d(ABC,EFG) = 1
=> P(ABC) != P(EFG) => d(ABCD,EFGH)=2


Do 04-06-2009 13:55:58
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
Beispiel 5 ist auch easy...
gleicher Schmäh wie bei Beispiel 3.
Wegen Singleton-Schranke ist M<=q^2
M=q^2 wenn man wieder die Paritätsfunktion benutzt
Argumentation genauso wie bei Beispiel 3
Triadischer-Code:
000
011
022
101
112
120
202
210
221
Bew:
das 3.Bit ist Paritätsbit.


Sa 06-06-2009 15:25:41
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 107
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
hat jemand eine idee zu beispiel 2 oder 4?


So 07-06-2009 11:11:10
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 05/2008
Beiträge: 27 + 12
Wohnort: Wien West
Studium: (alt) Bachelor Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
1 a,b,c existiert ein Code
1 d,e existiert kein Code

bei 5. hab ich die selbe lösung wie "kater"

jop, beim 2er hab ich was, beim 4er auch aber ich find es zach zum Argumentieren, deswegen kreuz ichs möglicherweise nicht an..

den 2er stell ich mal online:


Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.


Mo 08-06-2009 20:51:53
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
cool, dann ham wir jetzt alle beispiele!

bsp. 1,3,5 sind von mir
bsp. 4 ist von maria
bsp. 2 ist von Adem

~TeXed by kater~

EDIT: jetzt noch fehlerfreier...
EDIT2: Jetzt mit vereinfachtem Beispiel 2


Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.


Zuletzt geändert von kater am Di 09-06-2009 07:27:57, insgesamt 1-mal geändert.



Mo 08-06-2009 21:32:12
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 10/2007
Beiträge: 27 + 109
Studium: (alt) Master Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
4. Beispiel
Behauptung: w, w' binäre Wörter. Dann gilt: P(w)=P(w') folgt d(w,w')=0 mod 2
( P... Parität )
Beweis: durchdenken, wenn jemand Probleme damit hat nochmal melden :)

z.z. sei d ungerade, dann gilt:
es Existiert (n,M,d)-Code gdw es Existiert (n+1,M,d+1)-Code

<- Entferne von allen Wörtern das erste bit, damit bleibt der abstand der wörter >= d

-> Füge zu jedem Wort die Parität hinzu (also 0, wenn P(w)=0, 1, wenn P(w)=1)
Damit haben alle Wörter Parität 0, also muss die Distanz der Wörter gerade sein.
Außerdem muss die distanz >= d sein, weil durch hinzufügen eines bits sie nicht kleiner wird.
Weil d ungerade ist muss die distanz also mindestens d+1 sein -> fertig


Mo 08-06-2009 21:37:38
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
hmm, gibt es etwa eine einfachere möglichkeit "P(a)=P(b) <=> d(a,b) gerade" zu beweisen also so, wie ich es ins PDF geschrieben habe?
P(a)+d(a,b)=P(b) (mod 2)
weil wenn d(a,b) gerade, ändere ich eine gerade anzahl von bits um von a zu b zu kommen und damit bleibt die parität gleich.
ich verstehs schon... ist halt weniger sauber die argumentation also wird sie unserem prof wahrscheinlich besser gefallen :x
ich bleib trotzdem bei meiner version :P


Mo 08-06-2009 22:00:40
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 10/2007
Beiträge: 27 + 109
Studium: (alt) Master Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
hab das pdf zu spät gesehn und geglaubt, das 4er fehlt noch.
Jetzt hat man sogar eine auswahl :mrgreen:


Mo 08-06-2009 22:02:46
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
highstick hat geschrieben:
Jetzt hat man sogar eine auswahl :mrgreen:

^^was für ein luxus. das ist ja schon ein 5-sterne-forum hier. wir sollten eine benutzungsgebühr eintreiben! 8)


Mo 08-06-2009 22:13:06
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 05/2008
Beiträge: 27 + 12
Wohnort: Wien West
Studium: (alt) Bachelor Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
Hab auch noch eine eigene version vom 4er, bin aber grad nicht daheim.. :)


Mo 08-06-2009 23:07:38
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 10. Übung am 9.6.2009
heute in der nacht ist mir eingefallen, wie man beispiel 2 noch vereinfachen kann... (siehe pdf) :mrgreen:


Di 09-06-2009 07:28:54
Diesen Beitrag melden
Profil
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Auf das Thema antworten   [ 11 Beiträge ] 


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Du darfst neue Themen in diesem Forum erstellen.
Du darfst Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
Powered by phpBB © phpBB Group.  |  Designed by STSoftware for PTF  |  © Czechnology 2007 - 2021  |  Deutsche Übersetzung durch phpBB.de