Description
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 [5; Lemma 3.3].
Codewords are those matrices whose column vectors are in \(C_A\) and whose row vectors are in \(C_B\). In other words, the matrix-valued codewords \(c\) of a tensor code satisfy the parity check equation \(H_A c H^{\text{T}}_B = 0\).
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 [6,7].
Many (but not all [8]) tensor codes are robustly testable [9–11], a property useful for constructing LTCs [12], including a family of \(c^3\)-LTCs [13]. Duals of tensor codes formed by two random linear codes are also robustly testable, a property useful for constructing asymptotically good QLDPC codes [14,15] and proving distance bounds [16].
Rate
Decoding
Realizations
Notes
Parents
Cousins
- Left-right Cayley complex code — Left-right Cayley complex codewords for a fixed graph vertex are codewords of a tensor code.
- Low-density parity-check (LDPC) code — Tensor products of random LDPC codes are robustly testable [10,11].
- Reed-Solomon (RS) code — Tensor codes constructed from RS codes are robustly testable [21].
- Quantum check-product code — Quantum check-product codes extend the concept of a check product, which yields the dual of a tensor code, to a product between a classical and a quantum code.
- Classical-product code — Tensor-product codes are utilized in classical-product code constructions.
- Dinur-Hsieh-Lin-Vidick (DHLV) code — Tensor codes are used in constructing quantum DHLV codes.
- Quantum Tanner code — Tensor codes are used in constructing quantum Tanner codes.
References
- [1]
- P. Elias, “Error-free Coding”, Transactions of the IRE Professional Group on Information Theory 4, 29 (1954) DOI
- [2]
- H. Burton and E. Weldon, “Cyclic product codes”, IEEE Transactions on Information Theory 11, 433 (1965) DOI
- [3]
- G. D. Forney, Jr (1966). Concatenated Codes. MIT Press, Cambridge, MA.
- [4]
- W. Gore, “Further results on product codes”, IEEE Transactions on Information Theory 16, 446 (1970) DOI
- [5]
- A. Cross et al., “Quantum Locally Testable Code with Constant Soundness”, (2023) arXiv:2209.11405
- [6]
- 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
- [7]
- 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
- [8]
- P. Valiant, “The Tensor Product of Two Codes Is Not Necessarily Robustly Testable”, Lecture Notes in Computer Science 472 (2005) DOI
- [9]
- E. Ben-Sasson and M. Sudan, “Robust Locally Testable Codes and Products of Codes”, (2004) arXiv:cs/0408066
- [10]
- 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
- [11]
- E. Ben-Sasson and M. Viderman, “Tensor Products of Weakly Smooth Codes Are Robust”, Lecture Notes in Computer Science 290 (2008) DOI
- [12]
- I. Dinur, “The PCP theorem by gap amplification”, Journal of the ACM 54, 12 (2007) DOI
- [13]
- I. Dinur et al., “Locally Testable Codes with constant rate, distance, and locality”, (2021) arXiv:2111.04808
- [14]
- I. Dinur et al., “Good Quantum LDPC Codes with Linear Time Decoders”, (2022) arXiv:2206.07750
- [15]
- G. Kalachev and P. Panteleev, “Two-sided Robustly Testable Codes”, (2022) arXiv:2206.09973
- [16]
- A. Leverrier and G. Zémor, “Decoding quantum Tanner codes”, (2022) arXiv:2208.05537
- [17]
- G. Forney, “Generalized minimum distance decoding”, IEEE Transactions on Information Theory 12, 125 (1966) DOI
- [18]
- P. Chaichanavong and P. H. Siegel, “Tensor-product parity code for magnetic recording”, IEEE Transactions on Magnetics 42, 350 (2006) DOI
- [19]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [20]
- 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.
- [21]
- 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
- Victor V. Albert (2022-08-09) — most recent
- Shashank Sule (2022-04-21)
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/tree/main/codes/classical/matrices/tensor.yml.