Triple Check Code

Triple Check Code#

Triple check code#

SUMMARY OF PROPERTIES

block length           n = 6
rank                   m = 3
rate                 m/n = 1/2
minimum distance    d(C) = 3

s = 2, t = 0    double-error detection, no error correction
s = 0, t = 1    no error detection, single-error correction

The message is divided into blocks of three bits \(abc\) where each of \(a\), \(b\), and \(c\) is \(0\) or \(1\). Three check bits \(xyz\) are added where each of \(x\), \(y\), and \(z\) is also \(0\) or \(1\). This is done in such a way that the following three conditions are satisfied.

  1. The number of \(1\) s in \(abx\) is even.

  2. The number of \(1\) s in \(acy\) is even.

  3. The number of \(1\) s in \(bcz\) is even.

\( \begin{aligned} a + b + x &= 2k \\ a + c + y &= 2k \\ b + c + z &= 2k \\ \end {aligned} \)

So if \(abc = 110\) then \(x = 0\), \(y = 1\), and \(z = 1\) and so the code word is \(110011\).

Single-error correction mode

\( \begin{array}{rrr} \text{message } abc & \text{encoded message } abcxyz & a \text{ error} & b \text{ error} & c \text{ error} & x \text{ error} & y \text{ error} & z \text{ error} \\ \hline 000 & 000000 & \textcolor{red}{1}00000 & 0\textcolor{red}{1}0000 & 00\textcolor{red}{1}000 & 000\textcolor{red}{1}00 & 0000\textcolor{red}{1}0 & 00000\textcolor{red}{1} \\ 001 & 001011 & \textcolor{red}{1}01011 & 0\textcolor{red}{1}1011 & 00\textcolor{red}{0}011 & 001\textcolor{red}{1}11 & 0010\textcolor{red}{0}1 & 00101\textcolor{red}{0} \\ 010 & 010101 & \textcolor{red}{1}10101 & 0\textcolor{red}{0}0101 & 01\textcolor{red}{1}101 & 010\textcolor{red}{0}01 & 0101\textcolor{red}{1}1 & 01010\textcolor{red}{0} \\ 011 & 011110 & \textcolor{red}{1}11110 & 0\textcolor{red}{0}1110 & 01\textcolor{red}{0}110 & 011\textcolor{red}{0}10 & 0111\textcolor{red}{0}0 & 01111\textcolor{red}{1} \\ 100 & 100110 & \textcolor{red}{0}00110 & 1\textcolor{red}{1}0110 & 10\textcolor{red}{1}110 & 100\textcolor{red}{0}10 & 1001\textcolor{red}{0}0 & 10011\textcolor{red}{1} \\ 101 & 101101 & \textcolor{red}{0}01101 & 1\textcolor{red}{1}1101 & 10\textcolor{red}{0}101 & 101\textcolor{red}{0}01 & 1011\textcolor{red}{1}1 & 10110\textcolor{red}{0} \\ 110 & 110011 & \textcolor{red}{0}10011 & 1\textcolor{red}{0}0011 & 11\textcolor{red}{1}011 & 110\textcolor{red}{1}11 & 1100\textcolor{red}{0}1 & 11001\textcolor{red}{0} \\ 111 & 111000 & \textcolor{red}{0}11000 & 1\textcolor{red}{0}1000 & 11\textcolor{red}{0}000 & 111\textcolor{red}{1}00 & 1110\textcolor{red}{1}0 & 11100\textcolor{red}{1} \\ \end {array} \)

  • If \(a\) is incorrect then conditions \(1\) and \(2\) fail.

  • If \(b\) is incorrect then conditions \(1\) and \(3\) fail.

  • If \(c\) is incorrect then conditions \(2\) and \(3\) fail.

  • If \(x\) is incorrect then condition \(1\) alone fails.

  • If \(y\) is incorrect then condition \(2\) alone fails.

  • If \(z\) is incorrect then condition \(3\) alone fails.

Double-error detection mode - if a single bit is in error then the above holds and at least one condition fails; if two bits are in error then there is at least one condition involving one but not the other and so at least one condition fails

Properties

  • the code is moderately uneconomical: the encoded message is twice as long as the original

  • for correction, the code can deal with one error in a block of six; for detection, the code can deal with two errors in a block of six

  • since the code deals with one or two errors in a block of six rather than a block of three, the code is not quite as reliable as triple repetition (if used for pure error detection, the code can do rather better than this discussion suggests)

Implementation

  • Encoder: divide the message into blocks of three, and to each block calculate a further three bits satisfying the three conditions; output an amalgamated block of six

  • Error Processor: (assume that the receiver adopts a correction strategy where possible) check the three conditions; if none fail, the word is correct; if one or two fail, correct the single bit involved in the failing conditions and not in the others; if all three fail, send an error signal

  • Decoder: strip the last three bits off each block unless there is an error signal