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

Математическая логика
Классификация
Тип	Код блокировки
Длина блока	${\displaystyle 2^{n}}$ для некоторых ${\displaystyle n\in \mathbb {N} }$
Длина сообщения	${\displaystyle \log n}$
Размер алфавита	${\displaystyle 2}$
Обозначение	${\displaystyle (2^{n},\log n)_{2}}$-код

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

Определение

Позволять ${\displaystyle f_{1},\dots ,f_{2^{n}}:\{0,1\}^{k}\to \{0,1\}}$ для ${\displaystyle k=\log n}$ быть списком все функции от ${\displaystyle \{0,1\}^{k}\to \{0,1\}}$.Тогда длинная кодировка сообщения ${\displaystyle x\in \{0,1\}^{k}}$ это строка ${\displaystyle f_{1}(x)\circ f_{2}(x)\circ \dots \circ f_{2^{n}}(x)}$ где ${\displaystyle \circ }$ означает объединение строк. Эта строка имеет длину ${\displaystyle 2^{n}=2^{2^{k}}}$.

В Код Уолша-Адамара является подкодом длинного кода и может быть получен только с помощью функций ${\displaystyle f_{i}}$ которые линейные функции при интерпретации как функции ${\displaystyle \mathbb {F} _{2}^{k}\to \mathbb {F} _{2}}$ на конечное поле с двумя элементами. Поскольку есть только ${\displaystyle 2^{k}}$ таких функций длина блока кода Уолша-Адамара равна ${\displaystyle 2^{k}}$.

Эквивалентное определение длинного кода выглядит следующим образом: Кодирование длинного кода ${\displaystyle j\in [n]}$ определяется как таблица истинности булевой диктаторской функции на ${\displaystyle j}$-я координата, т.е. таблица истинности ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ с участием ${\displaystyle f(x_{1},\dots ,x_{n})=x_{j}}$.^[1]Таким образом, длинный код кодирует ${\displaystyle (\log n)}$-битовая строка как ${\displaystyle 2^{n}}$-битовая строка.

Свойства

Длинный код не содержит повторений в том смысле, что функция ${\displaystyle f_{i}}$ вычисление ${\displaystyle i}$-й бит вывода отличается от любой функции ${\displaystyle f_{j}}$ вычисление ${\displaystyle j}$й бит вывода для ${\displaystyle j\neq i}$.Среди всех кодов, не содержащих повторов, длинный код имеет максимально возможную длину вывода. Более того, он содержит все неповторяющиеся коды в качестве подкода.

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

1. Определение 7.3.1 в Пределы приближенных алгоритмов: PCP и уникальные игры (Учебные заметки по DIMACS)