Hasil pengkodean saluran menggunakan kompleksitas Kolmogorov

12

Biasanya entropi Shannon digunakan untuk membuktikan hasil pengkodean saluran. Bahkan untuk hasil pemisahan sumber-saluran digunakan shannon entropy. Mengingat kesetaraan antara pengertian Shannon (global) vs Kolmogorov (lokal) tentang informasi, apakah telah ada penelitian untuk memanfaatkan kompleksitas Kolmogorov untuk hasil ini (atau setidaknya untuk mengganti bagian pengkodean sumber dalam hasil pemisahan saluran sumber)?

it.information-theory kolmogorov-complexity shannon-entropy vs.
sumber

Sudahkah Anda melihat buku Li & Vitanyi edisi ke-3 ? Jika saya tidak salah, bab 8. dalam buku ini ditambahkan dalam edisi terbaru, dan berisi bab tentang Teori Informasi. Ini fitur Shannon entropi, informasi timbal balik, tingkat distorsi dll dianalisis dalam arti kompleksitas Kolmogorov.

Juho

Hai itu benar. Tetapi tidak ada aplikasi pada teorema coding Shannon yang berisik!

vs

8

Untuk kapasitas saluran, tampaknya sulit untuk mengganti entropi Shannon dengan kompleksitas Kolmogorov. Definisi kapasitas saluran tidak mengandung penyebutan entropi. Menggunakan entropi Shannon memberikan formula yang tepat untuk kapasitas saluran (ini adalah teorema Shannon). Jika Anda mengganti rumus dengan entropi Shannon dengan rumus dengan kompleksitas Kolmogorov, itu mungkin akan menjadi formula yang berbeda, dan itu akan menjadi jawaban yang salah .

$K$ $C$ $K/C$

Bagian yang sulit dari teorema pemisahan sumber-saluran menunjukkan bahwa Anda tidak bisa melakukan lebih baik daripada metode yang jelas (dijelaskan dalam paragraf sebelumnya) dari kompresi pertama dan kemudian pengkodean. Saya tidak tahu apakah ada yang membuktikan ini untuk kompleksitas dan kapasitas saluran Kolmogorov, tapi itu pertanyaan yang wajar untuk diselidiki.

Peter Shor
sumber

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

Saya tidak yakin apa yang Anda bicarakan ketika Anda menggunakan kualifikasi lokal / global pada entropi Shannon dan kompleksitas Kolmogorov.

Jadi perbaiki saya jika saya salah.

Entropi Shannon dapat dihitung. Kompleksitas Kolmogorov tidak. Karena itu mereka tidak menggambarkan masalah yang sama.

Anda bisa melihat entropi Shannon sebagai batas atas kompleksitas Kolmogrov.

Phil
sumber

Bagaimana Shannon entropi batas atas? Saya yakin terbukti keduanya sama.

T ....

Hasil pengkodean saluran menggunakan kompleksitas Kolmogorov

Jawaban: