Длинный код (математика) - Long code (mathematics)

Математическая логика
Классификация
ТипКод блокировки
Длина блока для некоторых
Длина сообщения
Размер алфавита
Обозначение-код

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

Определение

Позволять для быть списком все функции от .Тогда длинная кодировка сообщения это строка где означает объединение строк. Эта строка имеет длину .

В Код Уолша-Адамара является подкодом длинного кода и может быть получен только с помощью функций которые линейные функции при интерпретации как функции на конечное поле с двумя элементами. Поскольку есть только таких функций длина блока кода Уолша-Адамара равна .

Эквивалентное определение длинного кода выглядит следующим образом: Кодирование длинного кода определяется как таблица истинности булевой диктаторской функции на -я координата, т.е. таблица истинности с участием .[1]Таким образом, длинный код кодирует -битовая строка как -битовая строка.

Свойства

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

использованная литература