[math-fun] Infinitely long Gray-like codes ?
Most of the applications in the Wikipedia article on Gray codes consider *fixed length* codes for some length n. One of the properties of binary gray codes is that substrings of them contain all of the n-bit binary integers, but far more efficiently than simply concatenating all 2^n of them. I'm interested in a slightly different *infinite* sequence of bits, which contain these n-bit substrings as early as possible, s.t., for any n, there is a function f(n) that tells my how large of an initial substring of this infinite sequence I have to generate in order to make sure that all 2^n binary integers appear at least once. Furthermore, I may want to "tune" this infinite sequence in order to change the statistics of how frequently all of the different k-bit integers appear, how frequently all of the (k+1)-bit integers appear, etc. Has anyone studied such sequences?
de Bruijn cycles might be a better starting point --- see OEIS A080679, and https://en.wikipedia.org/wiki/De_Bruijn_sequence WFL On 3/29/18, Henry Baker <hbaker1@pipeline.com> wrote:
Most of the applications in the Wikipedia article on Gray codes consider *fixed length* codes for some length n.
One of the properties of binary gray codes is that substrings of them contain all of the n-bit binary integers, but far more efficiently than simply concatenating all 2^n of them.
I'm interested in a slightly different *infinite* sequence of bits, which contain these n-bit substrings as early as possible, s.t., for any n, there is a function f(n) that tells my how large of an initial substring of this infinite sequence I have to generate in order to make sure that all 2^n binary integers appear at least once.
Furthermore, I may want to "tune" this infinite sequence in order to change the statistics of how frequently all of the different k-bit integers appear, how frequently all of the (k+1)-bit integers appear, etc.
Has anyone studied such sequences?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I've wondered the same question before. My not-particularly-elegant solution is to take, for all n, the de Bruijn sequence of length 2^n, cyclically permuted such that it begins with a maximal string of zeroes, and concatenate them. So we get something like this: 01 0011 00010111 0000... It's half as efficient as a single de Bruijn code, because you might have to go up to 2^(n+1) to find your favourite length-n bitstring. Best wishes, Adam P. Goucher
Sent: Thursday, March 29, 2018 at 1:36 AM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Infinitely long Gray-like codes ?
de Bruijn cycles might be a better starting point --- see OEIS A080679, and https://en.wikipedia.org/wiki/De_Bruijn_sequence
WFL
On 3/29/18, Henry Baker <hbaker1@pipeline.com> wrote:
Most of the applications in the Wikipedia article on Gray codes consider *fixed length* codes for some length n.
One of the properties of binary gray codes is that substrings of them contain all of the n-bit binary integers, but far more efficiently than simply concatenating all 2^n of them.
I'm interested in a slightly different *infinite* sequence of bits, which contain these n-bit substrings as early as possible, s.t., for any n, there is a function f(n) that tells my how large of an initial substring of this infinite sequence I have to generate in order to make sure that all 2^n binary integers appear at least once.
Furthermore, I may want to "tune" this infinite sequence in order to change the statistics of how frequently all of the different k-bit integers appear, how frequently all of the (k+1)-bit integers appear, etc.
Has anyone studied such sequences?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Adam P. Goucher -
Fred Lunnon -
Henry Baker