15 votes
Accepted

Calculate Huffman code length having probability?

The intended answer is probably that the length of the longest codeword is approximately $$-\log_2 10^{-6} = 20.$$ But this is wrong. The information given doesn't come close to specifying the length ...
user avatar
6 votes
Accepted

How many different Huffman encoding for a given number of symbols

The answer is $C_{n-1} n!$ . That is, the $(n-1)$st Catalan number times $n$ factorial. There are $C_{n-1}$ ways of making a complete binary tree with $n$ leaves, and there are $n!$ ways of assigning ...
user avatar
6 votes

Why can't codes be defined over infinite fields?

Sphere packings give a nice analogue of codes over $\mathbb{R}$. A sphere packing is a set $\mathcal{P} \subset \mathbb{R}^n$ such that $d_{\mathcal{P}} := \inf_{x,y \in \mathcal{P}, x \neq y} \|x - y\...
user avatar
5 votes

Why can't codes be defined over infinite fields?

It is possible to define codes over infinite fields, but it is usually not as useful as codes over finite fields. The original motivation for error-correcting codes comes from the needs to transmits ...
user avatar
  • 5,190
5 votes

Minimal encoding of a set (unordered collection of elements)?

What you're looking for is called a "succinct" or "implicit" dictionary. The best solution I know of is Backyard cuckoo hashing, by Arbitman et al from FOCS 2010, which "guarantees constant-time [...
user avatar
  • 11k
5 votes

How to state the adequacy of an encoding of lambda calculus in itself?

As pointed out by others, the obvious definition of an "adequate" coding is that it is equitranslatable with any standard one. The question is therefore to characterize such codings in terms of more ...
user avatar
4 votes

How to state the adequacy of an encoding of lambda calculus in itself?

This is not an answer. It is an elaboration of the question, that looks interesting to me and maybe should deserve more attention than it actually received. First of all, let me say that there is an ...
user avatar
4 votes
Accepted

Is the Mendler-encoding in System-F adequate?

$\newcommand{\Alg}{\mathsf{Alg}\ }$ $\newcommand{\NatF}{\mathsf{NatF}\ }$ $\newcommand{\Nat}{\mathsf{Nat}}$ $\newcommand{\map}{\mathrm{map}\ }$ $\newcommand{\Z}{\mathrm{Z}}$ $\newcommand{\S}{\mathrm{S}...
user avatar
  • 621
4 votes
Accepted

Is subtractive dithering the optimal algorithm for sending a real number using one bit?

Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$. We can at least prove that if $x$ is ...
user avatar
  • 376
4 votes

Number of bits required for encoding variables with fixed sum?

Answer to question 1: $\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode the variables. Proof: Count how many ways there are to choose $y_1,\ldots,y_r$ such that $y_i \ge 0$ ...
user avatar
  • 1,101
3 votes

Question about "typical set" in Shannon's source coding theorem

$S_δ$ is not a subset of the typical set. As you mentioned, the most probable element is a member of $S_δ$ but it is not necessarily a member of the typical set. The only reason to use the typical ...
user avatar
  • 477
3 votes
Accepted

Treewidth relations between Boolean formulas and Tseitin encodings

There is a relation between the treewidth of a circuit and the primal treewidth of its Tseitin transformation but you will have to take the fan-in of the circuit into account, which is large when ...
user avatar
  • 1,855
2 votes
Accepted

Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well Asymptotic for ...
user avatar
1 vote

How many different Huffman encoding for a given number of symbols

The answer by Peter Shor is correct. But for an optimal case when the symbols can only be placed at unique leaf nodes the number of possible Huffman codes drops to $C_{n-1}2^{n-1}$.
user avatar
  • 11
1 vote
Accepted

Entropy of a byte in a compression algorithm?

I define a random variable X which samples a bit uniformly at random from C∗. Should I expect Prob[X = 0] to be close to 1/2? Roughly, yes. The compression algorithm is lossless (bijective), so the ...
user avatar
  • 7,090
1 vote
Accepted

Can we say that Church encoding is a form of Gödelization?

It's possible to do a Gödel numbering that assigns every term in System F to a unique natural number? The answer is yes, pick your favorite way of coding terms in F, simply because they are ...
user avatar
  • 21.3k

Only top scored, non community-wiki answers of a minimum length are eligible