A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [encoding]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
779 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 ...
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 ...
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. ...
592 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 ...
178 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-...
969 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: ...
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 ...
462 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 ...
235 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 ...
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 ...
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.
405 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 ...
195 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 ...
162 views

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 ...
37 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-...
13 views

### Is it possible to find the huffman code for each symbol given only the encoded string

If i have a encoded string such as this : 01111001100011010111100 And lets say i know the number of symbols, is it possible to find the code for each symbol ?,...