For Wirehair, I wanted to find a way to generate a random-looking binary matrix that is very easy to multiply, with the added requirement that it is invertible about as often as a normal random binary matrix. This is useful for making Wirehair run much faster while keeping the same level of error-correcting performance.

After stumbling through a couple of options, I designed a new matrix form I haven't seen before, I am naming the Shuffle-2 Code. It uses at its core the in-place deck shuffling algorithm, which is fast and efficient.

Before describing Shuffle-2 Codes, I want to briefly discuss Perfect Shuffle-2 Codes, which are simpler. Here is the algorithm to generate a 10x10 Perfect Shuffle-2 Code:

When the ROWS vector is not used to shuffle the row order, the code produces a matrix that resembles the "Matrix code" with long columns of ones.

As a result of this algorithm, the number of 1 bits in each row and column are the same (5). This is why I call it a "Perfect" Shuffle-2 Code. The problem with this matrix is that it is NEVER invertible. This unfortunate fact means that it cannot be used for Wirehair even through it only requires two bit flips per row to generate the entire matrix.

The reason I call it a Perfect Shuffle-2 code is now clear. If three or four bits are flipped per row, then it becomes a Perfect Shuffle-3 or Perfect Shuffle-4 code. These are progressively harder to generate, so I focus on the Shuffle-2 Code.

Example output: A random 17x17 Perfect Shuffle-2 Code matrix

To make these matrices invertible, a simple modification is made to destroy the "perfection" of the code. The modified algorithm is presented below, which generates Shuffle-2 Codes:

Invertible rate test results:

Continued in the next post.

After stumbling through a couple of options, I designed a new matrix form I haven't seen before, I am naming the Shuffle-2 Code. It uses at its core the in-place deck shuffling algorithm, which is fast and efficient.

Before describing Shuffle-2 Codes, I want to briefly discuss Perfect Shuffle-2 Codes, which are simpler. Here is the algorithm to generate a 10x10 Perfect Shuffle-2 Code:

(1) Shuffle the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, calling this vector the BITS vector. Shuffle the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, calling this vector the ROWS vector.

-- Notes: For Perfect Shuffle-2 Codes, these are the only shuffles required.

(2) In the first row, for each of the first 5 elements of the BITS vector, set the column to one, and set the other 5 columns to zero. Select which row to write to by using the first element of the ROWS vector.

-- Notes: Half of the bits in the first row are one, and half are zero. Which bits are set is uniformly random.

(3) For the 2nd through the 6th rows, choose two elements of the BITS vector, and flip just those two bits from the previous row to the next one. The way to choose which two bits to flip is as follows: Maintain two pointers, one for the start of the vector and one for the middle of the vector. Each time a pair of bits is flipped, increment each pointer forward. Select which row to write to by using consecutive elements of the ROWS vector.

-- Notes: This describes a code with Hamming distance of 2 between consecutive rows. Furthermore, each time a row is generated, the number of bits left in the BITS vector is reduced by 2. At the end of step (2), the entire BITS vector will have been used to flip all bits in the row. A total of 5 rows are affected by this step.

(3a) If the number of rows/columns is odd, flip one bit here from the front pointer in the next row.

(4) Set the pointers above back to the front and middle of the vector.

(5) For the 7th through the 10th rows, repeat step (3) by choosing two elements of the BITS vector, and flip just those two bits from the previous row to the next one. The way to choose which two bits to flip is the same as before: Use the two pointers and each time a pair fo bits is flipped, increment each pointer forward. Select which row to write to by using consecutive elements of the ROWS vector.

-- Notes: A total of 4 rows are affected by this step.

-- Notes: For Perfect Shuffle-2 Codes, these are the only shuffles required.

(2) In the first row, for each of the first 5 elements of the BITS vector, set the column to one, and set the other 5 columns to zero. Select which row to write to by using the first element of the ROWS vector.

-- Notes: Half of the bits in the first row are one, and half are zero. Which bits are set is uniformly random.

(3) For the 2nd through the 6th rows, choose two elements of the BITS vector, and flip just those two bits from the previous row to the next one. The way to choose which two bits to flip is as follows: Maintain two pointers, one for the start of the vector and one for the middle of the vector. Each time a pair of bits is flipped, increment each pointer forward. Select which row to write to by using consecutive elements of the ROWS vector.

-- Notes: This describes a code with Hamming distance of 2 between consecutive rows. Furthermore, each time a row is generated, the number of bits left in the BITS vector is reduced by 2. At the end of step (2), the entire BITS vector will have been used to flip all bits in the row. A total of 5 rows are affected by this step.

