On the construction of prefix-free and fix-free codes with specified codeword compositions |
| |
| Authors: | Ali Kakhbod Morteza Zadimoghaddam |
| |
| Institution: | a Department of Electrical Engineering and Computer Science (EECS), University of Michigan, Ann Arbor, MI, USAb Computer Science and Artificial Intelligence Laboratory (CSIL), MIT, Cambridge, MA, USA |
| |
| Abstract: | We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimize the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost. |
| |
| Keywords: | Algorithm Approximation algorithm Prefix-free code Fix-free code |
| 本文献已被 ScienceDirect 等数据库收录！ |
