Code Poetry
and Text Adventures

by catid posted (>30 days ago) 6:15pm Tue. Mar 13th 2012 PDT
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:

(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.

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


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.

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

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