sayısal iletişim ders notları

Communication Theory
ENFORMASYON TEORİSİ
KODLAMA
Doç. Dr. Hakan Doğan
ENFORMASYON DEYİMİ NEDEN KULLANILMIŞ?

Kaynaklarn, kanalların ,alıcıların bilgi karakteristiklerini incelemek.

Bilginin iletimini optimize etmek için

İletimin güvenirliliğinin düzeltilmesi
Farzedelim X şehirinden Y şehirine günlük hava tahmini veriliyor ve havanın
güneşli, bulutlu ,yağmurlu ,sisli olabileceğini farzedelim . Her hava belirteci bir
kaynak sembolu olarak kodlansın. Yani bir Kaynak kodlamayıcımız olsun. “source
koding” günlük hava raporu verilsin. Rapor dizisinede mesaj denir “message”
Bilgi tanımı : Alıcı gönderilen bilgiyi aldığında onun hakkında ki kalkan belirsizlik
miktarına denir.
Hava sembolu
İhtimal
Güneşli
Bulutlu
Yagmurlu
Sisli
0.65
0.20
0.10
0.05
Tablodan görüleceği üzere X şehrinin güneşli bir havası var ve biz A şehri güneşli
dediğimizde az bir bilgi vermiş oluruz diğer taraftan sisli dediğimizde bu şaşırtıcı olur
yani oldukça büyük bir bilgidir.
Örnek mesaj : güneşli ,güneşli ,güneşli ,bulutlu ,bulutlu ,yagmurlu
Tablo 1
Hava Sembolü
Güneşli
Bulutlu
Yagmurlu
Sisli
Tablo 2
Hava Sembolü
Güneşli
Bulutlu
Yagmurlu
Sisli
Kod
00
01
10
11
Kod
0
10
110
111
Mesaj’ın yukardaki şekle göre kodlaması
Tablo 1 ‘e göre
Tablo 2 ‘e göre
00 00 00 01 01 10
0 0 0 10 10 110
= 12 bit
= 10 bit
Sonuç ve yorum : daha kısa bir mesaj iletiminde kaynak kodlayıcı ihtimali yüksek
olan mesajı daha bir kod uzunluğuyla kodlar. Bu bir biçimde de şıkıştırma algoritması
olarak düşünülebilir.
Mesajın olasılığı


Kod sözcüğünün uzunluğu
Kod sözcüğünde ihtimali büyük olan mesajın kaybedilebilmesi göz önüne
alınıyor.
Kod sözcüğünün küçük olması kadar kod sözcükleri arasındaki farkında
büyük olması gerekmektedir.
000 111
001 şeklindeki gibi
Bilgi kaynakları hafızalı ve hafızasız olarak ikiye ayrılır. Hafızalı bir kaynakta
mevcut çıkış sembolü önceki sembole bağlıyken, hafızasız bir kaynakta herbir çıkış
önceki sembollerden bağımsız olarak iletilir.
Ayrık hafızasız kaynak için bigi içeriği (Information content of a Discrete
Memoryless Source (DMS))
Bir olaydaki bilgi içeriği olayın belirsizliği ile yakından ilgilidir. Bilgi içeriğine
literatürde kendi bilgisi^de denir. (self information )
X ile gösterilen bir DMS için X’in alabileceği değerleri gösteren alfabe (alphabet),
x1 , x2 , xm  ve P( xi ) ’de xi ’nin gelme olasılığını göstermek üzere
I ( xi )  log b
ile gösterilir.
b  2  bit
b  10  Hartley veya Decit
b  e  nat (natural unit )
1
P( xi )
(1.1)
Haberleşmede b  2 durumunu kullanrak bilgi içeriğini bit cinsinden ifade ediyoruz.
In a log10 a

