Code Poetry
and Text Adventures

by catid posted (>30 days ago) 12:09am Tue. Feb 10th 2015 PST
Matrix rows of all ones is desired.

To get these, one row symbol is taken as preferred.

All the other rows are chosen from this symbol.

Some rows have more ones than others.  Prefer ones with fewer ones.

When a small amount of traffic is being sent, 5-bit CRS codes are more ideal.

OOB data is one option.

For original data:
+ OOB flag (1 bit)
+ Code group (7 bits)
+ Original flag (1 bit)
+ Column symbol (7 bits)
+ DATA
-> packet id
but it is not too useful for other purposes
- encryption?  too far into the data part
- reliability?  doesn't support streams
- erasure code should be for all streams together since it's protecting the
entire channel.

For recovery data:
+ OOB flag (1 bit)
+ Code group (7 bits)
+ Original flag (1 bit)
+ First column symbol covered (7 bits)
+ Covered symbols (8 bits+1)
+ Row symbol (8 bits)
+ (Encoded) packet length (16 bits)
+ DATA

As packets are received, they must be kept until they are too old.

---------------------
On new recovery A:
---------------------

  0 1 2 3 4 5 6 7 8
   M   M   M
8 x x x x x|
9   x x x x x|
a    x x x x x|

(1) Assume that new recovery packets are always at the head end for now.

Pre-condition: All possible prior solutions have already been explored.

Pre-condition: A contains at least one missing packet.

Pre-condition: All single eliminations have been explored already, and in
this code path (new recovery A arrived) it suffices to check that
#Missing(A) == 1 to trigger single eliminations.
-> At least two missing packets are in A.

-> Solution is possible when: Sum(#Missing(Range 9-A)) <= #(Range 9-A)
This implies walking from A down should work.

When should the walk terminate??
At first, walking all the way through history is acceptable...
Starting from any point, the number of unknowns - number of equations will
be the same as last time, but with the latest row added.  Optimize later.

Are there any cases where skipping a recovery packet is a good idea??
Newer packets are always more helpful and have fewer unknowns that are not in common.
-> Linear walk back is fine!

In this case, eliminate the known Originals from 9, A.
Then perform Gaussian Elimination on the submatrix 3-4x9-A to recover 3-4.

After recovery completes, this process should be repeated recursively, as
it may have just solved a submatrix of a larger required solution to the left.

(1) Out of order can be done by running the above algorithm for the inserted
recovery packet backwards from its insertion point, and then running it again
for each recovery packet that arrived afterwards.
-- There should be an optimization possible here.


---------------------
On new original 5:
---------------------

  0 1 2 3 4 5 6 7 8
   M   M M /
8 x x x x x|
9   x x x x x|
a    x x x x x|

Run the walk algorithm for the earliest recovery packet
through to the last recovery packet that mentions it.
This should work because it is similar to have just
received the recovery packet and determining if it is
solvable.

There should be an optimization possible here too to
avoid running all of the walks.
last edit by catid edited (>30 days ago) 12:10am Tue. Feb 10th 2015 PST