Parity-check code
Description
Also known as a sum-zero 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.
Realizations
Can be realized on almost every communication device. Parity-check codes are some of the earlier error-correcting codes ([1], Ch. 27).
Parents
- Cyclic linear binary code — Since permutations preserve parity, the cyclic permutation of a parity-check codeword is another codeword.
- Nearly perfect code
- Maximum distance separable (MDS) code
- Divisible code — Binary parity-check codes are two-divisible.
Cousins
- Repetition code — Binary parity-check codes and repetition codes are dual to each other.
- \(q\)-ary parity-check code
- 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 parity-check codes are LDGM [2].
- Reed-Muller (RM) code — RM\((m-1,m)\) are parity-check codes.
References
Page edit log
- Victor V. Albert (2022-07-20) — most recent
- Victor V. Albert (2021-12-15)
- Yijia Xu (2021-12-14)
Zoo code information
Cite as:
“Parity-check code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/parity_check