Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



8x8 bit patterns
Posted:
Feb 28, 2013 4:51 AM


I have a little puzzle where I think the answer is that it is not possible but having tried all the tricks I can think of cannot prove it.
The problem arises from considering the possible bit patterns in an 8x8 JPEG encoding square and searching for one that includes all possible states for subsampling up to 2x2  that is 2x1, 4x1, 2x2
ie 0000, 0001, ...., 1111
and
00 00 00 ........... 11 00, 01, 10, 11
It would be really nice if it did 1x4 as well.
It is obvious that the 4x1 subsampling requirement means that the final solution if it exists must be a permutation of the nibbles 0,1,...,15
It is also obvious that taken as pairs and interpreted as 2x2 subsampled there are 16x15 possible states of which those involving 0,5,10,15 will have duplicate 2x2 subsampling patterns if used together. Using any pair taken from this set prevents a solution.
ie
4x1 2X2 0 0000 0001 1 5 0101 0001 1
Whereas
4x1 2x2 0 0000 0000 0 1 0001 0001 1
The best I have been able to obtain by a directed brute force attack is any number of solutions getting 11/15 of the 2x2 states and all of 4x1. I am still not convinced my algorithm is working correctly.
This is based on computing the 2x2 patterns for all the pairs and then combining them efficiently to try and maximise coverage in both domains.
The 4x1 pair {0,7} is represented as 2x2 {1,3} and bitmasks are used to compute worthwhile continuations and cull all branches already worse than existing solutions.
A complete solution should represent 0..15 in both domains 2x2 and 4x1. But alas I can't find one :(
I can't help thinking there should be some clever parity based argument to show that it is impossible to do better. Any suggestions?
Thanks for any enlightenment.
 Regards, Martin Brown



