The 2024 Developer Survey results are live! See the results

# Tag Info

Accepted

### Does there exist a Reed-Solomon-like code over decimal symbols?

The property of Reed–Solomon codes that you mention is known as Maximum Distance Separability, and codes with this property are known as MDS codes. In coding theory the most popular type of code is a ...
• 278k

### Is Reed Solomon also a Fountain code?

It's difficult to call Reed-Solomon a fountain code. This is due to two reasons. The first reason is rather technical. Let's assume you use a systematic code. After sending the message itself (the ...
• 20.7k
Accepted

### Is an AND gate which is noisy 1/3 of the time on only one of its inputs universal?

Let $\land_p$ be a gate with error $p$ only when the inputs are $1$ and $0$. What can we say about $$(x \land_p y) \land_p (x \land_p y)?$$ If $x=y=1$ then we always get $1$. If $x = 0$ then we ...
• 278k
Accepted

### Am I right that Reed-Solomon codes can be used to implement arbitrary-parity RAID schemes?

A Reed-Solomon code applied to 512-byte (4096-bit) sectors can support up to $n=2^{4096}$ drives in an array, of which any fraction may be parity drives. The limits of real-world RAID setups come from ...
• 2,202
Accepted

### Sphere packing inequality for error-correcting codes

For a codeword $x$, let $B_k(x)$, the ball of radius $k$ around $x$, consist of all words at distance at most $k$ from $x$. Notice that $$|B_k(x)| = \sum_{i=0}^k \binom{m+r}{i}.$$ If the code ...
• 278k

### Understanding connection between length of codeword and hamming distance in Hamming code

The answer to both questions is the sphere-packing bound. Consider a binary code on $n$ bits with minimum distance $2d+1$ and $M$ codewords. Imagine surrounding each point of the code with a ball of ...
• 278k
Accepted

### What would be a natural generalization of a byte parity check?

For $i \in \{0,\ldots,M-1\}$, add a new byte which is the sum (or XOR) of every byte whose index equals $i$ mod $M$. For example, if $M=2$, one byte is the sum of all the bytes in the even positions, ...
• 278k

### Protecting data unequally using Error Correction Codes

Schulman's tree code may come in handy: This is a prefix code where future symbols of the codeword give some information about the prefix up to that point. Using that code, there is better probability ...
• 20.7k

### Protecting data unequally using Error Correction Codes

Since error correction here is essentially discrete, it might not be easy to come up with an optimal transient encoding, however you can approximate this by applying different encoding schemes for ...
• 190

### Does there exist a Reed-Solomon-like code over decimal symbols?

One implementation in Python is available here: Decimal Reed-Solomon implementation See also the article: Reed-Solomon using decimal numbers
• 21

### Error correcting permutation code

The first reference seems to be Rank permutation group codes based on Kendall's correlation statistic by Chadwick and Kurz; your notion of distance is known as Kendall's tau distance. A more modern ...
• 278k
Accepted

### Analysis of brute force decoder in a $q$-ary erasure channel

To upper bound the first probability, we can assume without loss of generality that the sent codeword is the zero codeword. After deleting $|J|$ rows, we are left with a random $(n-|J|)\times k$ ...
• 278k
Accepted

### what does the redundancy of a code means?

A linear error-correcting code encodes $m$ message bits using $w$ encoded bits. The redundancy is $r = w-m$. In other words, it is a collection of $M = 2^m$ codewords out of the possible $W = 2^w$ ...
• 278k

### How can I correct this Hamming code?

The original problem is, I believe, the following. When using Hamming code with EVEN parity for 7-bit ASCII characters, the following symbol is retrieved: 01100110101. Assuming a 1-bit error, what ...
• 39k

### Improving heading measurements from low cost compass module

While 'major' improvements is subjective, you can certainly improve your system more than it is (at least as you have described). Based on your problem description, it sounds as if your measurements ...
• 238

### How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form?

When computing CRC, we are working over the field of two elements. In this field, 2=0. Therefore $$(x+1)(x^3+x^2+1) = x^4+x^2+x+1.$$
• 278k

### Bit errors and hamming distance

If you need four bit changes to change from A to B, then you can make two bit changes from A to some A' followed by two more bit changes from A' to B. If you receive A' then you don't know whether it ...
• 31.1k
Accepted

### Linear codes : why has the parity check matrix dimensions $(n-k)*k$?

You can have as many rows in $H$ as you like, but they will be linearly dependent after you reach $n-k$ independent rows. You can apply the rank-nullity theorem. If you like, think of the rank of $H$...
• 281
Accepted

### when can i detect the position of error in hamming code

You can never detect the positions of errors with certainty. You can make the assumption that there is at most a single bit error. Under that assumption, if your code is not a valid code, you can ...
• 31.1k
Accepted

### Decoding problem and conditional probabilities

Maximizing $P(r|t)$ is known as the Maximum Likelihood (ML) principle, while maximizing $P(t|r)$ is known as the Maximum A Posteriori probability (MAP) principle. Here are some facts that answer ...
• 3,397

### $2d+1$ threshold for error detection

Let's look at a simple, concrete example where $d=4$. Suppose the codebook is $C = \{0000,1111\}$. This means the sender transmits either the codeword $0000$ or the codeword $1111$ during each block ...
• 1,378

### Why double error correction and quadruple error detection cannot occur at the same time?

With a hamming distance of five, you can make one of two assumptions: A. No word has more than four errors. Since you need five changes to get from one valid word to another valid word, and five ...
• 31.1k
Accepted

### When is Viterbi's algorithm practical?

There is no threshold of $k$. Viterbi's algorithm has a certain complexity. For small enough $k$, you will be able to run Viterbi's algorithm on the given hardware at the given speed. For larger ...
• 278k
Accepted

### Error correction code without error detection

You might be interested in the binary erasure channel, in which each symbol is erased with probability $p$. The capacity of this channel is $1-p$, and there are practical erasure codes that achieve it....
• 278k
Accepted

### Existence of good error correcting codes

This is known as the Plotkin bound.
• 278k
Accepted

### Number of signatures of each type in a fixed column set of the Hadamard matrix

The $2^n \times 2^n$ Walsh-Hadamard matrix is given explicitly by $$M(u,v) = (-1)^{\langle u,v \rangle},$$ where $u,v \in \{0,1\}^n$, and the inner product is given by  \langle u,v \rangle = \sum_{...
• 278k

### Why does a CRC detect burst errors of longer than r+1 bits independently of burst length?

There is a dependence on the length. For an n-bit CRC and a k-bit burst error, the probability of a false positive is (2max(k – n, 0) – 1) / (2k – 1). One minus that is the probability of a k-bit ...
• 178

### How are non-binary codes implemented in practice, i.e. codes over $\mathbb{F}_q^n$ for $q\neq 2$?

For $\mathbb{F}_2^n$ people store the bits consisting of the coefficients of the polynomial of some generator $x$. For $\mathbb{F}_q$ the field is isomorphic to simple integers mod $q$, so they simply ...
• 13.8k
1 vote
Accepted

### Basic classical linear error correcting code for bits exercice (from Nielsen & Chuang)

Suppose that $e_1, \ldots, e_k$ are (linearly independent) rows of the generator matrix of $C$. We can find vectors $e_{k+1}, \ldots, e_{n}$ s.t. $\{e_i\}_{i=1}^n$ is a basis in $\mathbb{F}_2^n$ (not ...
• 183
1 vote

### Hamming code distance and error detection

Let's see. With parity, each block is 1001 bits long vs 1010 bit for Hamming code. So if the error rate is 0, then you economize 9 bits. OTOH, if each second block fails, the in 50% of cases you will ...
• 1,988

Only top scored, non community-wiki answers of a minimum length are eligible