On Optimal Finite-length Block Codes of Size Four for Binary Symmetric Channels
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- From Polar to Reed-Muller Codes: A Technique to Improve the Finite-Length PerformanceIEEE Transactions on Communications, 2014
- On Finite-Length Performance of Polar Codes: Stopping Sets, Error Floor, and Concatenated DesignIEEE Transactions on Communications, 2013
- An Improved Sphere-Packing Bound for Finite-Length Codes Over Symmetric Memoryless ChannelsIEEE Transactions on Information Theory, 2008
- Sphere-Packing Bounds Revisited for Moderate Block LengthsIEEE Transactions on Information Theory, 2004
- Finite-length analysis of low-density parity-check codes on the binary erasure channelIEEE Transactions on Information Theory, 2002
- A search procedure for finding optimum group codes for the binary symmetric channelIEEE Transactions on Information Theory, 1967
- Optimum(n,2)codes for small values of channel error probability (Corresp.)IEEE Transactions on Information Theory, 1967
- A search technique for quasi-perfect codesInformation and Control, 1966
- Group code equivalence and optimum codesIEEE Transactions on Information Theory, 1959
- A Class of Binary Signaling AlphabetsBell System Technical Journal, 1956