Questions tagged [hamming-distance]
The hamming-distance tag has no usage guidance.
29
questions
4
votes
2
answers
79
views
Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$
Let $W$ be a linear subspace of the vector space $V = (\mathbb{Z}/2\mathbb{Z})^n$. Let $k = \dim(W)$. For $v \in V$, define the distance from $v$ to $W$ to be $d(v,W):=\min_{w\in W} d(v,w)$ where $d(...
- 141
1
vote
0
answers
30
views
Name for class of error-correction codes
I'm considering a binary error-correction scheme, but I'm missing the correct terms to dig further into it.
The idea is to decide the code-rate during encoding, but for the decoder to decide how that'...
- 111
2
votes
1
answer
50
views
How Can the Bounded Search Tree Algorithm for Closest String run in $\mathcal{O}(kd)$ per node?
I am trying to understand an algorithm for solving Closest String using bounded search trees, as found in Parameterized Algorithms (Cygan et al., 2015).
Assume we have a set of $k$ strings $x_1, ..., ...
0
votes
0
answers
30
views
Encoding and Decoding
I am trying to find an encoding function e:{0,1}^20→{0,1}^10 and a decoding function d:{0,1}^10→{0,1}^20. Goal is to find d and e so that maxBdH(d(e(B)),B) is as small as possible. Here, dH denotes ...
0
votes
0
answers
57
views
What algorithm will determine if two strings match eachother or not?
$\require{enclose}$
Definition of parent
For any three strings $x$, $y$, and $p$, we say that $p$ is a parent of $x$ and $y$ if and only if all of the following:
$p$ is a $\enclose{updiagonalstrike, ...
1
vote
2
answers
63
views
Show that the Hamming distance of $wx$ and $xw$ cannot be 1
Let $w$ and $x$ be two binary strings. Show that the Hamming distance of $wx$ and $xw$ cannot be 1.
I think one approach is a proof by contradiction. I was thinking of explicitly writing out $w = w_1\...
- 289
1
vote
1
answer
25
views
Number of binary words that form a group of Hamming weight at most d
Consider binary words in {0,1}^n whose Hamming weight is at most some constant d. We want to select some of these words such that they form a group under addition. How many words can we choose at most?...
- 21
0
votes
0
answers
30
views
What is the best learning to hashing for embedding points in a Vector Space in Hamming Space?
I have a cloud of points in $\mathbb{R}^n$ and I want to embed them in Hamming Space.
One possible solution is for example found in Inductive Hashing on Manifolds.
The problem is:
I need an extremely ...
- 137
1
vote
1
answer
135
views
What is the intuition behind working of hamming codes
I am trying to understand hamming codes for single bit error correction. I understood all the things like hamming distance , k bit error detection and all basics for hamming codes. Also, I know the ...
- 195
0
votes
1
answer
47
views
Hierarchial clustering cannonnical representation?
I have to handle large binary dataset. That is one of the reasons I have to build my own Hierarchical Clustering. As I digged into the algorithms I was surprised and not ;) to find that it is possible ...
- 139
3
votes
2
answers
236
views
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)?
I am struggling to find how can I know the number of errors that can be corrected and detected using (n=10) bit code with a (k=550) codewords.
As far as I know, to calculate the number of errors to be ...
0
votes
0
answers
110
views
Travelling Salesman Problem: Distance between solutions
I'm designing a genetic algorithm to solve the travelling salesman problem. So far, I've gotten fairly good results. I'm now trying to improve on them by implementing some sort of diversification ...
- 101
3
votes
1
answer
83
views
Algorithm for cyclic $n$-string Hamming distance with constant sized language $\Sigma$
Suppose we are given a language $\Sigma$ where, suppose, $|\Sigma| = O(1)$. Consider two fixed strings $A, B \in \Sigma^n$. Define the Hamming metric between these strings as
$$d_{H}(A,B) = \sum_{i=1}^...
- 453
2
votes
1
answer
132
views
What is the difference between Hamming Distance and Manhattan Distance for non-binary data?
What is the difference between Hamming Distance and Manhattan Distance for non-binary data (specifically I am comparing points in $\mathbb{R}^2$)? I understand Manhattan sums the absolute difference ...
- 123
2
votes
1
answer
271
views
Calculate number of error-correcting code check bits
To design a code with $m$ data bits and $r$ check bits which allow all single-bit errors to be corrected, the formula
$$(n + 1) 2^m \leq 2^n$$
with $n = m + r$ and $(m + r + 1) \leq 2^r$ is used.
Why ...
- 41
2
votes
1
answer
140
views
Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other
I'm working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two ...
- 95
1
vote
0
answers
228
views
Channel coding and Error probability. Where are these probabilities from?
From where are the following probabilities?
We consider BSCε with ε = 0,1 and block code C = {c1, c2} with the code words c1 = 010 and c2 = 101. On the received word y we use the decoder D = {D1,D2} ...
- 51
1
vote
3
answers
681
views
Why ASCII letter A has a Hamming Distance of 3?
My question is what does [this construction gives a Hamming Distance a distance of 3] means? Why the Hamming Distance of ASCII letter A is 3? How do you determine the Hamming Distance is 3?
This is ...
2
votes
1
answer
522
views
Understanding connection between length of codeword and hamming distance in Hamming code
I came across following in Huffman coding:
Minimum Hamming distance to correct up to s errors is $2s + 1$ because that way the legal codewords are so far apart that even with $s$ changes the ...
- 1,637
1
vote
3
answers
275
views
Effects of parity bit on odd code length regarding its size after alternation
I am trying to understand code distance, but I am not sure regarding the following scenario:
Assume that you have an information word M with m bits, that You code into a coding word using the ...
- 11
1
vote
0
answers
26
views
finding amount of errors that can be fixed based on code length [closed]
i tried to look online and search this site and others but haven't found any good explanation to the following simple question: how many errors can a code with length k(k>2)fix?
- 11
0
votes
0
answers
42
views
minimal distance of a self correcting code
i wonder: how can i find minimal distance of a self correcting code in following situation: if we know that a code can fix every 3 errors(if not more than 3 errors, the word is recovered) and can ...
- 55
0
votes
1
answer
568
views
Hamming code distance and error detection
Suppose that data are transmitted in blocks of sizes 1000 bits. What is the maximum
error rate under which error detection and retransmission mechanism (1 parity bit per
block) is better than using ...
- 65
0
votes
1
answer
185
views
Covering radius of a code in the Hamming space
A deterministic $(2−2/(k+1))^n$ algorithm for $k$-SAT based on local search
I have read this paper and I couldn't understand how to culculate the $covering$ $radius$ of a code in the Hamming space. ...
- 59
6
votes
1
answer
931
views
Find binary number with max hamming distance wrt given set of binary numbers
Suppose we have a set $A$ of binary numbers with the same length $n$.
For example (with $n=8$):
$A = \{ 10010011, 01011011, 00010010, 11110001\}$
Now, I want to find the binary number $z$ (also with ...
- 73
0
votes
0
answers
58
views
finding the overhead and distance of an unknown code based on message making algorithm
for an information word M with m bits that is coded as following:
M is coded into a word A using an unknown code that allows detection of not more than one error.
the code word is the word obtained ...
- 101
2
votes
1
answer
566
views
How does this answer for automata and Hamming distance not lead to inconsistencies?
I had already been given the answer by the TA in class, but I don't understand it. I'm not asking for the answer on a homework problem or anything.
The problem:
The Hamming distance ("distance") of ...
- 21
2
votes
1
answer
201
views
Minimum number of strings to cover entire space within Hamming distance
Given $(n, k)$:
What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string?
Is there an asymptotic expansion or lower ...
- 1,393
2
votes
1
answer
5k
views
Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes
I was reading about CRC coding from two books:
Data Communication and Networking by Forouzan Page 294
Computer Network by Tanenbaum Page 188
They use following notations:
$d(x)$: dataword to be ...
- 1,745