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.

June 26

A variation of Gray code

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 2³ = 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 2^N+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)[reply]

Your system depends on the two readers crossing row-boundaries with perfect simultaneity - which rather defeats the object of using Gray codes in this context. If you could distinguish more than 2^N+1 different positions when the two readers are separated by a half-integral number of rows, then that would be impressive.

Did you read as far as Single-track Gray code? --catslash (talk) 17:26, 26 June 2015 (UTC)[reply]

Yes, there's no debouncing, rendering it useless for general use, but fortunately I don't need debouncing for my application.

I re-read the section on single-track Gray code but still don't see how it's connected. Could you please elaborate? My other car is a cadr (talk) 01:52, 27 June 2015 (UTC)[reply]

Just a minor usage note: It's Gray code, with the capital G, named after Frank Gray. Maybe slightly more important to keep in mind than it would be with (say) "abelian group", because there's a natural tendency to think that the code might somehow have something to do with the color gray. I've even seen it spelled "grey code", presumably for that reason. --Trovatore (talk) 18:30, 26 June 2015 (UTC) [reply]

Thanks, noted. I have updated my OP.

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)[reply]

Thank you very much for the help, DavidCary. I'll go read up on De Bruijn sequences.

What about the case where there's multiple tracks, i.e. N > 1? How do I calculate the number of possible positions when given arbitrary N and M? I guess I'm just trying to find a sweet spot where both the number of tracks and the number of sensors is minimized. My other car is a cadr (talk) 03:58, 27 June 2015 (UTC)[reply]

Nevermind, found the answer. It's as simple as 2^{N^M}-M. My other car is a cadr (talk) 04:58, 27 June 2015 (UTC)[reply]

Spotlight on railroad car on a sinusoidal track...

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)[reply]

The beam hits the ceiling at

x_{\mathrm {ceil} }=x-(y_{\mathrm {ceil} }-\sin(x))\cos(x)

(I reckon), where

\scriptstyle {y_{\mathrm {ceil} }=2}

. The intervals when the light spot is moving forward and backward start and end at the instants when the spot is stationary, i.e.

{\frac {\partial }{\partial x}}x_{\mathrm {ceil} }=0

which (again, I reckon), means

{\frac {(\cos(x))^{2}}{\sin(x)}}=-{\frac {y_{\mathrm {ceil} }}{2}}

which you need to solve for

\scriptstyle {x}

(the positions of the car for which the spot is stationary). This looks inconveniently like a quartic with two real and two complex solutions. Had you chosen $\scriptstyle {y_{\mathrm {ceil} }=3}$ , then the solutions would be $\scriptstyle {x={\frac {7}{6}}\pi }$ and $\scriptstyle {x={\frac {11}{6}}\pi }$ and the spot would be moving backwards for one third of a cycle. Usually the values in homework problems are chosen to make the arithmetic easy, so either this really isn't homework (in which case I would urge you to choose say $\scriptstyle {y_{\mathrm {ceil} }={\sqrt {2}}}$ or $\scriptstyle {y_{\mathrm {ceil} }=3}$ ), or else I've made a mistake. The two real solutions are

x=\arcsin \left({\frac {y_{\mathrm {ceil} }}{4}}-{\sqrt {\left({\frac {y_{\mathrm {ceil} }}{4}}\right)^{2}+1}}\right)

which are centred on the dip, and the two complex solutions are

x=\arcsin \left({\frac {y_{\mathrm {ceil} }}{4}}+{\sqrt {\left({\frac {y_{\mathrm {ceil} }}{4}}\right)^{2}+1}}\right)

which are centred on the crest. --catslash (talk) 21:30, 26 June 2015 (UTC)[reply]

And once you have an answer for constant dx/dt, compare the sinusoidal path lengths of spot-moving-forward and spot-moving-backward intervals to get the answer for constant ds/dt. The path lengths are given by incomplete elliptic integrals. --catslash (talk) 21:39, 26 June 2015 (UTC)[reply]

Thanx, *really* cool!Naraht (talk) 23:14, 30 June 2015 (UTC)[reply]