# Questions tagged [encoding-scheme]

The tag has no usage guidance.

89 questions
Filter by
Sorted by
Tagged with
72 views

### How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?

This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \{0,1\}^k$ and we want to guess what it is. A naive scheme ...
22 views

### Compactly representing integers when allowed a multiplicative error

Consider the problem of representing in memory numbers in the range $\{1,\ldots,n\}$. Obviously, exact representation of such number requires $\lceil\log_2(n)\rceil$ bits. In contrast, assume we are ...
76 views

### Homomorphic computation?

Cryptography has the concept of homomorphic encryption. Homomorphic encryption lets you transform binary values into an encoded form, put them through a circuit and then decode the bits, getting the ...
6k views

573 views

### Can I encode a graph in a unary alphabet

For a graph $G=(V,E)$, I build an adjacency matrix and encode it into binary, clearly. Now, imagine the alphabet I am given is $\Sigma=\{1\}$, is there a way for me to encode any graph instance with ...
18k views

### Is Morse Code binary, ternary or quinary?

I am reading the book: "Code: The Hidden Language of Computer Hardware and Software" and in Chapter 2 author says: Morse code is said to be a binary (literally meaning two by two) code because ...
532 views

### Using Huffman Encoding to improve Lempel-Ziv Encoding

Can anyone think of a way to use Huffman Encoding to improve the compression rate of Lempel-Ziv Encoding? My initial idea was to encode with higher probabilities given to shorter strings (i.e. the ...
48 views

### Is it possble to store a counter that could reach $\lfloor \frac{N}{x}\rfloor$ using $\lceil\log_2(N+1)\rceil$ - $\lfloor\log_2 x\rfloor$ bits?

Let $x,N$ be positive integers. I'd like to store a counter which could reach value of $\left\lfloor \frac{N}{x}\right\rfloor$ (i.e. could take any value in $0,1,\ldots,\frac{N}{x}$) using \lceil\...
79 views

### What is the theory foundation of the binary encoding of data digits into an EAN-13 barcode? [closed]

In the Wikipedia, there is explanation about EAN-13 and several table, which are called "Structure of EAN-13" and "Encoding of the digits", but I did not know what theory the contents of the two ...
110 views

### How can I construct a Turing Machine that accepts encoding of another Turing Machine? [closed]

How can I construct a Turing Machine that accepts the language L = <'M'> which is an encoding of a Turing Machine M?
851 views

### Turing machine working only with 1's and blanks - how to encode input?

Let's say we have a Turing machine which head can only write 1 or blank to the tape (although it can read all symbols from any input alphabet correctly). Can we operate with it on any input? My ...
382 views

### How do I interpret a binary tree generated using Huffman coding algorithm?

In the lecture note here, a binary tree was generated from the huffman algorithm. However it did not explain what this graph mean. From this binary tree, what can we say about the encoding for the ...
872 views

### Designing a prefix code for integers?

trying to figure out how to approach this problem. Suppose a sender in a network wanted to communicate the length n of the block it will be using in a subsequent transmission. If there were not ...
78 views

### Source Coding Theorem: what happen when go below N⋅H(x) bits?

I was following the text book by David Mackay: information theory inference and learning algorithms, this could be found online on his website. I have question on the source coding theorem (emphasis ...
142 views

This is the question: By definition of the IEEE754 standard, 32-bit floating point numbers are represented as follows: S (1 bit) E (8 bits) M (23 bits) S: Sign bit E: Exponent M: ...
58 views

### G1, G2, H1, H2 are submatrices of the generator and parity check matrices of a code as described below. Can G1 * H2' and G2 * H1' both be all zeroes?

$G$ and $H$ are the generator and parity check matrices respectively of a linear block code. Let $G_1 = G(:, 1:n-s)$ (Matlab style representation of sub matrices). That is, $G_1$ is equal to ...
137 views

### 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 ...
320 views

### Variable Length Encoding of Integers Using a Modulus Algorithm

Continuing on the theme from my last question Variable Length Encoding of Integers, I have come up with a simple encoding scheme, but for which an efficient algorithm eludes me. The constraints are ...
38 views

### Lexicographical position of a string in its type class

I have the following problem: Given a string $x\in\{1,...,M\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists ...
144 views

### How to store factorials? [closed]

Can someone help me to store the factorial of large numbers such as 100! efficiently? UPDATE: obviously, storing the argument rather than the factorial digits themselves achieves a significant saving....
794 views

### How does one choose an optimal alphabet for finding a Huffman encoding?

Huffman encoding will perform best when the distribution of symbols of an alphabet that the string to be encoded uses is dyadic. Given an arbitrary bit string S, ...
39 views

### Why do I not get the correct smallest possible value in 2's complement?

When using 2's complement with 4 bits, the largest positive int I can represent is 0111. The smallest negative one is 1000. The smallest int should intuitively be the negative of 0111 - 1 = 0110 ...
4k views

### A string representation of any Turing machine

The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble ...
295 views

### Precise definition of term: *schema*

Does the term schema, in the context of describing a structure, refer to the actual structure of the data, or the description of this structure? I.e. can I talk about the schema of an entity without a ...
228 views

### How do I find the shortest representation for a subset of a powerset?

I'm looking for an efficient algorithm for the following problem or a proof of NP-hardness. Let $\Sigma$ be a set and $A\subseteq\mathcal{P}(\Sigma)$ a set of subsets of $\Sigma$. Find a sequence \$w\...
434 views

### Encoding algorithms better than or equivalent to Run Length Encoding

I have a table in which some values are repeated often as shown in the figure below. I want to encode that table such that it makes use of less memory. I have heard about run length encoding (RLE) but ...
427 views

### Finding the difference between two number in a sorted list using divide-and-conquer

How to find the smallest difference between two numbers in a sorted list using divide-and-conquer approach? For example, ...
2k views

### Is there a difference between pure binary and binary?

In some books and on the internet I occasionally find "pure binary" and "binary" on its own, is there a difference between these two terms? If so, can someone describe briefly what they are?
6k views

### What are two's complement integers?

Can someone explain in plain English what "two's complement integer" means? I read this: in Java long is a 64-bit signed two's complement integer
994 views

### Reconstructing files from binary

Popular view tells us that any kind of information is just a collection of bits, that is zeroes and ones placed in a particular order. I was thus having this thought. Suppose that I have some kind of ...