In 2 log10 2
Hatırlatma : log 2 a 
P(0) = 0.7
P(1) = 0.3
1.denkleme göre 0.51 bit
1.denkleme göre 1.74 bit
P( A  B)  P( A).P( B) istatiksel bağimsız iki olay için
A olayı açıklanınca I(A) birim belirsizlik ortadan kalkar.
B olayı açıklanınca I(B) birim belirsizlik ortadan kalkar.
Hem A hem B oluyorsa C  A  B bu olayın olaması durumunda I(C) birim belirsizlik
ortadan kalkar.
IC= IC + IB
0.51 bize sıfır ‘ı göndermek için 1 bitten daha az yarım bite ihtiyacımız var diyor
peki yarım bit varmı  tabiki yok bu bize bilginin etkili bir biçimde “efficient”
depolanabilmesi veya iletilebilmesini gösterir.
Bazı Özellikler:
P( xi )  1  I ( xi )  0
I ( xi )  0
P( xi )  P( x j )  I ( xi )  I ( x j )
Entropi (Ortalama Bilgi) : Pratik haberleşme sistemlerinde bilgi kaynağından iletilen
uzun bilgi sembol dizileri söz konusu olduğu için kaynağın ürettiği tekbir sembolün
bilgi içeriğinden daha çok kaynağın ortlama bilgi içeriğinden bahsedilir. X kaynağına
ait ortalama bilgi miktarı
m
H ( X )  E[ I ( xi )]   P( xi )I ( xi )
(1.2)
i 1
m
H ( X )   P( xi ) log 2 ( P( xi )) bit / symbol
(1.3)
i 1
Sonuç: Bir işaretin bilgi içeriği, o işareti tanımlamak için gerekli bit sayısına eşittir.
(kendi bilgi formulü ile bulunur.) Eğer mesaj dizisi içinse bu kavram artık entropi dir.
Örnek : X kaynağı 0 veya 1 üreten bir kaynak olmak üzere P(0)=0.5, P(1)=0.5 ise
H(X) nedir?
1
1 1
1
H ( X )   log 2  log 2  1 bit / symbol
2
2 2
2
(1.4)
Kaynağın entropisi H ( X ) , m alfabedeki toplam sembol sayısını göstermek üzere
0  H ( X )  log 2 m ile sınırlıdır.
Bilgi Hızı (Information Rate)
R  r H(X )
(1.5)
b/s
Örnek : 4 KHz lik bir bantsınırlı bir işaret (ses) Nyquist hızında örnekleniyor ve 64
düzeyli bir işaret haline getiriliyor yani kuantalanıyor. (quantization)
(A) örnekleme hızını (fs) ve örnekleme aralığını Ts bulunuz.
(B) Sembol hızını (r) bulunuz.
(C) Düzeylerin gönderilme olasılıkları eşit ise bilgi hızını bulunuz.
A- B= 4 KHz ; Fs= 2B = 8K Hz , Ts = 1/fs = 1/ 8000 = 1.25 e-4
B- Sembol hızı r =1/Ts = fs= 8000 sembol/sn = 8ksembol/sn
C- Bilgi içeriği H= log2 (64) = 6 bit/sembol (bit/aralık)
Bilgi hızı = r*H = 48 kbps.
AYRIK HAFIZASIZ KANAL (Discrete Memoryless Channel (DMC))
Kanala giriş ve çıkış değerleri belli bir alfabeden oluşan (ayrık) ve çıkış değerleri
sadece o andaki giriş değerine bağlıysa bu kanala DMC denir.
Bilgi kanalı , giriş alfabesi  x1 , x2 , xm  ve çıkış alfabesi  y1 , y2 , yn  şartlı
olasılıklar kümesi bütün m ve n ler için P( yj/ xi)’lerden oluşur. Burada P( yj/ xi), xi
sembolü gönderildiğinde çıkış sembolü yj nin gelme olasığını göstermektedir.
İhtimali etkileyen faktör iletişim ortamının yapısı ve gürültü .
P( yj/ xi) : Geçiş Olasılığı (Transition probability)
Kanal Matrisi
 P( y1 x1 ) P( y2 x1 )

P( y1 x2 ) P( y2 x2 )
P(Y X )  


 P( y1 xm ) P( y2 xm )
P ( yn x1 ) 

P( yn x2 ) 


P( yn xm ) 
(1.6)
Bütün i değerleri için
n
 P( y
j 1
j
xi )  1
(1.7)
 P11
P
 21
 P31
Notasyon farkı : P(yj/xi) = Pij
P12
P22
P32
P13 
P23  gibi
P33 
P11
a1
b1
a2
b2
a3
b3
İKİLİ SİMETRİK KANAL : “Binary symmetric channel ‘BSC’ ”
p
0
0
q
p
q

q
1
q
p 
1
p
İKİLİ SİLEN KANAL : “Binary erasure channel ‘BEC’ ”
p
0
0
q
p q
0 q

S
q
1
p
0
p 
1
Giriş olasılıkları P(X) ve çıkış olasılıkları P(Y)
[ P( X )]  [ P( x1 ), P( x2 ),
P( xm )]
[ P(Y )]  [ P( y1 ), P( y2 ),
P( yn )]
(1.8)
gibi satır matrisi ile gösterilirse,
[ P(Y )]  [ P( X )][ P(Y X )]
olarak yazılabilir.
(1.9)
Eğer P( X ) diaygonal matris olarak gösterilirse;
0
 P( x1 )
 0
P( x2 )
[ P( X )]d  


0
 0
0
0 
0 
0 