(3a) If the number of rows/columns is odd, flip one bit here from the front pointer in the next row.

(4) Set the pointers above back to the front and middle of the vector.

(5) For the 7th through the 10th rows, repeat step (3) by choosing two elements of the BITS vector, and flip just those two bits from the previous row to the next one. The way to choose which two bits to flip is the same as before: Use the two pointers and each time a pair fo bits is flipped, increment each pointer forward. Select which row to write to by using consecutive elements of the ROWS vector.

-- Notes: A total of 4 rows are affected by this step.

When the ROWS vector is not used to shuffle the row order, the code produces a matrix that resembles the "Matrix code" with long columns of ones.

As a result of this algorithm, the number of 1 bits in each row and column are the same (5). This is why I call it a "Perfect" Shuffle-2 Code. The problem with this matrix is that it is NEVER invertible. This unfortunate fact means that it cannot be used for Wirehair even through it only requires two bit flips per row to generate the entire matrix.

The reason I call it a Perfect Shuffle-2 code is now clear. If three or four bits are flipped per row, then it becomes a Perfect Shuffle-3 or Perfect Shuffle-4 code. These are progressively harder to generate, so I focus on the Shuffle-2 Code.

Example output: A random 17x17 Perfect Shuffle-2 Code matrix

10000001111010011

00111110100101100

11000001011010011

00101100111110010

00111100101101100

00111100101110100

11000011010010011

01111110000101100

01011111000101100

00101000111010011

00101100111110100

11010011000001011

00101000111110010

10100000111010011

11010111000001101

11010111000101100

11000011010001011

00111110100101100

11000001011010011

00101100111110010

00111100101101100

00111100101110100

11000011010010011

01111110000101100

01011111000101100

00101000111010011

00101100111110100

11010011000001011

00101000111110010

10100000111010011

11010111000001101

11010111000101100

11000011010001011

To make these matrices invertible, a simple modification is made to destroy the "perfection" of the code. The modified algorithm is presented below, which generates Shuffle-2 Codes:

(1) Shuffle the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, calling this vector the BITS vector. Shuffle the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, calling this vector the ROWS vector.

-- Notes: For Perfect Shuffle-2 Codes, these are the only shuffles required.

(1a) Shuffle the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, and replace the BITS vector with the shuffled vector.

-- Notes: This destroys the perfection of the code, making it much more likely to be invertible.

(2) In the first row, for each of the first 5 elements of the BITS vector, set the column to one, and set the other 5 columns to zero. Select which row to write to by using the first element of the ROWS vector.

-- Notes: Half of the bits in the first row are one, and half are zero. Which bits are set is uniformly random.

(3) For the 2nd through the 6th rows, choose two elements of the BITS vector, and flip just those two bits from the previous row to the next one. The way to choose which two bits to flip is as follows: Maintain two pointers, one for the start of the vector and one for the middle of the vector. Each time a pair of bits is flipped, increment each pointer forward. Select which row to write to by using consecutive elements of the ROWS vector.

-- Notes: This describes a code with Hamming distance of 2 between consecutive rows. Furthermore, each time a row is generated, the number of bits left in the BITS vector is reduced by 2. At the end of step (2), the entire BITS vector will have been used to flip all bits in the row. A total of 5 rows are affected by this step.

(3a) Shuffle the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, and replace the BITS vector with the shuffled vector.

-- Notes: This destroys the perfection of the code, making it much more likely to be invertible.

(4) Set the pointers above back to the front and middle of the vector.

(5) For the remaining 7th through the 10th rows, repeat step (3) by choosing two elements of the BITS vector, and flip just those two bits from the previous row to the next one. The way to choose which two bits to flip is the same as before: Use the two pointers and each time a pair fo bits is flipped, increment each pointer forward. Select which row to write to by using consecutive elements of the ROWS vector.

-- Notes: A total of 4 rows are affected by this step.

Modifications in bold.

-- Notes: For Perfect Shuffle-2 Codes, these are the only shuffles required.

(1a) Shuffle the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, and replace the BITS vector with the shuffled vector.

-- Notes: This destroys the perfection of the code, making it much more likely to be invertible.

(2) In the first row, for each of the first 5 elements of the BITS vector, set the column to one, and set the other 5 columns to zero. Select which row to write to by using the first element of the ROWS vector.

-- Notes: Half of the bits in the first row are one, and half are zero. Which bits are set is uniformly random.

(3) For the 2nd through the 6th rows, choose two elements of the BITS vector, and flip just those two bits from the previous row to the next one. The way to choose which two bits to flip is as follows: Maintain two pointers, one for the start of the vector and one for the middle of the vector. Each time a pair of bits is flipped, increment each pointer forward. Select which row to write to by using consecutive elements of the ROWS vector.

-- Notes: This describes a code with Hamming distance of 2 between consecutive rows. Furthermore, each time a row is generated, the number of bits left in the BITS vector is reduced by 2. At the end of step (2), the entire BITS vector will have been used to flip all bits in the row. A total of 5 rows are affected by this step.

(3a) Shuffle the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, and replace the BITS vector with the shuffled vector.

-- Notes: This destroys the perfection of the code, making it much more likely to be invertible.

(4) Set the pointers above back to the front and middle of the vector.

(5) For the remaining 7th through the 10th rows, repeat step (3) by choosing two elements of the BITS vector, and flip just those two bits from the previous row to the next one. The way to choose which two bits to flip is the same as before: Use the two pointers and each time a pair fo bits is flipped, increment each pointer forward. Select which row to write to by using consecutive elements of the ROWS vector.

-- Notes: A total of 4 rows are affected by this step.

Modifications in bold.

Invertible rate test results:

2x2 matrix : Shuffle-2 invertible rate = 1. Random invertible rate = 0.365

3x3 matrix : Shuffle-2 invertible rate = 0.768. Random invertible rate = 0.337

4x4 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.315

5x5 matrix : Shuffle-2 invertible rate = 0.396. Random invertible rate = 0.311

6x6 matrix : Shuffle-2 invertible rate = 0.53. Random invertible rate = 0.289

7x7 matrix : Shuffle-2 invertible rate = 0.371. Random invertible rate = 0.285

8x8 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.286

9x9 matrix : Shuffle-2 invertible rate = 0.308. Random invertible rate = 0.281

10x10 matrix : Shuffle-2 invertible rate = 0.4. Random invertible rate = 0.277

11x11 matrix : Shuffle-2 invertible rate = 0.295. Random invertible rate = 0.282

12x12 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.293

13x13 matrix : Shuffle-2 invertible rate = 0.271. Random invertible rate = 0.294

14x14 matrix : Shuffle-2 invertible rate = 0.364. Random invertible rate = 0.291

15x15 matrix : Shuffle-2 invertible rate = 0.238. Random invertible rate = 0.29

16x16 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.269

17x17 matrix : Shuffle-2 invertible rate = 0.203. Random invertible rate = 0.287

18x18 matrix : Shuffle-2 invertible rate = 0.326. Random invertible rate = 0.283

19x19 matrix : Shuffle-2 invertible rate = 0.203. Random invertible rate = 0.301

20x20 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.294

3x3 matrix : Shuffle-2 invertible rate = 0.768. Random invertible rate = 0.337

4x4 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.315

5x5 matrix : Shuffle-2 invertible rate = 0.396. Random invertible rate = 0.311

6x6 matrix : Shuffle-2 invertible rate = 0.53. Random invertible rate = 0.289

7x7 matrix : Shuffle-2 invertible rate = 0.371. Random invertible rate = 0.285

8x8 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.286

9x9 matrix : Shuffle-2 invertible rate = 0.308. Random invertible rate = 0.281

10x10 matrix : Shuffle-2 invertible rate = 0.4. Random invertible rate = 0.277

11x11 matrix : Shuffle-2 invertible rate = 0.295. Random invertible rate = 0.282

12x12 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.293

13x13 matrix : Shuffle-2 invertible rate = 0.271. Random invertible rate = 0.294

14x14 matrix : Shuffle-2 invertible rate = 0.364. Random invertible rate = 0.291

15x15 matrix : Shuffle-2 invertible rate = 0.238. Random invertible rate = 0.29

16x16 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.269

17x17 matrix : Shuffle-2 invertible rate = 0.203. Random invertible rate = 0.287

18x18 matrix : Shuffle-2 invertible rate = 0.326. Random invertible rate = 0.283

19x19 matrix : Shuffle-2 invertible rate = 0.203. Random invertible rate = 0.301

20x20 matrix : Shuffle-2 invertible rate = 0. Random invertible rate = 0.294

Continued in the next post.

last edit by catid
edited (>30 days ago) 9:53pm Tue. Mar 13th 2012 PDT