Questions tagged [encoding]
The encoding tag has no usage guidance.
32
questions
4
votes
1
answer
131
views
Treewidth relations between Boolean formulas and Tseitin encodings
Suppose you have a propositional formula $\varphi$ in CNF. You want to efficiently obtain an equisatisfiable CNF formula encoding $\neg \varphi$. You use the usual Tseitin encoding with auxiliary ...
- 419
8
votes
0
answers
146
views
What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)
Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\mathbb R^+$, and an integer parameter $k\in\mathbb N$.
The Entropy-Constrained Quantization problem asks what is the best ...
- 9,378
5
votes
1
answer
146
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 ...
- 691
10
votes
1
answer
414
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,...
- 9,378
2
votes
1
answer
133
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 ...
- 133
2
votes
2
answers
284
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}$?
- 21
-1
votes
1
answer
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
1
answer
305
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 ...
- 389
1
vote
0
answers
63
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 ...
- 9,378
2
votes
0
answers
152
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 ...
- 2,331
-3
votes
1
answer
467
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 ...
- 2,501
1
vote
0
answers
41
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 ...
- 111
8
votes
2
answers
211
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-...
- 181
8
votes
0
answers
125
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 ...
- 181
2
votes
2
answers
3k
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 ...
- 143
2
votes
1
answer
370
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 ...
- 123
1
vote
1
answer
3k
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 ...
- 171
3
votes
1
answer
266
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\...
- 9,378
4
votes
2
answers
304
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 ...
- 9,378
4
votes
3
answers
425
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 ...
- 61
4
votes
4
answers
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 ...
- 165
2
votes
0
answers
106
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 ...
- 21
1
vote
2
answers
774
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 ...
- 73
4
votes
2
answers
428
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 ...
- 43
7
votes
6
answers
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:
...
- 171
5
votes
1
answer
520
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 ...
- 51
13
votes
5
answers
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 ...
- 171
22
votes
3
answers
797
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 ...
- 35.7k
4
votes
2
answers
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.
- 51
9
votes
5
answers
642
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 ...
- 4,600
2
votes
2
answers
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
2
answers
358
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. ...
- 971