Введение

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

История

Обычно приводится ссылка на , но это было доказано ранее Джоши отмечает, что результат был получен ранее с использованием более сложного доказательства. Также отмечается то же самое относительно .

Коды MDS

Коды линейных блоков, достигающие равенства в границе Синглтона, называются кодами MDS (максимально разделяемыми по расстоянию). Примеры таких кодов включают коды, имеющие только кодовые слова (все слова для , таким образом имеющие минимальное расстояние ), коды, использующие все (минимальное расстояние 1), коды с одним контрольным символом (минимальное расстояние 2) и их двойные коды. Их часто называют тривиальными кодами MDS. В случае бинарных алфавитов существуют только тривиальные коды MDS. Примеры нетривиальных кодов MDS включают коды Рида — Соломона и их расширенные варианты. Коды MDS являются важным классом блочных кодов, поскольку при фиксированных и они обладают наибольшими возможностями исправления и обнаружения ошибок. Существует несколько способов характеризации кодов MDS:

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

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

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