Hamming Codes MCQ Quiz in मल्याळम - Objective Question with Answer for Hamming Codes - സൗജന്യ PDF ഡൗൺലോഡ് ചെയ്യുക

Concept:

Hamming distance between two words of the same size is the number of differences between the corresponding bits. It can be calculated by applying the XOR operation.

Formula:

To guarantee the correction of up to s errors in all cases, the hamming distance in a block code must be d ≥ 2s + 1

Let hamming distance be minimum

∴ dmin = 2s + 1

Calculation

number of errors = s = 5.

∴ dmin = 2(5) + 1 = 11

Important Point:

Minimum Hamming distance is the smallest hamming distance between all possible pairs in a set of words. There are three parameters in this: codeword size, data word size, and minimum Hamming distance. When a codeword is corrupted during transmission, the hamming distance between sent and the received codeword is the number of bits affected by the error.

Hamming code is used to detect errors. Here the codeword belongs to even parity, So when the data word and the parity bits in check word is even then there is no error.

∴ P₁ P₂ D₃ P₄ D₅ D₆ D₇

    1   1   1   1   1   1   1

C₁ = (1, 3, 5, 7)

     =  1 1 1 1 (Even number of 1's, So no error)

C2 = (2, 3, 6, 7)

    = 1 1 0 1 (Odd number of 1's, So error present)

C2 = (4, 5, 6, 7)

    = 1 1 0 1 (Odd number of 1's, So error present)

∴ Check word C = C₄ C₂ C₁

= 1 1 0 = Decimal 6

Hence error is present at 6th position.

So, New code = 1 1 1 1 1 1 1

Concept:

General form of parity check matrix is:

[H] = [P^T I_n-k]

Generator matrix

[G] = [I_k P]

The standard steps to be followed are

1) Find generator matrix

2) List all code words

3) Find minimum hamming distance

Then use the relation

d_min ≥ s + 1

s = No of error that can be detected

d_min = Minimum hamming distance for the code

Calculations:

For (7, 4) code data bits = 4

\(\left[ H \right]=\left[ {{P}^{T}}{{I}_{n-k}} \right]\)

\(\left[ {{P}^{T}} \right]=\left[ \begin{matrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ \end{matrix} \right]\)

\(\left[ P \right]=\left[ \begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ \end{matrix} \right]\)

Generator matrix

G = [I_k P]

\(=\left[ \begin{matrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ \end{matrix} \right]\)

Code words \(=\left[ {{b}_{0}},{{b}_{1}},{{b}_{2}},{{b}_{3}} \right]\left[ \begin{matrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ \end{matrix} \right]\)

Minimum harming distance = 3

d_min ≥ t + 1

3 ≥ t + 1

t ≤ 2

generator matrix g(x) = x³ + x² + 1  = (1101)

message = 1101101

Pad the message single with the number of zeroes equal to highest degree of the generator matrix (3)

New message signal 1101101000

Now,

Hence the CRC code is 0110

The Hamming distance between two code words is the number of bits locations in which their elements differ.

Concept:

Hamming distance is for comparing two binary data strings. Hamming distance is the number of bit positions in which the two bits are different.

Explanation:

    001111

⊕ 010011

____________

    0 11100

The number of 1's is equal to Hamming distance and hence it is 3.

Tips and Tricks:

There is a change at 3rd, 4th and 5th bit from LSB and hence Hamming distance is 3.

Note:

⊕ → XOR

Concept:

Hamming distance between two words of the same size is the number of differences between the corresponding bits. It can be calculated by applying the XOR operation.

Formula:

To guarantee the correction of up to s errors in all cases, the hamming distance in a block code must be d ≥ 2s + 1

Let hamming distance be minimum

∴ dmin = 2s + 1

Calculation

number of errors = s = 5.

∴ dmin = 2(5) + 1 = 11

Important Point:

Minimum Hamming distance is the smallest hamming distance between all possible pairs in a set of words. There are three parameters in this: codeword size, data word size, and minimum Hamming distance. When a codeword is corrupted during transmission, the hamming distance between sent and the received codeword is the number of bits affected by the error.

The correct option is 1

Solution

Let's break down Hamming codes and the (7,4) example:

• Hamming Codes: These are a type of error-correcting code used in digital communication to detect and correct errors that might occur during transmission. They work by adding extra parity bits to the data.

• (n, k) Notation: Hamming codes are often represented as (n, k), where:

  • 'n' is the total length of the encoded message (including data bits and parity bits).
  • 'k' is the length of the original message (the data bits).

• (7, 4) Hamming Code: In your specific case, (7, 4) means:

  • n = 7: Each codeword has 7 bits in total.
  • k = 4: The original message you're encoding is 4 bits long.

• Parity Bits: The difference between 'n' and 'k' (n - k) gives you the number of parity bits. These parity bits are calculated based on the data bits and are used for error detection and correction. In the (7, 4) code, you have 7 - 4 = 3 parity bits.

For a 7-bit data, we need 4 parity bits.

To determine the number of parity bits required, we use the formula:

2^r >= m + r + 1

Where:

• r = number of parity bits
• m = number of data bits

In this case, m = 7.

So, we need to find the smallest value of r that satisfies the equation:

2^r >= 7 + r + 1

By trying different values for r, we find that r = 4 satisfies the equation.

Therefore, we need 4 parity bits for a 7-bit data in a Hamming code.

Solution

Convolution codes

• Convolution codes are generally error-detecting codes 
• They are comprised of parity bits with the message bits
• In convolution coding, k number of message bits are encoded continuously with m number of parity bits to have an overall sequence of n bits
• Linear matrix is not used to represent convolution code

The convolution code is generally represented by

• State diagram
• Logic tables
• Tree diagram
• Trellis diagram
• Generator polynomial 
• Generator matrix

Hence the correct option is 4