В теоретической информатике и теории кодирования , то длинный код является код коррекции ошибок , который локально декодируемый . Длинные коды имеют чрезвычайно низкую скорость, но играют фундаментальную роль в теории жесткости приближения .
Математическая логика | |
---|---|
Классификация | |
Тип | Код блокировки |
Длина блока | для некоторых |
Длина сообщения | |
Размер алфавита | |
Обозначение | -код |
Определение
Позволять для быть списком всех функций из. Тогда длинная кодировка сообщения это строка где обозначает конкатенацию строк. Эта строка имеет длину.
Код Уолша-Адамара является подкодом длинного кода и может быть получен только с помощью функцийкоторые являются линейными функциями при интерпретации как функциина конечном поле с двумя элементами. Поскольку есть только таких функций длина блока кода Уолша-Адамара равна .
Эквивалентное определение длинного кода выглядит следующим образом: Кодирование длинного кода определяется как таблица истинности функции булевой диктатуры на -я координата, т. е. таблица истинности с участием . [1] Таким образом, длинный код кодирует-битовая строка как -битовая строка.
Характеристики
Длинный код не содержит повторений в том смысле, что функция вычисление -й бит вывода отличается от любой функции вычисление -й бит вывода для . Среди всех кодов, не содержащих повторов, длинный код имеет максимально возможную длину вывода. Более того, он содержит все неповторяющиеся коды в качестве субкода.
Рекомендации
- ^ Определение 7.3.1 в пределах алгоритмов приближения: PCP и уникальные игры (Учебные лекции DIMACS)