I detta dokument anser vi att kodsystem för beräkningsbegränsade kanaler, som kan införa en godtycklig uppsättning fel så länge som (a) andelen fel begränsas med stor sannolikhet av en parameter p och (b) den process som lägger till felen kan beskrivas med en tillräckligt "enkel" krets. Koder för sådana kanalmodeller är attraktiva eftersom de, liksom koder för vanliga kontradiktoriska fel, kan hantera kanaler vars verkliga beteende är okänt eller varierar med tiden. För tre kategorier av kanaler, ger vi explicit, effektivt encodable/decodable koder för optimal hastighet där endast ineffektivt decodable koder tidigare var kända. I varje fall tillhandahåller vi en kodare/dekoder som fungerar för varje kanal i klassen. Kodarna är randomiserade, och sannolikheterna tas över (lokala, okända för dekoder) mynt av kodaren och de i kanalen. Unik avkodning för additiva fel. Vi ger den första konstruktionen av en poly-tid encodable/decodable kod för tillsats (alias. omedvetna) kanaler som uppnår Shannonkapaciteten 1 − H(p). Det här är kanaler som lägger till en godtycklig felvektor e 0, 1} N av vikt som mest pN till det överförda ordet; vektorn e kan bero på koden men inte på det särskilda överförda ordet. Sådana kanaler fånga binära symmetriska fel och bristning fel som specialfall. Listavkodning för online log-space-kanaler. En rymd-S(N ) avgränsad kanal läser och ändrar det överförda kodordet som en ström, med hjälp av högst S(N ) bitar av arbetsyta på överföringar av N bitar. För konstant S fångar detta många modeller från litteraturen, inklusive diskreta kanaler med ändligt minne och godtyckligt varierande kanaler. Vi ger en effektiv kod med optimal hastighet (i regel nära 1 – H(p)) som återvinner en kort lista som innehåller rätt meddelande med hög sannolikhet för kanaler begränsade till logaritmiskt utrymme. Listavkodning för flergångskanaler. För varje konstant c vi ger en liknande lista-avkodning resultat för kanaler som kan beskrivas av kretsar av storlek som mest N c, förutsatt att det finns pseudorandom generatorer. Vi är inte medvetna om några kanalmodeller som beaktas i informationsteorilitteraturen, förutom rent kontradiktoriska kanaler, som kräver mer än linjära kretsar för att genomföra.
Därefter tar REF ytterligare bort antagandet om installation av öppen nyckel specifikt för den kanal där antingen felet är oberoende av det faktiska meddelandet som skickas, eller felen kan beskrivas med polynomiska storlekskretsar.
Optimal-Rate Code Constructions for Computationally Simple Channels
{'venue': None, 'journal': 'arXiv: Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}