# Tag Info

## Hot answers tagged error-correcting-codes

11

The Hamming distance being 3 means that any two code words must differ in at least three bits. Suppose that 10111 and 10000 are codewords and you receive 10110. If you assume that only one bit has been corrupted, you conclude that the word you received must have been a corruption of 10111: hence, you can correct a one-bit error. However, if you assume that ...

10

The first step towards clarifying your confusion is forgetting about the formulas. You should be able to understand this material without looking at the formulas. You should even be able to develop the formulas on your own. Now to the actual question at hand. Suppose we have a bunch of codewords, and every two are different in at least 10 positions. Suppose ...

6

The CRC polynomial is very probably primitive, that is the order of $X$ modulo $G$ is $2^{32}-1$. In other words, $X$ is a generator of $GF(2^{32})^\times$. So using inputs $0,2^0,\ldots,2^{2^{32}-2}$ will result in all possible $2^{32}$ values. CRCs are hopefully always chosen with primitive polynomials, so this result is general. Even if the polynomial is ...

6

Yuval Filmus is absolutely right. You should not remeber the formula, but reinvent it when needed. It is really so simple. Let me try explaining a different way. The Hamming distance between two binary strings of the same length is the number of bit positions where the string differ. But the important point to remember is that it is a distance, pretty much ...

5

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 linear code, and these are only defined over alphabets which are prime powers. However, in the literature you can find some papers on MDS codes on arbitrary ...

5

One approach: Use a meet-in-the-middle algorithm. Build a precomputed table that stores $T_i = x^i \bmod P(x)$ for all $i$ up to the maximum message length. Now, given $S$, you are looking for $i,j$ such that $S = T_i + T_j$. This can be found by enumerating all $i$, and for each $i$, computing $S-T_i$ and checking whether it is present in the precomputed ...

5

A binary code is a set of vectors in $\mathbb{F}_2^n$ for some $n$. Presumably the context in which you encountered this construction is a motivation for it. It's a particular case of a more general construction known as a Cayley graph, though perhaps this particular case has a specific name. You are right that all arithmetic is done in $\mathbb{F}_2$. There ...

4

The same procedure actually works to correct any number of errors up to $e$. The requirement is that the error polynomial $E(x)$ has to be zero at every point $a_i$ where there was an error. Nothing says it has to be zero at only those points; you can have an $E(x)$ that is zero at other points too, and that's OK, as long as its degree is $e$. So, if $e$ ...

4

Right, the code $VT_0(4)$ has Levenshtein distance (edit distance) of 4: to get from one codeword to another you must do 2 deletions and 2 insertions. Therefore, the code can correct one deletion. Indeed, if 101 was received, the only possible way to get this message assuming one deletion, is if 1001 was sent. Decoding can be done in several ways: The ...

4

A memoryless channel is one where the probability of an error at a particular bit is independent of what happened at all prior bit positions. A channel can have memory if errors are correlated across bit positions. For instance, consider the following simple binary channel: if there was no error in the prior position, then there is a probability of 0.1 ...

4

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 systematic part), the "fountain" is the remaining redundancy symbols = evaluation of the polynomial in other points. In order to be decoded correctly, you must ...

3

CRC is conceived as the remainder of a polynomial division. It is efficient for detecting errors, when the calculated remainder does not match. Depending on the CRC size, it can detect bursts of errors (10 bits zeroed, for example), which is great for checking communications. The "FCS" term is used sometimes for some transformed version of the CRC (Ethernet ...

3

Both CRC and the Hamming code are binary linear codes. One significant difference is that the Hamming code only works on data of some fixed size (depending on the Hamming code used), whereas CRC is a convolutional code which works for data of any size. So, are CRC and the Hamming code fundamentally different ideas? This is a philosophical rather than a ...

3

The Hamming codes are optimal in the sense that among all codes with the same block length and minimal distance, they contain the most number of codewords. We know this because Hamming codes are perfect codes: their number of codewords matches the Hamming bound, which is an upper bound on the number of codewords in a code with given block length and minimal ...

3

This is not possible. There's no free lunch. You are looking for a compression scheme that is guaranteed to compress 32 bits down to less than 32 bits. That's not possible in general, unless you have prior knowledge that lets you rule out some of the possible 32-bit values. In particular, if you want to send 32 bits of information, and all $2^{32}$ ...

3

Let us call a data vector of some fixed length together with its CRC a codeword. Since CRC is a linear code, the set of codewords is closed under XOR (this is the definition of linear code). Let $x$ be a codeword, and suppose that $y$ is a noisy version of $x$ which is also a codeword. Since CRC is linear, $x \oplus y$ is also a codeword. If $D$ is the ...

3

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 supports correcting up to $k$ errors, then the sets $\{ B_k(x) : x \in C \}$ must be disjoint. The code contains $2^m$ many different codewords, hence we get $$2^m \... 3 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 radius d, consisting of all points at distance at most d from the point. These balls must be disjoint: if the balls corresponding to x,y contain some ... 3 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, and the other one is the sum of all the bytes in the odd positions. Since bursts have length at most M, each of these checksums will only be missing a single ... 2 When we say that a Hamming code detects (up to) 2 errors and can correct 1, we mean just that: There is an error-detection algorithm that returns NO if there are no errors and returns YES if there are one or two errors. There is absolutely no guarantee when there are more errors. There is an error-correction algorithm that gets a possibly corrupted word and ... 2 The author of the list that you mention has written a thorough report on the problem of selecting a CRC polynomial, which probably contains the answers to all your questions. See page C-19: Important to select CRC polynomial based on: Data Word length Desired HD Desired CRC size Safety-critical applications commonly select HD=6 at max message length For ... 2 Define the sets$$\begin{align*} P(d) &:= \{ p ~|~ \deg(p) \leq d \}\\ A_i(d) &:= \{ p \in P(d) ~|~ s(p) = i \} \end{align*}$$where s(p) is the number of 1 coefficients of the polynomial p. For a given CRC generator polynomial g, define$$ U_i(d) := \{ p \in A_i(d) ~|~ \exists q, p = q g \} $$So U_i(d) is the set of all undetected ... 2 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 to deocde correctly the prefix of the message than it's suffix. 2 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 different parts of your data. In your temperature digits example, you might consider an encoding with d=5 Hamming distance for integer part and d=3 for ... 2 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 reference is Codes in Permutations and Error Correction for Rank Modulation by Alexander Barg and Arya Mazumdar 2 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 matrix A, and we want to bound the probability that its (right) kernel is non-trivial, that is, that there is a non-zero vector x such that Ax=0. For any non-... 2 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 is a double bit error coming from A, or a double bit error coming from B. Therefore, you cannot fix double bit errors. Since four bit errors are needed to go ... 2 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. 

2

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 may be non linear (you will have to confirm this). If this is the case, then a linear filter, such as the Kalman Filter, won't work well at all. From here, you ...

2

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 was the original stored symbol? Write down your answer as a 7-bit binary, with no spaces. OP's statement, "..., which contains an ASCII value: 01100110101&...

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