Bilgi kodlama teorisinin temel kavramları. Bilgi teorisi ve kodlamanın temelleri. Görünüşleriyle aynı anda sinyal kodlama teorisi yaratılmamış olsaydı, bilgisayarların yaratılması imkansız olurdu.

Vikipedi, özgür ansiklopedi

kodlama teorisi- kodların özelliklerinin bilimi ve amaca ulaşmak için uygunlukları.

Genel bilgi

Kodlama, verilerin doğrudan kullanıma uygun bir biçimden iletilmesi, depolanması, otomatik işlenmesi ve yetkisiz erişime karşı korunması için uygun bir biçime dönüştürülmesi işlemidir. Kodlama teorisinin temel sorunları, bire bir kodlama konularını ve belirli koşullar altında bir iletişim kanalının uygulanmasının karmaşıklığını içerir:86. Bu bağlamda, kodlama teorisi temel olarak aşağıdaki alanları dikkate alır:18:

Veri sıkıştırma

İleri Hata Düzeltme

kriptografi

Kriptografi (diğer Yunancadan. κρυπτός - gizli ve γράφω - Yazıyorum), bu, gizliliği sağlama yöntemleri hakkında bir bilgi alanıdır (dışarıdan bilgi okumanın imkansızlığı), veri bütünlüğü (bilginin algılanamayacak şekilde değiştirilmesinin imkansızlığı), kimlik doğrulama (yazarlığın veya bir nesnenin diğer özelliklerinin doğrulanması), hem de yazarlığı reddetmenin imkansızlığı

04/04/2006 Leonid Chernyak Kategori:Teknolojiler

"Açık Sistemler" Görünüşleriyle eşzamanlı olarak, sinyal kodlama teorisi yaratılmamış olsaydı, bilgisayarların yaratılması imkansız olurdu.Kodlama teorisi, hesaplamanın gelişimini önemli ölçüde etkileyen matematiğin bu alanlarından biridir.

"Açık Sistemler"

Görünüşleriyle aynı anda sinyal kodlama teorisi yaratılmamış olsaydı, bilgisayarların yaratılması imkansız olurdu.

Kodlama teorisi, hesaplamanın gelişimini önemli ölçüde etkileyen matematiğin alanlarından biridir. Kapsamı gerçek (veya gürültülü) kanallar üzerinden veri iletimini kapsar ve konu, iletilen bilgilerin doğruluğunu sağlamaktır. Başka bir deyişle, sinyallemeden sonra verilerden güvenilir ve kolay bir şekilde yararlı bilgilerin çıkarılabilmesi için verilerin en iyi nasıl paketleneceğini araştırır. Bazen kodlama teorisi şifreleme ile karıştırılır, ancak bu doğru değildir: kriptografi ters sorunu çözer, amacı verilerden bilgi çıkarmayı zorlaştırmaktır.

Verileri kodlama ihtiyacı, yüz elli yıldan daha uzun bir süre önce, telgrafın icadından kısa bir süre sonra ortaya çıktı. Kanallar pahalı ve güvenilmezdi, bu da maliyeti en aza indirme ve telgraf iletiminin güvenilirliğini artırma görevini acil hale getirdi. Sorun, transatlantik kabloların döşenmesiyle daha da kötüleşti. 1845'ten beri özel kod kitapları kullanılmaya başlandı; Telgrafçılar onların yardımıyla mesajları manuel olarak “sıkıştırdı” ve yaygın kelime dizilerini daha kısa kodlarla değiştirdiler. Aynı zamanda, transferin doğruluğunu kontrol etmek için, birinci ve ikinci nesil bilgisayarlarda delikli kartların girişinin doğruluğunu kontrol etmek için de kullanılan bir yöntem olan parite kullanılmaya başlandı. Bunu yapmak için, son giriş güvertesine sağlama toplamı olan özel olarak hazırlanmış bir kart yerleştirildi. Giriş aygıtı çok güvenilir değilse (veya güverte çok büyükse), bir hata meydana gelebilir. Bunu düzeltmek için, hesaplanan sağlama toplamı kartta depolanan miktarla eşleşene kadar giriş prosedürü tekrarlandı. Bu şema sadece elverişsiz olmakla kalmaz, aynı zamanda çift hataları da gözden kaçırır. İletişim kanallarının gelişmesiyle birlikte daha etkin bir kontrol mekanizmasına ihtiyaç duyulmuştur.

Gürültülü kanallar üzerinden veri iletimi sorununa ilk teorik çözüm, istatistiksel bilgi teorisinin kurucusu Claude Shannon tarafından önerildi. Shannon zamanının bir yıldızıydı, ABD akademik seçkinlerinden biriydi. Vannevar Bush'ta yüksek lisans öğrencisi olarak 1940'ta 30 yaşın altındaki bilim insanlarına verilen Nobel Ödülü'nü (Nobel Ödülü ile karıştırılmamalıdır!) aldı. Shannon, Bell Laboratuarlarındayken, "Mesaj İletiminin Matematiksel Bir Teorisi" (1948) yazdı; burada, kanalın bant genişliği, mesaj kaynağının entropisinden büyükse, mesajın kodlanabileceğini gösterdi. gecikmeden iletilir. Bu sonuç, Shannon tarafından kanıtlanan teoremlerden birinde yer almaktadır, anlamı, yeterli bant genişliğine sahip bir kanal varsa, bir mesajın bazı gecikmelerle iletilebileceği gerçeğine indirgenir. Ayrıca, kanalda gürültü varlığında güvenilir iletimin teorik olasılığını gösterdi. Michigan'da memleketi olan Shannon'ın mütevazı bir anıtına oyulmuş C = W log ((P+N)/N) formülü, değer olarak Albert Einstein'ın E = mc 2 formülüyle karşılaştırılır.

Shannon'ın çalışması, bilgi teorisi alanında daha fazla araştırmaya yol açtı, ancak pratik mühendislik uygulamaları yoktu. Teoriden pratiğe geçiş, Shannon'ın Bell Laboratuarlarında çalışan ve "Hamming kodları" olarak adlandırılan bir kod sınıfını keşfetmesiyle ün kazanan Richard Hamming'in çabalarıyla mümkün oldu. 40'lı yılların ortalarında Bell Model V röle hesap makinesinde delikli kartlarla çalışmanın zorluğunun Hamming kodlarının icadını tetiklediğine dair bir efsane var. Operatörlerin olmadığı hafta sonları makinede çalışması için kendisine zaman verildi ve girdilerle kendisi uğraşmak zorunda kaldı. Olabildiğince, ancak Hamming, bilgisayarlardaki veri iletim hatları da dahil olmak üzere, öncelikle işlemci ve bellek arasındaki iletişim kanallarındaki hataları düzeltebilen kodlar önerdi. Hamming kodları, Shannon teoremlerinin gösterdiği olasılıkların pratikte nasıl gerçekleştirilebileceğinin kanıtı oldu.

Hamming makalesini 1950'de yayınladı, ancak dahili raporlar kodlama teorisini 1947'ye tarihlendirdi. Bu nedenle, bazıları, Shannon'ın değil, Hamming'in kodlama teorisinin babası olarak görülmesi gerektiğine inanıyor. Ancak, teknoloji tarihinde ilkini aramak işe yaramaz.

Yalnızca "hata düzeltme kodları"nı (Hata Düzeltme Kodu, ECC) ilk önerenin Hamming olduğu kesindir. Bu kodların modern modifikasyonları, tüm veri depolama sistemlerinde ve işlemci ile RAM arasındaki değişim için kullanılır. Varyantlarından biri olan Reed-Solomon kodları, CD'lerde kullanılır ve kayıtların gıcırtı ve çiziklere ve toz parçacıklarına neden olabilecek gürültüler olmadan çalınmasını sağlar. Hamming'e dayalı birçok kod versiyonu vardır, bunlar kodlama algoritmaları ve kontrol bitlerinin sayısı bakımından farklılık gösterir. Bu tür kodlar, gezegenler arası istasyonlarla derin uzay iletişiminin geliştirilmesiyle bağlantılı olarak özel bir önem kazanmıştır, örneğin, yedi bilgi biti için 32 kontrol bitinin veya altı için 26'nın olduğu Reed-Muller kodları vardır.

