Hamming distance

In information theory, the effectiveness of block codes is called Hamming distance and depends on the difference between one valid code word and another. The greater this difference, the less is the chance that a valid code will be transformed into another valid code by a series of errors. This difference is called the Hamming distance, and is defined as the number of bits that have to be changed to transform a valid codeword into another valid codeword.
If two codewords differ by a distance d, d errors are needed to convert one to the other.

For example:

• The Hamming distance between 1011101 and 1001001 It's 2.
• The Hamming distance between 2143896 and 2233796 It's 3.
• The Hamming distance between "tener"and..."reses"It's 3.

Error detection and correction

Hamming's distance is used to define some essential notions in code theory, such as error detector codes and error correction codes. In particular, it is said that a code C{displaystyle C} detect k{displaystyle k}- terrors if two words any c1,c2한 한 C{displaystyle c_{1},c_{2}in C} that have a distance of less than Hamming k{displaystyle k} They match. In other words, a code detects k{displaystyle k}- mistakes if and only if the distance of Hamming minimum between two words any in it is at least k+1{displaystyle k+1}.

It's said a code C{displaystyle C} correct k{displaystyle k}- mistakes if for every word w{displaystyle w} in the underlying Hamming space H{displaystyle H} There is at least one word c한 한 C{displaystyle cin C} such that the distance from Hamming w{displaystyle w} and c{displaystyle c} It's less than k{displaystyle k}. In other words, a code corrects k{displaystyle k}- mistakes if and only if the minimum distance of Hamming between two any of his words is at least 2k+1{displaystyle 2k+1}. This is easier to understand geometrically as two closed balls any radio k{displaystyle k} focused on different words are disjoint. In this context these balls are known as areas of Hamming.

In this way, a code that has distance of minimum Hamming d{displaystyle d} among his words can detect the most d− − 1{displaystyle d-1} errors and can correct (d− − 1)/2 {displaystyle lfloor (d-1)/2rfloor } mistakes. This last number is also known as the Radio packing or correction capacity code.

History and applications

The Hamming distance is named after its inventor Richard Hamming, a professor at the University of Nebraska, who introduced the term to establish a metric capable of establishing a code for detection and self-correction of codes. It is used in the transmission of digitized information to count the number of deviations in chains of equal length and to estimate the error, for this reason it is sometimes called signal distance.

The Hamming distance has the following properties.

• d(a,b)=d(b,a){displaystyle d(a,b)=d(b,a)}
• d(a,b)=0{displaystyle d(a,b)=0} Yes and only if a=b{displaystyle a=b}
• d(a,b)+d(b,c)≥ ≥ d(a,c){displaystyle d(a,b)+d(b,c)geq d(a,c)}

d is the number of p bits by which the sent message differs from the received message.

Yeah. d≥ ≥ p+1{displaystyle dgeq p+1} Then you can detect a weight error p

Yeah. d≥ ≥ 2p+1{displaystyle dgeq 2p+1} Then you can correct p digits.

Example: If we want to detect 3 errors then the minimum distance of Hamming must be (3)+1=4{displaystyle (3)+1=4}. If we want to correct 3 errors then the minimum distance of Hamming must be 2↓ ↓ (3)+1=7{displaystyle 2*(3)+1=7}.