The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
3answers
94 views

Compression functions are only practical because “The bit strings which occur in practice are far from random”?

I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question. Andrej explains that given the set of all bit strings of length 3 or ...
3
votes
2answers
58 views

Why Shannon's Entropy is said to be a measure of information?

I got a bit of how Shannon explained to find the number of bits required to represent a message and Shannon's Entropy.But it's natural to know that to code alphabet letters you need ...
5
votes
3answers
145 views

Compression of Random Data is Impossible?

A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to ...
16
votes
4answers
3k 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 ...
2
votes
1answer
36 views

Entropy notation: What does this mean?

If you look at page 13 of the lecture slides here there is this line $H(Y) = H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha))$ I don't really understand what the term on right hand side is. At first I ...
2
votes
2answers
113 views

Is 95% of code really non-semantic fluff? [closed]

According to A Study of Wheat and Chaff in Source Code, 95% of code is "chaff", or "non-core functionality", whatever that means. Is this really a sensible study? Does the IT World article correctly ...
3
votes
1answer
27 views

Lower bounds for space with some probability of error

There is an information theoretic lower bound of $\log_2 {U \choose x}$ for the number of bits to represent a subset of $x$ elements chosen from a universe of size $U$. We can in principle use this ...
4
votes
1answer
42 views

Doubt in derivation of a proof in Information Theory

In my class we were trying to derive Shannon's Source Theorem, first by proving the equivalent form in a weaker version. The question is: Consider a biased coin with probability of heads $p \geq ...
2
votes
1answer
20 views

Using all the entropy in an biased bit

Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new ...
3
votes
0answers
27 views

Name of a type of code similar to block codes

I've encountered a system where I need to construct a sort of quasi block code: We want to communicate a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. ...
0
votes
2answers
19 views

Why are long block lengths commonly assumed/used in channel coding proofs?

As the title states, why are long block lengths commonly assumed or used in channel coding proofs?
35
votes
8answers
9k views

Is Morse code without spaces uniquely decipherable?

Are all Morse code strings uniquely decipherable? Without the spaces, ......-...-..---.-----.-..-..-.. could be Hello World ...
1
vote
0answers
24 views

Information content of computational problems

The notion of low information content is used to describe sparse sets and tally sets in complexity theory. Such sets can not be $NP$-complete unless $P=NP$. I am not aware of a formal ...
2
votes
1answer
39 views

An example of a code that is neither p-code or s-code but is uniquely decodable?

As the title says, code can't be a prefix-code and can't be a suffix-code, but it must be uniquely decodable. One possible code is this: {1, 101, 1001, ... }. Number of zeroes corresponds to the index ...
1
vote
0answers
17 views

Can independence numbers of box products of cycles increase after stabilizing?

Is there an evidence or a proof that the independence of strong products of graphs can increase after stabilizing? I am interested in odd cycles only. Let $C_n$ be an odd cycle and $\alpha(G)$ ...
1
vote
1answer
23 views

Inferring Shannon Capacity of pentagon

Can we infer from the fact that the number of independent sets in product of $5$-cycle two times is $5$ and in product of $5$-cycle four times is $25$, that the capacity of pentagon is $\sqrt{5}$? ...
2
votes
1answer
38 views

Is the Source Coding Theorem straightforward for uniformly distributed random variables?

Shannon's source coding theorem states the following: $n$ i.i.d. random variables $X_1,\dots,X_n$ each with entropy H(x) can be compressed into more than n⋅H(x) bits with negligible risk of ...
3
votes
1answer
34 views

Understanding the flaw in a proof attempt of the Communication Complexity of Equality

I'm new to communication theory and I've been wondering where the following simple argument fails: Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
2
votes
2answers
130 views

Lovasz theta of even cycle

How does one show Lovasz theta of even $n$-cycle ($n$ is even) is of form $\frac{n}{2}$? Why is the Lovasz theta of such cycles not of form $\frac{n \cos(\frac{\pi}{n})}{1+\cos(\frac{\pi}{n})}$. Could ...
0
votes
0answers
17 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 ...
2
votes
1answer
65 views

Is a very long plain text password harder to crack than a short complicated password? [closed]

Is it true that a password consisting of the alphabet, even of common known names is much harder to find for a computer program than a short password, even though it uses numbers and other characters? ...
4
votes
1answer
53 views

Mutual information intuition

I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent. ...
1
vote
1answer
23 views

Entropy sources: Weaver (1949) typo?

In Recent Contributions to The Mathematical Theory of Communication (Weaver 1949), aka The Mathematics of Communication (Weaver 1949) (various copies exist online), and also published as Part I of The ...
1
vote
1answer
35 views

Why the alphabet of the digital information is composed of 2 elements? [duplicate]

please don't offer an answer about "it's an electronic thing" or something like that, just keep reading. I don't understand why we use a dictionary, a lexicon, with just 2 elements to express the ...
2
votes
1answer
62 views

Relationship between message entropy and complexity of the best algorithm

Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages? E.g. linear search problem. We have an ordered set of incomparable ...
3
votes
1answer
89 views

Error-correction code for transmission only with bit-flipping from 0 to 1

I am using a transmission system that uses a Bloom filter (this part is out of my control). I want to send a small amount of data (32 bits) using this system. For each bit [0,31], I add its index to ...
3
votes
1answer
128 views

