Tensor-product code[14] 

Also known as Tensor code, Kroneckerian code, Product code.

Description

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].

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 [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

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\).

Decoding

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].

Realizations

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

Notes

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

Parents

Cousins

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]
P. Panteleev and G. Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”, (2022) arXiv:2111.03654
[15]
G. Kalachev and P. Panteleev, “Two-sided Robustly Testable Codes”, (2023) arXiv:2206.09973
[16]
I. Dinur et al., “Good Quantum LDPC Codes with Linear Time Decoders”, (2022) arXiv:2206.07750
[17]
A. Leverrier and G. Zémor, “Decoding quantum Tanner codes”, (2022) arXiv:2208.05537
[18]
G. Forney, “Generalized minimum distance decoding”, IEEE Transactions on Information Theory 12, 125 (1966) DOI
[19]
P. Chaichanavong and P. H. Siegel, “Tensor-product parity code for magnetic recording”, IEEE Transactions on Magnetics 42, 350 (2006) DOI
[20]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[21]
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.
[22]
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
BibTeX:
@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:
https://errorcorrectionzoo.org/c/tensor

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.