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

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

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

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

>>> 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

>>>   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

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

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

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

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

Invisible wrote:
...
> 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.
...

http://google.com/search?&q=(analog+OR+analogue)+computer

-- 
Tor Olav
http://subcube.com

Post a reply to this message

Tor Olav Kristensen wrote:
> Invisible wrote:
> ...
>> 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.
> ...
> 
> http://google.com/search?&q=(analog+OR+analogue)+computer

Oh my God, check it out:

http://en.wikipedia.org/wiki/File:AKAT-1.JPG

Funkalishous, baby!


But yeah, I was thinking that splitting a signal into pieces and 
computing a step-wise correlation would seem to require digital 
electronics. But it doesn't really. You could probably wire up a system 
that has a meter showing the instantaneous correlation between two 
inputs without much difficulty. (And the spring in the meter will 
probably smooth it out quite nicely.)

Post a reply to this message

Invisible wrote:
> 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

Not too different, except you do it with dozens of different masks. :-)

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

Once you figure it out, then realize you can talk at two different speeds at 
the same time on the same frequencies (which is what the phone does for 
voice vs signaling), you can talk to two different carriers on the same 
frequency at the same time, and you have to account for round-trip speed of 
light delays, including predicting how much that delay will change before 
the next packet based on the fact that you're driving towards or away from 
the tower...   And the tower has to modify the timing of the chips for each 
phone based on the round-trip delays.

> And now I'm wondering... can you implement this stuff using only 
> analogue electronics? 

No idea. :-)

-- 
   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

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

Sure. The old analog phones used FDM (Frequency Division Multiplexing), and 
GSM uses (I think) TDMA - time division multiple access.  There's also 
phase-division multiple access, as well as various combinations thereof.

-- 
   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

On 23-4-2009 16:33, Invisible wrote:
> Tor Olav Kristensen wrote:
>> Invisible wrote:
>> ...
>>> 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.
>> ...
>>
>> http://google.com/search?&q=(analog+OR+analogue)+computer
> 
> Oh my God, check it out:
> 
> http://en.wikipedia.org/wiki/File:AKAT-1.JPG
> 
> Funkalishous, baby!
> 
We had one that filled one wall of the room at our practical instruction 
lab (beginning 1980's). With a patch panel of 4 by 2 meters or so. It 
used to be a section of an even larger one used for ship behaviour 
simulation. We got it as a gift when they converted to digital computers.

Post a reply to this message

Darren New wrote:
> Invisible wrote:
>> Really? That's interesting... I got to the CDMA article *from* the GSM 
>> article. o_O
> 
> Sure. The old analog phones used FDM (Frequency Division Multiplexing), 
> and GSM uses (I think) TDMA - time division multiple access.  There's 
> also phase-division multiple access, as well as various combinations 
> thereof.

Hmm, OK. Apparently,

"The modulation used in GSM is Gaussian minimum-shift keying (GMSK), a 
kind of continuous-phase frequency shift keying. In GMSK, the signal to 
be modulated onto the carrier is first smoothed with a Gaussian low-pass 
filter prior to being fed to a frequency modulator, which greatly 
reduces the interference to neighboring channels (adjacent channel 
interference)."

So not CDMA at all. Weird...

Post a reply to this message

Le 25/06/2009 10:27, Invisible nous fit lire :
> Darren New wrote:
>> Invisible wrote:
>>> Really? That's interesting... I got to the CDMA article *from* the
>>> GSM article. o_O
>>
>> Sure. The old analog phones used FDM (Frequency Division
>> Multiplexing), and GSM uses (I think) TDMA - time division multiple
>> access.  There's also phase-division multiple access, as well as
>> various combinations thereof.
> 
> Hmm, OK. Apparently,
> 
> "The modulation used in GSM is Gaussian minimum-shift keying (GMSK), a
> kind of continuous-phase frequency shift keying. In GMSK, the signal to
> be modulated onto the carrier is first smoothed with a Gaussian low-pass
> filter prior to being fed to a frequency modulator, which greatly
> reduces the interference to neighboring channels (adjacent channel
> interference)."
> 
> So not CDMA at all. Weird...

Not at all... but 3G (successor of GSM, in term of end-user technology/availabilty) is
using CDMA.
European use of UMTS (3G) is based on W-CDMA (W- : wideband), but not only.

GSM is 2G (quite old), playing with sub-channels (124 of 200kHz each, with 8 time
slot) in
TX & RX separated bands. Payload per timeslot is about 24.7 kbit/s (and no link
aggregation).
Of the 124 sub-frequencies, for a given point in space, they must be split between, at
least and optimaly, 3 ground-antenna (think plane-coloring... with some antenna having
different forms of cover, and some covers being influenced by the actual topology and
buildings)

GSM transmission is coded in the phase of a constant amplitude signal, allowing to
elect
the best antenna rather easily for the receiver (pick the strongest received
amplitude);
Phase modulation being one of the best modulation for issue with moving apparatus and
echo
of signal on buildings.

But it does not allow to share timeslots.

Between GSM and UMTS, GPRS and EDGE are extending the GSM system.
GPRS allow link aggregation (upto 8 timeslots, if the ground antenna is idle enough to
allow that), and then EDGE use a higher-density coding in the phase modulation to
extend
the bandwidth of GPRS (with limitation to the range... there must be a trade-off).

It's all like the old modem technology, giving new legs to an old horse.
(9600/28k/56k...)

CDMA (UMTS/...) is to GSM what ADSL is to modem. A totally different beast. The end
user
still surf the internet (resp. make phone calls), the technology in the middle is just
not
the same. And yet, it's only an electrical (resp. a radio) signal on a telephonic wire
(resp. on the air).

Post a reply to this message