Rastgele etkinlik alanı
1946'da Amerikalı istatistikçi John Tukey, BIT adını önerdi
Rasgele olayların bir alanını hayal edinher ikisi de bir kartal olan bir sahte jeton atmaktan ibarettir. Bir kartal ne zaman düşer? Her zaman açıktır. Bunu önceden biliyoruz, çünkü alanımız çok düzenli. Bir kartalın düşmesi güvenilir bir olaydır, yani olasılık 1'e eşittir. Düşmüş bir kartal hakkında söylersek çok bilgi verir miyiz? Hayır. Böyle bir mesajdaki bilgi miktarı, 0'a eşit sayılır.
Şimdi doğru parayı atalım: olması gerektiği gibi bir tarafında tura, diğer tarafında turaları var.Yazı tura gelmek, onu oluşturan iki farklı olay olacaktırTek bir atışın sonucunu bildirirsek, gerçekten de öyle olacaktırYeni Bilgi: Yazı 0 ve yazı 1 olarak bildirilecektir.Bu bilgiyi sağlayabilmemiz için sadece 1 bit'e ihtiyacımız var.
Etkinlik alanımızda belirsizlik ortaya çıktı ve yazı tura atmayanlara bu konuda söyleyecek bir şeyimiz varAncak mesajımızı doğru bir şekilde anlamak için tam olarak ne yaptığımızı, ne demek istediğimizi bilmesi gerekir0 ve 1.Etkinlik alanlarımız eşleşmelidir ve kod çözme işlemi, atma sonucunu geri yüklemek için benzersizdir.Verici ve alıcının olay uzayı çakışmaz veya çakışmazMesajın kesin olarak çözülme olasılığı, bilgi iletişim kanalında sadece gürültü olarak kalacaktır.
İki madeni para bağımsız olarak ve aynı anda atılırsa, eşit derecede olası farklı sonuçlar olacaktırBilgileri iletmek için 2 bite ihtiyacımız olacak ve mesajlarımız00, 01, 10 ve 11.İki kat daha fazla bilgi var.Böyle bir çift atışın sonucunu tahmin etmeye çalışırsak, hata yapma olasılığımız iki kat daha fazladır.
Bir olay alanının belirsizliği ne kadar büyükse, olay durumu iletisi o kadar fazla bilgi içerir.
Etkinlik alanımızı biraz karmaşıklaştıralım, şimdiye kadar meydana gelen tüm olaylar eşit derecede olasıydı.Ancak gerçek alanlarda, tüm olayların travmatik bir olasılığı yoktur.Diyelim ki gördüğümüz karganın siyah olma ihtimali 1'e yakın.Sokakta karşılaştığınız ilk yoldan geçenin bir erkek olma olasılığı yaklaşık 0,5'tir.Ancak Moskova sokaklarında bir timsahla tanışmak neredeyse inanılmaz.Sezgisel olarak, bir timsahla karşılaşma mesajınınKara kargadan çok daha fazla bilgi değeri.Bir olayın olasılığı ne kadar düşükse, böyle bir olay hakkındaki mesajda o kadar fazla bilgi bulunur.
Etkinlik alanı çok egzotik olmasın. Sadece pencerenin önünde durup geçen arabalara bakıyoruz. Dört renkli arabalar geçiyor, bunu bildirmemiz gerekiyor. Bunu yapmak için renkleri kodlayacağız: siyah - 00, beyaz - 01, kırmızı - 10, mavi - 11. Tam olarak hangi arabanın kullandığını bildirmek için sadece 2 bit bilgi aktarmamız gerekir.
Ama uzun zamandır arabaları seyrederken,Otomobillerin renginin eşit olmayan şekilde dağıldığını not ediyoruz: siyah -% 50 (her saniye), beyaz -% 25 (her dördüncü), kırmızı ve mavi -% 12,5 (her sekizinci) Sonra iletilen bilgileri optimize edebilirsiniz.
Çoğu siyah arabadır, bu yüzden siyahı gösterelim - 0 en kısa koddur ve diğerlerinin kodu 1 ile başlasın.Geri kalanın yarısı 10'da beyaz, kalan renkler 11'de başlar.Son olarak kırmızıyı 110, maviyi 111 olarak gösterelim.
Şimdi, arabanın rengi hakkında bilgi vererek, onu daha yakından kodlayabiliriz.
Shannon Entropy
Olay uzayımızın n farklı olaydan oluştuğunu varsayalım.Bir yazı iki yazı ile bir yazı atıldığında, tam olarak böyle bir olay vardır, bir doğru yazı tura atıldığında, iki yazı tura atıldığında 2veya araba gözlemi – 4.Her olay, meydana gelme olasılığına karşılık gelir.Bir madeni para iki yazı ile atıldığında, yalnızca bir olay vardır (yazı atma) ve olasılığı p1 = 1'dir.Doğru madalyonun altını çevirdiğinizde, iki olay vardır, bunlar eşit derecede olasıdır ve her birinin olasılığı 0.5'tir: p1 = 0.5, p2 = 0.5.İki doğru yazı tura atarsanız, dört olay vardır, hepsi eşit derecede olasıdır ve her birinin olasılığı 0.25'tir: p1 = 0.25, p2 = 0.25, p3 = 0.25, p4 = 0.25.Arabaları gözlemlerken dört olay vardır ve farklı olasılıkları vardır: siyah 0.5, beyaz 0.25, kırmızı 0.125, mavi 0.125: p1 = 0.5, p2 = 0.25, p3 = 0.125, p4 = 0.125.
Bu bir tesadüf değil.Shannon, üç koşulun yerine getirilmesi için entropiyi seçti (olay alanındaki belirsizlik ölçüsü):
- 1 olasılıklı geçerli bir olayın entropisi 0'dır.
- İki bağımsız olayın entropisi, bu olayların entropilerinin toplamına eşittir.
- Bütün olaylar eşit derecede muhtemel ise, entropi maksimumdur.
Tüm bu gereksinimler, etkinlik alanının belirsizliği hakkındaki fikirlerimizle oldukça tutarlıdır.Olaylar bağımsızsa, toplamın belirsizliği belirsizliklerin toplamına eşittir, basitçe toplanırlar (örnekVe son olarak, eğer tüm olaylar eşit derecede olasıysa, o zaman sistemin belirsizlik derecesi maksimumdur.İki yazı tura atılması durumunda olduğu gibi, dört olayın tümü eşit derecede olasıdır ve entropi 2'dir, bu da dört olayın olduğu arabalardan daha büyüktür, ancakBu durumda entropi 1.75'tir.
H miktarı bilgi, seçim ve belirsizliğin bir ölçüsü olarak bilgi teorisinde merkezi bir rol oynar.
Claude Shannon
Claude Elwood Shannon- Amerikalı mühendis, kriptanalist vematematikçi. "Bilgi çağının babası" olarak kabul edilir. Modern yüksek teknoloji iletişim sistemlerinde uygulama bulan bilgi teorisinin kurucusu. Şu anda modern iletişim teknolojilerinin temelini oluşturan temel kavramları, fikirleri ve bunların matematiksel formülasyonlarını sağladı.
1948'de "bit" kelimesini kullanmayı önerdiEn küçük bilgi birimini belirtmek için. Ayrıca, girdiği entropinin iletilen mesajdaki bilgilerin belirsizliğine eşdeğer olduğunu da göstermiştir. Shannon'un "Matematiksel İletişim Kuramı" ve "Gizli Sistemlerde İletişim Kuramı" makaleleri bilgi teorisi ve kriptografi için temel kabul edilir.
İkinci Dünya Savaşı sırasında Shannon, Bell Laboratuvarlarında kriptografik sistemler geliştirmek için çalıştı ve bu sistemler daha sonra hata düzelten kodlama yöntemlerini keşfetmesine yardımcı oldu.
Shannon, olasılık şemaları teorisine, oyun teorisine, otomata teorisine ve kontrol sistemi teorisine - sibernetik kavramının bir parçası olan bilim alanlarına önemli bir katkı yaptı.
kodlama
Ve atılan paralar ve geçen arabalar0 ve 1 sayılarına benzer. Boşluklarda meydana gelen olayları bildirmek için, bu olayları tanımlamanın bir yolunu düşünmeniz gerekir. Bu açıklamaya kodlama denir.
Mesajlar sonsuz sayıda farklı yolla kodlanabilir. Ancak Shannon, en kısa kodun bit cinsinden entropiden daha küçük olamayacağını gösterdi.
Bu nedenle bir mesajın entropisi bir ölçüdürmesajdaki bilgiler. Dikkate alınan tüm durumlarda kodlama sırasındaki bit sayısı entropiye eşit olduğundan, bu, kodlamanın optimal olduğu anlamına gelir. Kısacası mekanlarımızdaki olaylara dair mesajları kodlamak artık mümkün değil.
Optimum kodlamayla kaybedemezsiniz veyamesajda iletilen tek bir bitin bozulması. Bir bit bile kaybolsa bilgi bozulur. Ancak tüm gerçek iletişim kanalları, mesajın tüm parçalarının alıcıya bozulmadan ulaşacağı konusunda yüzde 100 güven sağlamaz.
Bu sorunu çözmek için yapmanız gerekenlerkod optimal değil, ancak gereksiz. Örneğin, mesajla birlikte sağlama toplamını iletin - mesaj kodu dönüştürülürken elde edilen ve mesajın alınması üzerine yeniden hesaplanarak doğrulanabilen özel olarak hesaplanmış bir değer. İletilen sağlama toplamı hesaplananla eşleşirse iletimin hatasız olma olasılığı oldukça yüksek olacaktır. Ve eğer sağlama toplamı eşleşmiyorsa, yeniden iletim talep edilmelidir. Günümüzde çoğu iletişim kanalı kabaca bu şekilde çalışmaktadır; örneğin internet üzerinden bilgi paketleri iletilirken.
Doğal dil mesajları
Oluşan etkinlik alanını göz önünde bulundurunDoğal dildeki yazılardan. Bu özel bir durum, ama en önemlilerinden biri. Buradaki olaylar iletilen karakterler olacaktır (sabit bir alfabenin harfleri). Bu karakterler farklı olasılıklara sahip dilde bulunur.
En sık kullanılan sembol (yanien sık Rusça yazılmış bütün metinlerde bulunur) bir boşluktur: bin karakterden oluşan, ortalama bir boşluk 175 defa bulunur. Frekansta ikinci olan "o" - 90 simgesidir, ardından diğer ünlüler: "e" (veya "e" - onları ayırt etmeyeceğiz) - 72, "a" - 62 ve i - 62 ve daha ileri ilk ünsüz "t" - 53. Ve "f" nadide - bu sembol bin karakter başına sadece iki kez bulunur.
Rusça'nın 31 harfli alfabesini kullanacağız.dil ("e" ve "e", "well" ve "ь" gibi farklı değildir). Eğer bütün harflere aynı olasılıkta sahip dilde rastlanırsa, sembol başına entropi H = 5 bit olacaktır, ancak sembollerin gerçek frekanslarını hesaba katarsak, entropi daha az olacaktır: H = 4.35 bit. (Bu, karakter bir bayt olarak iletildiğinde, geleneksel kodlamaya göre neredeyse iki kat daha az - 8 bit).
Fakat karakterdeki karakterin entropisi daha da düşüktür. Bir sonraki karakterin ortaya çıkma olasılığı, bütün metinlerdeki karakterin ortalama sıklığı tarafından tam olarak önceden belirlenmemiştir. Hangi karakterin izleneceği önceden aktarılan karakterlere bağlıdır. Örneğin, modern Rusça'da "ъ" sembolünden sonra ünsüz sembol sesini takip edemezsiniz. Ardışık iki ünlü harf "e" den sonra, üçüncü ünlü "e", "uzun boyunlu" kelimesi dışında çok nadiren takip eder. Yani, bir sonraki karakter bir dereceye kadar önceden belirlenmiş. Bir sonraki sembolün önceden belirlenmiş olduğunu hesaba katarsak, bir sonraki sembolün belirsizliği (yani bilgi) 4.35'ten bile az olacaktır. Bazı tahminlere göre, Rusça'daki şu sembol, dilin yapısına göre% 50'den daha önceden belirlenir, yani, optimal kodlama ile, tüm bilgiler mesajların yarısından silinerek iletilebilir.
Başka bir şey de, her harfin güvenle silinemeyeceğidir. Örneğin, yüksek frekanslı "o" (ve genellikle ünlüler) kesişmesi kolaydır, ancak nadiren "f" veya "e" oldukça problemlidir.
Birbirimizle iletişim kurduğumuz doğal dil son derece gereksizdir ve bu nedenle güvenilirdir; eğer bir şeyi yanlış duyarsak sorun değil, bilgi yine de iletilecektir.
Ancak Shannon, bilginin ölçüsünü tanıtana kadar, dilin gereksiz olduğunu ve mesajları ne ölçüde sıkıştırabileceğimizi (ve metin dosyalarının neden arşivleyici tarafından bu kadar iyi sıkıştırıldığını) anlayamadık.
Doğal dil artıklığı
"Biz nasıl vorpsimanie tektkt hakkında" makalesinde(isim tam olarak böyle geliyor!) Ivan Turgenev'in Noble Nest romanının bir parçası çekildi ve bazı dönüşümlere maruz kaldı: Harflerin% 34'ü, ancak rastgele olmayanları parçadan silindi. Kelimelerin ilk ve son harfleri kaldı, yalnızca ünlüler silindi, hepsi silinmedi. Amaç, yalnızca dönüştürülen metinle ilgili tüm bilgileri kurtarma fırsatını elde etmek değil, aynı zamanda bu metni okuyan kişinin eksik mektuplardan dolayı herhangi bir özel zorluk yaşamamasını sağlamaktı.
Bu bozuk yazıyı okumak neden nispeten kolay?metin? Aslında tüm kelimeleri yeniden oluşturmak için gerekli bilgileri içerir. Anadili Rusça olan birinin, tanıma amacıyla kullandığı belirli bir dizi olay (kelimeler ve tüm cümleler) vardır. Ek olarak, konuşmacının elinde bilgiyi kurtarmasına yardımcı olacak standart dil yapıları da vardır. Örneğin,“Blae Blee”- yüksek olasılıkla şu şekilde okunabilir:"Daha duyarlıydı.". Ama ayrı ayrı alınır"Daha çok falan"daha doğrusu şu şekilde geri yüklenecek:“Daha beyazdı”. Günlük iletişimde uğraştığımızdan berigürültü ve parazitin olduğu kanallarda bilgiyi geri yüklemede oldukça iyiyiz, ancak yalnızca önceden bildiğimiz bilgileri. Örneğin, ifade"Onun özellikleri en az hoş, htya nmngo rspkhli ve sıçrama değildir"son kelime hariç iyi okuyor"Sıçrama" - "toplandı". Bu kelime modern sözlükte yok. Bir kelimeyi hızlı okurken"Splls"Daha çok "birbirine yapışmış" gibi okunuyor; yavaş olduğunda sadece kafa karıştırıcı.
Sinyal Sayısallaştırma
Ses veya akustik salınımlar, sinüzoiddir. Bu, örneğin ses editörü ekranında görülebilir. Sesi doğru bir şekilde iletmek için sonsuz sayıda değere ihtiyacınız olacaktır - tüm sinüs dalgası. Bu analog bağlantı ile mümkündür. O şarkı söylüyor - dinlersiniz, şarkı sürerken bağlantı kesilmez.
Bir kanal üzerinden dijital iletişimde yalnızca sınırlı sayıda değer iletebiliriz. Bu, sesin doğru şekilde üretilemeyeceği anlamına mı geliyor? Öyle olmadığı ortaya çıktı.
Farklı sesler farklı şekilde modüle edilmiş sinüs dalgasıdır.Sadece ayrık değerler (frekanslar ve genlikler) iletiriz ve sinüs dalgasının kendisinin iletilmesi gerekmez - alıcı cihaz bunu üretebilir.Bir sinüzoid oluşturur ve üzerine bindirilir.bir iletişim kanalı üzerinden iletilen değerlerden oluşturulan modülasyon. İletişim kanalının girişindeki sesin çıkıştaki sesle çakışması için ayrı değerlerin iletilmesi gereken kesin prensipler vardır, burada bu değerler bazı standart sinüzoidlerin üzerine bindirilir (Kotelnikov teoremi budur) hakkında).
Kotelnikov teoremi (İngiliz Dili Edebiyatında - Nyquist - Shannon teoremi, okuma teoremi)- dijital alanında temel bir açıklamasinyal işleme, sürekli ve ayrık sinyalleri birbirine bağlayan ve “0'dan f1'e kadar frekanslardan oluşan herhangi bir F(t) fonksiyonunun, 1/(2*f1) saniye boyunca birbirini takip eden sayılar kullanılarak herhangi bir doğrulukla sürekli olarak iletilebileceğini belirten
Parazit önleyici kodlama. Hamming kodları
İletim için güvenilir olmayan bir kanaldaIvan Turgenev'in kodlanmış metni, bazı hatalara rağmen, oldukça anlamlı bir metinle sonuçlanacaktır. Fakat her şeyi bir parçaya kadar aktarmamız gerekirse, görev çözülmeyecektir: hangi bitlerin yanlış olduğunu bilmiyoruz, çünkü hata rastgeledir. Sağlama toplamı bile her zaman tasarruf etmez.
Bu yüzden bugün veri aktarırkenağlar, maksimum miktarda bilginin kanala itilebileceği en uygun kodlamaya çok eğilimli değil, aksine Ivan Turgenev'in parçasındaki kelimeleri okuduğumuzda olduğu gibi, hataların kurtarılabileceği kodlamaya (açıkça gereksiz).
Bir hatadan sonra bilgileri kurtarmanıza izin veren özel hata düzeltme kodları vardır. Bunlardan biri Hamming kodu.Diyelim ki dilimizin tamamı üç kelimeden oluşuyor:111000, 001110, 100011. Bu kelimeleri hem mesajın kaynağı hem de alıcı biliyor. Ve bir iletişim kanalında hataların meydana geldiğini biliyoruz, ancak bir kelimeyi iletirken birden fazla bilgi biti bozulmaz.
Diyelim ki önce 111000 kelimesini geçtiğimizi varsayalım. Sonuç olarak, birden fazla hata (hatayı tanımladık) kelimelerden birine dönüşebilir:
1) 111000,011.000, 101000, 110000, 111100, 111010, 111001.
001110 kelimesini iletirken, kelimelerin herhangi biri olabilir:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
Sonunda, 100011 için resepsiyondan alabiliriz:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010.
Üç listenin de çift olmadığını unutmayın.kesişir. Başka bir deyişle, iletişim kanalının diğer ucunda, 1. listeden herhangi bir kelime belirirse, alıcı 111000 kelimesinin kendisine iletildiğinden emin olduğunu bilir ve 2. listeden bir kelime belirirse, 001110 ve 3. listeden 100011 ibaresi belirir. Kodumuzda bir hata olduğunu söylediler.
Düzeltme iki faktörden kaynaklandı.İlk önce, alıcı “sözlüğün” tamamını biliyoryani, mesaj alıcısının olay alanı mesajı ileten alanın alanı ile çakışmaktadır. Kod yalnızca bir hatayla iletildiğinde, sözlükte olmayan bir kelime çıktı.
İkincisi, sözlükteki kelimeler özel bir şekilde seçildi.Bir hata meydana gelse bile alıcı bunu yapamaz.bir kelimeyi diğeriyle karıştırmak. Örneğin, sözlük "kız", "nokta", "çarpma" kelimelerinden oluşuyorsa ve iletim sırasında sonuç "vochka" ise, o zaman alıcı böyle bir kelimenin var olmadığını bilerek bunu yapamaz. hatayı düzeltin - üç kelimeden herhangi biri doğru olabilir. Sözlükte “nokta”, “daw”, “dal” yer alıyorsa ve birden fazla hataya izin verilmediğini biliyorsak, o zaman “vochka” kesinlikle bir “nokta”dır, “daw” değil. Hata düzeltme kodlarında kelimeler, hata sonrasında bile “tanınabilecek” şekilde hassas bir şekilde seçilir. Tek fark, "alfabe" kodunun yalnızca iki harften oluşmasıdır: sıfır ve bir.
Bu kodlamanın fazlalığı çok büyüktür ve bu şekilde iletebileceğimiz sözcük sayısı nispeten azdır.Herhangi bir kelimeyi sözlükten çıkarmamız gerekiyor,bir hata durumunda iletilen kelimelere karşılık gelen listenin tamamıyla çakışabilir (örneğin, "kız" ve "nokta" kelimeleri sözlükte olamaz). Ancak doğru mesaj iletimi o kadar önemlidir ki, hataya dayanıklı kodların araştırılması için büyük çaba harcanmaktadır.
duyum
Entropi (veya belirsizlik kavramları vemesajın öngörülemezliği) ve artıklık (veya önceden belirlenmiş ve öngörülebilirlik) çok doğal olarak, bilginin ölçülmesi hakkındaki sezgisel fikirlerimizle örtüşmektedir. Mesaj ne kadar önceden tahmin edilemezse (entropisi ne kadar büyükse, o kadar az olasılık vardır), o kadar fazla bilgi taşır. Bir sansasyon (örneğin, Tverskaya'da bir timsahla buluşma) nadir bir olaydır, öngörülebilirliği çok düşüktür ve bu nedenle bilgi değeri yüksektir. Genelde bilgi denir - hakkında henüz hiçbir şey bilmediğimiz olayların raporları. Fakat bize aynı kelimelerle ilgili ikinci ve üçüncü kez anlatırlarsa, mesajın fazlalığı büyük olacak, öngörülemezliği sıfıra düşecek ve konuşmacıdan "bildiğimden eminim" ifadesiyle el sallayarak dinlemeyeceğiz. Bu nedenle, medya ilk olmak için çok çalışıyor. Gerçekten beklenmedik haberlerin ortaya çıkmasına neden olan sezgisel yenilik duygusuna yapılan bu yazışma, Shannon’un genel okuyucu için amaçlanmayan makalesinin, doğanın bilgisinin evrensel bir anahtarı olarak algılandığı hissi haline gelmesinde büyük rol oynadı. - dilbilimciler ve edebiyat eleştirmenlerinden biyologlara.
AncakShannon bilgi kavramı - titiz matematiksel teorive iletişim teorisi dışındaki uygulamaları çok güvenilmez. Ancak iletişim teorisinde, merkezi bir rol oynar.
Anlam bilgisi
Shannon, entropi kavramını bir ölçü olarak tanıtıyorbilgi, bilgiyle çalışma fırsatı buldu - her şeyden önce onu ölçmek ve kanal kapasitesi veya optimum kodlama gibi özellikleri değerlendirmek. Ancak Shannon'un bilgiyle başarılı bir şekilde çalışmasına olanak tanıyan ana varsayım, bilgi üretiminin olasılık teorisi açısından başarılı bir şekilde tanımlanabilecek rastgele bir süreç olduğu varsayımıydı.Eğer süreç rastgele değilse, yani yasalara uyar (dahası, doğal dilde olduğu gibi her zaman açık değildir), o zaman Shannon'un aklı buna uygulanamaz.Shannon'ın söylediği hiçbir şeyin bilginin anlamlı olmasıyla hiçbir ilgisi yok.
Karakterlerden (veya alfabenin harflerinden) bahsederken,rastgele olaylar bağlamında tartışabiliriz, ancak dilin sözlerine ulaştığımızda durum dramatik bir şekilde değişecektir. Konuşma, özel olarak organize edilmiş bir süreçtir ve burada mesajın yapısı, iletildiği karakterlerden daha az önemli değildir.
Son zamanlarda hiçbir şey yapamıyormuşuz gibi görünüyordu.En azından metnin anlamlılığını ölçmeye bir şekilde yaklaşmak için yapılıyor ancak son yıllarda durum değişmeye başladı. Bu da öncelikle yapay sinir ağlarının makine çevirisi, metinlerin otomatik özetlenmesi, metinlerden bilgi çıkarılması ve doğal dilde rapor oluşturulması görevlerinde kullanılmasından kaynaklanmaktadır. Bu görevlerin tümü, doğal dilde bulunan anlamlı bilgilerin dönüştürülmesini, kodlanmasını ve kodunun çözülmesini içerir. Ve yavaş yavaş bu tür dönüşümler sırasındaki bilgi kayıpları ve dolayısıyla anlamlı bilginin kapsamı hakkında bir fikir oluşuyor. Ancak bugün Shannon'ın bilgi teorisinin sahip olduğu netlik ve doğruluk bu zor problemlerde henüz mevcut değildir.