# Tagged Questions

The tag has no usage guidance.

111 views

### Lower bound on prefix code lengths

For a prefix code $C:\{0,1\}^*\to\{0,1\}^*$, define $f(n)$ as the length of the longest encoding of a number with up to $n$ bits: $$f(n)=\max_{|k|\le n}\left|C(k)\right|.$$ (Note that by taking ...
154 views

### Does Huffman coding always produce shorter codes than the Shannon code?

Let $X\in\{1,2,\ldots,m\}$ be a discrete random variable with $X\sim p$. Let $C$ be a code for $X$ with $l_i$ being the length $i$-th codeword and let $L(C)$ be the expected length of the code. The ...
72 views

### What is the optimal binary encoding of the elements of a monoid?

The Question Let $M$ be a finite monoid. Let $S$ be a generating set of $M$. Say we have a binary encoding of $S$ represented by $\phi:S \rightarrow A^*$ where $A = \{0, 1\}$. This encoding should ...
332 views

281 views

### How do I construct an optimal affix code?

An affix code is a code that is simultaneously a prefix and suffix code. That is, no codeword is neither the prefix nor the suffix of any other codeword. Affix codes can be instantaneously decoded in ...