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

В теория кодирования, то Граница синглтона, названный в честь Ричарда Коллома Синглтона, является относительно грубым верхним пределом размера произвольного блочный код с длиной блока , размер и минимальное расстояние .

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

Минимальная дистанция набора кодовых слов длины определяется как

куда это Расстояние Хэмминга между и . Выражение представляет максимальное количество возможных кодовых слов в -арный блочный код длины и минимальное расстояние.

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

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

Сначала заметьте, что количество -арочные слова длины является , так как каждая буква в таком слове может занимать одну из разные значения, независимо от остальных букв.

Теперь позвольте быть произвольным -аричный блочный код минимального расстояния . Ясно, что все кодовые слова различны. Если мы прокол код, удалив первый букв каждого кодового слова, то все результирующие кодовые слова по-прежнему должны быть попарно разными, поскольку все исходные кодовые слова в имеют Расстояние Хэмминга по меньшей мере друг от друга. Таким образом, размер измененного кода такой же, как и у исходного кода.

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

,

и, таким образом, может быть не более их. С было произвольно, эта граница должна выполняться для максимально возможного кода с этими параметрами, таким образом:[1]

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

Если это линейный код с длиной блока , измерение и минимальное расстояние над конечное поле с элементов, то максимальное количество кодовых слов равно а граница Синглтона подразумевает:

,

так что

,

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

.

В случае линейного кода другое доказательство оценки Синглтона может быть получено, наблюдая за этим рангом матрица проверки на четность является .[3] Другое простое доказательство следует из наблюдения, что строки любой образующей матрицы в стандартном виде имеют вес не более .

История

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

Коды MDS

Линейные блочные коды, которые достигают равенства в границе Синглтона, называются Коды MDS (максимальное разделимое расстояние). Примеры таких кодов включают коды, которые имеют только два кодовых слова (слово, состоящее только из нулей и слово из одного слова, имеющее, таким образом, минимальное расстояние ), коды, использующие все (минимальное расстояние 1), коды с одним символом четности (минимальное расстояние 2) и их двойные коды. Их часто называют банальный Коды МДС.

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

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

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

Теорема: Позволять быть линейным [] код закончился . Следующие варианты эквивалентны:
  • это код MDS.
  • Любой столбцы матрица генератора за находятся линейно независимый.
  • Любой столбцы матрица проверки на четность за линейно независимы.
  • это код MDS.
  • Если порождающая матрица для в стандартной форме, то каждая квадратная подматрица является неособый.
  • Учитывая любые позиции координат, существует кодовое слово (минимального веса), поддерживать именно эти позиции.

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

Теорема: Позволять быть линейным [] Код MDS завершен . Если обозначает количество кодовых слов в веса , тогда

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

Линейная независимость столбцов порождающей матрицы кода MDS позволяет строить коды MDS из объектов в конечный проективная геометрия. Позволять быть конечным проективное пространство (геометрического) размера над конечным полем . Позволять - множество точек в этом проективном пространстве, представленное однородные координаты. Сформировать матрица столбцы которого являются однородными координатами этих точек. Потом,[11]

Теорема: является (пространственным) -дуга если и только если порождающая матрица Код MDS завершен .

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

Примечания

  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

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

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