Home   Groups   Digests   Personalise   Search   Login
  POV-Ray : Newsgroups : povray.off-topic : Code division multiplexing Server Time
29 Sep 2024 13:28:00 EDT (-0400)
  Code division multiplexing (Message 1 to 10 of 17)  
Goto Latest 10 Messages Next 7 Messages >>>
From: Invisible
Subject: Code division multiplexing
Date: 22 Apr 2009 11:26:47
Message: <49ef3737$1@news.povray.org>
 
I don't know why it works... but it does.

 >module CDM where
 >
 >encode :: [Int] -> [Int] -> [Int]
 >encode cs xs = do
 >  x <- xs
 >  c <- cs
 >  let y = if x == 1 then 1 else -1
 >  return (c*y)
 >
 >decode :: [Int] -> [Int] -> [Int]
 >decode cs [] = []
 >decode cs xs =
 >  let
 >    (xs0,xs1) = splitAt (length cs) xs
 >    y = sum (zipWith (*) cs xs0)
 >  in ((y `min` 1) `max` 0) : decode cs xs1

OK, so let's encode something:

   *CDM> encode [1,-1] [1, 0, 1]
   [1,-1,-1,1,1,-1]

   *CMD> decode [1,-1] [1,-1,-1,1,1,-1]
   [1,0,1]

Well that's nice. But now check this out:

   *CDM> let x1 = encode [1,1,1,1] [1,1,0,1]
   *CDM> let x2 = encode [1,-1,1,-1] [1,0,1,1]
   *CDM> let x3 = encode [1,1,-1,-1] [0,0,1,1]
   *CDM> let x4 = encode [1,-1,-1,1] [1,1,1,0]
   *CDM> x1
   [1,1,1,1,1,1,1,1,-1,-1,-1,-1,1,1,1,1]
   *CDM> x2
   [1,-1,1,-1,-1,1,-1,1,1,-1,1,-1,1,-1,1,-1]
   *CDM> x3
   [-1,-1,1,1,-1,-1,1,1,1,1,-1,-1,1,1,-1,-1]
   *CDM> x4
   [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,-1,1,1,-1]
   *CDM> let y = foldl1 (zipWith (+)) [x1,x2,x3,x4]
   *CDM> y
   [2,-2,2,2,0,0,0,4,2,-2,-2,-2,2,2,2,-2]
   *CDM> decode [1,1,1,1] y
   [1,1,0,1]
   *CDM> decode [1,-1,1,-1] y
   [1,0,1,1]
   *CDM> decode [1,1,-1,-1] y
   [0,0,1,1]
   *CDM> decode [1,-1,-1,1] y
   [1,1,1,0]

Magic!


Post a reply to this message
From: Darren New
Subject: Re: Code division multiplexing
Date: 22 Apr 2009 11:47:55
Message: <49ef3c2b$1@news.povray.org>
 
Invisible wrote:
> Magic!

http://denbeste.nu/cd_log_entries/2002/04/Howspreadingactuallyworks.shtml

http://denbeste.nu/special/cdma_spreading.html

Not magic, but certainly very difficult to understand intuitively.

-- 
   Darren New, San Diego CA, USA (PST)
   There's no CD like OCD, there's no CD I knoooow!


Post a reply to this message
From: Warp
Subject: Re: Code division multiplexing
Date: 22 Apr 2009 13:29:19
Message: <49ef53ef@news.povray.org>
 
Invisible <voi### [at] devnull> wrote:
> I don't know why it works... but it does.

>  >module CDM where
>  >
>  >encode :: [Int] -> [Int] -> [Int]
>  >encode cs xs = do
>  >  x <- xs
>  >  c <- cs
>  >  let y = if x == 1 then 1 else -1
>  >  return (c*y)
>  >
>  >decode :: [Int] -> [Int] -> [Int]
>  >decode cs [] = []
>  >decode cs xs =
>  >  let
>  >    (xs0,xs1) = splitAt (length cs) xs
>  >    y = sum (zipWith (*) cs xs0)
>  >  in ((y `min` 1) `max` 0) : decode cs xs1

> OK, so let's encode something:

>    *CDM> encode [1,-1] [1, 0, 1]
>    [1,-1,-1,1,1,-1]

>    *CMD> decode [1,-1] [1,-1,-1,1,1,-1]
>    [1,0,1]

