Kodlama teorisi. Kodlama türleri. Kodlama teorisinin doğuşu Kodlama yöntemlerinin sınıflandırılması

"Bu kursun amacı sizi teknik geleceğiniz için hazırlamaktır."

Merhaba, Habr. "Sen ve İşiniz" adlı harika makaleyi hatırlıyor musunuz (+219, 2442 yer imi, 394 bin okuma)?

Yani Hamming (evet, evet, kendi kendini kontrol eden ve kendi kendini düzelten Hamming kodları) onun derslerine dayanan bütün bir kitaba sahiptir. Çeviriyoruz, çünkü adam konuyu konuşuyor.

Bu kitap sadece BT ile ilgili değil, inanılmaz derecede havalı insanların düşünme tarzı hakkında bir kitap. “Bu sadece bir pozitif düşünce yükü değil; büyük işler yapma şansını artıran koşulları anlatıyor."

Halihazırda 28 (30 bölümden) bölümü tercüme ettik. Ve "kağıt üzerinde" yayın üzerinde çalışıyoruz.

Kodlama teorisi - I

Bilgisayarları ve nasıl çalıştıklarını düşündükten sonra, şimdi bilgi sunumu konusuna bakacağız: bilgisayarlar işlemek istediğimiz bilgiyi nasıl temsil ediyor. Herhangi bir karakterin anlamı, işlenme şekline bağlı olabilir, makinenin kullanılan bit için özel bir anlamı yoktur. 4. Bölümde yazılımın tarihçesini tartışırken, durdurma komutunun kodunun diğer komutların koduyla çakıştığı bazı sentetik programlama dillerini düşündük. Bu durum çoğu dil için tipiktir, talimatın anlamı ilgili program tarafından belirlenir.

Bilgi sunma problemini basitleştirmek için bilgiyi noktadan noktaya aktarma problemini ele alalım. Bu soru, bilgilerin korunması konusuyla ilgilidir. Zaman ve uzayda bilgi iletme sorunları aynıdır. Şekil 10.1 tipik bir iletişim modelini göstermektedir.

Şekil 10.1

Şekil 10.1'de solda bilgi kaynağıdır. Bir modeli düşünürken, kaynağın doğası umurumuzda değil. Dans hareketlerini temsil edebileceğimiz bir dizi alfabe sembolleri, sayılar, matematiksel formüller, müzik notaları, semboller olabilir - kaynağın doğası ve içinde saklanan sembollerin anlamı, aktarım modelinin bir parçası değildir. Biz sadece bilgi kaynağını dikkate alıyoruz, bu sınırlama ile birçok alana genişletilebilecek güçlü, genel bir teori elde ediliyor. Birçok uygulamadan bir soyutlamadır.

Shannon 1940'ların sonlarında bilgi teorisini yarattığında, bunun iletişim teorisi olarak adlandırılması gerektiğine inanılıyordu, ancak bilgi teriminde ısrar etti. Bu terim, teoride hem artan ilginin hem de sürekli hayal kırıklığının sabit bir kaynağı haline geldi. Müfettişler bütün "bilgi teorileri" oluşturmak istediler, semboller kümesi hakkında bir teoriye dönüştüler. İletim modeline dönersek, iletim için kodlanması gereken bir veri kaynağımız var.

Kodlayıcı iki bölümden oluşur, ilk parçaya kaynak kodlayıcı denir, tam adı kaynağın türüne bağlıdır. Farklı veri türlerinin kaynakları, farklı kodlayıcı türlerine karşılık gelir.

Kodlama işleminin ikinci kısmı kanal kodlama olarak adlandırılır ve veri iletim kanalının tipine bağlıdır. Böylece kodlama işleminin ikinci kısmı, iletim kanalının tipiyle eşleştirilir. Böylece standart arayüzler kullanılırken, kaynaktan gelen veriler önce arayüzün gereksinimlerine göre, ardından kullanılan veri iletim kanalının gereksinimlerine göre kodlanır.

Şekil 10.1'deki modele göre, veri bağlantısı “ekstra rastgele gürültüye” maruz kalmaktadır. Sistemdeki tüm gürültü bu noktada birleşir. Kodlayıcının tüm sembolleri bozulma olmadan aldığı ve kod çözücünün işlevini hatasız yaptığı varsayılır. Bu bir tür idealleştirmedir, ancak birçok pratik amaç için gerçeğe yakındır.

Kod çözme aşaması ayrıca iki aşamadan oluşur: kanal - standart, standart - veri alıcısı. Aktarım sonunda veriler tüketiciye aktarılır. Yine tüketicinin bu verileri nasıl yorumladığı sorusunu dikkate almıyoruz.

Daha önce belirtildiği gibi, örneğin telefon mesajları, radyo, TV programları gibi bir veri iletim sistemi, verileri bir bilgisayarın kayıtlarında bir dizi sayı olarak sunar. Yine uzaydaki iletimin, zamandaki iletimden veya bilginin depolanmasından farkı yoktur. Bir süre sonra gerekli olacak bilgileriniz var mı, daha sonra veri depolama kaynağında kodlanıp saklanması gerekir. Gerekirse bilgilerin kodu çözülür. Kodlama ve kod çözme sistemi aynıysa, verileri değişmeden iletim kanalı üzerinden iletiriz.

Fizikte sunulan teori ile geleneksel teori arasındaki temel fark, kaynakta ve alıcıda gürültü olmadığı varsayımıdır. Aslında, herhangi bir donanım parçasında hatalar meydana gelir. Kuantum mekaniğinde gürültü, bir başlangıç ​​koşulu olarak değil, belirsizlik ilkesine göre herhangi bir aşamada meydana gelir; her durumda, bilgi teorisindeki gürültü kavramı kuantum mekaniğindekine eşdeğer değildir.
Kesinlik için, sistemdeki veri gösteriminin ikili biçimini ayrıca ele alacağız. Diğer formlar da benzer şekilde ele alınır, basitlik adına onları dikkate almayacağız.

Ortak karakterlerin kısa ve nadir karakterlerin uzun olduğu klasik Mors nokta ve tire kodunda olduğu gibi, değişken uzunluklu kodlanmış karakterlere sahip sistemlere bakarak başlayalım. Bu yaklaşım, yüksek kod verimliliği elde etmenizi sağlar, ancak noktalar ve tireler arasında bir boşluk karakteri içerdiğinden, Mors kodunun ikili değil üçlü olduğunu belirtmekte fayda var. Koddaki tüm karakterler aynı uzunluktaysa, böyle bir koda blok kodu denir.

Kodun ilk bariz gerekli özelliği, bir mesajı gürültü olmadan açık bir şekilde deşifre etme yeteneğidir, en azından bu istenen bir özellik gibi görünmektedir, ancak bazı durumlarda bu gereklilik ihmal edilebilmektedir. İletim kanalından gelen veriler, alıcıya birler ve sıfırlar akışı gibi görünür.

