TY - GEN
T1 - Bounds on fixed-length post-processing functions for stationary biased random number generators
AU - Nuida, Koji
PY - 2008
Y1 - 2008
N2 - We investigate post-processing functions with fixedlength inputs/outputs for reducing biases of random bits. When original random bits are i.i.d., biases of the post-processed sequences are polynomials in bias of the original bits, and a function is regarded as better if least degrees of those polynomials are larger. In this article we give upper and lower bounds of the optimal least degree for such post-processing functions, and in some cases determine the optimal degree precisely.
AB - We investigate post-processing functions with fixedlength inputs/outputs for reducing biases of random bits. When original random bits are i.i.d., biases of the post-processed sequences are polynomials in bias of the original bits, and a function is regarded as better if least degrees of those polynomials are larger. In this article we give upper and lower bounds of the optimal least degree for such post-processing functions, and in some cases determine the optimal degree precisely.
UR - http://www.scopus.com/inward/record.url?scp=77951132349&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951132349&partnerID=8YFLogxK
U2 - 10.1109/ISITA.2008.4895580
DO - 10.1109/ISITA.2008.4895580
M3 - Conference contribution
AN - SCOPUS:77951132349
SN - 9781424420698
T3 - 2008 International Symposium on Information Theory and its Applications, ISITA2008
BT - 2008 International Symposium on Information Theory and its Applications, ISITA2008
T2 - 2008 International Symposium on Information Theory and its Applications, ISITA2008
Y2 - 7 December 2008 through 10 December 2008
ER -