En yeni ECC kodları arasında LDPC (Low-Density Parity-check Code) kodlarına değinilmelidir. Aslında, yaklaşık otuz yıldır biliniyorlar, ancak onlara özel ilgi, tam olarak yüksek çözünürlüklü televizyonun gelişmeye başladığı son yıllarda keşfedildi. LDPC kodları %100 güvenilir değildir, ancak kanal bant genişliğini maksimumda kullanırken hata oranı istenen seviyeye ayarlanabilir. “Turbo Kodlar” onlara yakındır, derin uzayda bulunan nesnelerle ve sınırlı kanal bant genişliği ile çalışırken etkilidirler.

Vladimir Alexandrovich Kotelnikov'un adı, kodlama teorisi tarihine sıkı sıkıya yazılmıştır. 1933'te "İletişimin Teknik Yeniden İnşasına İlişkin İlk Tüm Birlik Kongresi için Radyo İletişimine İlişkin Malzemeler" de, "Bant genişliği hakkında mı? Eter? ve? teller? Kotelnikov'un adı, eşdeğer olarak, kodlama teorisindeki en önemli teoremlerden birinin adında yer almaktadır. Bu teorem, iletilen sinyalin bilgi kaybı olmadan geri yüklenebileceği koşulları tanımlar.

Bu teorem, "WKS teoremi" (WKS kısaltması Whittaker, Kotelnikov, Shannon'dan alınmıştır) dahil olmak üzere çeşitli şekillerde adlandırılmıştır. Bazı kaynaklarda hem Nyquist-Shannon örnekleme teoremi hem de Whittaker-Shannon örnekleme teoremi kullanılır ve yerel üniversite ders kitaplarında en sık olarak “Kotelnikov teoremi” bulunur. Aslında, teoremin daha uzun bir geçmişi vardır. İlk kısmı 1897'de Fransız matematikçi Emile Borel tarafından kanıtlandı. Edmund Whittaker, 1915'te katkıda bulundu. 1920'de Japon Kinnosuki Ogura, Whittaker'in araştırmasında düzeltmeler yayınladı ve 1928'de Amerikalı Harry Nyquist, sayısallaştırma ve analog sinyal yeniden yapılandırma ilkelerini geliştirdi.

Claude Shannon(1916 - 2001) okul yıllarından itibaren matematik ve elektrik mühendisliğine eşit ilgi gösterdi. 1932'de, 1936'da Michigan Üniversitesi'ne girdi - 1940'ta mezun olduğu Massachusetts Teknoloji Enstitüsü'nde iki derece aldı - elektrik mühendisliği alanında yüksek lisans ve matematik alanında doktora. 1941'de Shannon, Bell Laboratories'e katıldı. Burada daha sonra bilgi teorisiyle sonuçlanan fikirler geliştirmeye başladı. 1948'de Shannon, bilim insanının temel fikirlerinin, özellikle entropi yoluyla bilgi miktarının belirlenmesinin formüle edildiği "Matematiksel İletişim Teorisi" makalesini yayınladı ve ayrıca iki seçimini belirleyen bir bilgi birimi önerdi. eşit derecede olası seçenekler, yani daha sonra denilen şey biraz . 1957-1961'de Shannon, şimdi adını taşıyan gürültülü iletişim kanalları için verim teoremini kanıtlayan çalışmalar yayınladı. 1957'de Shannon, 21 yıl sonra emekli olduğu Massachusetts Teknoloji Enstitüsü'nde profesör oldu. "Hak edilmiş bir dinlenme"de Shannon kendini tamamen eski hokkabazlık tutkusuna adadı. Birkaç hokkabazlık makinesi yaptı ve hatta genel bir hokkabazlık teorisi yarattı.

Richard Hamming(1915 - 1998) eğitimine 1937'de lisans derecesini aldığı Chicago Üniversitesi'nde başladı. 1939'da Nebraska Üniversitesi'nden yüksek lisans derecesi ve Illinois Üniversitesi'nden matematik alanında doktora derecesi aldı. 1945'te Hamming, atom bombasını inşa etmek için büyük bir hükümet araştırma çabası olan Manhattan Projesi üzerinde çalışmaya başladı. 1946'da Hamming, Claude Shannon ile birlikte çalıştığı Bell Telephone Laboratories'e katıldı. 1976'da Hamming, Monterey, California'daki Denizcilik Yüksek Lisans Okulu'nda bir sandalye aldı.

Onu ünlü yapan, hata tespit ve düzeltme kodlarının temel bir çalışması olan çalışma, 1950'de Hamming tarafından yayınlandı. 1956'da, IBM 650'nin ilk ana bilgisayarlarından birinin geliştirilmesine dahil oldu.Çalışmaları, daha sonra üst düzey programlama dillerine dönüşecek olan bir programlama dilinin temellerini attı. Hamming'in bilgisayar bilimi alanına katkısını takdir etmek için, IEEE onun adını taşıyan Bilgisayar Bilimi ve Sistem Teorisi için Seçkin Hizmet Madalyası verdi.

Vladimir Kotelnikov(1908 - 2005) 1926'da NE Bauman (MVTU) adını taşıyan Moskova Yüksek Teknik Okulu Elektrik Mühendisliği Bölümü'ne girdi, ancak MVTU'dan bağımsız bir enstitü olarak ayrılan Moskova Güç Mühendisliği Enstitüsü'nden (MPEI) mezun oldu. . Kotelnikov, lisansüstü okulda (1931-1933) okurken, daha sonra kendi adıyla anılacak olan "referans teoremini" matematiksel olarak tam olarak formüle etti ve kanıtladı. 1933'te yüksek lisans okulundan mezun olduktan sonra, Moskova Enerji Mühendisliği Enstitüsü'nde öğretmenlik yapmaya devam eden Kotelnikov, Merkezi İletişim Araştırma Enstitüsü'nde (TsNIIS) çalışmaya başladı. 1941'de V. A. Kotelnikov, matematiksel olarak çözülemeyen bir sistemin karşılaması gereken gereksinimler hakkında net bir pozisyon formüle etti ve onu deşifre etmenin imkansızlığına dair bir kanıt verildi. 1944'te Kotelnikov, 1980'e kadar çalıştığı MPEI radyo mühendisliği fakültesi dekanı profesörlüğünü aldı. 1953'te, 45 yaşında, Kotelnikov hemen SSCB Bilimler Akademisi'ne tam üye seçildi. 1968'den 1990'a kadar, V. A. Kotelnikov ayrıca Moskova Fizik ve Teknoloji Enstitüsü'nde profesör ve bölüm başkanıydı.

Kodlama teorisinin doğuşu

Çeşitli bilgi kaynaklarını ve bunların iletim kanallarını analiz etmek için, mesajda yer alan ve sinyal tarafından taşınan bilgi miktarını tahmin etmeyi mümkün kılacak nicel bir ölçüye sahip olmak gerekir. Böyle bir önlem, 1946'da Amerikalı bilim adamı C. Shannon tarafından tanıtıldı.

Ayrıca, bilgi kaynağının ayrık olduğunu, her biri ayrı bir gruptan (alfabe) seçilen bir dizi temel mesaj (i,) vererek, a, a 2 ,...,d A; ile bilgi kaynağının alfabesinin hacmidir.

Her temel mesaj, dikkate alınan bilgi kaynağının durumu hakkında bir dizi bilgi (incelenen örnekte) olarak belirli bilgileri içerir. Bu bilginin ölçüsünü ölçmek için anlamsal içeriği ve bu bilginin alıcısı için önem derecesi önemli değildir. Bir mesajı almadan önce, alıcının her zaman benim hangi mesajım olduğu konusunda bir belirsizliği olduğunu unutmayın. mümkün olanlardan ona verilecektir. Bu belirsizlik, i, mesajının iletiminin önceki olasılığı P(i,) kullanılarak tahmin edilir. Ayrık bir kaynağın temel mesajında ​​yer alan nesnel bir nicel bilgi ölçüsünün, belirli bir mesajı seçme olasılığı tarafından belirlendiği ve bu olasılığın bir fonksiyonu olarak cc'yi belirlediği sonucuna varıyoruz. Aynı işlev, bilgi alıcısının ayrık kaynağın durumuna ilişkin sahip olduğu belirsizlik derecesini karakterize eder. Beklenen bilgi hakkındaki belirsizlik derecesinin bilgi aktarım kanalları için gereksinimleri belirlediği sonucuna varılabilir.

Genel olarak, olasılık P(a,) bazı temel mesaj i'nin kaynağının seçimi (bundan sonra ona bir sembol diyeceğiz), daha önce seçilen sembollere, yani. koşullu bir olasılıktır ve böyle bir seçimin apriori olasılığı ile çakışmayacaktır.

Tim bu ^ P(a:) = 1, çünkü ben tam bir olaylar grubu oluşturuyorum

gyi) ve bu sembollerin seçimi bazı fonksiyonel bağımlılıklar kullanılarak gerçekleştirilir. J(a,)= P(a,) = 1, eğer kaynak tarafından sembol seçimi önceden belirlenmiş ise, J(a,)= bir „ bir P(a t ,a)- böyle bir seçimin olasılığı, o zaman bir çift sembolde bulunan bilgi miktarı, i ve i sembollerinin her birinde bulunan bilgi miktarının toplamına eşittir. Nicel bir bilgi ölçüsünün bu özelliğine toplama denir .

