Синглтон связан

В теории кодирования граница Синглтона , названная в честь Ричарда Коллома Синглтона, представляет собой относительно грубую верхнюю границу размера произвольного блочного кода. $C$ с длиной блока $n$, размер $M$ и минимальное расстояние $d$. Он также известен как Джошибунд . доказал Джоши (1958) и еще раньше Комамия (1953) .

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

Минимальное расстояние набора $C$ кодовых слов длины $n$ определяется как $$d=\min _{\{x,y\in C:x\neq y\}}d(x,y)$$ где $d(x,y)$ Хэмминга расстояние между $x$ и $y$. Выражение $A_{q}(n,d)$ представляет максимальное количество возможных кодовых слов в $q$-арный блочный код длины $n$ и минимальное расстояние $d$.

Тогда граница Синглтона утверждает, что $$A_{q}(n,d)\leq q^{n-d+1}.$$

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

Сначала заметим, что количество $q$-арные слова длины $n$ является $q^{n}$, поскольку каждая буква в таком слове может принимать одну из $q$ разные значения, независимо от остальных букв.

Теперь позвольте $C$ быть произвольным $q$-арный блочный код минимального расстояния $d$. Очевидно, что все кодовые слова $c\in C$ различны. Если мы проколем код, удалив первый $d-1$ буквы каждого кодового слова, то все результирующие кодовые слова все равно должны быть попарно разными, поскольку все исходные кодовые слова в $C$ иметь расстояние Хэмминга по крайней мере $d$ друг от друга. Таким образом, размер измененного кода такой же, как и исходный код.

Каждое вновь полученное кодовое слово имеет длину $$n-(d-1)=n-d+1,$$и, таким образом, может быть не более $q^{n-d+1}$ из них. С $C$ было произвольным, эта граница должна выполняться для максимально возможного кода с этими параметрами, таким образом: $$|C|\leq A_{q}(n,d)\leq q^{n-d+1}.$$

Линейные коды

Если $C$ представляет собой линейный код с длиной блока $n$, измерение $k$ и минимальное расстояние $d$ над конечным полем с $q$ элементов, то максимальное количество кодовых слов равно $q^{k}$ и граница Синглтона подразумевает: $$q^{k}\leq q^{n-d+1},$$так что $$k\leq n-d+1,$$который обычно записывается как $$d\leq n-k+1.$$

В случае линейного кода другое доказательство границы Синглтона можно получить, заметив, что ранг матрицы проверки четности равен $n-k$. Другое простое доказательство следует из наблюдения, что строки любой порождающей матрицы в стандартной форме имеют вес не более $n-k+1$.

История

Обычно этот результат цитируется Синглтоном (1964) , но ранее он был доказан Джоши (1958) . Джоши отмечает, что этот результат был получен ранее Комамией (1953) с использованием более сложного доказательства. Уэлш (1988 , с. 72) также отмечает то же самое в отношении Комамии (1953) .

МДС-коды

Линейные блочные коды, которые достигают равенства в границе синглтона, называются кодами MDS (разделяемыми на максимальное расстояние) . Примеры таких кодов включают коды, которые имеют только $q$ кодовые слова (все- $x$ слово для $x\in \mathbb {F} _{q}$, имея таким образом минимальное расстояние $n$), коды, которые используют всю $(\mathbb {F} _{q})^{n}$ (минимальное расстояние 1), коды с одним символом четности (минимальное расстояние 2) и их двойные коды . Их часто называют тривиальными MDS-кодами.

В случае двоичных алфавитов существуют только тривиальные MDS-коды.

Примеры нетривиальных кодов MDS включают коды Рида-Соломона и их расширенные версии.

MDS-коды являются важным классом блочных кодов, поскольку для фиксированной $n$ и $k$, они обладают наибольшими возможностями исправления и обнаружения ошибок. Существует несколько способов охарактеризовать коды MDS:

Теорема — Пусть $C$ быть линейным [ $n,k,d$] код закончен $\mathbb {F} _{q}$. Следующие действия эквивалентны:

• $C$ это код MDS.
• Любой $k$ столбцы порождающей матрицы для $C$ независимы линейно .
• Любой $n-k$ столбцы матрицы проверки четности для $C$ линейно независимы.
• $C^{\perp }$ это код MDS.
• Если $G=(I|A)$ является порождающей матрицей для $C$ в стандартной форме, то каждая квадратная подматрица $A$ является неособым .
• Учитывая любой $d$ координатных позиций, существует кодовое слово (минимального веса), опорой которого являются именно эти позиции.

Последняя из этих характеристик позволяет, используя тождества Мак-Вильямса , получить явную формулу для полного распределения веса кода MDS.

Теорема — Пусть $C$ быть линейным [ $n,k,d$] Код MDS закончился $\mathbb {F} _{q}$. Если $A_{w}$ обозначает количество кодовых слов в $C$ веса $w$, затем $$A_{w}={\binom {n}{w}}\sum _{j=0}^{w-d}(-1)^{j}{\binom {w}{j}}(q^{w-d+1-j}-1)={\binom {n}{w}}(q-1)\sum _{j=0}^{w-d}(-1)^{j}{\binom {w-1}{j}}q^{w-d-j}.$$

Дуги в проективной геометрии

Линейная независимость столбцов порождающей матрицы МДС-кода позволяет строить МДС-коды из объектов конечной проективной геометрии . Позволять $PG(N,q)$ — конечное проективное пространство (геометрической) размерности $N$ над конечным полем $\mathbb {F} _{q}$. Позволять $K=\{P_{1},P_{2},\dots ,P_{m}\}$ — множество точек в этом проективном пространстве, представленное однородными координатами . Сформируйте $(N+1)\times m$ матрица $G$ столбцы которого являются однородными координатами этих точек. Затем,

Теорема — $K$ это (пространственный) $m$-arc тогда и только тогда, когда $G$ является порождающей матрицей $[m,N+1,m-N]$ Код MDS закончился $\mathbb {F} _{q}$.

См. также

• Граница Гилберта–Варшамова
• Грисмер связан
• Хэмминг связан
• Джонсон связан
• Плоткин связан

Ссылки

• Джоши, Д.Д. (1958), «Примечание о верхних границах для кодов минимального расстояния», Information and Control , 1 (3): 289–295, doi : 10.1016/S0019-9958(58)80006-6
• Комамия, Ю. (1953), "Применение логической математики к теории информации", Proc. 3-я Япония. Нат. Конг. Прил. Математика. : 437
• Линг, Сан; Син, Чаопин (2004), Теория кодирования / Первый курс , Издательство Кембриджского университета, ISBN  0-521-52923-9
• МакВильямс, ФДж ; Слоан, NJA (1977), Теория кодов, исправляющих ошибки , Северная Голландия, стр. 33, 37 , ISBN  0-444-85193-3
• Плесс, Вера (1998), Введение в теорию кодов, исправляющих ошибки (3-е изд.), Wiley Interscience, ISBN  0-471-19047-0
• Роман, Стивен (1992), Теория кодирования и информации , GTM , vol. 134, Шпрингер-Верлаг, ISBN  0-387-97812-7
• Синглтон, RC (1964), «Дверные коды с максимальным расстоянием», IEEE Trans. Инф. Теория , 10 (2): 116–118, doi : 10.1109/TIT.1964.1053661.
• Вермани, Л.Р. (1996), Элементы алгебраической теории кодирования , Чепмен и Холл
• Уэлш, Доминик (1988), Коды и криптография , Oxford University Press, ISBN  0-19-853287-3

Дальнейшее чтение

• Дж. Х. ван Линт (1992). Введение в теорию кодирования . ГТМ . Том. 86 (2-е изд.). Спрингер-Верлаг. п. 61 . ISBN  3-540-54894-7 .
• Нидеррайтер, Харальд ; Син, Чаопин (2001). «6. Приложения к алгебраической теории кодирования». Рациональные точки на кривых над конечными полями. Теория и приложения . Серия лекций Лондонского математического общества. Том. 285. Кембридж : Издательство Кембриджского университета . ISBN  0-521-66543-4 . Збл   0971.11033 .