Abstract-Linear transformationer har många applikationer i informationsteori, såsom datakomprimering och felkorrigerande koder design. I detta dokument studerar vi kraften hos linjära omvandlingar i randomitetsextraktion, nämligen linjära extraktorer, som en annan viktig tillämpning. Jämfört med de flesta befintliga metoder för slumpmässig extraktion, linjära extraktorer (särskilt de konstruerade med glesa matriser) beräknas snabbt och kan helt enkelt implementeras med hårdvara som FPGAs, vilket gör dem mycket attraktiva i praktisk användning. Vi fokuserar främst på enkla, effektiva och glesa konstruktioner av linjära extraktorer. Speciellt visar vi att slumpmässiga matriser kan generera slumpmässiga bitar mycket effektivt från en mängd olika bullriga källor, inklusive bullriga mynt källor, bit-fixing källor, bullriga (dolda) Markov källor, samt deras blandningar. Det visar att lågdensitet slumpmässiga matriser har nästan samma effektivitet som högdensitet slumpmässiga matriser när inmatningssekvensen är lång, vilket ger ett sätt att förenkla maskinvaru/programvara implementation. Observera att även om vi konstruerade matriser med slumpmässighet, de är deterministiska (fröfria) extraktorer - en gång vi konstruerade dem, samma konstruktion kan användas för ett antal gånger utan att använda några frön. Ett annat sätt att konstruera linjära extraktorer är baserat på generatormatriser av primitiva BCH-koder. Denna metod är mer explicit, men mindre praktisk på grund av sin beräknings komplexitet och dimensionella begränsningar.
Sparse extraktorer för begränsade källor Motiverade av vissa tillämpningar, Zhou och Bruck REF visar att låg densitet slumpmässiga matriser effektivt kan extrahera slumpmässiga bitar från vissa begränsade bullriga källor, såsom bit fastställande källor och Markov källor.
Linear extractors for extracting randomness from noisy sources
{'venue': '2011 IEEE International Symposium on Information Theory Proceedings', 'journal': '2011 IEEE International Symposium on Information Theory Proceedings', 'mag_field_of_study': ['Computer Science']}