biz buna inanıyoruz P(a,)- kendisinden önceki tüm karakterlerden sonra i karakterini seçmenin koşullu olasılığı ve P(a,,i,) i sembolünü seçmenin koşullu olasılığıdır; i'den sonra ve öncekilerin tümü, ancak buna göre P (a 1, a 1) \u003d P (a) P(i,|i y), toplamsallık koşulu yazılabilir

Notasyonu tanıtıyoruz P(a) = P p P (ar) \u003d Q ve yeniden yazma koşulu (5.1):

biz buna inanıyoruz R, O* 0. (5.2) ifadesini kullanarak, fonksiyonun (p) formunu belirleriz. (R). Farklılaştırarak, çarparak R* 0 ve gösteren RO = R, yazmak

(5.3) bağıntısının herhangi biri için sağlandığına dikkat edin. R f O u^^O. Ancak bu gereklilik, (5.3)'ün sağ ve sol taraflarının sabitliğine yol açar: Pq>"(P)= ar"(/?) - ile - inşaat Sonra denkleme geliyoruz PC> "(P) = İLE ve entegrasyondan sonra elde ederiz

yeniden yazacağımızı hesaba katalım

Sonuç olarak, J(a,)'nin özelliklerine ilişkin iki koşulun yerine getirilmesi altında, fonksiyonel bağımlılığın formunun olduğu ortaya çıktı. J(a,) bir sembol seçme olasılığı üzerine bir t sabit bir katsayıya kadar İLE benzersiz olarak tanımlanmış

katsayı İLE sadece ölçeği etkiler ve bilgi miktarını ölçmek için birimler sistemini belirler. ln[P]'den beri F 0, o zaman seçmek mantıklı Os'a, böylece bilgi miktarının bir ölçüsü J(a) olumluydu.

kabul ettikten K=-1, yaz

Bilgi miktarının biriminin, olasılığı şuna eşit olan bir olayın meydana geldiği bilgisine eşit olduğu sonucu çıkar. Bende. Böyle bir bilgi miktarı birimine doğal birim denir. Daha sık olduğu varsayılır İLE= -, o zaman

Böylece, eşit derecede olası iki olaydan birinin meydana geldiği hakkında bir mesaj içeren ve "bit" olarak adlandırılan bilgi miktarının ikili birimine geldik. Bu birim, iletişim teknolojisinde ikili kodların kullanılması nedeniyle yaygındır. Genel durumda logaritmanın tabanını seçerek elde ederiz.

logaritma keyfi bir taban ile olabilir.

Nicel bilgi ölçüsünün toplanabilirlik özelliği, ifade (5.9) temelinde, bir dizi karakterden oluşan bir mesajdaki bilgi miktarının belirlenmesini mümkün kılar. Bir kaynağın böyle bir diziyi seçme olasılığı, önceden mevcut olan tüm mesajlar dikkate alınarak alınır.

Temel mesajda yer alan bilgilerin nicel ölçüsü a (, ortalama bilgi miktarı hakkında bir fikir vermez J(A) bir temel mesaj seçildiğinde kaynak tarafından verilir bir

Ortalama bilgi miktarı, bir bütün olarak bilgi kaynağını karakterize eder ve iletişim sistemlerinin en önemli özelliklerinden biridir.

Alfabe ile bağımsız mesajların ayrı bir kaynağı için bu özelliği tanımlayalım. İLE. ile belirtmek ÜZERİNDE) karakter başına ortalama bilgi miktarı ve rastgele bir değişken L'nin matematiksel beklentisidir - rastgele seçilen bir karakterde bulunan bilgi miktarı fakat

Sembol başına ortalama bilgi miktarına bağımsız mesajların kaynağının entropisi denir. Entropi, bir sonraki sembolü seçerken ortalama önsel belirsizliğin bir göstergesidir.

(5.10) ifadesinden, olasılıklardan birinin P(a) bire eşittir (dolayısıyla diğerleri sıfıra eşittir), o zaman bilgi kaynağının entropisi sıfıra eşit olacaktır - mesaj tamamen tanımlanmıştır.

Tüm olası sembollerin önceki olasılıkları eşitse entropi maksimum olacaktır. İLE, yani R(a() = 1 /İLE, sonra

Kaynak bağımsız olarak P, = olasılığı olan ikili sembolleri seçerse Sulh) ve P 2 \u003d 1 - P, o zaman karakter başına entropi

Şek. 16.1, bir ikili kaynağın entropisinin, iki ikili sembol arasından seçim yapmanın a priori olasılığına bağımlılığını gösterir, bu şekil ayrıca entropinin R, = R2 = 0,5

1 o 1 dvd - ve ikili birimlerde log 2 2 = 1-

Pirinç. 5.1. entropi bağımlılığı K = 2 bunlardan birini seçme olasılığı üzerine

Eşit olasılıklı sembol seçimine sahip, ancak farklı alfabe boyutlarına sahip kaynakların entropisi İLE, büyüme ile logaritmik olarak artar İLE.

Sembollerin seçilme olasılığı farklıysa, kaynağın entropisi düşer. ben(A) olası maksimuma göre H(A) psh = kayıt İLE.

