Questions tagged [encoding]
The encoding tag has no usage guidance.
30
questions
5
votes
1answer
104 views
Is the Mendler-encoding in System-F adequate?
In the paper "Efficiency of Lambda-Encodings in Total Type Theory" it is mentioned that the Church-encoding is adequate and the Parigot encoding is not adequate. This means that any ...
10
votes
1answer
344 views
Is subtractive dithering the optimal algorithm for sending a real number using one bit?
Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner.
We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,...
2
votes
1answer
101 views
Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?
I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using ...
2
votes
2answers
244 views
Why can't codes be defined over infinite fields?
In Coding Theory, people use $q$-ary alphabets: why do we need a finite set? Why can't we define codes over infinite sets. such as $\mathbb{R}$ or $\mathbb{C}$?
-1
votes
1answer
100 views
Does a code need at least two symbols to be defined as a code? [closed]
I am wondering whether you could still call a code something that, if transmitting, only transmits one symbol. Or does the formal definition of code require 2 or more symbols? (and would the answer ...
2
votes
1answer
270 views
Entropy of a byte in a compression algorithm?
I have a (fixed, long) string of bytes that I want to compress, $C$. I use a typical (good) lossless compression algorithm on it, to generate a compressed string of bytes, $C^*$. Then I define a ...
1
vote
0answers
62 views
What is known about data structures for encoding a set while considering approximate Rank queries?
Consider a universe $\mathcal U\triangleq \{1,2,\ldots n\}$, and assume that we are given a set $S\subseteq \mathcal U$.
There are many data structures that allow storing $S$ while answering Rank ...
2
votes
0answers
139 views
Unit hypercube encodings
How can we chose to place $k$ points in $[0,1]^d$, such that the minimum Euclidian distance between any two points is maximized?
Is there a more common term for these combinatorial designs than unit ...
-3
votes
1answer
433 views
Can we say that Church encoding is a form of Gödelization?
We see here the following statement about Godelization:
Gödel numbering in computer science means more or less "source code" and "data in binary format", so I hope the ...
1
vote
0answers
40 views
Reference request on dynamic flows combined with network coding
I have read some papers about network coding and dynamic flows (flows over time).
I think I have made comprehensive searches on google, google scholar and IEEE Xplore.
IMHO, the reasons for the ...
8
votes
2answers
198 views
How to state the adequacy of an encoding of lambda calculus in itself?
In the paper Discriminating coded lambda terms - Henk Barendregt a coding $\ulcorner M \urcorner$ of a lambda term $M$ is a term such that $M$ (and its parts) can be reconstructed from it in a lambda-...
7
votes
0answers
108 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 ...
2
votes
2answers
2k views
How many different Huffman encoding for a given number of symbols
In Huffman coding, if we have two symbols to be encoded, we will get the result either 01 or 10. If we have three symbols, we ...
2
votes
1answer
322 views
Question about “typical set” in Shannon's source coding theorem
I was following the textbook by David Mackay: Information theory inference and learning algorithms.
I have question on asymptotic equiparition' principle:
For an ensemble of $N$ $i.i.d$ random ...
1
vote
1answer
2k views
Calculate Huffman code length having probability?
Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits will ...
3
votes
1answer
208 views
Number of bits required for encoding variables with fixed sum?
Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$
It's easy to store the variables using $r\...
4
votes
2answers
262 views
Minimal encoding of a set (unordered collection of elements)?
Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$.
If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are ...
4
votes
3answers
318 views
Regular languages under change of encoding
Consider a regular language $L$ with alphabet $\Sigma = \{0,1\}$.
Can we say that the set of strings in $L$ (representing non-negative integers in binary encoding) when represented in some other ...
4
votes
4answers
2k views
Research in Coding Theory
I have just started learning about coding theory. Hence, I would like to ask for your suggestions and guidance for a very beginner like me.
Which books are good for beginning coding theory? (I start ...
2
votes
0answers
105 views
Bayesian compression
Suppose you have a sequence generated by an i.i.d. process (such as repeatedly rolling a die and recording the values in order) parameterized by some K-dimensional vector $\vec{\gamma}$ (the ...
1
vote
2answers
733 views
Arithmetic coding, the termination symbol, and the empty string
Suppose the source alphabet is $a, b, c$ with $a$ as the termination symbol and so the unit interval is correspondingly divided as
$[0, P(a), P(a)+P(b), 1]$.
Strings consisting of a bunch of $b$'s ...
4
votes
2answers
421 views
Combinations with symbols
Suppose we have the following symbols: $\{a,b\}$. Now there are some rules. More than 3 $b$'s are now allowed and $aa$ is not allowed. So $ababab$ is allowed, but for example $abbbbaba$ not (more than ...
7
votes
6answers
1k views
Efficient encoding of integers with constant digit sum
How can a large set of integers all with a known constant digit sum be encoded?
Example of integers in base 10, with digit sum 5:
...
5
votes
1answer
498 views
Can Bencodes Be Described With a Context-Free Grammar?
Bencoding is the encoding scheme used by Bittorrent applications. You’re probably most familiar with bencoding via the .torrent file format used by Bittorrent ...
13
votes
5answers
5k views
Why does Huffman coding eliminate entropy that Lempel-Ziv doesn't?
The popular DEFLATE algorithm uses Huffman coding on top of Lempel-Ziv.
In general, if we have a random source of data (= 1 bit entropy/bit), no encoding, including Huffman, is likely to compress it ...
22
votes
3answers
787 views
Adding integers represented by their factorization is as hard as factoring? Reference request
I'm looking for a reference for the following result:
Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation.
(I'm pretty sure ...
4
votes
2answers
3k views
Why does the Fibonacci sequence produce a worst-case Huffman encoding?
I noticed this in my Algorithms class, but just now got around to asking.
9
votes
5answers
624 views
Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters
Let $\Sigma$ be an alphabet, ie a nonempty finite set. A string is any finite sequence of elements (characters) from $\Sigma$. As an example, $ \{0, 1\}$ is the binary alphabet and $0110$ is a string ...
2
votes
2answers
3k views
Graph encoding algorithms that you know of ?
Is there any compilation of graph encoding algorithms? I know about Prufer and Huffman encoding. But papers say, prufer is not good enough to represent Minimum Spanning Trees in the sense it may ...
9
votes
2answers
355 views
Quick encoding of balanced vectors
It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. ...
