Coding over very noise channel Suppose that I want to send a message (consisting of bits) over a channel where from $n$ transferred bits as many as $n/2-\varepsilon n$ might be flipped, i.e., the distance of the code is $n-2\varepsilon n$. How does the number of encodable messages $m$ change as a function of $n$ and $\varepsilon$? I do not want to assume that $\varepsilon$ is a constant, so it can be for example $1/\log n$.
 A: For a binary code, as $n$ grows you cannot do better than the repetition code $$C=\{11\cdots1,00\cdots0\},$$ with two codewords as soon as the minimum distance required $d>n/2.$ See Theorem 4 of Venkat Guruswami's notes, for example, available [here][1]. The result for your case is
that if a binary code $C$ must satisfy $d>n/2$ then
$$
|C | = m \leq \frac{2d}{2d-n}.
$$
Letting $d=n(1-\frac{2}{\log n})$ gives
$$
m \leq \frac{2n(1-\frac{2}{\log n})}{2n(1-\frac{2}{\log n})-n}=
\frac{2n(1-\frac{2}{\log n})}{n(1-\frac{4}{\log n})}.
$$
For $d=n/2$ and below there is much more freedom: You have, for example, the first order Reed Muller Code which is formed by taking $n=2^k,$ and the rows of a $2^k\times 2^k$ Sylvester Hadamard Matrix as well as their translates obtained by adding the all 1 vector to obtain $m=2^{k+1}=2n.$
Edit: If $d=n/2-\varepsilon,$ then using the Gilbert-Varshamov lower bound the asymptotic relative rate $R(C)=m/n$ of the code obeys
$$
R(C)\geq 1-h_2(\delta)-o(1),
$$
where $\delta=d/n$ is the relative distance. Here $\delta=1/2-\varepsilon$ yields
$$
R(C) \geq 1-h_2(1/2-\varepsilon)-o(1)
$$
which can be estimated from below as
$$
R(C) \geq 
1-\sqrt{1-4\varepsilon^2}\geq 1-(1-2 \varepsilon^2)=2 \varepsilon^2,
$$
by using $h_2(q)\geq 2\sqrt{q(1-q)},$ for the binary entropy function.
[1]: https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes4.pdf
