Average Redundancy of Variable-Length Balancing Schemes a la Knuth

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 perform an asymptotic analysis and show that our scheme uses 1/2 log n + O(1) redundant bits to encode into length-n words with weight (n/2) + q for constant q.