Forward substitution for error-correction encoding and the like
In one embodiment, a forward substitution component performs forward substitution based on a lower-triangular matrix and an input vector to generate an output vector. The forward substitution component has memory, a first permuter, an XOR gate array, and a second permuter. The memory stores output sub-vectors of the output vector. The first permuter permutates one or more previously generated output sub-vectors stored in the memory based on one or more permutation coefficients corresponding to a current block row of the lower-triangular matrix to generate one or more permuted sub-vectors. The XOR gate array performs exclusive disjunction on (i) the one or more permuted sub-vectors and (ii) a current input sub-vector of the input vector to generate an intermediate sub-vector. The second permuter permutates the intermediate sub-vector based on a permutation coefficient corresponding to another block in the current block row to generate a current output sub-vector of the output vector.
1. An apparatus comprising a substitution component that performs substitution based on a triangular matrix and an input vector to generate an output vector, the apparatus comprising:
memory that stores output sub-vectors of the output vector;
a first permuter that permutates one or more previously generated output sub-vectors of the output vector based on one or more corresponding permutation coefficients to generate one or more permuted sub-vectors, wherein each permutation coefficient corresponds to a different sub-matrix in a current block row of the triangular matrix;
an XOR gate array that performs exclusive disjunction on (i) the one or more permuted sub-vectors and (ii) a current input sub-vector of the input vector to generate an intermediate sub-vector;
a second permuter that permutates the intermediate 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.
2. The apparatus of claim 1 , wherein:
the substitution component is a forward substitution component; and
the triangular matrix is a lower-triangular matrix.
3. The apparatus of claim 2 , wherein each output sub-vector of the output vector is proportional to
[
x
→
j
⊕
∑
k
=
0
j
-
1
[
w
→
k
]
T
(
j
,
k
)
]
-
T
(
j
,
j
)
,
where:
{right arrow over (x)} j is the current input sub-vector of the input vector;
{right arrow over (w)} k is a previously generated output sub-vector of the output vector;
T(j,k) is a permutation coefficient corresponding to the j th row and k th column of the lower-triangular matrix;
T(j,j) is a permutation coefficient corresponding to the j th row and j th column of the lower-triangular matrix; and
each permutation coefficient indicates an amount of reordering applied to a corresponding sub-vector.
4. The apparatus 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 H that is arranged in approximately lower-triangular form.
5. The apparatus of claim 4 , wherein:
the parity-check matrix H is given by:
H
=
[
A
B
T
C
D
E
]
where A, B, C, D, and E are sub-matrices of the parity-check matrix H;
T is the triangular matrix;
the input vector is generated by a first matrix-vector multiplication (MVM) component operating based on (i) sub-matrix A and (ii) the user-data vector; and
the output vector is applied to a second MVM component operating based on sub-matrix E.
6. The apparatus of claim 4 , wherein the encoder is a low-density parity-check (LDPC) encoder.
7. The apparatus of claim 1 , wherein each permutation coefficient corresponds to one of:
(i) reordering vector elements of a corresponding sub-vector;
(ii) leaving the corresponding sub-vector unchanged; and
(iii) replacing the corresponding sub-vector with a zero sub-vector.
8. The apparatus of claim 7 , wherein:
the first and second permuters are cyclic shifters; and
each cyclic shifter reorders the vector elements of a corresponding sub-vector by cyclically shifting the vector elements by a specified number of vector elements.
9. The apparatus of claim 7 , wherein:
the first and second permuters are implemented based on an Omega network; and
each Omega network reorders the vector elements of a corresponding sub-vector based on a corresponding permutation coefficient.
10. The apparatus of claim 7 , wherein:
the first and second permuters are implemented based on a Benes network; and
each Benes network reorders the vector elements of a corresponding sub-vector based on a corresponding permutation coefficient.
11. An encoder-implemented method for performing substitution based on a triangular matrix and an input vector to generate an output vector, the method comprising:
(a) the encoder storing in memory output sub-vectors of the output vector;
(b) the encoder permuting one or more previously generated output sub-vectors of the output vector based on one or more corresponding permutation coefficients to generate one or more permuted sub-vectors, wherein each permutation coefficient corresponds to a different sub-matrix in a current block row of the triangular matrix;
(c) the encoder performing exclusive disjunction on (i) the one or more permuted sub-vectors and (ii) a current input sub-vector of the input vector to generate an intermediate sub-vector;
(d) the encoder permuting the intermediate 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.
12. The encoder-implemented method of claim 11 , wherein:
the substitution is forward substitution;
the encoder implemented method is for performing forward substitution; and
the triangular matrix is a lower-triangular matrix.
13. The encoder-implemented method of claim 12 , wherein each output sub-vector of the output vector is proportional to
[
x
→
j
⊕
∑
k
=
0
j
-
1
[
w
→
k
]
T
(
j
,
k
)
]
-
T
(
j
,
j
)
,
where:
{right arrow over (x)} j is the current input sub-vector of the input vector;
{right arrow over (w)} k is a previously generated output sub-vector of the output vector;
T(j,k) is a permutation coefficient corresponding to the j th row and k th column of the lower-triangular matrix;
T(j,j) is a permutation coefficient corresponding to the j th row and j th column of the lower-triangular matrix; and
each permutation coefficient indicates an amount of reordering applied to a corresponding sub-vector.
14. The encoder-implemented method 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 H that is arranged in approximately lower-triangular form.
15. The encoder-implemented method of claim 14 , wherein:
the parity-check matrix H is given by:
H
=
[
A
B
T
C
D
E
]
where A, B, C, D, and E are sub-matrices of the parity-check matrix H;
T is the triangular matrix;
the input vector is generated by a first matrix-vector multiplication (MVM) step operating based on (i) sub-matrix A and (ii) the user-data vector; and
the output vector is applied to a second MVM step operating based on sub-matrix E.
16. The encoder-implemented method of claim 14 , wherein the encoder is a low-density parity-check (LDPC) encoder.
17. The encoder-implemented method of claim 11 , wherein each permutation coefficient corresponds to one of:
(i) reordering vector elements of a corresponding sub-vector;
(ii) leaving the corresponding sub-vector unchanged; and
(iii) replacing the corresponding sub-vector with a zero sub-vector.
18. The encoder-implemented method of claim 17 , wherein reordering the vector elements comprises cyclically shifting the vector elements by a specified number of vector elements.
19. The encoder-implemented method of claim 17 , wherein reordering the vector elements comprises applying the vector elements to an Omega network that reorders the elements based on the permutation coefficient.
20. The encoder-implemented method of claim 17 , wherein reordering the vector elements comprises applying the vector elements to a Benes network that reorders the elements based on the permutation coefficient.