Lång kod (matematik)

Matematisk logik
klassificering
Typ	Blockkod
Blocklängd	$2^{n}$ för vissa $n\in \mathbb {N}$
Meddelandets längd	$\log n$
Alfabetets storlek	$2$
Notation	$(2^{n},\log n)_{2}$ -kod

Inom teoretisk datavetenskap och kodningsteori är den långa koden en felkorrigerande kod som är lokalt avkodningsbar . Långa koder har en extremt dålig hastighet, men spelar en grundläggande roll i teorin om hårdhet av approximation .

Definition

Låt $f_{1},\dots ,f_{2^{n}}:\{0,1\}^{k }\to \{0,1\}$ för $k=\log n$ är listan över alla funktioner från $\{0, 1\}^{k}\till \{0,1\}$ . Då är den långa kodningen för ett meddelande $x\in \{0,1\}^{k}$ strängen ${\displaystyle f_{1}(x)\circ f_{2}(x)\circ \dots \circ f_{2^{n}}(x)} där ∘ {\$ displaystyle $circ }$ anger sammanlänkning av strängar. Denna sträng har längden $2^{n}=2^{2^{k}}$ .

Walsh -Hadamard-koden är en underkod till den långa koden och kan erhållas genom att endast använda funktioner $f_{i}$ är linjära funktioner när de tolkas som funktioner $\mathbb {F} _{2}^{k}\to \mathbb {F} _{2}$ på det finita fältet med två element. Eftersom det bara finns $2^{k}$ sådana funktioner, är blocklängden för Walsh-Hadamard-koden $2^{k}$ .

En ekvivalent definition av den långa koden är som följer: Den långa kodningen av $j\in [n]$ definieras som sanningstabellen för den booleska diktaturens funktion på ${\displaystyle j }:$ e koordinaten, dvs. sanningstabellen för $f:\{0,1\}^{n}\to \{0,1\}$ med $f(x_{1},\dots ,x_{n})=x_{j}$ . Sålunda kodar den långa koden en $(\log n)$ -bitarssträng som en $2^{n}$ -bitarssträng.

Egenskaper

Den långa koden innehåller inte upprepningar, i den meningen att funktionen $f_{i}$ som beräknar i $\displaystyle i}:$ e biten av utdata skiljer sig från alla funktioner $f_{j }$ beräknar ${\displaystyle j}:$ e biten av utdata för $j\neq i$ . Bland alla koder som inte innehåller upprepningar har den långa koden den längsta möjliga utgången. Dessutom innehåller den alla icke-upprepande koder som en underkod.