Date: Feb 28, 2013 4:51 AM
Author: Martin Brown
Subject: 8x8 bit patterns
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 00|00 0001 1

5 01|01 0001 1

Whereas

4x1 2x2

0 00|00 0000 0

1 00|01 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