# Tag Info

Accepted

### Is Morse code without spaces uniquely decipherable?

The following are both plausible messages, but have a completely different meaning: ...
• 1,054
Accepted

### Can PRNGs be used to magically compress stuff?

You've got a brilliant new compression scheme, eh? Alrighty, then... ♫ Let's all play, the entropy game ♫ Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some ...

### Efficient compression of simple binary data

Sure, of course there are algorithms. Here is my algorithm: First, check if the file contains ordered binary numbers from $0$ to $2^n-1$, for some $n$. If so, write out a 0 bit followed by $n$ one ...
• 140k
Accepted

### Do lossless compression algorithms reduce entropy?

A lot of casual descriptions of entropy are confusing in this way because entropy is not quite as neat and tidy a measure as sometimes presented. In particular, the standard definition of Shannon ...
• 596

### Is Morse code without spaces uniquely decipherable?

Quoting David Richerby from the comments: Since ⋅ represents E and − represents T, any Morse message without spaces can be interpreted as a string in $\{E,T\}^*$ Further, since A, I, M, and N are ...
• 480
Accepted

### Can data be compressed to size smaller than Shannon data compression limit?

Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by log2 of the reciprocal of the probability. ...
• 12.3k
Accepted

### Data compression using prime numbers

always compress random data sets by more than 50% That's impossible. You can't compress random data, you need some structure to take advantage of. Compression must be reversible, so you can't ...

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

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, ...
• 402
Accepted

### Simulating a probability of 1 of 2^N with less than N random bits

Wow, great question! Let me try to explain the resolution. It'll take three distinct steps. The first thing to note is that the entropy is focused more on the average number of bits needed per draw,...
• 140k
Accepted

• 269k
Accepted

### PRNG for generating numbers with n set bits exactly

What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern. This is known as enumerative coding, and it's one of the oldest deployed ...
• 18.8k

### Can data be compressed to size smaller than Shannon data compression limit?

It's trivially simple to show that you can compress below the Shannon limit--take a cheating compressor that has a bunch of common files assigned to tokens. Said files are stored as those tokens. (...

### Do lossless compression algorithms reduce entropy?

No, if the algorithm is lossless no steps in the compression sequence can reduce its entropy - otherwise it would not be able to be decompressed/decoded. However, the additional entropy may be stored ...

### Is Morse code without spaces uniquely decipherable?

Morse Code is actually a ternary code, not a binary code, so the spaces are necessary. If spaces were not there, a lot of ambiguity would result, not so much with the entire message, but with ...
• 658
Accepted

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

First of all, you're right: Multimedia files are represented (more or less) as random files. The reason for that is that those files are already compressed (lossy). Note that mp3, for example, is ...
• 1,841

### Can data be compressed to size smaller than Shannon data compression limit?

You first apply the model to the data, computing the sequence of probabilities, f.e. $1/2$, $1/3$, $1/6$. Then, to encode each symbol with probability $p$, you need $log_2(1/p)$ bits. And given some ...
• 1,787

### I think you can always compress compressed data, is it true?

Here's the problem with that reasoning: If you could always compress data, you could compress the compressed data, then compress that, etc. until you have something that is 0 bytes long. You can ...
• 29.1k
Accepted

### Compression of Random Data is Impossible?

Here's the Kolmogorov complexity argument that @YuvalFilmus mentions in his answer. Your input here is a sed script of some size plus an input file of some size. ...
• 17.3k