Problem 6 - Digital Design

1.

Show the logic diagram of the circuit than can correct a single-bit error and show the position of the error using logic gates (AND, OR, NOT, EXOR) for 4-bit data where extra bits for error detection/correction are attached besides 4-bit data.

2.

Show the width of attached bits for realizing 1-bit error correction and 2-bit error detection for 16-bit data and describe the outline of the logic design.

1.

The block length of a Hamming code is given by

$$n=2^r-1, \quad r\geq 3$$

For $n$ bits, we have $r$ parity bits and $k=2^r-1-r$ information bits. Here $k=4$, $r=3$, and $n=7$. We begin with the parity-check matrix $H$ for the systematic Hamming code. This matrix has $r$ rows and $n$ columns. The first $r$ columns are specified as the $r\times r$ identity matrix. The remaining $k$ columns consist of nonzero binary vectors of length $r$.

$$H=\left[\begin{array}{ccccccc} 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ \end{array}\right]$$

The form for the parity-check matrix for a systematic code is

$$H = \left[I\;\vert\;-P^T\right]$$

The generator matrix $G$ for the systematic code is

$$G = \left[P\;\vert\;I\right]$$

$$G = \left[\begin{array}{ccccccc} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1... ...& 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{array}\right]$$

For all Hamming codes, $d_{\min}=3$. We can use that code to correct a single error. The codes may be decoded using a syndrome table. For the error vector with its error in the $i$th column of $\bar{e}$, the corresponding syndrome is the $i$th row of $H^T$

$$\begin{tabular}{cc} $\bar{e}$ & $\bar{s}$ \\ \hline 1000000 & 1... ...110 \\ 0000100 & 101 \\ 0000010 & 011 \\ 0000001 & 111 \\ \end{tabular}$$

If we count bit positions in the error vector from left to right, starting with 1, this position corresponds to the number obtained from reading the symdrome from right to left, with the exception of syndromes 001 and 110.

$$G = \left[\begin{array}{ccccccc} 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1... ...& 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ \end{array}\right]$$

$$H=\left[\begin{array}{ccccccc} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{array}\right]$$

The code vector formed by $G$ are of the form

$$\bar{c}=[c_0 c_1 m_0 c_3 m_1 m_2 m_3]$$

$$c_0 = m_0 \oplus m_1 \oplus m_3$$

$$c_1 = m_0 \oplus m_2 \oplus m_3$$

$$c_3 = m_1 \oplus m_2 \oplus m_3$$

And the parity generator has the following implementation:

$$\includegraphics{hamming-code-parity-generator.ps}$$

We recalculate the parity bits and compare them to the parity bits received:

$$c_0' = m_0 \oplus m_1 \oplus m_3 \oplus c_0$$

$$c_1' = m_0 \oplus m_2 \oplus m_3 \oplus c_1$$

$$c_3' = m_1 \oplus m_2 \oplus m_3 \oplus c_3$$

There is a one-to-one mapping between the altered bit and the binary value of $c_0'c_1'c_3'$:

$$\begin{array}{cc} c_0 & 100 \\ c_1 & 010 \\ m_0 & 110 \\... ...1 \\ m_1 & 101 \\ m_2 & 011 \\ m_3 & 111 \\ \end{array}$$

So that the following implementation points out the erronerous bits:

$$\includegraphics{hamming-code-parity-check.ps}$$

2.

We can use the Hamming code for which $n=31$ and $r=5$ ($k=26$) and use padding so that our 16-bit data will fit the 26-bit data space. The outline of the procedure for the effective implementation is similar.