Semboller arasındaki korelasyon ne kadar büyükse, sonraki sembolleri seçme özgürlüğü o kadar az ve yeni seçilen bir sembolün sahip olduğu daha az bilgi. Bunun nedeni, koşullu dağılımın belirsizliğinin koşulsuz dağılımlarının entropisini aşamamasıdır. Kaynağın entropisini bellek ve alfabe ile belirtin İLE bir yandan bir yan H(AA"), ve kaynağın hafızasız, ancak aynı alfabede entropisi - aracılığıyla ÜZERİNDE) ve eşitsizliği kanıtlayın

Notasyonu tanıtarak P(aa") a sembolünü seçmenin koşullu olasılığı için,(/ = 1, 2, İLE) sembolün önceden seçildiğini varsayarsak ajij =1,2,İLE) ve dönüşümleri atlayarak, kanıtsız yazıyoruz

bu da eşitsizliği ispatlar (5.13).

(5.13) veya (5.14)'deki eşitlik şu durumlarda sağlanır:

Bu, bir sembolü seçmenin koşullu olasılığının, onu seçmenin koşulsuz olasılığına eşit olduğu anlamına gelir; bu, yalnızca hafızasız kaynaklar için mümkündür.

İlginç bir şekilde, Rusça'daki metnin entropisi, karakter başına 1.5 ikili birimdir. Aynı zamanda, aynı alfabe ile K= 32 bağımsız ve denk olabilir semboller koşuluyla H(A) tp = Karakter başına 5 ikili olanlar. Böylece, iç bağlantıların varlığı entropiyi yaklaşık 3,3 kat azalttı.

Ayrık bir kaynağın önemli bir özelliği, fazlalığı p'dir ve:

Bilgi kaynağının fazlalığı, içinde boyutsuz bir niceliktir. Doğal olarak, fazlalık olmadığında p u = 0.

Tüm sembollerin eşit olasılığı ile, semboller arasında korelasyon olmayan bir kaynaktan belirli bir miktarda bilgi iletmek için, iletilen minimum sembol sayısı /7 min: /r 0 (/7 0 R (L max)) gereklidir. Entropili bir kaynaktan aynı miktarda bilgiyi iletmek için (semboller birbirine bağlıdır ve eşit olmayan şekilde olasıdır), ortalama sayıda sembol gereklidir. n = n„H(A) m JH(A).

Ayrık bir kaynak, zaman birimi v H başına sembol sayısı ile belirlenen performans ile de karakterize edilir:

eğer performans ben(A) ikili birimlerde ve zamanı saniye cinsinden tanımlayın, ardından ÜZERİNDE) - saniyedeki ikili birim sayısıdır. Yeterince uzun /? uzunluğunda sabit karakter dizileri üreten ayrık kaynaklar için, aşağıdaki kavramlar tanıtılır: tüm uzunluk dizilerinin içine girdiği tipik ve atipik kaynak karakter dizileri P. Tüm tipik diziler NlMl (A) kaynak P-»oo yaklaşık olarak aynı gerçekleşme olasılığına sahiptir

Tüm atipik dizilerin toplam oluşma olasılığı sıfır olma eğilimindedir. (5.11) eşitliğine uygun olarak, tipik dizilerin olasılığını varsayarsak /N rm (A), kaynağın entropisi logN TIin (,4)'tür ve sonra

Gürültülü ayrı bir kanal üzerinden bilgi iletiminin miktarını ve hızını düşünün. Önceden, ayrı bir kaynak tarafından üretilen bilgileri bir dizi karakter (i,) biçiminde ele almıştık.

Şimdi, kaynak bilginin kodlandığını ve bir dizi kod sembolünü temsil ettiğini varsayalım. (B, (/ = 1,2,..T - kod tabanı), çıkışında bir sembol dizisinin göründüğü ayrı bir bilgi iletim kanalı ile tutarlıdır.

Kodlama işleminin bire bir olduğunu varsayıyoruz - karakter dizisine göre (B,)(i,) dizisini benzersiz bir şekilde geri yükleyebilir, yani kod sembolleri ile kaynak bilgileri tamamen geri yüklemek mümkündür.

Ancak, kaçış karakterlerini ele alırsak |?. j ve giriş sembolleri (/>,), daha sonra bilgi iletim kanalında parazit olması nedeniyle kurtarma mümkün değildir. Çıkış dizisinin entropisi //(/?)

giriş dizisinin entropisinden daha büyük olabilir H(B), ancak alıcı için bilgi miktarı artmadı.

En iyi durumda, girdi ve çıktı arasında bire bir ilişkiler mümkündür ve faydalı bilgiler kaybolmaz; en kötü durumda, bilgi iletim kanalının çıktı sembollerinden girdi sembolleri hakkında hiçbir şey söylenemez, faydalı bilgiler kanalda tamamen kaybolur.

Gürültülü bir kanaldaki bilgi kaybını ve gürültülü bir kanal üzerinden iletilen bilgi miktarını tahmin edelim. Aktarılan karakter 6 ile alınırsa, karakterin doğru bir şekilde iletildiğini düşünüyoruz.

sembol bj aynı numara ile (/= J). Ardından gürültüsüz ideal bir kanal için şunu yazıyoruz:

sembole göre bj- eşitsizliklerden dolayı kanal çıkışında (5.21)

belirsizlik kaçınılmazdır. Semboldeki bilgilerin ben tamamen iletilmez ve parazit nedeniyle bir kısmı kanalda kaybolur. Kantitatif bir bilgi ölçüsü kavramına dayanarak, ft sembolünü aldıktan sonra kanalın çıkışında meydana gelen belirsizliğin sayısal ifadesinin; :

ve iletim sırasında kanalda kaybolan bilgi miktarını belirler.

Sabitleme ft. ve tüm olası semboller üzerinden ortalama (5.22), toplamı elde ederiz

bir sembol alırken hafızasız bir kanal üzerinden temel bir sembol iletildiğinde kanalda kaybolan bilgi miktarını belirleyen bj(t).

Toplamın (5.23) tüm ft üzerinden ortalamasını alırken, şu şekilde ifade ettiğimiz Z? değerini elde ederiz. n(in/in- Hafızasız bir kanal üzerinden bir karakter iletilirken kaybolan bilgi miktarını belirler:

nerede P^bjbjj- iletildiğinde, bir olayın ortak olasılığı

sembol B. sembolü alacak B T .

H [w/ bilgi kaynağının özelliklerine bağlıdır.

kanal girişi İÇİNDE ve iletişim kanalının olasılıksal özellikleri hakkında. Shannon'a göre istatistiksel iletişim teorisinde n(in/in kanal güvenilmezliği olarak adlandırılır.

koşullu entropi YB/B, ayrık bir kaynağın entropisi

kanal girişinde H(W) ve entropi VE ^B) çıkışında olamaz

olumsuz. Parazitsiz bir kanalda, kanal güvenilmezliği

n(v/v = 0. (5.20) uyarınca, şunu not ediyoruz: S^v/v^

ve eşitlik sadece kanalın girdi ve çıktısı istatistiksel olarak bağımsız olduğunda gerçekleşir:

Çıkış sembolleri giriş sembollerine bağlı değildir - bozuk bir kanal veya çok güçlü parazit durumunda.

Daha önce olduğu gibi, tipik diziler için yazabiliriz

müdahalenin yokluğunda güvenilmez olduğunu söylemek

Kanal üzerinden ortalama olarak iletilen bilgilerin altında J[ b/ sembol başına kanal girişindeki bilgi miktarı arasındaki farkı anlıyoruz J(B) ve /? kanalında kaybolan bilgiler).

Bilginin kaynağı ve kanalın hafızası yoksa, o zaman

İfade (5.27), kanalın çıkış sembollerinin entropisini belirler. Kanalın çıkışındaki bilgilerin bir kısmı faydalıdır ve geri kalanı kanaldaki girişim tarafından üretildiğinden yanlıştır. şunu not edelim n[v/ 2?) kanaldaki parazit ve i(d)-I(d/d) - kanaldan geçen faydalı bilgiler arasındaki farkı ifade eder.

Kanalın çıkışında oluşan dizilerin büyük çoğunluğunun atipik olduğuna ve çok küçük bir toplam olasılığa sahip olduğuna dikkat edin.

Kural olarak, en yaygın parazit türü dikkate alınır - ek gürültü. N(t); Kanalın çıkışındaki sinyal şu ​​şekildedir:

Ayrık sinyaller için, (5.28)'den sonraki eşdeğer gürültü ayrık bir yapıya sahiptir. Gürültü, giriş ve çıkış sinyallerinin dizilerine benzer ayrık bir rastgele dizidir. Ayrık bir kanalda toplamsal gürültü alfabesinin sembollerini C1 = 0, 1,2, T- 1). Böyle bir kanalda koşullu geçiş olasılıkları

Çünkü VE (^B/?) Ve (B) daha sonra, sonuç olarak, girişe göre ayrık #(/) kanalının çıkış dizisinin bilgisi B(t) ya da tam tersi Ve (B) - H ^ in / in) (5).

Yani kanal üzerinden iletilen bilgi, girişindeki bilgiyi aşamaz.

Kanal girişi bir ortalama alırsa x k bir saniyede semboller, daha sonra gürültülü bir kanal üzerinden ortalama bilgi aktarım hızını belirlemek mümkündür:

nerede Н(В) = V k J(B,B^ - kanal girişinde kaynak performansı; n (inç / inç) \u003d U - n (inç, inç) ~ birim zaman başına kanalın güvenilmezliği; H (B) = V k H^B^- kanalın çıktısının oluşturduğu kaynağın performansı (yararlı olanın bir kısmını ve yanlış bilginin bir kısmını vererek); H ^ in / B ^ \u003d U ila 1 / (in / in)- yanlış bilgi miktarı,

birim zamanda kanalda parazit yarattı.

Bir kanal üzerinden bilgi iletiminin miktarı ve hızı kavramları, bir iletişim kanalının çeşitli bölümlerine uygulanabilir. Bu "enkoder girişi - dekoder çıkışı" bölümü olabilir.

Söz konusu kanalın kesitini genişleterek, bileşen parçalarından herhangi birinin hızını aşmanın imkansız olduğuna dikkat edin. Geri dönüşü olmayan herhangi bir dönüşüm bilgi kaybına yol açar. Geri dönüşü olmayan dönüşümler, yalnızca girişimin etkisini değil, aynı zamanda algılamayı, fazlalıklı kodlarla kod çözmeyi de içerir. Alma kaybını azaltmanın yolları vardır. Bu "genel olarak resepsiyon".

Ayrık bir kanalın bant genişliğini ve optimal kodlama teoremini düşünün. Shannon, giriş sinyalleri topluluğu üzerindeki bir dizi kısıtlama altında bilinen özelliklere (gürültü) sahip bir kanal üzerinden maksimum olası bilgi aktarım hızlarını belirleyen bir özellik tanıttı. Bu, C kanalının bant genişliğidir. Ayrık bir kanal için

maksimumun olası giriş kaynakları tarafından korunduğu yer İÇİNDE verilen v k ve giriş karakter alfabesinin hacmi T.

Ayrık bir kanalın çıktısının tanımına dayanarak yazıyoruz

Bağımsız giriş ve çıkış (kanalda yüksek gürültü seviyesi) ile C = 0 olduğuna ve buna göre,

sinyalde parazit girişimi olmadığında.

Hafızasız ikili simetrik kanal için

Pirinç. 5.2.

İkili kanalın kapasitesinin parametreye bağımlılığının grafiği rŞek. 5.2. saat r= 1/2 kanal bant genişliği C = 0, koşullu entropi

//(/?//?) = 1. Pratik ilgi

grafik 0'da temsil eder

Shannon'ın optimal kodlama konusundaki temel teoremi, kapasite kavramıyla ilgilidir. Ayrık bir kanal için formülasyonu aşağıdaki gibidir: eğer mesaj kaynağının performansı ÜZERİNDE) C kanalının bant genişliğinden daha az:

Kanalın hata veya güvenilmez olma olasılığının altında olduğu bir optimal kodlama ve kod çözme yöntemi vardır. n[a!A j keyfi olarak küçük olabilir. Eğer

böyle yollar yok.

Shannon teoremine göre, sonlu değer İTİBAREN kanal üzerinden hatasız bilgi aktarım hızının sınır değeridir. Ancak gürültülü bir kanal için en uygun kodu bulmanın yolları belirtilmemiştir. Bununla birlikte, teorem, bilgi iletim teknolojisinin temel olasılıkları hakkındaki görüşleri kökten değiştirdi. Shannon'dan önce, gürültülü bir kanalda bilgi aktarım hızını sıfıra indirerek keyfi olarak küçük bir hata olasılığı elde etmenin mümkün olduğuna inanılıyordu. Bu, örneğin, hafızasız bir kanalda karakter tekrarının bir sonucu olarak iletişim doğruluğunda bir artıştır.

Shannon teoreminin birkaç kesin kanıtı bilinmektedir. Teorem, rastgele kodlama ile ayrık bir hafızasız kanal için kanıtlandı. Bu durumda, belirli bir kaynak ve belirli bir kanal için rastgele seçilen tüm kodların kümesi dikkate alınır ve tüm kodlar üzerinde ortalama hatalı kod çözme olasılığının sıfıra asimptotik yaklaşımı gerçeği, süresinde sınırsız bir artışla ileri sürülür. mesaj dizisi. Böylece, yalnızca hatasız kod çözme olanağı sağlayan bir kodun varlığı kanıtlanmakta, ancak açık bir kodlama yöntemi önerilmemektedir. Aynı zamanda, ispat sırasında, mesaj dizisinin topluluğunun entropilerinin eşitliğini ve iletim için kullanılan bire bir karşılık gelen kod sözcükleri kümesinin eşitliğini korurken, topluluk açıkça ortaya çıkıyor. İÇİNDE kod simgeleri dizisinin karşılıklı bağımlılığını artırmak için ek fazlalık getirilmelidir. Bu, yalnızca kod sözcüklerinin seçildiği kod dizileri kümesini genişleterek yapılabilir.

Gürültülü kanallar için ana kodlama teoremi, belirli bir kodu seçmenin açık yollarını göstermemesine ve teoremin kanıtında da bulunmamasına rağmen, rastgele seçilen kodların çoğunun, yeterince uzun mesajı kodlarken gösterilebilir. diziler, hatalı kod çözmenin ortalama olasılığını biraz aşar. Bununla birlikte, uzun bloklarda kodlamanın pratik olanakları, bellek sistemlerinin uygulanmasındaki zorluklar ve çok sayıda kod elemanının dizilerinin mantıksal olarak işlenmesi ve ayrıca bilginin iletilmesi ve işlenmesindeki gecikmedeki artış nedeniyle sınırlıdır. Aslında, özellikle ilgi çekici olan, sürenin sonlu değerleri için hatalı kod çözme olasılığını belirlemeyi mümkün kılan sonuçlardır. P kullanılan kod blokları. Uygulamada, orta gecikme değerleri ile sınırlıdırlar ve kanal bant genişliğinin eksik kullanımı ile iletim olasılığında bir artış sağlarlar.

mesajları, onları yansıtan sinyallerle tanımlama yollarını araştıran bir bilgi teorisi dalıdır. Kodlama teorisinin görevi, bilgi kaynağını iletişim kanalıyla koordine etmektir.

Kodlamanın amacı, bilgi kaynağı aracılığıyla tüketiciye gelen hem kesikli hem de sürekli bilgidir. Kodlama kavramı, bilginin belirli bir iletişim kanalı üzerinden iletilmeye uygun bir forma dönüştürülmesi anlamına gelir.

Ters işlem - kod çözme - alınan mesajı kodlanmış biçimden genel kabul görmüş, tüketici tarafından erişilebilir olana geri yüklemekten oluşur.

Kodlama teorisinde birkaç alan vardır:

• statik veya verimli kodlama;
• gürültüye karşı bağışıklık kodlaması;
• düzeltici kodlar;
• döngüsel kodlar;
• aritmetik kodlar.

Kontrol sistemlerinin, özellikle bilgisayarların ortaya çıkmasıyla, kodlama olmadan bilgi iletimi imkansız olduğundan, kodlamanın rolü önemli ölçüde arttı ve değişti. Son zamanlarda, telekomünikasyon sistemlerinin gelişimi ve bilgi işleme ve depolama için bilgisayarların yaygın kullanımı ile bağlantılı olarak, yeni bir bilgi alanı ortaya çıktı - bilgi güvenliği.

Kodlama, sinyallerin ve mesaj öğelerinin yardımıyla bu öğelerin sabitlenebileceği bir yazışma sistemi biçiminde depolanması, işlenmesi ve iletilmesi sırasında bilgileri görüntülemenin evrensel bir yoludur.

Kod, bir mesajı, genellikle herhangi bir bilgi kaybı olmaksızın, mesajın bir sembolik temsilinden diğerine açık bir şekilde dönüştürmek için kullanılan bir kuraldır.

Tüm kod sözcükleri aynı uzunluktaysa, kod tek tip veya blok olarak adlandırılır.

Soyut bir alfabe ile sıralı ayrık bir semboller kümesini kastediyoruz.

Alfabetik kodlama. Alfabetik, yani harf harf, kodlama kod tablosundan ayarlanabilir. Aslında, dönüşüm kodu bir tür ikamedir.

nerede A alfabesi, B alfabesinde oluşan kelimeler kümesi. Harf kodları kümesine temel kodlar kümesi denir. Alfabetik kodlama, herhangi bir mesaj kümesi için kullanılabilir.

Bilgisayar veri işleme, ikili kod kullanımına dayanmaktadır. Bu evrensel kodlama yöntemi, kaynağı ve içeriği ne olursa olsun herhangi bir veri için uygundur.

Metin kodlaması

Metinler, bazı alfabelerde bulunan karakter dizileridir. Metin kodlaması, üzerine inşa edildiği alfabenin ikili kodlamasına indirgenir. Alfabenin en yaygın kullanılan bayt kodlaması. Bu durumda, alfabenin maksimum kapasitesi 256 karakterdir. Böyle bir alfabe iki grup alfabetik karakter (örneğin, Rusça ve Latince), sayılar, noktalama işaretleri ve matematiksel semboller, bir boşluk ve az sayıda ek karakter içerebilir. Böyle bir alfabeye örnek olarak ASCII kodu verilebilir.

Ancak, sınırlı 256 karakterlik kod seti bugün artık uluslararası iletişimin artan ihtiyaçlarını karşılamıyor. Evrensel 16-bit UNICODE karakter kodlama sistemi daha yaygın hale geliyor.

UNICODE kodlama sisteminde alfabenin gücü 216 = 65.536 farklı kod olup, bunların 63.484 kodu çoğu alfabenin karakterlerine karşılık gelir ve kalan 2048 kod ikiye bölünerek 1024 sütun x 1024 boyutunda bir tablo oluşturur. çizgiler. Bu tabloda bir milyondan fazla farklı karakterin yerleştirilebileceği bir milyondan fazla hücre var. Bunlar, "ölü" dillerin sembollerinin yanı sıra sözlük içeriği, işaretçiler, işaretler vb. Bu ek karakterler bir çift 16 bitlik sözcük gerektirir (satır numarası için 16 bit ve sütun numarası için 16 bit).

Böylece UNICODE sistemi, ulusal yazı sistemlerinin tüm karakterleri için evrensel bir kodlama sistemidir ve önemli ölçüde genişleme olanağına sahiptir.

görüntü kodlama

Çizimler, resimler, fotoğraflar kodlanmıştır raster formatında. Bu görünümde, her görüntü dikdörtgen renkli noktalar tablosudur. Her bir noktanın rengi ve parlaklığı, grafik verilerini temsil etmek için ikili bir kodun kullanılmasına izin veren sayısal biçimde ifade edilir.

Siyah beyaz görüntüleri gri tonlamalı olarak göstermek gelenekseldir, bunun için GreyScale modeli kullanılır. Bir noktanın parlaklığı bir bayt olarak kodlanmışsa 256 farklı gri tonu kullanılabilir. Bu doğruluk, insan gözünün duyarlılığı ve baskı teknolojisinin yetenekleri ile tutarlıdır.

Renkli görüntüleri kodlarken, rengin bileşenlere ayrıştırılması ilkesi kullanılır; bunun için RGB modeli kullanılır. Ekrandaki renkli görüntü, üç temel rengin karıştırılmasıyla elde edilir: kırmızı (Kırmızı, R), mavi (Mavi, B) ve yeşil (Yeşil, G).

Ekrandaki her piksel, bu renklerde parlayan birbirine yakın üç öğeden oluşur.

Bu prensibi kullanan renkli ekranlara RGB monitörler denir.

Piksel renk kodu, her bir temel rengin oranı hakkında bilgi içerir.

renk uyumu

Her üç bileşen de aynı yoğunluğa (parlaklığa) sahipse, kombinasyonlarından 8 farklı renk elde edilebilir (23):

24 bit renk derinliğinde renk şekillendirme:

Renk derinliği ne kadar büyük olursa, mevcut renk aralığı o kadar geniş olur ve sayısallaştırılmış görüntüdeki temsilleri o kadar doğru olur. Bit derinliği bire eşit olan bir pikselin yalnızca 2 (birinci dereceye kadar) olası durumu vardır - iki renk: siyah veya beyaz. Bit derinliği 8 birim olan bir pikselin 28 veya 256 olası renk değeri vardır. Bit derinliği 24 birim olan bir piksel 224 derece) veya 16.7 milyon olası değere sahiptir. 16,7 milyon renk içeren 24 bitlik görüntülerin çevremizdeki dünyanın renklerini doğru bir şekilde ilettiğine inanılmaktadır. Kural olarak, bit çözünürlüğü 1 ila 48 bit/piksel aralığında ayarlanır.

Kağıda yazdırırken, biraz farklı bir renk modeli kullanılır: monitör ışık yayarsa, renk eklenmesi sonucunda renk tonu elde edilir, ardından boyalar ışığı emer, renkler çıkarılır. Bu nedenle mavi (Cyan, C), macenta (Macenta, M) ve sarı (Sarı, Y) boyalar ana boyalar olarak kullanılmaktadır. Ek olarak, boyaların ideal olmaması nedeniyle, genellikle bunlara dördüncü bir tane eklenir - siyah (siyah, K). Her boya hakkında bilgi depolamak için ve bu durumda en sık 1 bayt kullanılır. Bu kodlama sistemine CMYK denir.

Daha kaba bir renk temsili daha az bit kullanır. Örneğin, renkli grafikleri 16 bit sayılarla kodlamaya Yüksek Renk denir. Bu durumda, her renge beş rakam atanır.

Ses ve video kodlama

Sağlam bilgilerle çalışma teknikleri bilgisayar teknolojisine her şeyden sonra geldi. Herhangi bir ses sinyaline uygulanabilen analitik bir kodlama yöntemi, analogdan dijitale dönüştürmeye dayanır. Orijinal analog sinyal, ikili kodda yazılmış bir dizi dijital sinyal olarak temsil edilir. Dönüşümün bit derinliği, tek bir dijital sinyale karşılık gelen veri miktarını belirler. Ses çalarken, ters bir dijitalden analoğa dönüştürme gerçekleştirilir.

Bu kodlama yöntemi, yeniden üretilen sinyalin orijinalden biraz farklı olması için bir hata içerir.

Tablo sentezine dayalı kodlama yöntemi yalnızca bir müzik parçasına uygulanabilir. Çeşitli müzik aletlerinin seslerinin örnekleri (örnekleri) önceden hazırlanmış tablolarda saklanır. Sayısal kodlar enstrümanı, notayı ve sesin süresini tanımlar.

Bir video sinyalini kodlarken, bir dizi görüntü (çerçeve) ve ses (ses izi) kaydetmek gerekir. Video kayıt formatı, her iki veri akışının da tek bir dijital diziye dahil edilmesini sağlar.

Kodlama teorisi. Kodlama türleri Kodlama teorisinin temel kavramları Daha önce, kodlama araçları yardımcı bir rol oynadı ve ayrı bir matematiksel çalışma konusu olarak kabul edilmedi, ancak bilgisayarların ortaya çıkmasıyla durum kökten değişti. Kodlama, bilgi teknolojisine kelimenin tam anlamıyla nüfuz eder ve çeşitli (hemen hemen tüm) programlama görevlerinin çözümünde merkezi bir konudur: ۞ bilgisayar belleğinde keyfi nitelikteki verilerin (örneğin, sayılar, metin, grafikler) temsil edilmesi; ۞ bilgilerin yetkisiz erişime karşı korunması; ۞ Haberleşme kanalları üzerinden veri aktarımı sırasında gürültü bağışıklığının sağlanması; ۞ veritabanlarındaki bilgilerin sıkıştırılması. Kodlama teorisi, mesajların onları temsil eden sinyallerle nasıl tanımlanabileceğini inceleyen bir bilgi teorisi dalıdır. Görev: Bilgi kaynağını iletişim kanalıyla koordine edin. Nesne: Bir bilgi kaynağı aracılığıyla tüketiciye sağlanan ayrık veya sürekli bilgi. Kodlama, bilginin belirli bir iletişim kanalı üzerinden iletilmeye uygun bir formüle dönüştürülmesidir. Matematikte kodlamaya bir örnek, Descartes tarafından tanıtılan ve geometrik nesneleri sayılar, harfler ve bunların kombinasyonları - formüller biçiminde analitik ifadeleriyle incelemeyi mümkün kılan koordinat yöntemidir. Kodlama kavramı, bilginin belirli bir iletişim kanalı üzerinden iletilmeye uygun bir forma dönüştürülmesi anlamına gelir. Kod çözme, alınan mesajın kodlanmış formdan tüketicinin erişebileceği bir forma geri yüklenmesidir.

Konu 5.2. Alfabetik kodlama Genel durumda kodlama problemi aşağıdaki gibi gösterilebilir. Sonlu sayıda karakterden oluşan iki A ve B alfabesi verilsin: ve. Alfabenin elemanlarına harf denir. A alfabesindeki sıralı bir kümeye kelime adı verilir, burada n =l()=| |. , n sayısı kelimedeki harf sayısını gösterir ve kelimenin uzunluğu olarak adlandırılır, Boş kelime belirtilir: Kelime için a1 harfi, kelimenin başlangıcı veya öneki, a harfi kelimenin sonu veya son ekidir. , ve Kelimeler birleştirilebilir. Bunu yapmak için, ikinci kelimenin öneki, ilk kelimenin son ekini hemen takip etmelidir, ancak yeni kelimede, kelimelerden biri boş olmadığı sürece, doğal olarak durumlarını kaybederler. Sözcüklerin bileşimi ve gösterilir, ayrıca n özdeş sözcüğün bileşimi gösterilir. A alfabesinin boş olmayan tüm sözcüklerinin kümesi A*: ile gösterilir: A kümesine mesaj alfabesi, B kümesine kodlama alfabesi denir. B alfabesinde oluşan kelime grubu B* ile gösterilecektir.

A alfabesinden B alfabesine kelimelerin eşlenmesini F ile gösterin. Daha sonra kelimeye kelimenin kodu denir. Kodlama, mesaj öğeleri ve bu öğelerin sabitlenebileceği sinyaller arasındaki yazışmalar sistemi biçiminde depolanması, iletilmesi ve işlenmesi sırasında bilgileri görüntülemenin evrensel bir yoludur. Bu nedenle, bir kod, bir mesajın bir sembolik temsil biçiminden (orijinal alfabe A) diğerine (nesne alfabesi B), genellikle herhangi bir bilgi kaybı olmaksızın, açık bir şekilde dönüştürülmesi (yani işlevi) için bir kuraldır. F: A* B*→ orijinal alfabe A'nın sözcüklerini B alfabesine dönüştürme işlemine bilgi kodlaması denir. Bir kelimeyi geri dönüştürme işlemine kod çözme denir. Bu nedenle, kod çözme F'nin tersidir, yani. F1. bir sözcük içine Herhangi bir kodlama için bir kod çözme işlemi gerçekleştirilmesi gerektiğinden, eşleme ters çevrilebilir (bir bijeksiyon) olmalıdır. |B|= m ise, F mimik kodlama olarak adlandırılır, en yaygın durum B = (0, 1) ikili kodlamadır. Aşağıda ele alınan bu durumdur. Tüm kod sözcükleri aynı uzunluktaysa, kod tek tip veya blok olarak adlandırılır. Alfabetik (veya harf harf) kodlama, bir kod tablosu ile belirtilebilir. Bazı ikameler bir kod veya kodlama işlevi görecektir. Sonra nerede, . Böyle bir harf harf kodlama, bir dizi temel kod olarak belirtilir. Alfabetik kodlama, herhangi bir mesaj kümesi için kullanılabilir. Böylece alfabetik kodlama en basitidir ve her zaman boş olmayan alfabelere girilebilir. . Birçok harf kodu

ÖRNEK A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) B = (0, 1) harfleri verilsin. O zaman kodlama tablosu bir ikame olabilir: . Bu bir BCD kodlamasıdır, bire birdir ve bu nedenle kodu çözülebilir. Ancak şema bire bir değildir. Örneğin, altı 111111 kümesi hem 333 hem de 77 kelimeleriyle ve ayrıca 111111, 137, 3311 veya 7111 artı herhangi bir permütasyonla eşleşebilir. Bir harfin temel kodu başka bir harfin temel kodunun ön eki değilse, alfabetik kodlama şemasına önek adı verilir. Temel kodlardan oluşan herhangi bir kelime benzersiz bir şekilde temel kodlara ayrışırsa, bir alfabetik kodlama şemasının ayrılabilir olduğu söylenir. Ayrılabilir bir şema ile alfabetik kodlama, kod çözmeye izin verir. Önek şemasının ayrılabilir olduğu kanıtlanabilir. Bir alfabetik kodlama şemasının ayrılabilir olması için, temel kodların uzunlukları, Macmillan eşitsizliği olarak bilinen bir ilişkiyi sağlamalıdır. Macmillan eşitsizliği Eğer alfabetik kodlama şeması

ayrılabilir ise aşağıdaki eşitsizlik geçerlidir. a harfinin temel kodu, b harfinin temel kodunun önekidir. Konu 5.3. Minimum fazlalık kodlaması Uygulamada, mesaj kodlarının mümkün olduğu kadar kısa olması önemlidir. Alfabetik kodlama herhangi bir mesaj için uygundur, ancak A alfabesinin tüm kelimelerinin kümesi hakkında hiçbir şey bilinmiyorsa, optimizasyon problemini tam olarak formüle etmek zordur. Bununla birlikte, pratikte ek bilgiler genellikle mevcuttur. Örneğin, doğal dilde sunulan mesajlar için, bu tür ek bilgiler, mesajdaki harflerin oluşma olasılık dağılımı olabilir. Daha sonra optimal bir kod oluşturma problemi, kesin bir matematiksel formülasyon ve kesin bir çözüm elde eder.

Bazı ayrılabilir alfabetik kodlama şeması verilsin. O zaman sıralı kümenin sıralı kümenin bir permütasyonu olduğu herhangi bir şema da ayrılabilir olacaktır. Bu durumda, temel kod setinin uzunlukları eşitse, şemadaki permütasyonları kodlanmış mesajın uzunluğunu etkilemez. Temel kodların uzunluklarının farklı olması durumunda, mesaj kodunun uzunluğu doğrudan hangi temel kodların hangi harflere karşılık geldiğine ve mesajdaki harflerin bileşimine bağlıdır. Belirli bir mesaj ve belirli bir kodlama şeması verildiğinde, mesaj kodunun uzunluğunun minimum olacağı böyle bir kod permütasyonu seçmek mümkündür. Sabit bir şema için sabit bir mesaj kodunun (S) uzunluğunun minimum olacağı temel kodları atamak için bir algoritma: ۞ harfleri, oluşum sayısına göre azalan düzende sıralayın; ۞ temel kodları artan uzunluk sırasına göre sıralayın; ۞ Harflere göre kodları öngörülen sıraya göre yerleştirin. Alfabe ve mesajdaki harflerin bulunma olasılıkları verilsin:

Burada pi, ai harfinin ortaya çıkma olasılığıdır ve mesajda görünme olasılığı sıfır olan harfler hariç tutulur ve harfler, ÖRNEK olarak belirtilen ve tanımlanan mesajların oluşma olasılığına göre azalan sırada sıralanır. Ayrılabilir bir alfabetik kodlama şeması için A=(a,b), B=(0,1), olasılık dağılımı altında kodlama maliyeti ve olasılık dağılımı altında kodlama maliyeti

Konu 5.4. Huffman Kodlaması Bu algoritma 1952'de David Huffman tarafından icat edildi. Konu 5.5. Aritmetik kodlama Huffman algoritmasında olduğu gibi, her şey bir elementler tablosu ve karşılık gelen olasılıklarla başlar. Giriş alfabesinin sadece üç elemandan oluştuğunu varsayalım: a1, a2 ve a3 ve aynı zamanda P(a1) = 1/2 P(a2) = 1/3 P(a3) = 1/6 a1, a1, a2, a3 dizisini kodlamak için. Aralığı bölelim, burada p sabit bir sayı, 0<р<(r­1)/2r, а "мощностная" граница где Tr(p)=­p logr(p/(r­ 1))­(1­р)logr(l­ p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения ­ одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для к­рого существует декодер,состоящий из регист

ra shift ve bir çoğunluk elemanı ve bir hatayı düzeltmenin bir sırası vardır ((2) ile karşılaştırın). matematiksel olarak kodlayıcı ve kod çözücü modelleri genellikle bir işlevsel elemanlar devresinden düşünülür ve karmaşıklık, devredeki elemanların sayısı olarak anlaşılır. Bilinen hata düzeltme kodları sınıfları için, K. ve D. için olası algoritmalar üzerine bir çalışma yapıldı ve kodlayıcı ve kod çözücünün karmaşıklığına ilişkin üst sınırlar elde edildi. Kodlama hızı, kodlamanın gürültü bağışıklığı ve kod çözücünün karmaşıklığı arasında da bazı ilişkiler bulunur (bkz. ). Kodlama teorisindeki bir başka araştırma yönü, birçok sonucun (örneğin, Shannon teoremi ve sınırı (3)) "yapıcı" olmadığı, (Kn) kodlarının sonsuz dizilerinin varlığına ilişkin teoremler olduğu gerçeğiyle ilgilidir. Bu tür (Kn) kod dizileri sınıfında bu sonuçları kanıtlamak için çabalar sarf edilmektedir, kp için, l uzunluğundaki rastgele bir kelimenin yavaş bir zaman kümesine ait olduğunu tanıyan bir Turing makinesi vardır. l'ye göre büyüme sırası (örneğin, llog l). Kodlama teorisinde geliştirilen bazı yeni yapılar ve sınırlar türetme yöntemleri, ilk bakışta kodlama teorisinin geleneksel problemlerinden çok uzak olan sorularda önemli ilerlemelere yol açmıştır. Burada, kontak devreleri ile mantık cebirinin işlevlerini gerçekleştirmenin semptom-optimal optimal yöntemindeki bir hatanın düzeltilmesiyle maksimum kodun kullanımına dikkat çekmeliyiz; bir paketin paketleme yoğunluğu için üst sınırın temel gelişimi eşit toplarla yeniden boyutlandırılmış Öklid uzayı; mantık cebirinin bir fonksiyon sınıfının formülleriyle uygulamanın karmaşıklığını tahmin etmede eşitsizliğin (1) kullanımına ilişkin. Kodlama teorisinin fikirleri ve sonuçları, kendi kendini düzelten devrelerin ve güvenilmez elemanlardan güvenilir devrelerin sentezi problemlerinde daha fazla gelişmelerini bulur. Yanan: Shannon K., Bilgi teorisi ve sibernetik üzerine çalışmalar, çev. İngilizce'den, M., 1963; Berlekamp E., Cebirsel kodlama teorisi, çev. İngilizce'den, M., 1971; Peterson, W., Weldon, E., Hata düzeltme kodları, çev. İngilizce'den, 2. baskı, M., 1976; Ayrık Matematik ve Sibernetiğin Matematiksel Soruları, cilt 1, M., 1974, bölüm 5; Bassalygo L.A., Zyablov V.V., Pinsker M.S., "Bilgi aktarımı sorunları", 1977, cilt 13, No. 3, s. 517; [In] V. M. Sidelnikov, "Mat. Sat.", 1974, v. 95, c. 1, s. 148 58. V. I. Levenshtein.

Matematiksel ansiklopedi. - M.: Sovyet Ansiklopedisi. I.M. Vinogradov. 1977-1985.  ALFABETİK KODLAMA  COEUCLIDAN BOŞLUĞU Diğer sözlüklere de bakınız:  DECODING - bkz. Kodlama ve Kod Çözme ... Matematik Ansiklopedisi  Ses Kodlama - Bu makale wikified edilmelidir. Lütfen makaleleri biçimlendirme kurallarına göre biçimlendirin. Bir PC kullanarak ses kodlamasının temeli, hava titreşimlerini elektrik titreşimlerine dönüştürme işlemidir ... Wikipedia kod görüntüleri), tanıma göre gerçekleştirilir. kurallar, k ryh naz'ın bütünlüğü. şifre K., ... ... Felsefi Ansiklopedi  ​​BİLGİ KODLAMASI - mesaj öğeleri ve sinyaller arasında, bu öğelerin yardımıyla sabitlenebilecek bir yazışma kurmak. B bir mesaj öğeleri kümesi olsun, A sembolleri olan bir alfabe olsun, Sonlu bir sembol dizisi çağrılsın. tek kelimeyle ... ... Fiziksel Ansiklopedi  ​​OPTİMAL KODLAMA - (mühendislik psikolojisinde) (eng. optimal kodlama) bir insan operatör tarafından kontrol edilen bir nesne hakkında bilgi alma ve işleme konusunda maksimum hız ve güvenilirlik sağlayan kodların oluşturulması (bkz. Bilgi Alımı, Kod Çözme). K. o. sorunu ... ... Büyük psikolojik ansiklopedi  ​​DECODING (mühendislik psikolojisinde) - (İngilizce kod çözme) bir insan operatör tarafından bilgi alma sürecinin son işlemi, karakterize eden parametreleri yeniden şifrelemekten oluşan kontrol nesnesinin durumu ve bunları kontrol edilen nesnenin görüntüsüne çevirmek ( bkz. Kodlama ... ... Büyük psikolojik ansiklopedi

 Kod çözme - iletilen ve alınan sinyaller tarafından kodlanmış bir mesajın geri yüklenmesi (bkz. Kodlama) ... Ekonomi ve Matematik Sözlüğü  KODLAMA - KODLAMA. Konuşma üretmenin aşamalarından biri de "kod çözme", bir konuşma mesajını anlama süreci olan alım ve yorumlamadır. Psikodilbilime bakın... Yeni bir metodolojik terimler ve kavramlar sözlüğü (dil öğretimi teorisi ve pratiği)  KODLAMA - (İngilizce kodlama). 1. Bir sinyalin bir enerji biçiminden diğerine dönüştürülmesi 2. Bir sinyal veya işaret sisteminin diğerlerine dönüştürülmesi, genellikle "kod dönüştürme", "kod değişikliği" (konuşma için "çeviri") olarak da adlandırılır. 3. K. (anımsatıcı) ... ... Büyük psikolojik ansiklopedi  ​​Kod Çözme - Bu makale bilgi teorisindeki kod hakkındadır, bu kelimenin diğer anlamları için koda (anlam ayrımı) bakın. Kod, her belirli mesajı kesin olarak tanımlanmış bir sembol (karakter) (veya sinyal) kombinasyonuyla eşleştirmek için bir kuraldır (algoritma). Kod da denir... ... En uygun kodlama Aynı mesaj farklı şekillerde kodlanabilir. Optimal olarak kodlanmış bir kod, mesaj iletimi için minimum sürenin harcandığı koddur. Her temel karakterin (0 veya 1) iletimi aynı süreyi alıyorsa, en uygun kod, mümkün olan minimum uzunluğa sahip olacaktır. Örnek 1. Olasılık dağılımına sahip sekiz durumu olan bir X(x1,x2,x3,x4,x5,x6,x7,x8) rastgele değişkeni olsun. karakterler: Bu 000, 001, 010, 011, 100, 101, 110, 111 Bu kodun iyi olup olmadığını cevaplamak için, onu optimal değerle karşılaştırmanız, yani entropiyi belirlemeniz gerekir.

L fazlalığı L=1H/H0=12.75/3=0.084 formülü ile belirledikten sonra kod uzunluğunu %8.4 azaltmanın mümkün olduğunu görüyoruz. Soru ortaya çıkıyor: Her harf için ortalama olarak daha az temel karakter olacak bir kod oluşturmak mümkün mü? Bu tür kodlar var. Bunlar ShannonFano ve Huffman kodlarıdır. Optimal kodları oluşturma ilkesi: 1. Her temel karakter maksimum miktarda bilgi taşımalıdır, bunun için kodlanmış metindeki temel karakterlerin (0 ve 1) ortalama olarak eşit sıklıkta ortaya çıkması gerekir. Bu durumda entropi maksimum olacaktır. 2. Birincil alfabenin büyük olasılıkla daha yüksek olan harflerine ikincil alfabenin daha kısa kod sözcüklerinin atanması gerekir.