Entropy/Length Profile Bounds for the Conversion of (Non)linear Codes in the Merge Regime

Abstract

Code conversion changes the parameters of encoded data while avoiding complete decoding and re-encoding. Existing general bounds largely rely on the algebraic structure of linear codes. This paper develops an information-theoretic framework for nonlinear code conversion in the merge regime. Using the entropy/length profile (ELP), we derive upper bounds on the number of unchanged symbols and lower bounds on the number of read symbols for arbitrary $(n,M)_q$ codes, without assuming linearity or requiring $\log_q M$ to be an integer. We also obtain joint bounds for multiple initial codes and consequences involving minimum distance. For linear codes, the proposed bounds reduce to the corresponding generalized Hamming weight (GHW) bounds. The construction based on Hamming codes converts Hamming codes of redundancy two into a Hamming code of any larger redundancy and simultaneously attains the general bounds on unchanged and read symbols. The construction based on quasigroups shows that new bounds remain tight for genuinely nonlinear codes of nonintegral dimension and at a nonintegral entropy threshold, which, to the best of our knowledge, is the first construction of convertible codes for nonlinear codes.