LOGO. Kvantum-tömörítés. Gyöngyösi László BME Villamosmérnöki és Informatikai Kar

LOGO

Kvantum-tömörítés Gyöngyösi László BME Villamosmérnöki és Informatikai Kar

Információelméleti alapok összefoglalása

A kódolási eljárás Az információ átadás hűsége és gazdaságossága a kódolástól függ Az információ átadási folyamat legfontosabb problémája a kódolás és dekódolás művelete    

Forrás-ABC Közlemény Kód-ABC (Csatorna-ABC) Kódközlemény

A forrás által szolgáltatott információ az úgynevezett forrás-ABC betűinek egymásután írásával adódó sorozatok formájában jelenik meg. Ezeket közleményeknek nevezzük. A csatornán a csatorna-ABC jeliből alkotott különböző hosszúságú sorozatok formájában lehet információt átvinni. Ezeket a sorozatokat nevezzük kódközleménynek.

Jelkészlet Az előállítható kódféleségek számát meghatározza:

Általánosságban:

 A kód-ABC jeleinek száma  A kód hossza

A kód-ABC és meghatározott hosszúságú jelsorozat mellett továbbítható kód féleségek számát jelkészletnek nevezzük. Az (m) jelű kód-ABC esetén milyen hosszúságú (n) jelsorozatot kell a csatornán továbbítani, hogy a rendszer minden lehetséges állapotát kifejezhessük ? V = mn, logmV=nlogmm, n=logmV/logmm, azaz n=logmV.

V = mn, ahol V - jelkészlet m - a kód-ABC jeleinek száma n - a kód hossza Ha a kód-ABC bináris, akkor a jelkészlet: Bitek száma 1 2 3

Jelkészlet 2=2 2x2=4 2x2x2=8

Jelkészlet Legyen df az adott kódrendszerben előforduló forrásABC jelek száma. Bináris csatorna esetén: nsz = log2 df [ bit ], ahol  nsz - a szükséges bitek száma  df - a forrás-ABC jeleinek száma.

Egy jel átlagos információ tartalma így: I= nsz /n= log2 df /n = (1/n) log2 df [bit/bit], ahol:  n - a kód tényleges hossza  df - a forrás-ABC jeleinek száma

Entrópia Valós rendszerekben az egyes szimbólumok előfordulási valószínűsége általában nem azonos, így információ tartalmuk sem azonos. Az információ tartalom és az előfordulás valószínűsége fordított arányban van egymással. Az egyes szimbólumok pi valószínűséggel jelennek meg, ahol: di

p i 1

i

 1.

Az átlagos információ tartalom (az entrópia) di

H   pi log2 pi i 1

bit / jel .

Az entrópia a rendszerben lévő határozatlanság (rendezetlenség) mértéke. Maximális értékét akkor veszi fel, ha minden állapot bekövetkezési valószínűsége azonos, vagyis ha pi=1/df.

Entrópia A df jelű forrás-ABC kódolásához szükséges kód-ABC jelek száma: di

di

1 1 H   pi log2 pi =   log2  df i 1 i 1 d f  1 1 1  log2    log2    log2 d d df  f f  d 1 1   f log2   log2   log2 p  log2 df . df df df 1  df

Ekkor minden állapot bekövetkezési valószínűsége azonos, így pi=1/df.

Az entrópia a valós rendszerekben előforduló szimbólumok átlagos információ tartalma. Az entrópia negatív értéket nem vehet fel. A kétállapotú rendszer entrópia változása a valószínűség függvényében:

Entrópia Az ai szimbólumok megjelenésének valószínűsége pi



a1

a2

p

p1

p2 

Pr( X  ak )  pk

 ak pk

 aK 

pK

p ( x )  Pr( X  x )

Példa:

 a b c d Pr 1 / 2 1 / 4 1 / 8 1 / 8

Entrópia 

a1

a2

p

p1

p2 

Pr( X  ak )  pk

 ak pk

 aK 

pK

p ( x )  Pr( X  x )

Meghatározása:

H ( X )   pk log pk    p ( x ) log p ( x ) k

x

Példa: Az egyes szimbólumok megjelenésének valószínűségei legyenek:

 a b c d Pr 1 / 2 1 / 4 1 / 8 1 / 8

H ( X )   pk log pk    p ( x ) log p ( x ) k

x

1 1 1 1 1 1 1 1 7 H ( X )   log  log  log  log  2 2 4 4 8 8 8 8 4

Entrópia 

a1

a2

p

p1

p2 

 ak

Pr( X  ak )  pk

pk

 aK 

pK

p ( x )  Pr( X  x )

