Chapter 2.7, Problem 5E

Suppose a codding scheme is devised that maps $k$-bit words onto $n$-bit code words. The efficiency of the code is the ratio $k/n$. Compute the efficiency of the coding scheme described in each of the following examples.

Example 1

Example 2

Example 3

Example 4

Example 1: Parity check – Consider $3$-bit words of the form $abc$. One coding scheme maps $abc$ onto $abcd$, where

$d\equiv a+b+c(\mathrm{mod}2)$ is called the parity check digit.

Example 2: Repetition Codes – Multiple errors can be detected (but not corrected) in a scheme in which a $k$-bit word is mapped onto a $2k$-bit code word according to the following scheme:

$x_1{x}_2\dots x_k\stackrel{encode}{\to }{x}_1{x}_2\dots x_k{x}_1{x}_2\dots x_k$

Example 3: Maximum Likelihood Decoding- Multiple errors can be detected and corrected if each $k$-bit word is mapped onto a $3k$- bit code word according to the following scheme (called a triple repetition code):

$x_1{x}_2\dots x_k\stackrel{encode}{\to }{x}_1{x}_2\dots x_k{x}_1{x}_2\dots x_k{x}_1{x}_2\dots x_k$

Example 4: Error Detection and Correction – Suppose $4$-bit words are mapped onto $9$-bit code words using the scheme

$x_1{x}_2{x}_3{x}_4\stackrel{encode}{\to }{x}_1{x}_2{x}_3{x}_4{x}_1{x}_2{x}_3{x}_{4}p$,

Where $p$ is the parity check digit

$p\equiv x_1+x_2+x_3+x_4(\mathrm{mod}2)$.