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