Граница синглтона - Singleton bound

В теория кодирования, то Граница синглтона, названный в честь Ричарда Коллома Синглтона, является относительно грубым верхним пределом размера произвольного блочный код ${\displaystyle C}$ с длиной блока ${\displaystyle n}$, размер ${\displaystyle M}$ и минимальное расстояние ${\displaystyle d}$.

Заявление о привязке

Минимальная дистанция набора ${\displaystyle C}$ кодовых слов длины ${\displaystyle n}$ определяется как

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

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

Тогда граница Синглтона утверждает, что

${\displaystyle A_{q}(n,d)\leq q^{n-d+1}.}$

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

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

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

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

${\displaystyle n-(d-1)=n-d+1}$,

и, таким образом, может быть не более ${\displaystyle q^{n-d+1}}$ их. С ${\displaystyle C}$ было произвольно, эта граница должна выполняться для максимально возможного кода с этими параметрами, таким образом:^[1]

${\displaystyle |C|\leq A_{q}(n,d)\leq q^{n-d+1}.}$

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

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

${\displaystyle q^{k}\leq q^{n-d+1}}$,

так что

${\displaystyle k\leq n-d+1}$,

который обычно записывается как^[2]

${\displaystyle d\leq n-k+1}$.

В случае линейного кода другое доказательство оценки Синглтона может быть получено, наблюдая за этим рангом матрица проверки на четность является ${\displaystyle n-k}$.^[3] Другое простое доказательство следует из наблюдения, что строки любой образующей матрицы в стандартном виде имеют вес не более ${\displaystyle n-k+1}$.

История

Обычно этот результат цитируется так: Синглтон (1964), но согласно Валлийский (1988 г., п. 72) результат можно найти в статье Комамия 1953 года.^[4]

Коды MDS

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

В случае двоичных алфавитов существуют только тривиальные коды MDS.^[5][6]

Примеры нетривиальных кодов MDS включают: Коды Рида-Соломона и их расширенные версии.^[7][8]

Коды MDS являются важным классом блочных кодов, поскольку для фиксированного ${\displaystyle n}$ и ${\displaystyle k}$, они обладают наибольшими возможностями исправления и обнаружения ошибок. Есть несколько способов охарактеризовать коды MDS:^[9]

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

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

Последняя из этих характеристик позволяет, используя Личности Маквильямса, явная формула для полного распределения веса кода MDS.^[10]

Теорема: Позволять ${\displaystyle C}$ быть линейным [${\displaystyle n,k,d}$] Код MDS завершен ${\displaystyle \mathbb {F} _{q}}$. Если ${\displaystyle A_{w}}$ обозначает количество кодовых слов в ${\displaystyle C}$ веса ${\displaystyle w}$, тогда

${\displaystyle 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}.}$

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

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

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

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

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

Примечания

1. Лин и Син 2004, п. 93
2. Роман 1992, п. 175
3. Pless 1998, п. 26
4. Комамия, Ю. (1953), "Применение логической математики в теории информации", Proc. 3-я Япония. Nat. Конг. Appl. Математика.: 437
5. Вермани 1996, Предложение 9.2
6. Лин и Син 2004, п. 94 Замечание 5.4.7.
7. МакУильямс и Слоан 1977, Гл. 11
8. Лин и Син 2004, п. 94
9. Роман 1992, п. 237, теорема 5.3.7
10. Роман 1992, п. 240
11. Bruen, A.A .; Thas, J.A .; Blokhuis, A. (1988), "О кодах M.D.S., дугах в PG (n, q), с четным q, и решении трех фундаментальных проблем Б. Сегре", Изобретать. Математика., 92: 441–459, Дои:10.1007 / bf01393742

Рекомендации

• Линг, Сан; Син, Чаопин (2004), Теория кодирования / Первый курс, Издательство Кембриджского университета, ISBN  0-521-52923-9
• MacWilliams, F.J.; Слоан, штат Нью-Джерси (1977), Теория кодов, исправляющих ошибки, Северная Голландия, стр.33, 37, ISBN  0-444-85193-3
• Плесс, Вера (1998), Введение в теорию кодов с исправлением ошибок (3-е изд.), Wiley Interscience, ISBN  0-471-19047-0
• Роман, Стивен (1992), Кодирование и теория информации, GTM, 134, Springer-Verlag, ISBN  0-387-97812-7
• Синглтон, Р. (1964), "Максимальное расстояние q-nary коды", IEEE Trans. Инф. Теория, 10 (2): 116–118, Дои:10.1109 / TIT.1964.1053661
• Вермани, Л. Р. (1996), Элементы алгебраической теории кодирования, Чепмен и Холл
• Валлийский, Доминик (1988), Коды и криптография, Издательство Оксфордского университета, ISBN  0-19-853287-3

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

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