15
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 of the longest codeword. Even the entire probability distribution doesn't specify the length of the longest codeword.
One can see this by constructing a ...
11
The answer is no.
I'll give an example of a language $L$ which is regular in binary but not in unary:
Consider $L=\{10^k|k\in \mathbb{N}\}$. The corresponding language in unary is $L'=\{1^{2^k}|k\in \mathbb{N}\}$.
It's easy to see that $L$ is regular while $L'$ is not even context free.
L'' also isn't regular either, by the link @Sylvain posted in his ...
8
From a mathematical perspective: Try
1) Handbook of coding theory - Huffman and Pless
2) Fundamentals of Error-Correcting Codes - Huffman and Pless
3) Introduction to coding theory - Ron Roth
4) Algebraic Geometric Codes: Basic Notions - Vladut, Nogin and Tsfasman
5) Introduction to Coding Theory - Van Lint
6) Algebraic ...
7
When the base k representation is regular, the set is called k-automatic
The wikipedia article on these reads:
For given "k" and "r", a set is "k"-automatic if and only if it is "k^r"-automatic. Otherwise, for "h"and "k" multiplicatively independent, then a set is both "h"-automatic and "k"-automatic if and only if it is 1-automatic, that is, ultimately ...
7
The language of valid Bencoded values is not context-free—and nor is just the language of Bencoded strings. Let $L$ be the set of valid Bencoded values, and let $L'$ be the intersection of $L$ with the regular language [0-9]*:a*, i.e. the Bencoded strings with just the symbol a. If $L$ were context-free, so would $L'$, but $L'$ does not ...
7
Just omit the last digit.
(Extra text to get over the 30-chaacter minimum.)
6
This is called run-length-limited coding, there has been lots of research done on it by the information theory community, and I will just refer you to the existing literature. After a brief glance at the wikipedia article I linked to, my impression is that you shouldn't rely on the references it contains, but do your own search of the literature.
One ...
6
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 these leaves to the symbols to get a Huffman code.
This sequence goes 2, 12, 120, 1680, 30240, and is listed in the Online Encyclopedia of Integer Sequences ...
6
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\| > 0$, where $\|\cdot \|$ is the Euclidean norm. This is called a sphere packing because we can place a(n open) sphere of radius $d_{\mathcal{P}}/2$ at ...
5
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 [insert, delete, lookup] operations in the worst case with high probability" while using $B + o(B)$ bits, where $B$ is the lower bound you mention.
If you need ...
5
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 bits over a noisy channel. Over such a channel, it is usually not possible to send real numbers with arbitrary precision.
However, there have been some works ...
5
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 elementary properties.
(Historical note. Smullyan studied this question in the context of combinatory logic. When I was a student, Henk Barendregt suggested ...
4
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 important condition in Barendregt's definition that has been omitted by Brennan, namely the fact that $\lceil M \rceil$ must be in normal form, that immediately ...
4
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$ and $\sum y_i = M-r$. There are exactly $\binom{M-1}{r-1}$ such ways (see e.g. here). Now, if there are only $k$ possible values for a variable, then $\lceil \log ...
4
Why shouldn't you be able to send the empty string? Shouldn't it be considered a valid message?
But if you don't allow the empty string as a message, then your modified protocol will work fine, and will save you on average a small fraction of a bit per message.
Is this tweak worth putting into your implementation so as to improve the performance? Let's ...
4
Lecture notes of the course "An Algorithmic Introduction to Coding Theory," by Madhu Sudan.
Publication Date: 2001. The first chapter offers useful comments regarding several textbooks on coding theory.
Available at http://people.csail.mit.edu/madhu/FT01/scribe/overall.pdf.
4
What about writing each number as a sum of powers of 10 (or whatever is the base for your problem) in ascending order and then delta-encode the exponents with some universal code? You might need to nudge the deltas since most codes start with '1', but if you use e.g. Levenstein coding to encode 122:
122 = 10^0 + 10^0 + 10^1 + 10^1 + 10^2
The exponent tuple ...
3
The Huffman algorithm considers the two least frequent elements recursively as the sibling leaves of maximum depth in code tree. The Fibonacci sequence (as frequencies list) is defined to satisfy F(n) + F(n+1) = F(n+2). As a consequence, the resulting tree will be the most unbalanced one, being a full binary tree.
2
excellent 50p survey by leading expert/member Luca Trevisan from 2004 also tracking recent/latest research in the field
Some Applications of Coding Theory in Computational
Complexity
sections:
Introduction
Error-Correcting codes
Sublinear Time Unique Decoding
Sublinear Time List Decoding
Locally Testable Codes
2
My favorites for the first part of your question:
Neal Koblitz: "A Course in Number Theory and Cryptography"
$\rightarrow$ Very good introduction for mathematical treatment
Oded Goldreich: "The Foundations of Cryptography"
$\rightarrow$ More applications, but also a good book for basical interests
Thomas M. Cover and Joy A. Thomas: "Elements of ...
2
Simple idea, but fits problem statement. I propose following encoding:
Pair of integers: $(S, N)$
Where
$S$ - desired sum
$N$ - place of number in sorted sequence of all possible positive integers with desired sum of digits.
For your example sequence of integers with sum=5 :
(5,1) = 5
(5,2) = 14
(5,3) = 23
(5,4) = 32
(5,5) = 41
(5,6) = 50
(5,7) = 105
(5,...
2
For the problem as you've posed it, it seems that you could simply replace every occurrence of an illegal sequence by a new symbol so that: aababbbaba -> xbayaba.
I guess that's probably too simple, but we'll need more information to provide a better solution (like the cost of adding symbols).
2
$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 set instead of $S_δ$ is to make the proof of the source coding theorem easier. (See the paragraph at the top of page 84 in your book.) The typical set along with ...
1
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 entropy of the input is the same as the entropy of the output. Under your hypothetical, the output's length is asymptotically larger than its entropy, so ...
1
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 countable number of expressions.
Just being able to assign numbers to expressions in a system is not useful by itself, the question is can it be done in a manner that ...
1
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}$.
1
$X = \{\{0,5\}, \{1,4\}, \{1,1,3\}, \{1,1,1,2\}, \{1,1,1,1,1\}, \{2,3\}, \{2,2,1\} \}$
$X$ is partition of 5 where only single digit numbers are allowed.
Observation:
Any number with digit sum 5 can be represented by permutation of one of the above sets stuffed with 0s.
Example:
$\begin{eqnarray*}
14 \rightarrow 10^040^0 \rightarrow 14:0,0\\
104 \...
1
Let's say you are dealing with numbers in base $b$ with up to $n$ digits whose digit values sum to $M$. To encode a number $N$ of length $l = \lfloor \log_b N \rfloor + 1 \leq n$, just create a bit vector of length $\log n + (M - 1)\log l$.
The first $\log n$ bits of the vector tell you how many digits $N$ has. The second $l$ bits tell you the position $p$...
Only top voted, non community-wiki answers of a minimum length are eligible