H ( X )    pk log pk    p ( x) log p ( x ) x

k

H ( p )  E[  log p ( X )] ahol

E[ f ( X )]   f ( x) p ( x) x

Entrópia Példa



a b c d Pr 1/ 2 1/ 4 1/ 8 1/ 8  log p 1 2 3 3 H ( p )  E[  log p ( X )] 1 1 1 1 7 H ( X )  1   2   3   3  2 4 8 8 4

Entrópia Az X egyenletes eloszlásra :

X ~ Unif [ A]

Az A halmaz elemszáma | A | Az egyes valószínűségek ekkor azonosak:

H ( X )  E[  log p ( X )]  E[  log(1 / | A |)]  log | A | Hogyan változik az entrópia, ha az eloszlás nem egyenletes?

X 1 , X 2 ,..., X n ~ p ( x)

Egymástól függetlenül

p ( X 1 , X 2 ,..., X n )  p ( X 1 ) p ( X 2 )... p ( X n ) Mennyire

véletlenszerű?

A véletlenszerűség is állandó!

Entrópia p ( X 1 , X 2 ,..., X n )  p ( X 1 ) p ( X 2 )... p ( X n ) 1 1 n log p ( X 1 ,..., X n )   log p ( X i )  E[log p ( X )]   H ( p ) n n i 1 Mivel,

H ( p )  E[  log p ( X )]

1 n f ( X i )  E[ f ( X )]   f ( x ) p ( x )  n i 1 x Innen:

Entrópia 1 log p( X1,..., X n )  H ( p ) n log p( X1,..., X n )  nH ( p ) p( X1,..., X n )  2 nH ( p ) , ahol

H ( p )  E[  log p( X )], továbbá E[f ( X )]   f ( x )p( x ). x

Így:

p( X1,..., X n )  2

 nH ( p )

.

X ~ Unif[ A] esetén p ( X )  1 / | A | konstans, így ( X 1 ,..., X n ) ~ Unif[ A] esetében

| A | 2 nH ( p )

Tipikus sorozatok Egy információforrás blokkjainak létezik egy közel 1 valószínűségű halmaza úgy, hogy ezeknek a blokkoknak a valószínűsége közel egyforma. Ezen blokkokat hívjuk tipikus sorozatoknak.

2 n ( H ( p ) )  p( x1, x2 ,..., xn )  2 n ( H ( p ) ) , ahol p( x1, x2 ,..., xn ) : a forrásbetűnkénti gyakoriság

 : tetszőleges pozitív szám, n:üzenet hossza H  p  : a p sorozat entrópiája.

Tipikus sorozatok X ~ Unif[ A]

esetén

p( X )  1 / | A |

konstans,

Ha n elegendően nagy és e kicsi, akkor az e-tipikus sorozatok száma

( X 1 ,..., X n ) ~ Unif[ A] egyenletes eloszlás mellett:

| A | 2

nH ( p )

Az X1..Xn, n hosszúságú p sorozat valószínűsége pedig:

p ( X 1 ,..., X n )  2

 nH ( p )

Tipikus halmaz 

a1

a2

p

p1

p2 

 ak pk

 aK 

pK

p ( X 1 ,..., X n )  2  nH ( p )

( X 1 ,..., X n ) ~ Unif[ A] , ahol | A | 2

n

A tipikus halmaz megadása:

An,  

n

nH ( p )

A n ,

Tipikus halmaz p ( X 1 ,..., X n )  2  nH ( p )

( X 1 ,..., X n ) ~ Unif[ A]

An ,

:

Olyan

2

, ahol

| A | 2 nH ( p )

( x1 , x 2 ,..., x n )   n sorozatok halmaza,

 n ( H ( p )  )

 p ( x1 , x 2 ,..., x n )  2

amelyre:

 n ( H ( p )  )

n n ( H ( p )  ) n ( H ( p ) ) 1   2  | A |  2   n,

A n ,

Példa: Pénzfeldobás

Pénzfeldobás  {Fej, Írás} Dobjunk fel egy pénzérmét kétszer egymás után:  {FF, FÍ, ÍF, ÍÍ} …… n Dobjunk fel egy pénzérmét alkalommal n  2 lehetséges kimenetel. Az entrópiát a feldobások számával adhatjuk meg.

Példa: Pénzfeldobás Példa a

b

c

d

Pr 1/ 4 1/ 4 1/ 4 1/ 4 ki HH HT TH TT Az érmefeldobás lehetséges kimenetelei, illetve a kimenetek valószínűségei kétszeri feldobásra

Példa: Pénzfeldobás 

a1

a2

p

p1

p2 

 ak

 aK 

pk

n

pK

A n ,

