Czy istnieje kod binarny o długości 6, rozmiarze 32 i odległości 2?

9

Problem polega na udowodnieniu lub obaleniu istnienia , st, ; ; . ( oznacza odległość uderzenia) $C$ $|c| = 6,\forall c\in C$ $|C| = 32$ $d(c_i,c_j)\geq2,1\leq i<j\leq32$ $d$

Próbowałem skonstruować satysfakcjonujący kod. Najlepsze, co mogę uzyskać, to pozwolić , połączenie , która ma rozmiar 16. 32 to teoretyczna górna granica wielkości, teraz nie nie wiem, co robić dalej, aby rozwiązać problem. $C = C'\times C'$ $C' = \{000,011,110,101\}$

information-theory coding-theory encoding-scheme Miangu
źródło

9

Tak, jest taki zestaw. Właściwie jesteś na dobrej drodze, aby znaleźć następujący przykład.

Niech . Możesz sprawdzić następujące elementy. $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$

$|C|=32$ .
$d(u,v)\geq2$ dla wszystkich , . (W rzeczywistości lub 4 lub 6.) $u,v\in C$ $u\not=v$ $d(u,v)=2$

Oto cztery powiązane ćwiczenia, wymienione w kolejności rosnących trudności. Jak w pytaniu dotyczy tylko kodu binarnego.

Ćwiczenie 1. Podaj kolejny przykład zestawu 32 słów o długości 6 i odległości par co najmniej 2.

Ćwiczenie 2. Pokaż, że istnieją tylko dwa takie zestawy, jak podano w odpowiedzi i ćwiczeniu 1.

Ćwiczenie 3. Uogólnij powyższe na słowa o dowolnej długości i odległości w parach co najmniej 2. (Wskazówka, .) $32=2^{6-1}$

Ćwiczenie 4. (dalsze uogólnienie określone w odpowiedzi Yuvala) Jeśli jest maksymalnym rozmiarem kodu o długości i minimalnej odległości pary , to . $A(n,d)$ $n$ $d$ $A(d,2d)=A(n-1,2d-1)$

John L.
źródło

1

Myślę, że może również wynosić 6, szczególnie dla i , ponieważ zarówno i ponieważ oba mają parzystą liczbę 1. A może coś mi brakuje?

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, dzięki. Zaktualizowano

John L.

@Miangu Czy moja odpowiedź była pomocna? Czy zastanawiałeś się nad tym? (Ten komentarz zostanie usunięty po otrzymaniu opinii).

John L.

7

Wszystkie słowa o parzystej parzystości z kodu liniowego zawierającego słowa kodowe i minimalną odległość . $2^{n-1}$ $2$

Mówiąc bardziej ogólnie, jeśli jest maksymalnym rozmiarem kodu o długości i minimalnej odległości , to . $A_2(n,d)$ $n$ $d$ $A_2(n,2d) = A_2(n-1,2d-1)$

Yuval Filmus
źródło

1

Niezły fakt, głosowano. Nawiasem mówiąc, dlaczego nie tylko zamiast ? Och, dwie litery.

A (n, d)

$A(n,d)$

A_{2} (n, d)

$A_2(n,d)$

John L.

1

Indeks dolny oznacza pole .

F_{2}

$\mathbb{F}_2$

Yuval Filmus

Czy istnieje kod binarny o długości 6, rozmiarze 32 i odległości 2?

Odpowiedzi: