Understanding spreading codes

Spreading codes as used in CDMA are binary-vectors that can be used to encode multiple binary streams to be sent over a  shared medium at the same time using the same carrier frequency. Sounds funky? It is! The secret is to use vectors which are mutually orthogonal. An easy mathematical way to create those is constructing Hadamard matrices as a base for the vectors, because it’s rows are orthogonal to each other.

Constructing those is surprisingly easy. You start with a matrix of order n and create a new of order 2n

H_{2n} =  \begin{pmatrix}  H_n & H_n \\  H_n & -H_n  \end{pmatrix}

A trivial Hadamard matrix is (1), lets expand it:
H_1=(1) \rightarrow  H_2=\begin{pmatrix}  1 & 1 \\  1 & -1  \end{pmatrix} \rightarrow  H_4=\begin{pmatrix}  1 & 1 & 1 & 1 \\  1 &-1 & 1 &-1 \\  1 & 1 & -1 & -1 \\  1 &-1 & -1 & 1 \\  \end{pmatrix}
H_4 allows 4 transmitters to simultaneously use the medium. To achive this you must encode each data stream. This is done by multiplying the data segment with the code. E.g: Sending 1011 =(1,-1,1,1) using code (1,-1,-1,1) becomes (1,-1,-1,1,-1,1,1,-1,1,-1,-1,1,1,-1,-1,1). If you’re represent the negatives as zeros, this becomes a simple bitwise AND-operation.

CDMA sample coding

Now what happens if multiple emitters try to transmit this at the same time? This is where the fancy math comes into play. Orthogonal vectors form a right angle in space. We have 4-dimensional vectors UMTS uses 512-dimensional vectors, so don’t try to picture it :) – instead think about what you know about dot products of vectors:

\overrightarrow{v_1} \cdot \overrightarrow{v_2} = |\overrightarrow{v_1}||\overrightarrow{v_2}|\cdot cos(\alpha)
Where \alpha is the angle formed by the vectors.

As cos(90°) is 0, the dot product becomes 0 for orthogonal vectors.

When you send information at the same time, the carrier waves interfere with each other therefore the sending process of multiple transmitters could be described as follows (the different c_ns represent differences in transmitting power):

c_1 \cdot \overrightarrow{v_1} + c_2 \overrightarrow{v_2} + ... + c_n \overrightarrow{v_n}
Because the vectors are mutually orthogonal the reciever only has to dot-multiply the signal with the desired channel vector. All other subtotals become 0.

E.g: S1 sends 11 and uses code (1,-1,-1,1), S2 sends 10 and uses code (1,1,1,1),

S1:  \begin{array}{rrrrrrrrr}  & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\  \cdot & 1 & -1 & -1 & 1 & 1 &-1 &-1 & 1 \\  \hline  = & 1 & -1 & -1 & 1 & 1 &-1 &-1 & 1  \end{array}

S2:  \begin{array}{rrrrrrrrr}  & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\  \cdot & 1 & 1 & 1 & 1 &- 1 &-1 &-1 & -1 \\  \hline  = & 1 & 1 & 1 & 1 &- 1 &-1 &-1 & -1  \end{array}

Sum:  \begin{array}{rrrrrrrrr}  & 1 & -1 & -1 & 1 & 1 &-1 &-1 & 1 \\  + & 1 & 1 & 1 & 1 &-1 &-1 &-1 & -1 \\  \hline  = & 2 & 0 & 0 & 2 & 0 &-2 &-2 & 0  \end{array}

The reciever doesn’t need the exact results of this, aslong as the signs preserve he can extract the the desired channel by dot multiplication:
First bit S1:
\begin{pmatrix}  2 \\  0 \\  0 \\  2  \end{pmatrix} \cdot    \begin{pmatrix}  1 \\  -1 \\  -1 \\  1  \end{pmatrix}    = 2 \cdot 1 + 0 \cdot -1 + 0 \cdot -1 + 2 \cdot 1 = 4

Second bit S2:
\begin{pmatrix}  0 \\  -2 \\  -2 \\  0  \end{pmatrix} \cdot    \begin{pmatrix}  1 \\  1 \\  1 \\  1  \end{pmatrix}    = 0 \cdot 1 + -2 \cdot 1 + -2 \cdot 1 + 0 \cdot 1 = -4

