Algebrai rész

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Singleton-korlát

$M\leq q^{n-d_{min}+1}$

• $q$ a kódábécé elemszáma (bináris esetben $q=2$)
• $M$ a kódszavak száma
• $d_{min}$ a minimális Hamming távolság
• n a kódszavak hossza

• ha = áll fenn, akkor a kód MDS tulajdonságú, ekkor $d_{min}=n-k+1$ (pl.: Reed-Solomon kódok)

Hamming-korlát

$\displaystyle \sum _{i=0}^{t}{\binom {n}{i}}(q-1)^{i}\leq q^{n-k}$

• a kód $t$ hibát tud javítani
• $q$ a kódábécé elemszáma (bináris esetben $q=2$)
• $k$ az üzenetek hossza
• $n$ a kódszavak hossza
• ha a képletben egyenlőség áll fenn, akkor a kód perfekt (pl.: Hamming kódok)
• bináris esetben a használjuk leggyakrabban a fenti képletet, ekkor az alakja: $\displaystyle \sum _{i=0}^{t}{\binom {n}{i}}\leq q^{n-k}$
• bináris, egy hibát javító Hamming-kód esetében a kód perfekt, ha $1+n=2^{n-k}$

Kódtervezés komplexitása

Off-line komplexitás

$O\left(\displaystyle {\binom {2^{n}}{2^{k}}}{\binom {2^{k}}{2}}\right)$

On-line komplexitás

$O\left(2^{k}\right)$

Random coding

paraméterek: $n=q^{t}-1~~~~~k=t$

• q a kódábécé elemszáma
• t a shiftregiszter hossza

$d_{min}=q^{t-1}$

Reed-Solomon kódok spektrális tulajdonságai

Fourier-transzformáció

def.

$GF(q)=GF(p^{m})$, ahol $p$ prim

$C_{j}=\displaystyle \sum _{i=0}^{n-1}\alpha ^{ij}c_{i}$ , ahol

• $\alpha$ a GF(q) egy n-edrendű eleme ( nem kell primitív elem, mert lehet, hogy n kisebb a test méreténél)
• a transzformáció a $c\in \left[GF(q)\right]^{n}$ vektort képezi le egy $C\in \left[GF(q)\right]^{n}$ vektorra

Inverz transzformáció

$c_{i}=f(n)\displaystyle \sum _{j=0}^{n-1}\alpha ^{-ij}C_{j},~~~~~i=0,1,\dots n-1$

• $f(n)=\left(n\mod p\right)^{-1}$, ahol a -1-edik hatvány a GF(p) beli multiplikatív inverz

Konvolúciós tétel

Ha az $e,f,g\in \left[GF(q)\right]^{n}$ vektorokra teljesül $e_{i}=f_{i}g_{1},~~~~i=0,1,\dots ,n-1~~~~~,~~akkor$ $E_{j}=f(n)~\displaystyle \sum _{k=0}^{n-1}F_{(j-k)mod~n}G_{k}$

• az $E_{j}$ ebben az esetben $F$, és $G$ ciklikus konvolúciója

Bithibavalószínűség

$P_{b}=\Phi \left(-{\sqrt {SNR}}\right)$ , ahol

• $\Phi$ a standard normális eloszlásfüggvény
• $SNR$ a jel-zaj viszony (Signal to Noise Ratio)

BSC

$SNR_{BSC}=\displaystyle {\frac {1}{N_{0}}}$

CSMA/CD ortogonális kódok

$SNR_{OC}=\displaystyle {\frac {1}{\displaystyle {\frac {N_{0}}{T_{S}}}}}$

• $T_{S}$ a signature time, azaz a kommunikáció során használatos jeltartási idő

CSMA/CD Random Coding

$SNR_{RC}=\displaystyle {\frac {1}{N_{0}+{\frac {M-1}{N}}}}$

• $N_{0}\geq 0$ az AWGN(additiv Gaussian White Noise) szórása a csatornán, avagy a zajteljesítmény
• $N=\displaystyle {\frac {T_{s}}{T_{c}}}$ a szimbóluim- és a chipidő hányadosa
• $M$ a felhasználók száma

Konvolúciós kódok komplex ábécé felett

$P_{e}\geq N_{d}\Phi \left(-\displaystyle {\frac {d}{2\sigma }}\right)$

• $P_{e}$ a hibás kódszóra való döntés valószínűsége
• $\sigma$ a gaussi zajmint szórása
• $N_{d}$ a zérus kódszótól d minimális euklideszi távolságra lévő kódszavak száma

$G=20\log _{10}\displaystyle {\frac {d_{free}}{d_{ref}}}~~~~~[dB]$

• $d_{ref}$ a kódolatlan esetben adódó minimális euklideszi távolság
• $d_{free}$(=$d_{\infty }$) a szabad távolság
• $d_{free}=\displaystyle \max _{r}d_{r}^{*}$

Viterbi-dekódolás bithibaaránya diszkrét emlékezetnélküli csatornán

$P_{b}\leq \displaystyle {\frac {\partial T(D,I)}{\partial I}}$

• $T(D,I)=\displaystyle \sum _{i=1}^{\infty }\sum _{d=1}^{\infty }a(d,i)I^{i}D^{d}$
• itt $I=1,D=e^{-{\frac {1}{2N_{0}}}}$

felhasználók száma

$M\sim O\left(N^{2}\right)$

• $M$ felhasználószám
• $N$ frekvenciák száma ( a szórókód mtx $NxN$-es )

CDMA/DS

Az ${\overline {\overline {R}}}$ mtx

${\overline {\overline {R}}}_{ij}=\displaystyle {\frac {1}{N}}~{\overline {C}}{i}~{{\overline {C}}{j}}^{T}$

• $N$ a felhasználószám
• ${\overline {C}}_{i}$ az i. szórókód vektor

vett vektor

${\overline {x}}={\overline {\overline {R}}}{\overline {y}}+{\overline {\nu }}\sim N({\overline {\overline {R}}}~{\overline {y}},N_{0}{\overline {\overline {R}}})$

• ${\overline {\overline {R}}}$ kovarianciamátrix
• az AWGN $N({\overline {0}},N_{0}{\overline {\overline {R}}})$

döntés - kvadr. optimalizálás

$\displaystyle \min _{{\overline {y}}\in \{1,-1\}^{M}}{\overline {y}}^{T}{\overline {\overline {R}}}{\overline {y}}-2{\overline {x}}^{T}{\overline {y}}$

• komplexitás $O(2^{M})$ - diszkrét tér miatt

Viterbi algoritmus

komplexitása

$O(V2^{k\cdot L})$

• $V=hossz/k$, tehát ennyi lépésben történik a kódolás
• mellesleg O($n\in R$)=O(1)

-- Zsolti - 2007.06.17.

Megbízhatóság alapú döntés

A döntés azt is figyelembe veszi, hogy az érték milyen "mélyen" van a döntési tartományban. Hogyha a döntési tartományok határától távoli az érték, akkor nagyobb valószínűséggel vette fel az elküldött vektor adott eleme az értéket, mintha a határ közelében lenne. Ennek az az oka, hogy az elemek alapból meghatározott értékeket vehetnek fel, majd AWGN zaj hatására veszik fel végleges értéküket.Ahhoz, hogy az érték átkerüljön a másik tartományba, a zaj értékének nagynak kell lennie, és mivel ez 0 várható értékű normális eloszlású vv.,ezért ennek kisebb a valószínűsége.

$P(X|c=t)\sim \displaystyle {\frac {1}{\sqrt {2\pi N_{0}}}}e^{-\left(\displaystyle {\frac {(X+t)^{2}}{2N_{0}}}\right)}$

• azonban a döntéshez a konstans szorzókat le lehet hagyni
• $\sim e^{-(X+t)^{2}}$ alapján össze lehet hasonlítani a valószínűségeket
• a döntés arra az értékre történik, aminek legnagyobb a valószínűsége

Shiftregiszter műveletekre

Ez a módszer tervezzünk szorzást végző shiftregiszteres architektúrát $GF(2^{N})$ felett jellegű feladatoknál kerülhet elő.

• Egy olyan rendszert készítünk, ami 1 lépésben előállítja a kívánt eredményt.
• A művelet egy meghatározott (bevasalt) elem, és egy változó elem között kerül végrehajtásra
• A shiftregiszterben a változó érték paramétereinek tárolásához N regiszter kell. ($GF(2^{N})$ miatt-a vektorok ilyen hosszúak)
• A regiszterekben a változó elem polinom reprezentációjának együtthatói vannak.
• Előre kiszámoljuk az elvégzendő művelet eredményét (polinom reprezentáció), majd ez alapján határozzuk meg az összeköttetéseket.
• A művelet elvégzését követően egy kifejezést kapunk, melyben a változó vektor együtthatói, és a polinom változójának hatványai vannak. Az elemeket a polinom változó alapján csoportosítjuk. Az összeköttetések abból adódnak, hogy az egyes hatványokhoz milyen együttható tartozik. Az együttható tagjainak összegét kell az eredetileg az adott polinomváltozó-hatvány együtthatóját tartalmazó regiszter bemenetére kötni.

Jelfeldolgozás rész

Nyquist feltétel

$\displaystyle \sum _{m}H\left(f+{\frac {m}{T}}\right)=1~~~~,ha~~~~|f|\leq \displaystyle {\frac {1}{2T}}$

• ha a feltétel teljesül nincs szimbólumközti áthallás

-- MadayPeter - 2007.06.08.