1
$\begingroup$

I am a physicist learning a bit of information theory.

I have encountered a term ("symbol codes") on Wikipedia, and cannot find what it means:

Source coding theorem for symbol codes

Let $\Sigma_1,\Sigma_2$ denote two finite alphabets and let $\Sigma_1^*$ and $\Sigma_2^*$ denote the set of all finite words over those alphabets (respectively).

Suppose that $X$ is a random variable taking values in $\Sigma_1$, and let $f$ be a uniquely decodable code from $\Sigma_1^*$ to $\Sigma_2^*$, where $|\Sigma_2| = a$. Let $S$ denote the random variable given by the length of the codeword $f(X)$.

If $f$ is optimal in the sense that it has the minimal expected word length for $X$, then (Shannon 1948): $$ \frac{H(X)}{\log_2 a} \leq \mathbb{E}[S] < \frac{H(X)}{\log_2 a} + 1, $$ where $\mathbb{E}$ denotes the expected value operator.

Please let me know what does symbol code mean.

$\endgroup$
  • 1
    $\begingroup$ It would be far easier to provide text and screenshot is not searchable, so please get rid of it. $\endgroup$ – Evil Sep 21 '19 at 13:49
2
$\begingroup$

"Symbol Codes" means codes that work over a (finite) alphabet with an arbitrary size. Many times people focus only on binary codes, and Shannon Thm says that the minimal code length of some random variable $X$ is between $H(X)$ and $H(X)+1$ bits.

But what if, instead of bits, you use trits, or symbols from a larger alphabet of size, say, $a$? Then, the length of $X$'s coding needs to be adjusted since every symbol of the codeword now "contains" $\log_2 a$ bits. Then, the wikipedia page says, the minimal code length will be between $H(x)/\log_2(a)$ and $H(x)/\log_2(a)+1$ symbols.

Multiply the equation by $\log_2 a$ to convert into information bits: the codeword will have $S$ symbols, hence $S\log_2 a$ bits, and this amount, by Shannon's coding theorem, can be minimized so that it is almost $H(X)$ (maybe up to one additional symbol, i.e., additional $\log_2 a$ bits).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I hadn't heard that term before, but from context, I believe it is talking about codes over a finite alphabet (i.e., discrete random variables as opposed to continuous random variables).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.