Parity Check Codes#
\((8, 7)\) parity check code#
ECFF
1992
Pretzel, Oliver. Error-Correcting Codes and Finite Fields. Oxford University Press Applied Mathematics and Computing Science Series.
SUMMARY OF PROPERTIES
block length n = 8
rank m = 7
rate m/n = 7/8
minimum distance d(C) = 2 because C consists of all words of even weight
s = 1 single-error detection
t = 0 no error correction
Introduction
A byte, or \(8\) bits, is a common unit of information in computer systems which can represent values from \(0\) to \(255\) inclusive.
If we want to transmit English messages we can use the following alphabet.
\( \begin{aligned} \text{L} &= \text{\{ a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z \}} \\ \text{U} &= \text{\{ A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z \}} \\ \text{D} &= \text{\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}} \\ \text{P} &= \{ \texttt{!}, \texttt{"}, \texttt{\#}, \texttt{\$}, \texttt{\%}, \texttt{\&}, \texttt{'}, \texttt{(}, \texttt{)}, \texttt{*}, \texttt{+}, \texttt{,}, \texttt{-}, \texttt{.}, \texttt{/}, \texttt{:}, \texttt{;}, \texttt{<}, \texttt{=}, \texttt{>}, \texttt{?}, \texttt{@}, \texttt{[}, \texttt{\textbackslash}, \texttt{]}, \texttt{\textasciicircum}, \texttt{\_}, \texttt{`}, \texttt{\{}, \texttt{|}, \texttt{\}}, \texttt{\textasciitilde} \} \\ \text{W} &= \{ \langle \texttt{space} \rangle, \texttt{\textbackslash t}, \texttt{\textbackslash n}, \texttt{\textbackslash r}, \texttt{\textbackslash x0b}, \texttt{\textbackslash x0c} \}\\ A &= \text{L} \cup \text{U} \cup \text{D} \cup \text{P} \\ |A| &= 94 = 26 + 26 + 10 + 32 \\ \end {aligned} \)
Observe that the number of symbols plus thirty or so more for control codes amounts to less than \(127 = 2^7 - 1\) or just \(7\) bits. Thus the eighth bit of a byte can be used as a parity bit to check that the byte has been received without error. The eighth bit is set so that the number of \(1\) s in the byte is even. This way, if a byte is transmitted and one of the bits goes wrong then the number of \(1\) s becomes odd and the receiver can ask for a retransmission. There is no way the receiver can tell which bit went wrong, and if two bits are incorrect the receiver will let the byte through. In practice, the order of the bits is reversed so that the check bit comes first.
For example
\( \begin{array}{rr|r} \text{symbol} & 7\text{-bit ASCII code} & 8\text{-bit encoding} \\ \hline 1 & \underset{2^0}{1}000\underset{2^4}{1}\underset{2^5}{1}0 & \underbrace{1000110}1 \\ \text{A} & \underset{2^0}{1}00000\underset{2^6}{1} & \underbrace{1000001}0 \\ \end {array} \)
Error-correcting capabilities
(1)
The code is economical: the encoded message is \(1/7\) th longer than the original. This means that if the original message has length \(n\) then the encoded message has length
\( \begin{aligned} n + \frac{1}{7}n = n \left( 1 + \frac{1}{7} \right) = \frac{8}{7} n \end {aligned} \)
In our case, \(n = 7\) and so the encoded message has length \(8\).
(2)
The code cannot correct errors; it is only suitable where the receiver can ask for retransmission, since errors can be detected but cannot be located
(3)
The probability of errors during transmission should be fairly low, because the code cannot cope with two errors in a byte
Implementation
Encoder: divide the message into blocks of seven, and to each block add an eighth bit to make the number of \(1\) s even
Error Processor: (assume that the receiver adopts a correction strategy where possible) count the number of \(1\) s in the received block, and emit an error signal if the number is odd
Decoder: strip the eighth bit