Questions tagged [hamming-distance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
14 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 ...
2
votes
1answer
43 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}^...
2
votes
1answer
26 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 ...
2
votes
1answer
34 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 ...
3
votes
1answer
107 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 ...
0
votes
0answers
16 views

Are My Answers to This Hamming Code Example Correct?

I have attempted to answer this question on Hamming code but i am very new to it and would appreciate feedback on my answers, Thank you! Question My Answers
1
vote
0answers
198 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} ...
1
vote
3answers
72 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 ...
1
vote
1answer
65 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
vote
2answers
47 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 ...
1
vote
0answers
20 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?
0
votes
0answers
12 views

distance of a code name in scheme

i wonder: is it true that if we take a information word, call it M(with m bits) for example, and code it by first coding M using a code, that we don't know anything about, except of it a length of k, ...
0
votes
0answers
24 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 ...
0
votes
1answer
174 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 ...
0
votes
1answer
42 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. ...
5
votes
1answer
296 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 ...
0
votes
0answers
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 ...
2
votes
1answer
249 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 ...
2
votes
1answer
93 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 ...
2
votes
1answer
4k 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 ...