Граница синглтона - Википедия - 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 д (х, у)}$ это Расстояние Хэмминга между ${ 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 д ^ {п}}$, так как каждая буква в таком слове может занимать одну из ${ displaystyle q}$ разные значения, независимо от остальных букв.

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

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

${ Displaystyle п- (д-1) = п-д + 1}$,

и, таким образом, может быть не более ${ Displaystyle д ^ {п-д + 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 д ^ {к} leq д ^ {п-д + 1}}$,

так что

${ Displaystyle к Leq п-d + 1}$,

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

${ Displaystyle д Leq п-к + 1}$.

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

История

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

Коды MDS

Линейные блочные коды, которые достигают равенства в границе Синглтона, называются Коды MDS (максимальное разделимое расстояние). Примеры таких кодов включают коды, которые имеют только два кодовых слова (слово, состоящее только из нулей и слово из одного слова, имеющее, таким образом, минимальное расстояние ${ displaystyle n}$), коды, использующие все ${ Displaystyle ( mathbb {F} _ {q}) ^ {п}}$ (минимальное расстояние 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} ^ {wd} (- 1) ^ {j} { binom {w} {j}} (q ^ {w-d + 1-j} -1) = { binom {n} {w}} (q-1) sum _ {j = 0} ^ {wd} (- 1) ^ {j} { binom {w-1} {j}} q ^ {wdj}.}$

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

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

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

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

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

Примечания

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

• Линг, Сан; Син, Чаопин (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.