论文标题
可变长度平衡方案的平均冗余
Average Redundancy of Variable-Length Balancing Schemes à la Knuth
论文作者
论文摘要
我们研究并提出了使用可变长度前缀将消息映射到恒定重量代码字上的方案。我们提供多项式时间计算公式，以估计我们的方案产生的冗余位数的平均数量。除了确切的公式外，我们还进行了渐近分析，并证明我们的方案使用$ \ frac12 \ log n+o（1）$冗余位，将消息编码为长度 - $ n $单词，带量$ $（n/2）+{\ sf q} $，用于常量$ {\ sf q} $。我们还提出了将消息映射到具有错误纠正功能的平衡代码簿中的方案。对于此类方案，我们提供了列举平均冗余位数的方法。
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 $\frac12 \log n+O(1)$ redundant bits to encode messages into length-$n$ words with weight $(n/2)+{\sf q}$ for constant ${\sf q}$. 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.
