Welcome to the Matrix Kingdom.

Matrix-based code Encodes \(K\) states (codewords) in an \(m\times n\)-dimensional matrix of coordinates over a field (e.g., the Galois field \(GF(q)\) or the complex numbers \(\mathbb{C}\)). Parents: Error-correcting code (ECC). Parent of: Matrix computation code, Rank-metric code, Regenerating code (RGC), Spacetime code (STC), Tensor-product code.
Matrix computation code Encoding that provides an extra redundancy for distributed matrix computation algorithms such as matrix multiplication. Parallelized algorithms distribute a desired computation over many nodes, and a key performance bottleneck is due to some nodes completing their individual tasks much later than other nodes. Matrix computation codes provide a layer of redundancy such that the computation can be performed without having all nodes finish their piece of the computation. Protection: Allows computation to complete without waiting for stragglers, or nodes that either do not finish or finish their portion of the computation much later than all other nodes. Parents: Matrix-based code. Cousins: Maximum distance separable (MDS) code.
Rank-metric code[1] Also called a Delsarte code. Each codeword is a matrix over \(GF(q)\), with codewords forming a \(GF(q)\)-linear subspace, and with the metric being the rank of the difference of matrices. The distance \(d\) is the minimum rank of all nonzero matrices in the code. Rank-metric codes on \(n\times m\) matrices are denoted as \([n\times m,k,d]_q\). Protection: Protects against errors with rank \(\leq \lfloor \frac{d-1}2 \rfloor\). Parents: Matrix-based code. Parent of: Gabidulin code, Maximum-rank distance (MRD) code.
Spacetime code (STC)[2] Code designed for wireless transmission of information (via, e.g., radio waves) such that the sender can send multiple times from multiple locations. A spacetime code uses a modulation scheme to encode a message into signals that are sent at different times through different antennas, thereby utilizing both spatial and temporal (i.e., spacetime) degrees of freedom. Parents: Matrix-based code. Parent of: Spacetime block code (STBC). Cousin of: Codeword stabilized (CWS) code, Homological bosonic code.
Tensor-product code[3][4][5][6] Also called tensor code, Kroneckerian code, or product code. A matrix-based code constructed out of two linear binary or \(q\)-ary codes \(C_A,C_B\) in an outer-product construction denoted as \(C_A \otimes C_B\). Its dual is sometimes called the check-product code [7; Lemma 3.3]. Protection: For linear codes \(C_A=[n_A,k_A,d_A]\) and \(C_B=[n_B,k_B,d_B]\), the resulting tensor code is \(C_A \otimes C_B=[n_A n_B,k_A k_B,d_A d_B]\). Tensor codes can be useful for protecting against burst errors [8][9]. Parents: Matrix-based code, Generalized concatenated code. Cousin of: Dinur-Hsieh-Lin-Vidick (DHLV) code, Left-right Cayley complex code, Low-density parity-check (LDPC) code, Quantum Tanner code, Quantum check-product code, Reed-Solomon (RS) code.
Gabidulin code[10][11] Also called a vector rank-metric code. A linear code over \(GF(q^N)\) that corrects errors over rank metric instead of the traditional Hamming distance. Every element \(GF(q^N)\) can be written as an \(N\)-dimensional vector with coefficients in \(GF(q)\), and the rank of a set of elements is rank of the matrix formed by their coefficients. Protection: Set of vectors \(\{x_1, x_2, \ldots, x_M\}\) determines a rank code with distance \(d=\min d(x_i, x_j)\). The code with distance \(d\) corrects all errors with rank of the error not greater than \(\lfloor (d-1)/2\rfloor\). Parents: Linear \(q\)-ary code, Rank-metric code. Cousins: Maximum-rank distance (MRD) code.
Maximum-rank distance (MRD) code[1][12][11] Also called an optimal rank-distance code. An \([n\times m,k,d]_q\) rank-metric code whose parameters are such that the Singleton-like bound \begin{align} k \leq \max(n, m) (\min(n, m) - d + 1) \end{align} become an equality. Parents: Rank-metric code. Cousins: Maximum distance separable (MDS) code, Reed-Solomon (RS) code. Cousin of: Gabidulin code.
Spacetime block code (STBC)[13] In a space-time block code, \(n\) spatially separated channels transmit symbols in \(T\) time slots. These symbols can be arranged in a \(T\times n\) matrix where the columns correspond to the channels, and the rows correspond to the time slots. The codewords \(\{X\}\) are \(T\times n\) matrices such that the codeword difference matrices have rank \(n\), and \(\min_{X\neq 0}\det(XX^*)\) is maximized. Protection: Provides protection against errors due to thermal noise and destructive interference arising from traversing an environment with scattering, reflection, and/or refraction. Parents: Spacetime code (STC). Parent of: Orthogonal Spacetime Block Code (OSTBC).
Orthogonal Spacetime Block Code (OSTBC)[13] The codewords are \(T\times n\) matrices as defined for spacetime codes, with the additional condition that columns of the coding matrix are orthogonal. The parameter \(n\) is the number of channels, and \(T\) is the number of time slots. Protection: If the matrix \(C-C'\), where \(C\) and \(C'\) are distinct codewords, has minimum rank \(b\), the code has diversity order \(bn_R\) (see Ref. [14], Sec. 28.2.1), where \(n_R\) is the number of receivers. The maximum possible diversity order is \(nn_R\). Parents: Spacetime block code (STBC). Parent of: Alamouti code.
Alamouti code[13] The simplest OSTBC, with two time slots, two channels, and with unitary coding matrix \begin{align} \begin{pmatrix}c_{1} & c_{2}\\ -c_{2}^{\star} & c_{1}^{\star} \end{pmatrix}~, \end{align} where \(c_i\) are complex numbers. Parents: Orthogonal Spacetime Block Code (OSTBC).

References

[1]
P. Delsarte, “Bilinear forms over a finite field, with applications to coding theory”, Journal of Combinatorial Theory, Series A 25, 226 (1978). DOI
[2]
V. Tarokh, N. Seshadri, and A. R. Calderbank, “Space-time codes for high data rate wireless communication: performance criterion and code construction”, IEEE Transactions on Information Theory 44, 744 (1998). DOI
[3]
P. Elias, “Error-free Coding”, Transactions of the IRE Professional Group on Information Theory 4, 29 (1954). DOI
[4]
H. Burton and E. Weldon, “Cyclic product codes”, IEEE Transactions on Information Theory 11, 433 (1965). DOI
[5]
G. D. Forney, Jr (1966). Concatenated Codes. MIT Press, Cambridge, MA.
[6]
W. Gore, “Further results on product codes”, IEEE Transactions on Information Theory 16, 446 (1970). DOI
[7]
Andrew Cross et al., “Quantum Locally Testable Code with Exotic Parameters”. 2209.11405
[8]
L. Bahl and R. Chien, “Single- and multiple-burst-correcting properties of a class of cyclic product codes”, IEEE Transactions on Information Theory 17, 594 (1971). DOI
[9]
R. Chien and S. Ng, “Dual product codes for correction of multiple low-density burst errors”, IEEE Transactions on Information Theory 19, 672 (1973). DOI
[10]
E. M. Gabidulin, Theory of Codes with Maximum Rank Distance, Problemy Peredachi Informacii, Volume 21, Issue 1, 3–16 (1985)
[11]
R. M. Roth, “Maximum-rank array codes and their application to crisscross error correction”, IEEE Transactions on Information Theory 37, 328 (1991). DOI
[12]
E. M. Gabidulin, "Theory of Codes with Maximum Rank Distance", Problemy Peredachi Informacii, Volume 21, Issue 1, 3–16 (1985)
[13]
S. M. Alamouti, “A simple transmit diversity technique for wireless communications”, IEEE Journal on Selected Areas in Communications 16, 1451 (1998). DOI
[14]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI