Codierungsth. Kugelpackungen < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:52 So 09.11.2014 | | Autor: | riju |
| Aufgabe | Seinen K ein Alphabet und r [mm] \in \IN_{0}. [/mm] Für u [mm] \in K^{n} [/mm] definiert [mm] B_{r}(u)={v|v \in K^{n}, d(u,v) \le r} [/mm] die Kugel vom Radius r um den Mittelpunkt u in [mm] K^{n}. [/mm] Ist |K|=q, so gilt [mm] |B_{r}(u)|=\summe_{j=0}^{r}\vektor{n\\ j}(q-1)^{j}, [/mm] denn |{v|v [mm] \in K^{n}, d(u,v)=j}|=\vektor{n\\ j}(q-1)^{j}. [/mm] Insbesondere ist also [mm] |B_{r}(u)| [/mm] unabhängig vom Mittelpunkt u.
Beweisen Sie: [mm] |B_{r}(u)|=\summe_{j=0}^{r}\vektor{n\\ j}(q-1)^{j} [/mm] |
Ich weiß jetzt nicht so richtig, wie ich das Beweisen soll. Ich weiß, dass es für j Fehlerstellen, j aus n mögliche Positionen für die Fehler gibt. Dabei stehen pro Fehlerstelle q-1 falsche Symbole zur Verfügung. Aber weiter weiß ich leider nicht.
Hat jemand einen Tipp?
Vielen Dank im Voraus.
Liebe Grüße
riju
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:23 Mo 10.11.2014 | | Autor: | felixf |
Moin riju!
> Seinen K ein Alphabet und r [mm]\in \IN_{0}.[/mm] Für u [mm]\in K^{n}[/mm]
> definiert [mm]B_{r}(u)={v|v \in K^{n}, d(u,v) \le r}[/mm] die Kugel
> vom Radius r um den Mittelpunkt u in [mm]K^{n}.[/mm] Ist |K|=q, so
> gilt [mm]|B_{r}(u)|=\summe_{j=0}^{r}\vektor{n\\ j}(q-1)^{j},[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> denn |{v|v [mm]\in K^{n}, d(u,v)=j}|=\vektor{n\\ j}(q-1)^{j}.[/mm]
> Insbesondere ist also [mm]|B_{r}(u)|[/mm] unabhängig vom
> Mittelpunkt u.
>
> Beweisen Sie: [mm]|B_{r}(u)|=\summe_{j=0}^{r}\vektor{n\\ j}(q-1)^{j}[/mm]
Setzen wir doch mal [mm] $R_j(u) [/mm] := [mm] \{ v \mid v \in K^n, \; d(u, v) = j \}$ [/mm] fuer ein beliebiges $j [mm] \in \IN$.
[/mm]
> Ich weiß jetzt nicht so richtig, wie ich das Beweisen
> soll. Ich weiß, dass es für j Fehlerstellen, j aus n
> mögliche Positionen für die Fehler gibt. Dabei stehen pro
> Fehlerstelle q-1 falsche Symbole zur Verfügung.
Das zeigt [mm] $|R_j(u)| [/mm] = [mm] \binom{n}{j} [/mm] (q - [mm] 1)^j$. [/mm] Oder?
Jetzt musst du zeigen, dass [mm] $B_r(u)$ [/mm] die disjunkte Vereinigung von [mm] $R_0(u), R_1(u), \dots, R_r(u)$ [/mm] ist. Daraus folgt dann die Formel fuer [mm] $|B_r(u)|$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 08:53 Di 11.11.2014 | | Autor: | riju |
Das hab ich soweit verstanden.
Eine Menge X ist die disjunkte Vereinigung, wenn [mm] X_{i} \bigcap X_{j} [/mm] = [mm] \emptyset, [/mm] für [mm] i\not=j [/mm] gilt. Das heißt die [mm] X_{i} [/mm] sind also paarweise disjunkt. Außerdem muss ja gelten, dass [mm] X=\bigcup_{i \in I} X_{i}. [/mm] Das heißt X ist die Vereinigung aller Mengen [mm] X_{i}. [/mm]
Also wie zeige ich dann, dass [mm] R_{i}(u) \bigcap R_{j} [/mm] gilt für i [mm] \not= [/mm] j?
Vielen Dank im Voraus.
Lg riju
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:19 Di 11.11.2014 | | Autor: | riju |
Also [mm] R_{i}(u) \cap R_{j}(u) [/mm] = { v|v [mm] \in K^{n}, [/mm] d(u,v)=i [mm] \wedge [/mm] d(u,v)=j }. Das müsste doch laut Definition des Durchschnitts rauskommen oder? Der Abstand von u und v kann ja nur i und j gleichzeitig sein, wenn i=j ist. Da aber gelten muss das [mm] i\not=j [/mm] ist, kann es diesen Durchschnitt niemals geben. Also ist der Durchschnitt für [mm] i\not=j [/mm] immer disjunkt. Oder seh ich das falsch?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:18 Di 11.11.2014 | | Autor: | felixf |
Moin!
> Also [mm]R_{i}(u) \cap R_{j}(u)[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= { v|v [mm]\in K^{n},[/mm] d(u,v)=i
> [mm]\wedge[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
d(u,v)=j }. Das müsste doch laut Definition des
> Durchschnitts rauskommen oder?
Genau.
> Der Abstand von u und v kann
> ja nur i und j gleichzeitig sein, wenn i=j ist. Da aber
> gelten muss das [mm]i\not=j[/mm] ist, kann es diesen Durchschnitt
> niemals geben.
Doch: es gibt den Durchschnitt. Was du sagen willst; da ist nichts drinnen. Sprich, er ist leer.
> Also ist der Durchschnitt für [mm]i\not=j[/mm] immer
> disjunkt.
Der Durchschnitt ist nicht diskunkt sondern leer; die beiden Mengen sind disjunkt 
> Oder seh ich das falsch?
Nein, du hast es nur etwas ungenau ausgedrückt :)
LG Felix
|
|
|
|
