Thursday, March 26, 2009

Gödelized coding

I was reading Frederick Pohl's "Starburst" recently. You may recall I reviewed it.
One of the things that intrigued me was the subject of Gödelized Numbering. The people on the ship planned to use it to encode their message for transmission back to Earth. They said it would use less power to transmit. I don't know about that, but from a purely mathematical point of view it caught my attention.

Here's a layman's version of this idea.
First, you write up your message.
Then count all the characters, including the space. Please don't ask me about punctuation.
Make up a list of prime numbers1 with as many numbers as you have characters. Yeah, those numbers get big pretty fast.
Associate the prime numbers list with the characters list. The first character has the first prime, the second number the second prime, the third the third, etc. etc. etc.
The characters have another number associated with. A more familiar one. A=1, B=2, C=3, D=4...X=24, Y=25, Z=26, space=0. You make this number the exponent of the prime number.

Yeah, I know. It's like reading board game rules. You don't understand what's going on until you actually start to play. Let me show you with a short word with letters at the beginning of the alphabet, cab, and hope that it makes more sense.

CAB = 23 * 31 * 52
CAB = (2*2*2)*(3)*(5*5)
CAB = 8 * 3 * 25
CAB = 600

Did you get all that?
C is the first letter of the message so it gets the first prime number, 2. C is also the third letter of the alphabet so 2 is raised to the third power (a.k.a cubed). 23
A is the second letter of the message so it gets the second prime number, 3. A, being the first letter of the alphabet, isn't multiplied. 31
B is the third letter of the message so it gets the third prime number, 5. B, being the second letter of the alphabet, is only squared. 52

At this point you're wondering what the point of all that is. You have a meaningless number. Well, not quite. You can see a zillion ways to take it apart but only one way is right. Get your calculator and follow along.

To get the first character out of the number you want to start dividing by the first prime number until you no longer get integers (i.e. whole numbers). Count the number of times you can divide it.

1) 600 / 2 = 300
2) 300 / 2 = 150
3) 150 / 2 = 75
4) 75 / 2 = 37.5

It successfully divided by 2 three times. The third letter of the
alphabet is C. The first letter of the message is C.

Repeat for the second prime/character.

1) 600 / 3 = 200
2) 200 / 3 = 66.666~

It successfully divided by 3 once. So the second character of the
message is the first letter of the alphabet.

One more with the third prime.

1) 600 / 5 = 120
2) 120 / 5 = 24
3) 24 / 5 = 4.8

Two divisions by 5 means that the third letter is B.

For a message like "Ibid Rules"
i=512
b=9
i=1953125
d=2401
[space]=11
r=112455406951957000000
u=69091933913008700000000000
l=2213314919066160
e=4084101
s=74615470927590700000000000
-----------------------------------------------
16,694,550,501,382,500,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

The question quickly arises why anybody would want to use this technique to send a message.
I tried converting this number to binary.
It went from 83 characters to 274 characters.

Monday I'll make an educated guess why they'd want to encode a number like this. I tried sounding it out to someone when I had a dry erase board handy. The graphics helped. I need to draw something up.


1A prime number is any number that can only be evenly divided by 1 and itself without resulting in a decimal point. Ex. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97...

4 comments:

BrianAlt said...

Maybe cause they can put it in hexidecimal and have only one number? If the message was sent as hexidecimal, each character would have it's own hex value. (I haven't worked out if it would actually be less that way.)

Sweetly Single said...

HOLY! So many numbers my eyes just exploded.

Ibid said...

Yeah, Yummy was a bit stunned when I was ranting about it as I read the book. But when we sat down with a calculator some weeks later and ran the numbers it started to make sense.

I've looked at some math blogs and they kinda fry my head. I tried to spell out the equations as best I could so that they could be followed.

GreenCanary said...

I think my eyes glazed over when he first tried explaining it to me. A second explanation was warranted and then I understood. I still don't get how it's an easier method of communication, or how it makes the message smaller, but I suspect this is because I'm a mathematical moron.