As you can see positive results represent logical ones and negative represent logical zeros. The result is gained by the dimension (length) of the code vector. This is a nice sideeffect of CDMA as in practice this means you can use significant lower emiting power.

Categories: Math, Networking

Towel day! also: student bodies election

While the election (ÖH-Wahl) isn’t a big deal usually, this year – at least for some fans of the author Douglas Adams – it definitely was: one of the election dates was Towel Day, giving you a socially tolerated reason to bring a towel into the polling booth. This didn’t happen within the last 10 years…

  • 1999: May 18th, 19th and 20th
  • 2001: May 15th, 16th and 17th
  • 2003: May 20th, 21st and 22nd
  • 2005: May 31st, June 1st and 2nd
  • 2007: May 22nd, 23rd and 24th
  • 2009: May 26th, 27th and 28th
  • 2011: May 24th, >>25th<<, 26th

…in fact I don’t even know if it ever happened before. Anyway I think this is an opportunity a student could only have once in a lifetime.

My towel at the end of the day - littered with badges

Some references:
http://dokumentation.htu.tugraz.at/oeh-wahlen/
http://www.oeh-wahl.gv.at

Categories: non-technical

Free your Arduino: use a custom bootloader for C-Programming

I used to replace my arduino NG’s (which is using an atmega168) bootloader in
order to receive a clean prototyping interface which doesn’t use the arduino’s IDE and libraries. There’re a lot of benefits when doing so, but also disadvantages
so I made a pro/con-list:

pros:

  • experienced atmega users will get a familiar programming interface
  • software written for atmega is highly portable, old code could be reused even for non arduino applications
  • more flash-space for actual programs
  • as you’re programming the atmega directly without the arduinos interface you’ll have more possibilities of configuring and using your arduino

cons:

  • your arduino won’t be compatible with wiring and arduino software
  • your EEPROM won’t be programmable via USB
  • writing code for the atmega wont be that easy anymore and you’ll need
    more understanding of the microcontroller you’re using.

Hardware you’ll need:

  • an atmega compatible ISP (In System Programmer)

Software you’ll need:

  • avrdude or similar
  • an avr toolchain (compiler,assembler, etc…)
  • a sofware-programmer that supports communication with your bootloader

I’ve decided using FastBoot by Peter Dannegger. For build and configuration instructions
download the source from [1] and read the README file.

Step 1: Connecting the arduino with the ISP

Make sure to configure your arduino to use an external power supply
and connect the ISC cable with arduinos “ISCP” contacts on it’s right side

1_ _
|_|_|  MISO  VCC
|_|_|  SCK   MOSI
|_|_|  RESET GND
ISCP

Note: Pin1 is often marked by a red wire or a small triangle (or similar)

If your ISP doesn’t supply the Atmega itself (PWR led’s not glowing)  you’ll
need an external power supply

Step 2: Write the bootloader into atmega’s flash

You’ll need avrdude (or similar software)
to check if your ISP is connected right execute the following command:

> avrdude -F -p MCU -c PROGRAMMERID -b BAUD
for me:
> avrdude -F -p atmega168  -c usbtiny -b 19200

which gives following output :

avrdude: AVR device initialized and ready to accept instructions
Reading | #####...### | 100% 0.01s
avrdude: Device signature = 0x1e9406
avrdude: safemode: Fuses OK
avrdude done.  Thank you.

If everything is ok upload the bootloader:

> avrdude -F -p MCU  -c PROGRAMMERID -b BAUD -U flash:w:yourfile.hex

for me:

> avrdude -F -p atmega168  -c usbtiny -b 19200 -U flash:w:bootloader.hex

Step 3: Setting up the atmega’s secure bits (fuses) to setup the chip

Check your MCU’s datasheet and use [2] for desired configuration. Be careful
because this could easily lock you out of your microcontroller, so only a high power
programmer can help you to “unbrick” it.

First read the fuses:
> avrdude -F -p MCU -c PROGRAMMERID -b BAUD -v

for me:
> avrdude -F -p atmega168  -c usbtiny -b 19200 -v

output:
...
avrdude: safemode: lfuse reads as FF
avrdude: safemode: hfuse reads as DF
avrdude: safemode: efuse reads as 0
avrdude: safemode: Fuses OK

On an arduino with atmega168 0xFF;0xDF; should be ok, which is external clock
with 8MHz+; Serial Flashing on; and no other special features
However efuse=0 (which reserves 512 KB of size for the bootloader) may not fit your bootloader check its documentation for efuse values

