Граница синглтона

В теории кодирования , то граница синглтон , названная в честь Ричарда Collom Singleton, является относительно сырым верхней границей размера произвольного блока кода с длиной блока , размером и минимальным расстоянием . Он также известен как Joshibound . ^[1]${\ 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}$,

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

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

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

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

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

История [ править ]

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

Коды MDS [ править ]

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

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

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

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

Теорема : Позвольте быть линейным [ ] кодом над . Следующие варианты эквивалентны:${\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. ^[11]

Теорема : Пусть - линейный [ ] код MDS над . Если обозначает количество кодовых слов в весе , то${\displaystyle C}$${\displaystyle n,k,d}$${\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 из объектов в конечной проективной геометрии . Пусть - конечное проективное пространство (геометрической) размерности над конечным полем . Позвольте быть набором точек в этом проективном пространстве, представленном с однородными координатами . Сформируйте матрицу , столбцы которой являются однородными координатами этих точек. Тогда ^[12]${\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}$

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Линг, Сан; Xing, Chaoping (2004), Теория кодирования / Первый курс , Cambridge University Press, ISBN 0-521-52923-9
• MacWilliams, FJ ; Sloane, NJA (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
• Синглтон, RC (1964), «q-nary коды максимального расстояния», IEEE Trans. Инф. Теория , 10 (2): 116-118, DOI : 10,1109 / TIT.1964.1053661
• Вермани, Л. Р. (1996), Элементы алгебраической теории кодирования , Chapman & Hall
• Валлийский, Доминик (1988), Коды и криптография , Oxford University Press, ISBN 0-19-853287-3

Дальнейшее чтение [ править ]

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