Single parity-check (SPC) code 

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

Cousins

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]
J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
[6]
P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[7]
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
[8]
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[9]
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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: parity_check

Cite as:
“Single parity-check (SPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/parity_check
BibTeX:
@incollection{eczoo_parity_check, title={Single parity-check (SPC) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/parity_check} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/parity_check

Cite as:

“Single parity-check (SPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/parity_check

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/reed_muller/parity_check.yml.