Single parity-check (SPC) code
Description
Also known as a sum-zero, zero-sum, or even-weight code. An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check 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.
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 linear binary code — Since permutations preserve parity, the cyclic permutation of an SPC codeword is another codeword. The generator polynomial of the code is \(x-1\).
- \(q\)-ary parity-check code
- Reed-Muller (RM) code — RM\((m-1,m)\) are parity-check codes.
- 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 [4; Table 12.1].
Cousins
- Repetition 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 [5].
- \(D_n\) checkerboard lattice code — \([n,n-1,2]\) SPC codes yield \(D_n\) checkerboard lattice codes via the mod-two lattice construction [6; Ex. 10.5.1].
- CSS 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]
- W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [5]
- 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
- [6]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
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