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

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

Заявление о границах

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

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

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

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

и) Если $d$ четный и $2d>n$ , затем

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

2) Если $d$ это странно и $2d+1>n$ , затем

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

3) Если $d$ четно, тогда

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

iv) Если $d$ странно, тогда

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

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

Доказательство дела i

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

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

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

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

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

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

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

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

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

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

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

С $M$ четно, отсюда следует, что

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

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

См. также

Ссылки

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