Mathematics desk | ||
---|---|---|
< June 25 | << May | June | Jul >> | Current desk > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
I was reading the Gray code article and thought of a related problem. With three binary digits, gray code (or any other code for that matter) can encode 23 = 8 positions at most:
Dec Gray code 0 000 1 001 2 011 3 010 4 110 5 111 6 101 7 100
But if we change the problem to this: support we are given a linear scale with N binary digits on each row, and an encoder that can read the current row and the next row, how many positions can be encoded?
At first I thought the answer was simply 2N+1, but it's actually much higher than that, surprisingly. For example this "car code" that I randomly came up with can encode 21 positions with N = 3:
Dec car code 0 000 1 001 2 011 3 010 4 110 5 111 6 101 7 100 8 101 9 111 10 110 11 010 12 011 13 001 14 000 15 000 16 100 17 110 18 100 19 000 20 010 21 000
I'm pretty sure I wasn't the first one to come up with this problem and that mathematicians have already solved it long ago, so I like to read more about this subject matter.
1. What's the general name for this class of problems?
2. How many positions can be encoded when two rows are known concurrently?
3. How many positions can be encoded when M rows are known concurrently? My other car is a cadr ( talk) 15:57, 26 June 2015 (UTC)
Dear My other car is a cadr,
You specifically ask "3. How many positions can be encoded when M rows are known concurrently?". With a single-track Gray code, it is possible to encode 30 positions when M=5 rows are known concurrently, and it is possible to encode exactly 360 positions when M=9 rows are known concurrently.
If you don't need debouncing for your application, then you can decode more positions with the same number of sensors using a De Bruijn sequence. With a binary De Bruijn sequence, it is possible to encode 2^M positions when M rows are known concurrently. With a binary De Bruijn sequence, it is possible to encode 32 positions when M=5 rows are known concurrently, and it is possible to encode 512 positions when M=9 rows are known concurrently. (Both single-track Gray codes and binary De Bruijn sequences each have N=1 bit per row). That seems to completely answer your question for the special case where each row is N=1 bit.
"1. What's the general name for this class of problems?"
That's a good question. I suspect that general De Bruijn sequences (possibly with an alphabet larger than the binary alphabet of 2 symbols) describe at least a few of the sequences you are asking about. I look forward to learning names of more general classes of such sequences. -- DavidCary ( talk) 03:40, 27 June 2015 (UTC)
Not a homework problem. Consider a sinusoidal railroad track in a building going up and down. x is the axis along the floor under the track, y is going up and down. y = sin(x). on the railroad is a *tiny*, (as tiny as you want) railroad car whose bed is parallel to the track under it, affixed to it is a spotlight which is perpendicular to it. The Ceiling of the building is at y=2. So during one period, the image of the spotlight on the ceiling is starts atat (-2,2) (the spotlight is along the line y=-x) and one cycle later is at 2 pi -2, 2) However in between, in moves back and forth as the railroad car tilts. My question is if x changes consistently (dx/dt is constant), what percentage of the time is the image of the spotlight moving forward on the ceiling and what percentage of time is it moving backwards. Second question, does that change if instead of dx/dt being constant ds/dt is constant where s measures the distance along the sine curve? Naraht ( talk) 18:27, 26 June 2015 (UTC)
Mathematics desk | ||
---|---|---|
< June 25 | << May | June | Jul >> | Current desk > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
I was reading the Gray code article and thought of a related problem. With three binary digits, gray code (or any other code for that matter) can encode 23 = 8 positions at most:
Dec Gray code 0 000 1 001 2 011 3 010 4 110 5 111 6 101 7 100
But if we change the problem to this: support we are given a linear scale with N binary digits on each row, and an encoder that can read the current row and the next row, how many positions can be encoded?
At first I thought the answer was simply 2N+1, but it's actually much higher than that, surprisingly. For example this "car code" that I randomly came up with can encode 21 positions with N = 3:
Dec car code 0 000 1 001 2 011 3 010 4 110 5 111 6 101 7 100 8 101 9 111 10 110 11 010 12 011 13 001 14 000 15 000 16 100 17 110 18 100 19 000 20 010 21 000
I'm pretty sure I wasn't the first one to come up with this problem and that mathematicians have already solved it long ago, so I like to read more about this subject matter.
1. What's the general name for this class of problems?
2. How many positions can be encoded when two rows are known concurrently?
3. How many positions can be encoded when M rows are known concurrently? My other car is a cadr ( talk) 15:57, 26 June 2015 (UTC)
Dear My other car is a cadr,
You specifically ask "3. How many positions can be encoded when M rows are known concurrently?". With a single-track Gray code, it is possible to encode 30 positions when M=5 rows are known concurrently, and it is possible to encode exactly 360 positions when M=9 rows are known concurrently.
If you don't need debouncing for your application, then you can decode more positions with the same number of sensors using a De Bruijn sequence. With a binary De Bruijn sequence, it is possible to encode 2^M positions when M rows are known concurrently. With a binary De Bruijn sequence, it is possible to encode 32 positions when M=5 rows are known concurrently, and it is possible to encode 512 positions when M=9 rows are known concurrently. (Both single-track Gray codes and binary De Bruijn sequences each have N=1 bit per row). That seems to completely answer your question for the special case where each row is N=1 bit.
"1. What's the general name for this class of problems?"
That's a good question. I suspect that general De Bruijn sequences (possibly with an alphabet larger than the binary alphabet of 2 symbols) describe at least a few of the sequences you are asking about. I look forward to learning names of more general classes of such sequences. -- DavidCary ( talk) 03:40, 27 June 2015 (UTC)
Not a homework problem. Consider a sinusoidal railroad track in a building going up and down. x is the axis along the floor under the track, y is going up and down. y = sin(x). on the railroad is a *tiny*, (as tiny as you want) railroad car whose bed is parallel to the track under it, affixed to it is a spotlight which is perpendicular to it. The Ceiling of the building is at y=2. So during one period, the image of the spotlight on the ceiling is starts atat (-2,2) (the spotlight is along the line y=-x) and one cycle later is at 2 pi -2, 2) However in between, in moves back and forth as the railroad car tilts. My question is if x changes consistently (dx/dt is constant), what percentage of the time is the image of the spotlight moving forward on the ceiling and what percentage of time is it moving backwards. Second question, does that change if instead of dx/dt being constant ds/dt is constant where s measures the distance along the sine curve? Naraht ( talk) 18:27, 26 June 2015 (UTC)