> Well that's nice. But now check this out:

>    *CDM> let x1 = encode [1,1,1,1] [1,1,0,1]
>    *CDM> let x2 = encode [1,-1,1,-1] [1,0,1,1]
>    *CDM> let x3 = encode [1,1,-1,-1] [0,0,1,1]
>    *CDM> let x4 = encode [1,-1,-1,1] [1,1,1,0]
>    *CDM> x1
>    [1,1,1,1,1,1,1,1,-1,-1,-1,-1,1,1,1,1]
>    *CDM> x2
>    [1,-1,1,-1,-1,1,-1,1,1,-1,1,-1,1,-1,1,-1]
>    *CDM> x3
>    [-1,-1,1,1,-1,-1,1,1,1,1,-1,-1,1,1,-1,-1]
>    *CDM> x4
>    [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,-1,1,1,-1]
>    *CDM> let y = foldl1 (zipWith (+)) [x1,x2,x3,x4]
>    *CDM> y
>    [2,-2,2,2,0,0,0,4,2,-2,-2,-2,2,2,2,-2]
>    *CDM> decode [1,1,1,1] y
>    [1,1,0,1]
>    *CDM> decode [1,-1,1,-1] y
>    [1,0,1,1]
>    *CDM> decode [1,1,-1,-1] y
>    [0,0,1,1]
>    *CDM> decode [1,-1,-1,1] y
>    [1,1,1,0]

> Magic!

  Are you seriously expecting people to understand what's going on there,
without any kind of explanation?

  I'm a programmer and I haven't the slightest idea.

-- 
                                                          - Warp


Post a reply to this message
From: Orchid XP v8
Subject: Re: Code division multiplexing
Date: 22 Apr 2009 13:34:18
Message: <49ef551a$1@news.povray.org>
 
Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> I don't know why it works... but it does.
> 
>>  >module CDM where
>>  >
>>  >encode :: [Int] -> [Int] -> [Int]
>>  >encode cs xs = do
>>  >  x <- xs
>>  >  c <- cs
>>  >  let y = if x == 1 then 1 else -1
>>  >  return (c*y)
>>  >
>>  >decode :: [Int] -> [Int] -> [Int]
>>  >decode cs [] = []
>>  >decode cs xs =
>>  >  let
>>  >    (xs0,xs1) = splitAt (length cs) xs
>>  >    y = sum (zipWith (*) cs xs0)
>>  >  in ((y `min` 1) `max` 0) : decode cs xs1
> 
>> OK, so let's encode something:
> 
>>    *CDM> encode [1,-1] [1, 0, 1]
>>    [1,-1,-1,1,1,-1]
> 
>>    *CMD> decode [1,-1] [1,-1,-1,1,1,-1]
>>    [1,0,1]
> 
>> Well that's nice. But now check this out:
> 
>>    *CDM> let x1 = encode [1,1,1,1] [1,1,0,1]
>>    *CDM> let x2 = encode [1,-1,1,-1] [1,0,1,1]
>>    *CDM> let x3 = encode [1,1,-1,-1] [0,0,1,1]
>>    *CDM> let x4 = encode [1,-1,-1,1] [1,1,1,0]
>>    *CDM> x1
>>    [1,1,1,1,1,1,1,1,-1,-1,-1,-1,1,1,1,1]
>>    *CDM> x2
>>    [1,-1,1,-1,-1,1,-1,1,1,-1,1,-1,1,-1,1,-1]
>>    *CDM> x3
>>    [-1,-1,1,1,-1,-1,1,1,1,1,-1,-1,1,1,-1,-1]
>>    *CDM> x4
>>    [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,-1,1,1,-1]
>>    *CDM> let y = foldl1 (zipWith (+)) [x1,x2,x3,x4]
>>    *CDM> y
>>    [2,-2,2,2,0,0,0,4,2,-2,-2,-2,2,2,2,-2]
>>    *CDM> decode [1,1,1,1] y
>>    [1,1,0,1]
>>    *CDM> decode [1,-1,1,-1] y
>>    [1,0,1,1]
>>    *CDM> decode [1,1,-1,-1] y
>>    [0,0,1,1]
>>    *CDM> decode [1,-1,-1,1] y
>>    [1,1,1,0]
> 
>> Magic!
> 
>   Are you seriously expecting people to understand what's going on there,
> without any kind of explanation?
> 
>   I'm a programmer and I haven't the slightest idea.

