# Error Detecting Codes

In this tutorial, we are going to learn about the **error detecting codes** with examples.

Submitted by Saurabh Gupta, on November 09, 2019

## Error Detecting Codes

A group of bits is known as words, and these words move as an entity from one block to another in the digital system. While moving from one part to another within the system via transmission media, the bits within the word can get altered/distorted due to external factors, whom we call Noise. Because digital systems need to be accurate to the digit, an error can pose a serious threat. So, several error detecting methods are introduced to find these incorrect bits in the words, which can be corrected and after detection and should be retransmitted.

### Parity

The simplest technique for detecting an error in a word is adding an extra bit in the group of bits, this extra bit is known as the **parity** bit.

There are two types of parity which we consider for **error detection** purposes which are **ODD parity** and **EVEN parity**. In **odd parity**, **0** or **1** parity bit is added to the group of bits such that the total number of 1 bit including the parity bit in word remains odd in number. Similarly, in even parity, 0 or 1 bit is added in the group of bits such that total no. of 1 bit including the parity bit in the word remains even in number.

Given below is a table which contains message bit of 4 bits and the parity bit in odd and even parity cases,

Word of 4 bits | Parity Bit(Odd) | Word of 4 bits | Parity Bit(Even) |
---|---|---|---|

0000 | 1 | 0000 | 0 |

0001 | 0 | 0001 | 1 |

0010 | 0 | 0010 | 1 |

0011 | 1 | 0011 | 0 |

0100 | 0 | 0100 | 1 |

0101 | 1 | 0101 | 0 |

1100 | 1 | 1100 | 0 |

0111 | 0 | 0111 | 1 |

1000 | 0 | 1000 | 1 |

1001 | 1 | 1001 | 0 |

1010 | 0 | 1010 | 0 |

... | ... | ... | ... |

... | ... | ... | ... |

A parity checker circuit is set up on the receiving side which generates an error whenever an odd number of 1's occurs in case of even parity and an even number of 1's occurs in case of odd parity system.

Generally, odd parity is used more often than even parity because even parity does not detect the situation where all 0's is created by a short circuit or other fault condition.

**Example 1: In even-parity system, which of the following words contain an error?**

**0010100011****1010001010****0010000110**

**Answer:** In an even-parity system, total number of 1’s should be even. So,

**0010100011**, contains 4 one bit which is even. Thus, it has no errors.**1011101010**, contains 6 one bit which is even. Thus, it has no errors.**0010000110**, contains 3 one bit which is odd. Thus, this word has an error.

**Example 2: In odd-parity system, which of the following words contain an error?**

**1011101111****1011000011****1011110110**

**Answer:** In an odd-parity system, total number of 1’s should be odd. So,

**1011101111**, contains 8 one bit which is even. Thus, it has an error.**1011000011**, contains 5 one bit which is odd. Thus, it has no errors.**1011110110**, contains 7 one bit which is odd. Thus, it has no errors.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions