Nahlédnutí do logu výzkumníkům odhalilo, že vyhledávače zásobují VÚČAKO neutuchajícím proudem zvídavců hledajících „princip CDMA“ nebo „jak funguje CDMA“. No, musíme sebekriticky přiznat, že pokud to dosud nevěděli, tady se to nevylepšilo. A vědecká rada rozhodla, že se s tím musí neco udělat.
Původní myšlenka totiž byla, že se v ústavu pro zasvěcené pojedná jen pár lahůdek jako je EV-DO a o obecnou osvětu se bezpochyby postarají osvědčená mediální zřídla masového poznání.
Z nejasných důvodů se tak neděje. Zběžné googlování odhalilo, že po bezmála dvou letech se české internetové zdroje ohledně principů CDMA omezují na blbé marketingové žvásty, tautologie rozvíjející do různé epické šíře mantru "kódové dělení používá pro dělení kód" a fachidiotské UMTS speciality ve stylu "DCCH->FACH->SCCPCH".
Výzkumníci se proto rozhodli odvážně se vrhnout do mokřadů popularizace. Sochaři, patologové a ženy v domácnosti se o CDMA možná dozví něco zajímavého. Profesionálové se doufejme slespoň shovívavě pobaví.
Pokud se bojíte, že za rohem číhá Proskurjakov,
nebojte se. Vezmeme to žertovně, i když se několika málo
triviálním vzorečkům nevyhneme.
Proč to všechno děláme?
No protože frekvenčního spektra máme málo a
potřebujeme, aby v něm mohlo komunikovat co nejvíce lidí
co nejrychleji.
V triviálním případě má každý
pár vysílač-přijímač vyhrazenou svoji frekvenci.
Takhle pracuje třeba AMPS nebo NMT a říkáme tomu
vícenásobný přístup s frekvenčním
dělením (FDMA). Funguje to, ale potíž je s efektivitou –
pásmo není nafukovacíí, a tak je "proužek"
pásma připadající na jeden "hovor" nutně jen
úzký – a tedy s velmi limitovanou kapacitou.
K řešení problému
vícenásobného přístupu lze také
přistoupit ve stylu "každý chvilku tahá pilku" –
tedy tak, že se uživatelé u vzácné frekvence
střídají v čase – každý ji má chvilku jen
pro sebe. Tomu se říká vícenásobný
přístup s časovým dělením (TDMA).
Nejznámější TDMA inkarnace jsou D-AMPS a GSM.
Ústřední myšlenkou jak FDMA tak i TDMA je
zabránit tomu, aby stejný fyzický prostředek –
frekvenci – v danou chvíli používal více než jeden
terminál.
Dělení nedělení.
Pak ale pár algebraických kouzelníků přišlo
s buřičskou myšlenkou. Prohlásili, že dosavadní
snaha oddělovat (v čase či frekvenčním prostoru)
účastníky při přístupu k přenosovému
médiu je jen pošetilý mentální blok.
Kýženým stavem je totiž oddělení informací
patřící jednotlivým účastníkům –
nikoli jejich fyzická separace při přístupu k
médiu.
Nechť si všichni hovoří přes sebe ve stejném
pásmu, nejsme tak omezení jako vousatí starci před
námi, kteří se v tom nedokázali přebrat. No –
vysmáli se jim, milé děti. Historii Qualcommu si ale
necháme na jindy. Je podstatné, že se myšlenka
ukázala jako nejen matematicky elegantní, ale i prakticky
velmi dobře realizovatelná.
Kódy
Oním gizmem zavádějícím řád do
chaosu povykujících vysílačů jsou kódy.
Odtud tedy vícenásobný přístup s
kódovým dělením (CDMA). V reálných
CDMA sítích je spousta různých kódů
poštelovaných pro různé účely.
Některé oddělují účastníky od sebe,
jiné řídicí od užitečných dat
téhož účastníka, pak máme kódy
starající se o rozprostírání spektra
nebo separaci sousedních sektorů a ještě jiné
kódy pečují o opravy chyb. K většině z nich se –
pokud to výzkumníky po pár dílech
nepřestane bavit – postupně dostaneme.
Ortogonalita
Devět z deseti odborníků doporučuje ortogonální kódy. Ve slovníku bude asi něco v tom smyslu, že původem řecké
slovo ortogonální znamená pravoúhlý.
Jak mohou být kódy pravoúhlé? Než
geometrickou představu ortogonality opustíme jako nadbytečnou,
ba škodlivou, sestrojíme takový
jednoduchý komunikační systém. Budeme
předávat informace současně Bobovi i Alici, a to tak, že
zapíchneme špendlík do nějakého čtverečku
milimetrového papíru. S Bobem, který to z
povzdálí pozoruje se dohodneme tak, že si odečte polohu
bodu na svislé ose, zatímco Alice se bude zajímat
o průmět na osu ortogonální/kolmou – tj. tu vodorovnou. Evidentně by to fungovalo – zdaliž bychom tedy namísto do roviny dané kolmými osami nemohli označkovat místo v prostoru ortogonálních kódů?
Pro další bude výhodné, když budeme s
kódy zacházet jako s vektory – třeba (1,0,1,0) a
poznačíme si je písmenky. Abychom poznali, že v je vektor, tak písmenko ztlustíme.
Geomertrie všedního dne nám dá v
ploše nahlédnout, že (1,0) a (0,1) jsou
ortogonální, ale s tak krátkými kódy
bychom daleko nedošli a v n-dimenzionálním
prostoru zase daleko nedojdeme s geometrií
všedního dne. Potřebujeme nějakou
lepší definici ortogonality. Triviální
představu o kolmosti z ortogonality vytěsníme pomocí
skalárního součinu.
Skalární součin bude udělátko, které
nám zobrazí vektorový prostor na domácky se
chovající reálná čísla. Přitom
budeme chtít, aby se chovalo pěkně a mravně, pročež budeme
požadovat následující veskrze rozumné vlastnosti:
1. chceme aditivitu – to jest aby: b(x,y+z) = b(x,y) + b(x,z)
2. násobení konstantou nás nerozhodí: b(kx, y) = kb(x,y)
3. chceme to mít symetrické: b(x, y) = b(y, x)
4. nechceme degeneraci: b(x,x) > 0 pro nenulové x
Naše požadavky splňuje třeba rozšíření
pojmu skalárního součinu vektorů v rovině jak jej
známe ze školy – tj. vezmu vektory po složkách,
pronásobím a výsledky posčítám.
Aby se to nepletlo, budeme si to značit tečkou, takže třeba
(1,0,1,0).(1,1,1,1) = 1+0+1+0 = 2. Oproti tomu
(1,0,0,0).(0,1,0,0) = 0.
No a za ortogonální prohlásíme
takové vektory (respektive kódy) v1…..vn jejichž
výše zavedený skalární součin je
nulový.
Stavíme CDMA systém
Nebolelo to a máme toho dost na CDMA systém pro Boba a
Alici. Abychom mohli začít, potřebujeme nějaké
dva pěkné ortogonální kódy. Co takhle v1=(1,1)
pro Boba a v2=(1,-1) pro Alici?
Důvěřujeme, ale prověřujeme: v1.v2 = 1-1 = 0. Hele – fakt jsou
ortogonální. Každý obor má svou
hantýrku – my v CDMA světě budeme v1 a v2 říkat chipy.
Kódujeme
Bobovi chceme sdělit, že (0,1,1,1), zatímco Alice jistě strne v němém úžasu, dozví-li se, že (1,0,1,0).
Kódovat budeme
pomocí chipů v, a to tak, že pro jedničku pošleme v a pro
nulu –v. Pro Boba tedy s použitím chipu v1
dostáváme (-1,-1,1,1,1,1,1,1), zatímco pro Alici a v2
máme (1,-1,-1,1,1,-1,-1,1).
Nebudeme se s tím párat a pošleme to dohromady – tj. sečteme. Na
svých mobilkách vidí Bob i Alice stejnou sekvenci:
(0,-2,0,2,2,0,0,2).
Dekódujeme
Bob dekóduje svým chipem – postupně dělá skalární součiny a dostává
((1,1).(0,-2), (1,1).(0,2), (1,1).(2,0), (1,1).(0,2)) = (-2, 2, 2, 2),
což až na pronásobení konstantou
odpovídá vyslané sekvenci (-1,1,1,1)
respektive (0,1,1,1)
zatímco Alice dekóduje pomocí v2 a
dostává ((1,-1).(0,-2), (1,-1).(0,2), (1,-1).(2,0),
(1,-1).(0,2)) = (2,-2,2,-2) – odpovídající
vyslanému (1,0,1,0)
Jak je tento zázrak – data pro Boba nejsou narušena těmi pro Alici a naopak – možný?
Jak to funguje?
Podívejme se, co se děje při dekódování. Vysíláme x1v1 + x2v2, kde xi je podle hodnoty posílaného bitu buď 1 nebo -1.
Bob dekóduje pomocí v1, tedy počítá v1.(x1v1 + x2v2).
Díky vlastnosti (1) skalárního součinu víme, že v1.(x1v1 + x2v2) = v1.x1v1 + v1.x2v2
Díky vlastnosti (2) můžeme přearanžovat xi takto: v1.x1v1 + v1.x2v2 = x1(v1.v1) + x2(v1.v2)
Vzpomeneme si, že kódy v1 a v2 jsme pečlivě volili tak, aby byly ortogonální – tedy musí platit, že v1.v2=0, druhý sčítanec vypadne a zbude jen x1(v1.v1)
O v1.v1
díky vlastnosti (4) víme, že je to nějaké
kladné číslo k – tedy se ho zbavíme bez vlivu na
znaménko xi.
A ejhle, dopracovali jsme se původního xi.
Hledáme dobré kódy
Shora uvedená matematika funguje pro libovolné ortogonální kódy. Inženýři ale budou mít na dobrý kód řadu dalších požadavků. Tak kupříkladu určitě budou vykřikovat, že chtějí, aby kód měl ostré autokorelační maximum. Chtějí tím říci, že jim pomůže když v.v bude co největší.
To má dobrý důvod. V reálném světě jsou kódy ortogonální jen do prvního odrazu rádiové vlny. Ve skutečnosti tak vi‚.vj‚ těžko bude nula – s trochou štěstí to ale bude nějaké "malé" číslo – dokud bude malé ve srovnání s vi.vi a vj.vj, nějak z toho ta data nakonec vydlabeme.
Požadavky na ortogonalitu a auto/cross-korelační vlastnosti jsou naneštěstí protichůdné, a tak volba dobrých kódu záleží na detailech implementace.
Synchronní systémy (jako CDMA2000) preferují přísnou ortogonalitu a přesným externím časováním se snaží kompenzovat problém, že Walsh-Hadamardovy kódy mají pro řadu časových posuvů hnusně velkou cross-korelaci.
Nesynchronizované UMTS rezignuje na přísnou ortogonalitu, ale použité Gold kódy mají jen tři cross-korelační maxima a se stoupající délkou kódu se ta dvě boční stávají nevýznamnými. Přijímač tak může nalézt začátek kódového slova bez dodatečné synchronizace.
Pro potřeby názornosti si nabrnkáme Walsh-Hadamardův kód postupem, který neukázal ani Walsh ani Hadamard, nýbrž někdy v půlce 19. století úžasně fousatý J.J. Sylvestr.
Walshovy kódy délky 2 už známe: (1,1) a (1,-1). Dáme je do řádků matice, kterou nazveme H.
Kód délky 2n vyrobíme rekurzívně skládáním do matic s řádky (H, H) a (H, -H) Třeba pro délku 4:
1 1 1 1
1 -1 1 -1
1 1 -1 -1
1 -1 -1 1
Je dobrým zvykem nakonec přerovnat řádky tak, aby počet znaménkových změn šel od nejmenší po největší.
Za domácí úkol můžete ověřit, že vzniklé kódy mají tu pozoruhodnou vlastnost, že ty kratší jsou – v polovičce případů – ortogonální i vůči segmentům těch následně delších. V inženýrské hantýrce se tomu říká OVSF (orthogonal variable spreading factor) kódy a ještě o nich uslyšíme.
A co GSM?
Mějme následující – evidentně ortogonální – kódy:
10000000
01000000
00100000
00010000
00001000
00000100
00000010
00000001
Snadno nahlížíme, že výsledně vysílaný vektor má tu vlastnost, že k jeho libovolné složce přispívá vždy jen právě jeden z osmi kódů. Přijímač se tak nemusí trápit s nějakými skalárními součiny – stačí když si počká na složku, která ho zajímá. CDMA systémům, které mají tuto vlastnost, budeme říkat TDMA.
// AMDG
Ukázkou sjednocující moci CDMA formalismu a demonstrací, že CDMA/TDMA dělení je vlastně umělé a GSM že je jen speciální případ mimořádně nešikovně navrženého CDMA systému, dnešní povídání ukončíme a budeme se těšit na pokračování příště.
Kristovo jatro!
primaDíky.Je to úžasné.
Jsem z toho jelen. Ale nejde hlasovat.
SkvěléDíky za informace. Není to asi sice úplně pro každého, ale moje středoškolská matematika na to stačí. Kdysi takovéhle věci psali na Mobil Serveru, ale pokrok se nedá zastavit…
Omyl clickNejak jsem omylem klikl na „Jsem z toho jelen“ misto na „Omoudril jsem se“. Takze kdyz se zobrazil vysledek meho hlasovani, tak jsem z toho byl jelen 🙂 Mozna by to chtelo trochu barevne oddelit, at clovek jasne vidi, na na co klika. Jinak clanek super! 🙂
Jo, to je onoZákladní principy. Nejtěžší je pochopit základní principy. Protože ty už nikdo nevysvětluje. Odborní odbornící prostě předpokládají a ostatní mlží. A ruku v ruce ohromují zkratkami a hantýrkou.Takže mnoho díků, zase vím něco, co má manželka a mí potomci ne.
Rekneme, ze ty matematicke sachy chapu (lemma). Ale selsky rozum se mi bouri: co ziskam tim, ze prenesu jednou pro vsechny (0,-2,0,2,2,0,0,2) – 8 jednotek, proti tomu, kdybych prenesl jednou (0,1,1,1) pro Boba a (1,0,1,0) pro Alici – celkem opet 8 jednotek? Je CDMA pro selky?
vůbec nevím o čem je řeč. ale pěkně se to čte, těším se na pokračování.
2adamBystrý dotaz. Až příště po cestě přidáme šum, ukáže se, že v tom rozdíl je.
2 adamkopp2 adamkoppSnad to bude explicitně v pokračováních, ale očekával bych, že největší užitek to přináší v opačném směru komunikace.Alice a Bob si současně posílají svoje 1 nebo -1, ve vzduchu se to sečte a BTSka si to rozebere na původní komponenty.
Nekdo chybi …… doufejme, ze priste prijde i Cecil. Nebo aspon matematika, pac pocty jsou moje slaba stranka 🙂 Uz je tam moc cisel.
Dobré 🙂Kvalitka, jen tak dál. Vysvětlení ortogonality na jednoduchém příkladě je povedené.
jsem pro NEHUL !!!Nejde hlasovat…
Nadherny clanek!Diky za skvele vysvetleni matematickych čachrů.Jen je skoda, ze uzasne fousatemu J.J. Sylvestrovi nefunguje http://WWW...
Pletu se?To adamkopp: No já těm matematickejm šachům zrovna nerozumím, ale myslím si že kdyby to rozdeleny, tak by jsi musel pridat nejaky jednotky pro urceni adresata, ne?
super…zrovna se ucim do predmetu „Teorie radiove komunikace“ a vysvetleni ortogonality pomoci „jablek a hrusek“ mi fakt pomohlo…
Viz tez..http://en.wikipedia.org/wiki/CdmaSouhlasim, ze je to o neco srozumitelnejsi prostemu cloveku nez scripta od Hrdiny 😉
FajnFajn článek, také jsem konečně pochopil ortogonalitu. Ty stránky tímto se zabývající ve skriptech od Hanuse (VUT Brno) jsem neměl odvahu přelouskat 🙂
Dik jak cyp :c)zdar, fakt dikes, uz sem to pochopil, nasel jsem totiz princip cdma popsany jen na wikipedii a v anglictine, tak se mi do toho moc nechtelo a ani sem to nechapal, ale z tohodle sem to pochopil a uz chapu i te wikipedii, za dva dny se me na to budou ptat u statnic tak wish me luck ;c)
superjj .. super napsane.
trochu teorieZdravím všechny, chtěl bych se zeptat, jestli nevíte někdo, kde bych našel na netu nebo v nějaké knize, trochu víc teorie k téhle problematice. sháním nějaké texty o hadamardových maticích a obecně o tvorbě signálu pro UMTS sítě. Dík za pomoc.
A. Viterbi: Principles of Digital Communication and Coding nebo novější V. Ipatov: Spread Spectrum and CDMA
supertak presne tohle jsem hledal, diky moc
Tak to teda anoTak tomuto hovorim excelentne pedagogicke prevedenie … nato ze som sa to uz ucil 2 krat (na dva rozlicne predmety a stale od zaciatku lebo sa to nedalo zapamatat) tak konecne uz v tom nemam humbuk … odomna 10 bodov z 10….
Pěkné vysvětleníHledám podobně srozumitelné vysvětlení vztahu mezi CDMA a technologií spread spectrum. Nevíte o něčem?