İki bitişik simgeye çift açılım, üç bitişik simgeye üçlü açılım diyelim ve genel olarak, N sembol gönderirsek, alıcı N sembolün temel kodunun tamamlayıcısını görür. N'nin değerini bilmeyen alıcı, akışı çevrilmiş bloklara bölmelidir. Veya başka bir deyişle, alıcı, orijinal mesajı kurtarmak için akışı benzersiz bir şekilde ayrıştırabilmelidir.

Az sayıda karakter içeren, genellikle çok daha büyük alfabelerden oluşan bir alfabe düşünün. Dillerin alfabeleri, büyük ve küçük harfler, sayı işaretleri, noktalama işaretleri dahil olmak üzere 16 ila 36 karakterden başlar. Örneğin ASCII tablosunda 128 = 2 ^ 7 karakter.
4 karakterden oluşan özel bir kod düşünün s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Alıcının bir sonraki alınan ifadeyi nasıl yorumlaması gerektiği

Nasıl s1s1s4 veya nasıl s2s4?

Bu soruya net bir cevap veremezsiniz, bu kod kesinlikle çözülmemiştir, bu nedenle tatmin edici değildir. Öte yandan, kod

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Mesajın kodunu benzersiz bir şekilde çözer. Rastgele bir dize alalım ve alıcının onu nasıl çözeceğini görelim. Şekil 10.II'deki forma göre bir kod çözme ağacı oluşturmanız gerekir. Hat

1101000010011011100010100110 …

Karakter bloklarına bölünebilir

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

Bir kod çözme ağacı oluşturmak için aşağıdaki kurala göre:

Ağacın tepesindeyseniz, bir sonraki karakteri okursunuz. Ağacın yaprağına ulaştığınızda diziyi bir karaktere çevirir ve başlangıca geri dönersiniz.

Böyle bir ağacın var olmasının nedeni, hiçbir karakterin diğerinin öneki olmamasıdır, bu nedenle her zaman kod çözme ağacının başına ne zaman geri döneceğinizi bilirsiniz.

Aşağıdakilere dikkat etmek gereklidir. İlk olarak, kod çözme, her bitin yalnızca bir kez incelendiği katı bir akış sürecidir. İkincisi, protokoller genellikle kod çözme işleminin sonunu işaretleyen ve mesajın sonunu belirtmek için gerekli olan karakterleri içerir.

Sondaki karakterin kullanılmasından kaçınmak, kod tasarımında yaygın bir hatadır. Elbette, sabit bir kod çözme modu sağlanabilir, bu durumda takip eden sembole gerek yoktur.

Şekil 10.II

Sonraki soru, akış (anlık) kod çözme kodlarıdır. Karakterleri görüntüleyerek bir öncekinden elde edilen kodu düşünün.

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Diyelim ki sırayı aldık 011111...111 ... Mesaj metninin kodunu çözmenin tek yolu, gruptaki bitleri sondan 3'e kadar gruplamak ve başında sıfır olan grupları seçmektir, bundan sonra kodunu çözebilirsiniz. Böyle bir kodun kodu benzersiz bir şekilde çözülebilir, ancak anında değil! Kodu çözmek için iletimin sonuna kadar beklemeniz gerekir! Pratikte, bu yaklaşım kod çözme hızını (McMillan teoremi) olumsuzlar, bu nedenle anında kod çözme yollarını aramak gerekir.

Aynı karakteri, Si'yi kodlamanın iki yolunu düşünün:

s1 = 0; s2 = 10; s3 = 110; s4 = 1110, s5 = 1111,

Bu yöntem için kod çözme ağacı Şekil 10.III'de gösterilmektedir.

Şekil 10.III

ikinci yol

s1 = 00; s2 = 01; s3 = 100; s4 = 110, s5 = 111,

Bu ayrılmanın kod çözme ağacı Şekil 10.IV'de gösterilmiştir.

Kod kalitesini ölçmenin en belirgin yolu, bir dizi mesaj için ortalama uzunluktur. Bunu yapmak için, her karakterin kodunun uzunluğunu, karşılık gelen pi oluşma olasılığı ile çarparak hesaplamak gerekir. Bu, tüm kodun uzunluğunu verecektir. q karakterlik bir alfabe için ortalama kod uzunluğu L formülü aşağıdaki gibidir.

pi, si karakterinin ortaya çıkma olasılığı olduğunda, li, kodlanmış karakterin karşılık gelen uzunluğudur. Etkin bir kod için L değeri mümkün olduğunca küçük olmalıdır. P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 ve p5 = 1/16 ise, kod # 1 için kod uzunluğunun değerini alırız.

Ve 2 numaralı kod için

Elde edilen değerler ilk kodun tercihini gösterir.
Alfabedeki tüm kelimelerin oluşma olasılığı aynıysa, ikinci kod tercih edilir. Örneğin, pi = 1/5 ile # 1 kodunun uzunluğu

Ve 2 numaralı kodun uzunluğu

Bu sonuç 2 kodun tercih edildiğini göstermektedir. Bu nedenle, "iyi" kod tasarlanırken, sembollerin ortaya çıkma olasılığı dikkate alınmalıdır.

Şekil 10.IV

Şekil 10.V

Karakter kod uzunluğu li'nin sınırlayıcı değerini belirleyen Kraft eşitsizliğini göz önünde bulundurun. Temel 2'ye dayanarak, eşitsizlik şu şekilde temsil edilir:

Bu eşitsizlik, alfabede çok fazla kısa sembol olamayacağı anlamına gelir, aksi takdirde toplam oldukça büyük olacaktır.

Herhangi bir hızlı benzersiz kod çözme kodu için Kraft'ın eşitsizliğini kanıtlamak için bir kod çözme ağacı oluşturuyoruz ve matematiksel tümevarım yöntemini uyguluyoruz. Bir ağacın bir veya iki yaprağı varsa, Şekil 10.V'de gösterildiği gibi, o zaman eşitsizlik şüphesiz doğrudur. Ayrıca, ağacın ikiden fazla yaprağı varsa, uzun m ağacını iki alt ağaca böleriz. Tümevarım ilkesine göre, eşitsizliğin yüksekliği m -1 veya daha az olan her dal için doğru olduğunu varsayıyoruz. Tümevarım ilkesine göre eşitsizliği her bir dal için uygulamak. K "ve K" " dallarının kodlarının uzunluklarını gösterelim. Ağacın iki dalı birleştirildiğinde, her birinin uzunluğu 1 artar, bu nedenle, kodun uzunluğu K' / 2 toplamlarından oluşur. ve K '' / 2,

Teorem ispatlandı.

Macmillan teoreminin kanıtını düşünün. Kraft'ın eşitsizliğini aerodinamik olmayan kod çözme kodlarına uyguluyoruz. Kanıt, herhangi bir K> 1 sayısı için, sayının n'inci kuvvetinin, n'nin oldukça büyük bir sayı olduğu yerde, n'nin doğrusal bir fonksiyonundan kesinlikle daha büyük olduğu gerçeğine dayanmaktadır. Kraft'ın eşitsizliğini n'inci kuvvete yükseltiyoruz ve ifadeyi bir toplam olarak temsil ediyoruz.

Nk, k uzunluğundaki karakter sayısı olduğunda, toplama, n'inci karakter gösteriminin minimum uzunluğu ile başlar ve maksimum uzunluk nl ile biter; burada l, kodlanmış karakterin maksimum uzunluğudur. Benzersiz kod çözme gereksiniminden kaynaklanmaktadır. Tutar formda sunulur

K> 1 ise, eşitsizliğin yanlış olması için n'yi yeterince büyük ayarlamak gerekir. Bu nedenle, k<= 1; теорема Макмиллана доказана.

Kraft eşitsizliğinin uygulanmasına ilişkin birkaç örnek düşünün. 1, 3, 3, 3 uzunluklarında benzersiz bir şekilde kodu çözülmüş bir kod olabilir mi? Evet, o zamandan beri

1, 2, 2, 3 uzunlukları ne olacak? Formüle göre hesaplayın

Eşitsizlik ihlal ediliyor! Bu kodda çok fazla kısa karakter var.

Nokta kodları (virgül kodları), tamamından oluşan son karakter dışında 0 karakterle biten 1 karakterden oluşan kodlardır. Özel durumlardan biri koddur.

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5 = 11111.

Bu kod için Kraft eşitsizliği ifadesini elde ederiz.

Bu durumda eşitlik elde ederiz. Nokta kodları için Kraft eşitsizliğinin bir eşitliğe dönüştüğünü görmek kolaydır.

Kodu oluştururken Kraft miktarına dikkat etmeniz gerekiyor. Kraft toplamı 1'i geçmeye başlarsa, bu, ortalama kod uzunluğunu azaltmak için farklı uzunlukta bir karakter ekleme ihtiyacı hakkında bir sinyaldir.

Unutulmamalıdır ki Kraft'ın eşitsizliği, bu kodun benzersiz bir şekilde deşifre edildiği anlamına gelmez, ancak bu uzunlukta karakterlere sahip, benzersiz bir şekilde deşifre edilen bir kod olduğu anlamına gelir. Benzersiz bir kodu çözülmüş kod oluşturmak için, bit li cinsinden karşılık gelen uzunluğa bir ikili sayı atayabilirsiniz. Örneğin, 2, 2, 3, 3, 4, 4, 4, 4 uzunlukları için Kraft eşitsizliğini elde ederiz.

Bu nedenle, böyle benzersiz bir kodu çözülmüş akış kodu mevcut olabilir.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

Fikir alışverişinde bulunduğumuzda gerçekte neler olduğuna dikkatinizi çekmek istiyorum. Örneğin, şu anda kafamdan sizinkine bir fikir aktarmak istiyorum. Bu fikri anlayabileceğinize (alabileceğinize) inandığım bazı kelimeler telaffuz ediyorum.

Ancak daha sonra bu fikri arkadaşınıza iletmek istediğinizde, neredeyse kesinlikle tamamen farklı kelimeler söyleyeceksiniz. Gerçekte, anlam veya anlam, belirli kelimelerle sınırlı değildir. Bazı kelimeler kullandım, ancak aynı fikri iletmek için tamamen farklı kelimeler kullanabilirsiniz. Böylece farklı kelimeler aynı bilgiyi aktarabilir. Ancak, muhatabınıza mesajı anlamadığınızı söyler söylemez, o zaman bir kural olarak, anlamı iletmek için, muhatap ikinci veya hatta üçüncü bir kelime grubu seçecektir. Bu nedenle, bilgi belirli bir kelime kümesinde yer almaz. Bunları veya bu kelimeleri aldıktan sonra, kelimeleri muhatabın size iletmek istediği fikre çevirmek için harika bir iş yapın.

Muhataplara uyum sağlamak için kelimeleri seçmeyi öğreniyoruz. Bu karşılaştırma, kod çözme sürecinde gürültüyü temsil etmek için kullandığım modeli tam olarak yansıtmasa da, bir anlamda, düşüncelerimizi ve kanaldaki gürültü seviyesini eşleştirerek kelimeleri seçiyoruz. Büyük organizasyonlarda, diğer kişinin ne dediğini duyamama büyük bir sorundur. Üst düzey pozisyonlarda çalışanlar “duymak istediklerini” duyarlar. Bazı durumlarda, kariyer basamaklarını tırmanırken bunu aklınızda tutmanız gerekir. Bilginin biçimsel bir biçimde sunulması, süreçlerin hayatımızdan kısmi bir yansımasıdır ve bilgisayar uygulamalarında biçimsel kuralların sınırlarının çok ötesinde geniş uygulama alanı bulmuştur.

Devam edecek...

Kitabın çevirisi, düzeni ve yayınlanması konusunda kim yardım etmek ister - kişisel olarak veya e-postayla yazın [e-posta korumalı]

Bu arada, başka bir harika kitabın çevirisini de başlattık -

kodlama Temel konseptler.

Çok eski zamanlardan beri insan pratiğinde çeşitli kodlama yöntemleri yaygın olarak kullanılmaktadır. Örneğin, ondalık konum gösterimi, doğal sayıları kodlamanın bir yoludur. Doğal sayıları kodlamanın başka bir yolu da Romen rakamlarıdır ve bu yöntem daha görsel ve doğaldır, aslında parmak - I, beş - V, iki beş - X. Ancak, bu kodlama yöntemiyle aritmetik işlemleri yapmak daha zordur. büyük sayılarda, bu nedenle konumsal ondalık gösterime dayalı yöntem kodlaması ile değiştirildi. Bu örnekten, çeşitli kodlama yöntemlerinin, kodlama hedeflerine bağlı olarak, belirli bir kodlama yönteminin avantajı veya dezavantajı olabilen, yalnızca kendilerine özgü belirli özelliklere sahip olduğu sonucuna varabiliriz.

Geometrik nesnelerin sayısal kodlama yöntemleri ve uzaydaki konumları yaygın olarak bilinmektedir: Kartezyen koordinatlar ve kutupsal koordinatlar. Ve bu kodlama yöntemleri, kendilerine özgü belirli özellikleri bakımından farklılık gösterir.

20. yüzyıla kadar kodlama yöntemleri ve araçları yardımcı bir rol oynadı, ancak bilgisayarların ortaya çıkmasıyla durum kökten değişti. Kodlama, bilgi teknolojisinde yaygın olarak kullanılmaktadır ve genellikle aşağıdakiler gibi çeşitli sorunların çözümünde merkezi bir konudur:

- bilgisayar belleğinde keyfi nitelikteki verilerin (sayılar, metin, grafikler) sunumu;

- iletişim kanalları üzerinden optimal veri aktarımı;

- bilgilerin (mesajların) yetkisiz erişime karşı korunması;

- iletişim kanalları aracılığıyla veri aktarımı sırasında gürültü bağışıklığının sağlanması;

- bilgilerin sıkıştırılması.

Bilgi teorisi açısından, kodlama, bir mesaj kaynağının alfabesinin ve belirli bir kurala göre yürütülen belirli bir koşullu sembol kümesinin açık bir şekilde karşılaştırılması işlemidir ve bir kod (kod alfabesi) tam bir kümedir. Orijinal mesajı kodlamak için kullanılabilen ve verilen kodlama kuralıyla mümkün olan farklı koşullu sembollerin (kod sembollerinin) (kümesi). Kod alfabesini oluşturan farklı kod sembollerinin sayısına kodun hacmi veya kod alfabesinin hacmi denir. Açıkçası, kod alfabesinin hacmi, kodlanan orijinal mesajın alfabesinin hacminden daha az olamaz. Bu nedenle kodlama, orijinal mesajın, iletişim kanalı üzerinden iletilen mesajı temsil eden bir kod sembolleri koleksiyonuna veya dizisine dönüştürülmesidir.

Kodlama, kod sembollerinin temsil edildiği türe bağlı olarak sayısal (dijital) ve sayısal olmayan olabilir: sırasıyla herhangi bir sayı sistemindeki sayılar veya diğer bazı nesneler veya işaretler.

Çoğu durumda, kod sembolleri, en basit bileşenlerin bazılarının bir koleksiyonu veya dizisidir, örneğin, bir kod sembolünün öğeleri olarak adlandırılan sayısal bir kodun kod sembollerindeki bir sayı dizisi. Bir kod sözcüğündeki bir öğenin konumu veya seri numarası, konumuna göre belirlenir.

Mesajların orijinal kaynağının alfabesinin bir karakterini temsil etmek için kullanılan kod karakterinin eleman sayısına kod değeri denir. Kodun değeri, orijinal mesajın alfabesinin tüm sembolleri için aynıysa, kod tek tip, aksi halde düzensiz olarak adlandırılır. Kod sembolüne dahil edilen öğelerin sayısı bazen kod sembolünün uzunluğu olarak adlandırılır.

Artıklık açısından, tüm kodlar yedekli olmayan kodlar ve yedekli kodlar olarak ikiye ayrılabilir. Fazlalıklı kodlarda, kalan elemanların daha verimli kullanılması nedeniyle kod sembollerinin eleman sayısı azaltılabilir, yedekli olmayan kodlarda ise kod sembollerindeki eleman sayısının azaltılması mümkün değildir.

Girişim yokluğunda ve onların varlığında kodlama sorunları önemli ölçüde farklıdır. Bu nedenle, verimli (entropi) kodlama ile düzeltici (hata düzeltici) kodlama arasında bir ayrım yapılır. Etkili kodlama ile görev, kodun fazlalığını azaltarak, mesaj kaynağının alfabesinin bir karakteri başına ortalama olarak minimum sayıda kod sembolü öğesi ile mesaj kaynağının alfabe karakterlerinin temsilini sağlamaktır. mesaj iletim hızında bir artış. Ve düzeltici (hata düzeltici) kodlama ile görev, kodun ek fazlalığını ekleyerek hataları tespit edip düzelterek orijinal alfabenin sembollerinin iletimindeki hata olasılığını azaltmaktır.

Ayrı bir kodlama görevi, mesajları yetkisiz erişime, bozulmaya ve imhaya karşı korumaktır. Bu tür kodlamayla, mesajlar öyle bir şekilde kodlanır ki, onları almış olsa bile, bir saldırgan onları çözemez. Bu tür mesaj kodlama işlemine şifreleme (veya şifreleme) denir ve şifre çözme işlemine şifre çözme (veya şifre çözme) denir. Kodlanmış mesajın kendisine şifreli (veya basitçe şifreleme) denir ve kullanılan kodlama yöntemine şifre denir.

Çoğu zaman, kodlama yöntemleri, orijinal mesaja kıyasla daha kısa uzunlukta mesaj kodlarının (bilgi kaybı olmadan) oluşturulmasına izin veren ayrı bir sınıfa ayrılır. Bu tür kodlama tekniklerine sıkıştırma veya veri paketleme teknikleri denir. Sıkıştırma kalitesi, genellikle yüzde olarak ölçülen ve kodlanmış mesajın ne kadarının orijinalden daha kısa olduğunu gösteren sıkıştırma oranı ile belirlenir.

Bir bilgisayar kullanarak bilgilerin otomatik olarak işlenmesinde, kural olarak, sayısal (dijital) kodlama kullanılır ve doğal olarak, kullanılan sayı sistemini doğrulama sorusu ortaya çıkar. Gerçekten de, sayı sisteminin tabanında bir azalma ile, kod sembollerinin elemanlarının alfabesi basitleştirilir, ancak kod sembolleri uzar. Öte yandan, sayı sisteminin tabanı ne kadar büyük olursa, bir kod sembolünü temsil etmek için gereken basamak sayısı o kadar az olur ve sonuç olarak, iletimi için o kadar az zaman olur, ancak sayı sisteminin tabanının büyümesiyle birlikte, iletişim kanalları ve temel sinyalleri tanımaya yönelik teknik araçlar için gereksinimler, kod sembollerinin çeşitli öğelerine karşılık gelen önemli ölçüde artar. Özellikle ikili sistemde yazılan bir sayının kodu, ondalık koddan ortalama olarak yaklaşık 3,5 kat daha uzundur. Tüm bilgi işleme sistemlerinde büyük bilgi dizilerini sayısal bilgi biçiminde depolamak gerektiğinden, sayısal kodun sembollerinin öğelerinin alfabesini seçmek için temel kriterlerden biri (yani, kullanılan sayı sisteminin temeli) ) depolama cihazlarındaki elektronik elemanların sayısını, sadeliğini ve güvenilirliğini en aza indirmektir.

Kod sembollerinin her bir elemanını sabitlemek için gereken elektronik elemanların sayısını belirlerken, bunun için tabana eşit en basit elektronik elemanların (örneğin, transistörlerin) sayısını gerektirdiği pratik olarak doğrulanmış varsayımdan hareket etmek gerekir. sayı sistemi a... Sonra bazı cihazlarda depolamak için n kod karakter öğeleri gerekli olacak m elektronik elemanlar:

M = bir n. (2.1)

Bu cihaza kaydedilebilecek en fazla sayıda farklı numara n:

N = bir n.

Bu ifadenin logaritmasını almak ve ondan ifade etmek n elde ederiz:

n= ln n/ ln a.

(2.1) ifadesini forma dönüştürme

m= bir ∙ içinde n/ ln a(2.2)

logaritmaların hangi temelinde belirlenebilir a element miktarı m verilen için minimum olacak n... tarafından farklılaştırılarak a işlev M = f(a) ve türevini sıfıra eşitleyerek şunu elde ederiz:

Açıkçası, herhangi bir sonlu için a

içinde n/ ln 2 bir ≠ 0

ve bu nedenle

içinde a - 1 = 0,

nerede a = e ≈ 2.7.