Conceptual question about entropy and information

Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that ...
2
votes
0answers
36 views

How to compare conditional entropy and mutual information?

I am solving a problem of information theory. The problem reads, Consider a stationary memoryless channel specified by the channel matrix $T = \begin{pmatrix}1-q&q\\r&1-r\end{pmatrix}$. ...
0
votes
1answer
41 views

Number of phrases of LZ compression

It is known that for the number $c(n)$ of phrases / tupel of the LZ compression for binary words of length $n$ the following relation holds: $$c(n)\leq\frac{n}{(1-\epsilon_n)\log_2 n}$$ With ...
3
votes
3answers
199 views

Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An ...
0
votes
1answer
128 views

Bayesian Nets & Markov Blanket

As i passed PHD entrance exam, some days ago, i want to find solutions for challenging problem. In Bayes network on X={X1,...Xn} each random variable has P parents and Q child's. for Xi we want to ...
1
vote
1answer
35 views

Mutual Information in a Binary Erasure Channel

Imagine a Binary Erasure Channel as depicted on Wikipedia. One equation describing the mutual information is: $$ \begin{align*}I(x;y) &= H(x) - H(x|y) \\ &= H(x) - p(y=0) \cdot 0 - p(y=?) ...
0
votes
1answer
71 views

Information loss of a 9-input majority gate [closed]

According to information theory, the logic gates AND, NAND, OR, NOR all lose 1.189 bits of information each with two bits of information at their inputs and with all inputs being independently and ...
25
votes
7answers
2k views

Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...
1
vote
1answer
26 views

On Shannon Capacity

Let $G$ be a graph whose Shannon Capacity is $\Theta(G)$. Is there any graph product for which the Shannon Capacity is $\Theta(G)^k$ where $k$ is the number of times the product is taken?
1
vote
1answer
41 views

Do the two huffman trees have the same corpus?

Consider the following Huffman trees: I was asked if those trees can have the same corpus. My answer was no, based on these calculations: For the right tree: $a_1 \le a_2$ $a_1 + a_2 \le a_5$ ...
5
votes
1answer
98 views

Showing that the entropy of i.i.d. random variables is the sum of entropies

The shannon entropy of a random variable $Y$ (with possible outcomes $\Sigma=\{\sigma_{1},...,\sigma_{k}\}$) is given by $H(Y)=-\sum\limits_{i=1}^{k}P(Y=\sigma_{i})\;\log(P(Y=\sigma_{i}))$. For a ...
2
votes
1answer
385 views

Gap between the average length of a Huffman code and its entropy

Difference between “average length” and “entropy” gives the percent of optimal. The optimal case is when the average length of a code is equal to the entropy. For example if average length is 1 and ...
3
votes
2answers
215 views

Compressing normally distributed data

Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly? Given the entropy of the Gaussian distribution, ...
0
votes
2answers
47 views

Arithmetic code: from interval to code value

I've not clear how to pass from final interval to code value, for example: Suppose we have the set of symbols={0,1,2,3} with probability={0.2, 0.5, 0.2 , 0.1} and that we have to encode a source ...
0
votes
1answer
55 views

Information capacity of Ternary-based system over Binary-based

Some researchers are trying to get a memory cell capable of having 3 states instead of 2. 1) How many memory cells, in principle and as a rough estimate, does a typical 1 megabyte memory chip has? is ...
1
vote
2answers
53 views

Why are bytes treated like the base unit?

If bits are the base unit of information, why are bytes treated like the base unit? For example, usually values are expressed in Mega/Giga/Tera/Exa bytes instead of bits. I am aware that bits are ...
1
vote
1answer
181 views

LZW decoding process

I'm trying to understand how LZW decodes a string. For example suppose that we have a dictionary where: a=0 b=1 and we have to encode the string "aabbabaabb", so the output of the encoding ...
2
votes
0answers
52 views

Notions of computational hardness in terms of information flow?

If we consider polynomial-time (or log-space) computable reductions $<_p^m$ as transformations between computational problems, then the following definitions of known complexity classes suggest ...
2
votes
1answer
157 views

Estimate entropy, based upon observed frequency counts

Suppose I have $n$ independent observations $x_1,\dots,x_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution. I can count the ...
3
votes
3answers
205 views

compressed information = randomness?

Suppose I have a compressed file and it is not possible to compress it more without loss of information. We say that this file is random or pseudorandom. So, if the randomness means not ...
2
votes
5answers
233 views

Is there a correlation of zip compression ratio and density of information provided by a text?

I'll phrase my question using an intuitive and rather extreme example: Is the expected compression ratio (using zip compression) of a children's book higher than that of a novel written for adults? ...
-1
votes
1answer
70 views

Information of a stream of bits

Here is my problem. I have to compute the amount of information that is possible to encode in a string of bits. This string of bits represent a stream. Let us call such stream as ...
0
votes
1answer
129 views

Notions of information content and randomness of binary square matrix

We have well established theory for measuring the information content and randomness of binary strings. Notions such as Shanon entropy and Kolmogorov-complexity were developed for binary strings. For ...
14
votes
2answers
340 views

What's harder: Shuffling a sorted deck or sorting a shuffled one?

You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits ...