Плоткин связан

В математике теории кодирования граница Плоткина , названная в честь Морриса Плоткина, представляет собой предел (или границу) максимально возможного числа кодовых слов в двоичных кодах заданной длины n и заданного минимального расстояния d .

Заявление о связанности

Код считается «двоичным», если кодовые слова используют символы из двоичного алфавита . В частности, если все кодовые слова имеют фиксированную длину n , то двоичный код имеет длину n . Эквивалентно, в этом случае кодовые слова можно считать элементами векторного пространства над конечным полем . Пусть будет минимальным расстоянием , т.е. ${\displaystyle \{0,1\}}$ ${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle \mathbb {F} _{2}}$ ${\displaystyle d}$ ${\displaystyle C}$

${\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y)}$

где — расстояние Хэмминга между и . Выражение представляет собой максимальное количество возможных кодовых слов в двоичном коде длины и минимального расстояния  . Граница Плоткина накладывает ограничение на это выражение. ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle A_{2}(n,d)}$ ${\displaystyle n}$ ${\displaystyle d}$

Теорема (граница Плоткина):

i) Если четно и , то ${\displaystyle d}$ ${\displaystyle 2d>n}$

${\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}$

ii) Если нечетно и , то ${\displaystyle d}$ ${\displaystyle 2d+1>n}$

${\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d+1}{2d+1-n}}\right\rfloor .}$

iii) Если четно, то ${\displaystyle d}$

${\displaystyle A_{2}(2d,d)\leq 4d.}$

iv) Если нечетно, то ${\displaystyle d}$

${\displaystyle A_{2}(2d+1,d)\leq 4d+4}$

где обозначает функцию пола . ${\displaystyle \left\lfloor ~\right\rfloor }$

Доказательство случая i

Пусть — расстояние Хэмминга и , а — число элементов в (таким образом, равно ). Граница доказывается путем ограничения величины двумя различными способами. ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M}$ ${\displaystyle C}$ ${\displaystyle M}$ ${\displaystyle A_{2}(n,d)}$ ${\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)}$

С одной стороны, есть выборы для и для каждого такого выбора есть выборы для . Так как по определению для всех и ( ), то следует, что ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle M-1}$ ${\displaystyle y}$ ${\displaystyle d(x,y)\geq d}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\neq y}$

${\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)\geq M(M-1)d.}$

С другой стороны, пусть будет матрицей , строки которой являются элементами . Пусть будет числом нулей, содержащихся в '-м столбце . Это означает, что '-й столбец содержит единицы. Каждый выбор нуля и единицы в одном и том же столбце вносит вклад точно (потому что ) в сумму и, следовательно, ${\displaystyle A}$ ${\displaystyle M\times n}$ ${\displaystyle C}$ ${\displaystyle s_{i}}$ ${\displaystyle i}$ ${\displaystyle A}$ ${\displaystyle i}$ ${\displaystyle M-s_{i}}$ ${\displaystyle 2}$ ${\displaystyle d(x,y)=d(y,x)}$ ${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)}$

${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)=\sum _{i=1}^{n}2s_{i}(M-s_{i}).}$

Величина справа максимальна тогда и только тогда, когда выполняется для всех (на этом этапе доказательства мы игнорируем тот факт, что являются целыми числами), тогда ${\displaystyle s_{i}=M/2}$ ${\displaystyle i}$ ${\displaystyle s_{i}}$

${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)\leq {\frac {1}{2}}nM^{2}.}$

Объединяя верхнюю и нижнюю границы, которые мы только что вывели, ${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)}$

${\displaystyle M(M-1)d\leq {\frac {1}{2}}nM^{2}}$

что, учитывая, что это эквивалентно ${\displaystyle 2d>n}$

${\displaystyle M\leq {\frac {2d}{2d-n}}.}$

Так как четно, то следует, что ${\displaystyle M}$

${\displaystyle M\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}$

Это завершает доказательство границы.

Смотрите также

• Алмазный код
• Элиас Бассалиго связан
• Связано Гилберт–Варшамов
• Гризмер связан
• Хэмминг связан
• Джонсон связан
• Синглтон-граница

Ссылки

• Плоткин, Моррис (1960). «Двоичные коды с указанным минимальным расстоянием». Труды IRE по теории информации . 6 (4): 445–450. doi :10.1109/TIT.1960.1057584.