p ( X 1 ,..., X n )  2  nH ( p )

( X 1 ,..., X n ) ~ Unif[ A]

, ahol

| A | 2

nH ( p )

( X 1 ,..., X n )

:

hossza

nH ( p ) „feldobás”

X ~ p( x)

:

hossza

H ( p ) „feldobás”

Kódolás Példa A a b c d Pr 1/ 4 1/ 4 1/ 4 1/ 4 kód 11 10 01 00

hossz  2  log 4   log(1/ 4 )

Kódolás 

a1

a2

p

p1

p2 

 ak pk

 aK 

n

pK

A n ,

p ( X 1 ,..., X n )  2  nH ( p )

( X 1 ,..., X n ) ~ Unif[ A], ahol

| A | 2

nH ( p )

Hány bit szükséges az A halmaz elemeinek kódolásához?

nH ( p )

bit

Tipikus sorozatok: példa Legyen n=20, az üzenetsorozatok:

A 0 előfordulásának valószínűsége legyen P(X=0)=3/4. Az 1 előfordulásának valószínűsége legyen P(Y=1)=1/4. A fenti sorozatok megjelenésének valószínűségei: 1. (1/4)20 2. (3/4)14(1/4)6 3. (3/4)20  Legnagyobb valószínűség ehhez tartozik. Azonban ezen sorozat nem jellemzi a 0 és 1 statisztikai tulajdonságait. A 2. sorozat azonban tipikus, hiszen megfelel 0 és 1 forráselemek megjelenési valószínűségeinek.

Tipikus sorozatok: példa Hogyan határozhatjuk meg a tipikus sorozatokat? Nagy számok törvénye: véletlen eseményt egymástól függetlenül sokszor megismételve, egy p valószínűségű elemi esemény relatív gyakorisága nagy valószínűséggel a p értékhez közelít Nézzük a 0-k megjelenési statisztikáit az egyes sorozatokban: 1. 0/20 << ¾ 2. 14/20 ≈ ¾  a legtipikusabb sorozat 3. 20/20 >> ¾. Az E-tipikus sorozatokra

2

 n ( H ( p ) )

 p( x1, x2 ,..., xn )  2

 n ( H ( p )  )

.

Tipikus sorozatok: példa Az előző három sorozat E-tipikusságának vizsgálata során tegyük fel, hogy E=1/3. Az E-tipikusságra vonatkozó egyenlőtlenség alapján:

2 n ( H ( p ) )  p( x1, x2 ,..., xn )  2 n ( H ( p ) ). Legyen   1/ 3.  1    2n ( H ( p ) ) | An, | 2n ( H ( p ) ) 0 : 1    p0   p0 ( X n )   1    p0   2 / 3  3 / 4   n   p0 ( X n )  n   4 / 3  3 / 4   n = 10   p0 ( X n )   n  20. 1: 1    p1   p1( X n )   1    p1   2 / 3 1/ 4   n   p0 ( X n )   n   4 / 3 1/ 4   n = 4   p1 ( X n )   n  6.

Tipikus sorozatok: példa 1.sorozat : 0  k vizsgálata:

3.sorozat : 0  k vizsgálata:

0   10   p0 ( X n )   n  20.  20   1.sorozat : 1  esek vizsgálata:

20   n  20. 10   p0 ( X n )    20   3.sorozat : 1  esek vizsgálata:

20   4   p1( X n )   n  6.  20  

0   n  6. 4   p1( X n )   20  

2.sorozat : 0  k vizsgálata: 14   10   p0 ( X n )   n  20.  20   2.sorozat : 1  esek vizsgálata: 6   4   p1( X n )   n  6.  20  

Csak a második sorozatban teljesül az egyenlőtlenség! A sorozatok küzül így csak a második sorozat tipikus.

Láncszabály

p ( x, y )  p X ( x ) pY | X ( y | x )  pY ( y ) p X |Y ( x | y )

H ( X , Y )  H ( X )  H (Y | X ) n

H ( X 1 ,..., X n )   H ( X i | X i 1 ,..., X 1 ) i 1

Kölcsönös információ p ( x, y ) I ( X ; Y )   p ( x, y ) log p( x) p( y ) x, y p( X , Y ) I ( X ; Y )  D( p ( x, y ) | p ( x) p ( y ))  E[log ] p ( X ) p (Y )

I ( X ;Y )  H ( X )  H ( X | Y ) I ( X ; Y )  H ( X )  H (Y )  H ( X , Y )

Forráskódolás

01100010111001110010101110001…

