Questions tagged [encoding]
The encoding tag has no usage guidance.
28
questions
0
votes
0answers
32 views
Lowerbound to sample complexity or run-time of doing sparse-coding
I noticed this interesting analogous discussion that happened here,
Lower bound proof for compressive sensing (Gel'fand widths)?
What is the closest analogue know for such a result for sparse-...
2
votes
2answers
191 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
99 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
236 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
59 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
133 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
296 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 significance of this should ...
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
176 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
98 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
1k 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 ...
1
vote
1answer
257 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 ...
0
votes
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
161 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
187 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
227 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
1k 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
104 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
656 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
395 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
950 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
448 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
4k 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
759 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
2k 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
590 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
2k 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 ...
10
votes
2answers
331 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. ...
