Characterization of All Optimal Finite-length Codes of Size Four for Binary Symmetric Channels

The search for optimal finite-length binary block codes is a long-standing open problem for memoryless binary symmetric channels (BSCs) with the maximum likelihood decoding. A recent work studied the optimal codes among all binary codes of size four, including both linear codes and nonlinear codes, and showed the existence of optimal codes in the set composed of linear codes and Class-I codes for any given blocklength. Furthermore, for blocklength up to 300, it has been shown that there exists a linear code that is optimal among all the codes of size four. However, it is unknown whether there are optimal codes outside the set of linear codes and Class-I codes for a general blocklength. In this paper, we derive a subset of nonlinear codes called Class-II codes and justify that the set composed of linear, Class-I and Class-II codes and their equivalent codes includes all the optimal codes of size four when the blocklength is not equal to 3. For blocklength 3, we verify that there are nonlinear codes (not equivalent to linear, Class-I or Class-II codes) that are optimal. For the blocklength from 2 to 300 and not equal 3, our computer evaluations show that no nonlinear code is optimal except for the ones that are equivalent to linear codes. Moreover, we characterize all the best codes among all linear codes of size four for any given blocklength.