A Mathematical Theory of Communication

17 An example of efficient coding

1. Describe the Hamming (7, 4) code Shannon gave as an example of efficient coding.
   Blocks of 7 binary symbols where noise flips at most one: \(X_3, X_5, X_6, X_7\) carry the message; \(X_4, X_2, X_1\) are parity bits making \(X_4{+}X_5{+}X_6{+}X_7\), \(X_2{+}X_3{+}X_6{+}X_7\) and \(X_1{+}X_3{+}X_5{+}X_7\) even. At the receiver, the three parity checks \(\alpha\beta\gamma\), read as a binary number, give the position of the wrong bit (0 = no error).

   check	positions
   \(\alpha\)	4 5 6 7
   \(\beta\)	2 3 6 7
   \(\gamma\)	1 3 5 7

   It transmits at exactly the channel capacity, \(\tfrac47\) bits per symbol, with all errors corrected.
   • Shannon, 1948, A Mathematical Theory of Communication (Bell System Technical Journal), §17