P( xm ) 
[ P( X , Y )]  [ P( X )]d [ P(Y X )]
Hatırlatma: P( A B) 
Örnek:
P( B A) P( A)
P( A, B)
P( A, B)
, P( B A) 
, P( A B) 
P( B)
P( A)
P( B)
(1.10)
(1.11)
Kanal için Etropi Hesaplamaları
H(X,Y) = Kanalın tümündeki ortalama belirsiklik miktarı ( Joint etropi )
H(X) = Kanalın girişindeki ortalama belirsizlik miktarı
H(Y) = Kanalın çıkışındaki ortalama belirsizlik miktarı
H(X/Y) = Kanalın çıkışı gözlendikten sonra kanal girişi hakkında kalan ortalama
belirsizlik miktarı.
H(Y/X) = X iletildiğinde kanalın çıkışındaki ortalama belirsizlik miktarı
H(X)
H(X/Y)
H(Y)
I(X,Y)
H(Y/X)
H(X,Y)
“Mutual Information”
I(X;Y) = H(X) – H(X/Y) = Kanalın çıkışı gözlemlendikten sonra kanal girişi
hakkındaki çözümlenen kısmı gösterir.
I(X;Y) = H(Y) – H(Y/X)
n
H (Y )   P( y j ) log 2 ( P( y j ))
(1.12)
j 1
m
H ( X )   P( xi ) log 2 ( P( xi ))
n
(1.13)
i 1
m
H ( X Y )   P( xi , y j ) log 2 ( P( xi y j ))
(1.14)
j 1 i 1
n
m
H (Y X )   P( xi , y j ) log 2 ( P( y j xi ))
(1.15)
j 1 i 1
n
m
H (Y , X )   P( xi , y j ) log 2 ( P( y j , xi ))
(1.16)
j 1 i 1
n
m
I ( X ; Y )   P( xi , y j ) log 2 (
j 1 i 1
P( xi y j )
P( xi )
)
(1.17)
KANAL KAPASİTESİ
C ile gösterilen bir kanalın “kanal sığası” iletebildiği maksimum ortalama
enformasyon miktarı olarak tanımlanır. DMC bir kanal için sembol başına kanal
kapasitesi
(1.18)
Cs  max( I ( X , Y ))
P ( xi )
Sayiyede r adet sembol gönderiliyorsa
C  rCs
b/s
Gürültüsüz kanal : Tüm giriş dağılımları için H(X/Y) = 0
gürültüsüzdür.
x1
y1
x2
y2
x3
y3
Buna göre gürültüsüz kanal için
Gürültülü kanal için
(1.19)
H(Y/X) = 0 ise kanal
1 0 0
0 1 0 


0 0 1
I(X,Y) = H(X)
I(X;Y) = H(X)- H(X/Y)
Kanal çıkışı gözlemlendikten sonra kanal girişindeki kalkan belirsizlik yoksa
I(X,Y) = 0
Toplamsal beyaz gürültülü kanal (AWGN : Additive White Gaussian Noise
Channel)
AWGN kanalda, X kanal girişi, n toplamsal band sınırlı beyaz sıfır ortalamalı  2
varyanslı gauss gürültüsü olmak üzere kanal çıkışı Y
Y  X n
Olarak yazılırsa bu kanalda örnek başına kapasite S/N sinyal gürültü oranını
göstermek üzere
(1.20)
Cs  max I  A;B  bit / sample
(1.21)
şeklinde yazılabilir. Kanalın bandgenişliği B Hz olarak sabitlenirse çıkışta bandsınırlı
olur ve Nyquist hızı 2B olacak şekilde örnekler alınırsa bu durumda kanal kapasitesi
C  2.B. Cs bit / sn
(1.22)
olur.

P 
C  B log 2  1 

N0B 

Örnek : 4 KHz bandgenişliğine sahip ve güç yoğunluk spektrumu  / 2  10 12 W / Hz
olan bir toplamsal beyaz gürültülü kanal için alıcıda alınması gerekli olan sinyalin
gücü 0.1 mW. Kanalın kapasitesini hesaplayınız.
B= 4000 Hz
P = 0.1 (10-3) W
N= N 0 B =2. 10-12 .4000 = 8. 10-9 W
SNR = 1.25 * 104
3.denkleme göre C= 54.44 * 103 b/s
R< C için iletim sağlanabilir. 33600 b/s model çalışabiir.
Shannon Teoremi :
C.E Shannon’a dek haberleşme teoricileri gürültülü bir kanal üzerinden enformasyon
iletimi işleminde yapılan hata olasılığı küçültmek için yegane yolun işaret/gürültü
oranının büyütülmesi ve/veya iletim hızının düşürülmesi gerektiğini
düşünmekteydiler. 1940 Shanon “gürültülü kodlama teoremi ” ile iletilmesi gereken
ortalama enformasyon miktarı R , C “kanal sığası” den küçük olduğu sürece uygun
kodlama tekniklerinden yararlanarak enformasyon iletim işleminin hatasız olarak
gerçekleşebileceğini göstermiştir.