Длинный код (математика)

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

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

Определение

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

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

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

Характеристики

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