encode <key> <data> gives you a bunch of stuff. decode <key> <stuff> 
gives you back the original data.

Which isn't that surprising. What's surprising is that if you add 
several of these together, the decode function still works. (Provided 
each data stream has a different key - or, more exactly, an "orthoganol" 
key.)

Apparently this is how mobile phones manage to all transmit at the same 
time yet not screw up each other's transmissions.

This much I would have thought would be vaguely intuitive from the 
program's output. Of course, to comprehend how I've implemented the 
encode/decode functions, you'd need to understand Haskell...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*


Post a reply to this message
From: Tim Attwood
Subject: Re: Code division multiplexing
Date: 22 Apr 2009 15:59:09
Message: <49ef770d$1@news.povray.org>
 
>>> I don't know why it works... but it does.
>>
>>>  >module CDM where
>>>  >
>>>  >encode :: [Int] -> [Int] -> [Int]
>>>  >encode cs xs = do
>>>  >  x <- xs
>>>  >  c <- cs
>>>  >  let y = if x == 1 then 1 else -1
>>>  >  return (c*y)
>>>  >
>>>  >decode :: [Int] -> [Int] -> [Int]
>>>  >decode cs [] = []
>>>  >decode cs xs =
>>>  >  let
>>>  >    (xs0,xs1) = splitAt (length cs) xs
>>>  >    y = sum (zipWith (*) cs xs0)
>>>  >  in ((y `min` 1) `max` 0) : decode cs xs1
>>
>>> OK, so let's encode something:
>>
>>>    *CDM> encode [1,-1] [1, 0, 1]
>>>    [1,-1,-1,1,1,-1]
>>
>>>    *CMD> decode [1,-1] [1,-1,-1,1,1,-1]
>>>    [1,0,1]
>>
>>> Well that's nice. But now check this out:
>>
>>>    *CDM> let x1 = encode [1,1,1,1] [1,1,0,1]
>>>    *CDM> let x2 = encode [1,-1,1,-1] [1,0,1,1]
>>>    *CDM> let x3 = encode [1,1,-1,-1] [0,0,1,1]
>>>    *CDM> let x4 = encode [1,-1,-1,1] [1,1,1,0]
>>>    *CDM> x1
>>>    [1,1,1,1,1,1,1,1,-1,-1,-1,-1,1,1,1,1]
>>>    *CDM> x2
>>>    [1,-1,1,-1,-1,1,-1,1,1,-1,1,-1,1,-1,1,-1]
>>>    *CDM> x3
>>>    [-1,-1,1,1,-1,-1,1,1,1,1,-1,-1,1,1,-1,-1]
>>>    *CDM> x4
>>>    [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,-1,1,1,-1]
>>>    *CDM> let y = foldl1 (zipWith (+)) [x1,x2,x3,x4]
>>>    *CDM> y
>>>    [2,-2,2,2,0,0,0,4,2,-2,-2,-2,2,2,2,-2]
>>>    *CDM> decode [1,1,1,1] y
>>>    [1,1,0,1]
>>>    *CDM> decode [1,-1,1,-1] y
>>>    [1,0,1,1]
>>>    *CDM> decode [1,1,-1,-1] y
>>>    [0,0,1,1]
>>>    *CDM> decode [1,-1,-1,1] y
>>>    [1,1,1,0]
>>
>>> Magic!
>>
>>   Are you seriously expecting people to understand what's going on there,
>> without any kind of explanation?
>>
>>   I'm a programmer and I haven't the slightest idea.
>
> encode <key> <data> gives you a bunch of stuff. decode <key> <stuff> gives 
> you back the original data.
>
> Which isn't that surprising. What's surprising is that if you add several 
> of these together, the decode function still works. (Provided each data 
> stream has a different key - or, more exactly, an "orthoganol" key.)
>
> Apparently this is how mobile phones manage to all transmit at the same 
> time yet not screw up each other's transmissions.
>
> This much I would have thought would be vaguely intuitive from the 
> program's output. Of course, to comprehend how I've implemented the 
> encode/decode functions, you'd need to understand Haskell...

No wonder cell phones keep cutting out.

All it takes for a bit to be lost is for one analog "chip" to be
a little outside of it's intended magnitude and then it misses
the whole bit.


