Skip to main content
4 votes
Accepted

Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other

There is a simple solution: use exactly the strings with sums of digits being divisible by $10$. There are $10^9$ such strings and it is easy to enumerate them, find $i$-th of them in the ...
Kaban-5's user avatar
  • 519
3 votes
Accepted

What is the intuition behind working of hamming codes

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 \...
Yuval Filmus's user avatar
3 votes
Accepted

Algorithm for cyclic $n$-string Hamming distance with constant sized language $\Sigma$

Let $\alpha \in \Sigma$ and $d_{\alpha, H}(A,B) = n - \sum1\{A(i)=B(i)=\alpha\}$. Then you can use your FFT technique to compute $d_{\alpha, H}(A, B)$ for each $\alpha \in \Sigma$. It will take $O(n \...
Vladislav Bezhentsev's user avatar
3 votes

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 ...
Yuval Filmus's user avatar
3 votes
Accepted

Minimum number of strings to cover entire space within Hamming distance

The object you are interested in is called a covering code. While less popular than error-correcting codes, covering codes share many of the same difficulties. In particular, there is little hope for ...
Yuval Filmus's user avatar
2 votes
Accepted

Find binary number with max hamming distance wrt given set of binary numbers

Here is the decision version of the problem, which we can the problem of farthest string. Given $m$ length-$n$ binary strings $s_1, s_2, \cdots, s_m$ and a number $k$, determine whether there is a ...
John L.'s user avatar
  • 39.1k
2 votes

How does this answer for automata and Hamming distance not lead to inconsistencies?

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 ...
Draconis's user avatar
  • 7,138
2 votes
Accepted

What is the difference between Hamming Distance and Manhattan Distance for non-binary data?

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{...
integrator's user avatar
  • 1,110
2 votes

Show that the Hamming distance of $wx$ and $xw$ cannot be 1

$w$ and $x$ are binary strings. Clearly $|wx|=|xw|$ and $|wx|_0=|xw|_0$. Suppose $wx$ and $xw$ differ only at position $i$, so that $(wx)[i]\ne(xw)[i]$, $(wx)[1..i-1]=(xw)[1..i-1]$, and $(wx)[i+1..n+k]...
rici's user avatar
  • 12.1k
2 votes

Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$

Your problem is very likely NP-hard. If you don't add the restriction that $W$ is sub-space, but just receive a set of boolean vectors $W$, then it is NP-hard and known as a Covering Radius proven NP-...
Bernardo Subercaseaux's user avatar
1 vote
Accepted

How Can the Bounded Search Tree Algorithm for Closest String run in $\mathcal{O}(kd)$ per node?

Please see Theorem 1 from the original paper. The distance of $z$ to $x_i$'s can be updated in $O(k)$ time. Note that $z$ might not necessarily be chosen from the given set of strings $x_1 , \dotsc, ...
Inuyasha Yagami's user avatar
1 vote

Number of binary words that form a group of Hamming weight at most d

Your structure is known as a group anticode with maximal distance $d$. The obvious construction is to take all vectors of the form $(x_1,\ldots,x_d,0,\ldots,0)$, obtaining a group of size $2^d$. ...
Yuval Filmus's user avatar
1 vote

Hierarchial clustering cannonnical representation?

You can always adjust your algorithm to use a deterministic tie-breaking rule, e.g., sort the data points before applying the clustering algorithm, and always break ties in favor of the earliest/...
D.W.'s user avatar
  • 161k
1 vote

How to recognise the number of errors that can be detected and corrected of a large set of codewords (k) each having a specified number of bits (n)?

There are $2^{10}$ binary strings of length $10$. We can partition them into pairs $x_1\ldots x_90,x_1\ldots x_91$. Since your code contains more than $2^9$ codewords, it will contain at least one ...
Yuval Filmus's user avatar
1 vote
Accepted

Calculate number of error-correcting code check bits

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 ...
Yuval Filmus's user avatar
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 ...
Bulat's user avatar
  • 1,898
1 vote
Accepted

Covering radius of a code in the Hamming space

It's easier to remove from your table all lines with codes already in C. In your case only two lines will remain, minimum distance in both lines are 1, so the maximum distance of these two is ...
Bulat's user avatar
  • 1,898
1 vote

Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes

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 >...
Shubham Singh rawat's user avatar

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