• DocumentCode
    1330835
  • Title

    Fast and efficient construction of an unbiased random sequence

  • Author

    Ryabko, Boris Ya ; Matchikina, Elena

  • Author_Institution
    Dept. of Appl. Math. & Cybernetics, Siberian State Univ. of Telecommun. & Inf. Sci., Novosibirsk, Russia
  • Volume
    46
  • Issue
    3
  • fYear
    2000
  • fDate
    5/1/2000 12:00:00 AM
  • Firstpage
    1090
  • Lastpage
    1093
  • Abstract
    The problem of converting a sequence of symbols generated by a Bernoulli source into an unbiased random sequence is well-known in information theory. The proposed method is based on Elias´ (1972) algorithm in which the sequence of symbols is divided into blocks of length N,N⩾1. We suggest a new method of constructing an unbiased random sequence which uses O(Nlog2N) bits of memory and takes O(log8Nloglog(N)) bit operations per letter
  • Keywords
    binary sequences; computational complexity; information theory; random codes; Bernoulli source; Elias´ algorithm; binary sequences; codeword; efficient sequence construction; fast sequence construction; information theory; unbiased random sequence; Books; Clocks; Computer science; Cryptography; Cyclic redundancy check; IEEE Press; Internet; Probability distribution; Random sequences; Random variables;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/18.841190
  • Filename
    841190
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1330835