Tag Info

6

If a single-bit error correction is attempted, the ordering presented in the example guarantees that the syndrome vector (the result of the multiplication of the checking matrix and the received data), if interpreted as an integer, will indicate the position of the error. Otherwise, a lookup table would have to be used.

4

Grid graphs are finite node-induced graphs of the infinite planar grid (whose vertices are integral points, and two vertices are linked when their Euclidean distance is 1). A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter proved that the Hamiltonian path problem on grid graphs is NP-complete. To reduce that to your problem, suppose the grid graph has $m$ ...

3

You say in the comments that we might have $c \approx 15$ or so. There should be very efficient algorithms in this case, using locality sensitive hashing. For example, here is a simple LSH. Randomly choose a set of about 10,000 indices (out of the 1,000,000). Hash each vector by computing some standard hash of the 10,000 bits in those positions (ignoring ...

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

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

Guidelines for the future: start with reviewing the definitions. According to Wolfram, a perfect code (with distance $d=2e+1$) is one such that "for every possible word $w_0$ of length $n$ with letters in $A$, there is a unique code word $w$ in $C$ in which at most $e$ letters of $w$ differ from the corresponding letters of $w_0$." OK, but this is cheating....

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

You are correct. Here's what's going on. There are two subtly different questions here. The Stack Overflow question is asking: "given a set of bitvectors that form a Hamming code, how do I find the minimum distance?". In contrast, it sounds like you might be asking "given an arbitrary set of bitvectors, how do I find the minimum distance?". Those aren't ...

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

Yes, such a Gray code sequence can be constructed for all $n$, even when $n$ is not a power of two. I'll describe how, below. I will say that $a_0,\dots,a_{n-1}$ is a Gray code sequence for $0,1,\dots,n-1$ if each $a_i$ is in the range $0..n-1$, and if each $a_i$ differs from $a_{i-1}$ in a single bit position. Note that this generalizes the usual notion ...

2

Consider the case where $k=1$. In other words, we're allowing a single error. We take our base automaton and apply this "error-allowing transformation" to it. The transformed automaton generally works as follows: The state $(q, 0)$ means "the underlying automaton is in state $q$, and we haven't made an error yet". The state $(q, 1)$ means "the underlying ...

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

2

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 find all different data where the hamming code differs from your code in only one bit position; if there is exactly one such data then you know where the error is ...

2

The Hamming distance between two length-$n$ vectors is the number of coordinates in which they differ. I've only ever seen it on finite alphabets, i.e. vectors in $\Sigma^n$ where $|\Sigma|\in \mathbb{N}$. In theory there is no problem with extending this to $\mathbb{R}$, but you may have to be careful with how you use equality of floats for instance. ...

2

Hamming codes are designed to correct a single error. A valid codeword $p_1 p_2 m_3 p_4 m_5 m_6 m_7$ satisfies the constraints \begin{align} &p_1 \oplus m_3 \oplus m_5 \oplus m_7 = 0 \\ &p_2 \oplus m_3 \oplus m_6 \oplus m_7 = 0 \\ &p_4 \oplus m_5 \oplus m_6 \oplus m_7 = 0 \end{align} (This is arranged simply by choosing $p_1 = m_3 \oplus m_5 \... 1 If you are using the Hamming(7,4) code as described in here, then there is already a bit error in$1001101$. Indeed, we have parity bits$p_1 = 1$,$p_2 = 0$and$p_3 = 1$and message bits$d_1 = 0$,$d_2 = 1$,$d_3 = 0$and$d_4 = 1$. Since (for example)$p_2 + d_1 + d_3 + d_4 = 1 \mod 2$, that means that there is a bit error (and it's among$p_2$,$d_1$,$...

1

Consider a binary code $C$ of length $n$ (each codeword consists of $n$ bits), containing $2^m$ codewords, and allowing all single-bit errors to be corrected. Let $x \in C$, and let $B_x$ denote all words at distance at most $1$ from $x$, that is $x$ itself, as well as any word obtained by flipping a single coordinate. Any word in $B_x$ could result from a ...

1

There are many equivalent Hamming codes depending on the ordering of parity and data bits. Assuming that: You are using the specific bit ordering described here: https://en.wikipedia.org/wiki/Hamming_code#General_algorithm By "even parity" you mean that the parity bits are computed as the sum (modulo 2) of the corresponding groups of bits By "odd parity" ...

1

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 have to transmit a second block, in 25% of cases third block and so on. On average you have to send 2 blocks. Now, let's go deeper. If the error rate is r, ...

1

Question 1: Suppose $k$ is fixed. Then, if any group of repeated $k$ bits is flipped, the error is not detected, so we need $k \ge m + 1$. On the other hand, if $k = m + 1$, then any combination of $m$ errors will be detected because at least $k$ bits must be flipped (i.e, the whole group of $k$ repetitions) in order to arrive at a valid code word. Question ...

1

The comment by @gnasher is right. Moreover, if the code was $k$ error correcting with $m$ data bits, each of the $2^m$ legal messages would require $$1+n+\binom{n}{2}+\cdot+\binom{n}{k}=\sum_{j=0}^k \binom{n}{j}$$ bit patterns dedicated to it, where $\binom{n}{j}$ is the number of words at Hamming distance $j$ from a given word.

1

A 010101 D 000111 There are two bits different (namely the bold ones). So the hamming distance is 2.

1

In a linear code, the minimum distance is the same as the minimum weight of a non-zero codeword. It's a nice exercise to prove this, and reduces the computation time quadratically. Computing the minimum distance of a code given the generator matrix (or the parity check matrix) is NP-hard, that is, given a generator matrix (or a parity check matrix) and an ...

1

A (binary) code $C$ is a collection of binary strings of some length $n$, known as codewords. The minimal distance of $C$ is the minimum Hamming distance between (different) codewords. Hamming codes have minimum distance 3, which means that (1) every two codewords differ in at least 3 places, (2) there exist two codewords which differ in exactly 3 places. ...

1

You just need to concentrate on the polynomial division here. First consider the case where we need to detect one - bit error . For this case $e(x) = x^k$ we can choose any polynomial with terms >=2 , since it will not divide the error polynomial completely . Next let us see the case of odd number of errors. Notice how this is different from one bit ...

1

You should do arithmetic modulo 2. Modulo 2, $-1$ is the same as $+1$.

1

They clearly say that the example is only given as an example. If you believe you need 5 parity bits - use 5 bits. They use 4 bits in their example for no good reason. True, they still wish you to mark it clearly. I guess the reason is (a) to make sure you know that the parity comes in powers of 2, and (b) to ease their grading. note you should not use ...

1

Your terminology is a bit off. Hamming distance is a metric on words given by the number of different symbols. The minimal distance of a code is the minimal (Hamming) distance between two different codewords, and enjoys the properties you listed.

1

The topic you want is Unequal Error Protection (UEP) codes. There are a number of constructions in this area and a google scholar search yields quite a few hits. Intuitively, imagine partitioning your code into disjoint point clouds, where cloud centres are chosen by the more important bits, thus intra-centre distance is high, hence those bits are more ...

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