A forrást a szimbólumok kimeneti valószínűségeikkel jellemezzük. Az egyes szimbólumok előfordulási valószínűsége egymástól független. Példa: Pénzfeldobás sorozat: p valószínűséggel fej, 1-p valószínűséggel írás.

A szimbólumok eloszlása ekkor p0,p1,…,pn.

Kvantum-adattömörítés

Adattömörítés abcde… n bit

nR bit tömörítés

abcde… kitömörítés

Cél: Azon legkisebb R meghatározása, amely esetén az eredeti üzenet még visszaállítható

Shannon: Az R értéke forrásentrópiánál nem lehet alacsonyabb: H  X   H  px    x px log  px .

Bináris entrópia Az entrópiafüggvény értékei nem-negatívak, értékeit a 0 és log  d  között veheti fel. A bináris entrópia:

H  p   H  p,1  p 

H  X   H  px    x px log  px 

0log0  0

Tipikus sorozatok A pénzfeldobás eredménye p valószínűséggel legyen FEJ, illetve ÍRÁS 1-p valószínűséggel. Így, n feldobást követően nagy valószínűséggel np FEJ, illetve n(1-p) ÍRÁS kimenetet számolhatunk össze. összes n üzenet

A kimenetek száma  hibavalószínűséggel közelíthető azok tipikus sorozataival: Tipikus sorozatok: np 1     FEJ kimenetek száma  np 1   

n 1  p 1     ÍRÁS kimenetek száma  n 1  p 1   

Tipikus sorozatok p

np 1  

1  p  

n 1 p 1  

Pr  x   2

 Pr  x   p

np log p   n 1 p  log1 p 

2

1  p  

n 1 p 1  

 nH  p,1 p 

A tipikus sorozatok száma  2 összes n üzenet

np 1  

nH  p,1 p 

A tipikus sorozatok előfordulási valószínűsége 1- hez tart .

A kimenetek száma  hibavalószínűséggel közelíthető azok tipikus sorozataival: Tipikus sorozatok: np 1     FEJ kimenetek száma  np 1   

n 1  p 1     ÍRÁS kimenetek száma  n 1  p 1   

Tipikus sorozatok tömörítése Foglaljuk indexelt listába az összes lehetséges 2

nH  p,1 p 

tipikus sorozatot:

A forrás kimenete legyen Y Ha Y nem tipikus sorozat, akkor küldjünk egy 0 bitet, majd a teljes Y üzenetet. Összesen  n+1 bit.

1. 2. 3. 4.

x1 x2 x3 x4 …

Ha az üzenet tipikus, küldjünk egy 1-est, majd az Y üzenethez tartozó sorszám értékét a táblázatból. Összesen:  nH ( p,1  p )  1 bit

Azaz, átlagosan csak H(p,1-p) bit szükséges egy tömörített üzenet elküldéséhez.

Tipikus sorozatok tömörítése A táblázatos tömörítési módszerrel nagyméretű üzenetek esetén a kimenetek változó hosszúságúak. A kimenetek átlagos mérete azonban megfelel a Shannon entrópiának. Az algoritmussal az üzenetek kitömörítése hibátlanul végrehajtható. Azonban a kisebb üzeneteket milyen algoritmussal tömöríthetjük? Megoldás: Rögzített hosszúságú tömörítés

A forrás kimenete legyen Y. Ha Y nem tipikus, akkor  nH  p,1  p   1 darab 0-t küldünk. Összesen:  nH ( p,1  p )  1 bit Ha az üzenet tipikus, egy 1-est, valamint az Y üzenet táblázatbeli indexének értékét küldjük. Összesen:  nH ( p,1  p )  1 bit

A rögzített hosszúság miatt lesznek hibák,azonban a hibák száma elhanyagolható.

Miért nem érhető el az Shannon-korlát alatti tömörítés? Legyen R  H  p,1  p  Ekkor rögzített hosszúság esetén legfeljebb 2nR sorozat n R  H  p,1 p    0. tömöríthető hibamentesen, így Pr  2 

Atipikus sorozatok

Pr  0 Pr  2nR  2

Tipikus sorozatok

 nH  p,1 p 

n R  H  p,1 p   2 

Kvantum-tömörítés

A kvantum-információforrás A klasszikus értelmezésű “pénzfeldobás”: 1 valószínűséggel 0 kimenet, 2 1 valószínűséggel 1 kimenet. 2

A “kvantum-pénfeldobás” 1 valószínűséggel 0 kimenet, 2 1 1 valószínűséggel 0  1  kimenet.  2 2

Általánosan: A kvantum-információforrás a  j kimeneti kvantumállapotot állítja elő, p j valószínűséggel.

Kvantum adattömörítés j

1

j

2

j

tömörítés

visszaállítás

3

