# Tag Info

50

You don't need a separator because Huffman codes are prefix-free codes (also, unhelpfully, known as "prefix codes"). This means that no codeword is a prefix of any other codeword. For example, the codeword for "e" in your example is 10, and you can see that no other codewords begin with the digits 10. This means that you can decode greedily by reading the ...

28

This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long... Morse Code isn't "officially" binary, ternary, quaternary, quinary, or even 57-ary (if I count correctly). Arguing about which one it is without context is not productive. It is up to you to define which of those five ...

26

Your code has the property that if you reverse all codewords, then you get a prefix code. This implies that your code is uniquely decodable. Indeed, consider any code $C = x_1,\ldots,x_n$ whose reverse $C^R := x_1^R,\ldots,x_n^R$ is uniquely decodable. I claim that $C$ is also uniquely decodable. This is because $$w = x_{i_1} \ldots x_{i_m} \text{ if and ... 19 Morse code is a prefix ternary code (for encoding 58 characters) on top of a prefix binary code encoding the three symbols. This was a much shorter answer when accepted. However, considering the considerable misunderstandings between users, and following a request from the OP, I wrote this much longer answer. The first "nutshell" section gives you the gist ... 13 It's helpful to imagine it as a tree. You are simply traversing the tree until you hit a leaf node, and then restarting from the root. From the algorithm which does huffman coding, you can see that this sort of structure is created in the process. https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png 12 I wrote a paper on this. The short answer is that there is no optimal encoding, nor even an optimal sequence of better and better encodings. Kraft's inequality states that there is a prefix code with word lengths k_0,k_1,\ldots if and only if$$ \sum_{n=0}^\infty 2^{-k_i} \leq 1. $$This gives a positive answer to your question. Concretely, Elias gamma ... 11 The largest 12 digit number in base 10 is 10^{12} - 1. In general the largest n position number in a base b is b^{n} - 1. So in your case you need a base large enough that b^{9} - 1 > 999,999,999,999 (10^{12} - 1). Solving for b:$$b^{9} - 1 > 10^{12} - 1b^{9} > 10^{12}b^{9/9} > 10^{12/9}b > 10^{12/9}b >...

9

Yes, there is such a set. You are actually on the right track to find the following example. Let $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$. You can check the following. $|C|=32$. $d(u,v)\geq2$ for all $u,v\in C$, $u\not=v$. (In fact, $d(u,v)=2$ or 4 or 6.) Here are four related exercise, listed in the order of increasing ...

7

All words of even parity from a linear code with $2^{n-1}$ codewords and minimum distance $2$. More generally, if $A_2(n,d)$ is the maximum size of a code of length $n$ and minimum distance $d$, then $A_2(n,2d) = A_2(n-1,2d-1)$.

6

First notice that a "file" is a sequence of 0s and 1s in binary format that are stored in some kind of persistent storage (an hard disk, a CD, an USB key, ...). According to the the type of information stored in the file (a plain text, a PDF document, an image, a video, a song, ...) its bits (bytes) are usually arranged using standard rules and they have ...

6

Consider a Turing machine with $n$ tape symbols and $m$ states. We can assume that the symbols and the states are ordered, so that we can talk about the first, second, ..., $n$th tape symbol, and the first, second, ..., $m$th state. (This is similar to your idea of counting Turing machines up to isomorphism.) So without loss of generality, the tape alphabet ...

5

Two's complement is the most commonly used way to represent signed integers in bits. First, consider unsigned numbers in 8 bits. Notice that $2^8 = 256 = 100000000_2$ does not fit into 8 bits and will thus be represented as 0000 0000. Therefore $255 + 1 =$ 1111 1111 + 0000 0001 = 0000 0000 and in that sense 1111 1111 acts as if it was $-1$. Two's complement ...

5

Files are always stored in the disk in binary format. Therefore if you know the binary version of the file, you simply know the file itself. A more interesting question is whether you can reconstruct the semantics of the file from its binary contents. Suppose you memorized the binary contents of a file, but forgot what type the file was. Could you ...

5

Despite my initial thoughts on this, it turns out this question can be formalized in a way that admits a fairly precise answer (modulo a couple of definition issues). The answer turns out to be 3 or 4, i.e. ternary or quaternary. The crowd-pleaser "everything goes from 2 to 57" answer is correct only in the sense that if someone asks you for a ...

5

As you mention in your question, everything that can be coded in binary (that is, every countable set) can also be encoded in unary. Arrange all binary strings in some order, say $$\epsilon, 0, 1, 00, 01, 10, 11, \ldots.$$ Let $w_i$ be the $i$th string in this order. You can convert from binary to unary by mapping $w_i$ to $1^i$ and vice versa. You ...

5

A Turing machine $M$ can be described as a 7-tuple $(Q,F,q_0,\Sigma,\Gamma,\delta, blank)$. This means that if someone gives you this 7-tuple, then the TM is well-defined, and you can precisely define how it behaves, etc. The encoding of a TM, usually denoted as $\langle M \rangle$ is a string that encompasses all the information of the 7-tuple describing $... 5 Where the 21 bits come from: The idea of unicode is based on the Universal Coded Character Sets (short UCS). It's a concept for a 31bit character set ordered as a 4D hypercube where the first three dimensions use 8bit and the fourth uses 7bit. Per row there are$2^8$characters. Per plane there are$2^8$rows$=65.536$characters. Per cube there are$2^8$... 5 Effective model theory studies computable structures. The collection of all finite trees is a two-sorted computable structure in which one sort consists of vertices (which can be identified with the natural numbers) and the other sort consists of trees. It has the following relations:$\operatorname{vertex}(x)$, which is true if$x$is a vertex.$\...

5

If I give you any message that you are supposed to decode, then you can do the following: Reverse the message, starting with the last bit instead of the first bit. Reverse the code words. Decode the message. Reverse the decoded string. You can do that because after reversing the six code words, you get a prefix-free code: 1010, 1001, 01, 000, 11, 001 is ...

4

Garey and Johnson are referring to the fact that any encoding scheme for some instance $I$ of a problem $\Pi$ will only differ in length (i.e. number of bits) by a polynomial amount. For example, consider two possible ways to encode a graph: adjacency matrix, and adjacency list. It is not possible to obtain a super-polynomial speedup by using one encoding ...

4

I believe I found a reduction from Hamiltonian path, thus proving the problem NP-hard. Call the word $w\in\Sigma^*$ a witness for $A$, if it satisfies the condition from the question (for each $L\in A$, there's $m\geq 1$ such that $\{w_{m+i}\mid 0\leq i<|L|\} = L$). Consider the decision version of the original problem, i.e. decide whether for some $A$ ...

4

I'm having trouble answering your question for two reasons. First, the entropy changes as you change the alphabet, so the "best" alphabet depends on the correlations between characters in the class of strings that you are trying to encode, not just the "dyadicness". (This is the problem with the notion of entropy: it depends on your model of what you know ...

4

The following code is often used as a standard prefix-code for natural numbers, which bounds the length of each codeword by $\log n+O(\log\log n)$: At first, we identify the natural numbers by binary strings: $$(0,\epsilon),(1,0),(2,1),(3,00),(4,01),...$$ Lets call $l(x)$ the length of the binary representation of the natural number $x$. Note that for each ...

4

A code is prefix-free if there does not exist any distinct two values v, w such that encode(v) is a prefix of encode(w). So, to prove that your encoding is prefix-free, you start by considering two arbitrary distinct values v, w and demonstrate that encode(v) is not a prefix of encode(w). I suggest you use proof by induction on the "size" of the largest ...

4

Let's take a different view angle. The problem is not really about encoding something like "decimals numbers" 0..127 into base-15 (which is messy). It's about converting a base-127 string into base-15. If you can see it that way, then it's just the same principle as with converting from, say, base-16 (hex) to base-10 (decimal), or base-10 to base-2.

4

\n and \t would get the job done as best as I could tell. In memory they're each only a character, but visually they offer a lot more. You then have an encoding scheme of \n then $x$ \t characters where $x$ is the nesting level. So this: [a b [c d [e] f]] in memory becomes: a\nb\n\tc\n\td\n\t\te\n\tf visually becomes: a b c d e f As ...

4

An $m\times m$ adjacency matrix requires $m^2$ bits, and $m=\sqrt{n}$ is just the solution to $m^2 = |\langle G\rangle| = n$. The point of the $\Omega$ is that a reasonable encoding doesn't have fewer than $\sqrt{n}$ vertices in a description of length $n$. For example "Write out the $k\times k$ adjacency matrix followed by $2^k$ zeroes" isn't "...

4

Unfortunately, as Raphael says, the answer is no. The formalist answer is that computability is defined for functions $f:\{0,1\}^* \to \{0,1\}$; it's not defined for functions on other domains. A possible motivation is that classical computability theory is concerned with what can be computed on a digital computer. A digital computer operates on bits. ...

3

In the following, I use "0" to denote a blank cell, and I first assume that 1 is not used in the original alphabet. I will deal with this at the end. A first solution is possible if you assume that the head can go over a cell and read it without writing on it. If you assume that you can tell the two ends of your input, the answer to your question is just ...

3

This is yet another example of enumerative encoding. Suppose that $x$ has $\alpha_i$ symbols of type $i$. The size of $S$ is then the multinomial coefficient $\binom{n}{\alpha_1,\ldots,\alpha_M}$. Pascal's identity reads $$\binom{n}{\alpha_1,\ldots,\alpha_M} = \sum_{i\colon \alpha_i \neq 0} \binom{n-1}{\alpha_1,\ldots,\alpha_i-1,\ldots,\alpha_M}.$$ In the ...

Only top voted, non community-wiki answers of a minimum length are eligible