Существует ли двоичный код длиной 6, размером 32 и расстоянием 2?

9

Задача состоит в том, чтобы доказать или опровергнуть существование , st, ; ; . ( обозначает расстояние Хэмминга) $C$ $|c| = 6,\forall c\in C$ $|C| = 32$ $d(c_i,c_j)\geq2,1\leq i<j\leq32$ $d$

Я пытался построить удовлетворительный код. Лучшее, что я могу получить, это позволить $C = C'\times C'$ , конкатенация $C' = \{000,011,110,101\}$ , размер 16. 32 - теоретическая верхняя граница размера, теперь я надеваю не знаю, что делать дальше, чтобы решить проблему.

information-theory coding-theory encoding-scheme Miangu
источник

9

Да, такой набор есть. Вы на правильном пути, чтобы найти следующий пример.

Пусть . Вы можете проверить следующее. $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$

$|C|=32$ .
$d(u,v)\geq2$ для всех , . (На самом деле, или 4 или 6.) $u,v\in C$ $u\not=v$ $d(u,v)=2$

Вот четыре связанных упражнения, перечисленных в порядке возрастания сложности. Как и в вопросе, речь идет только о двоичном коде.

Упражнение 1. Приведите еще один пример набора из 32 слов длиной 6 и парным расстоянием не менее 2.

Упражнение 2. Покажите, что существует только два таких набора, как указано в ответе и в упражнении 1.

Упражнение 3. Обобщите вышеизложенное для слов любой заданной длины и попарного расстояния не менее 2. (Подсказка, .) $32=2^{6-1}$

Упражнение 4. (дальнейшее обобщение указано в ответе Ювала) Если - максимальный размер кода длины и минимального попарного расстояния , то . $A(n,d)$ $n$ $d$ $A(d,2d)=A(n-1,2d-1)$

Джон Л.
источник

1

Я думаю, что также может быть 6, особенно для и , как и и потому что оба имеют четное число 1. Или я что-то упустил?

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, спасибо. Обновлено.

Джон Л.

@Miangu мой ответ полезен? Рассматривали ли вы принять это?

Джон Л.

7

Все слова четной четности из линейного кода с кодовыми словами и минимальным расстоянием . $2^{n-1}$ $2$

В более общем смысле, если - это максимальный размер кода длины и минимального расстояния , то . $A_2(n,d)$ $n$ $d$ $A_2(n,2d) = A_2(n-1,2d-1)$

Юваль Фильмус
источник

1

Хороший факт, проголосовал. Кстати, почему бы не просто вместо ? О, две буквы.

A (n, d)

$A(n,d)$

A_{2} (n, d)

$A_2(n,d)$

Джон Л.

1

Подстрочный индекс обозначает поле .

F_{2}

$\mathbb{F}_2$

Юваль

Существует ли двоичный код длиной 6, размером 32 и расстоянием 2?

Ответы: