Tensor-product code[14] 

Also known as Tensor code, Kroneckerian code, 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, denoted as \(C_{A}\boxplus C_{B}\).

Codewords are those matrices whose column vectors are in \(C_A=[n_A,k_A,d_A]\) and whose row vectors are in \(C_B=[n_B,k_B,d_B]\). Codewords \(c\) of a tensor code satisfy the parity check equation \(H_A c H^{\text{T}}_B = 0\).

A check-product code forms the matrix subspace dual to its corresponding tensor-product code, \begin{align} \label{eq:dual-tensor} C_{A}\boxplus C_{B}=C_{A}\otimes GF(2)^{n_{B}}+GF(2)^{n_{A}}\otimes C_{B}~. \tag*{(1)}\end{align} The parity-check matrix of this code is \(H_A \otimes H_B\), where \(H_{A,B}\) is the parity-check matrix of \(C_{A,B}\) [5; Lemma 3.3].


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 [6,7].

Many (but not all [8]) tensor codes are robustly testable [911], a property useful for constructing LTCs [12], including a family of \(c^3\)-LTCs [13]. A property equivalent to robust testability is \(\kappa\)-product expansion [14]. For check-product codes, this property means that for every codeword \(c_1 + c_2 \in C_{A}\boxplus C_{B}\), split up according to (1), \begin{align} \kappa\left(\frac{\|c_{1}\|_{A}}{n_{A}}+\frac{\|c_{2}\|_{B}}{n_{B}}\right)\leq\frac{|c_{1}+c_{2}|}{n_{A}n_{B}}~, \tag*{(2)}\end{align} where \(\|c_{1}\|_{A}\) (\(\|c_{2}\|_{B}\)) is the number of non-zero columns (rows) in \(c_1\) (\(c_2\)).

Check-product codes formed by two random linear codes are robustly testable [15; Thm. 1], a property useful for constructing asymptotically good QLDPC codes [15,16] and proving distance bounds [17].


Rate of the tensor-product code \(C_A \otimes C_B\) is a product of the rates of the codes \(C_A\) and \(C_B\).


The simple decoding algorithm (first decode all columns with \(C_1\), then all rows with \(C_2\)) corrects up to \((d_A d_B-1)/4 \) errors.Algorithms such as generalized minimum-distance decoding [18] or the min-sum algorithm can decode all errors of weight up to \((d_A d_B-1)/2\). Error location may be coupled with Viterbi decoding for every faulty sub-block [19].


Construction can be used in magnetic recording by taking the tensor product of a Reed-Solomon code and a parity-check code [19].


See Refs. ([20], Ch. 18; [21]) for expositions.




P. Elias, “Error-free Coding”, Transactions of the IRE Professional Group on Information Theory 4, 29 (1954) DOI
H. Burton and E. Weldon, “Cyclic product codes”, IEEE Transactions on Information Theory 11, 433 (1965) DOI
G. D. Forney, Jr (1966). Concatenated Codes. MIT Press, Cambridge, MA.
W. Gore, “Further results on product codes”, IEEE Transactions on Information Theory 16, 446 (1970) DOI
A. Cross et al., “Quantum Locally Testable Code with Constant Soundness”, (2023) arXiv:2209.11405
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
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
P. Valiant, “The Tensor Product of Two Codes Is Not Necessarily Robustly Testable”, Lecture Notes in Computer Science 472 (2005) DOI
E. Ben-Sasson and M. Sudan, “Robust Locally Testable Codes and Products of Codes”, (2004) arXiv:cs/0408066
I. Dinur, M. Sudan, and A. Wigderson, “Robust Local Testability of Tensor Products of LDPC Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 304 (2006) DOI
E. Ben-Sasson and M. Viderman, “Tensor Products of Weakly Smooth Codes Are Robust”, Lecture Notes in Computer Science 290 (2008) DOI
I. Dinur, “The PCP theorem by gap amplification”, Journal of the ACM 54, 12 (2007) DOI
I. Dinur et al., “Locally Testable Codes with constant rate, distance, and locality”, (2021) arXiv:2111.04808
P. Panteleev and G. Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”, (2022) arXiv:2111.03654
G. Kalachev and P. Panteleev, “Two-sided Robustly Testable Codes”, (2023) arXiv:2206.09973
I. Dinur et al., “Good Quantum LDPC Codes with Linear Time Decoders”, (2022) arXiv:2206.07750
A. Leverrier and G. Zémor, “Decoding quantum Tanner codes”, (2022) arXiv:2208.05537
G. Forney, “Generalized minimum distance decoding”, IEEE Transactions on Information Theory 12, 125 (1966) DOI
P. Chaichanavong and P. H. Siegel, “Tensor-product parity code for magnetic recording”, IEEE Transactions on Magnetics 42, 350 (2006) DOI
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
Wolf, Jack Keil. "An introduction to tensor product codes and applications to digital storage systems." 2006 IEEE Information Theory Workshop-ITW 2006 Chengdu. IEEE, 2006.
A. Polishchuk and D. A. Spielman, “Nearly-linear size holographic proofs”, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC ’94 (1994) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: tensor

Cite as:
“Tensor-product code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/tensor
@incollection{eczoo_tensor, title={Tensor-product code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/tensor} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Tensor-product code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/tensor

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/matrices/tensor.yml.