Hamming bound

In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error-correcting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code. An original message and an encoded version are both composed in an alphabet of q letters. Each code word contains n letters. The original message (of length m) is shorter than n letters. The message is converted into an n-letter codeword by an encoding algorithm, transmitted over a noisy channel, and finally decoded by the receiver. The decoding process interprets a garbled codeword, referred to as simply a word, as the valid codeword "nearest" the n-letter received string. Mathematically, there are exactly qm possible messages of length m, and each message can be regarded as a vector of length m. The encoding scheme converts an m-dimensional vector into an n-dimensional vector. Exactly qm valid codewords are possible, but any one of qn words can be received because the noisy channel might distort one or more of the n letters when a codeword is transmitted. An alphabet set is a set of symbols with elements. The set of strings of length on the alphabet set are denoted . (There are distinct strings in this set of strings.) A -ary block code of length is a subset of the strings of , where the alphabet set is any alphabet set having elements. (The choice of alphabet set makes no difference to the result, provided the alphabet is of size ; for example, any block code defined using the alphabet can be converted to one using the alphabet by a simple substitution cipher and vice versa. E.G. for the block code of length 2, the codewords and could be converted to the codewords and and vice versa.

About this result

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 (45)

Related people (13)

Related units (9)

Related concepts (9)

Related courses (4)

Related lectures (33)

Singleton bound

In coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude upper bound on the size of an arbitrary block code with block length , size and minimum distance . It is also known as the Joshibound. proved by and even earlier by . The minimum distance of a set of codewords of length is defined as where is the Hamming distance between and . The expression represents the maximum number of possible codewords in a -ary block code of length and minimum distance .

Error correction code

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors.

Griesmer bound

In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of linear binary codes of dimension k and minimum distance d. There is also a very similar version for non-binary codes. For a binary linear code, the Griesmer bound is: Let denote the minimum length of a binary code of dimension k and distance d. Let C be such a code. We want to show that Let G be a generator matrix of C. We can always suppose that the first row of G is of the form r = (1, ...

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?

EE-543: Advanced wireless receivers

Students extend their knowledge on wireless communication systems to spread-spectrum communication and to multi-antenna systems. They also learn about the basic information theoretic concepts, about c

PHYS-641: Quantum Computing

After introducing the foundations of classical and quantum information theory, and quantum measurement, the course will address the theory and practice of digital quantum computing, covering fundament

A Gapless Post-quantum Hash Proof System in the Hamming Metric

Serge Vaudenay, Bénédikt Minh Dang Tran

A hash proof system (HPS) is a form of implicit proof of membership to a language. Out of the very few existing post-quantum HPS, most are based on languages of ciphertexts of code-based or lattice-based cryptosystems and inherently suffer from a gap cause ...

2023

Mismatched Decoding Reliability Function at Zero Rate

Marco Bondaschi

We derive an upper bound on the reliability function of mismatched decoding for zero-rate codes. The bound is based on a result by Komlos that shows the existence of a subcode with certain symmetry properties. The bound is shown to coincide with the expurg ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

, , ,

Compute–forward is a coding technique that enables receiver(s) in a network to directly decode one or more linear combinations of the transmitted codewords. Initial efforts focused on Gaussian channels and derived achievable rate regions via nested lattice ...

2022

Untitled COM-102: Advanced information, computation, communication II

Error Channel Guarantees: Singleton's Bound COM-102: Advanced information, computation, communication II

Covers guarantees for MD decoding on an error channel, focusing on Singleton's Bound.

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.