HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
Introduction
In this article we will examine the various types of encoding schemes which are used for encoding and decoding of data.
All schemes for coding and decoding of data can be divided in to the following two categories
- Block Codes
- Convolution codes
All coding schemes are capable of performing at least one or more of the tasks mentioned below
- Detect if any bit in the message has been flipped.
- Detect the particular bit in the message which has been flipped.
- Correct the bit which has been flipped.
It may be noted that depending on the coding scheme used, it may be possible to detect if more than one bit has been flipped simultaneously. However it may /may not be possible to select the correct permutation of the bits as were present in the original message (soft decoding).
Block Code
A block code is defined as a set of rules for converting a set of source bits s_1, s_2, s_3, s_4 of length K into a set of transmitted bits s_1, s_2, s_3, s_4 , p_1, p_2, p_3 of length N where p_1, p_2, p_3 are the parity bits (length of parity bits is = N-K).
Block codes encode each bit in the given sequence of source bits separately and the output of a block code is always fixed.
We now present an example of Block Code
(N,K) Hamming Code
N Total number of bits in the message
K Number of Source bits.
(N-K) Parity check bits.
The source and the parity can have the following values {0,1}.
The parity bits are used to keep track of the number of {1} in the sequence of source bits. The value of the parity bit is assigned in the following manner
P_k = 0 if the number of {1s} is even.
P_k = 1 if the number of {1s} is odd.
The value of the parity bits is set as follows :
\begin{eqnarray}
p_1 = (s_1 + s_2 + s_3) \% 2 \\
p_2 = (s_1 + s_3 + s_4) \% 2 \\
p_3 = (s_1 + s_2 + s_4) \% 2
\end{eqnarray}
This encoding scheme has the follwing capabilities :
- Single bit errors can be detected and corrected.
- Double bit errors can be detected but not corrected.
Reference
[1] Hamming Code [http://en.wikipedia.org/wiki/Hamming_code]
Categories: Wireless Software
Comments