Radix yalnızca bir tamsayı olabileceğinden, o zaman a 2 veya 3'e eşit seçilir. Örneğin, depolama cihazının maksimum kapasitesini ayarlayalım. n= 10 6 sayı. Daha sonra sayı sistemlerinin farklı tabanları için ( a) element miktarı ( m) böyle bir depolama aygıtında, (2.2) ifadesine uygun olarak aşağıdakiler olacaktır (Tablo 2.1):

Tablo 2.1.

a
m	39,2	38,2	39,2	42,9		91,2

Dolayısıyla ekipman miktarının minimizasyonundan yola çıkarsak en avantajlısı bu parametrede birbirine yakın olan ikili, üçlü ve dörtlü sayı sistemleri olacaktır. Ancak ikili sayı sisteminde çalışan cihazların teknik uygulaması çok daha basit olduğundan, sayısal kodlamada en yaygın olanı 2 tabanlı sayı sistemine dayalı kodlardır.

Mesajları, onları yansıtan sinyallerle tanımlamanın yollarını araştıran bir bilgi teorisi dalıdır. Kodlama teorisinin görevi, bilgi kaynağını iletişim kanalıyla eşleştirmektir.

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

Ters işlem - kod çözme - alınan mesajı kodlanmış biçimden tüketicinin kullanabileceği genel olarak kabul edilene geri yüklemekten oluşur.

Kodlama teorisinde birkaç yön vardır:

• statik veya verimli kodlama;
• sıkışma önleyici kodlama;
• düzeltici kodlar;
• döngüsel kodlar;
• aritmetik kodlar.

Kontrol sistemlerinin, özellikle bilgisayarların ortaya çıkmasıyla, kodlama olmadan bilgi aktarımı 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 bilgisayar teknolojisinin yaygın kullanımı ile bağlantılı olarak, yeni bir bilgi alanı ortaya çıkmıştır - 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, bir mesajın sembolik biçiminden diğerine açık bir şekilde dönüştürmek için kullanılan bir kuraldır.

Tüm kod sözcükleri aynı uzunluğa sahipse, 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üştürme kodu bir tür ikamedir.

A alfabesinin olduğu yerde, 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, belirli bir alfabeye dahil edilen karakter dizileridir. Metin kodlaması, temel aldığı alfabenin ikili kodlamasına indirgenir. Alfabenin en yaygın kullanılan bayt kodlaması. Bu durumda, alfabenin maksimum kardinalitesi 256 karakterdir. Böyle bir alfabe, iki grup alfabetik karakter (örneğin, Rusça ve Latince), sayılar, noktalama işaretleri ve matematiksel işaretler, 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 artık uluslararası iletişimin artan ihtiyaçlarını karşılamamaktadır. Evrensel 16 bit karakter kodlama sistemi UNICODE 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 satırlık bir tablo oluşturur. . Bu tabloda, bir milyondan fazla farklı karakteri barındırabilen bir milyondan fazla hücre vardır. Bunlar, "ölü" dillerin simgelerinin yanı sıra sözcüksel içeriği olmayan simgeler, 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 sembolleri için evrensel bir kodlama sistemidir ve önemli ölçüde genişleme yeteneğine 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 verileri temsil etmek için ikili 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 hassasiyeti ve baskı teknolojisinin yetenekleri ile tutarlıdır.

Renkli görüntüleri kodlarken, bileşenlere renk ayrıştırma 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 renklerle parlayan birbirine yakın üç öğeden oluşur.

Bu prensibi kullanan renkli ekranlara RGB monitörler denir.

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

renk oluşum şeması

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

			Kahverengi

24 bit renk derinliğinde renk oluşumu:

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. Bire eşit bit derinliğine sahip bir pikselin yalnızca 2 (birinci güçte) olası durumu vardır - iki renk: siyah veya beyaz. Bit derinliği 8 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 bit görüntülerin, çevremizdeki dünyanın renklerini doğru bir şekilde yeniden ürettiğine inanılmaktadır. Tipik olarak, bit çözünürlüğü 1 ila 48 bit / piksel aralığında belirtilir.

Kağıda yazdırırken, biraz farklı bir renk modeli kullanılır: monitör ışık yayarsa, renklerin eklenmesi sonucunda renk tonu elde edilir, ardından boyalar ışığı emer, renkler çıkarılır. Bu nedenle cam göbeği (Cyan, C), macenta (Macenta, M) ve sarı (Sarı, Y) boyalar ana boyalar olarak kullanılmaktadır. Ek olarak, boyaların kusurlu olması nedeniyle, genellikle bunlara dördüncü 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 gösterimi 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

Ses bilgisiyle çalışma teknikleri en son bilgisayar teknolojisine geldi. Herhangi bir ses sinyaline uygulanabilen analitik bir kodlama yöntemi, analogdan dijitale dönüştürmeye dayanır. Orijinal analog sinyal, ikili kodda kaydedilen bir dizi dijital sinyal olarak temsil edilir. Dönüştürme biti, tek bir dijital sinyale karşılık gelen veri miktarını belirler. Ses çalarken, ters dijitalden analoğa dönüştürme işlemini gerçekleştirin.

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

Tablolu sentez kodlama yöntemi yalnızca bir müzik parçasına uygulanabilir. Çeşitli müzik aletlerinin seslerinin örnekleri (örnekleri) hazırlanan tablolarda saklanır. Sayısal kodlar enstrümanı, notayı ve süreyi tanımlar.

Bir video sinyalini kodlarken, bir dizi görüntü (kare) ve ses (film müziği) kaydetmeniz gerekir. Video kayıt formatı, her iki veri akışının da tek bir dijital diziye dahil edilmesini sağlar.

04.04.2006 Leonid Chernyak Kategori: Teknoloji

"Açık Sistemler" Sinyal kodlama teorisi, "görünüşleri ile aynı anda 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.

"Açık Sistemler"

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

Kodlama teorisi, hesaplamanın gelişimini belirgin şekilde etkileyen matematiğin alanlarından biridir. Kapsamı, verilerin gerçek (veya gürültülü) kanallar aracılığıyla iletilmesine kadar uzanır ve konu, iletilen bilgilerin doğruluğunu sağlamaktır. Başka bir deyişle, bir sinyal iletildikten sonra yararlı bilgilerin güvenilir ve basit bir şekilde veriden çıkarılabilmesi için verileri en iyi nasıl paketleyeceğini öğrenir. Bazen kodlama teorisi şifreleme ile karıştırılır, ancak bu doğru değildir: kriptografi tam tersi sorunu çözer, amacı verilerden bilgi elde etmeyi zorlaştırmaktır.

