Error Detection and Correction Codes

Parity bits are extra bits added to a data block to detect errors during transmission. They ensure that the total number of '1' bits in the block is even or odd, depending on the parity scheme.

Entropy is a measure of uncertainty or randomness associated with a random variable. It quantifies the average amount of information needed to describe the outcome of a random event.

Error syndrome is a binary code derived from the received code word that indicates the position of the error(s), if any, within the transmitted code word.

A code with a minimum Hamming distance of 1 can only detect a single error.

A code with a minimum Hamming distance of 10 can detect up to 10 errors.

The allowable combination for the error combination 001 is 101, as it is the closest allowable combination to it.

The allowable combination for the error combination 100 is 'None' as it is not within the Hamming distance of any allowable combination.

The allowable combination for the error combination 011 is 010, as it is the closest allowable combination.

A code word consists of data bits and parity bits.

The average length of codewords (q) is calculated by summing the product of the probability of each symbol (pi) and the length of its corresponding codeword (qi).

The redundancy of a code measures the proportion of redundant bits added to the original data. It is calculated using:

The average length of code words is calculated by taking the sum of the product of each symbol's probability (pi) and its corresponding code word's length (qi).

The efficiency of a code is calculated by dividing the average information by the maximum possible information.

ASCII code is a fixed-length code, meaning that every character is represented by the same number of bits.

Conditional entropy H(Y|X) represents the uncertainty about Y given that X is known. It is calculated by:

Bayes' theorem provides a way to calculate the conditional probability of an event A given another event B. It is given by:

The Chain rule states that the joint entropy of X and Y is equal to the conditional entropy of Y given X plus the entropy of X.

Hartley's formula calculates the amount of information I associated with a message source, which has an alphabet with m symbols, where the message length is n.

Hartley's formula calculates the entropy H associated with a source with an alphabet of m symbols.

Shannon's formula calculates the amount of information I for a message source where events have different probabilities.

Shannon's formula calculates the entropy H for a source with different probabilities for each symbol.

The Hamming code is a specific type of linear block code commonly used for error detection and correction. The formula to create Hamming code is:

Code rate (R) is the ratio of the number of information bits (k) to the total number of bits (n) in a code word.

The Hamming distance between two code words is the number of bit positions in which the two code words differ.

The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

The first step of Shannon-Fano algorithm is to arrange the characters of the alphabet in descending order based on their probabilities.

For a code to be able to detect r errors, the minimum Hamming distance dmin of the code should be at least r+1.

For a code to be able to correct s errors, the minimum Hamming distance dmin of the code should be at least 2s+1.