Existiert ein Binärcode mit Länge 6, Größe 32 und Abstand 2?

9

Das Problem besteht darin, die Existenz von , st, zu beweisen oder zu widerlegen ; ; . ( steht für Hamming Distance) $C$ $|c| = 6,\forall c\in C$ $|C| = 32$ $d(c_i,c_j)\geq2,1\leq i<j\leq32$ $d$

Ich habe versucht, einen zufriedenstellenden Code zu erstellen. Das Beste, was ich bekommen kann, ist, , eine Verkettung von , die die Größe 16 hat. 32 ist zufällig die theoretische Obergrenze der Größe, jetzt ich an Ich weiß nicht, was ich als nächstes tun soll, um das Problem zu lösen. $C = C'\times C'$ $C' = \{000,011,110,101\}$

information-theory coding-theory encoding-scheme Miangu
quelle

9

Ja, es gibt so einen Satz. Sie sind tatsächlich auf dem richtigen Weg, um das folgende Beispiel zu finden.

Sei . Sie können Folgendes überprüfen. $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$

$|C|=32$ .
$d(u,v)\geq2$ für alle , . (Tatsächlich ist oder 4 oder 6.) $u,v\in C$ $u\not=v$ $d(u,v)=2$

Hier sind vier verwandte Übungen, die in der Reihenfolge der zunehmenden Schwierigkeit aufgeführt sind. Wie in der Frage ist nur Binärcode betroffen.

Übung 1. Geben Sie ein weiteres Beispiel für einen Satz von 32 Wörtern mit einer Länge von 6 und einem paarweisen Abstand von mindestens 2.

Übung 2. Zeigen Sie, dass es nur zwei solcher Sätze gibt, wie in der Antwort und in Übung 1 angegeben.

Übung 3. Verallgemeinern Sie das Obige auf Wörter beliebiger Länge und paarweisen Abstands von mindestens 2. (Hinweis, .) $32=2^{6-1}$

Aufgabe 4. (weitere Verallgemeinerung in Yuvals Antwort angegeben) Wenn die maximale Größe eines Codes mit der Länge und dem minimalen paarweisen Abstand , dann ist . $A(n,d)$ $n$ $d$ $A(d,2d)=A(n-1,2d-1)$

John L.
quelle

1

Ich denke, kann auch 6 sein, speziell für und , da sowohl als auch weil beide eine gerade Anzahl von haben. Oder fehlt mir etwas?

d (u, v)

$d(u,v)$

u = 000000

$u=000000$

v = 111111

$v=111111$

u \in C

$u\in C$

v \in C

$v\in C$

Siegi

@siegi, danke. Aktualisiert.

John L.

7

Alle Wörter gleicher Parität aus einem linearen Code mit Codewörtern und Mindestabstand . $2^{n-1}$ $2$

Allgemeiner , wenn die maximale Größe eines Codes mit der Länge und dem minimalen Abstand , dann ist . $A_2(n,d)$ $n$ $d$ $A_2(n,2d) = A_2(n-1,2d-1)$

Yuval Filmus
quelle

1

Schöne Tatsache, positiv bewertet. Warum nicht einfach statt ? Oh, zwei Buchstaben.

A (n, d)

$A(n,d)$

A_{2} (n, d)

$A_2(n,d)$

John L.

1

Der Index kennzeichnet das Feld .

F_{2}

$\mathbb{F}_2$

Yuval Filmus

Existiert ein Binärcode mit Länge 6, Größe 32 und Abstand 2?

Antworten: