Outline

  1. Why need encode
  2. Different coding method

Error Correction

Link

correction may generally be realized in two different ways:

  • Automatic repeat request (ARQ) (sometimes also referred to as backward error correction): This is an error control technique whereby an error detection scheme is combined with requests for retransmission of erroneous data. Every block of data received is checked using the error detection code used, and if the check fails, retransmission of the data is requested – this may be done repeatedly, until the data can be verified.
  • Forward error correction (FEC): The sender encodes the data using an error-correcting code (ECC) prior to transmission. The additional information (redundancy) added by the code is used by the receiver to recover the original data. In general, the reconstructed data is what is deemed the “most likely” original data.

Error Detection Schemes

Material

  • Repetition codes
  • Parity codes
  • Cyclic redundancy checks (CRCs)

Coding

Convolutional Coding

viterbi_encoder

  1. The gates are XOR gates not OR gate.
  2. The top bit goes first.
inputs = ("1","0","0","1","1")

Output should be

['1', '1', '1', '0', '1', '1', '1', '1', '0', '1']
Viterbi Decoding
  • Draw the trellis first
  • Walk through an example

trellis

​ Assume the observation is "11", "10".

How to write the decoder:

“Dictionaries” we need to use check:

  • Given a state, what is output (encoded) result if the input is 0 or 1.
  • Given a state, what is the previous input that leads to current state.
  • Given a state, what are the previous states that can transit to current state. In this case, there are always two paths (branches).

“Traces” we need to track:

  • The distance metrics for each state and each input
  • What branch (with minimal distance) it chooses from previous step that leads to current