# Tag Info

12

The general case is indeed a bit complicated. However, in the case of 4 disks you can simplify it a lot; you do not really need to know any fancy math. You only need to know how to store 4 bits redundantly, and then you already know everything; just repeat the same scheme for each group of 4 bits that you need to store. We can represent the scheme as 4 x 4 ...

11

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 ...

10

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 ...

7

The computation for $Q$ is definitely more difficult than the XOR computation needed for $P$ though it is in one sense the same kind of calculation: a polynomial evaluation. Stripped of the detailed computational techniques described in the link, the idea is to regard the $n$ data bytes/drives $D_0$, $D_1, \ldots, D_{n-1}$ as the coefficients of a ...

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

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 ...

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 ...

4

I'm sure this greatly varies according to the application and the specific code in use. Though not for DRAMs, maybe this will give you some insights: For CDs encoding, a (28,24)-Reed Solomon code is used. For DVDs, it is a (208,194)-Reed Solomon code. Symbols are over $GF(2^8)$, that is, 8 bits per symbol. The notation is $(n,k)$-ReedSolomon for a ...

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

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

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

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$ ...

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

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 \... 2 The three disk raid-6 is trivial: Just store the same information on disk 1, disk 2 and disk 3. Any two disks may fail and you can still recover the data. So a three disk raid-6 is basically just a three disk raid-1. In the four disk case, there are two data "disks" (let's call them A and B) and two parity "disks" (let's call them P and Q). ... 2 Specifically for Memories, try google ECC memories. It seems that the main trend is to correct a single bitflip per memory address. For that purpose a distanse of d=3 is enough and a Hamming code can be used. Here is an AMD memory, where each 64 bits are encoded via Hamming code (d=3, fixing a single bit flip). TI's TMSx70 controller, uses a modified ... 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 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

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 ...

2

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 ...

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

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

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

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 ...

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