The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: 8x8 bit patterns
Replies: 3   Last Post: Mar 13, 2013 12:09 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Martin Brown

Posts: 259
Registered: 12/13/04
Re: 8x8 bit patterns
Posted: Mar 13, 2013 12:09 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On 01/03/2013 15:35, Martin Brown wrote:
> On 01/03/2013 13:57, bert wrote:
>> On Thursday, February 28, 2013 10:51:02 AM UTC+1, Martin Brown wrote:
>>> 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
>>> 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

>> No, I think that's quite unlikely to be true, on the basis that there are
>> one or two 16-bit strings which, cyclically, contain all sixteen nibbles
>> (I remember using them as read/write patterns in disk tests). One 8-bit
>> row of your square can contain five different nibbles, not just two.

> Yes. But in the context of JPEG encoding the 8x8 grid is split into only
> the aligned 4x1 and 2x2 panels that will tile the plane.
> I did find a bug and now have a partial solution that gets 14/16 states.
> A complete solution still eludes me as does a proof it is impossible...

A much improved algorithm after a bit more thought gave a full solution:

0000 1110 0x0E
0001 0100 0x14
0010 1101 0x2D
1010 1000 0xA8

1011 0011 0xB3
1111 1100 0xFC
0101 1001 0x59
0111 0110 0x76

Read as aligned 4x1, 2x2 or 1x4 blocks every state is represented.

Martin Brown

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.