# Tag Info

4

Let $\land_p$ be a gate with error $p$ only when the inputs are $1$ and $0$. What can we say about $$(x \land_p y) \land_p (x \land_p y)?$$ If $x=y=1$ then we always get $1$. If $x = 0$ then we always get $0$. When $x = 1$ and $y = 0$, we get the wrong answer $1$ with probability $$p \cdot p + p \cdot (1-p) \cdot p = p^2(2-p).$$ Call that function $f(p)$....

2

This is known as the Plotkin bound.

1

You mentioned in a comment that your messages are very short, only 7-10 bits long. Another option is to explicitly construct a code, with encoding and decoding done via a lookup table rather than by an algorithm or a formula. For instance, suppose you have $K=7$-bit messages, that you will encode to a $N=30$-bit codeword that will be written onto the tape, ...

1

I don't know if this problem has been studied, and I bet there will be better solutions, but I'll suggest a scheme that I suspect might work well enough, even if it's not optimal. Naive approach: brute-force decoding I would bet that any erasure code would work, if combined with brute-force decoding. For decoding, I am imagining that a naive algorithm is to ...

1

Here is what the remark says: A code $C \subseteq A^n$ is $t$-error-correcting if for all $x \in C$ and $y \in A^n$ such that $d(x,y) \leq t$, all $z \in C$ other than $x$ satisfy $d(x,y) < d(z,y)$. When is a code not $t$-error-correcting according to this remark? A code $C \subseteq A^n$ is not $t$-error-correcting if there exist $x,z \in C$ and $y \... 1 So, according to Theorem 4.3 of this monograph by Réné Struik, if we consider$q$-ary binary codes of length$n$, such that$n \to \infty$with$r/n \to p \in [0,(q-1)/q]$, then the minimal code size has the following asymptotic limit $$(1/n)\log_q N_{n,q}(r) \to 1-H_q(p),$$ where$H_q(p)$is the$q$-ary entropy of$p$. This answers my specific problem ... 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

What you are asking for: You want transformations T and T’, such that X = T(S) is undistinguishable from random, T’(X) = S, and if X’ = X with few random bit errors, then T’(X’) = S as well. But strings with errors can be distinguished: If A has no errors, then adding some random bit changes leaves T’(A) unchanged. If A already contains errors, then fewer ...

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