Өмнө дурьдсанчлан мэдээллийг үр дүнтэй кодлохын тулд мессежийн статистик хамаарлыг харгалзан үзэх шаардлагатай. Бидний ойрын зорилго бол хамааралтай мессежийн дарааллын мэдээллийн шинж чанарыг хэрхэн тооцоолох талаар сурах явдал юм. Хоёр мессежээр эхэлье.

Чуулгануудыг авч үзье X= {x i) Мөн Ю={y j) болон тэдний ажил XY={(x i,y j), П(x i,y j)). Аливаа тогтмол хувьд y jÎ Юбарьж болно нөхцөлт хуваарилалтмагадлал П(x i/y j) багц дээр Xмөн хүн бүрт x iÎ Xөөрийнхөө мэдээллийг тооцоолно

гэж нэрлэдэг нөхцөлт өөрийн мэдээлэлзурвасууд x iтогтмол үед y j.

Өмнө нь бид чуулгын энтропи гэж нэрлэдэг байсан Xмессежийн дундаж мэдээлэл x iÎ X. Үүний нэгэн адил нөхцөлт мэдээллийг дундажлана I(x i/y j) By x iÎ X, бид үнэ цэнийг авдаг

,

нөхцөлт энтропи гэж нэрлэдэг Xтогтмол үед y jÎ Ю. гэдгийг анхаарна уу энэ тодорхойлолтхэзээ нь тодорхойгүй байна П(x i/y j)=0. Хэлбэрийн илэрхийлэл гэдгийг тэмдэглэх нь зүйтэй zбүртгэл zгэж тэглэх хандлагатай байна z® 0 ба үүний үндсэн дээр бид үсэгнүүдэд тохирох энтропийн нэр томъёог тоолно x iмагадлалаар П(x i/y j)=0, тэгтэй тэнцүү.

Шинээр нэвтрүүлсэн энтропи Х(X/y j) нь санамсаргүй хэмжигдэхүүнээс хамаардаг учир санамсаргүй хэмжигдэхүүн юм y j. Хос магадлалын чуулгын санамсаргүй бус мэдээллийн шинж чанарыг олж авахын тулд бүх утгын дундажийг хийх шаардлагатай. y j .Хэмжээ

дуудсан нөхцөлт энтропичуулга Xтогтмол чуулгатай Ю. Нөхцөлт энтропийн хэд хэдэн шинж чанарыг тэмдэглэе.

2. , ба тэгш байдал нь зөвхөн чуулга бүрдсэн тохиолдолд л үүсдэг XТэгээд Юбие даасан.

5. Түүгээр ч барахгүй чуулга бүрдвэл тэгш байдал бий болно XТэгээд Юбүх хүнд нөхцөлт бие даасан байдал зО З.

Ярилцъя" физик утга» нөхцөлт энтропийн шинж чанарыг томъёолсон. 2-р шинж чанар нь чуулгын нөхцөлт энтропи нь түүний болзолгүй энтропиас хэтрэхгүй гэж заасан. 5-р өмч нь энэхүү мэдэгдлийг бэхжүүлж байна. Үүнээс үзэхэд нөхцөлт энтропи нь нөхцлийн тоо нэмэгдэх тусам нэмэгдэхгүй. Энэ хоёр баримт нь гайхмаар зүйл биш юм; нэмэлт мэдээлэлчуулгын тухай X, бусад чуулгын мессежүүдэд агуулагдсан, дунджаар,чуулгын мэдээллийн агуулгыг (тодорхойгүй) бууруулдаг X. Тэмдэглэл" дунджаар"Энд маш чухал, учир нь тэгш бус байдал H( X/y j) ≤ H( X), ерөнхийдөө үнэн биш юм.

1-5-р шинж чанарууд нь тэгш бус байдлыг илэрхийлдэг

, (11.4)

гагцхүү чуулга хамтран бие даасан байх тохиолдолд тэгш эрх боломжтой X 1 , …, Xn.

Энтропийг тооцоолох нь эх үсгийг дамжуулах эсвэл хадгалах зардлыг тооцоолох явдал гэдгийг санаарай. Нөхцөлт энтропийн шинж чанарууд нь захидал дамжуулахдаа үүнийг харуулж байна Xn+ 1 өмнөх үсэг гэдгийг ашиглах ёстой X 1 , …, Xnхүлээн авагч талд аль хэдийн мэдэгдэж байна. Энэ нь оронд нь зөвшөөрөх болно Х(Xn+1) арай бага зарцуулдаг Х(Xn +1 /X 1 ,…,Xn) бит. Үүний зэрэгцээ тэгш бус байдал (11.4) нь эдийн засгийн кодчилолд өөр хандлагыг харуулж байна. Энэ тэгш бус байдлаас харахад кодчилол хийхээс өмнө үсгүүдийг блок болгон нэгтгэх ёстой бөгөөд эдгээр блокуудыг шинэ "өргөтгөсөн" эхийн үсэг гэж үзэх ёстой. Зардал нь үсгийн бие даасан кодчилолтой харьцуулахад бага байх болно. Хоёр аргын аль нь илүү үр дүнтэй вэ?

