Bounds for changing codes without full decoding help nonlinear coding
Entropy/Length Profile Bounds for the Conversion of (Non)linear Codes in the Merge Regime
Information Theory
Summary
Sometimes when you have encoded (compressed or protected) data, you want to change how it's encoded without fully decoding and re-encoding it. Existing methods mostly work only for special 'linear' codes. This paper by the authors creates a new way to understand and limit how much of the code you need to read or keep the same when changing between arbitrary codes, including nonlinear ones. They also show examples where their limits are as tight as possible, even for nonlinear codes.
What this means in practice
- •For data storage engineers: Determine minimum data reads needed to convert stored codes without full decoding, improving storage system efficiency for nonlinear codes.
- •For communications protocol developers: Design code conversion steps that tightly control symbol changes and reads during data transmission upgrades involving nonlinear codes.
A theory result. No direct application yet.
Authors
Songping Ge, Han Cai, Xiaohu Tang
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.