People who code: we want your input. Take the Survey
3

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 \cdot \log(n) \cdot |\Sigma|)$ time. So you will have an $|\Sigma| \times n$ table, where you should find a column with a minimum sum, which can be done in $O(|\...


3

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 lexicographic order, generate random such string, et cetera. Indeed, if two strings differ in exactly one position, then their sums of digits are also different modulo $10$....


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 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 an exact formula for the minimal size of a covering code.


2

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 length-$n$ string $s$ such that $d(s,s_i)\ge k$ for all $i$. There is the problem of closest string. Given $m$ length-$n$ binary strings $s_1, s_2, \cdots, ...


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


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

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

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 max(1,1)=1 Overall, the algorithm is the following: for each possible code x, find the closest element c in C (i.e. the one with minimum distance d(x,c)) and record ...


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


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