Доор бид илүү нарийвчлалтай өгөх болно тоон шинж чанарэдгээр хоёр хандлага, гэхдээ үүнээс өмнө бид магадлалын онолын зарим тодорхойлолтыг эргэн санах хэрэгтэй.

Цаашид танилцуулахын тулд бидэнд магадлалын онолын зарим мэдэгдэж байгаа мэдээлэл хэрэгтэй болно.

1) Санамсаргүй үйл явдлын чуулгын магадлалын шинж чанарууд АТэгээд IN:

P(A,B)=P(A)*P(B/A); -> P(B/A)=P(A,B)/P(B);

P(A,B)=P(B)*P(B/A); -> P(A/B)=P(A,B)/P(A);

P(A/B)=P(A)*P(B/A)/P(B);

P(B/A)=P(B)*P(A/B)/P(A); АТэгээд INХэрэв

бие даасан, тэгвэл

P(A/B)=P(A); P(B/A)=P(B):

P(A,B)=P(A)*P(B);

Дахин хэлэхэд, салангид мессежийн эх сурвалжийн хувьд Шеннон энтропийн тодорхойлолт:

Түүний шинж чанарууд: ;

H > 0Нм;

сүх = лог N Бие даасан эх сурвалжийн тусламжтайгаар;

H(A,B)=H(A)+H(B)

НӨХЦӨТ ЭНТРОПИ Хэрэв системийн элементүүдийн төлөв байдал нь бие биенээсээ хамаардаггүй эсвэл нэг системийн төлөв нь нөгөө системийн төлөвөөс хамаардаггүй бол системийн зарим элемент (эсвэл зарим систем) аль нэгэнд байх нь тодорхойгүй байна. боломжит төлөвүүдийг системийн бие даасан элементүүдийн магадлалын шинж чанараар бүрэн тодорхойлох болно. Энэ тохиолдолдтодорхой хэмжээ

Системийн элементийн төлөв эсвэл мессежийн тэмдэгт бүрийн мэдээллийг дундаж энтропи гэж нэрлэдэг бөгөөд үүнийг тооцоолохдоо илэрхийлэлийг ашигладаг. Мессежийн тэмдэгт ногдох мэдээллийн дундаж хэмжээг тооцоолохдоо харилцан хамаарлыг харгалзан үзнэ.

Зарим үйл явдлууд бусадтай харьцуулахад тохиолдох нөхцөлт магадлал ба үүнээс үүссэн энтропийг нөхцөлт энтропи гэж нэрлэдэг. Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 1 , б 2 - Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 2 а Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 1 гэх мэт. Энэ тохиолдолд хөндлөнгийн оролцоотой сувгийн хувьд дамжуулалт гажуудсан, тэмдэг хүлээн авах үед б 1 . Магадгүй дүрүүд нь дамжуулагдсан байж магадгүй юм б 2 , б 3 гэх мэт.

