## 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].
- 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]
- P. Boyvalenkov, D. Danev, "Linear programming bounds." 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