12004 559 ECE233 RE2013 A15 06 PDF

Preview

Summary

lab notes...

Description

PRACTICAL SUBMISSION SHEET

Term: 1st Sem

Submission Date: 11-10-2020

Lecture Date: 3-10-2020

Practical No: 06

Course Code: ECE-233

Section: E2013

Group: EEE

Registration No: 12004559

Student Name: Devath Akhila

Roll No: RE2013A15

HAMMING CODE GENERATION,ERROR DETECTION AND CORRECTION USING FLIPFLOPS AND BASIC GATES: 1. CONCEPT LEARNED: Hamming code is a set of error-correction codes that can be used to detect and correct the errors that can occur when the data is moved or stored from the sender to the receiver. It is technique developed by R.W. Hamming for error correction. Hamming codes can detect up to two-bit errors or correct one-bit errors without detection of uncorrected errors. In this coding method, the source encodes the message by inserting redundant bits within the message. These redundant bits are extra bits that are generated and inserted at specific positions in the message itself to enable error detection and correction. When the destination receives this message, it performs recalculations to detect errors and find the bit position that has error. A parity bit is a check bit, which is added to a block of data for error detection purposes. It is used to validate the integrity of the data. The value of the parity bit is assigned either 0 or 1 that makes the number of 1s in the message block either even or odd depending upon the type of parity. Parity check is suitable for single bit error detection only.

The two types of parity checking are •

•

Even Parity − Here the total number of bits in the message is made even. Odd Parity − Here the total number of bits in the message is made odd. Number of Parity bits can be obtained from the formula: = 2p > p+m+1 Where, M= Number of message bits P= Parity bits Example:

Q: If m=4,then how many parity bits we need to design a hamming code? A: Given, m=4 we know that, 2p > p+m+1,

So, 2p> p+4+1 2p> p+5

[Assume, p=2]

22 > 7 4>7 23 > 8

[Not Equal],[Assume, p=3]

8>8

[So, L.H.S > R.H.S]

So, we need minimum 3 parity bits to transmit 4 message bits. m=4, p=3

p + m= No.of bits of hamming code 3 + 4=7-bit hamming code

20

21

22

1

2

3

P1

P2

m1 P3

4

….. 5

6

7

m2

m3

m4

We need to add parity bits in 2n place in given 1-7 numbers. This is a {7,4} Hamming code in which 7 are total bits and 4 are message bits.

➢ Generating Hamming Code for the Message 1110? Given, 1110 these are the message bits, i.e., m=4 So, p=? we know that,

2p > p+m+1, So, 2p> p+4+1 2p> p+5

[Assume, p=2]

22 > 7 4>7

[Not Equal],[Assume, p=3]

23> 8 8>8

[So, L.H.S > R.H.S]

So, we need minimum 3 parity bits to transmit 4 message bits. ... p=3 Hamming Code:

20

21

22

1

2

3

4

5

P1

P2

m1

P3

m2 m3 m4

0

0

1

0

1

6 1

7 0

We need to add parity bits in 2n place in given 1-7 numbers.

And also we need to take parity values according to odd or even parity to satisfy the defined solutions. EVEN parity transmission: P1→ 1,3,5,7 P1 1 1 0

[P1 should be 0 as to make the code Even.]

→ 0110

P1→ 1,3,5,7 (1s in first place) 001=1 011=3 101=5 111=7

P2→2,3,6,7 P2 1 1 0

[P2 should be 0 as to make the code Even.]

0110

P2→ 2,3,6,7 (1s in second place) 010=2 011=3

110=6 111=7 P3→ 4,5,6,7 P3 1 1 0

[P3 should be 0 as to make the code Even.]

0110

P3→ 4,5,6,7 (1s in third place)

100=4 101=5 110=6 111=7 So, the Hamming code is → 0 0 1 0 1 1 0 Even Parity: 0 0 1 0 1 1 0

Odd Parity: 1 1 1 1 1 1 0 [only the even parity’s 0,1 changes]

Error Correction in Hamming Code: Q: A {7,4} Hamming code is received as 1 1 1 0 0 0 0. Determine the corrected code when even and odd parity are there? A: Given, Hamming code: 1 1 1 0 0 0 0 1

2

3

4

5 6

7

P1 P2 m1 P3 m2 m3 m4 1

1

1

0 0

0

0

Even Parity: E3→ 4,5,6,7 → 0 0 0 0 → E3 = 0 E2→ 2,3,6,7 → 1 1 0 0 → E2 = 0 E1→ 1,3,5,7 → 1 1 0 0 → E1 = 0 As, how many parity bits are present those many are the error bits too. And the process goes on as it is as done with parity bits. So, Error → E3E2E1 → 0 0 0 ... No Error.

Odd Parity: E3→ 4,5,6,7 → 0 0 0 0 → E3 = 1 E2→ 2,3,6,7 → 1 1 0 0 → E2 = 1 E1→ 1,3,5,7 → 1 1 0 0 → E1 = 1 So, Error → E3E2E1 → 1 1 1 Error is in 7th place.

[111=7]

1 1 1 0 0 0 0→error… Corrected Error: 1 1 1 0 0 0 1 We can change the error by changing the binary code vice versa, according to its place in given hamming code.

2. KEY OBSERVATIONS AND SIGHTS: Hamming distance A key issue in designing any error correcting code is making sure that any two valid codewords are sufficiently dissimilar so that corruption of a single bit (or possibly a small number of bits) does not turn one valid code word into another. To measure the distance between two codewords, we just count the number of bits that differ between them. If we are doing this in hardware or software, we can just XOR the two codewords and count the number of 1 bit in the result. This count is called the Hamming distance. The key significance of the hamming distance is that if two codewords have a Hamming distance of d between them, then it would take d single bit errors to turn one of them into the other. For a set of multiple codewords, the Hamming distance of the set is the minimum distance between any pair of its members.

Minimum Hamming distance for error detection To design a code that can detect d single bit errors, the minimum Hamming distance for the set of codewords must be d + 1 (or more). That way, no set of d errors in a single bit could turn one valid codeword into some other valid codeword. Minimum Hamming distance for error correction To design a code that can correct d single bit errors, a minimum distance of 2d + 1 is required. That puts the valid codewords so far apart that even after bit errors in d of the bits, it is still less than half the distance to another valid codeword, so the receiver will be able to determine what the correct starting codeword was.

3. APPLICATION AREAS: Hamming codes are used in, •

• • • • • • • • • •

Computing Telecommunications Data compression Solving puzzles and turbo codes Satellites Plasma CAM Shielded wires Modems Computer memory Open connectors Embedded systems and processor

4. PROJECT FILE/CODE/REPORT: Hamming Code Generation:

Hamming Code Generation, error detection and correction using flipflops and basic gates:

THANKYOU…...