Pytania otagowane jako coding-theory

Matematyczna teoria kodów stosowana w komunikacji, kompresji danych i kryptografii.

13
Teoretycznie stosowanie kodów korygujących błędy
Jakie są zastosowania kodów korekcji błędów w teorii oprócz samej korekcji błędów? Jestem świadomy trzech zastosowań: twierdzenia Goldreicha-Levina o twardym rdzeniu, konstrukcji ekstraktora Trevisana i wzmocnienia twardości funkcji boolowskiej (autor: Sudan-Trevisan-Vadhan). Jakie są inne „poważne” lub „rekreacyjne” zastosowania kodów korygujących błędy? UPD: jedna zabawna aplikacja do dekodowania list kodów Reeda-Solomona …
1
Dobre kody dekodowalne przez obwody liniowe?
Szukam kodów korygujących błędy następującego typu: kody binarne o stałej szybkości, dekodowalny z pewnej stałej części błędów za pomocą dekodera możliwego do zaimplementowania jako logiczny obwód o rozmiarze , gdzie N jest długością kodowania.O ( N)O(N)O(N)N.NN Trochę tła: Spielman, w liniowych kodowalnych i dekodowalnych kodach korygujących błędy , dał kody …
2
Jak dobry jest kod Huffmana, gdy nie ma dużych liter prawdopodobieństwa?
Kod Huffmana dla rozkładu prawdopodobieństwa jest kodem prefiksu o minimalnej średniej ważonej długości słowa kodowego , gdzie jest długością tego słowa kluczowego. Jest dobrze znanym twierdzeniem, że średnia długość na symbol kodu Huffmana zawiera się między a , gdzie jest entropią Shannona rozkładu prawdopodobieństwa.ppp∑piℓi∑piℓi\sum p_i \ell_iℓiℓi\ell_iiiiH(p)H(p)H(p)H(p)+1H(p)+1H(p)+1H(p)=−∑ipilog2piH(p)=−∑ipilog2⁡piH(p) = -\sum_i \, p_i …
5
Dlaczego kodowanie Huffmana eliminuje entropię, której nie ma Lempel-Ziv?
Popularny algorytm DEFLATE wykorzystuje kodowanie Huffmana na Lempel-Ziv. Ogólnie rzecz biorąc, jeśli mamy losowe źródło danych (= 1 bit entropii / bit), żadne kodowanie, w tym Huffman, prawdopodobnie nie skompresuje go średnio. Gdyby Lempel-Ziv był „idealny” (do którego zbliża się większość klas źródeł, ponieważ długość dochodzi do nieskończoności), kodowanie postów …
1
Konstruowanie wektorów w pozycji ogólnej
Niech prawdziwa macierz k×nk×nk\times n ( k≤nk≤nk\le n ) AA{\bf A} z tą właściwością, że dowolny zbiór kkk kolumn ma pełną rangę. P: istnieje efektywny sposób deterministyczny znaleźć wektor tak że zmodyfikowanym matrycy ' = [aa{\bf a}A′=[Aa]A′=[Aa]{\bf A}' = [{\bf A}\;{\bf a}] zachowuje tę samą właściwość coAA{\bf A} : dowolnekkk …
2
Rozpuszczalność wypełnienia matrycy
Macierz ma wymiar n × n ( n - 1 ) . Chcemy wypełnić A za pomocą liczb całkowitych od 1 do n włącznie.AAAn×n(n−1)n×n(n−1)n \times n(n-1)AAA111nnn Wymagania: Każda kolumna jest permutacją 1 , … , n .AAA1,…,n1,…,n1, \dots, n Żadna submatrix utworzona z dwóch rzędów nie może mieć identycznych kolumn.AAA …
1
Błąd logiczny korygujący kod w
Czy istnieje znana konstrukcja kodu korygującego błędy liniowe (z rozsądnymi parametrami), na przykład gdy podano logiczny wektor zwraca również wartość logiczną wektora logicznego? (chociaż to koniec \ mathbb {F} _q )ECC:Fnq→FmqECC:Fqn→Fqm\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^mv∈{0,1}nv∈{0,1}nv\in \{0,1\}^nFqFq\mathbb{F}_q (to znaczy Pr[ECC(v)∈{0,1}m]>1−ϵPr[ECC(v)∈{0,1}m]>1−ϵ\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon , gdzie prawdopodobieństwo jest przejmowane równomiernie wybierając v∈{0,1}nv∈{0,1}nv\in \{0,1\}^n , a …
2
Zastosowania teorii wykresów spektralnych w teorii informacji i kodowania
Chciałem dowiedzieć się, jakie są zastosowania SGT w dziedzinie informacji i teorii kodowania, a może komunikacji. Najbardziej związana, która przychodzi mi na myśl, to praca nad kodami ekspanderów Michael Sipser i Daniel Spielman, „Kody ekspanderów”, Transakcje IEEE dotyczące teorii informacji, tom 42, nr 6, s. 1710–1722. 1996 Inne przykłady?
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.