Синглтон-граница
Верхняя граница в теории кодирования

В теории кодирования граница Синглтона , названная в честь Ричарда Коллома Синглтона, является относительно грубой верхней границей размера произвольного блочного кода с длиной блока , размером и минимальным расстоянием . Она также известна как граница Джоши . [1] доказана Джоши (1958) и еще раньше Комамией (1953). С {\displaystyle С} н {\displaystyle n} М {\displaystyle М} г {\displaystyle д}

Заявление о связанности

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

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

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

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

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

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

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

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

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

История

Обычная ссылка на этот результат — Singleton (1964), но ранее он был доказан Joshi (1958). Joshi отмечает, что ранее этот результат был получен Komamiya (1953) с использованием более сложного доказательства. Welsh (1988, стр. 72) также отмечает то же самое относительно Komamiya (1953).

МДС-коды

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

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

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

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

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

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

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

Теорема  —  Пусть будет линейным [ ] MDS-кодом над . Если обозначает количество кодовых слов в веса , то C {\displaystyle C} n , k , d {\displaystyle n,k,d} F q {\displaystyle \mathbb {F} _{q}} A w {\displaystyle A_{w}} C {\displaystyle C} w {\displaystyle w} A w = ( n w ) ∑ j = 0 w − d ( − 1 ) j ( w j ) ( q w − d + 1 − j − 1 ) = ( n w ) ( q − 1 ) ∑ j = 0 w − d ( − 1 ) j ( w − 1 j ) q w − d − j . {\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 из объектов в конечной проективной геометрии . Пусть будет конечным проективным пространством (геометрической) размерности над конечным полем . Пусть будет множеством точек в этом проективном пространстве, представленным однородными координатами . Сформируем матрицу , столбцы которой будут однородными координатами этих точек. Тогда, [11] P G ( N , q ) {\displaystyle PG(N,q)} N {\displaystyle N} F q {\displaystyle \mathbb {F} _{q}} K = { P 1 , P 2 , … , P m } {\displaystyle K=\{P_{1},P_{2},\dots ,P_{m}\}} ( N + 1 ) × m {\displaystyle (N+1)\times m} G {\displaystyle G}

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

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

Примечания

  1. ^ Keedwell, A. Donald; Dénes, József (24 января 1991 г.). Латинские квадраты: новые разработки в теории и приложениях. Амстердам: Elsevier. стр. 270. ISBN 0-444-88899-3.
  2. ^ Лин и Син 2004, стр. 93
  3. ↑ Роман 1992, стр. 175
  4. ^ Плесс 1998, стр. 26
  5. ^ Вермани 1996, Предложение 9.2.
  6. ^ Лин и Син 2004, стр. 94 Примечание 5.4.7
  7. ^ MacWilliams & Sloane 1977, Гл. 11
  8. ^ Лин и Син 2004, стр. 94
  9. ^ Роман 1992, стр. 237, Теорема 5.3.7
  10. ↑ Роман 1992, стр. 240
  11. ^ Bruen, AA; Thas, JA; Blokhuis, A. (1988), «О кодах MDS, дугах в PG(n,q) с четным q и решении трех фундаментальных проблем Б. Сегре», Invent. Math. , 92 (3): 441–459, Bibcode : 1988InMat..92..441B, doi : 10.1007/bf01393742, S2CID  120077696

Ссылки

  • Джоши, ДД (1958), «Заметка о верхних границах для кодов с минимальным расстоянием», Информация и управление , 1 (3): 289–295, doi : 10.1016/S0019-9958(58)80006-6
  • Комамия, Ё. (1953), «Применение логической математики к теории информации», Труды 3-го Японского национального конгресса прикладной математики : 437
  • Лин, Сан; Син, Чаопин (2004), Теория кодирования / Первый курс , Cambridge University Press, ISBN 0-521-52923-9
  • MacWilliams, FJ ; Sloane, NJA (1977), Теория кодов, исправляющих ошибки, North-Holland, стр. 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-ичные коды с максимальным расстоянием", IEEE Trans. Inf. Theory , 10 (2): 116–118, doi :10.1109/TIT.1964.1053661
  • Вермани, Л.Р. (1996), Элементы алгебраической теории кодирования , Чапман и Холл
  • Уэлш, Доминик (1988), Коды и криптография , Oxford University Press, ISBN 0-19-853287-3

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Singleton_bound&oldid=1193571793"