Post a reply to this message
From: Orchid XP v8
Subject: Re: Code division multiplexing
Date: 22 Apr 2009 16:11:30
Message: <49ef79f2$1@news.povray.org>
 
>>>   Are you seriously expecting people to understand what's going on 
>>> there,
>>> without any kind of explanation?
>>>
>>>   I'm a programmer and I haven't the slightest idea.
>>
>> encode <key> <data> gives you a bunch of stuff. decode <key> <stuff> 
>> gives you back the original data.
>>
>> Which isn't that surprising. What's surprising is that if you add 
>> several of these together, the decode function still works. (Provided 
>> each data stream has a different key - or, more exactly, an 
>> "orthoganol" key.)
>>
>> Apparently this is how mobile phones manage to all transmit at the 
>> same time yet not screw up each other's transmissions.
>>
>> This much I would have thought would be vaguely intuitive from the 
>> program's output. Of course, to comprehend how I've implemented the 
>> encode/decode functions, you'd need to understand Haskell...
> 
> No wonder cell phones keep cutting out.
> 
> All it takes for a bit to be lost is for one analog "chip" to be
> a little outside of it's intended magnitude and then it misses
> the whole bit.

No.

Each signal bit is encoded by several analog "chips". If one such chip 
is lost (a very likely occurance, given that others are using the same 
chip frequencies concurrently), the remaining chips still allow the 
signal to be recovered. (This is precisely _why_ there are several chips 
to each signal bit.)

Add error-detecting and correcting codes on top of that and you have... 
well personally I find it fairly unusual for *my* phone to cut out. But 
then, my network seems to have unusually good coverage.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*


Post a reply to this message
From: Darren New
Subject: Re: Code division multiplexing
Date: 22 Apr 2009 17:13:00
Message: <49ef885c$1@news.povray.org>
 
Orchid XP v8 wrote:
> Apparently this is how mobile phones manage to all transmit at the same 
> time yet not screw up each other's transmissions.

More specifically, how CDMA phones manage it. GSM phones and many others use 
different techniques.

-- 
   Darren New, San Diego CA, USA (PST)
   There's no CD like OCD, there's no CD I knoooow!


Post a reply to this message
From: Darren New
Subject: Re: Code division multiplexing
Date: 22 Apr 2009 17:15:04
Message: <49ef88d8$1@news.povray.org>
 
Tim Attwood wrote:
> All it takes for a bit to be lost is for one analog "chip" to be
> a little outside of it's intended magnitude and then it misses
> the whole bit.

Actually, the whole point of the technology is that you *can't* jam it 
without basically blanketing everything in the entire bandwidth (including 
your own signals), and it's virtually impossible to detect because it all 
sounds like noise unless the receiver has a key that matches the 
transmitter.  It was originally developed for military radios, ya know.

-- 
   Darren New, San Diego CA, USA (PST)
   There's no CD like OCD, there's no CD I knoooow!


Post a reply to this message
From: Invisible
Subject: Re: Code division multiplexing
Date: 23 Apr 2009 03:52:54
Message: <49f01e56$1@news.povray.org>
 
Darren New wrote:
> Orchid XP v8 wrote:
>> Apparently this is how mobile phones manage to all transmit at the 
>> same time yet not screw up each other's transmissions.
> 
> More specifically, how CDMA phones manage it. GSM phones and many others 
> use different techniques.

Really? That's interesting... I got to the CDMA article *from* the GSM 
article. o_O


Post a reply to this message
From: Invisible
Subject: Re: Code division multiplexing
Date: 23 Apr 2009 05:15:27
Message: <49f031af$1@news.povray.org>
 
Darren New wrote:

> http://denbeste.nu/special/cdma_spreading.html
> 
> Not magic, but certainly very difficult to understand intuitively.

Hey, neat.

So it's kind-of like this?

http://en.wikipedia.org/wiki/Visual_cryptography

I'm still trying to figure out exactly how it works, but it's quite neat.

And now I'm wondering... can you implement this stuff using only 
analogue electronics? My first instinct is "how the hell do you compute 
signal correlation without a computer?" but now I'm thinking maybe you 
can do it with some op-amps. The only real problem would be getting 
sender and receiver to generate the same psuedo-random reference signal, 
and keep it synchronised.


Post a reply to this message
Goto Latest 10 Messages Next 7 Messages >>>

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.