Coding

Problem - Sending data one place to another through a channel yields errors

• Idea: Detecting and correcting errors

• Basic Problem of Coding Theory: Message are transmitted over a communication channel which is subject to noise which distorts messages resulting in errors

Claude Shannon Model:

Source → Encoder → Channel (noise) → Decoder → Receiver.

Coding Theory

- Design of error correction codes for reliable transmission of information across noisy channels

• Goal = Error detection and Error Correction

Applications: CDs, hard drives, deep-space image transmission.

Source Coding: changes the message source such as a data terminal or a human voice to a suitable code for transmission

• Source encoder - transforms output into a sequence of symbols we call “message”

Error Control Coding (Channel Coding): 

• Binary Digits - Digits assigned to words within a rule

  • JUMP - 000 000

  • HOP - 000 111

  • STEP - 111 000

  • GLIDE - 111 111

• Codeword - string of binary digits representing a meaningful message; length of a codeword is the number of binary digits it has

Code - collection of all Codewords

• Repetition Code

• every digit is repeated a number of times

  • Majority Decoding Process - for each block of 5 digits, the original bit must the the one appearing most frequently in the block

• Parity Code

• Binary words are said to be of

  •  even parity if the number of 1’s is even.

  • odd parity  if the number of 1’s in it is odd.

• Hamming Code H (7,4)

• - Uses 4 binary digits + 3 redundancy digits → 7-bit codeword.

  • Simply add given the 3 equations, and determine if it is odd or even, if ODD (1), if EVEN (0)

    • x5=x1+x2+x4

    • x6=x1+x3+x4

    • x7=x2+x3+x4

Hamming Distance

• number of difference between corresponding bits; given same length of two binary words -> d(z,y)

  • Nearest Neighbor Decoding Principle - decodes to the closest valid codeword.

    • You get the nearest neighbor interpreting it as that

Minimum distance of a code:

smallest distance between any two distinct codewords in the code -> d(C)

• Detection and Correction:

  • Min Distance: 2e + 1 = 17

  • ED: 2e = 16

  • EC: e = 8 (ROUND DOWN)