To burn the fuses use:
> avrdude -F -p MCU  -c PROGRAMMERID -b BAUD -U lfuse:w:0xFF:m
> avrdude -F -p MCU  -c PROGRAMMERID -b BAUD -U hfuse:w:0xDF:m
> avrdude -F -p MCU  -c PROGRAMMERID -b BAUD -U efuse:w:0x00:m
for me:
> avrdude -F -p atmega168  -c usbtiny -b 19200 -U lfuse:w:0xFF:m
> avrdude -F -p atmega168  -c usbtiny -b 19200 -U hfuse:w:0xDF:m
> avrdude -F -p atmega168  -c usbtiny -b 19200 -U efuse:w:0x00:m

Step 4: upload the actual programm

The bootloader uses the ihex format so you’ll need to convert your application binary
to an ihex file (.hex)

To upload the code download the programming software from [3] and upload with:

> ./bootloader -d /dev/ttyUSBx -b BAUD -p yourapp.hex

for me:

> ./bootloader -d /dev/ttyUSB0 -b 19200 -p yourapp.hex

Note:The’re is also an app for programming the atmega on windows x86 (not x84-64) systems
it will also work with DOSBox on x64 systems and linux (linux users better use [3]).

I’ve made a full package .tgz with a blinking-led-example (on digital pin 13). Here:
http://x1598.at/~powertomato/blink.tgz

References:

[1] Bootloader Documentation (GER):
http://www.mikrocontroller.net/articles/AVR_Bootloader_FastBoot_von_Peter_Dannegger

[2] Fusebit Calculator:
http://www.engbedded.com/fusecalc/

[3] Linux programming tool (search for lboot.tgz or BootloaderXX_YYYYMMDD.tar.gz) (GER):
http://www.mikrocontroller.net/topic/73196#1955077

[4] Bootloader Download (search for fastboot_buildXX.tar.gz) (GER):
http://www.mikrocontroller.net/topic/146638#1824790

Further reading:

Arduino-to-Atmega168 Pinout:
http://arduino.cc/en/uploads/Hacking/Atmega168PinMap2.png

Use an arduino as an ISP:
http://arduino.cc/en/Tutorial/ArduinoISP

A neat USB-ISP:
http://www.ladyada.net/make/usbtinyisp/index.html

Atmega168 Datasheet:
http://www.atmel.com/dyn/resources/prod_documents/doc2545.pdf

Arduino on Bootloaders:
http://arduino.cc/en/Hacking/Bootloader?from=Main.Bootloader

Writing a bootloader by yourself (in german):
http://www.mikrocontroller.net/articles/AVR_Bootloader_in_C_-_eine_einfache_Anleitung

Categories: Microcontroller

Generating 8-bit sound with a microcontroller

Recently I’ve found the already exploited remains of a broken, pretty old Nokia phone. The only (usefull) parts I’ve haven’t desoldered was a SMD power led a vibration motor and a speaker. Since I always wanted to make a simple 8-bit like synthesizer, this time the speaker was the “lucky part”.

As a first try I used PWM to generate a 440 Hz square signal with my arduino. As a first test I directly connected the speaker to one of arduinos digital pins. For my surprise this actually worked. It was a bit quiet but it produced an A-tone. Usually a speaker is driven by an amplifier of the audio signal which is usually in range of -1.8V – 1.8V, so as the main problem of the low volume I identified that the speaker is only swinging with the half of its possible amplitude. Therefore I implemented a software PWM which generated a +5V -5V square wave istead of the 5V-0V square wave of the hardware PWM. For this I used the potential of two output pins of the controller. Which is 5V when a pin is pulled HIGH and the other one LOW. When you toggle both the resulting potential is -5V. As the volume of a speaker is proportional to the current I didn’t limit the output – be carefull when doing this, for me this worked fine as the speakers impedance was high enough to do so. The Atmega168s digital pins  maximum output is 40 mA when powered by a 5V source, but the input current mustn’t be higher than 20mA to avoid damaging the microcontroller.

After writing a driver for this I got it playing pretty neat sounding melodies. I used a SD-card cover as a resonant body, which made it much louder. So here is the temporary result:

Categories: Microcontroller
Follow

Get every new post delivered to your Inbox.