  A binary code of blocklength $n$ and codebook size $M$ is called an $(n,M)$
code, which is studied for memoryless binary symmetric channels (BSCs) with the
maximum likelihood (ML) decoding. For any $n \geq 2$, some optimal codes among
the linear $(n,4)$ codes have been explicitly characterized in the previous
study, but whether the optimal codes among the linear codes are better than all
the nonlinear codes or not is unknown. In this paper, we first show that for
any $n\geq 2$, there exists an optimal code (among all the $(n,4)$ codes) that
is either linear or in a subset of nonlinear codes, called Class-I codes. We
identified all the optimal codes among the linear $(n,4)$ codes for each
blocklength $n\geq 2$, and found ones that were not given in literature. For
any $n$ from $2$ to $300$, all the optimal $(n,4)$ codes are identified, where
except for $n=3$, all the optimal $(n,4)$ codes are equivalent to linear codes.
There exist optimal $(3,4)$ codes that are not equivalent to linear codes.
Furthermore, we derive a subset of nonlinear codes called Class-II codes and
justify that for any $n >300$, the set composed of linear, Class-I and Class-II
codes and their equivalent codes contains all the optimal $(n,4)$ codes. Both
Class-I and Class-II codes are close to linear codes in the sense that they
involve only one type of columns that are not included in linear codes. Our
results are obtained using a new technique to compare the ML decoding
performance of two codes, featured by a partition of the entire range of the
channel output.