j

J

0

4

j

0

5

F   pJ F   J , J 

J   j1,..., j n 

J

pJ  p j1  ...  p jn

 J   j ...  j 1

(ahol F  n

F 1

 J J  J .)

Mi az elérhető legjobb kvantum-tömörítés? “Klasszikus pénzfeldobás” 1 valószínűséggel 0 kimenet, 2 1 valószínűséggel 1 kimenet. 2

“Kvantum pénzfeldobás” 1 valószínűséggel 0 kimenet, 2 1 1 valószínűséggel 0  1  kimenet.  2 2

 1 Azaz: H    1. 2  1 H    1? 2  1  1/ 2  H   0.6.  2  

A Shannon-féle H  p j  korlátnál jobb eredmény!

A kvantum entrópia Legyen adott az    p j  j  j sűrűségmátrix. j

A sajátértékeket tartalmazó diagonális mátrix segítségével megadhatjuk a  sűrűségmátrix spektrális felbotását is:

   k ek ek (   tr   log   ). k

Neumann entrópia: S     H  k    k log k . k

Shumacher zajmentes csatornakódolási tétele: Az R tömörítés aránya nem lehet kisebb az S    Neumann-entrópia értékénél.

Neumann entrópia tulajdonságai S     H  k  ,ahol k a  sajátértékei 0  S     log  d 

A



B

S   A  B   S   A   S  B  .

AB Szub-additivitás: S   AB   S   A   S  B  .

A tipikus halmaz Példa:   p 0 0  1  p  1 1 , S     H  p  .

Atipikus sorozatok Tipikus sorozatok: x1,..., x2nS  

A tipikus részhalmaz: x1 ,..., x2nS   , P   x j j

xj .

A Schumacher-féle adattömörítés Az  j állapot bemérése. Az állapot eleme a P tipikus részhalmaznak? P, Q  I  P

P x j  j 0 ... 0

Q Küldés: 0

 nS   

.

Küldés: j . Kiegészítés 0 -val: j 0 ... 0 . Inverz transzformáció: j 0 ... 0  x j .

Cél: F  1.

Klasszikus és kvantumfüggvények különbsége

x

x 0

2

klasszikus f

f (x )

x

kvantum Uf

f x 

Hogyan állapítható meg az állapotról annak típusa? x

x 0

klasszikus áram kör

UT

 0 ha x tipikus T (x )   1 h a x atipikus

x T  x  Mé rés.

Az első regiszter állapotának alakulása a mérés után:

 P  valószínűséggel:    Q  valószínűséggel:  

P

 P Q  Q

.

Az unitér x j  j 0 ... 0 transzformáció végrehajtása

xj

xj

0

3

klasszikus táblázat

kvantum táblázat

j

j

klasszikus inverz

xj

táblázat

xj

inverz

xj  xj  0

kvantum táblázat j

j

n

Az unitér x j  j 0 ... 0 transzformáció végrehajtása

Az állapot tömörítése, egyszerűsített jelölésmóddal:

xj

j

U 0

0

A Schumacher-féle adattömörítés Az  j állapot bemérése. Az állapot eleme a P tipikus részhalmaznak? P, Q  I  P

P x j  j 0 ... 0

Q Küldés: 0

 nS   

.

Küldés: j . Kiegészítés 0 -val: j 0 ... 0 . Inverz transzformáció: j 0 ... 0  x j .

Cél: F  1.

A Schumacher-féle tömörítés Tipikus/atipikus állapot?

j

0

UT

Tömörítés, továbbítás

U

0 0

Dekódolás

U

mérés: 0

Ha az  J állapot tipikus, az első regiszter tartalma

 J P  J valószínűséggel

P J

J P J

lesz.

†

A  J visszaállíthatósága FJ  F   J ,  J   A J sűrűségmátrixra:

 J J  J

 J P  J valószínűséggel

P J

J P J

,

 J Q  J valószínűséggel hibás . J   J P  J

P J J P

J P J

J P J

  J Q  J hibás hibás

 P  J  J P   J Q  J hibás hibás .

FJ 

J P J J P J  J P J

Cél : F  1 F   pJ F   J , J    pJ  J P  J J

  pJ tr  P  J  J J

Azonban

Legyen

p

J

J J



J

n      ...   .

J

  p0 0 0  p1 1 1 ;

p0  p; p1  1  p.

  n   y py y y

P   x tipikus x x

Ekkor





F  tr P   n   x tipikus, y py tr  x x y y   x tipikus, y py  xy   x tipikus px  1.



LOGO

Köszönöm a figyelmet! Gyöngyösi László BME Villamosmérnöki és Informatikai Kar