Wyniki kodowania kanałów przy użyciu złożoności Kołmogorowa

12

Zwykle do udowodnienia wyników kodowania kanału używana jest entropia Shannona. Nawet w przypadku wyników separacji kanałów źródłowych stosowana jest entropia shannon. Biorąc pod uwagę równoważność między Shannonem (globalnym) a Kołmogorowskim (lokalnym) pojęciem informacji, czy przeprowadzono badania nad wykorzystaniem złożoności Kołmogorowa do tych wyników (lub przynajmniej w celu zastąpienia części kodującej źródło w wynikach separacji kanałów źródłowych)?

it.information-theory kolmogorov-complexity shannon-entropy

— vs
źródło

Brałeś spojrzeć na 3. edycji książki Li & Vitanyi ? Jeśli się nie mylę, rozdział 8. książki został dodany w najnowszym wydaniu i zawiera rozdział dotyczący teorii informacji. Zawiera entropię Shannona, wzajemne informacje, zniekształcenie prędkości itp. Analizowane pod kątem złożoności Kołmogorowa.

— Juho

Cześć, to prawda. Ale nie ma zastosowania do hałaśliwego twierdzenia Shannona o kodowaniu!

— vs

8

Jeśli chodzi o pojemność kanału, trudno jest zastąpić entropię Shannona złożonością Kołmogorowa. Definicja pojemności kanału nie zawiera żadnej wzmianki o entropii. Użycie entropii Shannona daje prawidłowy wzór na pojemność kanału (takie jest twierdzenie Shannona). Jeśli zastąpisz formułę entropią Shannona formułą o złożoności Kołmogorowa, prawdopodobnie byłaby to inna formuła, a więc byłaby to zła odpowiedź .

$K$ $C$ $K/C$

Trudna część twierdzenia o separacji kanałów od źródła pokazuje, że nie da się lepiej niż oczywista metoda (opisana w poprzednim akapicie) pierwszego kompresowania, a następnie kodowania. Nie wiem, czy ktokolwiek udowodnił to ze względu na złożoność Kołmogorowa i pojemność kanału, ale rozsądne pytanie należy zbadać.

— Peter Shor
źródło

K

$K$

K

$K$

1

C \leq 1

$C \leq 1$

Ω (\log^{*} n)

$\Omega(\log^{*}n)$

n

$n$

\log \log n

$\log\log{n}$

r

$r$

\frac{r}{\log^{*} r}

$\frac{r}{\log^{*}r}$

1

Nie jestem pewien, o czym mówisz, kiedy używasz lokalnych / globalnych kwalifikatorów w entropii Shannona i złożoności Kołmogorowa.

Więc popraw mnie, jeśli się mylę.

Entropia Shannona jest obliczalna. Złożoność Kołmogorowa nie jest. Dlatego nie opisują tego samego problemu.

Można było dostrzec entropię Shannona jako górną granicę złożoności Kołmogrowa.

— Phil
źródło

W jaki sposób entropia Shannona jest górną granicą? Wierzę, że udowodniono, że oba są takie same.

— T ....