Pertanyaan yang diberi tag coding-theory

Apa saja aplikasi kode koreksi kesalahan dalam teori selain koreksi kesalahan itu sendiri? Saya mengetahui tiga aplikasi: Teorema Goldreich-Levin tentang bit inti keras, konstruksi ekstraktor Trevisan dan penguatan kekerasan fungsi boolean (oleh Sudan-Trevisan-Vadhan). Apa aplikasi 'serius' atau...

Saya mencari kode koreksi kesalahan dari jenis berikut: kode biner dengan laju konstan, didekodekan dari beberapa fraksi konstan kesalahan, oleh decoder diimplementasikan sebagai sirkuit Boolean ukuran , di mana N adalah panjang pengkodean.O(N)O(N)O(N)NNN Beberapa latar belakang: Spielman,...

Kode Huffman untuk distribusi probabilitas adalah kode awalan dengan panjang codeword rata-rata tertimbang minimum , di mana adalah panjang dari kata sandi ke- . Ini adalah teorema yang terkenal bahwa panjang rata-rata per simbol kode Huffman adalah antara dan , di mana adalah entropi Shannon dari...

Algoritma DEFLATE populer menggunakan Huffman coding di atas Lempel-Ziv. Secara umum, jika kita memiliki sumber data acak (= 1 bit entropi / bit), tidak ada pengkodean, termasuk Huffman, yang cenderung memampatkannya secara rata-rata. Jika Lempel-Ziv "sempurna" (yang mendekati untuk sebagian besar...

Matriks memiliki dimensi n × n ( n - 1 ) . Kami ingin mengisi A menggunakan bilangan bulat antara 1 dan n , inklusif.SEBUAHAAn × n ( n - 1 )n×n(n−1)n \times n(n-1)SEBUAHAA111nnn Persyaratan: Setiap kolom adalah permutasi 1 , … , n .SEBUAHAA1 , … , n1,…,n1, \dots, n Setiap submatrix yang dibentuk...

Biarkan matriks nyata ( ) dengan properti yang ada dalam koleksi kolom adalah peringkat penuh.k ≤ n A kk × nk×nk\times nk ≤ nk≤nk\le nSEBUAHA{\bf A}kkk T: Apakah ada cara yang efisien untuk secara deterministik menemukan vektor sehingga matriks yang diperbesar mempertahankan properti yang sama...

Saya ingin mulai belajar tentang Pengodean Jaringan: http://en.wikipedia.org/wiki/Network_coding Apakah Anda tahu survei yang baik (misalnya dari Survei dan Tutorial IEEE) pada mata pelajaran di atas. Saya menemukan beberapa program universitas di google tetapi saya ingin beberapa rekomendasi...

Apakah ada konstruksi yang diketahui dari kode koreksi kesalahan linier (dengan parameter wajar), sehingga ketika diberi vektor Boolean , ia juga mengembalikan vektor Boolean whp? (meskipun sudah selesai )ECC:Fnq→FmqECC:Fqn→Fqm\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^mv∈{0,1}nv∈{0,1}nv\in...

Saya ingin mencari tahu apa saja aplikasi SGT di bidang informasi dan teori pengkodean dan mungkin komunikasi. Yang paling terkait yang terlintas dalam pikiran adalah pekerjaan pada Kode Expander Michael Sipser dan Daniel Spielman, "Kode Expander", Transaksi IEEE tentang Teori Informasi, Vol 42,...

Masalah berikut baru-baru ini muncul dari penelitian saya dan saya ingin bertanya apakah ada yang tahu apakah masalah ini dipertimbangkan sebelumnya atau telah mendengar apa pun yang mungkin terkait. Pengaturan umum adalah sebagai berikut. Kita diberi FFF , keluarga ttt -subsets dari { 1 , 2 , ....

Sebuah kode imbuhan adalah kode yang bersamaan awalan dan akhiran kode. Artinya, tidak ada codeword yang bukan awalan atau sufiks dari codeword lainnya. Kode Affix dapat didekodekan secara instan di kedua arah (maju dan mundur). Saya ingin membuat satu yang secara optimal mengompresi distribusi...

Pertimbangkan masalah keputusan berikut. Biarkan dan biarkan (C_0 ^ n, C_1 ^ n, \ dots, C_ {q-1} ^ n) menjadi cocok enumerasi himpunan bagian dari \ {0,1, \ dots, n-1 \} yang memiliki paling banyak n / 4 elemen.q=∑n/4i=0(ni)q=∑i=0n/4(ni)q = \sum_{i=0}^{n/4}