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
fDate :
5/1/2000 12:00:00 AM
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;
Journal_Title :
Information Theory, IEEE Transactions on
