Math Is Fun Forum

robinKr

Guest

2 dimensional matrix, 2x2 pattern qty?

For a 2 dimensional matrix that is K wide and L long, each intersection is a binary 1 or 0.
This represents a 2 dimensional parity bit check where odd qty of 1s is a 0 parity and even qty of 1s is a party 1.
A pattern of errors will not be detected by the 2 dimensional parity check and that patterns is 4 bits of 2x2 on adjacent row and column.  So in the column 2 errors cancel and in a row 2 errors cancel.

what is the equation to determine the number of 2x2 patterns that can exist in the KxL matrix?  Below is an example of a pattern, but it can be any pattern as long at the x's are in intersecting row and columns, and of course the row and columns are K and L long.

Any thoughts appreciated.  Im at a loss.

0x11x1101
1x11x1011
111111111
101111101

integer

Member

Registered: 2008-02-21

Posts: 79

Re: 2 dimensional matrix, 2x2 pattern qty?

It is not clear what you are asking.

11
11

that is one of the 2x2.

for this matrix

111
111
111

using this map

abc
def
ghi

does this represent

ab
de

bc
de

the possible 2x2 groups?

Can the bits occur in more that one group of the 2x2 cells?

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: 2 dimensional matrix, 2x2 pattern qty?

I think I understand the question.

Let's say that robin has the following matrix:

X = 11100
      00111
      00000
      10001

He wants to show this to somebody, but it's important that the elements are all correct so he builds in a parity count.

X' = 111001
       001111
       000000
       100010
       010100

Here, the upper corner is X and the additional row and column are the parities. This way, someone receiving the message can perform a check and if the parities don't match up then they know the message has been scrambled in some way.

However!
There is the unfortunate possibility that the message gets scrambled but passes the parity checks anyway.

eg.

X' = 101011
       100111
       010010
       001010
       010100

The parities check out even though the matrix involved is considerably different.
(The good news is that at least 4 of the bits need to be scrambled for this false positive to happen, so if the message is sent over 'light noise' then it'll definitely be correct or detected as wrong)

Robin's question asks for a given size of matrix, how many different matrices are there that will satisfy a certain parity check?
eg. How many different 5x4 matrices could successfully 'pretend' to be X above?

I'm not sure how to answer this yet, but I'm fairly sure that the answer is independent of what bits are in the parity-checking row and column.

---

Why did the vector cross the road?
It wanted to be normal.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: 2 dimensional matrix, 2x2 pattern qty?

Hi robinKr;

  Everyone who has looked at this problem has a different idea. I thought you wanted to know how many of those 4 x's you could fit in a n x m matrix observing the rule that the x's have to be in the same rows and columns.

1 X X 1
0 X X 1
0 0 0 1
0 0 0 0

is one arrangement While

1 X X 1
0 0 1 1
0 0 0 1
0 X X 0

is another. For square matrices n x n the answer is

So for that 4x4 you would get 36 ways to arrange those x's according to the rules. I am fairly sure of this (lots of empirical data), now for n x m : Here is one possible arrangement:

1 0 0 0 0 0 X 0 0 X
0 0 0 1 0 0 0 1 1 1
1 1 1 1 0 0 X 0 1 X

I think the formula is ( I am less sure as I have less examples):

Remember, this is not proven it is just the work I have been able to do so far.

Last edited by bobbym (2009-06-22 02:01:56)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.