On Optimal Finite-Length Block Codes of Size Four for Binary Symmetric Channels

An <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,M)$ </tex-math></inline-formula> code refers to a binary code with blocklength n and codebook size M. Such codes are studied in the context of memoryless binary symmetric channels (BSCs) with maximum likelihood (ML) decoding. Previous research has characterized some optimal codes among the linear <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,4)$ </tex-math></inline-formula> codes for any <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \geq 2$ </tex-math></inline-formula>. However, it was unknown whether these optimal codes among linear codes were better than all nonlinear codes. In this paper, we first demonstrate that for any <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \geq 2$ </tex-math></inline-formula>, there exists an optimal code among all <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,4)$ </tex-math></inline-formula> codes that is either linear or belongs to a subset of nonlinear codes called Class-I codes. We identify all the optimal codes among the linear <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,4)$ </tex-math></inline-formula> codes for each blocklength <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \geq 2$ </tex-math></inline-formula> and discover some that were not previously reported in the literature. For any n from 2 to 8, all the optimal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,4)$ </tex-math></inline-formula> codes are identified. Except for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n=3$ </tex-math></inline-formula>, all the optimal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,4)$ </tex-math></inline-formula> codes are equivalent to linear codes. There exist optimal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(3,4)$ </tex-math></inline-formula> codes that are not equivalent to linear codes. Furthermore, we introduce a subset of nonlinear codes called Class-II codes and show that for any <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \gt 3$ </tex-math></inline-formula>, the set composed of linear, Class-I, and Class-II codes and their equivalent codes contains all the optimal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,4)$ </tex-math></inline-formula> codes. Both Class-I and Class-II codes are close to linear codes in the sense that they involve only one type of column that is not included in linear codes. We derive a sufficient condition such that all the optimal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,4)$ </tex-math></inline-formula> codes are equivalent to linear codes, which can be evaluated by computer with a computation cost <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n^{6})$ </tex-math></inline-formula>.