Vi anser 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) processen 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 två 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 polynom-tid kodbar/decodable kod för additiv (alias. omedvetna) kanaler som uppnår Shannonkapaciteten 1 − H( p). Dessa ä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å slumpmässigheten i kodaren eller det särskilda överförda ordet. Sådana kanaler fånga binära symmetriska fel och bristning fel som specialfall. Lista avkodning för polynom-tid kanaler: För varje konstant c > 0, vi konstruera koder med optimal hastighet (arbitrerat nära 1 − H (p)) som effektivt återställa en kort lista som innehåller rätt meddelande med hög sannolikhet för kanaler som kan beskrivas av kretsar av storlek som mest N c. Vår konstruktion är inte helt explicit utan snarare Monte Carlo (vi ger en algoritm som, med hög sannolikhet, producerar en kodare / dekoder par som fungerar för all tid N c kanaler). Vi känner inte till några andra kanalmodeller i informationsteorins litteratur än rent kontradiktoriska kanaler, som kräver mer än linjära kretsar för att implementera. Vi motiverar avkopplingen för att lista avkodning med ett omöjligt resultat som visar att, i ett stort antal parametrar (p > 1/4), koder som är unikt decodable för en blygsam klass av kanaler (online, minneslösa, icke-uniforma kanaler) inte kan ha positiv hastighet. V. Guruswami och A. Smith effektiv (dvs. polynom-tid encodable och decodable) binära koder för lista avkodning med nära optimal hastighet är ett stort öppet problem. 1 Därför är vårt mål att utnyttja de beräkningsbegränsningar på kanalen för att få effektivt lista-decodable koder. Beräknat avgränsade kanaler. Vi anser kanaler vars beteende på Nbit ingångar beskrivs av en krets av storlek T(N) (till exempel T(N) = O(N 2 )). Ibland kallar vi detta den tidsbundna modellen och hänvisar till T(·) som en tidsbunden. Vi känner inte till några kanalmodeller som beaktas i informationsteorins litteratur förutom rent kontradiktoriska kanaler, som kräver mer än linjär tid att genomföra. Vi diskuterar också (online) rymdbundna kanaler; dessa kanaler gör ett enda pass över det överförda kodordet, bestämma vilka platser att korrumpera när de går, och är begränsade till att lagra högst S(N) bitar (dvs, de kan beskrivas av en-pass grenning program med bredd högst 2 S(N) ). Logaritmiska rymdkanaler, i synnerhet, kan realiseras av polynom-storlek kretsar. Lista avkodning för polynom-tid kanaler. Vårt huvudsakliga bidrag för tidsbundna kanaler är en konstruktion av polynom-tid encodable och lista-decodable koder som närmar sig den optimala hastigheten för kanaler vars tidsbundna är ett polynom i blocklängd N. Specifikt ger vi en effektivt beräkningsbar kodning funktion, Enc, som stochastically kodar meddelandet m i Enc(m; r), där r är privat slumpmässig vald vid kodaren, så att för varje meddelande m och tid N c - bundna kanal W, dekoder tar W (Enc(m; r) som ingång och returnerar en liten lista över meddelanden som, med hög sannolikhet över r och mynt i kanalen, innehåller det verkliga meddelandet m. Storleken på listan är polynomial i 1/ε, där N(1 - H( p) − ε) är längden på de överförda meddelandena. Vi betonar att dekoder inte vet valet av slumpmässiga bitar r som görs vid kodaren. Konstruktionen av vår kodningsfunktion Enc(·, ·) är Monte Carlo-vi ger en randomiserad algoritm som med stor sannolikhet producerar en kodare/dekoderpar Enc/Dec kommunicerar tillförlitligt över alla tids-N c-bundna kanaler (Definition 3.3). Den randomiserade konstruktionen är polynom tid, och den resulterande funktionen Enc (m; r) kan beräknas från m, r i deterministisk polynom tid. Vi vet dock inte hur vi effektivt kan kontrollera och intyga att en viss kodare Enc har de påstådda egenskaperna. Att få till stånd helt explicita konstruktioner är fortfarande ett spännande öppet problem. När det gäller polynom-tidsbegränsade kanaler förefaller det osannolikt att man kan lösa problemet utan ytterligare komplexa antaganden (t.ex. förekomsten av vissa pseudorandomgeneratorer). När det gäller online logspace-bundet kanal, kan det vara möjligt att få helt explicita konstruktioner utan komplexa antaganden (med t.ex. Nisan pseudorandom generatorer för logspace). Vi kommer att utveckla denna aspekt i avsnitt 9. En teknikalitet är att dekoder inte behöver returnera alla ord inom ett avstånd pN av det mottagna ordet (som är fallet för standard "kombinatoriska" begreppet lista avkodning), men det måste returnera rätt meddelande som en av kandidaterna med hög sannolikhet. Detta begrepp om listavkodning är naturligt för stokastiska koder i kommunikationsapplikationer. I själva verket är det exakt det begrepp som behövs i konstruktioner som "sieve" listan, såsom i Guruswami [2003] och Micali et al. [2005] och en tillämpning av våra resultat är en unik decodable kod för den offentliga nyckelmodellen (förutsatt en specifik polynom-tid bunden), stärka resultaten av Micali et al. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Se diskussionen om det relaterade arbetet i avsnitt 2 för en mer exakt redogörelse. För både additiva och tidsbundna modeller kräver våra konstruktioner nya metoder för att applicera verktyg från kryptografi och derandomisering till kodning-teoretiska problem. Vi ger en kort diskussion på hög nivå om dessa tekniker nästa gång. En utökad översikt över tillvägagångssättet bakom vår kodkonstruktion visas i Avsnitt 6. 1 Över stora alfabet, explicit optimal hastighet lista-decodable koder är kända. Konstruktion av styr/payload. I våra konstruktioner utvecklar vi flera nya tekniker. Den första är en ny "minskning" från standardkodning inställning utan inställning till inställningen av delad hemlig slumpmässighet. I modeller där fel fördelas jämnt är en sådan minskning relativt enkel [Ahlswede 1978], men denna minskning misslyckas mot kontradiktoriska fel. Istället visar vi hur man döljer den hemliga slumpmässigheten (kontrollinformationen) inuti huvudkodordet (lasten) på ett sådant sätt att dekodern kan lära sig kontrollinformationen, men (a) kontrollinformationen förblir dold för en avgränsad kanal och (b) dess kodning är robust för en viss, svagare klass av fel. Vi anser att denna teknik bör vara användbar i andra miljöer av avgränsat kontradiktoriskt beteende. Vår minskning kan också ses som ett nytt sätt att bootstrappa från "små" koder, som kan avkodas av brute force, till "stora" koder, som kan avkodas effektivt. Det vanliga sättet att göra detta är genom konkatering; tyvärr fungerar konkatering inte ens bra mot lätt oförutsägbara modeller, såsom additiva felmodellen. För det andra utvecklar våra resultat ytterligare en överraskande koppling mellan kodning och pseudorandomness. Att gömma "kontrollinformationen" från kanalen kräver att vi gör olika inställningar av kontrollinformationen oskiljbara från kanalens synvinkel. Således våra bevis tillämpa tekniker från kryptografi tillsammans med konstruktioner av pseudorandom objekt (generatorer, permutationer, och samplorer) från derandomization. Vanligtvis är de "test" som måste luras kompositioner av kanalen (som vi antar har låg komplexitet) med någon subrutin av dekoder (som vi designar för att ha låg komplexitet). Kopplingen till pseudorandomness visade sig i en enklare form i det tidigare arbetet med avgränsade kanaler [Lipton 1994; Galil et al. 1995; Micali m.fl. 2005] ; vår användning av denna förbindelse är betydligt mer känslig. De nödvändiga pseudorandom permutationer och provtagare kan uttryckligen konstrueras, och konstruktionen av de nödvändiga komplexitet-teoretiska pseudorandom generatorer är där vi använder slumpmässighet i vår konstruktion. För additiva fel räcker informationsteoretiska objekt som vi kan konstruera deterministiskt effektivt (t.ex. t-wise-oberoende strängar) och vi får en helt explicit konstruktion. Det finns flera arbetslinjer som syftar till att hantera kontradiktoriska, eller delvis kontradiktoriska, fel med hastigheter nära Shannon kapacitet. Vi kartlägger dem kortfattat här och lyfter fram relationen till våra resultat. Avkodning av lista. Lista avkodning infördes i slutet av 1950-talet [Elias 1957; Wozencraft 1958] och har bevittnat en hel del senaste algoritmiska arbete (jfr. undersökningen [Guruswami 2007] ). Under listan avkodning, dekoder utdata en liten lista över meddelanden som måste innehålla rätt meddelande. Slumpmässiga kodning argument visar att det finns binära koder för hastighet 1 − H( p) − ε som kan tolerera pN adversarial fel om dekoder får skriva ut en lista över storlek O( 1/ε) [Elias 1991; Zyablov och Pinsker 1982; Guruswami et al. År 2002]............................................................... Den explicita konstruktionen av binära list-decodable koder med hastighet nära 1 − H ( p), är dock fortfarande en stor öppen fråga. Vi tillhandahåller sådana koder för det speciella fall av korruption som införts av rymd- eller tidsbundna kanaler. Lägger till inställningsdelad slumpmässighet. En annan avkoppling är att tillåta randomiserade kodningsstrategier där avsändaren och mottagaren delar "hemlig" slumpmässighet, gömd från kanalen, som används för att välja en viss, deterministisk kod slumpmässigt från en familj av koder. Sådana randomiserade strategier kallades privata koder i Langberg [2004]. Med hjälp av denna hemliga delade slumpmässighet, kan man överföra med hastigheter som närmar sig
Explicit koder för hastighet närmar sig 1 − h (p) för att korrigera pn glömska bit flips (i betydelsen Theorem 1.2, med randomiserad kodning) gavs i REF.
Optimal Rate Code Constructions for Computationally Simple Channels
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}