Alternative names: Sum-zero code, Zero-sum code, Even-weight code.
Description
An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check bit or parity bit such that the parity (i.e., sum over all coordinates of each codeword) is zero. If the Hamming weight of a message is odd (even), then the parity bit is one (zero). This code requires only one extra bit of overhead and is therefore inexpensive. Its codewords are all even-weight binary strings. Its automorphism group is \(S_n\).Protection
This code cannot protect information, it can only detect 1-bit error.Rate
The code rate is \(\frac{n}{n+1}\to 1\) as \(n\to\infty\).Decoding
If the receiver finds that the parity information of a codeword disagrees with the parity bit, then the receiver will discard the information and request a resend.Wagner's rule yields a procedure that is linear in \(n\) [1] (see [2; Sec. 29.7.2] for a description).Realizations
Can be realized on almost every communication device. SPCs are some of the earliest error-correcting codes ([3], Ch. 27).Cousins
- Repetition code— Binary SPCs and repetition codes are dual to each other.
- Dual linear code— Binary SPCs and repetition codes are dual to each other.
- Linear binary code— Any \([n,k,d]\) code with odd distance can be extended to an \([n+1,k,d+1]\) code by adding a bit storing the sum of codeword coordinates.
- Low-density generator-matrix (LDGM) code— Concatenated SPCs are LDGM [4].
- \([[4,2,2]]\) Four-qubit code— The \([[4,2,2]]\) code is constructed from the \([4,3,2]\) SPC code via the CSS construction.
- \(D_4\) hyper-diamond lattice— The \(D_4\) lattice is constructed out of the \([4,3,2]\) SPC codes via Construction A [5; pg. 138].
- \(D_n\) checkerboard lattice— \([n,n-1,2]\) SPC codes yield \(D_n\) checkerboard lattices via Construction A [6; Exam. 10.5.1][5; pg. 138].
- Klemm code— The generator matrix of the Klemm code consists of a sum of the generator matrix of the repetition code and twice the generator matrix of the SPC code [7].
- \([[2m,2m-2,2]]\) error-detecting code— The \([[2m,2m-2,2]]\) error-detecting code is constructed via the CSS construction from an SPC code and its dual repetition code [8; Sec. III].
- Classical-product code— SPC codes are used as component codes in classical-product code constructions.
Member of code lists
- \(q\)-ary linear codes
- Algebraic-geometry codes
- Binary linear codes
- Classical codes
- Classical codes with a rate
- Classical codes with notable decoders
- Cyclic codes
- Evaluation codes
- Locally correctable codes
- Locally decodable codes
- Locally recoverable codes
- MDS codes
- Orthogonal arrays and friends
- Realized classical codes
- Small-distance classical codes
- Universally optimal codes
Primary Hierarchy
Parents
A CRC using the divisor 11 is a single parity-check code [9; Sec. 2.3.3].
Reed-Muller (RM) codeGRM Evaluation Divisible Linear \(q\)-ary Linear code over \(\mathbb{Z}_q\) LCC LRC Distributed-storage LDC ECC
SPCs are RM\((m-1,m)\) codes.
\(q\)-ary parity-check codeGRS AG Evaluation MDS Linear \(q\)-ary OA Cyclic Constacyclic \(t\)-design Universally optimal Skew-cyclic LRC Distributed-storage Small-distance block ECC
Binary SPCs are two-divisible.
SPCs are lexicodes [10].
The SPC code is a binary sharp configuration [11; Table 12.1].
\([n,n-1,2]\) Single parity-check (SPC) code
References
- [1]
- R. Silverman and M. Balser, “Coding for constant-data-rate systems”, Transactions of the IRE Professional Group on Information Theory 4, 50 (1954) DOI
- [2]
- A. Lapidoth, A Foundation in Digital Communication (Cambridge University Press, 2017) DOI
- [3]
- Encyclopedia of Computer Science and Technology, Second Edition Volume I (CRC Press, 2017) DOI
- [4]
- T. R. Oenning and Jaekyun Moon, “A low-density generator matrix interpretation of parallel concatenated single bit parity codes”, IEEE Transactions on Magnetics 37, 737 (2001) DOI
- [5]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [6]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [7]
- S. T. Dougherty, P. Gaborit, M. Harada, A. Munemasa, and P. Sole, “Type IV self-dual codes over rings”, IEEE Transactions on Information Theory 45, 2345 (1999) DOI
- [8]
- N. Rengaswamy, R. Calderbank, H. D. Pfister, and S. Kadhe, “Synthesis of Logical Clifford Operators via Symplectic Geometry”, 2018 IEEE International Symposium on Information Theory (ISIT) 791 (2018) arXiv:1803.06987 DOI
- [9]
- M. Ergen, “Basics of Cellular Communication”, Mobile Broadband 19 (2008) DOI
- [10]
- J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
- [11]
- P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Page edit log
- Victor V. Albert (2022-11-08) — most recent
- Victor V. Albert (2022-07-20)
- Victor V. Albert (2021-12-15)
- Yijia Xu (2021-12-14)
Cite as:
“\([n,n-1,2]\) Single parity-check (SPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/parity_check