Average Redundancy of Variable-Length Balancing Schemes \`{a} la Knuth

arXiv2204.13831MaRDI QIDQ6397757FDOQ6397757

Authors: Duc Tu Dao, Han Mao Kiah, Tuan Thanh Nguyen 

Publication date: 28 April 2022

Abstract: We study and propose schemes that map messages onto constant-weight codewords using variable-length prefixes. We provide polynomial-time computable formulas that estimate the average number of redundant bits incurred by our schemes. In addition to the exact formulas, we also perform an asymptotic analysis and demonstrate that our scheme uses $frac12logn+O(1)$ redundant bits to encode messages into length-$n$ words with weight $(n/2)+sfq$ for constant $sfq$. We also propose schemes that map messages into balanced codebooks with error-correcting capabilities. For such schemes, we provide methods to enumerate the average number of redundant bits.

This page was built for publication: Average Redundancy of Variable-Length Balancing Schemes \`{a} la Knuth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6397757)