Verileri kodlama ihtiyacı, ilk olarak 150 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 şiddetlendi. 1845'ten beri özel kod kitapları kullanılmaya başlandı; telgraf operatörleri tarafından mesajları manuel olarak "sıkıştırmak" için kullanıldılar ve ortak kelime dizilerini daha kısa kodlarla değiştirdiler. Aynı zamanda, iletimin doğruluğunu kontrol etmek için, birinci ve ikinci nesil bilgisayarlarda da delikli kartların doğruluğunu kontrol etmek için kullanılan bir yöntem olan eşlik kontrolünü kullanmaya başladılar. Bunu yapmak için, eklenmekte olan güverteye 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 saklananla eşleşene kadar giriş prosedürü tekrarlandı. Bu şema sadece garip olmakla kalmaz, aynı zamanda çift hataları da 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 yıldızıydı, ABD akademik seçkinlerinden biriydi. Vannevar Bush'un yüksek lisans öğrencisi olarak 1940 yılında Nobel Ödülü'nü aldı (Nobel Ödülü ile karıştırılmamalıdır!), 30 yaşın altındaki bilim insanlarına verildi. Shannon, Bell Laboratuarlarındayken, The Mathematical Theory of Message Transmission (1948) adlı kitabını yazdı ve burada kanalın bant genişliğinin mesaj kaynağının entropisinden daha yüksek olması durumunda, mesajın kodlanarak iletilebileceğini gösterdi. gereksiz gecikmeler 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'daki memleketinde dikilen Shannon'a mütevazı bir anıt üzerine oyulmuş C = W log ((P + N) / N formülü, Albert Einstein'ın E = mc 2 formülü ile değer olarak karşılaştırılır.

Shannon'ın çalışmaları, bilgi teorisi alanında daha fazla araştırma için yiyecek sağladı, ancak pratik mühendislik uygulamaları yoktu. Teoriden pratiğe geçiş, Shannon'ın Bell Laboratuarlarından bir meslektaşı olan ve "Hamming kodları" olarak adlandırılan bir kod sınıfının keşfiyle ünlenen Richard Hamming'in çabalarıyla mümkün oldu. Hamming kodlarının icadının, 40'lı yılların ortalarında Bell Model V röle hesap makinesinde delikli kartlarla çalışmanın zorluğundan kaynaklandığına 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ı. Ancak Hamming, bilgisayarlardaki veri iletim hatları da dahil olmak üzere, öncelikle işlemci ve bellek arasındaki iletişim kanallarındaki hataları düzeltebilecek kodlar önerdi. Hamming kodları, Shannon teoremlerinin işaret ettiği olasılıkların pratikte nasıl gerçekleştirilebileceğinin kanıtını sağlar.

Hamming makalesini 1950'de yayınladı, ancak kodlama teorisi dahili raporlarda 1947'ye kadar uzanıyor. Bu nedenle, bazıları Hamming'in Shannon değil, kodlama teorisinin babası olarak görülmesi gerektiğine inanıyor. Ancak teknoloji tarihinde ilkini aramak boşunadır.

Kesin olan, Hata Düzeltme Kodunu (ECC) ilk önerenin Hamming olduğudur. Bu kodların modern modifikasyonları, tüm veri depolama sistemlerinde ve işlemci ile ana bellek arasında değiş tokuş için kullanılır. Varyantlarından biri olan Reed-Solomon kodları CD'lerde kullanılır ve kayıtları gıcırtı ve çiziklere ve toz parçacıklarına neden olabilecek gürültü olmadan çalmanıza izin verir. 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 uzun mesafeli uzay iletişiminin geliştirilmesiyle bağlantılı olarak özel bir önem kazanmıştır; örneğin, yedi bilgi biti için 32 kontrol biti veya altı için 26 kontrol biti bulunan Reed-Muller kodları vardır.

En yeni ECC kodları arasında LDPC (Düşük Yoğunluklu Parite Kontrol Kodu) kodları bulunur. Aslında, otuz yıldır biliniyorlar, ancak onlara özel bir ilgi, tam olarak yüksek çözünürlüklü televizyonun gelişmeye başladığı son yıllarda ortaya çıktı. LDPC kodları %100 doğru değildir ancak hata oranı istenilen seviyeye ayarlanabilir ve bant genişliğinden mümkün olduğunca yararlanılır. Onlara yakın olan "Turbo Kodlar", derin uzayda ve sınırlı bant genişliğinde nesnelerle çalışırken etkilidirler.

Vladimir Aleksandrovich Kotelnikov'un adı, kodlama teorisi tarihine sıkı sıkıya yazılmıştır. 1933'te, "İletişimin teknik olarak yeniden yapılandırılması üzerine Birinci Tüm Birlik Kongresi için radyo iletişimiyle ilgili malzemeler" de, "Havanın bant genişliği hakkında mı?" Çalışmasını yayınladı. ve? tel?" Kodlama teorisinin en önemli teoremlerinden birinin başlığında Kotelnikov'un adı eşittir. 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 isimlerle adlandırılır. Bazı kaynaklar hem Nyquist-Shannon örnekleme teoremini hem de Whittaker-Shannon örnekleme teoremini kullanır ve Rus üniversite ders kitaplarında en yaygın olanı basitçe “Kotelnikov teoremi”dir. 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 katkısını 1915'te yaptı. 1920'de Japon Kinnosuki Ogura, Whittaker'ın araştırmasında değişiklikler yayınladı ve 1928'de Amerikalı Harry Nyquist, bir analog sinyali sayısallaştırma ve kurtarma ilkelerini netleştirdi.

Claude Shannon(1916 - 2001) okul yıllarından itibaren matematik ve elektrik mühendisliğine eşit ilgi gösterdi. 1932'de Michigan Üniversitesi'ne girdi, 1936'da Massachusetts Teknoloji Enstitüsü'nden 1940'ta mezun oldu ve iki derece aldı - elektrik mühendisliğinde yüksek lisans ve matematikte 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 formüle edildiği, özellikle entropi yoluyla bilgi miktarının belirlenmesinin formüle edildiği "Matematiksel iletişim teorisi" adlı bir makale yayınladı ve ayrıca iki seçimini belirleyen bir bilgi birimi önerdi. eşit derecede olası seçenekler, yani daha sonra biraz denilen şey ... 1957-1961'de Shannon, şimdi adını taşıyan gürültülü iletişim kanallarının kapasitesi hakkındaki teoremi kanıtladığı eserler yayınladı. 1957'de Shannon, 21 yıl sonra emekli olduğu Massachusetts Teknoloji Enstitüsü'nde profesör oldu. Shannon, "hak ettiği emekliliği" üzerine, uzun süredir devam eden hokkabazlık tutkusuna tamamen teslim oldu. Birkaç hokkabazlık makinesi yaptı ve hatta genel bir hokkabazlık teorisi geliştirdi.

Richard Hamming'in fotoğrafı.(1915 - 1998) eğitimine 1937'de lisans derecesini aldığı Chicago Üniversitesi'nde başladı. 1939'da Nebraska Üniversitesi'nden yüksek lisans derecesini ve Illinois Üniversitesi'nden matematik alanında doktora derecesini aldı. 1945'te Hamming, atom bombasını oluşturmak için büyük ölçekli bir hükümet araştırma projesi olan Manhattan Projesi'nin bir parçası olarak çalışmaya başladı. 1946'da Hamming, Claude Shannon ile birlikte çalıştığı Bell Telefon Laboratuvarlarında çalışmaya başladı. 1976'da Hamming, Monterey, California'daki Naval Graduate School'da bir sandalye aldı.

