Matrix vector multiplication for error-correction encoding and the like
In one embodiment, a matrix-vector multiplication (MVM) component generates a product vector based on (i) an input matrix and (ii) an input vector. The MVM component has a permuter, memory, and an XOR gate array. The permuter permutates, for each input sub-vector of the input vector, the input sub-vector based on a set of permutation coefficients to generate a set of permuted input sub-vectors. The memory stores a set of intermediate product sub-vectors corresponding to the product vector. The XOR gate array performs, for each input sub-vector, exclusive disjunction on (i) the set of permuted input sub-vectors and (ii) the set of intermediate product sub-vectors to update the set of intermediate product subvectors, such that all of the intermediate product sub-vectors in the set are updated based on a current input sub-vector before updating any of the intermediate product sub-vectors in the set based on a subsequent input sub-vector.
1. An apparatus comprising a matrix-vector multiplication (MVM) component that generates a product vector based on (i) an input matrix and (ii) an input vector, the MVM component comprising:
a permuter that:
for a current input sub-vector of the input vector, permutates the current input sub-vector based on a current set of permutation coefficients to generate a current set of permuted input sub-vectors, wherein each permutation coefficient in the current set corresponds to a different sub-matrix in a current block column of the input matrix; and
for a subsequent input sub-vector of the input vector, permutates the subsequent input sub-vector based on a subsequent set of permutation coefficients to generate a subsequent set of permuted input sub-vectors, wherein each permutation coefficient in the subsequent set corresponds to a different sub-matrix in a subsequent block column of the input matrix;
memory that stores a set of two or more intermediate product sub-vectors corresponding to the product vector, wherein each intermediate product sub-vector corresponds to a different block row of the input matrix; and
an XOR gate array that:
for the current input sub-vector, performs exclusive disjunction on (i) the current set of permuted input sub-vectors and (ii) the set of intermediate product sub-vectors to update the set of intermediate product sub-vectors; and
for the subsequent input sub-vector, performs exclusive disjunction on (i) the subsequent set of permuted input sub-vectors and (ii) the set of intermediate product sub-vectors to update the set of intermediate product sub-vectors, wherein the XOR gate array updates all of the intermediate product sub-vectors in the set based on the current input sub-vector before updating any of the intermediate product sub-vectors in the set based on the subsequent input sub-vector.
2. The invention of claim 1 , wherein each permutation coefficient corresponds to one of:
(i) reordering vector elements of a corresponding input sub-vector;
(ii) leaving the corresponding input sub-vector unchanged; and
(iii) replacing the corresponding input sub-vector with a zero sub-vector.
3. The invention of claim 2 , wherein:
the permuter is a cyclic shifter; and
the cyclic shifter reorders the vector elements of a corresponding input sub-vector by cyclically shifting the vector elements by a specified number of vector elements.
4. The invention of claim 2 , wherein:
the permuter is implemented based on an Omega network; and
the Omega network reorders the vector elements based on the permutation coefficient.
5. The invention of claim 2 , wherein:
the permuter is implemented based on a Benes network; and
the Benes network reorders the vector elements based on the permutation coefficient.
6. The invention of claim 2 , wherein the permutation coefficients correspond to two or more of:
(i) reordering vector elements of a corresponding input sub-vector;
(ii) leaving the corresponding input sub-vector unchanged; and
(iii) replacing the corresponding input sub-vector with a zero sub-vector.
7. The invention of claim 1 , wherein the XOR gate array updates all of the intermediate product sub-vectors in the set based on the current input sub-vector before a permuted input sub-vector based on the subsequent input sub-vector is received by the XOR gate array.
8. The invention of claim 1 , wherein the apparatus is an error-correction encoder that receives a user-data vector and generates a parity-bit vector based on a parity-check matrix that is arranged in approximately lower-triangular form.
9. The invention of claim 8 , wherein the error correction encoder further comprises a substitution component that performs substitution based on a triangular matrix and a second input vector to generate an output vector, the substitution component comprising:
memory that stores output sub-vectors of the output vector;
a second permuter that permutates one or more previously generated output sub-vectors of the output vector based on one or more other permutation coefficients to generate one or more other permuted sub-vectors, wherein each other permutation coefficient corresponds to a different sub-matrix in a current block row of the triangular matrix;
a second XOR gate array that performs exclusive disjunction on (i) the one or more other permuted sub-vectors and (ii) a current input sub-vector of the second input vector to generate a partially-updated sub-vector; and
a third permuter that permutates the partially-updated sub-vector based on a permutation coefficient corresponding to another sub-matrix in the current block row to generate a current output sub-vector of the output vector.
10. The invention of claim 8 , wherein the encoder is a low-density parity-check (LDPC) encoder.
11. A processor-implemented method for generating a product vector based on (i) an input matrix and (ii) an input vector, the method comprising:
(a) the processor permutating, for a current input sub-vector of the input vector, the current input sub-vector based on a current set of permutation coefficients to generate a current set of permuted input sub-vectors, wherein each permutation coefficient in the current set corresponds to a shift of a sub-matrix in a current block column of the input matrix;
(b) the processor permutating, for a subsequent input sub-vector of the input vector, the subsequent input sub-vector based on a subsequent set of permutation coefficients to generate a subsequent set of permuted input sub-vectors, wherein each permutation coefficient in the subsequent set corresponds to a different sub-matrix in a subsequent block column of the input matrix;
(c) the processor storing in memory a set of two or more intermediate product sub-vectors corresponding to the product vector, wherein each intermediate product sub-vector corresponds to a different block row of the input matrix;
(d) the processor performing, for the current input sub-vector, exclusive disjunction on (i) the current set of permuted input sub-vectors and (ii) the set of intermediate product sub-vectors to update the set of intermediate product sub-vectors; and
(e) the processor performing, for the subsequent input sub-vector, exclusive disjunction on (i) the subsequent set of permuted input sub-vectors and (ii) the set of intermediate product sub-vectors to update the set of intermediate product sub-vectors, wherein all of the intermediate product sub-vectors in the set are updated based on the current input sub-vector before updating any of the intermediate product sub-vectors in the set based on the subsequent input sub-vector.
12. The invention of claim 11 , wherein each permutation coefficient corresponds to one of:
(i) reordering elements of the corresponding input sub-vector;
(ii) leaving the corresponding input sub-vector unchanged; and
(iii) replacing the corresponding input sub-vector with a zero sub-vector.
13. The invention of claim 12 , wherein reordering the vector elements comprises cyclically shifting the vector elements by a specified number of vector elements.
14. The invention of claim 12 , wherein reordering the vector elements comprises applying the vector elements to an Omega network that reorders the elements based on the permutation coefficient.
15. The invention of claim 12 , wherein reordering the vector elements comprises applying the vector elements to a Benes network that reorders the elements based on the permutation coefficient.
16. The invention of claim 12 , wherein the permutation coefficients correspond to two or more of:
(i) reordering vector elements of a corresponding input sub-vector;
(ii) leaving the corresponding input sub-vector unchanged; and
(iii) replacing the corresponding input sub-vector with a zero sub-vector.
17. The invention of claim 11 , wherein all of the intermediate product sub-vectors in the set are updated based on the current input sub-vector before exclusive disjunction is performed on any permuted input sub-vector that corresponds to the subsequent input sub-vector.
18. The invention of claim 11 , wherein the encoder-implemented method is an error-correction encoder-implemented method that receives a user-data vector and generates a parity-bit vector based on a parity-check matrix that is arranged in approximately lower-triangular form.
19. The invention of claim 11 , wherein the encoder is a low-density parity-check (LDPC) encoder.
20. An error-correction encoder, wherein:
the error-correction encoder receives a user-data vector and generates a parity-bit vector based on a parity-check matrix that is arranged in approximately lower-triangular form;
the error correction encoder comprises a matrix-vector multiplication (MVM) component that generates a product vector based on (i) an input matrix and (ii) an input vector, the MVM component comprising:
a permuter that, for each input sub-vector of the input vector, permutates the input sub-vector based on a set of permutation coefficients to generate a set of permuted input sub-vectors, wherein each permutation coefficient in the set corresponds to a different sub-matrix in a current block column of the input matrix;
memory that stores a set of intermediate product sub-vectors corresponding to the product vector; and
an XOR gate array that, for each input sub-vector, performs exclusive disjunction on (i) the set of permuted input sub-vectors and (ii) the set of intermediate product sub-vectors to update the set of intermediate product sub-vectors, wherein the XOR gate array updates all of the intermediate product sub-vectors in the set based on a current input sub-vector before updating any of the intermediate product sub-vectors in the set based on a subsequent input sub-vector; and
the error-correction encoder further comprises a substitution component that performs substitution based on a triangular matrix and a second input vector to generate an output vector, the substitution component comprising:
memory that stores output sub-vectors of the output vector;
a second permuter that permutates one or more previously generated output sub-vectors of the output vector based on one or more other permutation coefficients to generate one or more other permuted sub-vectors, wherein each other permutation coefficient corresponds to a different sub-matrix in a current block row of the triangular matrix;
a second XOR gate array that performs exclusive disjunction on (i) the one or more other permuted sub-vectors and (ii) a current input sub-vector of the second input vector to generate a partially-updated sub-vector; and
a third permuter that permutates the partially-updated sub-vector based on a permutation coefficient corresponding to another sub-matrix in the current block row to generate a current output sub-vector of the output vector.