Оценка Гилберта – Варшамова для линейных кодов связана с общей границей Гилберта – Варшамова , которая дает нижнюю границу максимального числа элементов в коде с исправлением ошибок заданной длины блока и минимального веса Хэмминга над полем. . Это можно перевести в утверждение о максимальной скорости кода с данной длиной и минимальным расстоянием. Граница Гилберта – Варшамова для линейных кодов утверждает существование q- мерных линейных кодов для любого относительного минимального расстояния, меньшего заданной границы, которые одновременно имеют высокую скорость. Доказательство существования использует вероятностный метод и поэтому не является конструктивным. Гилберт-Варшамова является наиболее известным в терминах относительного расстояния для кодов над алфавитами размера меньше , чем 49. [ править ] Для больших алфавитов, Гоппа кода иногда достичь асимптотический лучше скорости в зависимости от расстояния , чем компромисса даются Gilbert -Варшамов связан. [1]
Граничная теорема Гилберта – Варшамова.
- Теорема. Пусть . Для каждого а также существует код со скоростью и относительное расстояние
Здесь является q- мерной функцией энтропии, определяемой следующим образом:
Вышеупомянутый результат был доказан Эдгаром Гилбертом для общего кода с использованием жадного метода, как здесь . Для линейного кода , Rom Варшамы доказываются с помощью вероятностного метода для случайного линейного кода. Это доказательство будет показано в следующей части.
Доказательство высокого уровня:
Чтобы показать существование линейного кода, который удовлетворяет этим ограничениям, для построения случайного линейного кода используется вероятностный метод . В частности, линейный код выбирается случайным образом путем выбора матрицы случайного генератора в котором элемент выбран равномерно по полю . Также расстояние Хэмминга линейного кода равно минимальному весу кодового слова . Итак, чтобы доказать, что линейный код, порожденный имеет расстояние Хэмминга , мы покажем, что для любого . Чтобы доказать это, мы докажем обратное; то есть вероятность того, что линейный код, сгенерированный имеет расстояние Хэмминга меньше, чем экспоненциально мала в . Тогда вероятностным методом существует линейный код, удовлетворяющий теореме.
Формальное доказательство:
Используя вероятностный метод, чтобы показать, что существует линейный код, у которого расстояние Хэмминга больше, чем , мы покажем, что вероятность того, что случайный линейный код, имеющий расстояние меньше, чем экспоненциально мала в .
Мы знаем, что линейный код определяется с помощью порождающей матрицы . Итак, мы используем «матрицу генератора случайных чисел»как средство описания случайности линейного кода. Итак, матрица случайного генератора размера содержит элементы, которые выбираются независимо и равномерно по полю .
Напомним, что в линейном коде расстояние равно минимальному весу ненулевого кодового слова. Позволять быть весом кодового слова . Так
Последнее равенство следует из определения: если кодовое слово принадлежит линейному коду, сгенерированному , тогда для какого-то вектора .
По неравенству Буля имеем:
Теперь для данного сообщения мы хотим вычислить
Позволять расстояние Хэмминга двух сообщений а также . Тогда для любого сообщения, у нас есть: . Следовательно:
Из-за случайности , - равномерно случайный вектор из . Так
Позволять объем шара Хэмминга радиуса . Тогда: [2]
Выбирая , указанное выше неравенство принимает вид
Ну наконец то , который экспоненциально мал по n, что мы и хотели раньше. Тогда вероятностным методом существует линейный код с относительным расстоянием и оценить по меньшей мере , что завершает доказательство.
Комментарии
- Приведенная выше конструкция Варшамова не является явной; то есть в нем не указывается детерминированный метод построения линейного кода, удовлетворяющего границе Гилберта – Варшамова. Наивный подход - перебирать все матрицы генератора размера над полем чтобы проверить, связан ли линейный код с достигает предсказанного расстояния Хэмминга. Этот исчерпывающий поиск требует экспоненциального времени выполнения в худшем случае.
- Также существует конструкция Лас-Вегаса, которая берет случайный линейный код и проверяет, имеет ли этот код хорошее расстояние Хэмминга, но эта конструкция также имеет экспоненциальное время выполнения.
- Для достаточно больших непростых q и некоторых диапазонов переменной δ оценка Гилберта-Варшамова улучшается оценкой Цфасмана-Владута-Зинка . [3]
Смотрите также
Рекомендации
- ^ Цфасман, Массачусетс; Владут С.Г .; Цинк, Т. (1982). «Модульные кривые, кривые Шимуры и коды Гоппы лучше, чем граница Варшамова-Гилберта». Mathematische Nachrichten . 104 .
- ^ Позднее неравенство происходит от верхней границы объема Хэмминга шара архивной 2013-11-08 в Wayback Machine
- ^ Стихтенот, Х. (2006). "Транзитивные и самодуальные коды, достигающие границы Цфасмана-Вла / spl breve / dut $ 80-Цинка". IEEE Transactions по теории информации . 52 (5): 2218–2224. DOI : 10.1109 / TIT.2006.872986 . ISSN 0018-9448 .