Onu ünlü yapan çalışma, hata bulma ve düzeltme kodlarının temel çalışması, 1950'de Hamming tarafından yayınlandı. 1956'da IBM 650'nin ilk ana bilgisayarlarından biri üzerinde çalıştı. Çalışmaları, daha sonra üst düzey programlama dillerine dönüşecek olan bir programlama dilinin temellerini attı. Hamming'in bilgisayar bilimlerindeki başarılarını takdir etmek için, IEEE, onun adını verdiği Enformatik ve Sistem Teorisi Üstün Hizmet Madalyası'nı kurdu.

Vladimir Kotelnikov(1908 - 2005) 1926'da N.E.Bauman (MVTU) adını taşıyan Moskova Yüksek Teknik Okulu Elektrik Mühendisliği Fakültesine girdi, ancak MVTU'dan bağımsız bir enstitü olarak ayrılan Moskova Güç Mühendisliği Enstitüsü'nden (MEI) mezun oldu. Kotelnikov, lisansüstü çalışmaları sırasında (1931-1933) daha sonra kendi adını alacak olan "sayma teoremini" matematiksel olarak formüle etti ve kanıtladı. 1933'te yüksek lisans okulundan mezun olduktan sonra, Kotelnikov, MPEI'de öğretmenlik yapmaya devam ederken, Merkezi Bilimsel Araştırma İletişim Enstitüsü'nde (TsNIIS) çalışmaya başladı. 1941'de V.A.Kotelnikov, matematiksel olarak deşifre edilemeyen bir sistemin hangi gereksinimleri karşılaması gerektiğine dair açık bir ifade formüle etti ve şifresinin çözülmesinin imkansızlığının bir kanıtı verildi. 1944'te Kotelnikov, 1980'e kadar çalıştığı MPEI radyo mühendisliği fakültesinin dekanı profesör olarak görev aldı. 1953'te 45 yaşındayken 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

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 görülmedi, ancak bilgisayarların ortaya çıkmasıyla durum kökten değişti. Kodlama, kelimenin tam anlamıyla bilgi teknolojisine nüfuz eder ve çeşitli (neredeyse tüm) programlama problemlerinin çözümünde merkezi bir konudur: ۞ bilgisayar belleğinde keyfi nitelikteki verilerin (örneğin, sayılar, metin, grafikler) sunumu; ۞ bilgilerin yetkisiz erişime karşı korunması; ۞ iletişim kanalları aracılığıyla 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ı onları temsil eden sinyallerle tanımlamanın yollarını araştıran bilgi teorisinin bir dalıdır. Amaç: Bilgi kaynağını iletişim kanalıyla koordine etmek. Nesne: Bir bilgi kaynağı aracılığıyla tüketiciye gelen kesikli 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ı, bilgiyi belirli bir iletişim kanalı üzerinden iletilmeye uygun bir forma dönüştürmek anlamına gelir. Kod çözme - alınan bir mesajın kodlanmış bir formdan tüketiciye sunulan bir forma geri yüklenmesi.

Konu 5.2. Alfabetik kodlama Genel olarak kodlama problemi aşağıdaki gibi gösterilebilir. Sonlu sayıda sembolden oluşan iki A ve B alfabesi verilsin: ve. Alfabenin elemanlarına harf denir. A alfabesindeki sıralı bir küme, n = l () = | ile gösterilen bir kelime olarak adlandırılacaktır. |. , n sayısı kelimedeki harf sayısını gösterir ve kelimenin uzunluğu olarak adlandırılır, Boş bir kelime belirtilir: Bir kelime için, a1 harfine kelimenin başlangıcı veya öneki denir, an harfi kelimenin sonu veya son eki. , ve Kelimeler bağlanabilir. Bunu yapmak için, ikinci kelimenin öneki, ilk kelimenin son ekini hemen takip etmelidir, yeni kelimede, kelimelerden biri boş olmadığı sürece, doğal olarak durumlarını kaybederler. Sözcüklerin bağlantısı ve belirtilir, ayrıca n özdeş sözcüklerin bağlantısı belirtilir. A alfabesinin boş olmayan tüm sözcüklerinin kümesi A ile gösterilecektir *: A Grubuna mesajların alfabesi ve 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österiyoruz. Daha sonra kelimeye kelimenin kodu denir. Kodlama, mesaj öğeleri ve sinyaller arasında, bu öğelerin sabitlenebileceği bir yazışma sistemi biçiminde depolanması, iletilmesi ve işlenmesi sırasında bilgi 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ı olmadan, açık bir şekilde dönüştürülmesi (yani bir işlev) 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 ters fonksiyonudur, yani. F1. word'e Herhangi bir kodlama için kod çözme işleminin yapılması gerektiğinden, eşleme tersine çevrilebilir (bijeksiyon) olmalıdır. | B | = m ise, F'ye m. kodlama denir, en yaygın durum B = (0, 1) ikili kodlamadır. Aşağıda bu durum ele alınmaktadır. Tüm kod sözcükleri aynı uzunluğa sahipse, kod tek tip veya blok olarak adlandırılır. Alfabetik (veya harf harf) kodlama bir kod tablosu ile belirtilebilir. Bir tür ikame, bir kod veya kodlama işlevi görecektir. Sonra, nerede,. Bu tür harf harf kodlama, bir dizi temel kod olarak belirtilir. Alfabetik kodlama, herhangi bir mesaj kümesi için kullanılabilir. Bu nedenle, 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 ikili bir ondalık kodlamadır, bire birdir ve bu nedenle kodu çözülebilir. Ancak, şema bire bir değildir. Örneğin, altı birlik 111111 kümesi, 333 veya 77 kelimesini veya 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ıştırılabiliyorsa, alfabetik kodlama şeması ayrılabilir olarak adlandırılır. 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ılabilirse eşitsizlik doğrudur ÖRNEK Alfabetik kodlama şeması A = (a, b) ve B = (0, 1) ayrılabilirdir, çünkü ve bu nedenle Macmillan eşitsizliği sağlanır. 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, genellikle ek bilgiler mevcuttur. Örneğin, doğal dilde sunulan mesajlar için, bu tür ek bilgiler, mesajda görünen harflerin 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 atandığına ve mesajdaki harflerin bileşimine bağlıdır. Belirli bir mesaj ve belirli bir kodlama şeması belirtilirse, mesaj kodunun uzunluğunun minimum olacağı böyle bir kod permütasyonu seçilebilir. Sabit bir mesaj S kodunun uzunluğunun sabit bir şema için minimum olacağı temel kodları atama algoritması: ۞ 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 şekilde yerleştirin. Alfabenin ve harflerin mesajda görünme olasılıklarının verilmesine izin verin:

