Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Issue understanding matrix layout #17

Open
orlp opened this issue Aug 26, 2019 · 5 comments
Open

Issue understanding matrix layout #17

orlp opened this issue Aug 26, 2019 · 5 comments

Comments

@orlp
Copy link

orlp commented Aug 26, 2019

In WirehairCodec.h we find:

    (1) Matrix Construction
        A = Original data blocks, N blocks long.
        D = Count of dense/heavy matrix rows (see below), chosen based on N.
        E = N + D blocks = Count of recovery set blocks.
        R = Recovery blocks, E blocks long.
        C = Matrix, with E rows and E columns.
        0 = Dense/heavy rows sum to zero.
        +---------+-------+   +---+   +---+
        |         |       |   |   |   |   |
        |    P    |   M   |   |   |   | A |
        |         |       |   |   |   |   |
        +---------+-----+-+ x | R | = +---+
        |    D    |  J  |0|   |   |   | 0 |
        +---------+-+---+-+   |   |   +---+
        |    0      |  H  |   |   |   | 0 |
        +-----------+-----+   +---+   +---+
        A and B are Ex1 vectors of blocks.
            A has N rows of the original data padded by H zeros.
            R has E rows of encoded blocks.
        C is the ExE hybrid matrix above:
            P is the NxN peeling binary submatrix.
                - Optimized for success of the peeling solver.
            M is the NxD mixing binary submatrix.
                - Used to mix the D dense/heavy rows into the peeling rows.
            D is the DxN dense binary submatrix.
                - Used to improve on recovery properties of peeling code.
            J is a DxD random-looking invertible submatrix.
            H is the 6x18 heavy GF(256) submatrix.
                - Used to improve on recovery properties of dense code.
            0 is a Dx6 zero submatrix.

My confusion lies in the M, D, J and 0 part. If M is NxD and D is DxN and J is DxD, then J exactly fills the corner between M and D and there should be no room for the 0 part. What gives?

@catid
Copy link
Owner

catid commented Aug 27, 2019

Sorry about the confusion. I had to go check the code to be sure.

_dense_count = D
_block_count = N
_mix_count = _dense_count + 6

So it looks like the 0 matrix to the right of J is Dx6 in size, and the size of M is Nx(D+6) rather than NxD.

@orlp
Copy link
Author

orlp commented Aug 28, 2019

@catid Another issue I have with that particular section of documentation is that there are multiple references to an object B, however one calls it a vector, the other a matrix, and none of them say what B actually is.

A and B are Ex1 vectors of blocks.

After that the encoder will start producing random-
looking M-byte blocks by generating new rows for P and M and
multiplying them by B.

Once enough rows have been
received, back-substitution reconstructs matrix B.

@catid
Copy link
Owner

catid commented Aug 28, 2019 via email

@orlp
Copy link
Author

orlp commented Aug 28, 2019

Perhaps also could be added how matrix J is generated.

@catid
Copy link
Owner

catid commented Aug 29, 2019 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants