Hamming code

In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance of three. Richard W. Hamming invented Hamming codes in 1950 as a way of automatically correcting errors introduced by punched card readers. In his original paper, Hamming elaborated his general idea, but specifically focused on the Hamming(7,4) code which adds three parity bits to four bits of data. In mathematical terms, Hamming codes are a class of binary linear code. For each integer r ≥ 2 there is a code-word with block length n = 2r − 1 and message length k = 2r − r − 1. Hence the rate of Hamming codes is R = k / n

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

Related publications

Related people (2)

Related people

Related units (2)

Related units

Related concepts (19)

Related concepts

Related courses (7)

Related courses

Related lectures (12)

Related lectures

New Results On The Pseudoredundancy

Zihui Liu

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

Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels

Seyed Hamed Hassani, Shrinivas Kudekar, Yury Polyanskiy, Rüdiger Urbanke

Consider a binary linear code of length N, minimum distance d(min), transmission over the binary erasure channel with parameter 0 < epsilon < 1 or the binary symmetric channel with parameter 0 < epsilon < 1/2, and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions "quickly" from delta to 1-delta for any delta > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/root d(min)). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as Theta(1/N1/2-kappa), for any kappa > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since Theta(1/N-1/2) is the smallest transition possible for any code, we speak of "almost" optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.

IEEE2018

Linear Programming Decoding of Spatially Coupled Codes

Badih Ghazi, Rüdiger Urbanke

For a given family of spatially coupled codes, we prove that the linear programming (LP) threshold on the binary-symmetric channel (BSC) of the tail-biting graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ensemble. This result is in contrast with the fact that spatial coupling significantly increases the belief propagation threshold. To prove this, we establish some properties related to the dual witness for LP decoding. More precisely, we prove that the existence of a dual witness, which was previously known to be sufficient for LP decoding success, is also necessary and is equivalent to the existence of certain acyclic hyperflows. We also derive a sublinear (in the block length) upper bound on the weight of any edge in such hyperflows, both for regular low-density parity-check (LPDC) codes and spatially coupled codes and we prove that the bound is asymptotically tight for regular LDPC codes. Moreover, we show how to trade crossover probability for LP excess on all the variable nodes, for any binary linear code.

Ieee-Inst Electrical Electronics Engineers Inc2014

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 channel coding, and bit-interleaved coded modulation.

COM-404: Information theory and coding

The mathematical principles of communication that govern the compression and transmission of data and the design of efficient methods of doing so.

COM-302: Principles of digital communications

This course is on the foundations of digital communication. The focus is on the transmission problem (rather than being on source coding).

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 unreliabl

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

Block code

In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide rang