The short answer is no. There isn't such an algorithm that takes inputs of n bits and produces an output of y bits where n > y for all possible inputs.
You may immediately think of zipping or raring files and nearly all the time you get something smaller, and most of the time something, much, smaller. Well I am going to prove you that it's not possible.
Mathematical proof
A lossless encryption algorithm is mathematically a function, but a special type of function, a bijection. This is because the inverse of it must also be a function, if not this means the algorithm we are looking at is not lossless*.
Intuitive Explanation
Example 1) Let's try to design an algorithm for 2 bit strings, there are only 4 different inputs, which are
00, 01, 10, 11
but there are only 3 outputs:
null string, 0, 1
Now, how can we compress them to 1 and 0 bit? It is obvious when we think like that but this is true for all n, it is just not this obvious.
Example 2) Assume for a second we have a program which can compress anything, it doesn't have to be a super method which cuts the file size to half, but a just-fine method which drops file size at least by 1 bit. You give a 100 byte file and you get a file with 800-1=799 bits. Now what happens when you try to compress the resulting file? I mean giving the algorithm a 799 bit file and get a 798 bit file, remember we don't care what type of file that is, it might be compressed before or not. Do you see where this is going? If we compress that 800 times, we get a file with 0 bits. Can that be real?
One Last Point:
One of the first things came to my mind before thinking this through is,"That might be possible, it doesn't have to go all the way to 0, because it can look like the graph of the function 1/x+n. Each time you compress it will get a little bit lower, but the graph should be asymptotic to a some constant file size."
Do you see where this chain breaks? The thing that makes the previous statement meaningless is that there are infinite number of real numbers between any two real numbers, so a function may decrease over time for infinite time but not reach zero. Size of bitstrings are natural numbers. Even though there are infinitely many natural numbers, the thing what matters is the question "Are there infinitely many natural numbers between any two fixed natural numbers?" The answer is obviously no, this prevents us from thinking them like decreasing functions.
I am interested in hearing from you, what do you think is worth investigating and creating a simple brainstorming report?
*:At best case lossless, which is bad enough.
No comments:
Post a Comment