Kiskoza: /* Singleton-korlát */

2014-04-17T09:07:57Z

Singleton-korlát

← Régebbi változat		A lap 2014. április 17., 11:07-kori változata
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==

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|KodElmKepletek}} TOC ==Singleton-korlát== $M\leq q^{n-d_{min}+1}$ * $q$ a kódábécé elemszáma (bináris e…”

2012-10-21T20:01:36Z

Ú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…”

Új lap

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

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

-- [[MadayPeterTamas|MadayPeter]] - 2007.06.08.

[[Category:Infoalap]]

Algebrai rész - Laptörténet

Kiskoza: /* Singleton-korlát */

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|KodElmKepletek}} __TOC__ ==Singleton-korlát== M\leq q^{n-d_{min}+1} * q a kódábécé elemszáma (bináris e…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|KodElmKepletek}} TOC ==Singleton-korlát== $M\leq q^{n-d_{min}+1}$ * $q$ a kódábécé elemszáma (bináris e…”