**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Hamming distance

Summary

In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is named after the American mathematician Richard Hamming.
A major application is in coding theory, more specifically to block codes, in which the equal-length strings are vectors over a finite field.
The Hamming distance between two equal-length strings of symbols is the number of positions at which the corresponding symbols are different.
The symbols may be letters, bits, or decimal digits, among other possibilities. For example, the Hamming distance between:
"kain" and "kain" is 3.
"krin" and "krin" is 3.
"kin" and "kin" is 4.
and is 4.
2396 and 2396 is 3.
For a fixed length n, the Hamming distance is a metric on the set of the words of length n (also known as a Hamming space), as it fulfills the conditions of non-negativity, symmetry, the Hamming distance of two words is 0 if and only if the two words are identical, and it satisfies the triangle inequality as well: Indeed, if we fix three words a, b and c, then whenever there is a difference between the ith letter of a and the ith letter of c, then there must be a difference between the ith letter of a and ith letter of b, or between the ith letter of b and the ith letter of c. Hence the Hamming distance between a and c is not larger than the sum of the Hamming distances between a and b and between b and c. The Hamming distance between two words a and b can also be seen as the Hamming weight of a − b for an appropriate choice of the − operator, much as the difference between two integers can be seen as a distance from zero on the number line.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (1)

Related courses (12)

Related people (5)

Related concepts (34)

Related units (2)

Related lectures (143)

COM-102: Advanced information, computation, communication II

Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?

PHYS-100: Advanced physics I (mechanics)

La Physique Générale I (avancée) couvre la mécanique du point et du solide indéformable. Apprendre la mécanique, c'est apprendre à mettre sous forme mathématique un phénomène physique, en modélisant l

ME-390: Foundations of artificial intelligence

This course provides the students with 1) a set of theoretical concepts to understand the machine learning approach; and 2) a subset of the tools to use this approach for problems arising in mechanica

Hamming distance

In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences.

Coding theory

Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods.

Decoding methods

In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, such as a binary symmetric channel. is considered a binary code with the length ; shall be elements of ; and is the distance between those elements. One may be given the message , then ideal observer decoding generates the codeword .

Error-Correcting Codes: Hamming Distance and Polynomial MultiplicationCOM-404: Information theory and coding

Covers error-correcting codes, Hamming distance, and polynomial multiplication in algebraic fields.

Spelling Error Correction

Explores spelling error correction, including neologisms and borrowings, using edit distance and finite-state automata.

Ergodic properties of low complexity symbolic systems

Explores the influence of complexity on ergodic properties of symbolic systems, presenting the Curtis-Hedlund-Lyndon Theorem and constructions of minimal subshifts.

The concepts of pseudocodeword and pseudoweight play a fundamental role in the finite-length analysis of LDPC codes. The pseudoredundancy of a binary linear code is defined as the minimum number of rows in a parity-check matrix such that the corresponding minimum pseudoweight equals its minimum Hamming distance. By using the value assignment of Chen and Klove we present new results on the pseudocode-word redundancy of binary linear codes. In particular, we give several upper bounds on the pseudoredundancies of certain codes with repeated and added coordinates and of certain shortened subcodes. We also investigate several kinds of k-dimensional binary codes and compute their exact pseudocodeword redundancy.

2019