Hamming Codes: History

1 Introduction

An important issue in human history is the transmission of information.
This information is always encoded in some form for example via the spoken or written word (letters), by radio, spoken, or fo example Morse Code, or by telephone, or other means of electronic transmission.

In most cases the information is additionally encoded in some form and needs to be then decoded upon arrival.

For example in radio, information in encoded into electro magnetic waves that upon receipt need to played at just the right frequency.
Most transmission currently is digital. The information is encoded in a string of 0’s and 1’s.

The string is transmitted somehow and then decoded.
In addition there maybe layers of secrecy and additional encryption of the message itself.

This is not our concern here. Instead the medium of tranmission is not perfect, there is no 100% guarantee that what is transmitted arrives at its destination intact.
For example if two people speak to each other a background noise may drown out part of the conversation.

In analog forms of transmission a 0 may be encoded in some kind of voltage value say 0 V, and a 1 as another voltage value, say 1 V.
Upon receipt voltages below some threshold value, say 1/2, are assigned to be a 0 and those above are assigned to be a

1. In digital transmission there maybe some analog component somewhere, or some stray gamma ray that interferes and corrupts the digital information.

1.1 Methods to transmit information and protocols to reduce con- fusion.
If we consider human history, then we should begin perhaps in the early days where people communicate via gestures, facial expressions, and sound sequences.
Later people learned the spoken word and then the written word where words or characters have graphical repre- sentation on clay, paper or parchment.

Even among people from the same culture who are taught the proper gestures, facial expressions and sound sequences, common ways to parse sequences and write them up, confusion occurs when two expressions with different meaning have representations that seem similar.

So a first method to reduce confusion is to ensure that different meanings are represented in very different ways.
We see this for example in the design of letters and fonts (the actual graphical representation) of the letters.

The alphabet is of course not universal.
Some cultures use very different graphical representations, and there are many Western languages where the standard alphabet is not so suitable.
For instance when the V and W sound the same, of C and K, or B and P, or when different letters look similar, for example I and J.

Nevertheless the first step is: to create distance between expressions with different meanings.
The second is to have ways in which confusion can be detected (which usually involves the development of some context in which part of the received expression seems to not make sense

Problem1: Prove that the Cayley digraph has a Hamiltonian path from...