„Algebrai rész” változatai közötti eltérés
(vitalap) (Új oldal, tartalma: „{{GlobalTemplate|Infoalap|KodElmKepletek}} __TOC__ ==Singleton-korlát== <math> M\leq q^{n-d_{min}+1}</math> * <math>q</math> a kódábécé elemszáma (bináris e…”) |
|||
13. sor: | 13. sor: | ||
* ha = áll fenn, akkor a kód MDS tulajdonságú, ekkor <math>d_{min}= n-k+1</math> (pl.: Reed-Solomon kódok) | * ha = áll fenn, akkor a kód MDS tulajdonságú, ekkor <math>d_{min}= n-k+1</math> (pl.: Reed-Solomon kódok) | ||
+ | |||
==Hamming-korlát== | ==Hamming-korlát== | ||
A lap jelenlegi, 2014. április 17., 09:07-kori változata
Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.
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
Tartalomjegyzék
Singleton-korlát
[math] M\leq q^{n-d_{min}+1}[/math]
- [math]q[/math] a kódábécé elemszáma (bináris esetben [math]q=2[/math])
- [math]M[/math] a kódszavak száma
- [math]d_{min}[/math] a minimális Hamming távolság
- n a kódszavak hossza
- ha = áll fenn, akkor a kód MDS tulajdonságú, ekkor [math]d_{min}= n-k+1[/math] (pl.: Reed-Solomon kódok)
Hamming-korlát
[math]\displaystyle\sum_{i=0}^t \binom{n}{i} (q-1)^i\leq q^{n-k}[/math]
- a kód [math]t[/math] hibát tud javítani
- [math]q[/math] a kódábécé elemszáma (bináris esetben [math]q=2[/math])
- [math]k[/math] az üzenetek hossza
- [math]n[/math] 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: [math]\displaystyle\sum_{i=0}^t \binom{n}{i} \leq q^{n-k}[/math]
- bináris, egy hibát javító Hamming-kód esetében a kód perfekt, ha [math]1+n= 2^{n-k}[/math]
Kódtervezés komplexitása
Off-line komplexitás
[math]O\left( \displaystyle\binom{2^n}{2^k}\binom{2^k}{2}\right)[/math]
On-line komplexitás
[math]O\left( 2^k\right)[/math]
Random coding
paraméterek: [math]n=q^t-1 ~~~~~k=t[/math]
- q a kódábécé elemszáma
- t a shiftregiszter hossza
[math]d_{min}=q^{t-1}[/math]
Reed-Solomon kódok spektrális tulajdonságai
Fourier-transzformáció
def.
[math]GF(q)=GF(p^m)[/math], ahol [math]p[/math] prim
[math]C_j=\displaystyle\sum_{i=0}^{n-1}\alpha^{ij}c_i[/math] , ahol
- [math]\alpha[/math] 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 [math]c\in\left[GF(q)\right]^n[/math] vektort képezi le egy [math]C\in\left[GF(q)\right]^n[/math] vektorra
Inverz transzformáció
[math]c_i=f(n)\displaystyle\sum_{j=0}^{n-1}\alpha^{-ij}C_j,~~~~~i=0,1,\dots n-1[/math]
- [math]f(n)=\left(n \mod p\right)^{-1}[/math], ahol a -1-edik hatvány a GF(p) beli multiplikatív inverz
Konvolúciós tétel
Ha az [math]e,f,g\in\left[GF(q)\right]^n[/math] vektorokra teljesül [math]e_i=f_i g_1, ~~~~ i=0,1,\dots,n-1 ~~~~~,~~akkor[/math] [math]E_j=f(n)~\displaystyle\sum_{k=0}^{n-1}F_{(j-k) mod~n}G_k[/math]
- az [math]E_j[/math] ebben az esetben [math]F[/math], és [math]G[/math] ciklikus konvolúciója
Bithibavalószínűség
[math]P_b=\Phi\left(-\sqrt{SNR}\right)[/math] , ahol
- [math]\Phi[/math] a standard normális eloszlásfüggvény
- [math]SNR[/math] a jel-zaj viszony (Signal to Noise Ratio)
BSC
[math]SNR_{BSC}=\displaystyle\frac{1}{N_0}[/math]
CSMA/CD ortogonális kódok
[math]SNR_{OC}=\displaystyle\frac{1}{\displaystyle\frac{N_0}{T_S}}[/math]
- [math]T_S[/math] a signature time, azaz a kommunikáció során használatos jeltartási idő
CSMA/CD Random Coding
[math]SNR_{RC}=\displaystyle\frac{1}{N_0 + \frac{M-1}{N}}[/math]
- [math]N_0 \geq 0[/math] az AWGN(additiv Gaussian White Noise) szórása a csatornán, avagy a zajteljesítmény
- [math]N=\displaystyle\frac{T_s}{T_c}[/math] a szimbóluim- és a chipidő hányadosa
- [math]M[/math] a felhasználók száma
Konvolúciós kódok komplex ábécé felett
[math]P_e \geq N_d \Phi\left(-\displaystyle\frac{d}{2\sigma} \right)[/math]
- [math]P_e[/math] a hibás kódszóra való döntés valószínűsége
- [math]\sigma[/math] a gaussi zajmint szórása
- [math]N_d[/math] a zérus kódszótól d minimális euklideszi távolságra lévő kódszavak száma
[math]G=20\log_{10}\displaystyle\frac{d_{free}}{d_{ref}} ~~~~~[dB][/math]
- [math]d_{ref}[/math] a kódolatlan esetben adódó minimális euklideszi távolság
- [math]d_{free}[/math](=[math]d_\infty[/math]) a szabad távolság
- [math]d_{free}=\displaystyle\max_rd_r^*[/math]
Viterbi-dekódolás bithibaaránya diszkrét emlékezetnélküli csatornán
[math] P_b\leq\displaystyle\frac{\partial T(D,I)}{\partial I}[/math]
- [math]T(D,I)=\displaystyle\sum_{i=1}^{\infty}\sum_{d=1}^{\infty}a(d,i)I^iD^d[/math]
- itt [math]I=1,D=e^{-\frac{1}{2N_0}}[/math]
CDMA/FH
felhasználók száma
[math]M\sim O\left(N^2\right)[/math]
- [math]M[/math] felhasználószám
- [math]N[/math] frekvenciák száma ( a szórókód mtx [math]N x N[/math]-es )
CDMA/DS
Az [math]\overline{\overline R}[/math] mtx
[math]\overline{\overline R}_{ij}=\displaystyle\frac{1}{N}~\overline C{i}~{\overline C{j}}^T[/math]
- [math]N[/math] a felhasználószám
- [math]\overline C_i[/math] az i. szórókód vektor
vett vektor
[math]\overline x = \overline{\overline R} \overline y+ \overline \nu \sim N(\overline{\overline R} ~\overline y,N_0\overline{\overline R}) [/math]
- [math]\overline{\overline R}[/math] kovarianciamátrix
- az AWGN [math]N(\overline 0, N_0\overline{\overline R} )[/math]
döntés - kvadr. optimalizálás
[math]\displaystyle\min_{\overline y \in \{1,-1\}^M} {\overline y}^T\overline{\overline R} \overline y - 2 {\overline x}^T \overline y [/math]
- komplexitás [math]O(2^M)[/math] - diszkrét tér miatt
Viterbi algoritmus
komplexitása
[math]O(V2^{k \cdot L})[/math]
- [math]V=hossz/k[/math], tehát ennyi lépésben történik a kódolás
- mellesleg O([math]n\in R[/math])=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.
[math] P(X|c=t)\sim\displaystyle\frac{1}{\sqrt{2\pi N_0}}e^{-\left(\displaystyle\frac{(X+t)^2}{2 N_0}\right)}[/math]
- azonban a döntéshez a konstans szorzókat le lehet hagyni
- [math]\sim e^{-(X+t)^2}[/math] 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 [math]GF(2^N)[/math] 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. ([math]GF(2^N)[/math] 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
[math]\displaystyle\sum_{m}H\left(f+\frac{m}{T}\right)=1~~~~,ha ~~~~|f|\leq\displaystyle\frac{1}{2T}[/math]
- ha a feltétel teljesül nincs szimbólumközti áthallás
-- MadayPeter - 2007.06.08.