Гажуудлыг нөхцөлт сувгийн магадлалын матрицаар тодорхойлно П(А/ Б)={ х(б би / Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг би }.

Дуу чимээ бүхий холбооны сувгаар дохио дамжуулах үйл явцыг авч үзээд нөхцөлт энтропийг тооцоолох механизмыг ойлгоход ашиглацгаая.

Хэрэв мессежийн эх үүсвэр нь тэмдэгтүүдийг үүсгэдэг

б л , А 2 , ..., a би ..., А n

магадлалын дагуу

х(а 1 ), х (а 2 ) ... ..., х (а би ), ..., х (а n ),

дамжуулах сувгийн гаралт дээр бид тэмдэгтүүдийг хүлээн авдаг

Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 1 ,б 2 , ..., б би ..., б n

магадлалын дагуу

p(Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 1 ), p (Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 2 ), ..., х (б би , ..., p (Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг n ),

дараа нь нөхцөлт энтропийн тухай ойлголт H (B/б би ) илгээх замаар юуны тодорхойгүй байдлыг илэрхийлдэг б би , бид авах болно Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг би., үзэл баримтлал Х(А/б би ) хүлээн авсны дараа үлддэг тодорхойгүй байдал Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг би яг юу илгээсэн б би. Үүнийг дээрх зурагт графикаар харуулав. Хэрэв харилцаа холбооны сувагт хөндлөнгийн оролцоо байгаа бол аль ч дохиог янз бүрийн магадлалаар хүлээн авах боломжтой. Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг j ба эсрэгээр, хүлээн авсан дохио Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг jаль нэг дохиог илгээсний үр дүнд гарч ирж болно б би . Хэрэв харилцаа холбооны сувагт хөндлөнгийн оролцоо байхгүй бол илгээсэн тэмдэг нь үргэлж байдаг А 1 хүлээн зөвшөөрөгдсөн тэмдэгттэй таарч байна Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 1 , А 2 -б 2 , ..., А n -б n .

Энэ тохиолдолд H(A) мессежийн эх үүсвэрийн энтропи нь H(B) мессеж хүлээн авагчийн энтропитэй тэнцүү байна.. Хэрэв харилцаа холбооны сувагт хөндлөнгийн оролцоо байгаа бол энэ нь дамжуулагдсан мэдээллийн зарим хэсгийг устгах эсвэл гажуудуулдаг.

Мэдээллийн алдагдлыг хувийн болон ерөнхий нөхцөлт энтропигоор бүрэн дүрсэлдэг. Сувгийн матрицыг ашиглан хэсэгчилсэн болон ерөнхий нөхцөлт энтропийг тооцоолоход тохиромжтой. "Сувгийн матриц" гэсэн нэр томъёо нь: статистикийн хувьд тодорхойлсон матриц энэ сувагхолболт, товчлолд ашигласан. Хэрэв харилцаа холбооны сувгийг мессежийн эх үүсвэрийн талаас тодорхойлсон бол (жишээ нь илгээсэн дохио нь мэдэгдэж байгаа бол) дохио дамжуулах үед гарах магадлал. б би хөндлөнгийн оролцоотой холбооны сувгаар бид дохио хүлээн авах болно Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг j нөхцөлт магадлал гэж тэмдэглэсэн p(б j /ai).мөн сувгийн матриц нь хэлбэртэй байна

Диагональ (томоор) дагуу байрлах магадлал нь зөв хүлээн авах магадлалыг тодорхойлдог, үлдсэн хэсэг нь худал юм. Сувгийн матрицын баганыг дүүргэх цифрүүдийн утга нь гол диагональаас холдох тусам буурдаг бөгөөд хөндлөнгийн оролцоо бүрэн байхгүй тохиолдолд үндсэн диагональ дээр байрлах цифрүүдээс бусад нь тэгтэй тэнцүү байна.

Тэмдгийг дамжуулж байна б биөгөгдсөн холбооны суваг дахь мессежийн эх үүсвэрээс тухайн хэлбэрийн нөхцөлт магадлалын хуваарилалтаар тодорхойлогддог p(б j /а би ), магадлалын нийлбэр үргэлж нэгтэй тэнцүү байх ёстой. Жишээлбэл, дохионы хувьд А 1

Нэг дохионы хувьцааны мэдээллийн алдагдал а бихэсэгчилсэн нөхцөлт энтропи ашиглан тайлбарласан болно. Жишээлбэл, дохионы хувьд а 1

Дүн дүнгийн дагуу гүйцэтгэнэ j,учир нь би-р муж (д энэ тохиолдолдэхний) тогтмол хэвээр байна.

Дамжуулах алдагдал бүх дохиоӨгөгдсөн холбооны сувгийг ерөнхий нөхцөлт энтропи ашиглан тайлбарлав. Үүнийг тооцоолохын тулд та бүх хэсэгчилсэн нөхцөлт энтропийг нэгтгэн дүгнэх хэрэгтэй, өөрөөр хэлбэл давхар нийлбэрийг хийх хэрэгтэй. биболон өөр j.

Мэдээллийн эх тэмдэг үүсэх магадлал тэгш бус тохиолдолд тэмдэг тус бүрийн харагдах магадлалыг түүнд тохирох хэсэгчилсэн нөхцөлт энтропийг үржүүлэх замаар харгалзан үзнэ. Энэ тохиолдолд нийт нөхцөлт энтропи

Нөхцөл байдлыг гаднаас нь шинжвэл мессеж хүлээн авагч(энэ нь хүлээн авсан дохио мэдэгдэж байх үед) , дараа нь тэмдгийн хүлээн авсан хамт Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг jтэмдэгтүүдийн аль нэгийг илгээсэн гэж таамаглаж байна б 1 , б 2 , …, б би ,…, б Н. Энэ тохиолдолд сувгийн матриц нь дараах хэлбэртэй байна.

Энэ тохиолдолд нөхцөлт магадлалын нийлбэр нь мөрөнд биш, харин сувгийн матрицын баганад нэгтэй тэнцүү байх ёстой.

Хэсэгчилсэн нөхцөлт энтропи

Мөн нийт нөхцөлт энтропи

Системийн нийт нөхцөлт энтропиА системтэй харьцуулахад B нь судалж буй системийн элементүүдийн төлөвийг илэрхийлэх мессежийн эх сурвалжийн аль ч тэмдэгт агуулагдах мэдээллийн хэмжээг тодорхойлдог.

Ерөнхий нөхцөлт энтропи нь бүх тэмдэгтүүдийн дунджаар тодорхойлогддог. А битус бүрийн тохиолдох магадлалыг харгалзан. Энэ нь эх тэмдгийн харагдах магадлал ба хаяг хүлээн авагч тэмдгийг хүлээн авсны дараа үлдэх тодорхойгүй байдлын үржвэрийн нийлбэртэй тэнцүү байна.

Хэрэв харилцаа холбооны сувагт хөндлөнгийн оролцоо байхгүй бол үндсэн диагональ дээр байрлахаас бусад сувгийн матрицын бүх элементүүд тэгтэй тэнцүү байна. Энэ нь дохио дамжуулах үед гэдгийг харуулж байна А 1 бид гарцаагүй авна Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 1 дамжуулах үед А 2 - Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 2 , ..., А Н - Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг Н. Зөв дохио хүлээн авах магадлал өндөр болно болзолгүй, болон нөхцөлт энтропи тэг болно.

Тэмдгийг дамжуулах үед нөхцөлт энтропи хамгийн дээд хэмжээндээ хүрдэг А бимагадгүй хамт тэнцүү магадлалхүлээн авсан дохионы аль нэг нь Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 1 , Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг 2 , ..., Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг Н .

Нөхцөлт энтропи

Энтропи (мэдээллийн)- мэдээллийн эмх замбараагүй байдлын хэмжүүр, анхдагч цагаан толгойн аль ч тэмдгийн харагдах байдлын тодорхойгүй байдал. Мэдээллийн алдагдал байхгүй тохиолдолд энэ нь дамжуулагдсан мессежийн нэг тэмдэгт ногдох мэдээллийн хэмжээтэй тэнцүү байна.

Жишээлбэл, орос хэл дээрх өгүүлбэрийг бүрдүүлж буй үсгүүдийн дарааллаар: өөр өөр үсэгөөр өөр давтамжтай гарч ирдэг тул тохиолдлын тодорхойгүй байдал нь зарим үсгүүдийн хувьд бусдаас бага байдаг. Хэрэв бид үсгийн зарим хослолыг анхаарч үзвэл (энэ тохиолдолд бид энтропийн тухай ярьдаг n-р дараалал, харна уу) нь маш ховор тохиолддог, дараа нь тодорхойгүй байдал улам бүр багасдаг.

Мэдээллийн энтропийн тухай ойлголтыг харуулахын тулд Максвеллийн чөтгөр гэж нэрлэгддэг термодинамик энтропийн талбараас жишээ авч болно. Мэдээлэл ба энтропи гэсэн ойлголтууд нь хоорондоо гүн гүнзгий холбоотой боловч үүнийг үл харгалзан онолын хөгжил статистик механикмөн мэдээллийн онол нь тэдгээрийг хоорондоо нийцүүлэхийн тулд олон жил зарцуулсан.

Албан ёсны тодорхойлолтууд

Мэдээллийн энтропибие даасан санамсаргүй үйл явдлын хувьд x-тай n боломжит нөхцөл(1-ээс n)-ийг дараах томъёогоор тооцоолно.

Энэ хэмжээг мөн нэрлэдэг мессежийн дундаж энтропи. Тоо хэмжээ гэж нэрлэдэг хувийн энтропи, зөвхөн шинж чанар би- e муж.

Тиймээс үйл явдлын энтропи xнийлбэр нь байна эсрэг тэмдэгбүх ажил харьцангуй давтамжуудүйл явдал тохиолдох би, өөрсдийн хоёртын логарифмаар үржүүлсэн (2-р суурийг зөвхөн хоёртын хэлбэрээр танилцуулсан мэдээлэлтэй ажиллахад хялбар болгох үүднээс сонгосон). Дискрет санамсаргүй үйл явдлын энэхүү тодорхойлолтыг магадлалын тархалтын функц болгон өргөжүүлж болно.

Ерөнхийдөө Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг-арийн энтропи(Хаана Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэгтэнцүү 2, 3, ...) эх цагаан толгойтой эх ба салангид хуваарилалтмагадлал хаана х бимагадлал юм б би (х би = х(б би) ) дараах томъёогоор тодорхойлогдоно.

Шеннон энтропийн тодорхойлолт нь термодинамик энтропи гэсэн ойлголттой холбоотой. Больцманн, Гиббс нар хийсэн гайхалтай ажил By статистик термодинамик, энэ нь "энтропи" гэдэг үгийг батлахад хувь нэмэр оруулсан мэдээллийн онол. Термодинамик ба мэдээллийн энтропи хоёрын хооронд холбоо байдаг. Жишээлбэл, Максвеллийн чөтгөр мөн адил ялгаатай байдаг термодинамик энтропимэдээлэл, ямар ч хэмжээний мэдээлэл олж авах нь алдагдсан энтропитэй тэнцэнэ.

Альтернатив тодорхойлолт

Энтропийн функцийг тодорхойлох өөр нэг арга Хүүний нотолгоо юм Хгагцхүү хэрвээ л өвөрмөц байдлаар тодорхойлогддог (өмнө дурдсанчлан). Хнөхцөлийг хангаж байна:

Үл хөдлөх хөрөнгө

Энтропи нь контекстээр тодорхойлогдсон хэмжигдэхүүн гэдгийг санах нь чухал магадлалын загвармэдээллийн эх сурвалжийн хувьд. Жишээлбэл, зоос шидэх нь энтропи − 2(0.5log 2 0.5) = 1 бит (бие даасан гэж үзвэл) байна. Зөвхөн "А" үсгүүдээс бүрдэх стринг үүсгэдэг эх үүсвэр нь тэг энтропитэй байна: . Жишээлбэл, энтропийг туршилтаар тогтоож болно Англи хэл дээрх тексттэмдэгт бүрт 1.5 биттэй тэнцүү бөгөөд энэ нь мэдээж өөр өөр текстийн хувьд өөр өөр байх болно. Өгөгдлийн эх үүсвэрийн энтропийн зэрэг нь мэдээллийг алдагдуулахгүйгээр, оновчтой кодчилолтойгоор шифрлэхэд шаардагдах өгөгдлийн элементэд ногдох битийн дундаж тоог хэлнэ.

1. Зарим өгөгдлийн бит мэдээлэл зөөхгүй байж болно. Жишээлбэл, өгөгдлийн бүтэц нь ихэвчлэн илүүдэл мэдээллийг хадгалдаг эсвэл өгөгдлийн бүтэц дэх мэдээллээс үл хамааран ижил хэсгүүдтэй байдаг.
2. Энтропийн хэмжээг үргэлж битийн бүхэл тоогоор илэрхийлдэггүй.

Математик шинж чанарууд

Үр ашиг

Практикт тааралдсан анхны цагаан толгойн магадлалын хуваарилалт, энэ нь оновчтой байдлаас хол байна. Хэрэв анхны цагаан толгой нь байсан бол nтэмдэгтүүд байвал магадлалын тархалт нь жигд байдаг "оновчтой цагаан толгой"-той харьцуулж болно. Анхны болон оновчтой цагаан толгойн энтропийн харьцаа нь эх үсгийн үр ашиг бөгөөд үүнийг хувиар илэрхийлж болно.

Үүнээс үзэхэд анхны цагаан толгойн үр дүнтэй байдал nТэмдэгтүүдийг түүнтэй тэнцүү гэж тодорхойлж болно n-арийн энтропи.

Энтропи нь онолын хувьд ердийн багц эсвэл практикт Хаффман кодчилол, Лемпел-Зив-Велч кодчилол эсвэл арифметик кодчилол ашиглан хийж болох хамгийн их алдагдалгүй (эсвэл бараг алдагдалгүй) шахалтыг хязгаарладаг.

Хувилбар ба ерөнхий дүгнэлт

Нөхцөлт энтропи

Хэрэв цагаан толгойн тэмдэгтүүдийн дараалал нь бие даасан биш бол (жишээлбэл, Франц"q" үсгийн ард бараг үргэлж "у" үсэг ордог бөгөөд "дэвшилтэт" гэсэн үг байдаг Зөвлөлтийн сонинуудАраас нь ихэвчлэн "үйлдвэрлэл" эсвэл "хөдөлмөр" гэсэн үг байдаг), ийм тэмдэгтүүдийн дарааллаар (тиймээс энтропи) зөөвөрлөх мэдээллийн хэмжээ бага байх нь ойлгомжтой. Ийм баримтыг харгалзан үзэхийн тулд нөхцөлт энтропи ашигладаг.

Нэгдүгээр эрэмбийн нөхцөлт энтропи (Марковын нэгдүгээр эрэмбийн загвартай төстэй) нь цагаан толгойн үсгийн энтропи бөгөөд нэг үсэг дараалан гарч ирэх магадлал (өөрөөр хэлбэл хоёр үсэгний хослолын магадлал) мэдэгдэж байна.

Хаана биөмнөх тэмдэгтээс хамааралтай төлөв байдал бөгөөд х би (j) - энэ бол магадлал j, тэгсэн тохиолдолд биөмнөх дүр байсан.

Тиймээс "" үсэггүй орос хэлний хувьд.

Шуугиантай суваг дахь өгөгдөл дамжуулах явцад мэдээллийн алдагдлыг хэсэгчилсэн болон ерөнхий нөхцөлт энтропиээр бүрэн дүрсэлсэн болно. Энэ зорилгоор гэж нэрлэгддэг сувгийн матрицууд. Тиймээс, эх үүсвэрийн алдагдлыг тодорхойлохын тулд (өөрөөр хэлбэл илгээсэн дохио нь мэдэгдэж байгаа) хүлээн авагч тэмдэг хүлээн авах нөхцөлт магадлалыг анхаарч үзээрэй. Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг jдүрийг илгээсэн тохиолдолд б би. Энэ тохиолдолд сувгийн матриц дараах хэлбэртэй байна.

Мэдээжийн хэрэг диагональ дагуу байрлах магадлал нь зөв хүлээн авах магадлалыг тодорхойлдог бөгөөд баганын бүх элементүүдийн нийлбэр нь хүлээн авагчийн талд харгалзах тэмдэг гарч ирэх магадлалыг өгөх болно. х(Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг j) . Дамжуулсан дохионы алдагдал б би, хэсэгчилсэн нөхцөлт энтропигоор тодорхойлогддог:

Бүх дохионы дамжуулалтын алдагдлыг тооцоолохын тулд ерөнхий нөхцөлт энтропийг ашиглана.

Энэ нь хүлээн авагч талын энтропийг ижил төстэй байдлаар авч үздэг гэсэн үг юм: үүнийг хаа сайгүй зааж өгсөн болно (шугамын элементүүдийг нэгтгэн авч болно; х(б би) , диагональ элементүүд нь хүлээн авсан тэмдэгтийг яг илгээсэн байх магадлалыг, өөрөөр хэлбэл зөв дамжуулах магадлалыг хэлнэ).

Харилцан энтропи

Харилцан энтропи, эсвэл нэгдлийн энтропи, нь хоорондоо холбогдсон системүүдийн энтропийг (статистикийн хамааралтай мэдээллүүдийн хамтарсан тохиолдлын энтропи) тооцоолоход зориулагдсан бөгөөд үүнийг тэмдэглэнэ. Х(АБ), Хаана А, урьдын адил, дамжуулагчийг тодорхойлдог, мөн Б- хүлээн авагч.

Дамжуулсан болон хүлээн авсан дохионы хоорондын хамаарлыг магадлалаар тодорхойлно хамтарсан арга хэмжээ х(б би Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг j) , болон төлөө бүрэн тайлбарсувгийн шинж чанар, зөвхөн нэг матриц шаардлагатай:

Илүү ихийг ерөнхий тохиолдол, Хэрэв энэ нь тайлбарлаж буй суваг биш, харин зүгээр л харилцан үйлчилдэг системүүд байх үед матриц нь дөрвөлжин байх албагүй. Мэдээжийн хэрэг, тоо бүхий баганын бүх элементүүдийн нийлбэр jөгөх болно х(Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг j) , мөрийн дугаарын нийлбэр биБайна х(б би) , мөн бүх матрицын элементүүдийн нийлбэр нь 1-тэй тэнцүү байна. Хамтарсан магадлал х(б би Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг j) үйл явдал б биТэгээд Мэдээлэл дамжуулах сувгаар санамсаргүй A тэмдгийн эх үүсвэрээс мессеж дамжуулахыг авч үзье. Энэ тохиолдолд найдвартай дамжуулалтаар a 1 тэмдгийг дамжуулахдаа бид олж авна гэж үздэг jАнхны болон нөхцөлт магадлалын үржвэрээр тооцно.

Нөхцөлт магадлалыг Байесийн томъёог ашиглан гаргадаг. Тиймээс эх сурвалж ба хүлээн авагчийн энтропийг тооцоолох бүх өгөгдөл байдаг.

Харилцан энтропи нь матрицын бүх магадлалыг мөр (эсвэл багана) дээр дараалан нийлж, тэдгээрийн логарифмаар үржүүлж тооцдог.

Хэмжилтийн нэгж нь бит/хоёр тэмдэгт бөгөөд үүнийг харилцан энтропи нь илгээсэн болон хүлээн авсан хос тэмдэгт ногдох тодорхойгүй байдлыг тодорхойлдогтой холбон тайлбарладаг. Энгийн хувиргалтаар бид бас олж авдаг

Харилцан энтропи нь өмчтэй байдаг мэдээллийн бүрэн байдал- үүнээс та авч үзэж буй бүх тоо хэмжээг авах боломжтой.

Санамсаргүй хэмжигдэхүүний энтропи болон мэдээллийн хэмжээг тооцоолох Шенноны томъёог (3.3) авч үзээд бид санамсаргүй хэмжигдэхүүн (X)-ийн талаарх мэдээлэл ажиглагчид шууд ирдэг гэж үзсэн. Гэсэн хэдий ч бид дүрмээр бол бидний сонирхдог санамсаргүй хэмжигдэхүүн (X)-ийн тухай бус харин X-тэй стохастик байдлаар холбоотой өөр нэг (Y) тухай мэдээллийг авдаг. Санамсаргүй хэмжигдэхүүнүүдийн ийм холболт нь функциональ холболтоос ялгаатай бөгөөд нэг утгын утга тус бүр нь өөр утгын нэг сайн тодорхойлогдсон утгатай тохирдог. X ба Y хоёр санамсаргүй хэмжигдэхүүнүүдийн хоорондох стохастик (магадлал) холболт нь тэдгээрийн аль нэгнийх нь өөрчлөлт нь нөгөөгийн үнэд нөлөөлдөг гэсэн үг боловч X-ийн утгыг мэдэхийн тулд утгыг зөв зааж өгөх боломжгүй юм. Y нь зөвхөн Y утгын өөрчлөлтийн хандлагыг зааж өгч болно.

B-г үзье санамсаргүй үйл явдал; p(B) – түүний үүсэх магадлал; N-г авдаг санамсаргүй хэмжигдэхүүнийг X-ээр тэмдэглэе өөр өөр утгатай(x 1 , x 2 , … x N ) ба A k-ээр дамжуулан X санамсаргүй хэмжигдэхүүн x k утгыг авах үйл явдал:

A k = ( X = x k ), k=1,2, …N ;

Бид A k үйл явдлын магадлалыг p(A k) гэж тэмдэглэнэ. Зарим үйл явдлын магадлал нь өөр үйл явдал болсон эсэхээс хамаарч өөрчлөгдөж болно. В үйл явдал болсон гэсэн таамаглалаар тооцсон А k үзэгдлийн магадлалыг p B (A k) A k үзэгдлийн нөхцөлт магадлал гэнэ, энэ тохиолдолд:

Хэрэв А k үзэгдлийн тохиолдох магадлал нь В үйл явдал болсон эсэхээс хамаарахгүй бол A k ба B үйл явдлуудыг бие даасан гэж нэрлэдэг. магадлал p(A k).

Тодорхойлолт. В нөхцөл дэх X санамсаргүй хэмжигдэхүүний нөхцөлт энтропи нь хэмжигдэхүүн юм

(4.2)

Шэннон (3.3) томъёоноос ялгаатай нь бид магадлалын оронд p(A k) ашигладаг. нөхцөлт магадлал p B (A k).

Одоо Y-г өөр нэг санамсаргүй хэмжигдэхүүн (y 1, y 2, ... y M) авч үзье. Y санамсаргүй хэмжигдэхүүн y j утгыг авах үйл явдлыг B j-ээр тэмдэглэе.

B j = ( Y = y j ), j=1, 2,... М.

Бид B j үйл явдлын магадлалыг p(B j) гэж тэмдэглэнэ.

Тодорхойлолт. Х санамсаргүй хэмжигдэхүүний нөхцөлт энтропи at утгыг тохируулахсанамсаргүй хэмжигдэхүүн Y нь хэмжигдэхүүн H Y (X)

(4.3)

(4.3) томъёог өөрчилье:

Формула (4.3) дараах хэлбэртэй байна.

(4.4)

Y санамсаргүй хэмжигдэхүүнийг ажигласнаар олж авсан X санамсаргүй хэмжигдэхүүний талаарх мэдээллийн хэмжээг тооцоолъё. Энэ хэмжээний мэдээллийн I(X,Y) нь Y санамсаргүй хэмжигдэхүүнийг ажиглах үед X санамсаргүй хэмжигдэхүүний энтропийн бууралттай тэнцүү байна:

H(X) ба H Y (X)-ийн илэрхийллүүдийг (15)-д орлуулъя:

Эхний нийлбэрт бид p(A k)=p(A k B 1)+ p(A k B 2)+ p(A k B 3)…+ p(A k B M) гэж солино. Энэ тэгш байдал үнэхээр явагддаг, учир нь A k B 1 , A k B 2 , … A k B M үйл явдлууд нь хосоороо үл нийцэх ба A k тохиолдвол тэдгээрийн аль нэг нь тохиолдох болно. Эсрэгээр, хэрэв B j-ийн аль нэг нь тохиолдвол A k бас тохиолдоно. Өөрчлөлтийг үргэлжлүүлснээр бид дараахь зүйлийг олж авна.

Тиймээс бид өөр санамсаргүй хэмжигдэхүүн Y-г ажиглахдаа X санамсаргүй хэмжигдэхүүний талаарх мэдээллийн хэмжээг тооцоолох томъёотой байна.

(4.6)

Хэрэв санамсаргүй хэмжигдэхүүн(эсвэл үйл явдлууд) нь бие даасан байвал тэдгээрийн хувьд p(A k B j) = p(A k)p(B j) хамаарал явагдана - хоёр үйл явдлын хамтдаа тохиолдох магадлал нь магадлалын үржвэртэй тэнцүү байна. эдгээр үйл явдлууд.

I(X,Y) утгын тухайд дараах мэдэгдлүүд үнэн байна.

Бие даасан санамсаргүй хэмжигдэхүүнүүдийн хувьд бид олж авдаг

Энэ нь санамсаргүй хэмжигдэхүүн Y-г ажиглах нь X санамсаргүй хэмжигдэхүүний талаарх мэдээллийг авахад ямар ч давуу тал өгөхгүй гэсэн үг юм.

Бусад тохиолдолд I(X,Y) >0 байх ба дараах тэгш бус байдал биелнэ.

Y=F(X) функциональ холболт байгаа тохиолдолд тэгш байдал бий болно. Энэ тохиолдолд Y-г ажиглах нь өгдөг бүрэн мэдээлэлтухай X. Хэрэв Y=X бол I(X,X) = H(X).

I(X,Y) хэмжигдэхүүн нь тэгш хэмтэй: I(X,Y) = I(Y,X). Энэ нь санамсаргүй хэмжигдэхүүн Y-ийн ажиглалт нь санамсаргүй хэмжигдэхүүн Х-ийн тухай Х санамсаргүй хэмжигдэхүүнийг ажиглахад Y санамсаргүй хэмжигдэхүүнтэй ижил хэмжээний мэдээллийг өгдөг гэсэн үг юм. Хэрэв бид стохастик хамааралтай хоёр санамсаргүй хэмжигдэхүүнийг авч үзэх юм бол Мэдээллийн онолын тусламжтайгаар аль нь шалтгаан, аль нь үр дагавар болохыг тогтоох боломжгүй юм.

Нөхцөлт энтропи

Цогцолборын хамтарсан энтропийг олъё мэдээллийн систем(A, B найрлага) хэрэв тэдгээрийн мессеж нь бие даасан биш бол, i.e. хэрэв В мессежийн агуулгад А мессеж нөлөөлсөн бол.

Жишээлбэл, Comet болон Rocket хөлбөмбөгийн багуудын тоглолтын тухай "Сүүлт од яллаа" гэсэн мессеж нь Рокет хэрхэн тоглосон талаарх эргэлзээг бүрэн арилгадаг.

Өөр нэг жишээ: А мессеж нь эрэгтэй хүний ​​тухай мэдээлэл (овог, нэр, овог нэр, төрсөн он, төрсөн газар, боловсрол, гэрийн хаяг, утасны дугаар), мессежийг агуулна. INэмэгтэйн тухай ижил төстэй мэдээллийг агуулсан - дурдсан хүний ​​эхнэр. Мэдээжийн хэрэг мессеж INхэсэгчлэн А мэдээллийг агуулсан, тухайлбал: эхнэрийн овог, гэрийн хаяг, утасны дугаар нь нөхрийнхөө овог, гэрийн хаяг, утасны дугаартай давхцах магадлалтай, түүнчлэн түүний төрсөн он, хамгийн их магадлалтай байдаг магадлалын тооцоолол. нөхрийн төрсөн жил ойртож байна. Тиймээс мессеж INнь бидний хувьд А мессежээс бага мэдээлэл агуулдаг бөгөөд хоёр мессежийн нийлмэл мэдээлэл нь тусдаа мессежүүдийн мэдээллийн энгийн нийлбэр биш юм.

Эх сурвалжаа өгөөч Ачуулга үүсгэдэг Мамессежүүд (a, a 2 ,..., a Ma), эх сурвалж нь чуулга үүсгэдэг Мбмессеж (b 2, b 2,..., bdd,) болон эх сурвалжууд нь хамааралтай. Ерөнхий цагаан толгойЭх сурвалж нь (a, b;) хэлбэрийн хосуудын багц бөгөөд цагаан толгойн нийт хүч нь: Ма X Мб.

Нарийн төвөгтэй мэдээллийн системийн энтропи (хоёр эх сурвалжаас) тэнцүү байна

Түүнээс хойш А ба Бхамааралтай, тэгвэл А

Үүнийг энтропийн илэрхийлэлд орлуулах нарийн төвөгтэй систем, бид авах:

Эхний улиралд индекс j-аас л авах боломжтой IN,нийлбэрийн дарааллыг өөрчилснөөр бид маягтын нэр томъёог олж авна ), найдвартай үйл явдлыг тодорхойлдог тул 1-тэй тэнцүү байна

(мэдээлэлүүдийн аль нэг нь ямар ч тохиолдолд хэрэгждэг). Тиймээс эхний нэр томъёо нь дараахтай тэнцүү байна.

Хоёр дахь хугацаанд, маягтын нөхцөл

а мэдээ хэрэгжсэн тохиолдолд В эхийн энтропийн утгыг агуулсан байх; - бид үүнийг хэсэгчилсэн нөхцөлт энтропи гэж нэрлэх болно. Хэрэв та орвол энэ үзэл баримтлалболон түүний тэмдэглэгээг ашиглавал хоёр дахь нэр томъёо нь дараах хэлбэртэй байна.

эсвэл илүү дэлгэрэнгүй

Энд H(B |A) нь эх үүсвэрийн нийт нөхцөлт энтропи юм IN A эх үүсвэртэй харьцуулахад. Бид эцэст нь нийлмэл системийн энтропийн хувьд:

Үр дүнгийн илэрхийлэл нь ерөнхий дүрэмнарийн төвөгтэй системийн энтропийг олох. Эх сурвалжууд бие даасан байх тохиолдолд (2.9) илэрхийлэл нь (2.11)-ийн онцгой тохиолдол болох нь тодорхой байна. А ба Б.

Нөхцөлт энтропийн тухайд дараах мэдэгдлийг хийж болно.

1. Нөхцөлт энтропи нь сөрөг бус хэмжигдэхүүн юм. Түүнээс гадна, H(B |A) = 0 зөвхөн ямар нэгэн мессеж байвал Амессежийг бүрэн тодорхойлдог IN,тэдгээр.

Энэ тохиолдолд H(A, B) = H (A).

2. Хэрэв эх сурвалжууд А ба INбие даасан, дараа нь H(B |A) = H(B) бөгөөд энэ нь болж хувирна хамгийн өндөр үнэ цэнэнөхцөлт энтропи. Өөрөөр хэлбэл, А эх сурвалжийн мэдээ нь В эх сурвалжийн мэдээний тодорхойгүй байдлыг нэмэгдүүлж чадахгүй; Энэ нь ямар ч нөлөө үзүүлэхгүй (хэрэв эх үүсвэрүүд нь бие даасан байвал) эсвэл В-ийн энтропийг бууруулж болно.

Дээрх мэдэгдлүүдийг нэг тэгш бус байдлаар нэгтгэж болно.

тэдгээр. нөхцөлт энтропи болзолгүй энтропиас хэтрэхгүй.

3. (2.11) ба (2.12)-ын хамаарлаас дараах нь гарч байна

Түүнээс гадна А, В эх сурвалжууд бие даасан байх тохиолдолд л тэгш байдал хэрэгжинэ.

Энтропи эх үүсвэр тасралтгүй мессежүүд

Хаана байгаа системийг авч үзье чанарын шинж чанаруудтөлөв байнга өөрчлөгддөг ( тасралтгүй дохио). Систем x төлөвт байх магадлалыг (өөрөөр хэлбэл дохио нь x утгыг авдаг) магадлалын нягтралаар тодорхойлогддог /(x). Ийм мессежийн энтропийг олохын тулд бид дохионы боломжит өөрчлөлтийн мужийг Dx хэмжээтэй дискретт хуваана. i-р дискретт системийг олох магадлал тэнцүү байна