Question

In: Computer Science

write and explain two dimensional parity check code and hamming codes in simple way please

write and explain two dimensional parity check code and hamming codes
in simple way please

Solutions

Expert Solution

TWO DIMENSIONAL PARITY

We will make a Two Dimensional array from the message bit. After that, according to the even or odd parity, We will fill make the last column and last row of the matrix.

Total Parity Bits – i + j + 1 (Row+Column+1)

Here Parity Bit = 3 + 5 +1 = 9

One point is to be Remember that the Value of (i, j ) should be of message array i.e. inspite of having the value of i = 4, j = 6 (which is of array with parity bits). we will take value of message array i.e i=3, j=5.

Row and column parity bits are known as Redundant Bits i.e i+j+1.

The code that is to be transmitted will be the whole message included Redundant Bits.
For ex :

Now, this code is transmitted and reaches the receiver side, where the receiver will again form a similar Two Dimensional array.

CASES OCCURS IN TWO DIMENSIONAL PARITY

CASE 1 :

Suppose a bit is in error. Then it can be easily detected and the code is corrected. As shown in fig.

CASE 2 :

When two erroneous bits are detected and corrected. The undesired part is that two other bits also detected as an incorrect bit.

CASE 3 :

When odd no. of error takes place in a particular row or particular column.

CASE 4 :

When even no. of error takes place in a particular row.

CASE 5 :

Where the error is not detected so not corrected.

HAMMING CODES

Hamming code is a liner code that is useful for error detection up to two immediate bit errors. It is capable of single-bit errors.

In Hamming code, the source encodes the message by adding redundant bits in the message. These redundant bits are mostly inserted and generated at certain positions in the message to accomplish error detection and correction process.

Calculating the Hamming Code

The key to the Hamming Code is the use of extra parity bits to allow the identification of a single error. Create the code word as follows:

  1. Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.)
  2. All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.)
  3. Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips.
    Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,...)
    Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,...)
    Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,...)
    Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,...)
    Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,...)
    Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,...)
    etc.
  4. Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if the total number of ones in the positions it checks is even.

Here is an example:

A byte of data: 10011010
Create the data word, leaving spaces for the parity bits: _ _ 1 _ 0 0 1 _ 1 0 1 0
Calculate the parity for each parity bit (a ? represents the bit position being set):

  • Position 1 checks bits 1,3,5,7,9,11:
    ? _ 1 _ 0 0 1 _ 1 0 1 0. Even parity so set position 1 to a 0: 0 _ 1 _ 0 0 1 _ 1 0 1 0
  • Position 2 checks bits 2,3,6,7,10,11:
    0 ? 1 _ 0 0 1 _ 1 0 1 0. Odd parity so set position 2 to a 1: 0 1 1 _ 0 0 1 _ 1 0 1 0
  • Position 4 checks bits 4,5,6,7,12:
    0 1 1 ? 0 0 1 _ 1 0 1 0. Odd parity so set position 4 to a 1: 0 1 1 1 0 0 1 _ 1 0 1 0
  • Position 8 checks bits 8,9,10,11,12:
    0 1 1 1 0 0 1 ? 1 0 1 0. Even parity so set position 8 to a 0: 0 1 1 1 0 0 1 0 1 0 1 0
  • Code word: 011100101010.

Finding and fixing a bad bit

The above example created a code word of 011100101010. Suppose the word that was received was 011100101110 instead. Then the receiver could calculate which bit was wrong and correct it. The method is to verify each check bit. Write down all the incorrect parity bits. Doing so, you will discover that parity bits 2 and 8 are incorrect. It is not an accident that 2 + 8 = 10, and that bit position 10 is the location of the bad bit. In general, check each parity bit, and add the positions that are wrong, this will give you the location of the bad bit.


Related Solutions

Differentiate between parity code and hamming code with examples
Differentiate between parity code and hamming code with examples
Construct a generator matrix and a parity check matrix for a ternary Hamming code Ham(2, 3)....
Construct a generator matrix and a parity check matrix for a ternary Hamming code Ham(2, 3). Assume a codeword x from for the ternary Hamming code Ham(2, 3)$ was sent and the word y was received. Use the partiy check matrix you constructed in part (a) to decode y in each part using syndrome decoding: (b) y = ( 1 , 1 , 1 , 0 ), (c) y = ( 2 , 2 , 2 , 2 ), (d)...
Construct an even parity Hamming code for 1101010
Construct an even parity Hamming code for 1101010
The data to be sent : 11011100110, how to create the Hamming code with even parity?...
The data to be sent : 11011100110, how to create the Hamming code with even parity? If the right most bit is changed due to noise during transmission, how does the receiver to correct the incorrect bit. Assume only one bit is altered during transmission.  
Construct an even parity Hamming code with a total of 7 bits (4 data bits and...
Construct an even parity Hamming code with a total of 7 bits (4 data bits and 3 check bits).
Given the data-bits m = 11010110, determine the number of k (parity-bits) by using Hamming Code...
Given the data-bits m = 11010110, determine the number of k (parity-bits) by using Hamming Code requirements. Illustrate the error detection and correction scheme using Hamming code method, for both the sender and receiver to detect an error at the following positions: a.6thbit position. b.11thbit position.Assume an odd-parity scheme for this problem.
Given the data-bits m = 11010110, determine the number of k (parity-bits) by using Hamming Code...
Given the data-bits m = 11010110, determine the number of k (parity-bits) by using Hamming Code requirements. Illustrate the error detection and correction scheme using Hamming code method, for both the sender and receiver to detect an error at the following positions: a. 6th bit position. b. 11th bit position. Assume an odd-parity scheme for this problem.
Please attach the output screenshots, narrative descriptions, or paste the Python codes. Please write code to...
Please attach the output screenshots, narrative descriptions, or paste the Python codes. Please write code to print the type of the following variables. Please write down the codes and the output as well. x = 3.5 y = '3.5' z = {1:'John', 2:'Wick', 3:'Barry', 4:'Allen'}
Error detection/correction C Objective: To check a Hamming code for a single-bit error, and to report...
Error detection/correction C Objective: To check a Hamming code for a single-bit error, and to report and correct the error(if any) Inputs: 1.The maximum length of a Hamming code 2.The parity of the check bits (even=0, odd=1) 3.The Hamming code as a binary string of 0’s and 1’s Outputs: 1.The original parity bits (highest index to lowest index, left to right) 2.The new parity bits (highest index to lowest index, left to right) 3.The bit-wise difference between the original parity...
Given the 21-bit even-parity Hamming code: 0 1010 0111 0011 0000 0101 and assuming there is...
Given the 21-bit even-parity Hamming code: 0 1010 0111 0011 0000 0101 and assuming there is one incorrect bit. a. Which bit is incorrect? My educated guess for what the incorrect bit maybe has me thinking it is the '1' bit at the end of the '0111' byte, but I have no full proof as to why it is that specific bit. Am I in the right area to think that? b. After the error is corrected, what decimal number...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT