Also known as 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).
Parents
- Cyclic redundancy check (CRC) code — A CRC using the divisor 11 is a single parity-check code [4; Sec. 2.3.3].
- Reed-Muller (RM) code — SPCs are RM\((m-1,m)\) codes.
- \(q\)-ary parity-check code
- Nearly perfect code
- Maximum distance separable (MDS) code
- Divisible code — Binary SPCs are two-divisible.
- \(q\)-ary sharp configuration — The SPC code is a binary sharp configuration [5; Table 12.1].
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 [6].
- \(D_n\) checkerboard lattice code — \([n,n-1,2]\) SPC codes yield \(D_n\) checkerboard lattice codes via Construction A [7; Ex. 10.5.1].
- \([[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.
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]
- M. Ergen, “Basics of Cellular Communication”, Mobile Broadband 19 (2008) DOI
- [5]
- P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [6]
- 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
- [7]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [8]
- N. Rengaswamy et al., “Synthesis of Logical Clifford Operators via Symplectic Geometry”, 2018 IEEE International Symposium on Information Theory (ISIT) (2018) arXiv:1803.06987 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:
“Single parity-check (SPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/parity_check