Burada pi, ai harfinin oluşma olasılığıdır ve mesajda bulunma olasılığı sıfır olan harfler hariç tutulur ve harfler, ÖRNEK olarak belirtilen ve tanımlanan mesajın oluşma olasılıklarına göre azalan sıraya göre sıralanır. Ayrılabilir bir alfabetik kodlama şeması için A = (a, b), B = (0,1), bir olasılık dağılımı ile, kodlama maliyeti ve bir olasılık dağılımı ile, 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 yalnızca üç öğeden 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 kodlamamız gerekiyor. Aralığı böldük, 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, для к­рого существует декодер,состоящий из регист

bir kayma ve bir çoğunluk unsuru ve bir hatayı düzeltme sırası vardır ((2) ile karşılaştırın). Matematiksel olarak. Kodlayıcı ve kod çözücü modelleri genellikle işlevsel elemanların şemasından düşünülür ve karmaşıklık devredeki eleman sayısı olarak anlaşılır. Hata düzeltmeli bilinen kod sınıfları için, algoritmalar ve algoritmalar için olası algoritmaların bir çalışması gerçekleştirilir ve kodlayıcı ve kod çözücünün karmaşıklığı için üst sınırlar elde edilir. Kodlama aktarım hızı, kodlama gürültüsü bağışıklığı ve kod çözücü karmaşıklığı arasında da bazı ilişkiler bulunmuştur (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ığı, ancak sonsuz (Kn) kod dizilerinin varlığına ilişkin teoremleri temsil ettiği gerçeğiyle bağlantılıdır. bu, l uzunluğundaki keyfi bir kelimenin bir anda bir kümeye ait olduğunu ve l'ye göre daha yavaş bir büyüme sırasına sahip olduğunu tanıyan bir Turing makinesinin bulunduğu bu tür kod dizilerinin (Kn) sınıfıyla sonuçlanır. örneğin, llog l). Kodlama teorisinde geliştirilen bazı yeni yapılar ve sınırlar elde etme 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 fonksiyonlarını gerçekleştirmek için asimptotik olarak optimal bir yöntemde bir hatanın düzeltilmesi ile maksimum bir kodun kullanılmasına işaret etmek gerekir; prensipte, yeniden paketleme yoğunluğu için üst sınırın iyileştirilmesi. eşit toplarla boyutlu Öklid uzayı; mantık cebirinin bir fonksiyon sınıfının formülleriyle uygulamanın karmaşıklığını tahmin ederken eşitsizliğin kullanımı (1). Kodlama teorisinin fikirleri ve sonuçları, kendi kendini düzelten devreleri ve güvenilmez elemanlardan güvenilir devreleri sentezleme problemlerinde daha fazla gelişmelerini bulur. Yanan: Shannon K., Bilgi teorisi ve sibernetik üzerine çalışmalar, çev. İngilizceden., 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 problemleri, v.1, Moskova, 1974, bölüm 5; Bassalygo L.A., Zyablov V.V., Pinsker M.S, "Olası Bilgi iletimi", 1977, v. 13, no. 3, s. 517; [V] Sidelnikov VM, "Mat. Sb.", 1974, cilt 95, v. 1, s. 148 58. V. I. Levenshtein.

Matematik Ansiklopedisi. - M.: Sovyet ansiklopedisi. I.M. Vinogradov. 1977-1985.  ALFABETİK KODLAMA  COEUCLIDE SPACE Diğer sözlüklere de bakınız:  DECODING - bkz. Kodlama ve kod çözme ... Matematik Ansiklopedisi  Ses bilgilerini kodlama - Bu makale wikified olmalıdır. Lütfen makale biçimlendirme kurallarına göre doldurunuz. Bir PC kullanarak ses kodlaması, tanım gereği taahhüt edilen hava titreşimlerini elektrik titreşimlerine dönüştürme sürecine dayanır ... Wikipedia kod görüntüleri. kurallar, agregaya rykh denir. şifre K., ... ... Felsefi Ansiklopedi  ​​BİLGİ KODLAMA - mesaj öğeleri ve sinyaller arasında, bu öğelerin yardımıyla sabitlenebilecek yazışmaların kurulması. B, mesajın öğeleri kümesi, A sembollerle alfabe, Sonlu semboller dizisi olarak adlandırılsın. kelime ... ... Fiziksel ansiklopedi  ​​OPTİMAL KODLAMA - (mühendislik psikolojisinde) (İngilizce optimal kodlama) bir insan operatörü tarafından bir kontrol nesnesi hakkında bilgi alma ve işlemenin maksimum hızını ve güvenilirliğini sağlayan kodların oluşturulması (bkz. Bilgi Alımı, Kod Çözme). K. o. sorunu ... ... Büyük psikolojik ansiklopedi  ​​DECODING (mühendislik psikolojisinde) - (tur bkz. Kodlama ... ... Büyük psikolojik ansiklopedi

 Kod çözme - iletilen ve alınan sinyaller tarafından kodlanmış bir mesajın kurtarılması (bkz. Kodlama) ... Ekonomi ve Matematik Sözlüğü  KODLAMA - KODLAMA. Konuşma üretiminin 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 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ğerine dönüştürülmesi, buna genellikle "dönüştürme", "kod değişikliği" (konuşma için "çeviri") de denir. 3. K. (anımsatıcı) ... ... Büyük Psikoloji Ansiklopedisi  Kod Çözme - Bu makale bilgi teorisindeki kod hakkındadır, bu kelimenin diğer anlamları için koda (anlamlar) bakın. Kod, her belirli mesajı kesin olarak tanımlanmış bir sembol (işaret) (veya sinyal) kombinasyonuyla eşleştirmek için bir kuraldır (algoritma). Kod olarak da adlandırılır ... ... En uygun kodlama Aynı mesaj farklı şekillerde kodlanabilir. Optimal olarak kodlanmış, mesaj iletimi için minimum sürenin harcandığı bir kod olarak kabul edilecektir. Her temel sembolün (0 veya 1) iletimi aynı süreyi alıyorsa, en uygun kod, mümkün olan minimum uzunluğa sahip olacaktır. Örnek 1. Bir 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. 000, 001, 010, 011, 100, 101, 110 , 111 Bu kodun iyi olup olmadığını cevaplamak için, onu en uygun değerle karşılaştırmanız, yani entropiyi belirlemeniz gerekir.

L fazlalığını L = 1H / H0 = 12.75 / 3 = 0.084 formülüne göre belirledikten sonra kod uzunluğunu %8.4 azaltmanın mümkün olduğunu görüyoruz. Soru ortaya çıkıyor: bir harfin ortalama olarak daha az temel karakter olacağı 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 sembol maksimum miktarda bilgi taşımalıdır, bunun için kodlanmış metindeki temel sembollerin (0 ve 1) ortalama olarak eşit sıklıkta ortaya çıkması gerekir. Bu durumda entropi maksimum olacaktır. 2. İkincil alfabenin daha kısa kod sözcüklerini, birincil alfabenin yüksek olasılıklı harflerine atamak gerekir.