• DocumentCode
    2088149
  • Title

    Extraction of optimally unbiased bits from a biased source

  • Author

    Naslund, Mats ; Russell, Alexander

  • Author_Institution
    NADA, R. Inst. of Technol., Stockholm, Sweden
  • fYear
    1998
  • fDate
    22-26 Jun 1998
  • Firstpage
    90
  • Lastpage
    91
  • Abstract
    We explore the problem of transforming n independent and identically biased {-1,1}-valued random variables, X1, ..., X n, into a single {-1,1} value, f(X1, ..., Xn ), so that this result is as unbiased as possible. In general, no function f produces a completely unbiased result. We perform the first study of the relationship between the bias b of these Xi and the rate at which f(X1, ..., Xn) can converge to an unbiased {-1,1} random variable (as n→∞)
  • Keywords
    Boolean functions; approximation theory; convergence of numerical methods; error analysis; random processes; Diophantine approximation; XOR function; biased source; convergence; error terms bounding; identically biased random variables; optimally unbiased bits extraction; perfectly unbiased output distributions; Arithmetic; Computer science; Random variables; Terminology;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Information Theory Workshop, 1998
  • Conference_Location
    Killarney
  • Print_ISBN
    0-7803-4408-1
  • Type

    conf

  • DOI
    10.1109/ITW.1998.706449
  • Filename
    706449